Abstract
Solving the level (or balanced) schedule problem is the most important scheduling goal for just-in-time production assembly systems. No previous methods have been presented for determining optimal balanced schedules in multi-level facilities. In this paper, it is shown that the multi-level, min-max problem is NP-hard in the strong sense. A dynamic programming algorithm (DP) is developed for both the min-max and min-sum problems which, for the first time, permits optimal schedules to be determined for large, multi-level problems. The time and space requirements of the DP are analyzed and several techniques for reducing the DP's computational requirements are described. A filtering scheme is proposed to eliminate dominated solutions from a problem's potentially vast state space. Extensive computational testing of the min-max algorithm is reported and the conclusions from this testing are presented.
Similar content being viewed by others
References
M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
T. Goldstein and J. Miltenburg, The effects of pegging in the scheduling of just-in-time production systems, Working Paper No. 294, Faculty of Business, McMaster University, 1988.
H. Groeflin, H. Luss, M. Rosenwein and E. Wahls, Final assembly sequencing for just-in-time manufacturing, International Journal of Production Research 27(1989)199–213.
R. Hall, Zero Inventories, Dow Jones-Irwin, Homewood, IL, 1983.
J. Hooker, Needed: An empirical science of algorithms, Operations Research 42(1994)201–212.
R. Inman and R. Bulfin, Sequencing JIT mixed-model assembly lines, Management Science 37 (1991)901–904.
W.J. Kennedy and J.E. Gentle, Statistical Computing, Marcel Dekker, New York, 1980.
W. Kubiak, Minimizing variation of production rates in just-in-time systems: A Survey, European Journal of Operational Research 66(1993)259–271.
W. Kubiak and S. Sethi, A note on “Level schedules for mixed-model assembly lines in just-in-time production systems”, Management Science 37(1991)121–122.
W. Kubiak and S. Sethi, Optimal level schedules for flexible assembly lines in JIT production systems, International Journal of Flexible Manufacturing Systems 6(1994)137–154.
J. Miltenburg, Level schedules for mixed-model assembly lines in just-in-time production systems, Management Science 32(1989)192–207.
J. Miltenburg and T. Goldstein, Developing production schedules which balance part usage and smooth production loads in just-in-time production systems, Naval Research Logistics 38(1991) 893–910.
J. Miltenburg and G. Sinnamon, Scheduling mixed-model, multilevel assembly lines in just-in-time production systems, International Journal of Production Research 27(1989)1487–1509.
J. Miltenburg, G. Steiner and S. Yeomans, A dynamic programming algorithm for scheduling mixed-model, just-in-time production systems, Mathematical and Computer Modelling 13(1990)57–66.
Y. Monden, Toyota Production Systems, Industrial Engineering and Management Press, Norcross, GA, 1983.
K. Okamura and H. Yamashita, A heuristic algorithm for the assembly line model-mix sequencing problem to minimize the risk of stopping the conveyor, International Journal of Production Research 17(1979)233–247.
G. Steiner and S. Yeomans, Level schedules for mixed-model, just-in-time assembly processes, Management Science 36(1993)728–735.
G. Steiner and S. Yeomans, Level schedules for mixed-model, multi-level JIT assembly systems with pegging, Working Paper, Faculty of Administrative Studies, York University, North York, Ontario, 1993.
S. Yeomans, Optimal level schedules for mixed-model, just-in-time assembly systems, Ph.D. Dissertation, Department of Management Science and Information Systems, McMaster University, Hamilton, Ontario, 1992.
Rights and permissions
About this article
Cite this article
Kubiak, W., Steiner, G. & Scott Yeomans, J. Optimal level schedules for mixed-model, multi-level just-in-time assembly systems. Annals of Operations Research 69, 241–259 (1997). https://doi.org/10.1023/A:1018985029260
Issue Date:
DOI: https://doi.org/10.1023/A:1018985029260