Wednesday, November 28, 2012

Interval Scheduling

Interval Scheduling
                                   
                                                                               By: Abhishek Arora


Disclaimer:

         All characters appearing in this article are fictitious. Any resemblance to real persons, living or dead, is purely coincidental.

Abstract:
 
A long time ago, there was a saint born on this earth. Lord Shiva gifted him with enormous powers in return of his prayers.

          One day on seeing the grieving family members of a dead person, the saint got very angry with the death. He couldn’t able to bear the pain and sorrow caused by death. He made a protective layer on the earth by his powers so that no death reapers can now enter the earth and take a life.

This caused a great imbalance in the functioning of earth and all the gods became very tensed especially Yamraj because it was their duty to make proper balance of life and death on this earth. All the gods gathered together and request the saint to remove that protected layer but he didn't agree with them. Though he allowed Yamraj to send his one death reaper on the night of Full moon to take life and carry souls to afterlife one by one.


It was a very short period of time to carry all the souls to afterlife. Yamraj was in the state of dilemma to how to properly schedule his time and carry maximum souls to afterlife because he can only send one death reaper to earth and the death time of every earthling is written in his life book. Time to take a soul depends upon how far is the death place of the person from the place of Yamraj. Reapers carry soul to Yamraj one by one.

He didn't have a solution for this question. Goddess Saraswati is the goddess of knowledge. Yamraj was sure that goddess Saraswati must have a solution for his problem. Yamraj decided to take help from Goddess Saraswati.


Goddess Saraswati being the goddess of knowledge knew how to handle such type of problem. She picked a stone and wrote the procedure on it. She told the Yamraj that this procedure would be known as Interval Scheduling in the future.



                                          Interval Scheduling
 
Given a set of tasks with their arrival time and running time we need to schedule them within a given time period such that we are able to schedule maximum number of tasks.

Let p1,p2,p3....pI be the tasks to be scheduled.
Let s1,s2,s3......sI be the starting time of tasks.
Let r1,r2,r3.......rI be the time required by each task respectively.


Algorithm:

 
Implementation:

• Sorting intervals according to the right-most ends (their finishing time)
• For every consecutive task:
  • If the left-most end(starting time) is after the right-most end of the last
selected interval then we select this interval
  • Otherwise we skip it and go to the next interval

This approach is a Greedy approach.
Consider the following set of activities represented graphically in non-decreasing order of finishing times




Using the greedy strategy an optimal solution is {1, 4, 8, 11}.









Scenario of Yamraj:

But Yamraj wasn't able to understand a single word written above.
Then Goddess Saraswati smiled and said to Yamraj:
  • Taking a soul to afterlife is a task for you.
  • Death time of a person is the starting time of your task.
  • Time to reach to the dying person and taking his soul to your place is the time required to complete that task.
This approach worked for Yamraj and he implemented this approach in bringing souls to afterlife on every Full moon night for many years. 

But as the years passed Yamraj noticed that sin and violence had increased a lot in the earth. But he couldn't able to do anything. He just have one night to cause deaths in the earth and it also didn't assure that Yamraj is picking bad guys.

It made Yamraj to worry. He wanted to do something about the increasing sin and “adharm” on earth. But he didn't know how to pick maximum bad guys in his given time slot. So he again decided to take help from Goddess Saraswati. He went to Goddess Saraswati and asked for her help.

Goddess Saraswati smiled and asked Yamraj, “how will you decide who is bad and who is good??”.

Yamraj answered, “Devi we keep a count of all the deeds of humans. If a human do sins throughout his life he gets punished in the afterlife.”

Goddess Saraswati smiled and said to Yamraj, “ I can help you with this but it doesn't guarantee you that you will able to bring maximum souls to afterlife”

           It put Yamraj in a thinking state. He didn't know what to do now. He want to take as many as possible lives on every full moon night but he also want to do something about the increasing sins and adharma on earth. So Yamraj said, “I want you to tell me the way to pick as many as possible bad guys.”
 
Goddess Saraswati again picked a stone and wrote the procedure on it. She told the Yamraj that this procedure would be known as Dynamic Weighted Interval Scheduling in the future.




Weighted Interval Scheduling

Suppose we are given n jobs. Each job i has a start time si , a finish time fi , and a weight wi .

We would like to find a set M of optimal jobs whose total weight is maximized.

Let us assume that our n jobs are sorted by non-decreasing finish times fi .

M(i)= The maximum weight of any set of compatible jobs, all of which finish by fi .

p(j)= job with the largest index less than j which is compatible with job j. In other words, the largest k such that fk ≤ sj . If no such job exists define p(j) = 0.

Then
M(i) = max{M(i − 1), wi + M(p(i))}.


Consider the optimal solution for M(i). Either job i is used or it is not.
  • If it is not, then we have a maximum weight set of compatible jobs from among jobs 1 through i − 1. By definition, this is M(i − 1).
  • Alternatively, if i is used for M(i). Since jobs p(i) + 1 through i − 1 all conflict with job i, this means that the remaining jobs selected for M(i) are drawn from 1 through p(i). Removing i from the optimal solution for M(i) yields a compatible solution on jobs 1 . . . p(i).
Therefore M(i) = wi + M(p(i)).

Finally, since M(i) is a maximization, the larger of these two terms is correct.
As base cases, we define M(0) = 0 and M(1) = w1.



The algorithm works as follows:

  • sort jobs by increasing finish times.
  • compute function p(i) for i from 1 to n (this can clearly be done in O(n2) time. If we want to do better, we can either binary search for each i, or all p(i) values can be computed in a single linear pass if we have already created a second list of jobs sorted by increasing start times).

set M(0) = 0 and M(1) = w1
loop over i from 2 to n
            set M(i) = max{M(i − 1), wi + M(p(i))}
endloop

Sorting takes O(n log n) time. The computation of p(i) takes another O(n log n) time and the main loop are both linear, and therefore the total running time is O(n log n).


Note that we computed the value of an optimal schedule, but not the schedule itself. To actually compute the actual schedule, we have a few options. One is to use the computed values M(i) to reverse engineer an optinal set A of jobs to select.


Alternatively, we can change the algorithms so we build lists as we go:
  • sort jobs by increasing finish times.
  • compute function p(i) for i from 1 to n
set M(0) = 0 and M(1) = w1
set A(0) = 0 and A(1) = {1}
loop over i from 2 to n
            if M(i − 1) > wi + M(p(i))
                         set A(i) = A(i − 1) and M(i) = M(i − 1)
             else M(i − 1) ≤ wi + M(p(i))
                         set A(i) = {i} A(p(i)) and M(i) = wi + M(p(i))
             endif
endloop



Again Yamraj wasn't able to understand how to implement it. Then goddess Saraswati told him:
  • Taking a soul to afterlife is a job for you
  • Death time of a person is the starting time of your task.
  • Time to reach to the dying person and taking his soul to your place is the time required to complete that job.
  • All the bad deeds done by that human is the weight of the job.

Yamraj was finally happy to have a solution for this. He continued to use this approach to take life of bad guys until the death protecting layer of earth was removed by the saint.

In the final moments of the saint’s life when he was old and in the state of misery, and no one was there to support him. He was waiting eagerly for his death but death wasn’t able to come to him due to his protected layer. He then realized that it is very important to leave this life and move to afterlife. He removed that protected layer and apologize to all the gods. It was a sigh of relief for all the gods specially Yamraj.


References:

faculty.cse.tamu.edu/nikolova/Teaching/.../lec3.pdf - United States
lonati.di.unimi.it/algo/0910/lab/kowalski6.pdf



No comments:

Post a Comment