LSSPER: Solving the Resource-Constrained Project Scheduling Problem with Large Neighbourhood Search

Mireille Palpant, Christian Artigues and Philippe Michelon

Annals of Operations Research, 2004, vol. 131, issue 1, 237-257

Abstract: This paper presents the Local Search with SubProblem Exact Resolution (LSSPER) method based on large neighbourhood search for solving the resource-constrained project scheduling problem (RCPSP). At each step of the method, a subpart of the current solution is fixed while the other part defines a subproblem solved externally by a heuristic or an exact solution approach (using either constraint programming techniques or mathematical programming techniques). Hence, the method can be seen as a hybrid scheme. The key point of the method deals with the choice of the subproblem to be optimized. In this paper, we investigate the application of the method to the RCPSP. Several strategies for generating the subproblem are proposed. In order to evaluate these strategies, and, also, to compare the whole method with current state-of-the-art heuristics, extensive numerical experiments have been performed. The proposed method appears to be very efficient. Copyright Kluwer Academic Publishers 2004

Keywords: resource-constrained project scheduling problem; large neighbourhood search (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://hdl.handle.net/10.1023/B:ANOR.0000039521.26237.62 (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:131:y:2004:i:1:p:237-257:10.1023/b:anor.0000039521.26237.62

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

DOI: 10.1023/B:ANOR.0000039521.26237.62

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 ().