Robust Local Search for Solving RCPSP/max with Durational Uncertainty
Venue
Journal of Artificial Intelligence Research, vol. 43 (2012), pp. 43-86
Publication Year
2012
Authors
Na Fu, Hoong Chuin Lau, Pradeep Varakantha, Fei Xiao
BibTeX
Abstract
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.
