MACHINE SCHEDULING

1.3.1 Minimizing Mean Lateness

For any schedule, the mean lateness is defined as

∑(Cj−dj)/n = ∑(Cj/n)−∑(dj/n)
mean lateness = mean completion date − mean due date

The mean due date is a constant, therefore the problem is equivalent to that of minimizing the mean completion date. By the results of the previous example of an interchange proof, we know that SPT schedules are both necessary and sufficient for mean completion date optimality and so SPT schedules are necessary and sufficient to minimize mean lateness.

1.3.2 Minimizing Maximum Lateness (and Tardiness)

Let S be any schedule that minimizes maximum lateness = max{ C_j − d_j }, and suppose that the maximum lateness occurs on a unique job j>1. Interchange adjacent jobs j−1 and j to produce schedule S′.

S  = (1,2,3,...,j−1,j,...,n)
S′ = (1,2,3,...,j,j−1,...,n)

Now C′_j < C_j and so L′_j < L_j = L(S). S is optimal so L(S)≤L(S′), and for all jobs other than j and j−1 the lateness is the same in both schedules, so we must have that L′_j−1 ≥ L_j. But C′_j−1 = C_j and so we must have d_j−1 ≤ d_j. We conjecture that if this were true for all jobs, perhaps the resulting schedule would be optimal.

Let S be any schedule such that d_j ≤ d_j+1 for all jobs j. Such a schedule is known as EDD ( earliest due date). 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 (perhaps not immediately) in S.

S  =   - - - - - j - - - - - - - - - i - - - - - - -
S0 =  - - - - - - - - - - i j - - - - - - - - - - -
S1 =  - - - - - - - - - - j i - - - - - - - - - - -

Construct S¹ from S⁰ by interchanging jobs i and j and leaving all other jobs in the same positions. Let T be the time at which job i starts processing in S⁰.

L1k = L0k for all jobs k other than i and j
L1j < L0j as C1j < C0j
L1i = C1i − di
= C0j − di
≤ C0j − dj as dj ≤ di as S is EDD
= L0j

Let job l¹ be the job that realizes the maximum lateness in S¹. By the above results we have that there is a job l⁰ such that L¹_l¹ ≤ L⁰_l⁰. Thus L( S¹)≤ L(S⁰), and S⁰ being optimal therefore implies that S¹ is optimal. Now interchanging jobs i and j reduced by one the number of pairs of jobs in S⁰ which were in a different order than in S. But as there can be at most a finite number of such pairs, we can construct a finite sequence of optimal schedules, {S⁰, S¹, S², ..., S*} such that S*=S. As S is any EDD schedule, we have just proven that all EDD schedules are optimal, and hence that EDD is sufficient to minimize maximum lateness. Note that this is not a necessary condition, as there may be many optimal schedules which are not in EDD order.

Tardiness is defined as T_j = max{0, L_j}. If for some schedule the maximum lateness is not positive then the maximum tardiness is 0 which is obviously optimal. Otherwise the maximum lateness is positive, and so the maximum tardiness is equal to the maximum lateness. Thus EDD is sufficient to minimize maximum tardiness.

1.3.3 Maximizing Minimum Lateness

As the minimum lateness of a schedule may be decreased without increasing any of the completion dates, this is not a regular function, and so permutation schedules may not (and in fact do not) form a dominant set. However it is easy to prove (as in section 1.3.3 (Minimizing Maximum Lateness)), that over permutation schedules a sufficient condition for maximizing the minimum lateness (and hence minimizing the maximum earliness) is the SST ( shortest slack time) rule: d_j − t_j ≤ d_j+1 − t_j+1 for all jobs j. The expression d_j − t_j represents the latest date at which a job may be started without being tardy. Slackness is this date less the ready date of the machine.

1.3.4 Secondary Measures of Performance

If some condition is sufficient but not necessary for optimizing a given measure of performance, then there may be many different optimal schedules. We may then try to optimize some secondary measure of performance over this set of solutions, although the solution may not be optimal for this secondary measure over all possible schedules.

In section 1.3.2 (Minimizing Maximum Lateness) we showed that EDD was sufficient, but not necessary, to minimize maximum tardiness. In section 1.2.1 (Adjacent Interchange Proof Example) we showed that SPT was both necessary and sufficient to minimize mean completion date. The following algorithm, known as Smith's Rule [Smith, W.E. Various optimizers for single stage production. Naval Research Logistics Quarterly 3.1(1956)] may be used to minimize mean completion date over all schedules that have minimal maximum tardiness, T_max (which may be determined by constructing an EDD schedule).

If n ≤ 1, the schedule is trivially optimal. Otherwise let X = { j: d_j ≥ T_max + ∑t_i } and find a job j that has maximum processing time over all jobs in X. Use Smith's Rule to schedule all jobs other than j and then schedule job j last.

The above algorithm produces an optimal schedule. Similar rules may be designed for other primary and secondary measures of performance, although there would be no guarantee that the resulting schedule would be optimal.

1.3.5 Minimizing the Number of Tardy Jobs

The following algorithm, known as Moore's algorithm [Moore, J.M. Sequencing n jobs on one machine to minimize the number of late jobs Management Science 15.1(1968),102–109] or Hodgson's algorithm, may be used to find a schedule with a minimum number of tardy jobs.

Form an EDD schedule of all jobs, and if no more than one job is late, the schedule is optimal. Otherwise determine the first late job, say i, and find the job scheduled no later than i that has the largest processing time, say job j. Use Moore's algorithm to schedule all jobs other than j, and then schedule job j last.

Note that job j may be job i itself, and that the resulting schedule is not necessarily the only optimal schedule.