×

Balancing \(U\)-lines in a multiple \(U\)-line facility. (English) Zbl 0949.90032

Summary: \(U\)-shaped production lines and facilities consisting of many such lines are important parts of modern manufacturing systems. The problem of balancing and rebalancing \(U\)-line facilities is studied in this paper. Like the traditional line balancing problem this problem is NP-hard. The objective is to assign tasks to a minimum number of regular, crossover, and multiline stations while satisfying cycle time, precedence, location, and station-type constraints. A secondary objective is to concentrate the idle time in one station so that improvement efforts can be focused there in accordance with modern just-in-time principles. A reaching dynamic programming algorithm is presented for determining optimal balances. It is effective for balancing and rebalancing facilities with any number of \(U\)-lines, provided that individual \(U\)-lines do not have more than 22 tasks and do not have wide, sparse precedence graphs.

MSC:

90B30 Production models
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baybars, I., A survey of exact algorithms for the simple assembly line balancing problem, Management Science, 32, 909-932 (1986) · Zbl 0601.90081
[2] Hackman, S. T.; Magazine, M. J.; Wee, T. S., Fast, effective algorithms for simple assembly line balancing problems, Operations Research, 37, 6, 916-924 (1989) · Zbl 0689.90047
[3] Hall, R. W., Zero Inventories (1983), Dow Jones, Irwin: Dow Jones, Irwin Homewood, Illinois
[4] Hoffmann, T. R., Eureka: A hybrid system for assembly line balancing, Management Science, 8, 1, 39-47 (1992) · Zbl 0825.90511
[5] Japan Management Association, Canon Production System (1987), Productivity Press: Productivity Press Portland, OR, USA
[6] Johnson, R. V., Assembly line balancing algorithms: Computational comparisons, International Journal of Production Research, 19, 277-287 (1981)
[7] Johnson, R. V., Optimally balancing large assembly lines with ‘Fable’, Management Science, 34, 1, 240-253 (1988)
[8] Lawler, E. L., Efficient implementation of dynamic programming algorithms for sequencing problems, (Report BW 106/79 (1979), Stichting Mathematish Centrum, 2e Boerhaavestraat 49: Stichting Mathematish Centrum, 2e Boerhaavestraat 49 Amsterdam) · Zbl 0416.90036
[9] Miltenburg, G. J.; Wijngaard, J., The U-line balancing problem, Management Science, 40, 10, 1378-1388 (1994) · Zbl 0822.90077
[10] Miltenburg, G. J.; Sparling, D. H., Optimal solution algorithms for the U-line balancing problem, (Working paper (1994), McMaster University: McMaster University Hamilton, Ontario) · Zbl 0951.90527
[11] Miltenburg, G. J.; Sparling, D. H., An extension of the U-line balancing problem: Travel times and pairs of U-lines, (Working paper (19946), McMaster University: McMaster University Hamilton, Ontario) · Zbl 0951.90527
[12] Monden, Y., Toyota Production System (1993), Industrial Engineering Press, Institute of Industrial Engineers: Industrial Engineering Press, Institute of Industrial Engineers Norcross, GA
[13] Provan, J. S.; Ball, M. O., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM Journal of Computing, 12, 777-788 (1983) · Zbl 0524.68041
[14] Schonberger, R. J., Japanese Manufacturing Techniques: Nine Hidden Lessons in Simplicity (1982), The Free Press: The Free Press New York
[15] Shimbum, N. K., The Factory Management Notebook Series: Case Studies in Improvement, Mixed-Model Production (1991), Productivity Press: Productivity Press Portland, OR, USA
[16] Steiner, G., On the complexity of dynamic programming for sequencing problems with precedence constraints, Annals of Operations Research, 26, 103-123 (1990) · Zbl 0709.90063
[17] Talbot, F. B.; Patterson, J. H., An integer programming algorithm with network cuts for solving the assembly line balancing problem, Management Science, 30, 1, 85-99 (1984) · Zbl 0554.90055
[18] Talbot, F. B.; Patterson, J. H.; Gehrlein, W. V., A comparative evaluation of heuristic line balancing techniques, Management Science, 32, 4, 430-454 (1986)
[19] Wantuck, K. A., Just In Time for America (1989), The Forum Ltd: The Forum Ltd Milwaukee, WI
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.