TY - JOUR

T1 - Worst-Case Performance of Approximation Algorithms for Tool Management Problems

AU - Crama, Yves

AU - Van De Klundert, Joris

PY - 1999/8

Y1 - 1999/8

N2 - Since the introduction of flexible manufacturing systems, researchers have investigated various planning and scheduling problems faced by the users of such systems. Several of these problems are not encountered in more classical production settings, and so-called tool management problems appear to be among the more fundamental ones of these problems. Most tool management problems are hard to solve, so that numerous approximate solution techniques have been proposed to tackle them. In this paper, we investigate the quality of such algorithms by means of worst-case analysis. We consider several polynomial-time approximation algorithms described in the literature, and we show that all these algorithms exhibit rather poor worst-case behavior. We also study the complexity of solving tool management problems approximately In this respect, we investigate the interrelationships among tool management problems, as well as their relationships with other well-known combinatorial problems such as the maximum clique problem or the set covering problem, and we prove several negative results on the approximability of various tool management problems.

AB - Since the introduction of flexible manufacturing systems, researchers have investigated various planning and scheduling problems faced by the users of such systems. Several of these problems are not encountered in more classical production settings, and so-called tool management problems appear to be among the more fundamental ones of these problems. Most tool management problems are hard to solve, so that numerous approximate solution techniques have been proposed to tackle them. In this paper, we investigate the quality of such algorithms by means of worst-case analysis. We consider several polynomial-time approximation algorithms described in the literature, and we show that all these algorithms exhibit rather poor worst-case behavior. We also study the complexity of solving tool management problems approximately In this respect, we investigate the interrelationships among tool management problems, as well as their relationships with other well-known combinatorial problems such as the maximum clique problem or the set covering problem, and we prove several negative results on the approximability of various tool management problems.

UR - http://www.scopus.com/inward/record.url?scp=0001707164&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1520-6750(199908)46:5<445::AID-NAV1>3.0.CO;2-R

DO - 10.1002/(SICI)1520-6750(199908)46:5<445::AID-NAV1>3.0.CO;2-R

M3 - Article

AN - SCOPUS:0001707164

SN - 0894-069X

VL - 46

SP - 445

EP - 462

JO - Naval Research Logistics

JF - Naval Research Logistics

IS - 5

ER -