A 1. 47-approximation for a preemptive single-machine scheduling problem
From MaRDI portal
Publication:1577468
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)
analysis of algorithms; suboptimal algorithms; production/scheduling; single-machine deterministic scheduling; approximations/heuristic
90B35: Deterministic scheduling theory in operations research
90C59: Approximation methods and heuristics in mathematical programming
90B30: Production models
Related Items
The power of \(\alpha\)-points in preemptive single machine scheduling., Preemptive scheduling with availability constraints to minimize total weighted completion times
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