Project selection with discounted returns and multiple constraints

Project selection with discounted returns and multiple constraints

0.00 Avg rating0 Votes
Article ID: iaor1999622
Country: Netherlands
Volume: 94
Issue: 1
Start Page Number: 87
End Page Number: 96
Publication Date: Oct 1996
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: integer, programming: dynamic, scheduling
Abstract:

This paper considers the problem of selecting a subset of N projects subject 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 hence the overall problem reduces to a multiconstraint nonlinear integer (0–1) problem. This problem can be solved optimally in pseudo-polynomial time using a dynamic programming method but the method is impractical except when the number of constraints, K, is very small. We therefore propose two heuristic methods which require O(N3K) and O(N4K) computations, respectively, and evaluate them computationally on 640 problems with up to 100 projects and up to 8 constraints. The results 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 optimum for the multiconstraint case.

Reviews

Required fields are marked *. Your email address will not be published.