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 (15)

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

This page was built for publication: Preemptive online scheduling: Optimal algorithms for all speeds