The same swap, with weights on, moves sum w C by w_a p_b − w_b p_a. That is negative exactly when p_a / w_a > p_b / w_b, so the ordering key is the ratio and not the time and not the weight. The two rules that use one number each are both wrong, and on the lab's instance running the heaviest job first costs 113 where the ratio reaches 97.
Core ideas
One new subtraction and two corollaries, one of which is that the two rules a reader would guess are both beaten on the same instance.
Only C_a and C_b move, exactly as before, so the change in sum w C is w_a C_a + w_b C_b after minus before. Substituting the four completion times and cancelling the start time gives w_a p_b − w_b p_a. Nothing about the derivation changed; the objective put a multiplier on each term and the multiplier survived into the answer.
w_a p_b < w_b p_a divides through by w_a w_b, which is positive, to give p_a / w_a < p_b / w_b. So the swap improves exactly when the job in front has the larger ratio, and the rule is to sort by p/w ascending. A long heavy job and a short light job can have the same ratio, in which case the order between them does not matter at all: the difference is exactly zero.
Heaviest-weight-first ignores p and puts an eight-hour job at the front because it is worth four; shortest-first ignores w and puts a nearly worthless job at the front because it takes two hours. On the lab's instance they cost 113 and 109 against the ratio's 97. Neither is a silly rule; each is a correct rule for a question nobody asked.
The material
The subtraction with weights in it, the rule it produces, and a measured comparison against the two rules a reader would reach for first.
Each job carries a positive weight w_j, and the objective is sum w C = sum over j of w_j C_j. The weight is the cost of one unit of waiting for that job: twice the weight means an hour of delay hurts twice as much. Weights are not priorities and they are not ranks — they are multipliers, and the arithmetic uses their sizes.
Let a and b be adjacent with a first. Swapping them changes sum w C by exactly w_a p_b − w_b p_a, whatever the start time and whatever the rest of the order.
Only C_a and C_b change, for the same reason as in the unweighted case: earlier jobs are untouched, and later jobs start once the same two jobs have been done.
Let the pair start at t. Before, the two contribute w_a(t + p_a) + w_b(t + p_a + p_b). After, they contribute w_b(t + p_b) + w_a(t + p_b + p_a).
Subtracting, every term in t cancels, w_a p_a cancels against itself and w_b p_b against itself, and what is left is w_a p_b − w_b p_a.
□
Divide the improvement condition w_a p_b − w_b p_a < 0 by the positive quantity w_a w_b and it becomes p_a / w_a > p_b / w_b. This is why the weights must be strictly positive and why the lab refuses a weight of zero rather than accepting it: the ratio is a division, and a job of no weight at all is a job whose position cannot be argued about by this method.
The weighted shortest processing time rule, or Smith's rule, orders the jobs by p / w ascending. It minimises sum w C. With all the weights equal it is p divided by a constant, so it is shortest-first again — the unweighted theorem is the special case, not a separate result.
B is both the longest job and the heaviest, which is what makes the instance worth looking at: the two one-number rules disagree about it as loudly as they can. Heaviest-first puts B at the very front, where its eight hours delay everything else. Shortest-first puts it at the very back, where four units of weight wait the whole nineteen hours. The ratio puts it second, and the 97 is not available any other way.
Heaviest-first produces B C D A. The ratio of B is 2 and the ratio of C is 2/3, so the pair at the front is out of order and the identity says the swap moves w_B p_C − w_C p_B = 4 × 2 − 3 × 8 = 8 − 24 = −16.
Make that one swap and the order becomes C B D A, worth 113 − 16 = 97, which is optimal. So the entire gap between the rival rule and the theorem on this instance is one adjacent pair, and the exact size of the gap was available from two multiplications before the swap was made.
Three swaps, three subtractions, and the walk stops on Smith's order without ever having been told what Smith's rule is. That is the same demonstration as in the unweighted case with one difference worth noticing: the largest single improvement, −16, came last. There is no reason for the improvements to get smaller, and a reader who stops swapping because the gains look small has stopped early.
The unweighted rule is not merely analogous to this one; it is this one. Set every weight to the same value w and the ratio p/w orders the jobs exactly as p does, so Smith's rule returns the shortest-first order and sum w C = w sum C is minimised by minimising sum C. The lab has a preset with four equal weights for exactly this check, and the two rules return the same order on it.
One warning about the ratio, because it is the kind of thing that survives into practice as folklore. p/w is an ordering key and nothing else. It is not a cost, it is not a priority score to be compared across instances, and adding the ratios up or averaging them computes nothing. The only fact about it is that sorting by it ascending minimises sum w C.
Interactive
The swap moves sum wC by w_a p_b − w_b p_a, which is negative exactly when p_a/w_a > p_b/w_b
Method
Four steps, and the second is the one that separates this rule from the two that look like it.
p:w, with w the cost of one unit of waiting. If you cannot say what a weight of 4 means relative to a weight of 1 in the units of the problem, the model is not finished and no rule will finish it for you.
As a fraction. 2/3 and 2 and 3 are the keys on the lab's instance, and two jobs there tie at 3. Rounding the ratios to decimals is how a genuine tie becomes a fictitious ordering, and on a tie the exchange identity says the order genuinely does not matter.
Smallest ratio first. Checking one pair by hand is worth the seconds it takes: on the lab's instance C has ratio 2/3 and B has 2, so C goes first even though B is four times the weight.
Run heaviest-weight-first on the same jobs and compute sum w C for both. On the lab's instance that is 113 against 97, and the difference is the number worth carrying into the argument about whether the rule is worth changing.
The lab's opening preset. B is eight hours long and worth four, so the two one-number rules put it at opposite ends of the schedule and the ratio puts it in the middle.
The line to keep is the one about shortest-first: it attains sum C = 37, which is the true optimum for the unweighted objective, and it costs 109 on the weighted one. A rule can be exactly, provably optimal and be the wrong rule, and there is nothing in its output that reveals which of the two it is being.
The tie between A and D at ratio 3 is worth checking by hand. A is 3:1 and D is 6:2; the swap moves w_A p_D − w_D p_A = 1(6) − 2(3) = 0. Two of the twenty-four orders attain 97, and the lab reports the count rather than naming one order and implying it is unique.
For a rehearsal, type the five jobs of “One Machine, Six Objectives” in as p:w — A 6:1, B 4:2, C 5:4, D 3:3, E 7:1 — and work out the three figures before the panel does. The supplied first move is that the ratios are 6, 2, 5/4, 1, 7. Smith's rule gives 108, heaviest-first gives 111 and shortest-first gives 114; one adjacent swap separates the shortest-first order from Smith's, and it is worth −6.
You should be able to run the adjacent exchange with weights, reach w_a p_b − w_b p_a, divide by w_a w_b to turn the improvement condition into p_a/w_a > p_b/w_b, state Smith's rule, show that equal weights reduce it to shortest-first, and compute by how much a named rival rule loses on a given instance rather than asserting that it does.
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.