Assignment of tools to machines in a flexible manufacturing system

Thomas H. D'Alfonso, Jose A. Ventura

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


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 mafazine, 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 to a graph theoretic heuristic that utilizes cluster analysis. For most test problems, the subgradient algorithm is superior, but is sensitive to convergence parameters.

Original languageEnglish (US)
Pages (from-to)115-133
Number of pages19
JournalEuropean Journal of Operational Research
Issue number1
StatePublished - Feb 16 1995

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Assignment of tools to machines in a flexible manufacturing system'. Together they form a unique fingerprint.

Cite this