Algorithms with limited number of preemptions for scheduling on parallel machines

DOI10.1007/S10878-012-9545-0MaRDI QIDQ2015808zbMATH OpenOpenAlexFDO

Authors Yiwei Jiang, Zewei Weng, Jueliang Hu

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

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

Recommendations

• Algorithms with limited number of preemptions for scheduling on parallel machines
• Parallel machine covering with limited number of preemptions
• Parallel Processor Scheduling with Limited Number of Preemptions
• Schedules with a single preemption on uniform parallel machines
• Preemptive and non-preemptive scheduling on two unrelated parallel machines

Cites work

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

Cited in

(10)

• Parametric analysis of the quality of single preemption schedules on three uniform parallel machines
• On a scheduling problem where a job can be executed only by a limited number of processors
• Preemptive and non-preemptive scheduling on two unrelated parallel machines
• Parallel machine covering with limited number of preemptions
• Preemptive scheduling on a small number of hierarchical 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
• Algorithms with limited number of preemptions for scheduling on parallel machines
• Parallel Processor Scheduling with Limited Number of Preemptions

This page was built for publication: Algorithms with limited number of preemptions for scheduling on parallel machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2015808)