Lower bounds for online makespan minimization on a small number of related machines
From MaRDI portal
Publication:398887
DOI10.1007/S10951-012-0288-7zbMath1297.90048OpenAlexW2129652129MaRDI QIDQ398887
Jarett Schwartz, József Békési, Jiří Sgall, Łukasz Jeż
Publication date: 18 August 2014
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10951-012-0288-7
Related Items (3)
A survey on makespan minimization in semi-online environments ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ A lower bound on deterministic online algorithms for scheduling on related machines without preemption
Cites Work
- Unnamed Item
- Semi-online preemptive scheduling: one algorithm for all variants
- Competitive ratio of list scheduling on uniform machines and randomized heuristics
- On the optimality of list scheduling for online uniform machines scheduling
- Online scheduling on three uniform machines
- Preemptive online scheduling: Optimal algorithms for all speeds
- New algorithms for related machines with temporary jobs.
- On-line scheduling revisited
- New lower and upper bounds for on-line scheduling
- A lower bound for on-line scheduling on uniformly related machines
- A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption
- Bounds for List Schedules on Uniform Processors
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
- On-line routing of virtual circuits with applications to load balancing and machine scheduling
- On-Line Load Balancing for Related Machines
- Bounds for Certain Multiprocessing Anomalies
- Randomized on-line scheduling on two uniform machines
This page was built for publication: Lower bounds for online makespan minimization on a small number of related machines
