Network decomposition techniques for resource-constrained project scheduling

Arno Sprecher

No 505, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

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.

Keywords: Project Scheduling; Resource Constraints; Branch-and-Bound; Decomposition; Computational Results (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147593/1/manuskript_505.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:zbw:cauman:505

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().