The problem can be stated as follows :
“Given a set of n jobs all of which must be scheduled on a single resource such that all jobs arrive at time s and each job has a deadline di and a length ti, minimize the maximum lateness of the resulting schedule.”
We need to assign a start time si to each job i. Jobs are allowed to be late i.e., a job i may finish at time fi = si + ti > di. If job i is late, its lateness is defined to be li = fi – di. Otherwise, li = 0. So the objective is to find a schedule that minimizes the maximum lateness, L = maxi li.
This problem can be solved optimally with a simple greedy strategy of scheduling jobs based on earliest deadline (Earliest Deadline First).
Proof of optimality:
We will prove the optimality of our greedy algorithm by transforming an optimal solution step-by-step into our solution. At each step, we will show that the maximum lateness does not increase.
Claim: There is an optimal schedule with no idle time. An idle time is a gap in a schedule, time when no job is being performed yet there are jobs left.
Proof: It is easy to see that there must exist an optimal schedule that has no idle time. We can transform an optimal schedule having idle times into one having none by scheduling jobs earlier during the gaps. This can only decrease their finishing time and hence lateness, never increase it.
Observation: Our solution has no idle time.
Let us say that a schedule A has an inversion if it schedules a job i before another job j but di > dj.
Observation: Our solution has no inversion.
Claim: All schedules with no inversions and no idle time have the same maximum lateness.
Proof: If two different schedules have neither inversions nor idle times, they can only differ in the order in which jobs with identical deadlines are scheduled. Among all such jobs having the same deadline, the last one has the greatest lateness and this lateness does not depend on the order of the jobs.
Claim: There is an optimal schedule that has no inversions and no idle time.
Proof: We will prove this by using an exchange argument. Let OPT be an optimal schedule. If OPT has an inversion, then there is a pair i and j such that j is scheduled immediately after i and dj < di. After swapping i and j, we get a schedule with one less inversion. Since job j finishes earlier now than in OPT, its lateness cannot increase. In the new schedule, job i finishes at time f(j) – the finishing time of job j in OPT. Its lateness is f(j) – di < f(j) – dj, which is less than the lateness of job j in OPT. Hence, swapping jobs i and j does not increase the maximum lateness of the schedule. Since there are at most nC2 inversions, hence after at most nC2 swaps, we get an optimal schedule with no inversions.
From the fact that there is an optimal schedule having no inversions and no idle time combined with the facts that all schedules with no inversions and no idle time have the same maximum lateness and that our schedule has no inversions and no idle time, we can conclude that our schedule is optimal.
This proves the optimality of the greedy algorithm.
Time Complexity: O(n log n) (dominated by the time to sort the jobs)
Take a look at C++ implementation.
Reference: Algorithm Design by Kleinberg and Tardos