Scheduling with forbidden sets

AbstractWe consider the case of minimizing the makespan when scheduling tasks with respect to a class of so-called forbidden sets, i.e. sets of tasks that are not allowed to be scheduled in parallel. Following the notion of Graham et al. [7], the treated problem will be abbreviated by P∞|FS|Cmax. This problem is NP hard even for unit task length and forbidden sets that contains exactly two elements. Moreover, we show that the existence of a polynomial-time approximation algorithm with a worst-case ratio strictly less than 2 implies P = NP. We point out that the corresponding re-optimization problem (after changing the instance slightly) is NP hard as well, even if only one forbidden set is added or removed. Furthermore, the latter re-optimization problems have approximation thresholds of 32 and 43, respectively. To conclude our results, we show that the bound of 32 is tight for the case of re-optimizing an optimal schedule after adding a new forbidden set