Scheduling with Uncertain Processing Times
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23
summary
Shows a 3 + Δ/2 approximation for stochastic unrelated‑machine scheduling, where Δ upper‑bounds the squared coefficient of variation of job sizes. Uses a time‑index LP relaxation (finite, solvable up to ε) to get fractional start probabilities, then rounds by assigning jobs up front and imposing probabilistic delays and tentative start times per machine; sequencing uses Smith’s rule on each machine. Special cases: exponential sizes give 2×, deterministic gives 1.5×.
AI-written summary · about
chapters (17)
- 0:00Intro
- 1:12Single Machine Scheduling
- 2:03Identical Parallel Machine Scheduling
- 3:04Unrelated Machine Scheduling Given: m machines, machine-dependent processing times py
- 4:46Stochastic Scheduling
- 8:00Optimality
- 9:20An Example
- 12:11Stochastic World: Deliberate Idleness
- 13:48Approximation Algorithms
- 17:12LP Relaxation Identical Machines
- 18:56Structuring The Input
- 19:21Time-Indexed LP Relaxation: Intuition
- 22:48Technical Detail: Infinite LP Solution?
- 23:57LP-Based Scheduling Policy
- 25:10Proof of Performance Ratio
- 29:01Lower Bounds
- 30:44Final Remarks