Today we look at the greedy method for job scheduling based on deadlines - with an optimization. The complexity is sort by price which is O(nlogn). We insert each job in current solution. This is the main concern. We maintain J in sorted order of deadline The worst case happens when each new job is feasible and has a smaller deadline than all of J.
To check the feasibility of job i, we begin by inserting in J of size i - 1
This takes i - 1 steps.
Therefore the complexity of insertion is 1 + 2 + ... + n - 1 = O(n ^ 2)
The final complexity is the complexity of sorting as well as insertion and this comes out to be O(n ^ The Bottleneck that we have is inserting each job in J.
This can probably be addressed with a once and for all slot for each new job. In this case, the addition of the job i with deadline di will be at lesser time since we find the rightmost free slot before di. We call this slot alpha-i. We would like to schedule i at slot alpha-i and since its the rightmost we don't need to move it afterwards. That is when a job is scheduled, it is scheduled as late as possible given the current constraints and we don't need to move it afterwards because no job is ever going to move to the right and we don't modify our constraints. The time slot i is actually the range [i - 1, i ]. Let Ni be the first free slot to the left of i. Then ni <= i. If i < j, ni = nj. For both of them the first free slot is on the left. i.e i and j are in the same set if ni = nj . So all { i, i + 1, i + 2, j-1, j } incoming jobs are all in one set. Given a set k in general, f(k) is the value ni. the largest interval free to the left of all of k. Initially no jobs need to be scheduled beyond the largest deadline, Time slots are 1, 2, .. D . D is the maximum deadline of all jobs. All slots are free, so ni = 1 for all i. Sets {1}, {2}, .. , {D} F({j}) = j. Add a job with deadline d, we compute nd. To compute nd, check all k such that d belongs to k,
n(d) = F(k) and this tends to zero when the job is not feasible. Otherwise we can schedule new job at time F(k). Now we have to update F(k). The next free slot must be further to the left. So the new value must be less than F(k) - 1 . We know there is a set contains this value. So we just have to merge the sets.Merge set K with set containing F(k) - 1. So I will have n jobs and n disjoint operations on this data set.
We can explain this with an example. We have six jobs and their deadlines are as shown 2,1,2,6,1,6 K = {0},{1},{2},{3},{4},{5},{6} F(k) for these are correspondingly 0,1,2,3,4,5,6
We create a line of time slots and we add zero to it. So we have 0,1,2,3,4,5, and 6
when you look at the first job, the deadline for this job is 2 so we have it in its own set {2} and F({2}) = 2. Implicitly this means that we are going to assign job 1 to time slot 2. and we have to update the fact that the time slot 2 is no longer available and this we do by merging {2} with the set containing F({2}) - 1 which is equal to 1. and the set corresponding is {1} and we merge {2} with {1} and this will gives us a new picture. Merge {2} with {1} and the number of sets have collapsed by 1 resulting in {0} {1,2}, {3}, {4}, {5}, {6} with F values 0 ,1, 3, 4, 5, 6 . We put 2 at 1 and merged {1,2} so we have to continue that with the set F({1, 2}) - 1 = 0 resulting in a new set {0, 1, 2 } so continuing d[3] = 2 and 2 belongs to {0,1,2} but F of this set is 0 so the job 3 is not feasible. We discard it. d[4] = 6 so we assign it to timeslot 6. This belongs to set {6} and we merge it with the F({6}) - 1 = 5 which is the set {5} resulting in {5,6}
We now have sets {0,1,2}, {3}, {4}, {5,6} with F values 0,3,4,5 respectively. d[5] = 1 and 1 belongs to set {0,1,2}.This is not feasible. So finally we come to the last job d[6] and d[6] = 6 and 6 belongs to {5,6} and F is 5 so we implicitly schedule job 6 at 5 and we merge {5,6} with 4 and there are no more jobs. We have so far picked out the jobs 1,2, 4 and 6 and we have a schedule.
To check the feasibility of job i, we begin by inserting in J of size i - 1
This takes i - 1 steps.
Therefore the complexity of insertion is 1 + 2 + ... + n - 1 = O(n ^ 2)
The final complexity is the complexity of sorting as well as insertion and this comes out to be O(n ^ The Bottleneck that we have is inserting each job in J.
This can probably be addressed with a once and for all slot for each new job. In this case, the addition of the job i with deadline di will be at lesser time since we find the rightmost free slot before di. We call this slot alpha-i. We would like to schedule i at slot alpha-i and since its the rightmost we don't need to move it afterwards. That is when a job is scheduled, it is scheduled as late as possible given the current constraints and we don't need to move it afterwards because no job is ever going to move to the right and we don't modify our constraints. The time slot i is actually the range [i - 1, i ]. Let Ni be the first free slot to the left of i. Then ni <= i. If i < j, ni = nj. For both of them the first free slot is on the left. i.e i and j are in the same set if ni = nj . So all { i, i + 1, i + 2, j-1, j } incoming jobs are all in one set. Given a set k in general, f(k) is the value ni. the largest interval free to the left of all of k. Initially no jobs need to be scheduled beyond the largest deadline, Time slots are 1, 2, .. D . D is the maximum deadline of all jobs. All slots are free, so ni = 1 for all i. Sets {1}, {2}, .. , {D} F({j}) = j. Add a job with deadline d, we compute nd. To compute nd, check all k such that d belongs to k,
n(d) = F(k) and this tends to zero when the job is not feasible. Otherwise we can schedule new job at time F(k). Now we have to update F(k). The next free slot must be further to the left. So the new value must be less than F(k) - 1 . We know there is a set contains this value. So we just have to merge the sets.Merge set K with set containing F(k) - 1. So I will have n jobs and n disjoint operations on this data set.
We can explain this with an example. We have six jobs and their deadlines are as shown 2,1,2,6,1,6 K = {0},{1},{2},{3},{4},{5},{6} F(k) for these are correspondingly 0,1,2,3,4,5,6
We create a line of time slots and we add zero to it. So we have 0,1,2,3,4,5, and 6
when you look at the first job, the deadline for this job is 2 so we have it in its own set {2} and F({2}) = 2. Implicitly this means that we are going to assign job 1 to time slot 2. and we have to update the fact that the time slot 2 is no longer available and this we do by merging {2} with the set containing F({2}) - 1 which is equal to 1. and the set corresponding is {1} and we merge {2} with {1} and this will gives us a new picture. Merge {2} with {1} and the number of sets have collapsed by 1 resulting in {0} {1,2}, {3}, {4}, {5}, {6} with F values 0 ,1, 3, 4, 5, 6 . We put 2 at 1 and merged {1,2} so we have to continue that with the set F({1, 2}) - 1 = 0 resulting in a new set {0, 1, 2 } so continuing d[3] = 2 and 2 belongs to {0,1,2} but F of this set is 0 so the job 3 is not feasible. We discard it. d[4] = 6 so we assign it to timeslot 6. This belongs to set {6} and we merge it with the F({6}) - 1 = 5 which is the set {5} resulting in {5,6}
We now have sets {0,1,2}, {3}, {4}, {5,6} with F values 0,3,4,5 respectively. d[5] = 1 and 1 belongs to set {0,1,2}.This is not feasible. So finally we come to the last job d[6] and d[6] = 6 and 6 belongs to {5,6} and F is 5 so we implicitly schedule job 6 at 5 and we merge {5,6} with 4 and there are no more jobs. We have so far picked out the jobs 1,2, 4 and 6 and we have a schedule.
No comments:
Post a Comment