A lower bound for randomized on-line scheduling algorithms

DOI10.1016/0020-0190(94)00110-3MaRDI QIDQ1336752zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

randomizationschedulingcombinatorial problemson-line algorithmsworst case bounds

Mathematics Subject Classification ID

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)

Recommendations

• A lower bound for randomized on-line multiprocessor scheduling
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• Publication:4801952
• Randomized algorithms for that ancient scheduling problem
• A lower bound for on-line scheduling on uniformly related machines

Cites work

• Bounds for Certain Multiprocessing Anomalies

Cited in

(30)

• Preemptive multiprocessor scheduling with rejection
• Randomized priority algorithms
• An on-line LS algorithm for some \(Q_m|r_j|C_{\max}\) scheduling
• Scheduling with testing on multiple identical parallel machines
• Randomized on-line scheduling on three processors.
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
• A lower bound for randomized on-line multiprocessor scheduling
• An optimal online algorithm for scheduling two machines with release times
• Semi-online scheduling revisited
• Improved lower bounds for online scheduling to minimize total stretch
• On-line scheduling revisited
• On-line bin-stretching
• Semi-online scheduling with decreasing job sizes
• Resource augmentation in load balancing.
• A better lower bound for on-line scheduling
• Barely random algorithms for multiprocessor scheduling
• Scheduling with limited machine availability
• Randomized algorithms for that ancient scheduling problem
• Preemptive online scheduling: Optimal algorithms for all speeds
• Online makespan minimization: the power of restart
• A guessing game and randomized online algorithms
• Online algorithms with advice for bin packing and scheduling problems
• Scheduling In the random-order model
• Randomized on-line scheduling similar jobs to minimize makespan on two identical processors
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• A lower bound for on-line scheduling on uniformly related machines
• Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
• Preemptive scheduling on a small number of hierarchical machines
• On-line load balancing for related machines
• New algorithms for related machines with temporary jobs.

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)