Swapping two adjacent jobs changes the completion time of those two jobs and of nothing else, and the whole change in sum C is p_b − p_a. That one subtraction is the entire proof that shortest-first is optimal: it is negative exactly when the shorter job was behind, so an order with a longer job in front of a shorter one can always be improved, and only the sorted order cannot. The lab runs the argument rather than stating it.
Core ideas
One argument, taken slowly, because every later rule on this course is this argument with a different quantity in the subtraction.
Take the jobs in positions i and i + 1 and exchange them. Everything before position i finishes at the same clock, because nothing about it changed. Everything after position i + 1 finishes at the same clock too, because the same two jobs were done in between and the same total amount of work was completed. Only two completion times move, so the difference in sum C is a subtraction rather than a recomputation.
Let the pair start at time t. Before the swap the two finish at t + p_a and t + p_a + p_b; after it, at t + p_b and t + p_b + p_a. The second of each pair is the same number, so the difference is (t + p_b) − (t + p_a) = p_b − p_a. The start time t cancels, which is why the same subtraction works at every position in every order.
If any adjacent pair has the longer job first, the swap strictly improves sum C, so that order is not optimal. The only orders with no such pair are those sorted by p ascending. Hence shortest-first is optimal — and the lab does not take this on trust: from the worst order it takes improving swaps one at a time and reports where it stops.
The material
One definition, the swap identity proved in three lines, and ten improving swaps taken in front of you.
Given an order and a position i, the adjacent exchange at i is the order obtained by swapping the jobs in positions i and i + 1 and leaving everything else alone. It is improving for an objective when the swapped order has a strictly smaller value.
Adjacent is the load-bearing word. An arbitrary transposition moves every completion time between the two jobs and gives a difference with a sum in it; an adjacent one moves exactly two, and the difference collapses to a single subtraction that does not mention the rest of the schedule.
Let a and b be adjacent, with a first, and let the pair begin at time t. Swapping them changes sum C by exactly p_b − p_a, whatever t is and whatever the rest of the order is.
Only C_a and C_b change: every earlier job is untouched, and every later job starts when the same two jobs have been done, so it starts and finishes at the same clock as before.
Before: C_a = t + p_a and C_b = t + p_a + p_b, summing to 2t + 2p_a + p_b. After: C_b = t + p_b and C_a = t + p_b + p_a, summing to 2t + 2p_b + p_a.
Subtract: the change is (2p_b + p_a) − (2p_a + p_b) = p_b − p_a. No term involving t or any other job survives.
□
Read the sign. The change is negative exactly when p_b < p_a, that is, exactly when the shorter job was behind the longer one. So any order containing an adjacent pair in the wrong length order can be strictly improved by one swap, and an order that cannot be improved by any adjacent swap has no such pair — which is to say it is sorted by processing time ascending.
The shortest processing time rule orders the jobs by p ascending, breaking ties arbitrarily. Every tie-break gives the same sum C, because swapping two jobs with equal p moves sum C by p_b − p_a = 0.
The theorem is that SPT minimises sum C, and nothing more. It says nothing about weights, nothing about due dates, and nothing about the makespan, which does not move. It also says nothing about the individual jobs: shortest-first is the rule that makes the longest job wait the longest, which is exactly what minimising an unweighted total of finish times asks for.
The lab starts from the worst order there is and repeatedly takes the first adjacent swap that improves sum C, printing the exact quantity each one moved. It is never told what SPT is. On this instance it takes ten swaps and then stops, and where it stops is the sorted order:
Ten swaps is not a bound and not an estimate; it is the count on this instance, and it is the number of pairs in a five-job order, because the starting order was the exact reverse of the finishing one. The second preset starts one swap away from sorted and takes two, not one: swapping the out-of-order pair puts a new out-of-order pair next to each other. Watching that happen is worth more than being told that greedy local improvement is subtle.
What the walk demonstrates and the theorem proves are two different things, and it is worth being clear about which is which. The walk shows that on this instance improving swaps exist until the order is sorted. The theorem shows that on every instance an unsorted order has an improving swap, so no unsorted order can be optimal. The lab then checks the conclusion a third way, against all 120 orders, and reports 58 from the enumeration as well.
Interactive
Swap two neighbours and the sum of completion times moves by p_b − p_a, and by nothing else
Method
Four steps, and the third one is where a wrong rule dies.
Call them a then b, starting at t. Do not choose a position and do not choose an instance: the argument has to work at every position in every order, and it will, because t cancels.
Only the two swapped jobs move, so the difference is (w_a C_a + w_b C_b) after minus the same before. For sum C that is p_b − p_a; for a different objective it is a different subtraction, and the rest of the argument is unchanged.
p_b − p_a < 0 exactly when p_b < p_a. That condition is the rule: keep the smaller p in front. If your condition depends on t or on another job, the objective does not have an exchange rule and the argument stops here rather than being patched.
Any order violating the condition on some adjacent pair is improvable, so it is not optimal; the orders that violate it nowhere are the sorted ones. Then run the enumeration on a small instance anyway. A proof and a measurement that agree are worth more than either alone, and the lab prints both.
The lab's opening preset, with the subtraction written out at every step. The instance is five jobs whose longest is nine hours long, started in the order that makes everything wait behind it.
The −3 at position 1 is the whole lesson in one line. Two completion times changed, 9 and 15 became 6 and 15, and the three jobs after the pair finished at 20, 23 and 25 both before and after. The lab recomputes all five completion times on both schedules and confirms it rather than asking you to believe it.
Notice that the walk never goes uphill and never needs to. Greedy local improvement solves this problem exactly, which is unusual and is a consequence of the identity: there is no order with an out-of-order pair that is nonetheless optimal, so there is nowhere for a local search to get stuck.
For a rehearsal, switch to the preset where only one adjacent pair is out of order and predict the number of swaps before running it. The supplied first move is that the typed order A B C D E has p = 2, 3, 7, 5, 6, so the only inverted adjacent pair is C, D. The answer is not one swap. Say why, and by how much each of the swaps moves sum C, before the panel tells you.
You should be able to set up an adjacent pair with a symbolic start time, write both schedules' completion times, subtract to get p_b − p_a, say why no other job appears in the difference, read the improvement condition off the sign, and finish the argument by observing that the orders with no improving swap are exactly the sorted ones.
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.