Principles of Sequencing and Scheduling, 2nd Edition

6Sequencing for Stochastic Scheduling

6.1 Introduction

As we discussed in Chapter 2, the basic single‐machine sequencing model is characterized by seven conditions:

1. C1. There are n single‐operation jobs simultaneously available for processing (at time zero).
2. C2. Machines can process at most one job at a time.
3. C3. Setup times for the jobs are independent of job sequence and are included in processing times.
4. C4. Job descriptors are deterministic and known in advance.
5. C5. Machines are continuously available (no breakdowns occur).
6. C6. Machines are never kept idle while work is waiting.
7. C7. Once an operation begins, it proceeds without interruption.

Such conditions, which help us analyze the problem, may also restrict the applicability of the model. Specifically, by adopting conditions C4 and C5, we limit ourselves to deterministic models, with all parameters assumed to be known. In this chapter, we explore a relaxation of condition C4, allowing processing times to be random. We assume that condition C5 remains unchanged. However, if we relax C5 and allow machine breakdowns, the effect is ultimately quite similar to relaxing C4 because the time required to process a job becomes uncertain. When processing times are random, the problem that results is called a stochastic scheduling problem.

As discussed in Chapter 2, conditions C6 and C7 are inconsequential for regular performance measures in the deterministic version of the basic model – that is, inserted idle time and job preemption ...