Optimal preemptive semi-online scheduling to minimize makespan on two related machines
From MaRDI portal
Publication:1866010
DOI10.1016/S0167-6377(02)00179-7zbMath1049.90024MaRDI QIDQ1866010
Leah Epstein, Lene Monrad Favrholdt
Publication date: 3 April 2003
Published in: Operations Research Letters (Search for Journal in Brave)
Related Items
Optimal preemptive semi-online scheduling on two uniform processors ⋮ SEMI-ONLINE MACHINE COVERING ⋮ Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines ⋮ Disjoint Path Allocation with Sublinear Advice ⋮ ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER ⋮ Semi-online scheduling: a survey ⋮ Preemptive online scheduling with rejection of unit jobs on two uniformly related machines ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ The online knapsack problem: advice and randomization ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ Semi-online scheduling on two uniform machines with the known largest size ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information ⋮ Semi-online scheduling on two uniform processors ⋮ Semi-online preemptive scheduling: one algorithm for all variants ⋮ Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data ⋮ Optimal semi-online preemptive algorithms for machine covering on two uniform machines ⋮ Optimal online algorithms for scheduling on two identical machines under a grade of service ⋮ Online makespan scheduling with job migration on uniform machines ⋮ Optimal and online preemptive scheduling on uniformly related machines ⋮ Preemptive machine covering on parallel machines
Cites Work
- Unnamed Item
- A lower bound for randomized on-line multiprocessor scheduling
- Online algorithms. The state of the art
- Preemptive on-line scheduling for two uniform processors
- An optimal algorithm for preemptive on-line scheduling
- A lower bound for on-line scheduling on uniformly related machines
- Scheduling Independent Tasks on Uniform Processors
- Tighter Bounds for LPT Scheduling on Uniform Processors
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
- A Level Algorithm for Preemptive Scheduling
- A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- Semi-online scheduling with decreasing job sizes
- Randomized on-line scheduling on two uniform machines
- Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
- Preemptive multiprocessor scheduling with rejection