PART SELECTION AND TOOL ALLOCATION IN DISCRETE PARTS MANUFACTURING

A recurrent problem in discrete parts manufacturing is to select the o ptimal 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 solutio n. 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 cas e relative error of the proposed heuristic approaches 1/2. Finally, we demonstrate via extensive computational experimentation that the gree dy heuristic produces near optimal solutions for a variety of problem instances.