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