Scheduling to Minimize Lateness: An Exchange Argument

In this section we look at solving another scheduling problem where there is one resource and a set of requests to use that resource for a certain amount of time. Each request has a deadline and a time interval length and can be scheduled any time before the deadline. Different requests cannot overlap. An example of this problem is scheduling jobs to minimize lateness. The algorithm must determine a start and a finish time for each request. If the finish time of a request is greater than the deadline then we note that the job is late. The lateness of a job is calculated by the finish time minus the deadline. If the request is not late then the lateness is 0.

The Algorithm:

There are two greedy ways to approach the problem and sort the data:

• order the jobs smallest to largest by the length of the job
• order the jobs smallest to largest by their slack times (deadline minus the length of the job)

Both of these approaches fail and will not produce the optimal solution. Our approach will be to sort the jobs by their deadlines in increasing order. The jobs will be scheduled in this order with each job's start time beginning at the previous jobs finish time.

  Order the jobs in order of their deadlines
  Assume the notation that d<sub>1</sub> =< ... =< d<sub>n</sub>
  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<sub>i</sub>
     Let f = f + t<sub>i</sub>
  End
  Return the set of scheduled intervals [s(i),f(i)] for i = 1,...,n
  

Analysis

The solution that is produced from this algorithm does not have any idle time, meaning that there are no gaps between jobs where the machine is not doing anything and there are still jobs to complete.

(4.7) There is an optimal schedule with no idle time.

To prove that our solution is optimal and the maximum lateness is minimized, we use the exchange argument. We consider an optimal schedule O and modify O to transform it to the schedule that our greedy algorithm produced. If a schedule puts a job with a greater deadline ahead of a job with a smaller deadline, then we say that schedule has an inversion. Our greedy algorithm produces a schedule with NO inversions.

(4.8) All schedules with no inversions and no idle time have the same maximum lateness

Proof

If there are two schedules without idle time or inversions, they can only be different in the order they schedule jobs with the same deadline. Jobs with the same deadline are scheduled consecutively and the last one as the maximum lateness which is not affected by the order of the jobs. To prove this we take an optimal schedule with no idle time and convert it to a schedule with out any inversions. The changes we make to the schedule will not increase the maximum lateness. So both schedules are optimal

(4.9) There is an optimal schedule that has no inversions and no idle time

Proof