Lesson · Scheduling · Due dates, and which question you asked

Earliest Due Date and Maximum Lateness

Sorting by due date minimises maximum lateness, and the proof is the adjacent exchange with a maximum in place of a sum. It is the most useful rule on the course and the most over-claimed: on the lab's five jobs it attains L max = 6, which is optimal, while costing 17 of total tardiness where 16 exists and leaving 4 jobs late where 2 is possible. Three due-date objectives, one rule, and it answers one of them.

Open the interactive lesson Practice

L_j = C_j − d_j (may be negative) T_j = max(L_j, 0) U_j = 1 if late L max = max L_j T max = max T_j sum T sum U EDD: sort by d ascending. Minimises L max, and minimises T max the exchange: swapping an out-of-order pair cannot raise the larger of two latenesses A 6:8, B 4:4, C 5:12, D 3:6, E 7:20: EDD B D A C E, L max 6 — optimal same order, sum T 17 where 16 exists; 4 jobs late where 2 is possible

One rule, four due-date objectives, and one of them answered

Core ideas

What this lesson establishes

The rule and its proof are short. The two ideas that take work are what the proof does not cover, and why the objective it does cover is the one with a maximum in it.

A maximum is not a sum, and the exchange handles it differently

For sum C the swap produced a difference. For L max it produces an inequality: after swapping an out-of-order adjacent pair, the later-due job finishes earlier than it did, and the earlier-due job finishes no later than the pair finished before. So the larger of the two latenesses cannot have gone up, and since no other job moved, L max cannot have gone up. That is enough — optimality needs an argument that the swap never hurts, not one that it always helps.

Minimising the worst is not minimising the total

L max is decided by one job; sum T is paid by all of them. Making the worst job less bad routinely means making several others worse, and the lab's instance is exactly that: EDD gives latenesses 0, 1, 5, 6, 5 for a maximum of 6 and a total tardiness of 17, while the order that attains 16 has a maximum of 10. Neither order dominates the other, and no rule reconciles them because they are different questions.

Total tardiness is where the exchange argument stops

1 || sum T has no exchange rule, and this course does not invent one. Swapping an adjacent pair changes the tardiness of both jobs by amounts that depend on where the due dates sit relative to the clock, so the difference does not collapse to a subtraction on the two jobs alone. The lab exhibits the optimum by enumeration and names the boundary, which is more useful than a plausible-looking heuristic.

The material

Sorting by due date, what it proves, and the three things it does not

The four due-date objectives, the exchange argument for the one with a maximum in it, and the same order measured on the other three.

Definition · Lateness, tardiness, and the four objectives

For a job finishing at C_j with due date d_j, the lateness is L_j = C_j − d_j and may be negative; the tardiness is T_j = max(L_j, 0) and may not; and U_j is 1 when C_j > d_j.

The four objectives are L max (the worst lateness, which can be negative if everything finishes early), T max (the worst tardiness, which cannot), sum T (total tardiness) and sum U (the number of late jobs). They are four questions, not four spellings of one.

Theorem · Earliest due date minimises maximum lateness

Ordering the jobs by d ascending minimises L max, and it also minimises T max.

Take any order and any adjacent pair a then b with d_a > d_b, starting at time t and finishing at t + p_a + p_b. Before the swap the two latenesses are t + p_a − d_a and t + p_a + p_b − d_b; the larger of the two is at least the second one.

After the swap they are t + p_b − d_b and t + p_b + p_a − d_a. The first of these is smaller than t + p_a + p_b − d_b because p_b < p_a + p_b; the second is smaller than t + p_a + p_b − d_b because d_a > d_b. So both new latenesses are below the old maximum of the pair.

No other job moved, so L max over the whole schedule did not increase. Repeating on any remaining out-of-order pair reaches the due-date order without ever increasing L max, so that order attains the minimum. T max is max(L max, 0), so the same order minimises it.

□

Notice what shape that argument has. The unweighted case gave an identity and a strict improvement; this one gives only that the swap does no harm. That is the normal situation for a maximum, and it is enough: a sequence of harmless swaps reaching the rule's order shows the rule's order is at least as good as where you started, whatever that was.

The rule, on five jobs, doing exactly what it promises

