Principles of Sequencing and Scheduling, 2nd Edition

10Flow Shop Scheduling

10.1 Introduction

This chapter deals with a model based on the design in which machines are arranged in series. In this design, jobs flow from an initial machine, through several intermediate machines, and ultimately to a final machine before completing. Traditionally, we refer to this design as a flow shop, even though an actual shop may contain much more than a single serial configuration.

In a flow shop, the work in a job is broken down into separate tasks called operations, and each operation is performed at a different machine. In this context, a job is a collection of operations with a special precedence structure. In particular, each operation after the first has exactly one direct predecessor, and each operation before the last has exactly one direct successor, as shown in Figure 10.1. Thus, each job requires a specific sequence of operations to be carried out for the job to be complete.

Figure 10.1 The precedence structure of a job in a flow shop.

The shop contains m different machines, and in the “pure” flow shop model, each job consists of m operations, each of which requires a different machine. The machines in a flow shop can thus be numbered 1, 2, …, m; and the operations of job j are numbered (1, j), (2, j), …, (m, j), so that they correspond to the machine required. For example, p₅₃ denotes the operation time on machine 5 for job 3. ...