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 to ols may require multiple slots. Tools are grouped based upon a pairwis e similarity coefficient that indicates the frequency of successive op erations that require both tools. Typical solution strategies have inc luded 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, tw o integer subproblems are formed in which the first is further decompo sed into several knapsack subproblems. The second subproblem can be so lved by a linear network code. A subgradient algorithm is developed to solve the dual problem. The algorithm is compared to a graph theoreti c heuristic that utilizes cluster analysis. For most test problems, th e subgradient algorithm is superior, but is sensitive to convergence p arameters.