Variant of interval scheduling (multiple machines with given availability)

Question

I am looking for an algorithm to solve the following variant of interval scheduling : schedule some tasks on multiple machines, which are only available during a given interval of time. Two tasks cannot be performed at the same time by the same machine. I am trying to maximize the number of scheduled tasks.

More formally, we are given $m$ intervals $[B_i, E_i]$ (the machines) and $t$ tasks $[b_i, e_i]$. We must output $m$ lists $[i_1, i_2, ..., i_{k_j}]$ such that for each $1 \leq j \leq m$, $B_j \leq b_{i_1} \leq e_{i_1} \leq b_{i_2} \leq ... \leq e_{i_{k_j}} \leq E_j$, all the elements of the lists are distinct and $\sum_{j = 1}^m k_j$ is maximal (ideally t).

I thought about the greedy algorithm consisting on scheduling first the task that finishes the earliest, on the compatible machine whose last task finishes the latest (we consider every machine has at first a task finishing at the beginning of its working interval). However, this idea doesn't work, how we can see considering the instance of the problem where we have two machines, working on the intervals (0, 3) and (1, 4), with the tasks (1, 3) and (2, 4).
This way of selecting the machine on which we schedule the task is however not so stupid, and prevents other problems (the algorithm works if we are allowed to exchange the end of the working interval of the machines).

Is there a fast algorithm to solve this or is it a hard problem ?

Answer 1

Let us call $n$ the number of intervals and $m$ the number of available machines.

There is an algorithm by Brucker and Nordmann running in time essentially $O(n^{m-1})$. Thus for any constant $m$, the problem admits a polynomial time algorithm. The authors claim that the algorithm is practical up to $m=5$ machines.

When $m$ is not constant, the problem appears to be hard, however I do not know whether the version you stated is NP-hard. In this case, Faigle, Kern and Nawijn show that by a simple greedy algorithm you can schedule at least half of the intervals scheduled in an optimal solution. This is the overview of their algorithm, that they call $G$ (the jobs are denoted by $I_1,I_2,\ldots,I_n$, and are considered ordered by their left endpoints):

$G$ places $I_t$ on a free feasible machine if such a machine is available. Otherwise $G$ tries to replace a job $I_v$ by $I_t$ on a feasible machine with the goal to reduce the maximal remaining processing time. If neither action is possible, $G$ discards $I_t$.