On the Robustness of Graham’s Algorithm for Online Scheduling

DOI10.1007/978-3-540-73951-7_31MaRDI QIDQ3603540zbMATH OpenOpenAlexFDO

Authors Michael Gatto, Peter Widmayer

Publication date 17 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_31

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Recommendations

• On robust online scheduling algorithms
• An experimental study of online scheduling algorithms
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
• Performance guarantees for scheduling algorithms under perturbed machine speeds

Cited in

(2)

• Comparing deterministic, robust and online scheduling using entropy
• On robust online scheduling algorithms

This page was built for publication: On the Robustness of Graham’s Algorithm for Online Scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3603540)