Grouping parts and tools in flexible manufacturing systems production planning

Batch production in a flexible manufacturing environment is necessary not only to satisfy some technological constraints but also to achieve potential reductions in processing time, to reduce work-in-process and finished goods inventories, and to simplify the production planning process. Central to batch production is the problem of grouping part types and the required tools into families for simultaneous processing. This paper presents a practical and useful algorithm for grouping parts and tools in flexible manufacturing systems (FMSs).This problem is first formulated as a 0-1 linear integer program. A Lagrangian dual formulation is then developed to obtain an upper bound on the optimal objective function value. The Lagrangian dual program is further decomposed into a linear network subproblem and a set of knapsack subproblems. A subgradient algorithm with several enhancement strategies is employed to minimize the upper bound obtained from the dual problem. Computational results for medium and large-scale problems demonstrate that this solution procedure is effective.