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