Lower bounds for on-line single-machine scheduling.

DOI10.1016/S0304-3975(02)00488-7zbMath1040.68007OpenAlexW2058876827MaRDI QIDQ1874403

Rob van Stee, Leah Epstein

Publication date: 25 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00488-7

zbMATH Keywords

randomized algorithmsscheduling jobs

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20)

Related Items

Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart ⋮ Online scheduling with delivery time on a bounded parallel batch machine with limited restart ⋮ On competitive analysis for polling systems ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan ⋮ Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart ⋮ Single machine batch scheduling with release times ⋮ Online scheduling in a parallel batch processing system to minimize makespan using restarts

Cites Work

• The power of \(\alpha\)-points in preemptive single machine scheduling.
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• Approximation Techniques for Average Completion Time Scheduling
• Single Machine Scheduling with Release Dates
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Algorithms for minimizing weighted flow time
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item