MACHINE SCHEDULING

1.8.1 Dominance Conditions

Suppose we have a schedule S₀ 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 j₁ and j₂ such that j₂ is scheduled immediately before j₁ on machine 1, but scheduled after j₁ on machine 2.

m1:  - - - - - - j2 j1 - - - - - - - - - - - - - - - -
m2:  - - - - - - - - - - - j1 - - - - - j2 - - - - - -

Consider interchanging the order of jobs j₁ and j₂ on the first machine to give schedule S₁.

m1:  - - - - - - j1 j2 - - - - - - - - - - - - - - - -
m2:  - - - - - - - - - - - j1 - - - - - j2 - - - - - -

In S₀ jobs j₁ and j₂ both finished processing on m₁ before either started on m₂, and so in S₁ this is also true and hence S₁ is a feasible schedule. Now as no other jobs or machines were affected, the completion dates of all jobs on all machines numbered 2 or higher are the same in S₁ as in S₀. Thus the interchange did not increase the final completion date of any job. Similarly we could remove any other discrepancies between the sequences on the first two machines, and as there are a finite number of such discrepancies, we can schedule the jobs on the first machine in the same order as on the second without changing the completion date of any job. Thus as in section 1.2.2 (Regular Functions) we see that schedules in which the jobs are in the same order on the first two machines form a dominant subset of schedules without preemption.

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.

1.8.2 Two Machine Flowshops

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 i may precede job j only if min{ 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 t_j,k + l_j over all jobs j and machines k.
If k=1 schedule j first followed by an optimal schedule of all other jobs, otherwise schedule j last preceded by an optimal schedule of all other jobs.

A similar algorithm is:

Let u = { j : t_j,1 < t_j,2 }. Schedule u in non-decreasing order of t_j,1 + l_j, followed by the remaining jobs in non-increasing order of 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₀ be any optimal permutation schedule. If all adjacent pairs of jobs in S₀ are in the same order as in S, then S= S₀ and so S is optimal. Otherwise there exists a pair of jobs i and j such that i immediately precedes j in S₀ but j precedes i in S.
Thus min{ t_j,1 + l_j , t_i,2 + l_i }  ≤  min{ t_i,1 + l_i , t_j,2 + l_j }.
Construct S₁ from S₀ by interchanging jobs i and j. Let T₁ and T₂ be the date the last job before i and j finishes on machines 1 and 2 respectively. Let M₀ be the date job j finishes in S₀, and M₁ be the date job i finishes in S₁. Then:

M0 = max{
  T1 + ti,1 + tj,1 + lj + tj,2
  T1 + ti,1 + li + ti,2 + tj,2,
  T2 + ti,2 + tj,2 }
M1 = max{
  T1 + tj,1 + ti,1 + li + ti,2,
  T1 + tj,1 + lj + tj,2 + ti,2,
  T2 + tj,2 + ti,2 }

Suppose M₁ = T₂ + t_j,2 + t_i,2. Then as M₀ ≥ T₂ + t_i,2 + t_j,2, we have M₁ ≤ M₀.

Suppose M₁ = T₁ + t_j,1 + l_j + t_j,2 + t_i,2.
  M₀ ≥ T₁ + t_i,1 + t_j,1 + l_j + t_j,2
  so M₀ − M₁ ≥ ( t_i,1 + l_i )−( t_i,2 + l_i ),
  M₀ ≥ T₁ + t_i,1 + l_i + t_i,2 + t_j,2
  so M₀ − M₁ ≥ ( t_i,1 + l_i )−( t_j,1 + l_j ),
  thus M₀ − M₁ ≥ (t_i,1 + l_i ) − min{ t_j,1 + l_j ,t_i,2 + l_i } ≥ 0
  as i→j in S
  and hence M₁ ≤M₀.

Suppose M₁ = T₁ + t_j,1 + t_i,1 + l_i + t_i,2.
  M₀ ≥ T₁ + t_i,1 + t_j,1 + l_j + t_j,2
  so M₀ − M₁ ≥ ( t_j,2 + l_j )−( t_i,2 + l_i ),
  M₀ ≥ T₁ + t_i,1 + l_i + t_i,2 + t_j,2
  so M₀ − M₁ ≥ ( t_j,2 + l_j )−( t_j,1 + l_j ),
  thus M₀ − M₁ ≥ ( t_j,2 +l_j )− min{ t_j,1 + l_j ,t_i,2 +l_i } ≥ 0
  as i→j in S and hence M₁ ≤ M₀.

In all cases M₁ ≤ M₀, and so the interchange does not delay any job scheduled on the second machine after jobs i and j. Now as no job before i and j was delayed on the second machine, and as no other jobs on the first machine were delayed, we have that the makespan of S₁ is no greater than that of S₀. Since S₀ is optimal, so must be S₁. But S₁ has one less pair of jobs than S₀ out of order, and as there are at most a finite number of such disorderings we can construct a sequence of optimal schedules S₀, S₁, S₂, ..., such that the last such schedule is equal to S, and hence S must be optimal.

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 j and both machines k. Then the algorithm will schedule job i before all other jobs j, and t_i,1 = min{ t_i,1 +l_i , t_j,2 + l_j } ≤ min{ t_j,1 + l_j , t_i,2 + l_i }. Suppose t_j,2 + l_j ≤t_i,k + l_i for all jobs i and both machines k. Then the algorithm will schedule all other jobs i before job j, and t_j,2 + l_j = min{ t_i,1 + l_i , t_j,2 + l_j } ≤ min{ t_j,1 + l_j , t_i,2 + l_i }.
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.

1.8.3 Special Models

If l_j =0 for all jobs j, then the flowshop is known as Johnson's model. The sufficiency rule, known as Johnson's rule [Johnson, S.M. 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 i precedes j only when min{ t_i,1 ,t_j,2 } ≤ min{ t_j,1 ,t_i,2 }, then the schedule minimizes makespan.

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 t_j,2 ≤ t_k,3 for all jobs i, j, and k, the same rule applied to the first and third machine gives an optimal schedule if we define l_j as t_j,2.

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 j may start processing or setup on the second machine after it has started on the first, and the stop lag, b_j, as the earliest time it may finish on the second machine after finishing on the first. Thus l_j is max{a_j − t_j,1 , b_j − t_j,2}, and the sufficiency rule may be used to find an optimal schedule.

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 −s_j,2.