Various extensions in resource-constrained project scheduling with alternative subgraphs

Abstract

In this research, we present several extensions for the resource-constrained project scheduling problem with alternative subgraphs (RCPSP-AS). First of all, we investigate more complex variants of the alternative project structure. More precisely, we consider nested alterative subgraphs, linked alternative branches, multiple selection, caused and closed choices, and split choices. Secondly, we introduce non-renewable resources in the RCPSP-AS in order to implicitly avoid certain combinations of alternatives given a limited availability of this resource over the complete project horizon. We formulate both the basic RCPSP-AS and its extensions as an ILP model and solve it using Gurobi. The computational experiments are conducted on a large set of artificial project instances as well as three case studies. The results show the impact of the different extensions on the project makespan and the computational complexity. We observe that combinations of the proposed extensions might imply complex alternative project structures, resulting in an increasing computational complexity or even infeasible solutions. The analysis of the three case studies shows that it is hard to find feasible solutions with a small time limit or optimal solutions with a larger time limit for projects with a realistic size in terms of the number of activities or alternatives.

Keywords:

• Project scheduling
• resource constraints
• alternative subgraphs
• integer formulation
• case studies

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the Nationale Bank van België (NBB) and the Bijzonder Onderzoeksfonds (BOF) under grant BOFGOA021.

Notes on contributors

Tom Servranckx

Tom Servranckx obtained his PhD in 2020 for his research in the domain of project scheduling. In his dissertation, he introduced and investigated the RCPSP with alternative subgraphs (RCPSP-AS), proposed a solution approach for the RCPSP-AS and validated the approach on real-life cases. In addition, he also studied the integration of the static scheduling phase and the dynamic project control phase. More precisely, he investigated how back-up schedules can be used by project managers to deal with uncertainty during project execution.

José Coelho

José Pedro Fernandes da Silva Coelho is graduated in Computer Science Engineering, and has a master degree on Operational Research and System Engineering, and a PhD in 2004 on System Engineering, in Technical Lisbon University. He is an Assistant Professor at the Portuguese Open University, Department of Sciences and Technology, and a researcher in Institute for Systems and Computer Engineering, Technology and Science (INESC TEC), in the center of Information Systems and Computer Graphics (CSIG). He has published a total of 13 papers in Q1 journals: 9 papers in Computer Science, of which 8 are also in Management Science and Operations Research, two papers in Management of Technology and Innovation, one paper Computer Science Applications, and another paper in E-learning. His main research field is on operational research, on project management and scheduling, but he is also interested in meta heuristics, eLearning, and art and technology.

Mario Vanhoucke

Mario Vanhoucke is Full Professor of Business Management and Operations Research at Ghent University (Belgium), Vlerick Business School (Belgium and China) and UCL School of Management at University College London (UK). He is a lecturer in Project Management, Business Statistics, Decision Sciences for Business and Applied Operations Research. His main research interest lies in the integration of project scheduling, risk management and project control using algorithmic modelling and optimisation. He is an advisor for +10 PhD projects, has published +100 papers in various international publications and is the author of 4 project management books published by Springer, the business novel ‘The data-driven project manager’ and 4 online books. Mario Vanhoucke has been the founding member and Director of the EVM Europe Association (2009–2017). He also has – in collaboration with the company OR-AS – released a commercial project management software tool ProTrack 3.0 as well as a research PM software engine P2 Engine.