A metaheuristic scheduling procedure for resource-constrained projects with cash flows

Resource-constrained project scheduling problems with cash flows (RCPSPCF) are complex, combinatorial optimization problems. Many heuristics have been reported in the literature that produce reasonable schedules in limited pr oject environments. However, the lack of a heuristic that dominates under d iffering project conditions can lead to a suboptimal choice of an appropria te heuristic for scheduling any given project. This may result in poor sche dules and monetary losses. This paper reports on the application of the tab u search metaheuristic procedure for the RCPSPCE Strategies for neighborhoo d generation and candidate selection that exploit the special features of t he problem are combined with a simple multiheuristic start procedure. Exten sive experimentation, with multiple data sets and comparison with an upper bound, indicates a significant improvement, both in project Net Present Val ue (NPV) as well as the number of projects, where the metaheuristic outperf orms the best known heuristics in the literature. More specifically, this p rocedure produces the best schedules in over 85% of the projects tested, in contrast to the best single-pass heuristics which have been shown to domin ate in at most 20% of the same cases. This iterative, general purpose heuri stic is able to adapt significantly better to the complex interactions of t he many critical parameters of the RCPSPCF than single-pass heuristics that use more specific information about each project environment. (C) 1999 Joh n Wiley & Sons, Inc.