Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm

In this paper we present an exact solution procedure of the branch-and-bound type for solving the multi-mode resource-constrained project scheduling problem. The basic enumeration scheme is enhanced by search tree reduction schemes which highly increase the performance of the algorithm. Among the benefits of the approach are ease of description, ease of implementation, ease of generalization, and, additionally, superior performance of the exact approach as well as reasonable heuristic capabilities of the truncated version. The procedure has been coded in C and implemented on a personal computer. Using the standard project generator ProGen we have established a wide range of instances. More than 10,000 problem instances have been systematically generated to evaluate the algorithm's performance. The experimental investigation illustrates: First, the effect of the bounding rules. Second, the superior performance of the exact approach and the capabilities of the truncated version; the size of the projects that can be solved to optimality has been nearly doubled. Third, the impact of the variation of several project characteristics on solution time and quality. (C) 1998 Elsevier Science B.V. All rights reserved.