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 < j I is a sorted list of Interval objects (sorted by finish time)
- 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 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