A lower bound for randomized on-line multiprocessor scheduling

DOI10.1016/S0020-0190(97)00093-8MaRDI QIDQ287130zbMATHOpenAlexFDO

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

zbMATH Keywords

randomizationonline algorithmsschedulingcombinatorial problemsworst-case bounds

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• scientific article; zbMATH DE number 1003243 (Why is no real title available?)
• A better lower bound for on-line scheduling
• A lower bound for randomized on-line scheduling algorithms
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• An optimal algorithm for preemptive on-line scheduling
• Bounds for Certain Multiprocessing Anomalies
• New algorithms for an ancient scheduling problem.

Cited in

(29)

• Optimal semi-online preemptive algorithms for machine covering on two uniform machines
• Online interval scheduling: Randomized and multiprocessor cases
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Preemptive multiprocessor scheduling with rejection
• Preemptive machine covering on parallel machines
• Robust algorithms for preemptive scheduling
• Randomized priority algorithms
• 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
• An optimal online algorithm for scheduling two machines with release times
• Semi-online scheduling revisited
• On-line scheduling revisited
• Semi-online scheduling with decreasing job sizes
• Resource augmentation in load balancing.
• A better lower bound for on-line scheduling
• A lower bound for randomized on-line scheduling algorithms
• A lower bound on the period length of a distributed scheduler
• Preemptive online scheduling: Optimal algorithms for all speeds
• Lower bound algorithms for multiprocessor task scheduling with ready times
• Online algorithms with advice for bin packing and scheduling problems
• Scheduling In the random-order model
• 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
• Online randomized multiprocessor scheduling
• Parallel solutions for preemptive makespan scheduling on two identical machines
• Optimal on-line algorithms to minimize makespan on two machines with resource augmentation

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)