Assignment of tools to machines in a flexible manufacturing system

Subgradient optimization is employed to solve the problem of assigning tools to machines in a flexible manufacturing system (FMS). Machines in the FMS have a limited number of slots in the tool magazine, and tools may require multiple slots. Tools are grouped based upon a pairwise similarity coefficient that indicates the frequency of successive operations that require both tools. Typical solution strategies have included graph theoretic heuristics. Lagrangian relaxation is utilized in the algorithm developed in this article. The problem is formulated as a linear integer program. After dualizing two sets of constraints, two integer subproblems are formed in which the first is further decomposed into several knapsack subproblems. The second subproblem can be solved by a linear network code. A subgradient algorithm is developed to solve the dual problem. The algorithm is compared with a graph theoretic heuristic that utilizes cluster analysis. For most test problems, the subgradient algorithm is superior, but is sensitive to convergence parameters.