One machine, five jobs, no idle time and nothing random: the simplest scheduling problem there is. It already has six sensible objectives, and the order that is best for one of them is beaten on the others by a different order each time. One number does not move at all — the makespan is the same in every one of the 120 orders — and knowing which number that is, before any rule is chosen, is what this lesson is for.
Core ideas
Three ideas, and the first is a subtraction that has no answer: there is nothing to optimise about the makespan on one machine, and a reader who does not know that will spend effort on it.
One machine that never stops finishes the last job when the work runs out, and the work does not depend on the order. On the lab's five jobs that is 6 + 4 + 5 + 3 + 7 = 25, and the panel reports 25 for all 120 orders. Every other objective moves, some of them by a factor of two. Sequencing buys you nothing at all on the makespan and a great deal on the rest, and that asymmetry is the shape of the whole subject.
Shortest-first gives the least total completion time, 65. Smith's ratio gives the least weighted total, 108. Earliest-due-date gives the least maximum lateness, 6. The fewest late jobs is 2, and the least total tardiness is 16 — attained by an order that no rule on this course produces. Five different orders, five different answers, and none of them is the schedule.
Each objective in the panel is computed twice, by a forward clock and by a position-weighted sum that never forms a running clock, and the two must agree before anything is drawn. Then each is compared with the best of all 120 orders, found by enumeration. So the word “optimal” on the screen means a comparison was made, and when the instance is too large to enumerate the panel says the claim is unchecked rather than printing it anyway.
The material
The definitions, one order scored against all six at once, and the five rules that each win exactly one of them.
n jobs, job j with a processing time p_j, a weight w_j and a due date d_j. One machine runs one job at a time, every job is available at time zero, no job is interrupted, and the machine never idles. A schedule is then just an order.
For an order, C_j is the clock when job j finishes. The lateness is L_j = C_j − d_j, which may be negative; the tardiness is T_j = max(L_j, 0), which may not; and U_j is 1 if C_j > d_j and 0 otherwise. The six objectives are sum C, sum w C, L max, T max, sum T and sum U, and every one of them is to be made small.
The makespan C max is the seventh, and it is the one worth disposing of first. It is the largest C_j, and on this model it is sum p whatever the order, because the machine starts at zero and never stops. That is not a theorem about a clever schedule; it is arithmetic about a machine with no gaps in it.
With every job available at time zero, no preemption and no forced idle time, every order has makespan sum p.
The machine starts the first job at time 0 and starts each later job the instant the previous one finishes, so at every moment before the end it is working.
The total amount of work is sum p and none of it is done twice or skipped, so the last job finishes at sum p. The order was never used in the argument, so it cannot matter.
□
Drop any one of the three assumptions and this stops being true, which is why they are stated rather than assumed. Release dates force idle time; a second machine makes the makespan the hard part; and a setup cost that depends on which job ran before makes the total work itself depend on the order.
Every column there is read off one clock. The C column is the running total of p; wC multiplies it by the weight; L subtracts the due date and is allowed to be negative; T clips the negatives to zero. Nothing in the table required a decision, and that is the point — the decision was the order, and it was made before any of this.
Four different orders appear in that last column and none of them is the one typed. The arrival order is optimal for nothing, which is unremarkable; what is worth looking at is that no single order appears twice. D B C A E is shortest-first and is 9 worse than the best on weighted completion time. B D A C E is earliest-due-date and is 17 against a best total tardiness of 16. Being best at one of these is normally being beaten at the rest.
The lab fills the order box from a rule. Shortest processing time gives D B C A E, which attains sum C = 65. Smith's ratio p/w gives D C B A E, which attains sum wC = 108. Earliest due date gives B D A C E, which attains L max = 6 and T max = 6.
Now the two that lose. Heaviest-weight-first — a rule that sounds exactly as reasonable as the others — gives C D B A E and costs 111 on weighted completion time against the 108 Smith's ratio reaches. And shortest-first, which is provably optimal for sum C, costs 114 on the weighted version: the same order, a different question, and a worse answer than the rule that loses to it on the unweighted one.
So the first thing to do with a scheduling problem is not to choose a rule. It is to write down which of these six numbers you are being paid to make small, because the rules disagree and there is no tie-break between them that lives inside the arithmetic. A workshop that is judged on how many orders ship late wants sum U and should not be running shortest-first; a workshop billed by customer-hours waiting wants sum w C and should not be running earliest-due-date.
This is the path's hazard in its cheapest possible form. Every figure in the table above is exact and every claim of optimality has been checked against 120 orders. An answer that is right about sum C and was wanted for sum T is still wrong, and nothing in the solve will ever say so.
Interactive
The makespan never moves; everything else does, and no order wins on all of them
Method
Five steps, and the last one is the only one that involves a decision.
name p:w:d, and say out loud what each number is. A weight is not a priority number to be sorted on and a due date is not a deadline that cannot be missed; they are the multiplier in one objective and the subtrahend in three others.
C is the running total of the processing times in the chosen order. Everything else on the page comes off that one column, which is why an error there is an error in all six figures at once and an error anywhere else is local.
sum C adds the column. sum w C adds it weighted. L_j = C_j − d_j, and L max is the largest of those including the negative ones. T_j clips at zero, sum T adds the clipped values, sum U counts the positive ones.
It should equal sum p, and it should be the same for every order you try. If it is not, one of the three assumptions has quietly been dropped — usually a release date, sometimes an idle gap you put in by hand.
Write the objective at the top of the page and then choose. Every rule in this course is optimal for exactly one thing and beaten on the rest, and the decision about which thing was made outside the arithmetic long before the first job ran.
The lab's opening example, in full. The instance is its first preset, so every line below can be checked against the panel by switching the order box between the five rules.
The starred lines are the three theorems of the next three lessons, and each of them is a rule attaining an enumerated optimum. The unstarred figures beside them are the price of that optimum measured on a different objective, and they are what makes this a subject rather than a list of rules.
WEIGHT is the row to stare at. Running the heaviest job first is a perfectly sensible policy, it is what most workshops actually do, and it costs 111 where 108 was available from a rule that is no harder to run. The gap is small and it is not zero, and nothing in the schedule announces it.
For a rehearsal, switch the preset to the four-job example and repeat the whole table. The supplied first move is that the makespan will be 2 + 8 + 3 + 6 = 19 and will not move; predict, before the panel says so, whether the typed order is optimal for any of the six. It is optimal for none of them, and the total tardiness it costs is 14 against a best of 8.
You should be able to build the completion-time clock for a typed order, read sum C, sum w C, L max, T max, sum T and sum U off it, state that the makespan is sum p and say which three assumptions make that true, and explain why an order that attains one of the six optima is normally beaten on the other five.
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.