This is an old revision of the document!


4.2. Scheduling to Minimize Lateness: An Exchange Argument

The Problem

  • 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 = maxi l i by scheduling all requests using nonoverlapping intervals.

Designing the algorithm

  • 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 d1,d2,…,dn
  • s = start time for all of the jobs
  • f = finishing time of the last scheduled job


Algorithm

Order the jobs in order of their deadlines –> Takes O(nlogn) time
Assume d1≤ d2 ≤ d3,…,d n-1 ≤ dn
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 + ti
Let f = f + ti

End
Return the set of scheduled intervals [s(i),f(i)] for i = 1,2,…,n


Algorithm Analysis

courses/cs211/winter2012/journals/jeanpaul/chapterfour_sectionii.1330289380.txt.gz · Last modified: 2012/02/26 20:49 by mugabej
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0