Stochastic Single-Machine Scheduling with Breakdowns

Abstract

We look at single-machine scheduling problems with breakdowns and stochastic processing times. We present static list algorithms to minimize the maximum lateness, to minimize the total weighted completion time and to maximize the number of on-time jobs (based on either expected completion time or a minimum success probability of being on time). These problems are all solved in both discrete and continuous time. We also study the problem with stochastic processing time, deterministic release date and no breakdowns. We do not study cases with precedence constraints or release dates and assume that breakdowns do not cause loss of progress on jobs.