Part selection and tool allocation in discrete parts manufacturing

A recurrent problem in discrete parts manufacturing is to select the optimal mix of parts and to allocate the necessary tools on a machine's carousel in order to maximize net profit. We formulate the problem as an integer program and compute an upper bound for the optimal solution. We then develop a greedy type heuristic to obtain a lower bound on the value of the optimal solution. Further, we show that the worst case relative error of the proposed heuristic approaches 1/2. Finally, we demonstrate via extensive computational experimentation that the greedy heuristic produces near optimal solutions for a variety of problem instances.