Capacity and tool allocation problem in flexible manufacturing systems

This study addresses an allocation problem that arises in the semiconductor industry and flexible manufacturing systems where the tools should be loaded on computer numerical controlled (CNC) machines to process a number of operations. The time and tool magazine capacities of the CNC machines and the number of available tools of each type are limited. The objective is to maximize the total weight of operation assignments. We present a mixed integer programming formulation of the problem and show that the problem is NP-hard in the strong sense. We show that the linear programming relaxation upper bound dominates the best possible Lagrangean relaxation upper bound. We develop several lower bounding procedures and a lower bounding procedure using Lagrangean relaxation approach. Our computational results show that the upper and lower bounding procedures produce near-optimal solutions in reasonable times.