Parallel machine covering with limited number of preemptions

DOI10.1007/S11766-014-3138-XMaRDI QIDQ462268zbMATHOpenAlexFDO

Authors Yiwei Jiang, Jueliang Hu, Zewei Weng, Yuqing Zhu

Publication date 3 November 2014

Published in Applied Mathematics. Series B (English Edition) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11766-014-3138-x

zbMATH Keywords

approximation algorithmpreemptive schedulingmachine coveringworst case ratio

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• Preemptive machine covering on parallel machines
• Algorithms with limited number of preemptions for scheduling on parallel machines
• Algorithms with limited number of preemptions for scheduling on parallel machines
• A combination of parallel machine scheduling and the covering problem
• On the complexity of scheduling unrelated parallel machines with limited preemptions
• Combination of parallel machine scheduling and vertex cover
• scientific article; zbMATH DE number 1187165
• Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
• Optimal preemptive scheduling on a fixed number of identical parallel machines
• Power of preemption for minimizing total completion time on uniform parallel machines

Cites work

• scientific article; zbMATH DE number 1182760 (Why is no real title available?)
• A Level Algorithm for Preemptive Scheduling
• A comment on scheduling on uniform machines under chain-type precedence constraints
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Algorithms with limited number of preemptions for scheduling on parallel machines
• Bounds on Multiprocessing Timing Anomalies
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
• Parallel Processor Scheduling with Limited Number of Preemptions
• Preemptive Scheduling of Uniform Processor Systems
• Preemptive machine covering on parallel machines
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Scheduling with deadlines and loss functions
• The exact LPT-bound for maximizing the minimum completion time
• The maximum gain of increasing the number of preemptions in multiprocessor scheduling
• The power of preemption on unrelated machines and applications to scheduling orders
• Tight bounds for bandwidth allocation on two links

Cited in

(5)

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

This page was built for publication: Parallel machine covering with limited number of preemptions

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