A dynamic program with fathoming and dynamic upper bounds for the assembly line balancing problem

It has been suggested that relaxation and fathoming methods can be used to reduce the state space of certain dynamic programs. This paper applies these techniques to the dynamic program for assembly line balancing and shows that with an optimal upper bound, a substantial reduction in state space is possible. With a static nonoptimal upper bound however, the approach is found to offer little improvement over conventional dynamic programming. To achieve more consistent results, a dynamic upper bound procedure is proposed. Applied to a well-known set of assembly line balancing problems, the performance of the proposed algorithm was found comparable to a state-of-the-art integer programming method. The approach appears generalizable to dynamic programs with a similar structure.