×

zbMATH — the first resource for mathematics

State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. (English) Zbl 1083.90019
Summary: The assembly line balancing problem arises and has to be solved when an assembly line has to be configured or redesigned. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line. The so-called simple assembly line balancing problem (SALBP), a basic version of the general problem, has attracted attention of researchers and practitioners of operations research for almost half a century.
In this paper, we give an up-to-date and comprehensive survey of SALBP research with a special emphasis on recent outstanding and guiding contributions to the field.

MSC:
90B30 Production models
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts, E.H.L.; Korst, J.H.M., Simulated annealing and Boltzmann machines: A stochastic approach to combinatorial optimization and neural computing, (1989), Wiley Chichester · Zbl 0674.90059
[2] Ajenblit, D.A., Wainwright, R.L., 1998. Applying genetic algorithms to the U-shaped assembly line balancing problem. In: Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, Anchorage, AK, pp. 96-101.
[3] Alvim, A.C.F., Ribeiro, C.C., Glover, F., Aloise, D.J., 2003. A hybrid improvement heuristic for the one-dimensional bin packing problem. Working Paper, Catholic University of Rio de Janeiro, Brazil.
[4] Anderson, E.J.; Ferris, M.C., Genetic algorithms for combinatorial optimization: the assembly line balancing problem, ORSA journal on computing, 6, 161-173, (1994) · Zbl 0805.90056
[5] Arcus, A.L., COMSOAL: A computer method of sequencing operations for assembly lines, International journal of production research, 4, 259-277, (1966)
[6] Balas, E., An additive algorithm for solving linear programs with zero-one variables, Operations research, 13, 517-546, (1965) · Zbl 0194.19903
[7] Bautista, J.; Pereira, J., Ant algorithms for assembly line balancing, (), 65-75
[8] Bautista, J., Suarez, R., Mateo, M., Companys, R., 2000. Local search heuristics for the assembly line balancing problem with incompatibilities between tasks. In: Proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, CA, 2404-2409.
[9] Baybars, I., A survey of exact algorithms for the simple assembly line balancing problem, Management science, 32, 909-932, (1986) · Zbl 0601.90081
[10] Baybars, I., An efficient heuristic method for the simple assembly line balancing problem, International journal of production research, 24, 149-166, (1986) · Zbl 0584.90042
[11] Baykasoglu, A., Özbakir, L., Telcioglu, M.B., 2002. Multiple-rule based genetic algorithm for simple assembly line balancing problems (MRGA-SALBP-I). In: Proceedings of the 5th International Conference on Managing Innovations in Manufacturing (MIM) 2002, Milwaukee, WI, USA, pp. 402-408.
[12] Becker, C., Scholl, A., this issue. A survey on problems and methods in generalized assembly line balancing. European Journal of Operations Research. doi:10.1016/j.ejor.2004.07.023. · Zbl 1083.90013
[13] Bennett, G.B.; Byrd, J., A trainable heuristic procedure for the assembly line balancing problem, AIIE transactions, 8, 195-201, (1976)
[14] Berger, I.; Bourjolly, J.-M.; Laporte, G., Branch-and-bound algorithms for the multi-product assembly line balancing problem, European journal of operational research, 58, 215-222, (1992) · Zbl 0757.90029
[15] Betts, J.; Mahmoud, K.I., A method for assembly line balancing, Engineering costs and production economics, 18, 55-64, (1989)
[16] Bock, S., 2000. Modelle und verteilte Algorithmen zur Planung getakteter Fließlinien: Ansätze zur Unterstützung eines effizienten Mass Customization, Gabler, Wiesbaden.
[17] Bock, S.; Rosenberg, O., A new distributed fault-tolerant algorithm for the simple assembly line balancing problem, (), 474-480
[18] Bockmayr, A., Pisaruk, N., 2001. Solving assembly line balancing problems by combining IP and CP. In: Proceedings of the 6th Annual Workshop of the ERCIM Working Group on Constraints, Prague, Czech Republic.
[19] Boctor, F.F., A multiple-rule heuristic for assembly line balancing, Journal of the operational research society, 46, 62-69, (1995) · Zbl 0829.90068
[20] Bonney, M.C., Schofield, N.A., Green, A., 1976. Assembly line balancing and mixed model line sequencing. In: Proceedings of the Fifth INTERNET World Congress, Birmingham, pp. 112-121.
[21] Buxey, G.M.; Slack, N.D.; Wild, R., Production flow line system design–A review, AIIE transactions, 5, 37-48, (1973)
[22] Chiang, W.-C., The application of a tabu search metaheuristic to the assembly line balancing problem, Annals of operations research, 77, 209-227, (1998) · Zbl 0895.90103
[23] Dar-El, E.M.; Rubinovitch, Y., MUST–A multiple solutions technique for balancing single model assembly lines, Management science, 25, 1105-1114, (1979)
[24] De Reyck, B.; Herroelen, W., Assembly line balancing by resource-constrained project scheduling–A critical appraisal, Foundations of computing and control engineering, 22, 143-167, (1997) · Zbl 0899.68007
[25] Driscoll, J.; Thilakawardana, D., The definition of assembly line balancing difficulty and evaluation of balance solution quality, Robotics and computer integrated manufacturing, 17, S81-S86, (2001)
[26] Easton, F.; Faaland, B.; Klastorin, T.D.; Schmitt, T., Improved network based algorithms for the assembly line balancing problem, International journal of production research, 27, 1901-1915, (1989)
[27] Erel, E.; Sarin, S.C., A survey of the assembly line balancing procedures, Production planning and control, 9, 414-434, (1998)
[28] Falkenauer, E., A hybrid grouping algorithm for bin packing, Journal of heuristics, 2, 5-30, (1996)
[29] Falkenauer, E., 1997. A grouping genetic algorithm for line balancing with resource dependent task times. In: Proceedings of the Fourth International Conference on Neural Information Processing 1997, University of Otago, Dunedin, New Zealand, pp. 464-468.
[30] Falkenauer, E., Delchambre, A., 1992. A genetic algorithm for bin packing and line balancing. In: Proceedings of the 1992 IEEE International Conference on Robotics and Automation, Nice, France, pp. 1186-1192.
[31] Fekete, S.P.; Schepers, J., New classes of fast lower bounds for bin packing problems, Mathematical programming, 91, 11-31, (2001) · Zbl 1051.90020
[32] Fleszar, K.; Hindi, K.S., An enumerative heuristic and reduction methods for the assembly line balancing problem, European journal of operational research, 145, 606-620, (2003) · Zbl 1011.90039
[33] Freeman, D.S., Swain, R.W., 1986. A heuristic technique for balancing automated assembly lines. Research Report No. 86-6, Industrial and Systems Engineering Department, University of Florida, Gainesville.
[34] Gehrlein, W.V.; Patterson, J.H., Sequencing for assembly lines with integer task times, Management science, 21, 1064-1070, (1975)
[35] Gehrlein, W.V.; Patterson, J.H., Balancing single model assembly lines: comments on a paper by E.M. dar-el (mansoor), AIIE transactions, 10, 109-112, (1978)
[36] Ghosh, S.; Gagnon, R.J., A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems, International journal of production research, 27, 637-670, (1989)
[37] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers Boston · Zbl 0930.90083
[38] Görke, M.; Lentes, H.-P., Leistungsabstimmung von montagelinien, Arbeitsvorbereitung, 13, 71-77, (1976), 106-113, and 147-153
[39] Goldberg, D.E., Genetic algorithms in search, optimization and machine learning, (1989), Addison-Wesley Reading, MA · Zbl 0721.68056
[40] Goncalves, J.F.; Almeida, J.R., A hybrid genetic algorithm for assembly line balancing, Journal of heuristics, 8, 629-642, (2002)
[41] Gutjahr, A.L.; Nemhauser, G.L., An algorithm for the line balancing problem, Management science, 11, 308-315, (1964) · Zbl 0137.39303
[42] Hackman, S.T.; Magazine, M.J.; Wee, T.S., Fast, effective algorithms for simple assembly line balancing problems, Operations research, 37, 916-924, (1989) · Zbl 0689.90047
[43] Heinrici, A., A comparison between simulated annealing and tabu search with an example from the production planning, (), 498-503
[44] Held, M.; Karp, R.M.; Shareshian, R., Assembly line balancing–dynamic programming with precedence constraints, Operations research, 11, 442-459, (1963) · Zbl 0126.36201
[45] Helgeson, W.B.; Birnie, D.P., Assembly line balancing using the ranked positional weight technique, Journal of industrial engineering, 12, 394-398, (1961)
[46] Hoffmann, T.R., Assembly line balancing with a precedence matrix, Management science, 9, 551-562, (1963)
[47] Hoffmann, T.R., Assembly line balancing: A set of challenging problems, International journal of production research, 28, 1807-1815, (1990)
[48] Hoffmann, T.R., EUREKA: A hybrid system for assembly line balancing, Management science, 38, 39-47, (1992) · Zbl 0825.90511
[49] Hoffmann, T.R., Response to note on microcomputer performance of “FABLE” on hoffmann’s data sets, Management science, 39, 1192-1193, (1993)
[50] Jackson, J.R., A computing procedure for a line balancing problem, Management science, 2, 261-271, (1956)
[51] Jaeschke, G., Branching and bounding: eine allgemeine methode zur Lösung kombinatorischer probleme, Ablauf- und planungsforschung, 5, 133-155, (1964)
[52] Johnson, R.V., Assembly line balancing algorithms: computation comparisons, International journal of production research, 19, 277-287, (1981)
[53] Johnson, R.V., Optimally balancing large assembly lines with “FABLE”, Management science, 34, 240-253, (1988)
[54] Johnson, R.V., Note: microcomputer performance of “FABLE” on hoffmann’s data sets, Management science, 39, 1190-1193, (1993)
[55] Kao, E.P.C.; Queyranne, M., On dynamic programming methods for assembly line balancing, Operations research, 30, 375-390, (1982) · Zbl 0481.90043
[56] Kim, Y.K.; Kim, Y.; Kim, Y.J., Two-sided assembly line balancing: A genetic algorithm approach, Production planning and control, 11, 44-53, (2000)
[57] Klein, R.; Scholl, A., Maximizing the production rate in simple assembly line balancing–A branch and bound procedure, European journal of operational research, 91, 367-385, (1996) · Zbl 0924.90094
[58] Klein, R.; Scholl, A., Computing lower bounds by destructive improvement–an application to resource-constrained project scheduling, European journal of operational research, 112, 322-346, (1999) · Zbl 0938.90030
[59] Klein, R.; Scholl, A., PROGRESS: optimally solving the generalized resource-constrained project scheduling problem, Mathematical methods of operations research, 52, 467-488, (2000) · Zbl 1023.90028
[60] Klenke, H., 1977. Ablaufplanung bei Fließfertigung. Gabler, Wiesbaden.
[61] Labbé, M.; Laporte, G.; Mercure, H., Capacitated vehicle routing on trees, Operations research, 39, 616-622, (1991) · Zbl 0736.90029
[62] Lapierre, S.D., Ruiz, A., Soriano, P., this issue. Balancing assembly lines with tabu search. European Journal of Operational Research. doi:10.1016/j.ejor.2004.07.031. · Zbl 1083.90017
[63] Lawler, E.L., 1979. Efficient implementation of dynamic programming algorithms for sequencing problems, Report BW 106/79, Stichting Mathematisch Centrum, Amsterdam. · Zbl 0416.90036
[64] Leu, Y.Y.; Matheson, L.A.; Rees, L.P., Assembly line balancing using genetic algorithms with heuristic-generated initial populations and multiple evaluation criteria, Decision sciences, 25, 581-606, (1994)
[65] Martello, S.; Toth, P., Knapsack problems–algorithms and computer implementations, (1990), Wiley New York · Zbl 0708.68002
[66] McMullen, P.R.; Frazier, G.V., Using simulated annealing to solve a multiobjective assembly line balancing problem with parallel workstations, International journal of production research, 36, 2717-2741, (1998) · Zbl 0942.90545
[67] McMullen, P.R.; Tarasewich, P., Using ant techniques to solve the assembly line balancing problem, IIE transactions, 35, 605-617, (2003)
[68] McNaughton, R., Scheduling with deadlines and loss functions, Management science, 6, 1-12, (1959) · Zbl 1047.90504
[69] Merengo, C.; Nava, F.; Pozetti, A., Balancing and sequencing manual mixed-model assembly lines, International journal of production research, 37, 2835-2860, (1999) · Zbl 0949.90570
[70] Mertens, P., Fließbandabstimmung mit dem verfahren der begrenzten enumeration nach Müller-merbach, Ablauf- und planungsforschung, 8, 429-433, (1967)
[71] Moodie, C.L.; Young, H.H., A heuristic method of assembly line balancing for assumptions of constant or variable work element times, Journal of industrial engineering, 16, 23-29, (1965)
[72] Nourie, F.J.; Venta, E.R., Finding optimal line balances with optpack, Operations research letters, 10, 165-171, (1991) · Zbl 0738.90038
[73] Nourie, F.J.; Venta, E.R., Microcomputer performance of optpack on hoffmann’s data sets: comparison with eureka and FABLE, Management science, 42, 304-306, (1996) · Zbl 0884.90099
[74] Pastor, R.; Andres, C.; Duran, A.; Perez, M., Tabu search algorithms for an industrial multi-product and multi-objective assembly line balancing problem, with reduction of the task dispersion, Journal of the operational research society, 53, 1317-1323, (2002) · Zbl 1139.90419
[75] Peeters, M., Degraeve, Z., this issue. An linear programming based lower bound for the simple assembly line balancing problem. European Journal of Operational Research. doi:10.1016/j.ejor.2004.07.024. · Zbl 1083.90028
[76] Pinnoi, A.; Wilhelm, W.E., A branch and cut approach for workload smoothing on assembly lines, INFORMS journal on computing, 9, 335-350, (1997) · Zbl 0901.90133
[77] Pinnoi, A.; Wilhelm, W.E., A family of hierarchical models for assembly system design, International journal of production research, 35, 253-280, (1997) · Zbl 0949.90646
[78] Pinnoi, A.; Wilhelm, W.E., Assembly system design: A branch and cut approach, Management science, 44, 103-118, (1998) · Zbl 0989.90049
[79] Pinto, P.A.; Dannenbring, D.G.; Khumawala, B.M., A heuristic network procedure for the assembly line balancing problem, Naval research logistics quarterly, 25, 299-307, (1978) · Zbl 0402.90048
[80] Ponnambalam, S.; Aravindan, G.; Mogileeswar Naidu, G., A multi-objective genetic algorithm for solving assembly line balancing problem, International journal of advanced manufacturing technology, 16, 341-352, (2000)
[81] Rachamadugu, R.; Talbot, B., Improving the equality of workload assignments in assembly lines, International journal of production research, 29, 619-633, (1991)
[82] Raouf, A.; Tsui, C.L.; El-Sayed, E.A., A new heuristic approach to assembly line balancing, Computers and industrial engineering, 4, 223-234, (1980)
[83] Rekiek, B., de Lit, P., Pellichero, F., Falkenauer, E., Delchambre, A., 1999. Applying the equal piles problem to balance assembly lines. In: Proceedings of the ISATP 1999, Porto, Portugal, pp. 399-404.
[84] Rekiek, B.; de Lit, P.; Pellichero, F.; L’Eglise, T.; Fouda, P.; Falkenauer, E.; Delchambre, A., A multiple objective grouping genetic algorithm for assembly line balancing, Journal of intelligent manufacturing, 12, 467-485, (2001)
[85] Rekiek, B.; de Lit, P.; Delchambre, A., Hybrid assembly line design and user’s preferences, International journal of production research, 40, 1095-1111, (2002) · Zbl 1064.90534
[86] Rekiek, B.; Dolgui, A.; Delchambre, A.; Bratcu, A., State of art of optimization methods for assembly line design, Annual reviews in control, 26, 163-174, (2002)
[87] Rosenblatt, M.J.; Carlson, R.C., Designing a production line to maximize profit, IIE transactions, 17, 117-121, (1985)
[88] Rubinovitz, J.; Levitin, G., Genetic algorithm for assembly line balancing, International journal of production economics, 41, 343-354, (1995) · Zbl 0909.90161
[89] Sabuncuoglu, I.; Erel, E.; Tanyer, M., Assembly line balancing using genetic algorithms, Journal of intelligent manufacturing, 11, 295-310, (2000)
[90] Saltzman, M.J.; Baybars, I., A two-process implicit enumeration algorithm for the simple assembly line balancing problem, European journal of operational research, 32, 118-129, (1987) · Zbl 0622.90043
[91] Schofield, N.A., Assembly line balancing and the application of computer techniques, Computers and industrial engineering, 3, 53-69, (1979)
[92] Scholl, A., 1993. Data of assembly line balancing problems. Schriften zur Quantitativen Betriebswirtschaftslehre 16/93, TU Darmstadt.
[93] Scholl, A., 1994. Ein B&B-Verfahren zur Abstimmung von Einprodukt-Fließbändern bei gegebener Stationsanzahl. In: Dyckhoff, H. et al. (Eds.), Operations Research Proceedings 1993, Springer, Berlin, pp. 175-181.
[94] Scholl, A., Balancing and sequencing assembly lines, (1999), Physica Heidelberg · Zbl 0939.90527
[95] Scholl, A.; Klein, R., SALOME: A bidirectional branch and bound procedure for assembly line balancing, INFORMS journal on computing, 9, 319-334, (1997) · Zbl 0895.90121
[96] Scholl, A.; Klein, R., Balancing assembly lines effectively–A computational comparison, European journal of operational research, 114, 50-58, (1999) · Zbl 0949.90034
[97] Scholl, A.; Voß, S., Kapazitätsorientierte leistungsabstimmung in der fließfertigung, Zeitschrift für betrie-bswirtschaftliche forschung, 47, 919-935, (1995)
[98] Scholl, A.; Voß, S., Simple assembly line balancing–heuristic approaches, Journal of heuristics, 2, 217-244, (1996)
[99] Scholl, A.; Klein, R.; Jürgens, C., BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Computers and operations research, 24, 627-645, (1997) · Zbl 0882.90113
[100] Schrage, L.; Baker, K.R., Dynamic programming solution of sequencing problems with precedence constraints, Operations research, 26, 444-449, (1978) · Zbl 0383.90054
[101] Shtub, A.; Dar-El, E.M., A methodology for the selection of assembly systems, International journal of production research, 27, 175-186, (1989)
[102] Sprecher, A., A competitive branch-and-bound algorithm for the simple assembly line balancing problem, International journal of production research, 37, 1787-1816, (1999) · Zbl 0949.90522
[103] Sprecher, A., Dynamic search tree decomposition for balancing assembly lines by parallel search, International journal of production research, 41, 1413-1430, (2003)
[104] Suresh, G.; Sahu, S., Stochastic assembly line balancing using simulated annealing, International journal of production research, 32, 1801-1810, (1994) · Zbl 0906.90087
[105] Suresh, G.; Vinod, V.V.; Sahu, S., Genetic algorithm for assembly line balancing, Production planning and control, 7, 38-46, (1996)
[106] Talbot, F.B.; Patterson, J.H., An integer programming algorithm with network cuts for solving the assembly line balancing problem, Management science, 30, 85-99, (1984) · Zbl 0554.90055
[107] Talbot, F.B.; Patterson, J.H.; Gehrlein, W.V., A comparative evaluation of heuristic line balancing techniques, Management science, 32, 430-454, (1986)
[108] Thilakawardana, D., Driscoll, J., Deacon, G. An efficient genetic algorithm application in assembly line balancing. European Journal of Operational Research. Balancing of Automated Assembly and Transfer Lines (Special issue).
[109] Tonge, F.M., Summary of a heuristic line balancing procedure, Management science, 7, 21-39, (1960) · Zbl 0995.90625
[110] Tonge, F.M., Assembly line balancing using probabilistic combinations of heuristics, Management science, 11, 727-735, (1965)
[111] Ugurdag, H.F.; Rachamadugu, R.; Papachristou, C.A., Designing paced assembly lines with fixed number of stations, European journal of operational research, 102, 488-501, (1997) · Zbl 0955.90019
[112] Van Assche, F.; Herroelen, W.S., An optimal procedure for the single-model deterministic assembly line balancing problem, European journal of operational research, 3, 142-149, (1979) · Zbl 0392.90035
[113] Watanabe, T.; Hashimoto, Y.; Nishikawa, L.; Tokumaru, H., Line balancing using a genetic evolution model, Control engineering practice, 3, 69-76, (1995)
[114] Wee, T.S.; Magazine, M.J., Assembly line balancing as generalized bin packing, Operations research letters, 1/2, 56-58, (1982) · Zbl 0491.90049
[115] Zäpfel, G., Ausgewählte fertigungswirtschaftliche optimierungsprobleme von fließfertigungssystemen, (1975), Beuth Berlin
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.