4.2. Scheduling to Minimize Lateness: An Exchange Argument

• We have a single resource and a set of n requests to use the resource
• The resource has a deadline d _i and requires a contiguous interval of time t _i
• Each request is flexible: It can be scheduled at any time before its deadline.
• Each accepted request is assigned an interval of length t _i , and different requests are assigned nonoverlapping intervals
• Let S = the overall start time
• Each request i is assigned an interval of time of length t _i = [ S(i), fi)], where f(i) = S(i)+ t(i)
• The algorithm must always determine the start time
• Lateness, l _i = f(i) - d(i))
• l _i = 0 if the request i is not late
• A request is late if it misses the deadline –>f(i)> d _i
  

–> Goal of the algorithm: Minimize the maximum lateness, L = max_i l _i by scheduling all requests using nonoverlapping intervals.

• After quite a bit of analysis, we find that the optimal solution to this problem is using a method called Earliest Deadline First:sort the jobs in increasing order of their deadlines d _i and schedule them in this order.
• Thus jobs are scheduled in the order d₁,d₂,…,d_n
  
• s = start time for all of the jobs
• f = finishing time of the last scheduled job

Order the jobs in order of their deadlines –> Takes O(nlogn) time
Assume d₁ ≤ d₂ ≤ d₃,…,d _n-1 ≤ d_n
Initially f = s –> Takes O(1) time
Consider the jobs i= 1,2,…,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,2,…,n

• Exchange Argument: Gradually modifying an optimal schedule,conserving its optimality at each step, but eventually transforming it into a schedule similar to the schedule given by the greedy algorithm to prove the optimality of the latter.
• There is an inversion if a job i with deadline d_i is scheduled before another job j with deadline d_j
• The greedy algorithm has no idle time and by definition,no inversions. There is an optimal schedule with no idle time.
• All schedules with no inversions and no idle time have the same maximum lateness.
• There is an optimal schedule that has no inversions and no idle time.
• As a consequence, the schedule produced by the greedy algorithm has optimal maximum lateness

–> For proofs of the above claims,see the book of the course

I give this section an 8/10 for being brief and concise in its explanation of the material.