On the worst case performance of TESSA

Abstract

TESSA is a facility layout heuristic for obtaining a maximal planar adjacency graph (MPG) from relationship chart data. Computational experiments performed by Boswell (1992b) have shown that the algorithm produces good quality solutions, almost all of which are above 90% of the often unattainable upper bound. In this paper we show that the heuristic displays arbitrarily bad theoretical worst case performance.

Additional information

Notes on contributors

K. H. WATSON

To whom correspondence should be addressed