0
$\begingroup$

So I am trying to figure out what kind of algorithm I would use if I wanted to implement the ISP with a predefined number of resources. Consider this example interval scheduling problem.

Say there are n requests for a lecture hall and three lecture halls are available to satisfy these requests. Each request has a starting time and an ending time. Create an algorithm to get a maximal scheduling.

I am familiar with the process and I know how the ISP would work if I had only one resource. But how would I apply it in this scenario if I had two, three, or a predefined set of resources.

Any input will be appreciated.

$\endgroup$
  • $\begingroup$ Do you know the complexity of the problem? If it's NP-complete, formulating an IP may be a good and easy way. $\endgroup$ – Raphael Jul 20 '16 at 6:54
3
$\begingroup$

The greedy scheduling with a first fit resource selection is actually not correct. Consider the case where the intervals are:

${ (1, 3) , (2, 5) , (6, 7) , (4, 8) }$,

for simplicity assume we only have 2 resources. The greedy algorithm will assign intervals 1, 2, 3 to resources 1, 2, 1 respectively and will fail to assign a resource for the last interval. Although, a more optimal assignment would have been assigning all 4 of them 1, 2, 2, 1 in the following order.

So another greedy choice has to be made which is the selection of the resource to host the interval. The greedy choice would be selecting the compatible resource with the latest finish time. That way resources which are good (i.e. support more intervals) are kept free.

Intuition to the correctness of the algorithm:

There are 2 claims: 1) Intervals with early finishing time are always better to schedule first.

This is proven by an exchange argument, assume we would leave an interval with early finish time unscheduled to take a later interval, future intervals will definitely have a harder job finding a free room.

2) When an interval is compatible, it is always better to select the worst compatible room.

Since by claim 1, the interval will be taken anyway, the state of the rooms will have a room with $nextFreeTime = endTime_{cur}$ leaving 2 rooms with their previous $nextFreeTime$. Selecting the room with a larger $nextFreeTime$ will leave the better rooms for worse intervals.

Note: The problem can be solved with a less efficient but more obviously correct algorithm using a 3D dynamic programming approach. The state of the dp would indicate the last taken resource in each of the rooms, and the transitions are for each current interval, try selecting all of the compatible rooms updating their states. The intervals are still taken in order of finish time (Claim 1 still holds). The complexity becomes $O(n^3)$, however this is not scalable for k resources unlike the greedy algorithm.

$\endgroup$
  • $\begingroup$ Nice explanation. I'd assumed DP would be necessary for this! $\endgroup$ – j_random_hacker Jul 22 '16 at 13:54
0
$\begingroup$

Scheduling could still be done greedily.

Psuedocode:

sort requests by finishing time
list of schedules = [[]]
for each request
    for each schedule in list of schedules
        if request can be appended to schedule
            append and break
    if not appended
        create new schedule
        add request to schedule
        append schedule to list
sort list of schedules by number of requests in each

This should work for any number of requests and 'resources'.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.