Scheduling to minimize lateness

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.

An instance of scheduling to minimize lateness

An instance of scheduling to minimize lateness

This problem can be solved optimally with a simple greedy strategy of scheduling jobs based on earliest deadline (Earliest Deadline First).

Algorithm:

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

Advertisements

2 thoughts on “Scheduling to minimize lateness

  1. Hi Kartik , this is very easy and basic problem, which u mention, there are many more complicated problems in Scheduling , if u try to solve them by greedy method, it can be useful to me and others. if u want i can send u the scheduling problems

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s