Principles of Sequencing and Scheduling, 2nd Edition

14The Job Shop Problem

14.1 Introduction

The classical job shop scheduling problem differs from the flow shop problem in one important respect: The flow of work is not unidirectional. The elements of the problem are a set of m machines and a collection of n jobs to be scheduled. Each job consists of several operations with the same linear precedence structure as in the flow shop model. Although a job can have any number of operations, the most common formulation of the job shop problem specifies that each job has exactly m operations, one on each machine. It is not difficult, however, to adapt the main ideas to general cases in which a job visits the same machine more than once or skips some machines. Because the workflow in a job shop is not unidirectional, we can think of each machine in the shop as having the input and output flows of work shown in Figure 14.1. Unlike the flow shop model, there is no initial machine that performs only the first operation of a job, nor is there a terminal machine that performs only the last operation of a job.

Figure 14.1 Workflow in a job shop.

In the flow shop, machine k performs the kth operation of any job, and there is no need to distinguish between operation number and machine number. In the job shop, by contrast, it is appropriate to describe an operation with a triplet (i, j, k) to denote that for job i, operation j requires machine ...