Various extensions in resource-constrained project scheduling with alternative subgraphs

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.