A linear programming based lower bound for the simple assembly line balancing problem

The simple assembly line balancing problem is a classical integer programming problem in operations research. A set of tasks, each one being an indivisible amount of work requiring a number of time units, must be assigned to workstations without exceeding the cycle time. We present a new lower bound, namely the LP relaxation of an integer programming formulation based on Dantzig–Wolfe decomposition. We propose a column generation algorithm to solve the formulation. Therefore, we develop a branch-and-bound algorithm to exactly solve the pricing problem. We assess the quality of the lower bound by comparing it with other lower bounds and the best-known solution of the various instances from the literature. Computational results show that the lower bound is equal to the best-known objective function value for the majority of the instances. Moreover, the new LP based lower bound is able to prove optimality for an open problem.