Tool design problems in a punch press flexible manufacturing system

Vernon Ning Hsu, Dilip Chhajed, Timothy J. Lowe

Research output: Contribution to journalArticlepeer-review


In this paper, we study tool design problems encountered in using a punch press Flexible Manufacturing System (FMS) for producing flat sheet-metal parts. We consider the problem of designing the minimum number of tools needed to punch a given set of holes in the parts. Holes described by a single attribute as well as two attributes are considered. We model the tool design problems as graph theoretic problems. Such an approach is believed to be new for the problem studied. We have made the following major contributions: First, we show that the two-attribute tool design problem is equivalent to the minimum clique cover problem on the intersection graph of rectangles, which is a well known NP-complete problem. Second, we develop a fast algorithm to construct a set-covering formulation from the underlying graph model. In addition, we show that our approach has applications beyond the tool design problem (e.g., location problems).

Original languageEnglish (US)
Pages (from-to)331-340
Number of pages10
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number4
StatePublished - Apr 1998

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Tool design problems in a punch press flexible manufacturing system'. Together they form a unique fingerprint.

Cite this