Counting late jobs is a different objective again, and it has an exact algorithm rather than a sorting rule. Moore–Hodgson offers the jobs in due-date order, and the moment the accepted set runs past a due date it discards the longest job accepted so far. The job discarded is usually not the job that went late, and on the lab's five jobs the algorithm leaves two late where due-date order alone leaves four.
Core ideas
Three ideas: what the objective throws away, why the discard is the longest job, and why the answer is a set rather than an order.
sum U adds one for each job that misses its date and nothing for how badly. A job one minute late and a job three weeks late contribute the same. That makes the objective coarse and makes it the right one surprisingly often — a shipment either made the sailing or did not — and it changes the problem completely, because now a job can be written off entirely and pushed to the very end at no further cost.
When the set runs past a due date, exactly one job has to go, and every candidate costs the same one unit of sum U. So take the one that frees the most machine time, which is the longest job accepted so far. On the lab's instance the job that goes late at the second step is D, taking three hours, and the job discarded is B, taking four: the same one late job either way, and one extra hour of room for everything after it.
What the algorithm computes is the largest set of jobs that can all finish on time. Once that set is known, running it in due-date order is what makes it feasible, and the discarded jobs go afterwards in any order at all — they are late whatever happens and no objective here prices how late. So the output is kept, then discarded, and only the first half is a scheduling decision.
The material
The objective, the algorithm in four lines, five steps run in front of you, and the two rival rules it beats.
U_j is 1 when C_j > d_j and 0 otherwise, and the objective sum U counts the late jobs. A schedule is measured by how many promises it broke, not by how far.
Sort the jobs by due date ascending. Keep a set S, initially empty, and a running finish time. Offer the jobs in that order: add the next job to S and advance the finish time by its processing time. If the finish time now exceeds the due date of the job just added, remove from S the job with the largest processing time and reduce the finish time by it.
At the end, S is a largest set of jobs that can all be on time. Schedule S in due-date order, then the discarded jobs in any order. The number of late jobs is the number discarded.
The algorithm is offered the jobs in due-date order and it is not the due-date rule. That distinction is the whole reason it works, and the lab prints both figures side by side so it cannot be blurred: due-date order alone leaves four jobs late on the instance where the algorithm leaves two.
D is the job that pushed the set past a due date: adding it took the finish from 4 to 7 against D's due date of 6. The instinct is to discard D. Either choice leaves exactly one job late at this point, so the two are tied on the objective and the tie is broken by what is left behind.
Discarding D frees three hours; discarding B frees four. The algorithm takes the four, and the extra hour is what lets C and E both join later without another discard. B had been comfortably on time at step 1 and is thrown out at step 2 without ever having been the problem.
Due-date order leaves four late, and it is not a bad rule — it is the optimal rule for maximum lateness on this very instance. It loses here because it never gives up on anything: it keeps trying to run B and A on time and fails at both, and the hours spent failing make C late as well. Writing two jobs off at the start is what buys the other three.
That is the difference between a sorting rule and an algorithm, and it is why this lesson is not a fourth exchange argument. There is no key you can sort the jobs by that produces D C E B A; the answer depends on a set being built and repaired, and the repair looks at jobs that were accepted several steps earlier.
It does not minimise total tardiness, and it does not try to. Its output on the lab's instance runs the two discarded jobs at the very end, where B finishes at 19 against a due date of 4 and A at 25 against 8. That is 15 + 17 = 32 hours of tardiness against the 17 due-date order costs, and the algorithm is indifferent to all of it, because the objective counts jobs.
It also does not weight the jobs. The weighted version — minimise sum w U, the value of the work that misses its date — is a genuinely harder problem, and no version of this argument reaches it: the tie that let us discard the longest job was a tie because every discard cost one unit, and with weights the discards cost different amounts. The lab does not offer a weighted mode, and this is why.
One structural point worth keeping. The kept set finishes on time in due-date order, and the lab checks that job by job rather than trusting it: D at 3 against 6, C at 8 against 12, E at 15 against 20. If a set can be run on time at all, it can be run on time in due-date order — which is the exchange argument of “Earliest Due Date and Maximum Lateness”, used here as a tool rather than as a result.
Interactive
The job thrown out is the longest one accepted so far, not the one that was late
Method
Five steps, and the fourth is the one people get wrong.
This is the order they will be offered in, not the answer. The answer is the set that survives, and the algorithm is not finished until every job has been offered once.
The finish time is the sum of the processing times of the jobs currently in the set, so adding a job advances it by that job's p. Keep the number in front of you; it is the only state the algorithm has besides the set.
Not with any other job's due date. Because the set is kept in due-date order and every earlier job was on time when it was checked, the newest job is the only one that can have gone late.
The longest in the whole set, which may be a job accepted several steps ago and may be the job just added. Reduce the finish time by that job's processing time. Discarding the job that went late is the natural move and it is not the algorithm: on the lab's instance it would free three hours where four were available.
The survivors all finish on time, and the count of late jobs is the count of discards. The order among the discarded jobs is free — they are late however they run, and this objective does not price how late.
The lab's opening preset — the same five jobs as the due-date lesson. Every line is what the panel shows as the step slider is moved from one to five.
Step 2 is the step to reread. The job that went late was D; the job thrown out was B. Both choices leave one job late at that moment, so the objective cannot distinguish them, and the algorithm breaks the tie on the only thing that matters afterwards — how much machine time the discard returns. Four hours rather than three is the whole reason C and E both fit later on.
The bottom block is the reason this lesson exists. Due-date order is the optimal rule for maximum lateness on these same jobs, and it is twice as bad here. There is no ordering of the five jobs by any key that produces D C E B A; the answer came from a set that was built and repaired, and the repair reached back to a job accepted two steps earlier.
For a rehearsal, switch to the preset with one twelve-hour job and four small ones and predict the run before starting it. The supplied first move is that the four small jobs B 2:5, C 3:7, D 2:9, E 4:13 are offered first and all fit, reaching a finish of 11. Say what happens when the twelve-hour job arrives, which job is discarded, and how many end up late — and then check whether the big job could have been kept alongside any of the others.
You should be able to offer the jobs in due-date order, maintain the set and the running finish time, compare against the due date of the job just added, discard the longest job in the set when the set runs late, check the surviving set job by job, report the schedule as the kept set followed by the discards, and say what the same jobs cost under due-date order alone.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.