Conception de recherche locale en présence de neutralité

Résumé : Le problème d'ordonnancement de type Flowshop de permutation (FSP) est un problème d'optimisation combinatoire (COP) très étudié dans la littérature. Pour les instances de Taillard [4], certains travaux font mention de la présence de nombreuses solutions ayant la même qualité. Les recherches locales utilisent un opérateur de voisinage pour se déplacer d'une solution vers un de ses voisins. Lorsque deux solutions voisines ont la même qualité, on parle de neutralité. Le FSP semble présenter une telle caractéristique. Aussi certaines questions se posent naturellement : Comment caractériser la neutralité du FSP ? La neutralité est-elle utilisée pour résoudre le FSP ? Pour répondre à ces questions, nous commençons par analyser la neutralité des instances de Taillard du FSP à travers une analyse de paysage. Puis, nous proposons d'étudier les performances de trois algorithmes de recherche locale, dont deux utilisent les caractéristiques de neutralité du problème.
Type de document :
Communication dans un congrès
ROADEF 2012 : 13e congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Apr 2012, Angers, France. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00840357
Contributeur : Marie-Eléonore Kessaci <>
Soumis le : mardi 2 juillet 2013 - 15:35:56
Dernière modification le : samedi 16 janvier 2016 - 01:09:38
Document(s) archivé(s) le : jeudi 3 octobre 2013 - 04:08:50

Fichier

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

Identifiants

  • HAL Id : hal-00840357, version 1

Citation

Marie-Eleonore Marmion, Clarisse Dhaenens, Laetitia Jourdan, Arnaud Liefooghe, Sébastien Verel. Conception de recherche locale en présence de neutralité. ROADEF 2012 : 13e congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Apr 2012, Angers, France. 2012. <hal-00840357>

Partager

Métriques

Consultations de
la notice

260

Téléchargements du document

122