Randomized algorithms for on-line scheduling problems: How low can't you go?

DOI10.1016/S0167-6377(01)00115-8MaRDI QIDQ1612009zbMATH OpenFDO

Authors L. Stougie, Arjen P. A. Vestjens

Publication date 28 August 2002

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://research.tue.nl/en/publications/2b2504be-4fa2-4a73-a6b8-a87112c375f4

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20) Deterministic scheduling theory in operations research (90B35)

Recommendations

• A lower bound for randomized on-line scheduling algorithms
• A lower bound for randomized on-line multiprocessor scheduling
• A better lower bound for on-line scheduling
• Randomized algorithms for that ancient scheduling problem
• Randomized on-line and semi-on-line scheduling on identical machines
• New lower and upper bounds for on-line scheduling
• A randomized algorithm for online scheduling with interval conflicts
• Randomized online algorithms for maximizing busy time interval scheduling
• Randomized approximation and online algorithms for assignment problems

Cites work

• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• A guessing game and randomized online algorithms
• A PTAS for minimizing the total weighted completion time on identical parallel machines.
• Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1305545 (Why is no real title available?)
• scientific article; zbMATH DE number 1094690 (Why is no real title available?)
• scientific article; zbMATH DE number 6472638 (Why is no real title available?)
• Minimizing average completion time in the presence of release dates
• On randomization in on-line computation.
• On-line multi-threaded scheduling
• Online algorithms. The state of the art

Cited in

(15)

• LP-based online scheduling: From single to parallel machines
• A lower bound for randomized on-line scheduling algorithms
• Online scheduling problems with flexible release dates: applications to infrastructure restoration
• Lower bounds for on-line single-machine scheduling.
• Metrical service systems with multiple servers
• Online scheduling on two parallel machines with release dates and delivery times
• The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
• An improved greedy algorithm for stochastic online scheduling on unrelated machines
• Online scheduling on two parallel machines with release times and delivery times
• A lower bound for randomized on-line multiprocessor scheduling
• A guessing game and randomized online algorithms
• Lower bounds for on-line single-maschine scheduling
• An optimal online algorithm for scheduling two machines with release times
• On competitive analysis for polling systems
• Online k-server routing problems

This page was built for publication: Randomized algorithms for on-line scheduling problems: How low can't you go?

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