On Small Deviations Conjecture

• Autorzy: Kubiak, W.
• Języki publikacji: EN

Abstrakty

EN

Brauner and Crama [4] conjectured that the only n-product, n>2, standard instance of the maximum deviation just-in-time sequencing problem with maximum deviation less than 1/2 is made up of the first n nonnegative powers of 2. We prove that this conjecture holds true. We also exploit this result to prove special cases of the well known Fraenkel's conjecture.

Słowa kluczowe

EN

just-in-time sequencing; Fraenkel's conjecture

• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2003
• Tom: Vol. 51, nr 2
• Strony: 189-203
• Opis fizyczny: 7 rys., bibliogr. 13 poz.

Twórcy

autor

Kubiak, W.

• Faculty of Business Administration, Memorial University of Newfoundland St. John's, NF Canada,

Bibliografia

• [1] E. Altman, B. Gaujal, A. Hordijk, Balanced sequences and optimal routing, The Netherlands, Report TW-97-08, (Leiden University 1998).
• [2] M. Balinski, N. Shahidi, A simple approach to the product rate variation problem via axiomatics, Operations Processing Letters, 22 (1998) 129-135,
• [3] J. Bautista, R. Companys, A. Corominas, A note on the relation between the product rate variation (PRV) and the apportionment problem, Journal of Operational Research Society, 47 (1996) 1410-1414.
• [4] N. Brauner, Y. Crama, Facts and questions about the maximum deviation just-in-time scheduling problem, Research Report G.E.M.M.E. No 0104, University of Liège, Liège 2001.
• [5] R. L. Graham, Covering the positive integers by disjoint sets of the form {[nα + β][n = 1,2...}, J. Combin. Th. A, 15 (1973) 354-358.
• [6] M. Y. Kovalyov, W. Kubiak, S. Yeomans, A computational analysis of balanced JIT optimization algorithms, Information Processing and Operational Research, 39 (2001) 299-316.
• [7] W. Kubiak, S. P. Sethi, A note on Level schedules for mixed-model assembly lines in just-in-time production systems, Management Science, 6 (1991) 137-154.
• [8] W. Kubiak, S. P. Sethi, Optimal just-in-time schedules for flexible transfer lines, The International Journal of Flexible Manufacturing Systems, 6 (1994) 137-154.
• [9] J. G. Miltenburg, Level schedules for mixed-model assembly lines in just-in-time production systems, Management Science, 35 (1989) 192-207.
• [10] Y. Monden, Toyota production systems, Industrial Engineering and Management Press, Norcross, GA, 1983.
• [11] G. Steiner, S. Yeomans, Level schedules for mixed-model, just-in-time production processes, Management Science, 39 (1993) 401-418.
• [12] R. Tijdeman, Exact covers of balanced sequences and Fraenkel’s conjecture, in: Algebraic number theory and diophantine analysis, Proc. Intern. Conf. Graz, Austria, Ed. by F. Halter-Koch and R. F. Tichy, Walter de Gruyter, Berlin, (2000) 467-483.
• [13] J. V. Uspensky, On a problem arising out of the theory of a certain game, Amer. Math. Monthly, 34 (1927) 516-521.