The combinatorial nature of problems in process systems engineering has led
to the establishment of mixed-integer optimization techniques as a major p
aradigm in this area. Despite the success of these methods in tackling prac
tical sized problems, the issue of exponential increase of the computationa
l effort with the problem size has been of great concern. A major open ques
tion has been whether there is any hope of ever designing 'efficient' exact
algorithms for this class of problems. Further, if such algorithms are not
possible, one would like to know whether provably good approximation schem
es can be devised. In this paper, we pursue analytical investigations to pr
ovide answers to these two questions in the context of the process planning
problem. By means of a computational complexity analysis, we first prove t
hat the general process planning problem is NP-hard, and thus efficient exa
ct algorithms for this class of problems are unlikely to exist. Subsequentl
y, we develop an approximation scheme for this problem and prove, via proba
bilistic analysis, that the error of the heuristic vanishes asymptotically
with probability one as the problem size increases. Finally, we present com
putational results to substantiate the theoretical findings. (C) 2000 Elsev
ier Science Ltd. All rights reserved.