In this section we consider scheduling problems in which more than one machine is available for processing the jobs, and each job must be processed for a given amount of time on each machine and in the same given order as all other jobs. The definitions for identical, uniform, and independent processors given in section 1.7 (Parallel Machines) apply equally to serial processors.

Suppose we have a schedule `S _{0}` in which the jobs are arranged in a different
order on the first machine than on the second.
In particular there will be two jobs

m_{1}: - - - - - - j_{2}j_{1}- - - - - - - - - - - - - - - - m_{2}: - - - - - - - - - - - j_{1}- - - - - j_{2}- - - - - -

Consider interchanging the order of jobs `j _{1}` and

m_{1}: - - - - - - j_{1}j_{2}- - - - - - - - - - - - - - - - m_{2}: - - - - - - - - - - - j_{1}- - - - - j_{2}- - - - - -

In `S _{0}` jobs

If we consider the last two machines in any flowshop schedule, we can in a similar manner arrange the jobs on the last machine into the same order as on the second last machine. In this case some of the completion dates may be increased, but the completion date of the last job is not. As it is the completion date of this last job that determines makespan, it follows that for minimizing makespan, schedules in which the jobs are in the same order on the last two machines form a dominant set.

Suppose that the requirement that no job be processed on two machines at the same time is relaxed.
Instead we require that each job `j` start on the second machine no earlier
than `l _{j}` units after it has finished on the first machine.
This
lag time
may be negative, in which case the job may begin on the second machine before it has completed on the first.
The following rule gives a sufficient condition for minimizing
makespan.

Job

imay precede jobjonly ifmin{ t._{i},1 + l_{i}, t_{j,2 }+ l_{j}} ≤ min{ t_{j,1}+ l_{j}, t_{i,2}+ l_{i}}

Such an optimal schedule may be produced by the following algorithm.

Determine the smallest

tover all jobs_{j,k}+ l_{j}jand machinesk.

Ifk=1schedulejfirst followed by an optimal schedule of all other jobs, otherwise schedulejlast preceded by an optimal schedule of all other jobs.

A similar algorithm is:

Let

u = { j : t. Schedule_{j,1}< t_{j,2}}uin non-decreasing order oft, followed by the remaining jobs in non-increasing order of_{j,1}+ l_{j}t._{j,2}+ l_{j}

We will now prove the rule and the first algorithm.
Let `S` be any schedule produced by the rule, and let `S _{0}` be any optimal permutation schedule.
If all adjacent pairs of jobs in

Thus

Construct

M_{0}= max{ T_{1}+ t_{i,1}+ t_{j,1}+ l_{j}+ t_{j,2}T_{1}+ t_{i,1}+ l_{i}+ t_{i,2}+ t_{j,2}, T_{2}+ t_{i,2}+ t_{j,2}}M_{1}= max{ T_{1}+ t_{j,1}+ t_{i,1}+ l_{i}+ t_{i,2}, T_{1}+ t_{j,1}+ l_{j}+ t_{j,2}+ t_{i,2}, T_{2}+ t_{j,2}+ t_{i,2}}

Suppose `M _{1} = T_{2} + t_{j,2} + t_{i,2}`.
Then as

Suppose `M _{1} = T_{1} + t_{j,1} + l_{j} + t_{j,2} + t_{i,2}`.

so

so

thus

as

and hence

Suppose `M _{1} = T_{1} + t_{j,1} + t_{i,1} + l_{i} + t_{i,2}`.

so

so

thus

as

In all cases `M _{1} ≤ M_{0}`,
and so the interchange does not delay any job
scheduled on the second machine after jobs

We may now prove the algorithm by showing that the schedule it produces satisfies the rule.
Suppose `t _{i,1} + l_{i} ≤ t_{j,k} + l_{j}`
for all jobs

Thus whenever a job is scheduled it satisfies the rule with respect to all other jobs regardless of how they are scheduled, and hence the resulting schedule must be optimal.

If `l _{j} =0` for all jobs

Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1.1(1954)] becomes

If all jobs are scheduled such that

iprecedesjonly when min{t}, then the schedule minimizes makespan._{i,1},t_{j,2}} ≤ min{ t_{j,1},t_{i,2}

The dominance conditions of section 1.8.1 apply to Johnson's model,
and hence permutation schedules form a dominant set for the two and three machine flowshop.
For the three machine case,
if `t _{i,1} ≥ t_{j,2}` or

Mitten
[Mitten, L.G.
Sequencing n jobs on two machines with arbitrary time lags

.
Management Science 5.3(1959)293–298]
defined the
start lag,
`a _{j}`, of a job as being the earliest time job

Burns and MacEwan considered a model in which a machine may be set up for a job while that
job is still being processed on a previous machine.
`l _{j}` is thus