Multi-criteria Scheduling: An Agent-based Approach for Expert Knowledge Integration

Abstract : In this work, we present an agent-based approach to multi-criteria combinatorial optimization. It allows to flexibly combine elementary heuristics that may be optimal for corresponding single-criterion problems. In the multi-criteria case a smart combination of such heuristics is supposed to efficiently approximate the whole Pareto-front of non-dominated trade-off solutions. We optimize an instance of the scheduling problem 1 |dj | sum Cj, Lmax and show that the modular building block architecture of our optimization model and the distribution of acting entities enable beneficial integration of problem specific expert knowledge. We present a universal mutation operator for combinatorial problem encodings that allows to construct certain solution strategies, such as advantageous sorting or known optimal sequencing procedures. In this way, it becomes possible to derive more complex heuristics from atomic local heuristics that are known to tackle fractions of the complete problem. We show that it is possible to approximate both single-criterionproblems such as Pm|dj| sum Uj as well as more challenging multi-criteria scheduling problems, like Pm || Cmax; sum Cj and Pm| dj | Cmax, sum Cj; sum Uj
Type de document :
Article dans une revue
Journal of Scheduling, Springer Verlag, 2011, 〈10.1007/s10951-011-0256-7〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00758224
Contributeur : Joachim Lepping <>
Soumis le : mercredi 28 novembre 2012 - 13:15:44
Dernière modification le : mercredi 11 avril 2018 - 01:51:41
Document(s) archivé(s) le : samedi 17 décembre 2016 - 16:06:57

Fichier

gl2010.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Christian Grimme, Joachim Lepping, Uwe Schwiegelshohn. Multi-criteria Scheduling: An Agent-based Approach for Expert Knowledge Integration. Journal of Scheduling, Springer Verlag, 2011, 〈10.1007/s10951-011-0256-7〉. 〈hal-00758224〉

Partager

Métriques

Consultations de la notice

298

Téléchargements de fichiers

664