Problem space search algorithms for resource-constrained project scheduling

Kedar Naphade, S. David Wu and Robert Storer

Annals of Operations Research, 1997, vol. 70, issue 0, 307-326

Abstract: The Resource-Constrained Project Scheduling (RCPS) problem is a well known and challenging combinatorial optimization problem. It is a generalization of the Job Shop Scheduling problem and thus is NP-hard in the strong sense. Problem Space Search is a local search "metaheuristic" which has been shown to be effective for a variety of combinatorial optimization problems including Job Shop Scheduling. In this paper, we propose two problem space search heuristics for the RCPS problem. These heuristics are tested through intensive computational experiments on a 480-instance RCPS data set recently generated by Kolisch et al. [12]. Using this data set we compare our heuristics with a branch-and-bound algorithm developed by Demuelemeester and Herreolen [9]. The results produced by the heuristics are extremely encouraging, showing comparable performance to the branch-and-bound algorithm. Copyright Kluwer Academic Publishers 1997

Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018982423325 (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:spr:annopr:v:70:y:1997:i:0:p:307-326:10.1023/a:1018982423325

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018982423325

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().