Lower bounds for on-line single-machine scheduling.

DOI10.1016/S0304-3975(02)00488-7MaRDI QIDQ1874403zbMATHOpenAlexFDO

Authors Leah Epstein, Rob van Stee

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

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

Recommendations

• scientific article; zbMATH DE number 1834660
• A lower bound for on-line scheduling on uniformly related machines
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• A note on on-line scheduling with precedence constraints on identical machines
• scientific article; zbMATH DE number 1182764

Cites work

• scientific article; zbMATH DE number 3883931 (Why is no real title available?)
• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• scientific article; zbMATH DE number 1256760 (Why is no real title available?)
• scientific article; zbMATH DE number 1094690 (Why is no real title available?)
• scientific article; zbMATH DE number 1947447 (Why is no real title available?)
• scientific article; zbMATH DE number 2119710 (Why is no real title available?)
• scientific article; zbMATH DE number 6472636 (Why is no real title available?)
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Algorithms for minimizing weighted flow time
• Approximation techniques for average completion time scheduling
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• Single machine scheduling with release dates
• The power of \(\alpha\)-points in preemptive single machine scheduling.

Cited in

(12)

• A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan
• Online scheduling in a parallel batch processing system to minimize makespan using restarts
• Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart
• A better lower bound for on-line scheduling
• scientific article; zbMATH DE number 1834660 (Why is no real title available?)
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
• Lower bounds on online deadline scheduling with preemption penalties
• On competitive analysis for polling systems
• Online scheduling with delivery time on a bounded parallel batch machine with limited restart
• A note on on-line scheduling with precedence constraints on identical machines
• Single machine batch scheduling with release times
• Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart

This page was built for publication: Lower bounds for on-line single-machine scheduling.

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