The combinatorial nature of problems in process systems engineering has led to the establishment of mixed-integer optimization techniques as a major paradigm in this area. Despite the success of these methods in tackling practical sized problems, the issue of exponential increase of the computational effort with the problem size has been of great concern. A major open question 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 schemes can be devised. In this paper, we pursue analytical investigations to provide answers to these two questions in the context of the process planning problem. By means of a computational complexity analysis, we first prove that the general process planning problem is NP-hard, and thus efficient exact algorithms for this class of problems are unlikely to exist. Subsequently, we develop an approximation scheme for this problem and prove, via probabilistic analysis, that the error of the heuristic vanishes asymptotically with probability one as the problem size increases. Finally, we present computational results to substantiate the theoretical findings.