Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/147593 
Authors: 
Year of Publication: 
1999
Series/Report no.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel No. 505
Publisher: 
Universität Kiel, Institut für Betriebswirtschaftslehre, Kiel
Abstract: 
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.
Subjects: 
Project Scheduling
Resource Constraints
Branch-and-Bound
Decomposition
Computational Results
Document Type: 
Working Paper
Document Version: 
Digitized Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.