Competitive analysis of preemptive single-machine scheduling

DOI10.1016/j.orl.2010.08.012zbMath1202.90146OpenAlexW1977040436MaRDI QIDQ614049

R. A. Sitters

Publication date: 23 December 2010

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

Full work available at URL: https://doi.org/10.1016/j.orl.2010.08.012

zbMATH Keywords

schedulingcompetitive analysisonline algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (7)

Online Appointment Scheduling in the Random Order Model ⋮ On competitive analysis for polling systems ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ On-line Scheduling with a Monotonous Subsequence Constraint ⋮ Modeling single machine preemptive scheduling problems for computational efficiency ⋮ On-line scheduling with monotone subsequence constraints ⋮ A Tight 2-Approximation for Preemptive Stochastic Scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• LP-based online scheduling: From single to parallel machines
• The power of \(\alpha\)-points in preemptive single machine scheduling.
• Designing PTASs for MIN-SUM scheduling problems
• Efficient Algorithms for Average Completion Time Scheduling
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Coping with Incomplete Information in Scheduling — Stochastic and Online Models
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time

This page was built for publication: Competitive analysis of preemptive single-machine scheduling