Weighted interval scheduling with m-machines

Question

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.

1. For every interval j, the rightmost mutually compatible interval i, where i < j I is a sorted list of Interval objects (sorted by finish time)
2. Use dynamic algorithm to schedule weighted intervals
3. 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 optimum schedule of items: 3 (weight 4) and 7 (weight 2) = total weight 6. (which seems strange as it is not the maximum weight that can be obtained)

For machine 2, I then repeat this with the items 3 and 7 removed. The resulting schedule would then be: 1 (weight 3) and 6 (weight 5) = total weight 8.

See attached for Python code used (modified slightly from the python tutorial).

import collections
import bisect
import time
from datetime import datetime

class Interval(object):
    '''Date weighted interval'''

    def __init__(self, title, start, finish, weight):
        self.title = title
        self.start = start
        self.finish = finish
        self.weight = weight

    def __repr__(self):
        return str((self.title, self.start, self.finish, self.weight))


def compute_previous_intervals(I):
    '''For every interval j, compute the rightmost mutually compatible  interval i, where i < j
       I is a sorted list of Interval objects (sorted by finish time)
    '''
    # extract start and finish times
    start = [i.start for i in I]
    finish = [i.finish for i in I]

    p = []
    for j in xrange(len(I)):
        i = bisect.bisect_right(finish, start[j]) - 1  # rightmost interval f_i <= s_j
        p.append(i)

    return p

def schedule_weighted_intervals(I):
    '''Use dynamic algorithm to schedule weighted intervals
       sorting is O(n log n),
       finding p[1..n] is O(n log n),
       finding OPT[1..n] is O(n),
       selecting is O(n)
       whole operation is dominated by O(n log n)
    '''

    I.sort(lambda x, y: x.finish - y.finish)  # f_1 <= f_2 <= .. <= f_n

    print I
    p = compute_previous_intervals(I)

    print p

    # compute OPTs iteratively in O(n), here we use DP
    OPT = collections.defaultdict(int)
    OPT[-1] = 0
    OPT[0] = 0
    for j in xrange(1, len(I)):
        #print j
        OPT[j] = max(I[j].weight + OPT[p[j]], OPT[j - 1])
        #print OPT[j]
    print OPT
    # given OPT and p, find actual solution [intervals in O(n)
    O = []


    def compute_solution(j):
        if j >= 0:  # will halt on OPT[-1]
            print "start", j,  I[j]
            if I[j].weight + OPT[p[j]] > OPT[j - 1]:
                #print I[j].weight + OPT[p[j]], "greater than",  OPT[j - 1]
                O.append(I[j])
                #print I[j]
                compute_solution(p[j])
            else:
                #print I[j].weight + OPT[p[j]], "not greater than",  OPT[j - 1]
                compute_solution(j - 1)

    compute_solution(len(I)-1)

    # resort, as our O is in reverse order (OPTIONAL)
    O.sort(lambda x, y: x.finish - y.finish)

    return O

if __name__ == '__main__':
    I = []
    I.append(Interval(1 , 0, 3, 3))
    I.append(Interval(2 , 1, 4, 2))
    I.append(Interval(3 , 0, 5, 4))
    I.append(Interval(4 , 3, 6, 1))
    I.append(Interval(5 , 4, 7, 2))
    I.append(Interval(6 , 3, 9, 5))
    I.append(Interval(7 , 5, 10, 2))
    I.append(Interval(8 , 8, 10, 1))

    print I

    O = schedule_weighted_intervals(I)
    print "subset = ", O

Answer 1

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.