A Multi-mode RCPSP with Stochastic Nonrenewable Resource Consumption

Many processes within production scheduling and project management involve the scheduling of a number of activities, each activity having a certain duration and requiring a certain amount of limited resources. The duration and resource requirements of activities are com- monly the result of estimations, and thus generally subject to uncertainty. If this uncertainty is not taken into account the resulting schedules may not be robust in the sense that, when executed, the uncertainty may cause the schedules to take longer than expected, consume more resources, or be outright infeasible. We propose a new variant of the Multi-mode Resource-Constrained Project Scheduling Problem, where the nonrenewable resource requirements of each mode is given by a Gaussian distribution, and the nonrenewable resource constraints must be satisfied with a certain probability p. Such constraints are also known as chance constraints. We present a Conic Quadratic Integer Program model of the problem, and describe and experiment with a branch-and-cut algorithm for solving the problem. In each node of the branch-and-bound tree, the branching decisions are propagated in order to remove variables from the problem, and thus improve bounds. In addition we experiment with cutting on the conic quadratic resource constraints. Computational experiments show that the branch-and-cut algorithm outperforms CPLEX 12.1. We finally examine the “cost of uncertainty” by investigating the relation between values of p, the makespan, and the solution time.