Principles of Sequencing and Scheduling, 2nd Edition

2Single‐machine Sequencing

2.1 Introduction

The pure sequencing problem is a specialized scheduling problem in which an ordering of the jobs completely determines a schedule. Moreover, the simplest pure sequencing problem is one in which there is a single resource, or machine, and all processing times are deterministic. As simple as it is, however, the one‐machine case is still very important. The single‐machine problem illustrates a variety of scheduling topics in a tractable model. It provides a context in which to investigate many different performance measures and several solution techniques. It is therefore a building block in the development of a comprehensive understanding of scheduling concepts. In order to completely understand the behavior of a complex system, it is vital to understand its parts, and quite often the single‐machine problem appears as a part of a larger scheduling problem. Sometimes, it may even be possible to solve the imbedded single‐machine problem independently and then to incorporate the result into the larger problem. For example, in multiple‐operation processes, a bottleneck stage may exist, and the treatment of the bottleneck by itself with single‐machine analysis may determine the properties of the entire schedule. At other times, the level at which decisions must be made may dictate that resources should be treated in the aggregate, as if jobs were coming to a single facility.

In addition to the limitation to a single machine, the basic problem ...