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.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/hal-00840357
Contributor : Marie-Eléonore Kessaci <>
Submitted on : Tuesday, July 2, 2013 - 3:35:56 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Document(s) archivé(s) le : Thursday, October 3, 2013 - 4:08:50 AM

File

exemple_ROADEF2012.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-00840357⟩

Share

Metrics

Record views

370

Files downloads

150