A framework for the complexity of high-multiplicity scheduling problems

Brauner, Nadia; Crama, Yves; Grigoriev, Alexander; van de Klundert, Joris

doi:10.1007/s10878-005-1414-7

Download

Article (Scientific journals)

A framework for the complexity of high-multiplicity scheduling problems

Brauner, Nadia; Crama, Yves; Grigoriev, Alexander et al.

2005 • In Journal of Combinatorial Optimization, 9 (3), p. 313-323

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/1721

DOI
10.1007/s10878-005-1414-7

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

JOCO Feb26 2005.pdf

Author postprint (124.58 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

computational complexity; design of algorithms; scheduling; high multiplicity

Abstract :

[en] The purpose of this note is to propose a complexity framework for the analysis of high multiplicity scheduling problems. Part of this framework relies on earlier work aiming at the definition of output-sensitive complexity measures for the analysis of algorithms which produce "large" outputs. However, different classes emerge according as we look at schedules as sets of starting times, or as related single-valued mappings.

Disciplines :

Production, distribution & supply chain 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 :

A framework for the complexity of high-multiplicity scheduling problems

Publication date :

May 2005

Journal title :

Journal of Combinatorial Optimization

ISSN :

1382-6905

eISSN :

1573-2886

Publisher :

Springer, Dordrecht, Netherlands

Volume :

Issue :

Pages :

313-323

Peer reviewed :

Peer Reviewed verified by ORBi

Commentary :

The original publication is available at www.springerlink.com

Available on ORBi :

since 02 December 2008

Statistics

Number of views

163 (10 by ULiège)

Number of downloads

336 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

A. Bar-Noy, R. Bhatia, J.S. Naor, and B. Schiber, "Minimizing service and operation costs of periodic scheduling," Mathematics of Operations Research, vol. 27, pp. 518-544, 2002.
N. Brauner and Y. Crama, "The maximum deviation just-in-time scheduling problem," Discrete Applied Mathematics, vol. 134, pp. 25-50, 2004.
N. Brauner, Y. Crama, A. Grigoriev, and J. van de Klundert, "On the complexity of high-multiplicity scheduling problems," University of LiÈge, Liège, Belgium, Working paper GEMME 0110, 2001.
N. Brauner, G. Linke, and W. Kubiak, "Complexity of one-cycle robotic flow-shops," Journal of Scheduling, vol. 6, pp. 355-371, 2003.
J.J. Clifford and M. E. Posner, "High multiplicity in earliness-tardiness scheduling," Operations Research, vol. 48, pp. 788-800, 2000.
J.J. Clifford and M.E. Posner, "Parallel machine scheduling with high multiplicity," Mathematical Programming, vol. 89, pp. 359-383, 2001.
S.S. Cosmadakis and C.H. Papadimitriou, "The traveling salesman problem with many visits to few cities," SIAM Journal on Computing, vol. 13, pp. 99-108, 1984.
M.E. Dyer, "The complexity of vertex enumeration methods," Mathematics of Operations Research, vol. 8, pp. 381-402, 1983.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman: San Francisco, CA, 1979.
F. Granot and J. Skorin-Kapov, "On polynomial solvability of the high multiplicity total weighted tardiness problem," Discrete Applied Mathematics, vol. 41, pp. 139-146, 1993.
A. Grigoriev, "High Multiplicity Scheduling Problems," Maastricht University, The Netherlands. Doctoral thesis, 2003.
D.S. Hochbaum and R. Shamir, "Minimizing the number of tardy job units under release time constraints," Discrete Applied Mathematics, vol. 28, pp. 45-57, 1990.
D.S. Hochbaum and R. Shamir, "Strongly polynomial algorithms for the high multiplicity scheduling problem," Operations Research, vol. 39, pp. 648-653, 1991.
D.S. Hochbaum, R. Shamir, and J.G. Shanthikumar, "A polynomial algorithm for an integer quadratic nonseparable transportation problem," Mathematical Programming, vol. 55. pp. 359-376, 1992.
J. Hurink and S. Knust, "Makespan minimization for flow-shop problems with transportation times and a single robot," Discrete Applied Mathematics, vol. 112, pp. 199-216, 2001.
D.S. Johnson, M. Yannakakis, and C.H. Papadimitriou, "On generating all maximal independent sets," Information Processing Letters, vol. 27, pp. 119-123, 1988.
W. Kubiak and S.P. Sethi, "A note on "Level schedules for mixed-model assembly lines in just-in-time production systems," Management Science, vol. 37, pp. 121-122, 1991.
W. Kubiak and S.P. Sethi, "Optimal just-in-time schedules for flexible transfer lines," International Journal of Flexible Manufacturing Systems, vol. 6. pp. 137-154, 1994.
E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, "Generating all maximal independent sets: NP-hardness and polynomial-time algorithms," SIAM Journal on Computing, vol. 9, pp. 558-565, 1980.
S.T. McCormick, S.R. Smallwood, and F.C.R. Spieksma, "A polynomial algorithm for multiprocessor scheduling with two job lengths," Mathematics of Operations Research, vol. 26, pp. 31-19, 2001.
J. Miltenhurg, "Level schedules for mixed-model assembly lines in just-in-time production systems," Management Science, vol. 35, pp. 192-207, 1989.
A. Munier and K Sourd, "Scheduling chains on a single machine with non-negative time-lags," Mathematical Methods of Operations Research, vol. 57, pp. 111-123, 2003.
C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall: Englewood Cliffs, N.J., 1982.
M. Pinedo, Scheduling: Theory, Algorithms and Systems. Prentice Hall: Hnglewood Cliffs, N.J., 1995.
M.E. Posner, "The complexity of earliness and tardiness scheduling problems under id-encoding," New York University, New York, U.S.A. Working Paper 85-70, 1985.
H.N. Psaraftis, "A dynamic programming approach for sequencing groups of identical jobs," Operations Research. vol. 28, pp. 1347-1359, 1980.
M. Rothkopf, "The travelling salesman problem: On the reduction of certain large problems to smaller ones," Operations Research, vol. 14, pp. 532-533, 1966.
G. Steiner and J.S. Yeomans, "Level schedules for mixed-model, just-in-time processes," Management Science, vol. 39, pp. 728-735, 1993.