Algorithms with limited number of preemptions for scheduling on parallel machines

DOI10.1007/S10878-012-9545-0zbMATH Open1296.90052OpenAlexW2294497340MaRDI QIDQ2015808FDOQ2015808

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

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

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)

Cites Work

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

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)