A framework for the complexity of high-multiplicity scheduling problems

[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

168 (10 by ULiège)

Number of downloads

341 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

publications

supporting

mentioning

contrasting

Smart Citations

Citing PublicationsSupportingMentioningContrasting

View Citations

See how this article has been cited at scite.ai

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

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.

Name	Provider / Domaine	Expiration	Description
JSESSIONID	Oracle Corporation www.uliege.be	Session	General purpose platform session cookie, used by sites written in JSP. Usually used to maintain an anonymous user session by the server.
CookieScriptConsent	CookieScript .uliege.be	1 year	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.

Name	Provider / Domaine	Expiration	Description
_pk_id	InnoCraft Ltd .uliege.be	1 year	Used to store a few details about the user such as the unique visitor ID
_pk_ses	InnoCraft Ltd .uliege.be	30 minutes	Short lived cookies used to temporarily store data for the visit
_pk_ref	InnoCraft Ltd .uliege.be	6 months	Used to store the attribution information, the referrer initially used to visit the website