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.