Network decomposition techniques for resource-constrained project scheduling

Network decomposition techniques for resource-constrained project scheduling

0.00 Avg rating0 Votes
Article ID: iaor20023222
Country: United Kingdom
Volume: 53
Issue: 4
Start Page Number: 405
End Page Number: 414
Publication Date: Apr 2002
Journal: Journal of the Operational Research Society
Authors:
Keywords: project management
Abstract:

The purpose of this paper is to study an obvious but unexplored approach for scheduling resource-constrained projects. The approach combines elements of heuristic and exact solution procedures. The project considered is decomposed into subprojects, the subproblems are optimally solved, and the solutions are concatenated. The strategy is tested on the benchmark instances of ProGeu. Several of the best known makespans collected in PSPLIB are improved. The algorithm has reduced more best known makespans than the state-of-the-art heuristic for medium-sized projects. 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 on the quality of the solutions of the subproblems – if approximately solved. Consequently, on the one hand, the approach benefits from the progress made in the development of exact solution procedures. But, on the other hand, the results question the rigid construction of schedules by conventional algorithms relying on extensions of partial schedules, and thus provide fundamental insights into the development of exact solution procedures.

Reviews

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