Robust Local Search and Its Application to Generating Robust Schedules

摘要

In this paper, we propose an extended local search framework to solve combinatorial optimization problems with data uncertainty. Our approach represents a major departure from scenario-based or stochastic programming approaches often used to tackle uncertainty. Given a value 0 ＜ ε ≤ 1, we are interested to know what the robust objective value is, i.e. the optimal value if we allow an e chance of not meeting it, assuming that certain data values are defined on bounded random variables. We show how a standard local search or meta-heuristic routine can be extended to efficiently construct a decision rule with such guarantee, albeit heuristically. We demonstrate its practical applicability on the Resource Constrained Project Scheduling Problem with minimal and maximal time lags (RCPSP/max) taking into consideration activity duration uncertainty. Experiments show that, partial order schedules can be constructed that are robust in our sense without the need for a large planned horizon (due date), which improves upon the work proposed by Policella et al. 2004.