Assembly System Design: A Branch and Cut Approach

Abstract

This paper addresses the single-product assembly system design problem (ASDP), which seeks to minimize total cost by optimally integrating design (selecting the machine type to locate at each activated station) and operating issues (assigning tasks to observe precedence relationships and cycle time restrictions). We propose an effective branch-and-cut approach for solving single-product ASDPs, adapting inequalities known to be valid for embedded line balancing structures to form inequalities that are valid for the ASDP. The implementation also involves a specialized preprocessor, a heuristic, separation procedures, and an enumeration scheme. Computational tests establish benchmark results for this first implementation of cutting planes for solving the ASDP.