Preemptive online scheduling: Optimal algorithms for all speeds
From MaRDI portal
Publication:1016520
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
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
