In this paper, we investigate the problem of finding a robust baseline schedule for the project scheduling problem under uncertain process times. We assume that the probability distribution for the duration is unknown but an estimation together with an interval in which this time can vary is given. At most $ \Gamma $ of the jobs will deviate from the estimated time.
We present two solution approaches to this problem. The first approach treats the problem of determining earliest guaranteed finish times and can be solved in polynomial time by an extension of the critical path method. The second is a two-stage approach determining the baseline schedule in the first stage and an adaptation to the scenario in the second stage. We introduce a novel formulation and derive an exact algorithm and two heuristics. A computational study on benchmark instances reveals that the heuristics perform well on larger instances.
Citation
Arie M.C.A. Koster, Jenny Segschneider, Nicole Ventsch, (2024), Γ-robust optimization of project scheduling problems, Computers & Operations Research, 161, doi: https://doi.org/10.1016/j.cor.2023.106453.