Preemptive online scheduling: Optimal algorithms for all speeds

DOI10.1007/s00453-008-9235-6zbMath1166.90007OpenAlexW2594258165MaRDI QIDQ1016520

Jiří Sgall, Tomáš Ebenlendr, Wojciech Jawor

Publication date: 6 May 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9235-6

zbMATH Keywords

schedulingonline algorithmsmakespan

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Randomized algorithms (68W20)

Related Items

Better Algorithms for Online Bin Stretching ⋮ Semi-online scheduling: a survey ⋮ A two-phase algorithm for bin stretching with stretching factor 1.5 ⋮ Lower bounds for online makespan minimization on a small number of related machines ⋮ Preemptive online scheduling with rejection of unit jobs on two uniformly related machines ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Online bin stretching with three bins ⋮ Unnamed Item ⋮ Robust algorithms for preemptive scheduling ⋮ On the optimality of list scheduling for online uniform machines scheduling ⋮ Semi-online preemptive scheduling: one algorithm for all variants ⋮ On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes ⋮ Optimal and online preemptive scheduling on uniformly related machines ⋮ A lower bound on deterministic online algorithms for scheduling on related machines without preemption

Cites Work

• A lower bound for randomized on-line multiprocessor scheduling
• Optimal and online preemptive scheduling on uniformly related machines
• Preemptive on-line scheduling for two uniform processors
• A lower bound for randomized on-line scheduling algorithms
• Randomized on-line scheduling on three processors.
• On-line scheduling revisited
• An optimal algorithm for preemptive on-line scheduling
• A lower bound for on-line scheduling on uniformly related machines
• Scheduling with Deadlines and Loss Functions
• On randomized online scheduling
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A Level Algorithm for Preemptive Scheduling
• Preemptive Scheduling of Uniform Processor Systems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• On-Line Load Balancing for Related Machines
• STACS 2004
• Bounds for Certain Multiprocessing Anomalies
• Randomized on-line scheduling on two uniform machines
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios