Improved network based algorithms for the assembly line balancing problem

F. Easton, B. Faaland, T. D. Klastorn, T. Schmitt

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


In this paper, we present two network based algorithms for solving Type 1 assembly line balancing problems. These algorithms are based on the generation of the network of feasible subsets; the shortest path through this network corresponds to the minimum cost solution. While the methods presented here may require the generation of all feasible subsets, they use upper and lower bounds and dominance to eliminate many of these subsets. The first method (which we call the Frontscan algorithm) evaluates nodes in a manner similar to a procedure originally suggested by Mansoor (1967); the second procedure (which we call the Backscan algorithm) evaluates nodes by proceeding backwards through the network. Both procedures are quite versatile and are easily adapted to the line balancing problem with stochastic task times, duplicate parallel work stations, zoning restrictions, etc. Computational tests indicate that these algorithms are more efficient than previous network based methods (including dynamic programming methods) and favourably compare with branch and bound methods. A numerical example illustrates the algorithms.

Original languageEnglish (US)
Pages (from-to)1901-1915
Number of pages15
JournalInternational Journal of Production Research
Issue number11
StatePublished - Nov 1989

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Improved network based algorithms for the assembly line balancing problem'. Together they form a unique fingerprint.

Cite this