Strategies for project scheduling with alternative subgraphs under uncertainty: similar and dissimilar sets of schedules

In the resource-constrained project scheduling problem with alternative subgraphs (RCPSP-AS), we model alternative execution modes for work packages in the project. In contrast to the traditional RCPSP, the project network consists of different alternative work packages. To that purpose, the scheduling problem selects the best possible alternatives for the construction of the baseline schedule. On top of that, several back-up schedules are created in order to cope with unexpected changes along the project progress. In the presence of uncertainty, we can then switch between these alternative schedules at different decision moments in order to bring the project back on track. The alternative schedules are combined in a set of schedules that should be constructed by the project manager prior to project execution. We present a computational experiment to investigate the ability of using such a set of schedules in the presence of uncertainty during project execution. The experiments indicate that using a set of schedules outperforms the use of a single schedule, even when the uncertainty level is relatively low. The results also show that the composition of this schedule set is important. Therefore, a degree of schedule similarity is proposed to analyse this composition, and results show that a mix of similar and dissimilar schedules performs best. Finally, we show that the solution quality of each schedule in the set has an impact on the performance of the schedule switches given the project disruptions.