Search code examples
algorithmgreedy

Understanding scheduling to minimize lateness problem

I was reading the following link to get a better understanding of the optimality for the algorithm. I was wondering why the "inversion" is needed for the proof of optimality? I have been scratching my head about this for awhile. Any help is appreciated. Thanks!

https://kartikkukreja.wordpress.com/2013/11/24/scheduling-to-minimize-lateness/

Solution

  • The logic is:

    Assume there is an optimal solution: 1) There is always a no inversion version of solution compared to the optimal solution with NO EXTRA latency was introduced;

    2) If 1) is solid, then we can narrow down the problem to how to schedule jobs to minimize idle time

    3) Obviously, the proposed solution already minimize the idle time because there is 0 idle time.

    So, in short, introducing inversion is to narrow down the problem to minimize idle time.