Competitive analysis of preemptive single-machine scheduling

DOI10.1016/J.ORL.2010.08.012MaRDI QIDQ614049zbMATH OpenOpenAlexFDO

Authors René 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

competitive analysisonline algorithmsscheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• scientific article; zbMATH DE number 2119710
• Competitive analysis of a better on-line algorithm to minimize total completion time on a single-machine
• Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time
• Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time

Cites work

• 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
• Designing PTASs for MIN-SUM scheduling problems
• Efficient algorithms for average completion time scheduling
• scientific article; zbMATH DE number 1834660 (Why is no real title available?)
• scientific article; zbMATH DE number 6472636 (Why is no real title available?)
• LP-based online scheduling: From single to parallel machines
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• The power of \(\alpha\)-points in preemptive single machine scheduling.

Cited in

(13)

• Competitive analysis of a better on-line algorithm to minimize total completion time on a single-machine
• The power of \(\alpha\)-points in preemptive single machine scheduling.
• Modeling single machine preemptive scheduling problems for computational efficiency
• On-line scheduling with monotone subsequence constraints
• Single parameter analysis of power of preemption on two and three uniform machines
• Online appointment scheduling in the random order model
• Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time
• On-line Scheduling with a Monotonous Subsequence Constraint
• A tight 2-approximation for preemptive stochastic scheduling
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• On competitive analysis for polling systems
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling

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

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