A Theoretical Framework for Instance Complexity of the Resource-Constrained Project Scheduling Problem

Rob Van Eynde () and Mario Vanhoucke ()
Additional contact information
Rob Van Eynde: Faculty of Economics and Business Administration, Ghent University, Ghent 9000, Belgium
Mario Vanhoucke: Faculty of Economics and Business Administration, Ghent University, Ghent 9000, Belgium; Vlerick Business School, Ghent 9000, Belgium; UCL School of Management, University College London, London E14 5AA, United Kingdom

Mathematics of Operations Research, 2022, vol. 47, issue 4, 3156-3183

Abstract: The resource-constrained project scheduling problem (RCPSP) addresses the problem of constructing a schedule with minimum makespan for a set of activities, subject to precedence and resource constraints. Recent research introduced a data set with small instances that cannot be solved by the state-of-the-art algorithms, revealing a gap in our understanding of instance complexity. We propose a new theoretical framework for the instance complexity for the RCPSP, consecutively incorporating precedence constraints, resource constraints, and activity durations. Our approach contributes to the existing knowledge base in two ways. First, it is independent from solution algorithms, which enables generalisable conclusions. Second, the theoretical perspective enables a deeper understanding of the drivers of instance complexity. We evaluate the performance of our approach with a series of computational experiments. These show that our framework is a strong discriminator between easy and hard instances and explains a large fraction of CPU times of optimal solution algorithms.

Keywords: Primary: 06A07; 05C30; 90B35; resource-constrained project scheduling; instance complexity; partial orders; counting problems (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1237 (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:inm:ormoor:v:47:y:2022:i:4:p:3156-3183

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().