Improved network based algorithms for the assembly line balancing problem

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.