Tool selection for optimal part production: a Lagrangian relaxation approach

This paper extends previous work on implementation problems associated with a flexible system that produces flat sheet-metal parts with interior holes. The paper makes four main contributions. First, we formulate the problem of selecting tooling and design standards to minimize the cost of producing parts as an optimization model. Second, we develop a projected subgradient algorithm for the Lagrangian relaxation of the problem by using the model's special structure to develop relationships between the Lagrangian multipliers. Third, we demonstrate that the algorithm produces close to optimal solutions (duality gap less than 2%) very quickly on a number of problems derived using a substantial data set obtained from a Chicago area firm. Fourth, an important variant of the traditional repair kit problem is shown to be a special case of the tool selection problem.