Shoemaker Proof

I am working as a coach for our programming team.

One of the problems is the Shoemaker problem. The complete description can be found at Shoemaker Description.

The simple solution is to sort the jobs in order by the cost/delay ratio, then do the jobs in decreasing order.

It is a simple solution, but I was not convinced that it was correct, so I proved it as follows.

I will use the following annotations to indicate sums, costs and delays.

cost(m) will be the cost for each day that job m is delayed.
delay(m) will be the number of days it takes to complete job m. All jobs that are completed after m will incur a cost for this delay. Job m does not pay a penalty for itself.
sum_cost(i,j) will be the sum of all the costs for jobs i through j.

It is easy to validate if there are only two jobs. The cost for each job is

Do 1 first: delay(1)*cost(2)
Do 2 first: delay(2)*cost(1)

The first formula will be less than the second, when cost(2)/delay(2) < cost(1)/delay(1)

The difficulty arises when there are more terms.

Assume that the jobs have been sorted by cost/delay.

The proposed minimum sum is
delay(1)sum_cost(2,n) + delay(2)sum_cost(3,n) + ... + delay(n-1)sum_cost(n,n)

Consider any other sum than this one. A position m can be found such that

cost(m)/delay(m) < cost(m+1)/delay(m+1)

In other terms,

formula 1 (f1): delay(m+1)cost(m) - delay(m)cost(m+1) < 0

By switching the order of these two in the sum, then a smaller cost will result.

Term m: delay(m)sum_cost(m+1,n) + delay(m+1)sum_cost(m+2,n) =

Effect of switching term m and term m+1:
delay(m)sum_cost(m+1,n) - delay(m)cost(m+1) + delay(m+1)sum_cost(m+2,n) + delay(m+1)cost(m)

The difference between this new term and the original is:
delay(m+1)cost(m) - delay(m)cost(m+1)

By the above formula (f1), this term is less than 0. The conclusion is that any sum that has terms that are out of order can be rearranged to find a smaller sum. It follows that the sum formed from the jobs in descending order by cost/delay is the minimum. QED.