A Branch and Cut Approach for Workload Smoothing on Assembly Lines

This article presents a strong cutting plane method implemented by branch and cut to solve the assembly line workload smoothing problem which minimizes the maximum idle time for a specified number of stations to balance workloads assigned to all stations. The approach exploits a problem formulation that embeds the assembly line-balancing polytope. Thus, inequalities that are known to be valid for the line-balancing polytope are also valid for workload smoothing. This article describes an approach for implementing a strong cutting plane method that employs such valid inequalities, including separation algorithms. Preprocessing methods are described to decompose and reduce a precedence graph as well as to estimate bounds on parameters that are involved in valid inequalities. Finally, computational experience that evaluates the efficacy of the approach is presented.