2. SINGLE-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 is characterized by these conditions :
C1. There are n single-operation jobs simultaneously available for processing (at time zero).
C2. Machines can process at most one job at a time.
C3. Setup times for the jobs are independent of job sequence and are included in processing times.
C4. Job descriptors are deterministic and known in advance.
C5. Machines are continuously available (no breakdowns occur).
C6. Machines are never kept idle while work is waiting.
C7. Once an operation begins, it proceeds without interruption.
Under these conditions, there is a one-to-one correspondence between a sequence of the n jobs and a permutation of the job indices 1, 2, . . . , n. The total number of distinct solutions to the basic single-machine problem is therefore n!, which is the number of different sequences of n elements. Whenever a schedule can be completely characterized by a permutation of integers, it is called a permutation schedule, which is a classification that extends beyond single-machine cases. In describing permutation schedules, it is helpful to use brackets to indicate position in sequence. Thus [5] = 2 means that the fifth job in sequence is job 2. Similarly, d refers to the due date of the first job in sequence.

After covering some preliminaries in Section 2.2, we review the elementary sequencing results in Section 2.3 for problems containing no due dates, and in Section 2.4 for problems involving due dates. The chapter is organized to show how differences in the choice of a criterion often lead to differences in the optimal schedule. Later, we examine several general-purpose methodologies that can be applied to single-machine problems.