TITLE

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

AUTHOR(S)
Sewell, E. C.; Jacobson, S. H.
PUB. DATE
July 2012
SOURCE
INFORMS Journal on Computing;Summer2012, Vol. 24 Issue 3, p433
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
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.
ACCESSION #
84109522

 

Related Articles

  • A Multiobjective Optimization Algorithm to Solve the Part Feeding Problem in Mixed-Model Assembly Lines. Fathi, Masood; Alvarez, Maria Jesus; Mehraban, Farhad Hassani; Rodríguez, Victoria // Mathematical Problems in Engineering;2014, p1 

    Different aspects of assembly line optimization have been extensively studied. Part feeding at assembly lines, however, is quite an undeveloped area of research. This study focuses on the optimization of part feeding at mixed-model assembly lines with respect to the Just-In-Time principle...

  • The cluster problem revisited. Wechsung, Achim; Schaber, Spencer; Barton, Paul // Journal of Global Optimization;Mar2014, Vol. 58 Issue 3, p429 

    In continuous branch-and-bound algorithms, a very large number of boxes near global minima may be visited prior to termination. This so-called cluster problem (J Glob Optim 5(3):253-265, ) is revisited and a new analysis is presented. Previous results are confirmed, which state that at least...

  • Competitive Two-Agent Scheduling with Learning Effect and Release Times on a Single Machine. Der-Chiang Li; Peng-Hsiang Hsu // Mathematical Problems in Engineering;2013, p1 

    The learning effect has gained much attention in the scheduling research recently, where many researchers have focused their problems on only one optimization. This study further addresses the scheduling problem in which two agents compete to perform their own jobs with release times on a common...

  • A Discrete Fruit Fly Optimization Algorithm for the Traveling Salesman Problem. Jiang, Zi-bin; Yang, Qiong // PLoS ONE;11/3/2016, Vol. 11 Issue 11, p1 

    The fruit fly optimization algorithm (FOA) is a newly developed bio-inspired algorithm. The continuous variant version of FOA has been proven to be a powerful evolutionary approach to determining the optima of a numerical function on a continuous definition domain. In this study, a discrete FOA...

  • BUFFER SPACE ALLOCATION IN AUTOMATED ASSEMBLY LINES. Smith, J. MacGregor; Daskalaki, Sophia // Operations Research;Mar/Apr88, Vol. 36 Issue 2, p343 

    Automated assembly lines are modeled as finite open queueing networks and a heuristic for buffer space allocation within these lines is presented. The Expansion Method, an analytical technique for modeling finite open queueing networks and Powell's unconstrained optimization procedure are...

  • Practical ABC intelligence solution for Quadratic Assignment. Behzadi, Golnar; Sundarakani, Balan // Proceedings of the International Conference on Industrial Engine;2014, p959 

    One of the key challenges in the scope of NP-hard problems is associated with finding a suitable solution algorithm as a result of degrees of complexity integrated in such problems. Among that, Quadratic assignment problems (QAPs) have considerable popularity because of various real-world...

  • APPLICATION OF COMBINATIONAL PROGRAMMING TO A CLASS OF ALL-ZERO-ONE INTEGER PROGRAMMING PROBLEMS. Pierce, John F. // Management Science;Nov68, Vol. 15 Issue 3, p191 

    Problem-solving procedures based on the methods of combinatorial programming are presented for solving a class of integer programming problems in which all elements are zero or one. All of the procedures seek first a feasible solution and then successively better and better feasible solutions...

  • Runtime Analysis of Ant Colony Optimization with Best-So-Far Reinforcement. Gutjahr, Walter J.; Sebastiani, Giovanni // Methodology & Computing in Applied Probability;Sep2008, Vol. 10 Issue 3, p409 

    The paper provides some theoretical results on the analysis of the expected time needed by a class of Ant Colony Optimization algorithms to solve combinatorial optimization problems. A part of the study refers to some general results on the expected runtime of the considered class of algorithms....

  • A Stochastic Combinatorial Optimization Model for Test Sequence Optimization.  // Journal of Computers;Sep2010, Vol. 5 Issue 9, p1424 

    No abstract available.

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics