A branch and cut approach for certain problems in assembly systems

Abstract

This research addresses certain problems associated with assembly systems, namely the assembly line balancing problem (ALBP), the workload smoothing problem (WSP), and the single-product assembly system design problem (ASDP). The ALBP prescribes task assignments which minimize the number of stations; the WSP, task assignments which minimize the maximum idle time at all stations in a line of a specified number of stations; and the ASDP, machine types and task assignments such that total cost is minimized. Motivated by the success of strong cutting plane methods in solving a variety of problems and the fact that inequalities that are valid for a polytope are also valid for more complex problems in which the polytope is embedded, this research begins by studying the polyhedral structure of the ALBP. The node packing problem defined on the intersection graph which is constructed by certain rules is shown to represent a relaxation of the ALBP. Consequently, several families of valid inequalities are derived and proven that under certain conditions they define facets for the associated polytopes. A polynomial separation algorithm is devised for each family of valid inequalities. In addition, 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. A branch and cut algorithm is implemented for the WSP, directly incorporating the separation algorithms and preprocessing methods for the ALBP, which is embedded in the WSP. Similarly, valid inequalities for the ASDP are derived by extending the inequalities that have been shown to be valid for the ALBP. Consequently, a branch and cut method is implemented for solving the ASDP, adapting the separation algorithms and preprocessing methods that have been devised for the ALBP. Computational results that evaluate the efficacy of the branch and cut approaches for both the WSP and the ASDP clearly demonstrate that the branch and cut algorithms can achieve an order of magnitude improvement in runtimes and the number of nodes enumerated. In fact, the branch and cut techniques are shown to be powerful and offer promise for other problems as well.