Principles of Sequencing and Scheduling, 2nd Edition

7Safe Scheduling

7.1 Introduction

In Chapter 6, our coverage of stochastic scheduling was confined to stochastic counterparts of models with regular performance measures. Indeed, those models are the most prominent subjects in the literature on stochastic scheduling. However, the typical stochastic model misses an important part of the problem: It fails to account for safety time. To use an analogy, imagine that we attempted to build stochastic inventory models by relying only on the analysis of average behavior and making no provisions for safety stock. Just as safety stocks are vital to practical inventory policies, safety time is vital to practical scheduling policies. However, the optimal determination of safety time has no counterpart in deterministic scheduling. Safe scheduling departs from the dominant paradigm in stochastic scheduling by considering safety time explicitly.

In stochastic inventory theory, safety stocks are usually determined in one of two ways – by meeting service‐level targets explicitly or by minimizing the expected total cost due to overstocking and understocking and thereby deriving service‐level constraints implicitly. We can use analogous approaches in safe scheduling, where, as in Chapter 6, processing times are random. To use service‐level constraints, we replace the deterministic definition of “on time” by a stochastic one. Define the service level for job j as SL_j = Pr{C_j ≤ d_j}, the probability that job j completes by its due date.

Let b_j