The maximum deviation just-in-time scheduling problem

[en] This note revisits the maximum deviation just-in-time (MDJIT) scheduling problem previously investigated by Steiner and Yeomans. Its main result is a set of algebraic necessary and sufficient conditions for the existence of a MDJIT schedule with a given objective function value. These conditions are used to provide a finer analysis of the complexity of the MDJIT problem. The note also investigates various special cases of the MDJIT problem and suggests several questions for further investigation. (C) 2003 Elsevier B.V. All rights reserved.

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

Language :

English

Title :

The maximum deviation just-in-time scheduling problem

Publication date :

05 January 2004

Journal title :

Discrete Applied Mathematics

ISSN :

0166-218X

eISSN :

1872-6771

Publisher :

Elsevier Science Bv, Amsterdam, Netherlands

Volume :

134

Issue :

1-3

Pages :

25-50

Peer reviewed :

Peer Reviewed verified by ORBi

Commentary :

Available online at www.sciencedirect.com

Available on ORBi :

since 02 December 2008

Statistics

Number of views

241 (9 by ULiège)

Number of downloads

298 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

E. Altman, B. Gaujal, A. Hordijk, Balanced sequences and optimal routing, J. ACM 47 (2000) 752-775.
Balinski M., Shahidi N. A simple approach to the product rate variation problem via axiomatics. Oper. Res. Lett. 22:1998;129-135.
Balinski M., Young H.P. The quota method of apportionment. Amer. Math. Monthly. 82:1975;701-730.
Bautista J., Companys R., Corominas A. A note on the relation between the product rate variation (PRV) problem and the apportionment problem. J. Oper. Res. Soc. 47:1996;1410-1414.
Bondy J.A., Murty U.S.R. Graph Theory with Applications. 1976;North-Holland, New York.
N. Brauner, Y. Crama, J. van de Klundert, A. Grigoriev, A note on the complexity of high-multiplicity optimization problems, Working Paper GEMME, University of Liège, Liège, 2001.
N. Brauner, V. Jost, W. Kubiak, On symmetric Fraenkel's and small deviations conjecture, Working paper, Les cahiers du laboratoire Leibniz, No 54, Grenoble, France, 2002.
Gabow H., Tarjan R.E. A linear-time algorithm for a special case of disjoint set union. J. Comput. System Sci. 30:1985;209-221.
Gallo G. An. O(n log n) algorithm for the convex bipartite matching problem Oper. Res. Lett. 3:1984;31-34.
Glover F. Maximum matching in a convex bipartite graph. Naval Res. Logistics Quart. 4:1967;313-316.
Grötschel M., Lovász L., Schrijver A. Geometric Algorithms and Combinatorial Optimization. 1993;Springer, Berlin.
Hochbaum D.S., Shamir R. Strongly polynomial algorithms for the high multiplicity scheduling problem. Oper. Res. 39:1991;648-653.
Inman R.R., Bulfin R.L. Sequencing JIT mixed-model assembly lines. Manage. Sci. 37:1991;901-904.
Kovalyov M.Y., Kubiak W., Yeomans J.S. A computational study of balanced JIT optimization algorithms. INFOR. 39:2001;299-316.
Kubiak W. Minimizing variation of production rates in just-in-time systems. a survey European J. Oper. Res. 66:1993;259-271.
W. Kubiak, Cyclic just-in-time sequences are optimal, Preprint, Memorial University of Newfoundland, St. John's, Canada, 2000.
Kubiak W., Sethi S.P. A note on level schedules for mixed-model assembly lines in just-in-time production systems. Manage. Sci. 37:1991;121-122.
Kubiak W., Sethi S.P. Optimal just-in-time schedules for flexible transfer lines. Internat. J. Flexible Manuf. Systems. 6:1994;137-154.
Kubiak W., Steiner G., Yeomans J.S. Optimal level schedules for mixed-model, multi level just-in-time assembly systems. Ann. Oper. Res. 69:1997;241-259.
Lenstra H.W. Jr. Integer programming with a fixed number of variables. Math. Oper. Res. 8:1983;538-548.
Lipski W. Jr., Preparata F.P. Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Inform. 15:1981;329-346.
Miltenburg J. Level schedules for mixed-model assembly lines in just-in-time production systems. Manage. Sci. 35:1989;192-207.
Monden Y. Toyota Production System. 1983;Institute of Industrial Engineers, Norcross, GA.
Psaraftis H.N. A dynamic programming approach for sequencing groups of identical jobs. Oper. Res. 28:1980;347-359.
Steiner G., Yeomans J.S. Level schedules for mixed-model, Just-in-time processes. Manage. Sci. 39:1993;728-735.
Steiner G., Yeomans J.S. Optimal level schedules in mixed-model, multi level JIT assembly systems with pegging. European J. Oper. Res. 95:1996;38-52.
Tijdeman R. On complementary triples of Sturmian bisequences. Indagationes Math. 7:1996;419-424.
Tijdeman R. Exact covers of balanced sequences and Fraenkel's conjecture. Halter-Koch F., Tichy R.F. Algebraic Number Theory and Diophantine Analysis. 2000;467-483 Walter de Gruyter, Berlin.
Tijdeman R. Fraenkel's conjecture for six sequences. Discrete Math. 222:2000;223-234.