Improving iterative repair strategies for scheduling with the SVM

Autor(en): Gersmann, K
Hammer, B
Stichwörter: ALGORITHM; Computer Science; Computer Science, Artificial Intelligence; RCPSP; reinforcement learning; RESOURCE; ROUT algorithm; scheduling; SEARCH; SVM
Erscheinungsdatum: 2005
Herausgeber: ELSEVIER
Volumen: 63
Startseite: 271
Seitenende: 292
The resource constraint project scheduling problem (RCPSP) is an NP-hard benchmark problem in scheduling which takes into account the limitation of resources' availabilities in real life production processes and subsumes open-shop, job-shop, and flow-shop scheduling as special cases. We present here an application of machine learning to adapt simple greedy strategies for the RCPSP. Iterative repair steps are applied to an initial schedule which neglects resource constraints. The rout-algorithm of reinforcement learning is used to learn an appropriate value function which guides the search. We propose three different ways to define the value function and we use the support vector machine (SVM) for its approximation. The specific properties of the SVM allow to reduce the size of the training set and SVM shows very good generalization behavior also after short training. We compare the learned strategies to the initial greedy strategy for different benchmark instances of the RCPSP. (C) 2004 Elsevier B.V. All rights reserved.
11th European Symposium on Artificial Neural Networks (ESANN), Brugge, BELGIUM, APR, 2003
ISSN: 09252312
DOI: 10.1016/j.neucom.2004.01.193

Show full item record

Page view(s)

Last Week
Last month
checked on Mar 4, 2024

Google ScholarTM