Please use this identifier to cite or link to this item:
|Title:||Robust local search and its application to generating robust schedules||Authors:||Lau, H.C.
|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.
checked on Feb 27, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.