Chapter 4.2: Minimizing Lateness

For situations in which there is only a single resource and a set of n requests to use the resource for an interval of time. Each resource is available starting at time s and each request i has deadline d_i. Each request requires time t_i but is willing to be scheduled at any time before the deadline. Obviously, since there is only one resource, different requests must be assigned nonoverlapping intervals.

We will denote the start time of request i as s(i) and the finish time f(i)=s(i)+t_i. We will say that a request is late if it misses its deadline. The lateness of such a request is l_i=f(i)-d_i. Note that l_i=0 if request i is not late. Our goal is to assign each request to an interval in such a way that minimizes the maximum lateness.

The greedy algorithm that always produces an optimal solutions sorts the requests in increasing order of their deadlines, and schedules them in this order. Basically, it ensures that the jobs with the earliest deadlines get completed earlier. Here's an outline of the algorithm:

• Order the jobs in order of their deadline
• assume, for simplicity of notation, that d_i ⇐…⇐ d_n
• initially f=s
• consider the jobs i=1,…,n in this order

-assign job i to the time interval from s(i)=f to f(i)=f+t_i -let f=f+t_i

• end
• return the set of scheduled intervals [s(i),f(i)] for i=1,…,n

This algorithm produces a schedule with no idle time. If there is an optimal schedule with idle time, greedy will eliminate the idle time and create a schedule that is more optimal than optimal (hence, the optimal schedule has no idle time).

To prove that greedy is optimal, we use an exchange argument. We modify the optimal solution until it looks like the greedy solution, preserving optimality at each step. We say that a schedule has in inversion if a job i with deadline d_i is scheduled before another job j with an earlier deadline d_i < d_i. The greedy schedule has no inversions. All schedules with no inversions and no idle time have the same maximum lateness. Basically, if the optimal solution has an inversion then we can swap the two inverted jobs and the resultant schedule will have one less inversion and a maximum lateness no larger than before. So in the end, the optimal schedule can be manipulated to look like greedy, but still be optimal. Therefore, the greedy algorithm is optimal.

I would rate this section a 10. It was very easy to read and followed from the lectures.