Weighted interval scheduling with m-machines

I am looking for some advice and direction on solving the weighted interval scheduling problem with $m$-machines to plan some experimental "wet lab" procedures.

The problem is very similar to the standard weighted interval scheduling problem described but with the important difference that more than 1 'machine' can be used.

The problem has the following specifics:

• There can be a fixed number of machines (e.g. 2 machines)

• The machines can be run in parallel and are identical.

• No machine can be assigned to two overlapping intervals

• The inputs are a list of intervals with start time, stop time and a weight (score). And the number of machines available

• The output is a schedule for each machine consisting of a subset of the intervals, whose weight is maximal.

I can find some great explanations as to how weighted interval scheduling can be solved with 1 machine (python tutorial). And how interval scheduling can be solved on >1 machine when not weighted (interval scheduling with >1 resource)

Approach attempted

As far as I can tell, the Dynamic programming approach solve the weighted interval scheduling problem is widely used.

• For every interval j, the rightmost mutually compatible interval i, where i

• Use dynamic algorithm to schedule weighted intervals

• Trace-back recursively to get the subset of intervals

These steps are explained in detail here and here.

The most simplistic way I could think of would be be to perform an algorithm for 1 machine, like the algorithm described in the python tutorial, then repeat the algorithm with the previously scheduled items removed.

Example data

Data consists of interval id, start time, end time and weight
(1, 0, 3, 3)
(2, 1, 4, 2)
(3, 0, 5, 4)
(4, 3, 6, 1)
(5, 4, 7, 2)
(6, 3, 9, 5)
(7 , 5, 10, 2)
(8 , 8, 10, 1)

The intervals would like this if sorted by descending finishing time:

If $m$ = 2, i.e. I have 2 machines.

If I do the approach described in the python tutorial for machine 1 I get the optimu

If the number of machines is a small constant, then the problem can be solved in polynomial time. In particular, if you have $m$ machines and intervals, the problem can be solved in $O(n^{m+1})$ time using dynamic programming.

If $m$ is part of the input, the problem might be NP-hard. In this case, I suggest you take a look at the general approaches mentioned in Dealing with intractability: NP-complete problems. If you want an exact optimum solution, I suggest trying to formulate this as an integer linear programming (ILP) problem or as a SAT instance. If you want a heuristic, a greedy algorithm might be a reasonable starting point.

For instance, here is how you can formulate this problem as an ILP instance. Introduce zero-or-one variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ means the $i$th interval is assigned to machine $j$. Now add the following constraints / linear inequalities:

-
Each interval is assigned to at most one machine:

$$\sum_j x_{i,j} \le 1.$$

-
No pair of overlapping intervals are assigned to the same machine:

$$x_{i,j} + x_{i',j} \le 1,$$

for all pairs $i,i'$ of overlapping intervals.

Now maximize the objective function $\sum_{i,j} c_i x_{i,j}$, where $c_i$ is the weight of the $i$th interval. Then feed this to an off-the-shelf ILP solver (e.g., lp_solve, CPLEX, etc.).

If you want a greedy approach, here is the obvious approach. Sort the intervals by decreasing "bang-for-the-buck", where the "bang-for-the-buck" of an interval is its weight divided by its length. Consider the intervals in that order. When you consider an interval, if there is a machine that's available for that entire interval, schedule the interval on that machine; otherwise, skip that interval. Proceed until you have considered all the intervals.

StackExchange Computer Science Q#42008, answer score: 3