jobs A 6:8 B 4:4 C 5:12 D 3:6 E 7:20 p:d EDD B D A C E job p d C L T B 4 4 4 0 0 D 3 6 7 1 1 late A 6 8 13 5 5 late C 5 12 18 6 6 late E 7 20 25 5 5 late L max 6 T max 6 sum T 17 late 4 of 5 best L max over all 120 orders: 6 EDD attains it best T max over all 120 orders: 6 EDD attains it

L max = 6 is set by C, which finishes at 18 against a due date of 12. Seventeen hours of work are due by hour twelve and twenty-five hours of work exist, so something has to be late; the rule's achievement is that nothing is more than six hours late, and the enumeration confirms that no order does better.

The same order, on the objective it does not solve

EDD B D A C E T = 0, 1, 5, 6, 5 sum T 17 late 4 the best B D C A E T = 0, 1, 0, 10, 5 sum T 16 late 3 and its L max is 10, not 6 Moore–Hodgson late 2, which is the enumerated minimum best sum T over 120 orders 16 best sum U over 120 orders 2

Example · Where the extra hour of tardiness went

The order that attains sum T = 16 differs from EDD by one adjacent swap: C and A change places. C then finishes at 12 exactly on its due date and contributes nothing, while A slides from 13 to 18 and goes from 5 hours tardy to 10.

Total tardiness falls from 17 to 16 because one job was taken from 6 to 0 while another rose by 5. Maximum lateness rises from 6 to 10, because the worst job is now worse. Both orders are optimal — for different objectives — and choosing between them is a decision about whether a schedule is judged on its worst job or on all of them.

So EDD is optimal for two of the four due-date objectives and beaten on the other two: 17 against 16, and 4 late against 2. The second of those has a rule, and “Minimising the Number of Late Jobs” is it. The first does not, and the honest thing is to say so.

The boundary, stated rather than worked around

1 || sum T — one machine, minimise total tardiness — has no adjacent-exchange rule. Run the argument and see why: swapping a and b changes T_a and T_b, but each of those changes is a clipped quantity, so the amount depends on whether t + p_a sits above or below d_a, and the same swap moves the sum by different amounts in different parts of the schedule. There is no condition on the pair alone that decides it.

This is worth dwelling on because it is the one place on the course where the technique runs out, and a reader who has seen three rules fall out of one subtraction will expect a fourth. The lab's answer is to enumerate: it reports 16 and the order that attains it, and says that no rule here produced that order. On a larger instance the enumeration is not available either, and then the honest report is a heuristic value with a bound attached — which is the shape of answer “Integer Programming” is about.

One more warning about due dates, and it is about the model rather than the rule. A due date here is a number the objective is measured against, not a constraint. Nothing in this model refuses to run a schedule in which four of five jobs are late; the arithmetic prices it. If a date genuinely cannot be missed it is a constraint, the problem may be infeasible, and that is a different question from any of the four here.

Interactive

Earliest due date, and the objective it does not touch

EDD minimises the worst lateness; total tardiness is a different problem with no rule

Order by due date, and watch it win one objective and lose another

Four rules fill the order box and the panel scores each against the enumerated best of every order, on maximum lateness and on total tardiness at once. The slider swaps a pair you choose and prints both maxima, so the exchange argument can be run by hand on the instance it is being claimed for.

Worked example

Jobs, as name time:due

Order by

Swap the job in this position with the next1

Maximum lateness, L max—

The best L max there is—

Total tardiness, sum T—

The best sum T there is—

Jobs finishing late—

Objectives this rule is best at—

The exchange argument for L max is the one on the previous page with a different quantity: swapping an out-of-order adjacent pair cannot make the worst lateness worse, because the later job finishes earlier and the earlier job finishes no later than the pair did before. The lab swaps a pair you choose and prints both maxima.

Method

Meeting due dates, and saying which promise you kept

Five steps, and the fourth stops a true statement being used as a false one.

Write the jobs as p:d and add the times up

If the total work exceeds the last due date, something is late no matter what, and knowing that before you start prevents the search for a schedule that does not exist. On the lab's instance the work is 25 and the last due date is 20.

Sort by due date ascending

Ties in the due dates can be broken arbitrarily for L max; the exchange argument only ever needed d_a > d_b, so equal due dates are already in order either way.

Build the clock and subtract the due dates, keeping the signs

