Add to ORKGWe 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 P1jFSjCmax . 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-optimizat...