Okay let's continue the perfect correctness of our greedy algorithm for
minimizing the sum of the weight of completion times and let's move onto
understanding the ramifications of the exchange of jobs suggested at the
conclusion of the previous video. So recall the basic ideas to use this
observation that the optimal schedule sigma star by virtue of our assumption of
being different from the greedy one has to have this pair of consecutive jobs
where the earlier one has the higher index.
So my question for you involves thinking about how the completion times of all of
the jobs change after we make this exchange of the two jobs i and j.
Which ones go up? Which ones go down?
Which ones are unaffected? Which ones can we not actually predict
whether they go up or down? All right, so the answer to this, quite
key question is the third answer. Jobs other than I and J are unaffected, the
completion time of job I goes up, and the completion time of job J goes down.
So let's review why. Consider a job K, other than I or J, it's probably easiest
to see if in sigma-star, K completes before I and J, scheduled earlier than I
and J. Don't, remember what the completion time
of a job is, it's just the time that needs to elapse before it gets done, so
it's the sum of the job lengths up to, and including that job itself.
So if K was scheduled before I and J before, it's exactly the same after I and
J are swapped. You don't know the difference.
Exactly the same set of jobs precedes Job K is the force whose completion time is
the same. But if you think about it, this exact
same argument is true for jobs K that succeed INJ.
So before we do the swap, it has to wait for a bunches ops to complete, including
INJ and after we swap INJ, it still has to wait for INJ to complete.
Yeah, they complete in opposite order but who cares?
The amount of time of the lapse is exactly the same.
So importantly, jobs other than INJ are completely agnostic to the swap.
Their completion time is exactly the same as before.
So that's the first. Part.
so job I, it's completion time goes up. It's easier to see why it used to be
before J, now it has to wait for J. In fact we can say exactly how much
completion time goes up by. It goes up by exactly the length of J.
That is the extra time that now needs to elapse before I gets completed.
By exactly the same reasoning the completion time of job j actually drops
it has to wait for the same jobs to complete before it being accepted no
longer has to wait for job I. So, not only can we say its completion
time goes down we can say that it goes down so by precisely the length of job I.
So now we are in a great position to finish off this proof.
Let's summarize what we got so far. So, for a cost benefit analysis of
exchanging I and J, we discovered the cost is limited to an increase in the
completion time of job I and the benefit is limited to the decrease in the
completion time of job J. Specifically the cost, the new cost
incurred by the exchange is the weight of job I times the amount by which it's
completion time went up, namely the length of job J.
Similarly, the benefit of the exchange is the drop of LI and J's completion time
and that gets multiplied by it's weight's of WJ.
So now finally we are at the point where we can use the fact that this purportedly
optimal schedule sigma star schedules I and J in some sense incorrectly,
with a higher index job first despite it having a lower ratio in contrast to the
principles followed by our greedy algorithm.
So why is it relevant that the earlier job I has a higher index?
Well, a higher index corresponds to a lower ratio.
Remember we did this notation switch so that the first job has the highest ratio,
the second job has the second highest ratio and so on.
So the bigger your index, the further you are down in the ordering, the lower your
ratio. So because I is bugger than J, that means
I's ratio is worse than J. The usefulness of this becomes even more
apparent when we clear denominators. We multiply both sides by the, by LI
times LJ. And then we find that WI times LJ is
strictly less than WJ times LI. But what are these, these are just the
cost and benefit terms respectively of our thought experiment exchange,
exchanging I and j. So what does it mean that the benefit of
the swap outweighs the cost? It mean if we take sigma star, this
reportedly optimal solution, and we invert the jobs I and j, we get a
schedule with an even better weighted sum of completion times, but that is nuts.
That's absurd, sigma star was supposed to be optimal.
So here's our contradiction. That completes the proof.