In this section we consider single machine scheduling in which each job is
available at date zero, and has a
due date
`d _{j} > 0` by which time the job
should be completed.

For any schedule, the mean lateness is defined as

∑(Cmean lateness = mean completion date − mean due date_{j}−d_{j})/n = ∑(C_{j}/n)−∑(d_{j}/n)

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.

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

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

Now `C′ _{j} < C_{j}` and so

Let `S` be any schedule such that `d _{j} ≤ d_{j+1}` for all jobs

S = - - - - - j - - - - - - - - - i - - - - - - -S^{0}= - - - - - - - - - - i j - - - - - - - - - - -S^{1}= - - - - - - - - - - j i - - - - - - - - - - -

Construct `S ^{1}` from

Lfor all jobs k other than^{1}_{k}= L^{0}_{k}iandjLas^{1}_{j}< L^{0}_{j}C^{1}_{j}< C^{0}_{j}L^{1}_{i}= C^{1}_{i}− d_{i}= C^{0}_{j}− d_{i}≤ Cas^{0}_{j}− d_{j}das S is EDD_{j}≤ d_{i}= L^{0}_{j}

Let job `l ^{1}` be the job that realizes the maximum lateness in

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.

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

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 letX = { j: dand find a job_{j}≥ T_{max}+ ∑t_{i}}jthat has maximum processing time over all jobs inX. 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.

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 thanithat has the largest processing time, say jobj. Use Moore's algorithm to schedule all jobs other thanj, and then schedule jobjlast.

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