TY - RPRT

T1 - A Multi-mode RCPSP with Stochastic Nonrenewable Resource Consumption

AU - Muller, Laurent Flindt

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

M3 - Report

T3 - DTU Management 2011

BT - A Multi-mode RCPSP with Stochastic Nonrenewable Resource Consumption

PB - DTU Management

CY - Kgs. Lyngby

ER -