====== 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 <sub>i</sub>// and requires a contiguous interval of time //t <sub>i</sub>//
  * Each request is flexible: It can be scheduled at any time before its deadline.
  * Each accepted request is assigned an interval of length //t <sub>i</sub>// , 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 <sub>i</sub>// = [ S(//i//), f//i//)], where f(//i//) = S(//i//)+ t(//i//)
  * The algorithm must always determine the start time
  * Lateness, //l <sub>i</sub>// = f(//i//) - d(//i//))
  * //l <sub>i</sub>// = 0 if the request //i// is not late
  * A request is late if it misses the deadline -->f(//i//)> d <sub>i</sub>\\
\\
--> Goal of the algorithm: Minimize the //maximum lateness, L = max<sub>i</sub> l <sub>i</sub>// 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 <sub>i</sub> and schedule them in this order.
  * Thus jobs are scheduled in the order d<sub>1</sub>,d<sub>2</sub>,...,d<sub>n</sub>\\
  * 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 d<sub>1</sub> ≤ d<sub>2</sub> ≤ d<sub>3</sub>,...,d <sub>n-1</sub> ≤ d<sub>n</sub>
>>>>>>>>>>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<sub>i</sub>
>>>>>>>>>>>>>>>>>>>>Let //f// = //f// + t<sub>i</sub>
>>>>>>>>>>End
>>>>>>>>>>Return the set of scheduled intervals [s(i),//f//(i)] for i = 1,2,...,n
\\
=== Algorithm Analysis ===

  * //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<sub>i</sub> is scheduled before another job //j// with deadline d<sub>j</sub>
  * 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.