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 d _{i} and a length t_{i}, minimize the maximum lateness of the resulting schedule.”*

We need to assign a start time s_{i} to each job i. Jobs are allowed to be late i.e., a job i may finish at time f_{i} = s_{i} + t_{i} > d_{i}. If job i is late, its lateness is defined to be l_{i} = f_{i} – d_{i}. Otherwise, l_{i} = 0. So the objective is to find a schedule that minimizes the maximum lateness, L = max_{i} l_{i}.

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 d_{i} > d_{j}.

**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 d_{j} < d_{i}. 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) – d_{i} < f(j) – d_{j}, 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 ^{n}C_{2} inversions, hence after at most ^{n}C_{2} 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

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

I know the algorithm here is extremely simple but its proof is rather complicated. I wanted to illustrate how proofs are laid out for greedy algorithms, in this case, using an exchange argument. In case you haven’t already seen my other posts, I’ve written a few other posts on scheduling problems having a greedy solution (eg. Interval Scheduling Problem, Interval Partitioning Problem).

Most scheduling problems, however, do not have a greedy solution (eg. Weighted Interval Scheduling Problem which has a DP solution) and some of them are actually NP-complete (eg. Flow Shop Scheduling Problem, Multiprocessor Scheduling, Open-shop_scheduling) so an optimal greedy algorithm is unlikely to exist for them.

I’ll be happy to look at other scheduling problems. You can drop me a mail at kartikkukreja92[at]gmail[dot]com.