Job-shop problems with temporally incompatible jobs represent a typical class of scheduling problems with broad practical relevance, e.g. scheduling of airplanes. However, these problems are in general NP-complete, so that so far solutions have mostly been based on heuristic approaches. In this article we investigate the possibility of exact solutions in special cases where the problem is amenable to a solution via a generalized colouring algorithm for tree-like graphs. We show that the treewidth of the underlying graph-theoretical problem determines the complexity of an exact solution and discuss possible practical applications.
Keywords: Treelike Graph -- Scheduling -- Job Shop Problem -- Rostering