Stochastic Machine Scheduling with Precedence Constraints 2: LP-Based Graham List Scheduling Is a (2 − 1/m + max{1, (m − 1)Δ/m})-Approximation for P|in-forest|E[Σ w_j C_j]Research Paper
Scheduling jobs whose durations are uncertain is the normal situation in project management, manufacturing and computing: a job's processing time becomes known only when the job finishes, but a distribution for it is available in advance. Stochastic machine scheduling models this by random, independent processing times and asks for a scheduling policy,…