Scheduling resource-constrained projects with alternative subgraphs to minimise cost

The resource-constrained project scheduling problem aims to schedule project activities given precedence relations and limited resources. This well-known scheduling problem has been extended into the so-called resource-constrained project scheduling problem with alternative subgraphs (RCPSP-AS). In this variant, the project network comprises multiple alternatives for executing work packages, which are smaller parts of the project, with the challenge of selecting and scheduling some of these alternatives such that the project makespan is minimised. This study introduces cost objectives and cumulative resource constraints in the RCPSP-AS, leading to the formulation of a new problem referred to as the RCPSP-ASC, where C signifies the incorporation of new cost objectives. To address this problem, novel priority rules are devised, and existing ones are adjusted. We present three empirical production case studies to underscore the relevance of these problem extensions in real-life settings. Moreover, a proposed mixed-integer mathematical model is validated using Gurobi and the computational efficiency of obtaining (near-)optimal solutions is investigated. Using existing project complexity indicators, we show that time- and resource-based priority rules are competitive for projects with low complexity. Moreover, the time-based priority rule is the best-performing rule for time minimisation and an additional combined heuristic is proposed for further improving the solutions. We also test the cost performance of a dynamic genetic algorithm (GA) from the existing literature on a subset of project instances for which the GA produces either low-quality or high-quality results in terms of time performance. Finally, an off-the-shelf constraint programming (CP) satisfiability (SAT) solver is implemented that shows improved results for the high-quality subset of instances compared to the dynamic GA and comparable results for the low-quality subset.