Scheduling Tutors – Greedy Algorithms – 1
February 16, 2011 Leave a comment
Question.We are a tutor-scheduling organization. We have at our disposal an infinite number of tutors using whom we service the tutoring requests that come our way.
Consider any particular day. We get a certain number of tutoring requests. Each request has a specified starting time, and the duration of the tutoring session is exactly 30 minutes. Each tutor can work for any continuous period of 2 hours in a day. (The tutor need not actually be tutoring for the whole of the 2 hours; it is just that he/she will certainly not tutor outside of that 2 hour period.) We are the ones who decide the starting time of the 2 hour working period for each tutor.
We also need to remember that a tutor cannot service more than one request simultaneously.
Our aim is to service the tutoring requests using a minimum number of tutors. How can we achieve that?
We can tackle this problem greedily.
We order the requests in non-descending order on the basis of their starting times. Take the first request. Schedule a tutor to start his/her 2 hour period at exactly the starting time of the 1st request. Now, look at the 2nd request. Ask yourself the following question: Can the 1st tutor (i.e. the one who has already been scheduled to work) also service this request? If yes, let him/her do so. If not, schedule a 2nd tutor to start his/her 2 hour period at exactly the starting time of this new request. Continue in the same manner for the succeeding requests. i.e. Do the following: For each new request, check if that request can be serviced by any of the tutors already scheduled to work. If yes, schedule the tutor who has the shortest time remaining in his/her 2 hr period, to service this request. If not, schedule a new tutor to start his/her 2 hour period at exactly the starting time of this new request.
In pseudo code form, we would have:
Sort the requests in non-decreasing order of starting times.
count = 0; // this is the # of tutors assigned thus far.
flag = UNSERVICED. // an indicator for whether a particular request has been serviced or //not.
While (one or more requests remain to be serviced)
Remove the 1st request from our sorted list.
For ( each of the tutors scheduled thus far )
//Note: we iterate through the already assigned tutors in the order in which they were
// assigned (so as to be able to schedule the tutor with the least remaining time in
// his/her 2 hr period.
If ( that tutor can service this request )
Schedule him/her to service this request.
Come out of the For loop.
Set: flag = SERVICED.
If (flag == UNSERVICED)
// means that no already scheduled tutor was able to service the new request.
// We need a new tutor.
Assign a new tutor to start his/ her 2 hr period at the starting time of the new request.
Set: flag = UNSERVICED.
count ++ ;
End of While loop.
Analysis of running time:
– Say there are n requests. Sorting them will take O(n log n) time.
– In the worst case, we might need to schedule n tutors to service n requests.In such a scenario, the time required for assigning tutors will be (this is because of the fact that before we assign a new tutor we check with each of the already assigned tutors as to whether they can service the new request).
– Hence, the algorithm will run in time.
Intuitive proof of correctness of the algorithm:
– Consider the 1st request (in sorted order). Obviously, since no tutors have been assigned thus far, we need to schedule a new tutor for this request. Now, consider the choice we have wrt when to schedule this new tutor. Certainly, we cannot schedule him/her to start his/her 2 hr period after the starting time of the 1st request. If we schedule him/her to start working before the starting time of the 1st request, the time that elapses between the moment the tutor’s 2 hr period starts and the starting time of the 1st request would be effectively wasted. Hence, the best thing would be to schedule the 1st tutor to start his/her 2 hr period at exactly the starting time of the 1st request.
– Similarly, one can argue that for each newly assigned tutor, the algorithm chooses exactly the right time for him/her to start their working period.
– Also, we observe that the algorithm does not assign any new tutors unless there is a need to do so.
– And finally, the algorithm always schedules a tutor with the least remaining time in their schedule to service a new request (when selecting among already assigned tutors). This results in maximum number of requests being serviced by already assigned tutors without having the need to assign a new one.