Principles of Sequencing and Scheduling, 2nd Edition

8Extensions of the Basic Model

8.1 Introduction

The basic single‐machine model provides an opportunity to study a variety of scheduling criteria as well as a number of solution techniques. These themes have been central to the coverage in the preceding chapters. The assumptions of the basic model are highly specific, however, and for the results and insights to be of some general value, the assumptions must be extended to more complicated and realistic situations. We have already taken this route with respect to some assumptions. This chapter deals with additional models in which the assumptions of the basic model are relaxed.

We introduced the basic model with seven assumptions, two of which turned out to be derived conditions for regular measures. The assumptions were:

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.

In our coverage of stochastic models, we relaxed C4 and explored the implications of scheduling with uncertain information. We also encountered a situation in which it becomes desirable to violate C6. In this chapter, we examine ...