Multiplicity and complexity issues in contemporary production scheduling |
| |
Authors: | N Brauner Y Crama † A Grigoriev ‡ J van de Klundert § |
| |
Institution: | Laboratoire Leibniz-IMAG, 46 avenue Félix Viallet, 38031 Grenoble cedex, France; HEC Management School, University of Liège, Boulevard du Rectorat 7 (B31), 4000 Liège, Belgium; Department of Quantitative Economics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands; Department of Mathematics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands |
| |
Abstract: | High multiplicity scheduling problems arise naturally in contemporary production settings where manufacturers combine economies of scale with high product variety. Despite their frequent occurrence in practice, the complexity of high multiplicity problems – as opposed to classical, single multiplicity problems – is in many cases not well understood. In this paper, we discuss various concepts and results that enable a better understanding of the nature and complexity of high multiplicity scheduling problems. The paper extends the framework presented in Brauner et al. Journal of Combinatorial Optimization (2005 ) Vol. 9, pp. 313–323] for single machine, non-preemptive high multiplicity scheduling problems, to more general classes of problems. |
| |
Keywords: | computational complexity design of algorithms scheduling high multiplicity |
|
|