Please use this identifier to cite or link to this item: http://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.

Page view(s)

13
checked on Sep 21, 2018

Google ScholarTM

Check


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