Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionii [2012/02/26 19:33] – [The Problem] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionii [2012/02/26 22:13] (current) – [Designing the algorithm] mugabej
@@ Line 7: / Line 7: @@
   * 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.