Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

9-2007

Abstract

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 chance of not meeting it, assuming that certain data values are defined on bounded random variables. We show how a standard local search or metaheuristic 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.

Discipline

Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering

Publication

International Conference on Automated Planning and Scheduling (ICAPS)

Publisher

AAAI

Additional URL

https://www.aaai.org/Papers/ICAPS/2007/ICAPS07-027.pdf

Download

Share

COinS