Power of Preemption for Minimizing Total Completion Time on Uniform Parallel Machines

DOI10.1137/16M1066610zbMath1354.90049OpenAlexW2569786510MaRDI QIDQ2957687

Leah Epstein, Asaf Levin, Alan J. Soper, Vitaly A. Strusevich

Publication date: 27 January 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1066610

zbMATH Keywords

schedulingtotal completion timeuniformly related machinespower of preemption

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Discrete mathematics in relation to computer science (68R99)

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, The benefit of preemption for single machine scheduling so as to minimize total weighted completion time, Preemptive and non-preemptive scheduling on two unrelated parallel machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comment on scheduling on uniform machines under chain-type precedence constraints
• Algorithms with limited number of preemptions for scheduling on parallel machines
• Single parameter analysis of power of preemption on two and three uniform machines
• Scheduling with Deadlines and Loss Functions
• Power of Preemption on Uniform Parallel Machines
• Approximability of Average Completion Time Scheduling on Unrelated Machines
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Preemptive Scheduling of Uniform Processor Systems
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Parallel Processor Scheduling with Limited Number of Preemptions
• Scheduling independent tasks to reduce mean finishing time
• Scheduling Unrelated Machines by Randomized Rounding
• Parallel Machine Scheduling: Impact of Adding Extra Machines
• Technical Note—Minimizing Average Flow Time with Parallel Machines
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders