computational complexity; design of algorithms; scheduling; high multiplicity
Abstract :
[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 :
61
Issue :
1
Pages :
75-91
Peer reviewed :
Peer Reviewed verified by ORBi
Commentary :
The definitive version is available at www.blackwell-synergy.com
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
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.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
