PROJECT SELECTION WITH DISCOUNTED RETURNS AND MULTIPLE CONSTRAINTS

This paper considers the problem of selecting a subset of N projects s ubject to multiple resource constraints, The objective is to maximize the net present value of the total return, where the return from each project depends on its completion time and the previously implemented projects. It is observed that the optimal order (sequence) of projects does not depend on the particular subset of selected projects and hen ce the overall problem reduces to a multiconstraint nonlinear integer (0-1) problem. This problem can be solved optimally in pseudo-polynomi al time using a dynamic programming method but the method is impractic al except when the number of constraints, K, is very small. We therefo re propose two heuristic methods which require O((NK)-K-3) and O((NK)- K-4) computations, respectively, and evaluate them computationally on 640 problems with up to 100 projects and up to 8 constraints. The resu lts show that the best heuristic is on the average within 0.08% of the optimum for the single-constraint case and within 2.61% of the optimu m for the multiconstraint case.