×

zbMATH — the first resource for mathematics

A branch, bound, and remember algorithm for the simple assembly line balancing problem. (English) Zbl 06599280
Summary: We present a new exact algorithm for the assembly line balancing problem. The algorithm finds and verifies the optimal solution for every problem in the combined benchmarks of Hoffmann, Talbot, and Scholl in less than one-half second per problem, on average, including one problem that has remained open for over 10 years. The previous best-known algorithm is able to solve 257 of the 269 benchmarks. The new algorithm is based on a branch-and-bound method that uses memory to eliminate redundant subproblems.

MSC:
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bautista J., Pereira J., Dorigo M., Di Caro G., Sampels M.Ant algorithms for assembly line balancing. Ant Algorithms: 3rd Internat. Workshop, Vol. 2463 (2002) (Springer, Berlin) 49-61Lecture Notes in Computer Science
[2] Bautista J., Pereira J.Ant algorithms for a time and space constrained assembly line balancing problem. Eur. J. Oper. Res. (2007) 177(3):2016-2032CrossRef · Zbl 1109.90032
[3] Bautista J., Pereira J.A dynamic programming-based heuristic for the assembly line balancing problem. Eur. J. Oper. Res. (2009) 194(3):787-794CrossRef · Zbl 1168.90404
[4] Bautista J., Suarez R., Mateo M., Companys R.Local search heuristics for the assembly line balancing problem with incompatibilities between tasks. Proc. 2000 IEEE Internat. Conf. Robotics and Automation (2000) (IEEE, Piscataway, NJ) 2404-2409
[5] Becker C., Scholl A.A survey on problems and methods in generalized assembly line balancing. Eur. J. Oper. Res. (2006) 168(3):694-715CrossRef · Zbl 1083.90013
[6] Blum C.Beam-ACO for simple assembly line balancing. INFORMS J. Comput. (2008) 20(4):618-627Abstract · Zbl 1243.90058
[7] Boysen N., Fliedner M., Scholl A.A classification of assembly line balancing problems. Eur. J. Oper. Res. (2007) 183(2):674-693CrossRef · Zbl 1179.90103
[8] Dechter R., Pearl J.Generalized best-first search strategies and the optimality of A*. J. Assoc. Comput. Machinery (1985) 32(3):505-536CrossRef · Zbl 0631.68075
[9] Easton F. F.A dynamic program with fathoming and dynamic upper bounds for the assembly line balancing problem. Comput. Oper. Res. (1990) 17(2):163-175CrossRef · Zbl 0689.90050
[10] Fleszar K., Hindi K. S.An enumerative heuristic and reduction methods for the assembly line balancing problem. Eur. J. Oper. Res. (2003) 145(3):606-620CrossRef · Zbl 1011.90039
[11] Gourgand M., Grangeon N., Norre S.Metaheuristics based on bin packing for the line balancing problem. RAIRO Oper. Res. (2007) 41(2):193-211 · Zbl 1190.90087
[12] Hall S. N., Jacobson S. H., Sewell E. C.An analysis of pediatric vaccine formulary selection problems. Oper. Res. (2008) 56(6):1348-1365Link · Zbl 1167.90594
[13] Hoffmann T. R.Assembly line balancing with a precedence matrix. Management Sci. (1963) 9(4):551-562Link
[14] Hoffmann T. R.Assembly line balancing: A set of challenging problems. Internat. J. Production Res. (1990) 28(10):1807-1815CrossRef
[15] Hoffmann T. R.EUREKA: A hybrid system for assembly line balancing. Management Sci. (1992) 38(1):39-47Link · Zbl 0825.90511
[16] Johnson R. V.Optimally balancing large assembly lines with ”FABLE.”. Management Sci. (1988) 34(2):240-253Link
[17] Jouglet A., Baptiste P., Carlier J., Leung J. Y.-T.Branch-and-bound algorithms for total weighted tardiness. Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004) (CRC Press, Boca Raton, FL) . Chapter 13 · Zbl 1056.90054
[18] Kao G. K., Sewell E. C., Jacobson S. H.A branch, bound, and remember algorithm for the 1|r_i|t_i scheduling problem. J. Scheduling (2009) 12(2):163-175CrossRef · Zbl 1179.90139
[19] Kao G. K., Sewell E. C., Jacobson S. H., Hall S. N.New dominance rules and exploration strategies for the 1|r_i|U_i scheduling problem. Comput. Optim. Appl. (2011) . Forthcoming
[20] Korf R. E.An improved algorithm for optimal bin packing. Proc. 18th Internat. Joint Conf. Artificial Intelligence (2003) (Morgan Kaufmann, San Francisco) 1252-1258
[21] Lapierre S. D., Ruiz A., Soriano P.Balancing assembly lines with tabu search. Eur. J. Oper. Res. (2006) 168(3):826-837CrossRef · Zbl 1083.90017
[22] Michie D.”Memo” functions and machine learning. Nature (1968) 218(5136):19-22
[23] Morin T. L., Marsten R. E.Branch-and-bound strategies for dynamic programming. Oper. Res. (1976) 24(4):611-627Link · Zbl 0352.90075
[24] Nourie F. J., Venta E. R.Finding optimal line balances with OptPack. Oper. Res. Lett. (1991) 10(3):165-171CrossRef · Zbl 0738.90038
[25] Sabuncuoglu I., Erel E., Tanyer M.Assembly line balancing using genetic algorithms. J. Intelligent Manufacturing (2000) 11(3):295-310
[26] Scholl A., Becker C.State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. Eur. J. Oper. Res. (2006) 168(3):666-693CrossRef · Zbl 1083.90019
[27] Scholl A., Klein R.SALOME: A bidirectional branch-and-bound procedure for assembly line balancing. INFORMS J. Comput. (1997) 9(4):319-334Link · Zbl 0895.90121
[28] Scholl A., Klein R.Balancing assembly lines effectively–A computational comparison. Eur. J. Oper. Res. (1999) 114(1):50-58CrossRef · Zbl 0949.90034
[29] Scholl A., Voß S.Simple assembly line balancing–Heuristic approaches. J. Heuristics (1996) 2(3):217-244
[30] Sewell E. C., Kao G. K., Jacobson S. H.A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times. (2009) . Technical report, Southern Illinois University, Edwardsville · Zbl 1258.90043
[31] Sprecher A.A competitive branch-and-bound algorithm for the simple assembly line balancing problem. Internat. J. Production Res. (1999) 37(8):1787-1816 · Zbl 0949.90522
[32] Talbot F. B., Patterson J. H., Gehrlein W. V.A comparative evaluation of heuristic line balancing techniques. Management Sci. (1986) 32(4):430-454Link
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.