- Efficient and Exact Solutions for Job Shop Scheduling Problems via a Generalized Colouring Algorithm for Tree-Like Graphs
- International Journal of Operations and Quantitative Management - IJOQM, 22-3 (2016) 253-272.
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
- SKR 2016 [bib]