TAOCP 6.1 Exercise 17

Let a schedule be a permutation $a_1 a_2 \dots a_n$ of the jobs $1,2,\dots,n$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.1: Sequential Searching

Exercise 17. [M23] [M23] (J. R. Jackson.) Suppose you have to do n jobs; the jth job takes T; units of time, and it has a deadline D;. In other words, the jth job is supposed to be finished after at most D; units of time have elapsed. What schedule a1 a2...an for processing the jobs will minimize the maximum tardiness, namely

max(Ty,, Da,, Ta, +Ta,, Day;---) Tay t+Tas+++++Tan, Day)?

Verified: no
Solve time: 3m09s

Solution

Let a schedule be a permutation $a_1 a_2 \dots a_n$ of the jobs $1,2,\dots,n$. Define completion times

$$ C_k = T_{a_1} + T_{a_2} + \cdots + T_{a_k}. $$

The quantity to be minimized is

$$ L_{\max} = \max_{1 \le k \le n} (C_k - D_{a_k}). $$

This is exactly the maximum lateness of the schedule.

The claim is that ordering the jobs by nondecreasing deadlines,

$$ D_{a_1} \le D_{a_2} \le \cdots \le D_{a_n}, $$

minimizes $L_{\max}$.

Exchange argument

Consider any schedule that is not ordered by nondecreasing deadlines. Then there exist adjacent positions $k,k+1$ such that

$$ D_{a_k} > D_{a_{k+1}}. $$

Let $i = a_k$ and $j = a_{k+1}$. Let the partial completion time before these two jobs be

$$ C = T_{a_1} + \cdots + T_{a_{k-1}}. $$

In the original order $(i,j)$, the completion times of these two positions are

$$ C_i = C + T_i, \quad C_j = C + T_i + T_j. $$

Their contributions to lateness are

$$ L_i = C + T_i - D_i, \quad L_j = C + T_i + T_j - D_j. $$

After swapping them to $(j,i)$, the completion times become

$$ C'_j = C + T_j, \quad C'_i = C + T_j + T_i, $$

and the corresponding lateness values are

$$ L'_j = C + T_j - D_j, \quad L'_i = C + T_j + T_i - D_i. $$

We compare the two schedules only on these two positions, since all earlier completion times are unchanged.

For job $i$, the difference is

$$ L'_i - L_j = (C + T_i + T_j - D_i) - (C + T_i + T_j - D_j) = D_j - D_i \le 0 $$

because $D_j \le D_i$ is false in this inversion and hence $D_j - D_i < 0$.

For job $j$, the difference is

$$ L'_j - L_i = (C + T_j - D_j) - (C + T_i - D_i) = (T_j - T_i) + (D_i - D_j). $$

Since $D_i > D_j$, the term $D_i - D_j$ is positive, but no sign restriction is needed on $T_i,T_j$ because we compare maxima. Instead, observe directly:

$$ L'_j = C + T_j - D_j \le C + T_i + T_j - D_j = L_j, $$

since $T_i \ge 0$.

Thus each of the two swapped lateness values does not exceed the corresponding value in the original order, except possibly for $L'_i$ compared to $L_j$, and in that case we already have $L'_i \le L_j$.

Therefore,

$$ \max(L'_i, L'_j) \le \max(L_i, L_j). $$

All other jobs are unaffected, so the maximum lateness of the entire schedule does not increase under this adjacent swap.

Iteration to global order

Repeatedly applying such swaps removes all inversions of the form $D_{a_k} > D_{a_{k+1}}$. The process terminates only when no such inversion remains, which is exactly the condition that

$$ D_{a_1} \le D_{a_2} \le \cdots \le D_{a_n}. $$

Since each swap does not increase the maximum lateness, the final schedule has maximum lateness no larger than the initial schedule.

Thus any optimal schedule can be transformed into one ordered by nondecreasing deadlines without increasing $L_{\max}$, so at least one optimal schedule has this form.

Optimality

A schedule ordered by nondecreasing $D_j$ is therefore optimal for minimizing

$$ \max(T_{a_1} - D_{a_1},, T_{a_1}+T_{a_2}-D_{a_2},, \dots,, T_{a_1}+\cdots+T_{a_n}-D_{a_n}). $$

This completes the proof. ∎