Loading...
Going to the core of hard resource-constrained project scheduling instances
Coelho, José Vanhoucke, Mario
Coelho, José
Vanhoucke, Mario
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2020
Journal
Computers and Operations Research
Book
Publication Volume
121
Publication Issue
September
Publication Begin page
Publication End page
Publication NUmber of pages
Collections
Abstract
The resource-constrained project scheduling problem (RCPSP) is one of the most studied problems in the project scheduling literature, and aims at constructing a project schedule with a minimum makespan that satisfies both the precedence relations of the network and the limited availability of the renewable resources. The problem has attracted attention due to its NP hardness status, and different algorithms have been proposed that solve a wide variety of RCPSP instances to optimality or near-optimality. In this paper, we analyse the hardness of this problem from an experimental point-of-view by testing different algorithms on a huge set of existing instances and detect which ones are difficult to solve. To that purpose, we propose a three-phased approach that makes use of five elementary blocks, well-performing algorithms and a huge amount of computational power to transform easy RCPSP instances into very hard ones. The purpose of this study is to create insight and understanding into what makes an RCPSP instance hard, and propose a new dataset that consists of a small set of instances that are impossible to solve with the algorithms currently existing in the literature. These instances should be as small as possible in terms of number of activities and resources, and should be as diverse as possible in terms of network structure and resource strictness. Such a dataset should enable researchers to focus their attention on the development of radically new algorithms to solve the RCPSP rather than gradually improving current algorithms that can solve the existing RCPSP instances only slightly better.
Research Projects
Organizational Units
Journal Issue
Keywords
Resource-Constrained Project Scheduling, Project Networks, Resource Constraints