Multiplicity and complexity issues in contemporary production scheduling

[en] 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.

Disciplines :

Quantitative methods in economics & management

Author, co-author :

Brauner, Nadia

Crama, Yves ; Université de Liège - ULiège > HEC - École de gestion de l'ULiège > Recherche opérationnelle et gestion de la production

Grigoriev, Alexander

van de Klundert, Joris

Language :

English

Title :

Multiplicity and complexity issues in contemporary production scheduling

Publication date :

February 2007

Journal title :

Statistica Neerlandica

ISSN :

0039-0402

Publisher :

Blackwell Publishing, Oxford, United Kingdom

Volume :

Issue :

Pages :

75-91

Peer reviewed :

Peer Reviewed verified by ORBi

Commentary :

The definitive version is available at www.blackwell-synergy.com

Available on ORBi :

since 01 December 2008

Statistics

Number of views

133 (5 by ULiège)

Number of downloads

254 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

AGNETIS, A. (1997), No-wait flowshop scheduling with large lot size, Annals of Operations Research 70, 415-438.
BAR-NOY, A., R. BHATIA, J. S. NAOR and B. SCHIBER (2002), Minimizing service and operation costs of periodic scheduling, Mathematics of Operations Research 27, 518-544.
BRAUNER, N. and Y. CRAMA (2004), The maximum deviation just-in-time scheduling problem, Discrete Applied Mathematics 134, 25-50.
BRAUNER, N., G. FINKE and W. KUBIAK (2003), Complexity of one-cycle robotic flow-shops, Journal of Scheduling 6, 355-371.
BRAUNER, N., Y. CRAMA, A. GRIGORIEV and J. VAN DE KLUNDERT (2005), A framework for the complexity of high-multiplicity scheduling problems, Journal of Combinatorial Optimization 9, 313-323.
CLIFFORD, J. J. and M. E. POSNER (2000), High multiplicity in earliness-tardiness scheduling, Operations Research 48, 788-800.
CLIFFORD, J. J. and M. E. POSNER (2001), Parallel machine scheduling with high multiplicity, Mathematical Programming 89, 359-383.
DYER, M. E. (1983), The complexity of vertex enumeration methods, Mathematics of Operations Research 8, 381-402.
GAREY, M. R. and D. S. JOHNSON (1979), Computers and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, CA.
GAREY, M. R., D. S. JOHNSON and R. SETHI (1976), The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research 1, 117-129.
GILMORE, P. C. and R. E. GOMORY (1964), Sequencing a one-state variable machine: a solvable case of the traveling salesman problem, Journal of Operations Research Society of America 12, 655-679.
GRANOT, F. and J. SKORIN-KAPOV (1993), On polynomial solvability of the high multiplicity total weighted tardiness problem, Discrete Applied Mathematics 41, 139-146.
GRIGORIEV, A. (2003), High multiplicity scheduling problems, Doctoral thesis, Maastricht University, Maastricht.
GRIGORIEV, A. and J. VAN DE KLUNDERT (2006), On the high multiplicity traveling salesman problem, Discrete Optimization 3, 50-62.
HOCHBAUM, D. S. and R. SHAMIR (1990), Minimizing the number of tardy job units under release time constraints, Discrete Applied Mathematics 28, 45-57.
HOCHBAUM, D. S. and R. SHAMIR (1991), Strongly polynomial algorithms for the high multiplicity scheduling problem, Operations Research 39, 648-653.
HOCHBAUM, D. S., R. SHAMIR and J. G. SHANTHIKUMAR (1992), A polynomial algorithm for an integer quadratic nonseparable transportation problem. Mathematical Programming 55, 359-376.
HOFFMAN, A. J. (1963), On simple linear programming problems, in Proceedings of the Symposium on Pure Mathematics 7, AMS, Providence, 317-327.
HURINK, J. and S. KNUST (2001), Makespan minimization for flow-shop problems with transportation times and a single robot, Discrete Applied Mathematics 112, 199-216.
JOHNSON, D. S., M. YANNAKAKIS and C. H. PAPADIMITRIOU (1988), On generating all maximal independent sets, Information Processing Letters 27, 119-123.
KUBIAK, W. and S. P. SETHI (1994), Optimal just-in-time schedules for flexible transfer lines, International Journal of Flexible Manufacturing Systems 6, 137-154.
LAWLER, E. L., J. K. LENSTRA and A. H. G. RINNOOY KAN (1980), Generating all maximal independent sets: NP-hardness and polynomial-time algorithms, SIAM Journal on Computing 9, 558-565.
MCCORMICK, S. T., S. R. SMALLWOOD and F. C. R. SPIEKSMA (2001), A polynomial algorithm for multiprocessor scheduling with two job lengths, Mathematics of Operations Research 26, 31-49.
MCNAUGHTON, R. (1959), Scheduling with deadlines and loss functions, Management Science 6, 1-12.
PAPADIMITRIOU, C. H. and K. STEIGLITZ (1982), Combinatorial optimization: algorithms and complexity, Prentice Hall: Englewood Cliffs, New Jersey.
PARK, J. K. (1991), A special case of the n-vertex traveling salesman problem that can be solved in O(n) time, Information Processing Letters 40, 247-254.
PINEDO, M. (1995), Scheduling: Theory, algorithms and systems, Prentice Hall, Englewood Cliffs, New Jersey.
POSNER, M. E. (1985), The complexity of earliness and tardiness scheduling problems under id-encoding, Working Paper 85-70, New York University, New York.
ROTHKOPF, M. (1966), The travelling salesman problem: on the reduction of certain large problems to smaller ones, Operations Research 14, 532-533.
STEINER, G. and J. S. YEOMANS (1993), Level schedules for mixed-model, just-in-time processes, Management Science 39, 728-735.
T'KINDT, V., K. BOUIBEDE-HOCINE and C. ESSWEIN (2005), Counting and enumeration complexity with application to multicriteria scheduling. 4OR 3, 1-21.