A Branch and Cut Approach for Workload Smoothing on Assembly Lines
Anulark Pinnoi, Wilbert F. Wilhelm
INFORMS Journal on Computing · 1997 · Volume 9 · Issue 4
Abstract
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.
Keywords
workload smoothing, branch and cut
Enable JavaScript for citation tools and additional paper interactions.