Interval Scheduling Problem with more than One Resource

Question

Consider the interval scheduling problem, see also here.

In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest finish time, choose the next compatible one, and so on.

Now, let us say we have two resources instead of one. How do I schedule my jobs now? As my idea goes, again you start by sorting the requests in order of finish time. My problem is, how do I proceed after that? Do I choose the resources in sequential or in an alternate fashion?

If I go for sequential manner, I schedule all the possible jobs in the first resource and then do the same for second resource with the jobs yet to be scheduled.

If I go for alternate fashion, I choose the first possible job in the first resource, then second possible job in the second resource and so on.

In each case we will have take in to account the chosen jobs being compatible, needless to say.

I can not decide which of these is going to be optimal.

Any input will be appreciated.

Answer 1

Plot the intervals for all the jobs (sorted by earliest finishing time) on the x axis. Start with y = 1.

If two jobs overlap, then plot the intervals of the later job on a higher y -- i.e., above the already plotted job interval. Stop when all jobs have had their intervals plotted. Sort the levels such that the bottom most level has the maximum number of jobs and the top most level has the least number of jobs.

Now, start at the lowest bottom most level of your plot (i.e., y = 1). Allocate all the jobs at this level to machine 1. Then move to y = 2 and allocate all these jobs to machine 2. Repeat till all available machines have jobs.

The number of jobs that can be allocated to k machines is optimal (simple greedy exchange argument).