Analytical investigations of the process planning problem

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.