A lower bound for randomized on-line multiprocessor scheduling
From MaRDI portal
Publication:287130
DOI10.1016/S0020-0190(97)00093-8zbMath1336.68107OpenAlexW1999476761MaRDI QIDQ287130
Publication date: 26 May 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00093-8
Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (23)
Scheduling with testing on multiple identical parallel machines ⋮ Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures ⋮ On the value of job migration in online makespan minimization ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Semi-online scheduling revisited ⋮ Randomized on-line scheduling on three processors. ⋮ Preemptive scheduling on a small number of hierarchical machines ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ Robust algorithms for preemptive scheduling ⋮ A lower bound for on-line scheduling on uniformly related machines ⋮ Scheduling In the random-order model ⋮ Online algorithms with advice for bin packing and scheduling problems ⋮ Semi-online scheduling with decreasing job sizes ⋮ Randomized priority algorithms ⋮ Optimal semi-online preemptive algorithms for machine covering on two uniform machines ⋮ Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios ⋮ Preemptive multiprocessor scheduling with rejection ⋮ An optimal online algorithm for scheduling two machines with release times ⋮ Preemptive online scheduling: Optimal algorithms for all speeds ⋮ Resource augmentation in load balancing. ⋮ On-line scheduling revisited ⋮ Preemptive machine covering on parallel machines ⋮ Optimal preemptive semi-online scheduling to minimize makespan on two related machines
Cites Work
- Unnamed Item
- Unnamed Item
- New algorithms for an ancient scheduling problem.
- A better lower bound for on-line scheduling
- A lower bound for randomized on-line scheduling algorithms
- An optimal algorithm for preemptive on-line scheduling
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
- Bounds for Certain Multiprocessing Anomalies
This page was built for publication: A lower bound for randomized on-line multiprocessor scheduling
