A Branch, Bound, and Remember Algorithm for the Simple Assembly Line Balancing Problem

References

• 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 ScienceCrossref, Google Scholar
• 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, Google Scholar
• Bautista J., Pereira J. A dynamic programming-based heuristic for the assembly line balancing problem. Eur. J. Oper. Res. (2009) 194(3):787–794Crossref, Google Scholar
• 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–2409Crossref, Google Scholar
• Becker C., Scholl A. A survey on problems and methods in generalized assembly line balancing. Eur. J. Oper. Res. (2006) 168(3):694–715Crossref, Google Scholar
• Blum C. Beam-ACO for simple assembly line balancing. INFORMS J. Comput. (2008) 20(4):618–627Link, Google Scholar
• Boysen N., Fliedner M., Scholl A. A classification of assembly line balancing problems. Eur. J. Oper. Res. (2007) 183(2):674–693Crossref, Google Scholar
• Dechter R., Pearl J. Generalized best-first search strategies and the optimality of A*. J. Assoc. Comput. Machinery (1985) 32(3):505–536Crossref, Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• Gourgand M., Grangeon N., Norre S. Metaheuristics based on bin packing for the line balancing problem. RAIRO Oper. Res. (2007) 41(2):193–211Crossref, Google Scholar
• Hall S. N., Jacobson S. H., Sewell E. C. An analysis of pediatric vaccine formulary selection problems. Oper. Res. (2008) 56(6):1348–1365Link, Google Scholar
• Hoffmann T. R. Assembly line balancing with a precedence matrix. Management Sci. (1963) 9(4):551–562Link, Google Scholar
• Hoffmann T. R. Assembly line balancing: A set of challenging problems. Internat. J. Production Res. (1990) 28(10):1807–1815Crossref, Google Scholar
• Hoffmann T. R. EUREKA: A hybrid system for assembly line balancing. Management Sci. (1992) 38(1):39–47Link, Google Scholar
• Johnson R. V. Optimally balancing large assembly lines with “FABLE.”. Management Sci. (1988) 34(2):240–253Link, Google Scholar
• 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 13Google Scholar
• Kao G. K., Sewell E. C., Jacobson S. H. A branch, bound, and remember algorithm for the 1|ri|∑ ti scheduling problem. J. Scheduling (2009) 12(2):163–175Crossref, Google Scholar
• Kao G. K., Sewell E. C., Jacobson S. H., Hall S. N. New dominance rules and exploration strategies for the 1|ri|∑ Ui scheduling problem. Comput. Optim. Appl. (2011) . ForthcomingGoogle Scholar
• Korf R. E. An improved algorithm for optimal bin packing. Proc. 18th Internat. Joint Conf. Artificial Intelligence (2003) (Morgan Kaufmann, San Francisco) 1252–1258Google Scholar
• Lapierre S. D., Ruiz A., Soriano P. Balancing assembly lines with tabu search. Eur. J. Oper. Res. (2006) 168(3):826–837Crossref, Google Scholar
• Michie D. “Memo” functions and machine learning. Nature (1968) 218(5136):19–22Crossref, Google Scholar
• Morin T. L., Marsten R. E. Branch-and-bound strategies for dynamic programming. Oper. Res. (1976) 24(4):611–627Link, Google Scholar
• Nourie F. J., Venta E. R. Finding optimal line balances with OptPack. Oper. Res. Lett. (1991) 10(3):165–171Crossref, Google Scholar
• Sabuncuoglu I., Erel E., Tanyer M. Assembly line balancing using genetic algorithms. J. Intelligent Manufacturing (2000) 11(3):295–310Crossref, Google Scholar
• 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, Google Scholar
• Scholl A., Klein R. SALOME: A bidirectional branch-and-bound procedure for assembly line balancing. INFORMS J. Comput. (1997) 9(4):319–334Link, Google Scholar
• Scholl A., Klein R. Balancing assembly lines effectively—A computational comparison. Eur. J. Oper. Res. (1999) 114(1):50–58Crossref, Google Scholar
• Scholl A., Voß S. Simple assembly line balancing—Heuristic approaches. J. Heuristics (1996) 2(3):217–244Crossref, Google Scholar
• 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, EdwardsvilleGoogle Scholar
• Sprecher A. A competitive branch-and-bound algorithm for the simple assembly line balancing problem. Internat. J. Production Res. (1999) 37(8):1787–1816Crossref, Google Scholar
• Talbot F. B., Patterson J. H., Gehrlein W. V. A comparative evaluation of heuristic line balancing techniques. Management Sci. (1986) 32(4):430–454Link, Google Scholar