A column-generation approach for the assembly system design problem with tool changes

This assembly system design problem (ASDP) is to prescribe the minimum-cost assignment of machines, tooling, and tasks to stations, observing task precedence relationships and cycle time requirements. The ASDP with tool changes also prescribes the optimal sequence of operations at each station, including tool changes, which are important, for example, in robotic assembly. A unique solution approach decomposes the model into a master problem, which is a minimum-cost network-flow problem that can be solved as a linear program, and subproblems, which are constrained, shortest-path problems that generate station configurations. Subproblems are solved on state-operation networks, which extend earlier formulations to incorporate tooling considerations. This paper presents a specialized algorithm to solve the subproblems. Computational tests benchmark the approach on several classes of problems, and the results are promising. In particular, tests demonstrate the importance of using engineering judgment to manage problem complexity by controlling the size of state-operation networks.