We consider the case of minimizing the makespan when
scheduling tasks with respe ct 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., the treated problem will be abbreviated
by P&;|FS|Cmax. This problem is NP}
hard even for unit task length and forbidden sets tha t
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 3/2 and 4/3, respectively. To
conclude our results, we show that the bound of 3/2
is tight for the case of re-optimizing an optimal
schedule after adding a new forbidden set. Keywords:
scheduling, forbidden sets, approximation, sensitivity
approximation threshold, m machine problem
