A lower bound for randomized on-line multiprocessor scheduling
DOI10.1016/S0020-0190(97)00093-8zbMATH Open1336.68107OpenAlexW1999476761MaRDI QIDQ287130FDOQ287130
Authors: Jiří Sgall 
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
Recommendations
- A lower bound for randomized on-line scheduling algorithms
- A better lower bound for on-line scheduling
- A lower bound for on-line scheduling on uniformly related machines
- Randomized algorithms for on-line scheduling problems: How low can't you go?
- Lower bounds and semi on-line multiprocessor scheduling
Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Bounds for Certain Multiprocessing Anomalies
- 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
- Title not available (Why is that?)
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
- Title not available (Why is that?)
- New algorithms for an ancient scheduling problem.
Cited In (30)
- Semi-online scheduling with decreasing job sizes
- A lower bound on the period length of a distributed scheduler
- Scheduling with testing on multiple identical parallel machines
- Semi-online scheduling revisited
- Online algorithms with advice for bin packing and scheduling problems
- Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
- Preemptive online scheduling: Optimal algorithms for all speeds
- Online interval scheduling: Randomized and multiprocessor cases
- Resource augmentation in load balancing.
- Optimal semi-online preemptive algorithms for machine covering on two uniform machines
- Randomized algorithms for on-line scheduling problems: How low can't you go?
- On-line scheduling revisited
- Scheduling In the random-order model
- On the value of job migration in online makespan minimization
- Preemptive multiprocessor scheduling with rejection
- Optimal preemptive semi-online scheduling to minimize makespan on two related machines
- A lower bound for on-line scheduling on uniformly related machines
- A better lower bound for on-line scheduling
- A lower bound for randomized on-line scheduling algorithms
- Preemptive scheduling on a small number of hierarchical machines
- Robust algorithms for preemptive scheduling
- Randomized on-line scheduling on three processors.
- Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures
- An optimal online algorithm for scheduling two machines with release times
- Lower bound algorithms for multiprocessor task scheduling with ready times
- Optimal on-line algorithms to minimize makespan on two machines with resource augmentation
- Online randomized multiprocessor scheduling
- Preemptive machine covering on parallel machines
- Randomized priority algorithms
- Parallel solutions for preemptive makespan scheduling on two identical machines
This page was built for publication: A lower bound for randomized on-line multiprocessor scheduling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287130)
