Network decomposition techniques for resource-constrained project scheduling

Numerous exact algorithms have been developed for solving the resource-constrained project scheduling problem. Experimental studies have shown that currently even projects with only 60 activities cannot be optimally solved within a reasonable amount of time. Therefore heuristics employing genetic concepts, sampling strategies, simulated annealing or taboo search have been developed. Additionally truncated versions of the branch-and-bound algorithms are studied. By limiting the CPU-time, the total number of node evaluations, or the number of branching alternatives, the solution time is reduced at the expense of the quality of the generated schedules. The purpose of this paper is to study a combination of exact and heuristic elements. The project to be considered is decomposed into subprojects, the related subproblems are optimally solved, and the solutions are concatenated. The solution strategy has been implemented and tested on the benchmark instances provided by ProGen. The numerical results show that the decomposition approach outperforms the truncated version of the branch-and-bound algorithm employed. On average, the quality of the overall solution depends on the size of the subproblems, and the quality of the solutions of the subproblems. Consequently the approach will benefit from the progress made in the development of exact solution procedures.