ABSTRACT
Because many operations can be described as flow shops with multiple machines, it would be ideal to be able to schedule these optimally. In a flow shop the technological constraints demand that the jobs pass through the machines in the same order; i.e., if J
same is true for all jobs. Most production lines are arranged in this manner. We would like to derive algorithms that can handle the largest possible family
of flow shops. To this end we start with two theorems. We shall see that these imply that for some 2 and 3 machine flow shops we need only consider permutation schedules. A permutation schedule is one in which each machine processes the jobs in the same order; i.e., if on machine M
then the same is true for all machines. This is an important result as there are far fewer permutation schedules and they are also easier to implement because the person executing the schedule can use the same processing order on all machines. In flow shops there is a natural ordering of the machines, namely that given by the technological constraints as the processing order for each and every job. We assume that each job must be processed by M
constraints therefore have the form in Figure 9.1, which also has an example of a four-job, four-machine problem scheduled both as flow and permutation.
