A decomposition-based stochastic programming approach for the project scheduling problem under time/cost trade-off settings and uncertain durations

Resource allocation in project networks allows for the control of the processing time of an activity under time-cost tradeoff settings. In practice, project decisions are made in advance when activity durations are still highly uncertain. Given an activity-on-node project network and a set of execution modes for each activity, we consider the problem of deciding how and when to execute each activity to minimize project completion time or total cost with respect to captured activity durations. The inherent stochasticity is represented using a set of discrete scenarios in which each scenario is associated with a probability of occurrence and a realization of activity durations. In this paper, we propose a path-based two-stage stochastic integer programming approach in which the execution modes are determined in the first stage while the second stage performs activity scheduling according to the realizations of activity durations, hence, providing flexibility in the scheduling process at subsequent stages. The solution methodology is based on a decomposition algorithm which has been implemented and widely tested using a large number of test instances of varying size and uncertainty. The reported computational results demonstrate that the proposed algorithm converges fast to the optimal solution and present the benefits of using the stochastic model as opposed to the traditional deterministic model that considers only expected values of activity durations. (C) 2010 Elsevier Ltd. All rights reserved.