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

DOI10.1016/S0167-6377(01)00115-8zbMath1030.90041MaRDI QIDQ1612009

Arjen P. A. Vestjens, Leen Stougie

Publication date: 28 August 2002

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

Mathematics Subject Classification ID

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

Related Items (11)

Lower bounds for on-line single-machine scheduling. ⋮ Online \(k\)-server routing problems ⋮ Online scheduling problems with flexible release dates: applications to infrastructure restoration ⋮ On competitive analysis for polling systems ⋮ An improved greedy algorithm for stochastic online scheduling on unrelated machines ⋮ Metrical service systems with multiple servers ⋮ The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates ⋮ An optimal online algorithm for scheduling two machines with release times ⋮ LP-based online scheduling: From single to parallel machines ⋮ Online Scheduling on Two Parallel Machines with Release Times and Delivery Times ⋮ Online scheduling on two parallel machines with release dates and delivery times

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online algorithms. The state of the art
• Minimizing average completion time in the presence of release dates
• On randomization in on-line computation.
• On-line multi-threaded scheduling
• A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines
• A guessing game and randomized online algorithms
• Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine

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