Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/130106
Title: Robust local search and its application to generating robust schedules
Authors: Lau, H.C.
Ou, T. 
Xiao, F.
Issue Date: 2007
Citation: Lau, H.C., Ou, T., Xiao, F. (2007). Robust local search and its application to generating robust schedules. ICAPS 2007, 17th International Conference on Automated Planning and Scheduling : 208-215. ScholarBank@NUS Repository.
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 denned 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. Copyright © 2007, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Source Title: ICAPS 2007, 17th International Conference on Automated Planning and Scheduling
URI: http://scholarbank.nus.edu.sg/handle/10635/130106
ISBN: 9781577353447
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.