A lower bound for randomized on-line scheduling algorithms
DOI10.1016/0020-0190(94)00110-3zbMATH Open0821.68011OpenAlexW1965521122MaRDI QIDQ1336752FDOQ1336752
Authors: Bo Chen, Gerhard J. Woeginger, André van Vliet 
Publication date: 19 September 1995
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)00110-3
Recommendations
- A lower bound for randomized on-line multiprocessor scheduling
- Randomized algorithms for on-line scheduling problems: How low can't you go?
- scientific article; zbMATH DE number 1894930
- Randomized algorithms for that ancient scheduling problem
- A lower bound for on-line scheduling on uniformly related machines
Combinatorics in computer science (68R05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed algorithms (68W15) Network design and communication in computer systems (68M10)
Cites Work
Cited In (31)
- Semi-online scheduling with decreasing job sizes
- Title not available (Why is that?)
- 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
- On-line bin-stretching
- Preemptive online scheduling: Optimal algorithms for all speeds
- Resource augmentation in load balancing.
- A lower bound for randomized on-line multiprocessor scheduling
- Barely random algorithms for multiprocessor scheduling
- Randomized algorithms for on-line scheduling problems: How low can't you go?
- Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
- New algorithms for related machines with temporary jobs.
- On-line scheduling revisited
- Scheduling In the random-order model
- On-line load balancing for related machines
- On the value of job migration in online makespan minimization
- Preemptive multiprocessor scheduling with rejection
- An on-line LS algorithm for some \(Q_m|r_j|C_{\max}\) scheduling
- A lower bound for on-line scheduling on uniformly related machines
- A better lower bound for on-line scheduling
- Preemptive scheduling on a small number of hierarchical machines
- Scheduling with limited machine availability
- Randomized on-line scheduling on three processors.
- A guessing game and randomized online algorithms
- An optimal online algorithm for scheduling two machines with release times
- Randomized on-line scheduling similar jobs to minimize makespan on two identical processors
- Improved lower bounds for online scheduling to minimize total stretch
- Randomized algorithms for that ancient scheduling problem
- Randomized priority algorithms
This page was built for publication: A lower bound for randomized on-line scheduling algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336752)
