Algorithms for deterministic and stochastic project scheduling problems

Abstract

This thesis develops modelling and algorithmic approaches for two Project Scheduling Problems. We first consider the Discrete Time-Cost Tradeoff Problem (DTCTP) which involves determining an execution mode for each project activity associated to a time-cost pair so that either deadline or budget restrictions are satisfied. A new, path-based formulation is proposed which is subsequently solved using an exact cutting plane algorithm enhanced with speed-up techniques. Extensive computational results demonstrate that the algorithm can optimally solve some of the hardest and largest instances in the literature. By introducing uncertainty, we construct the stochastic DTCTP with static modes, under a Two-Stage Stochastic Programming approach; the first-stage determines the modes while the second performs activity scheduling according to observed outcomes. The formulation is solved via an exact decomposition-based algorithm, which is shown to converge fast to optimality through extensive experimentation; the benefits of using stochastic models over traditional deterministic approaches which only consider expected values are also confirmed. A Multi-Stage formulation for the stochastic dynamic DTCTP is also proposed, which, to the best of our knowledge, is the first in the field. This allows adjusting the mode decisions according to observations and its complexity is due to the presence of decision-dependent uncertainty as the decisions influence the time discovery of the random variables. A Branch-and-Bound methodology is developed using lower and upper bounds and dominance rules and its generic features are discussed. Our extensive computational study highlights the value of flexibility associated to dynamic models and tests the performance of the proposed approaches in solving computationally difficult, non-standard, stochastic programs. The final part of this thesis focuses on the Stochastic Resource-Constrained Project Scheduling Problem, which involves scheduling project activities under limited resources and uncertain durations. A solution methodology is presented, implemented and computationally evaluated using randomly generated test instances. Computational results are reported.