L_j = C_j − d_j, negative for a job that finishes early. L max is the largest of these including the negatives, so a schedule where everything is early has a negative maximum lateness and that is a meaningful, useful number.

Say which objective you have just optimised, and measure the others

You have minimised L max and T max. You have not minimised sum T and you have not minimised the number of late jobs. Compute both anyway: on the lab's instance they are 17 and 4, against 16 and 2.

If total tardiness is the objective, stop and say so

There is no exchange rule for it. At this size, enumerate and report the exact optimum. At any larger size, report a value and a bound, and do not present a due-date order as though it answered the question.

Which due-date question a due-date order answers

Score 0 / 0

Choose the answer you can justify.

Five jobs, two due-date objectives, and one order that cannot serve both

The lab's opening preset — the five jobs of “One Machine, Six Objectives” with the weights dropped and the due dates kept. Every figure is what the panel reports as the rule selector is moved.

jobs A 6:8 B 4:4 C 5:12 D 3:6 E 7:20 work 25, last due date 20, so at least one job is late EDD, by due date ascending B (4), D (6), A (8), C (12), E (20) job p d C L T B 4 4 4 0 0 D 3 6 7 1 1 A 6 8 13 5 5 C 5 12 18 6 6 E 7 20 25 5 5 L max 6 T max 6 sum T 17 late 4 THE OTHER RULES, SAME JOBS SLACK d − p B A D C E L max 7 sum T 20 late 4 SPT D B C A E L max 10 sum T 18 late 3 FCFS A B C D E L max 12 sum T 26 late 4 THE ENUMERATED OPTIMA, over all 120 orders L max 6 attained by EDD T max 6 attained by EDD sum T 16 attained by B D C A E, which no rule here produces sum U 2 attained by 10 of the 120 orders B D C A E: T = 0, 1, 0, 10, 5 sum T 16 but L max 10

The two starred orders differ by one adjacent swap and neither dominates the other. EDD has the smaller worst job and the larger total; B D C A E has the smaller total and a worst job nearly twice as bad. A report that says “we scheduled by due date, so lateness is minimised” is true and is routinely heard as the other claim.

SLACK, ordering by d − p, is the rule most often confused with this one, and it is not the same rule and not optimal for anything here: 7 against 6 on maximum lateness, and 20 against 17 on total tardiness. The lab has a preset where the two orders differ, for exactly this comparison.

For a rehearsal, type A 5:5, B 4:6, C 6:7, D 2:9 — four jobs with seventeen hours of work and a last due date of nine. Predict before running it whether EDD attains the best L max, and what it costs on total tardiness. The supplied first move is that EDD is the typed order A B C D. It attains L max = 8, which is optimal, and costs 19 on sum T where 15 exists — four worse, on an instance with only four jobs.

Common mistakes

Hearing “minimises lateness” as “minimises how late things are in total”It minimises the largest single lateness. On the lab's instance that costs 17 of total tardiness where 16 exists, and on the four-job instance 19 where 15 exists. Both sentences are about lateness and they name different numbers; the rule answers one of them.

Clipping the negatives before taking the maximumL max uses the signed latenesses, so a job finishing two hours early contributes −2. Clip first and you have computed T max, which is a different objective that happens to agree whenever anything is late. On an all-early schedule the two differ, and the signed one is the informative one.

Ordering by slack d − p and calling it earliest due dateThey are different rules and they give different orders. On the lab's third preset they disagree on all four jobs; on its opening preset slack ordering gives L max = 7 where earliest-due-date gives 6. The exchange argument was about d, and d − p is not d.

Check your understanding

✓

Finish when you can prove the rule and state, unprompted, the two objectives it does not touch.

You should be able to run the adjacent exchange for a maximum, showing that both new latenesses fall below the pair's old maximum, conclude that due-date order minimises L max and T max, compute sum T and the number of late jobs for the same order, and say why total tardiness has no exchange rule rather than reaching for slack or for shortest-first.

Note: One of the two objectives EDD lost is not lost for long. Counting late jobs rather than adding up hours of lateness turns out to have a rule, and it is not a sorting rule — it builds a set of jobs that will finish on time and throws jobs out of it, and the job it throws out is not the job that was late. “Minimising the Number of Late Jobs” runs it a step at a time, and on these same five jobs it leaves two late where due-date order leaves four.