A Branch-and-Cut Approach for a Generic Multiple-Product….pdfVIP

A Branch-and-Cut Approach for a Generic Multiple-Product Assembly-System Design Problem Wilbert E. Wilhelm • Radu Gadidov Department of Industrial Engineering, Texas AM University, TAMUS 3131, College Station, Texas 77843-3131, USA Fort James Corporation, Deerfield, Illinois, 60015, USA wilhelm@tamu.edu _____________________________________________________________________________________ This paper presents two new models to deal with different tooling requirements in the generic multiple- product assembly-system design (MPASD) problem and proposes a new branch-and-cut solution approach, which adds cuts at each node in the search tree. It employs the facet generation procedure (FGP) to generate facets of underlying knapsack polytopes. In addition, it uses the FGP in a new way to generate additional cuts and incorporates two new methods that exploit special structures of the MPASD problem to generate cuts. One new method is based on a principle that can be applied to solve generic 0- 1 problems by exploiting embedded integral polytopes. The approach includes new heuristic and preprocessing methods, which are applied at the root node to manage the size of each instance. This paper establishes benchmarks for MPASD through an experiment in which the approach outperformed IBMs Optimization Subroutine Library (OSL), a commercially available solver. (Programming:Integer,Cutting Planes; Production Scheduling: Flexible Manufacturing Line Balancing) _____________________________________________________________________________________ 1. Introduction To serve the specialized demands of customers