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 classi
cal production settings, and so-called tool management problems appear to b
e among the more fundamental ones of these problems. Most tool management p
roblems are hard to solve, so that numerous approximate solution techniques
have been proposed to tackle them. In this paper, we investigate the quali
ty of such algorithms by means of worst-case analysis. We consider several
polynomial-time approximation algorithms described in the literature, and w
e show that all these algorithms exhibit rather poor worst-case behavior. W
e also study the complexity of solving tool management problems approximate
ly. In this respect, we investigate the interrelationships among tool manag
ement problems, as well as their relationships with other well-known combin
atorial problems such as the maximum clique problem or the set covering pro
blem, and we prove several negative results on the approximability of vario
us tool management problems. (C) 1999 John Wiley & Sons, Inc.