A 1. 47-approximation for a preemptive single-machine scheduling problem

DOI10.1016/S0167-6377(00)00024-9zbMath0955.90025MaRDI QIDQ1577468

David P. Williamson, Michel X. Goemans, Joel M. Wein

Publication date: 4 September 2000

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

zbMATH Keywords

analysis of algorithmssuboptimal algorithmsproduction/schedulingsingle-machine deterministic schedulingapproximations/heuristic

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Production models (90B30)

Related Items

Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time, Single machine batch scheduling with release times and delivery costs, Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates, Preemptive scheduling with availability constraints to minimize total weighted completion times, Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times, The power of \(\alpha\)-points in preemptive single machine scheduling.

Cites Work

• Scheduling-LPs bear probabilities. Randomized approximations for min-sum criteria
• Minimizing average completion time in the presence of release dates
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• A supermodular relaxation for scheduling with release dates
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item