Capacity and tool allocation problem in flexible manufacturing systems

Bilgin S., Azizoglu M.

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, vol.57, no.6, pp.670-681, 2006 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 57 Issue: 6
  • Publication Date: 2006
  • Doi Number: 10.1057/palgrave.jors.2602039
  • Journal Name: JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Page Numbers: pp.670-681
  • Keywords: operation assignment, capacity allocation, tool allocation, LAGRANGIAN-RELAXATION, MACHINES, MODEL
  • Middle East Technical University Affiliated: Yes

Abstract

This study addresses an allocation problem that arises in the semiconductor industry and flexible manufacturing systems where the tools should be loaded on computer numerical controlled (CNC) machines to process a number of operations. The time and tool magazine capacities of the CNC machines and the number of available tools of each type are limited. The objective is to maximize the total weight of operation assignments. We present a mixed integer programming formulation of the problem and show that the problem is NP-hard in the strong sense. We show that the linear programming relaxation upper bound dominates the best possible Lagrangean relaxation upper bound. We develop several lower bounding procedures and a lower bounding procedure using Lagrangean relaxation approach. Our computational results show that the upper and lower bounding procedures produce near-optimal solutions in reasonable times.