A lower bound on deterministic online algorithms for scheduling on related machines without preemption
From MaRDI portal
Publication:2344208
DOI10.1007/s00224-013-9451-6zbMath1328.68314OpenAlexW1984292487MaRDI QIDQ2344208
Publication date: 12 May 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-013-9451-6
Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)
Related Items
A survey on makespan minimization in semi-online environments ⋮ Semi-online scheduling: a survey ⋮ Online load balancing on uniform machines with limited migration ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ Starting time minimization for the maximum job variant ⋮ Online makespan scheduling with job migration on uniform machines ⋮ Tight lower bounds for semi-online scheduling on two uniform machines with known optimum
Cites Work
- Lower bounds for online makespan minimization on a small number of related machines
- 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.
- A lower bound for on-line scheduling on uniformly related machines
- Bounds for List Schedules on Uniform Processors
- On-line routing of virtual circuits with applications to load balancing and machine scheduling
- On-Line Load Balancing for Related Machines
- On-line load balancing for related machines
- Randomized on-line scheduling on two uniform machines
