Network decomposition techniques for resource-constrained project scheduling

A Sprecher ()
Additional contact information
A Sprecher: Christian-Albrechts-Universität zu Kiel

Journal of the Operational Research Society, 2002, vol. 53, issue 4, 405-414

Abstract: 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.

Keywords: project management; scheduling; resource; allocation (search for similar items in EconPapers)
Date: 2002
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601308 Abstract (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:53:y:2002:i:4:d:10.1057_palgrave.jors.2601308

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601308

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().