Optimal and online preemptive scheduling on uniformly related machines

DOI10.1007/s10951-009-0119-7zbMath1176.90208OpenAlexW2144626912MaRDI QIDQ1041344

Tomáš Ebenlendr, Jiří Sgall

Publication date: 2 December 2009

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-009-0119-7

zbMATH Keywords

online schedulingpreemptionuniformly related machines

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (8)

A survey on makespan minimization in semi-online environments ⋮ Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Robust algorithms for preemptive scheduling ⋮ Semi-online preemptive scheduling: one algorithm for all variants ⋮ Algorithms with limited number of preemptions for scheduling on parallel machines ⋮ Preemptive online scheduling: Optimal algorithms for all speeds ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes

Cites Work

• Unnamed Item
• Minimizing makespan and preemption costs on a system of uniform machines
• Preemptive online scheduling: Optimal algorithms for all speeds
• Preemptive on-line scheduling for two uniform processors
• Bin stretching revisited
• New algorithms for related machines with temporary jobs.
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• An optimal algorithm for preemptive on-line scheduling
• A lower bound for on-line scheduling on uniformly related machines
• A comment on scheduling on uniform machines under chain-type precedence constraints
• Scheduling Independent Tasks on Uniform Processors
• Tighter Bounds for LPT Scheduling on Uniform Processors
• Bounds for List Schedules on Uniform Processors
• A Level Algorithm for Preemptive Scheduling
• Preemptive Scheduling of Uniform Processor Systems
• A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Scheduling Parallel Machines On-Line
• On-Line Load Balancing for Related Machines
• STACS 2004
• Randomized on-line scheduling on two uniform machines
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios

This page was built for publication: Optimal and online preemptive scheduling on uniformly related machines