Algorithms with limited number of preemptions for scheduling on parallel machines

DOI10.1007/s10878-012-9545-0zbMath1296.90052OpenAlexW2294497340MaRDI QIDQ2015808

Jueliang Hu, Yiwei Jiang, Zewei Weng

Publication date: 24 June 2014

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9545-0

zbMATH Keywords

approximation algorithmmakespanworst case ratio\(i\)-preemptive scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Parametric analysis of the quality of single preemption schedules on three uniform parallel machines, Schedules with a single preemption on uniform parallel machines, The benefit of preemption with respect to the \(\ell_p\) norm, Power of Preemption for Minimizing Total Completion Time on Uniform Parallel Machines, Preemptive and non-preemptive scheduling on two unrelated parallel machines

Cites Work

• Minimizing makespan and preemption costs on a system of uniform machines
• Optimal and online preemptive scheduling on uniformly related machines
• A comment on scheduling on uniform machines under chain-type precedence constraints
• The maximum gain of increasing the number of preemptions in multiprocessor scheduling
• Scheduling with Deadlines and Loss Functions
• Some Results on Liu’s Conjecture
• A Level Algorithm for Preemptive Scheduling
• Preemptive Scheduling of Uniform Processor Systems
• Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling
• Parallel Processor Scheduling with Limited Number of Preemptions
• Bounds on Multiprocessing Timing Anomalies
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders