Veröffentlichung

Titel:
Efficient and Exact Solutions for Job Shop Scheduling Problems via a Generalized Colouring Algorithm for Tree-Like Graphs
AutorInnen:
Soller, H.
Kulmann, F.
Rödder, W.
Kategorie:
Zeitschriftenaufsätze
 
International Journal of Operations and Quantitative Management - IJOQM, 22-3 (2016) 253-272.
Abstract:

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

10.05.2024