A target-time-windows technique for project scheduling under uncertainty

We address the problem of determining the start times of activities in order to maximize the expected net present value of a project given precedence constraints. We assume that each activity has a random duration and profit with a known probability distribution. Most approaches generate either: a baseline schedule that is robust to uncertainty (using proactive approaches), or a policy that reacts to the revelation of uncertainty (using reactive approaches). We propose an integrated proactive-reactive technique that generates both a baseline time window for each activity’s start time, and a policy that indicates how the schedule should be adapted for each realization of uncertainty. The time window explicitly constrains the extent to which the realized start times vary. An important feature of our approach is that, once computed, it can easily be communicated and implemented in practice. Numerical experiments show that the objective value of the solutions generated by our technique can be within 4%, on average, of the optimal value obtained with perfect information, and up to 50% better when compared to an earliest-start policy. Moreover, the variability of activities’ start times can be 10 times smaller when compared to those generated by other policies. We solve an instance with 300 scenarios and 357 activities in 30 min, illustrating the scalability of our technique on a real-world problem that produces out-of-sample feasible solutions with a desired probability.