Robust Local Search for Solving RCPSP/max with Durational Uncertainty
  Scheduling problems in manufacturing, logistics and project management have
frequently been modeled using the framework of Resource Constrained Project
Scheduling Problems with minimum and maximum time lags (RCPSP/max). Due to the
importance of these problems, providing scalable solution schedules for
RCPSP/max problems is a topic of extensive research. However, all existing
methods for solving RCPSP/max assume that durations of activities are known
with certainty, an assumption that does not hold in real world scheduling
problems where unexpected external events such as manpower availability,
weather changes, etc. lead to delays or advances in completion of activities.
Thus, in this paper, our focus is on providing a scalable method for solving
RCPSP/max problems with durational uncertainty. To that end, we introduce the
robust local search method consisting of three key ideas: (a) Introducing and
studying the properties of two decision rule approximations used to compute
start times of activities with respect to dynamic realizations of the
durational uncertainty; (b) Deriving the expression for robust makespan of an
execution strategy based on decision rule approximations; and (c) A robust
local search mechanism to efficiently compute activity execution strategies
that are robust against durational uncertainty. Furthermore, we also provide
enhancements to local search that exploit temporal dependencies between
activities. Our experimental results illustrate that robust local search is
able to provide robust execution strategies efficiently.
