Nous serons accueillis dans les locaux de Polytech'Lille.
Programme de la journée
(9h - 16h30)
Accueil : 9h - 9h30
Exposés :
5 exposés sont prévus pour cette journée. En fonction
de l'heure du repas, qui reste à définir, nous aurons 3 exposés
le matin et deux l'après-midi ou inversement.
Prévoir entre 30 et 45 minutes par exposé.
- "Le
routage robuste sans conflits de chariots autoguidés Bi-directionnels
" Samia MAZA - IRCyN / Nantes
- "
Heuristiques, Métaheuristiques et systèmes de voisinage : Application
à des problèmes théoriques et industriels de type TSP
et ordonnancement" - Laurent DEROUSSI - LIMOS / Clermont-Ferrand
- "Planification des activités
de maintenance dans un contexte de télé-maintenance" - Alexei
IVANOV - LAB / Besançon
- "Conception métaheuristique
évolutionnaire pour l'ordonnancement flowshop multi-objectif" - Mathieu
Basseur - LIFL / Lille
- "Méta-heuristiques
pour le paramétrage automatique d'un logiciel d'ordonnancement industriel
" - El-Djillali Talbi, Laurent Geneste, Bernard Grabot - ENIT
- Discussions diverses
Résumés
Fin de la journée prévue vers 16h30.
Informations pratiques
Merci de nous prévenir de votre venue afin que nous puissions organiser
au mieux la journée (salles, repas, ...).
Plan d'accès,
Liste d'hotels
Organisation locale
E-G. Talbi - talbi@lifl.fr
C. Dhaenens-Flipo - dhaenens@lifl.fr
Résumés
1 -
Dans les systèmes manufacturiers actuels, les systèmes de transport
jouent un rôle important qui influe sur l'efficacité et la flexibilité
de ces systèmes. On s'intéresse au problème de routage
sans conflits de chariots autoguidés bi-directionnels. Ce sont des
véhicules automatisés, qui se déplacent en suivant des
circuits de guidage. Du fait de la bidirectionnalité des chariots
(ou des circuits), différents types de conflits et de blocages en
résultent. Plusieurs méthodes de routage de chariots sans conflits
ont été proposées, mais très peu sont celles
qui sont implémentables sur un système réel. En effet,
la majorité des méthodes proposées sont prédictives,
et du fait de la complexité du problème, il est difficile de
trouver un algorithme de routage performant en temps réel et qui soit
de complexité acceptable. On propose une méthode routage efficace
qui permet l'évitement de conflits en temps réel, et cela en
partant d'une méthode purement prédictive. On présentera
différents algorithmes qui permettent un routage robuste et dont la
complexité est acceptable. Notre méthode de routage présente
aussi l'avantage de s'appliquer à tout type de circuits.
2 -
L'objet de cette thèse est la proposition d'une méthodologie
permettant de construire des systèmes de voisinage performants pour
la résolution des problèmes d'optimisation combinatoire par
les méthodes approchées. L'objectif principal poursuivi tout
au long du mémoire est d'essayer de justifier en quoi notre démarche
de conception de systèmes de voisinage est intéressante. Ce
travail est conduit aussi bien sur le plan théorique que sur le plan
expérimental.
Sur le plan théorique, une caractérisation des systèmes
de voisinage par deux grandeurs mathématiques, la combinatoire et
la profondeur, est proposée. La combinatoire mesure la taille des
systèmes de voisinage, et la profondeur détermine la faculté
qu'un système de voisinage a de trouver des minima locaux de bonne
qualité. La force de ces outils réside dans leur mise en oeuvre,
qui se révèle très simple en comparaison de l'existant.
Sur le plan expérimental, notre démarche est mise en oeuvre
avec succès sur trois problèmes différents (le TSP,
le ATSP et le JSP avec transport), et en utilisant quatre métaheuristiques
différentes (l'algorithme du kangourou, le recuit simulé, la
méthode de recherche locale itérée et la méthode
hybride recuit / recherche locale), ce qui démontre sa flexibilité.
Pour le TSP, nous proposons une variante de l'algorithme du kangourou, bien
plus efficace que la version originale. Les résultats montrent que
cette variante trouve typiquement une solution optimale pour la majorités
des instances de la TSPLIB inférieures à 1500 villes.
L'approche de résolution utilisée pour résoudre le ATSP
consiste à transformer une instance asymétrique en une instance
symétrique qui possède le double de villes, puis à appliquer
la méthode précédente. La majorité des instances
de la TSPLIB (dont la taille n'excède pas 443 villes) sont résolues
en quelques secondes.
3 -
4 -
5 - Pendant longtemps, les responsables d'atelier ont attendu des outils
d'ordonnancement qu'ils déterminent rapidement et quelquefois de façon
interactive un ordonnancement réalisable. Cependant, de nombreuses
entreprises, soumises à une pression concurrentielle forte, exigent
actuellement d'obtenir un ordonnancement optimal relativement à un
ou plusieurs critères. La plupart des logiciels d'ordonnancement industriels
actuels utilisent une multitude de paramètres qui ont une influence
directe sur la qualité de l'ordonnancement. Régler ces paramètres
manuellement est une activité complexe, fastidieuse et requérant
une grande expertise, d'où l'intérêt d'automatiser cette
tache gràce à des méthodes d'optimisation combinatoire.
Nous décrirons ici un environnement dans lequel ont été
intégrées plusieurs méta-heuristiques visant à
assurer cette optimisation. Cet environnement permet de définir une
fonction objectif complexe sur la base d'une multitude de critères
élémentaires, et d'optimiser un ordonnancement en sélectionnant
puis en réglant les paramètres qui ont une influence sur les
résultat de l'ordonnancement. Cet environnement a été
testé sur le logiciel d'ordonnancement Ortems. Les premiers résultats
obtenus sur ces cas industriels (plusieurs dizaines de paramètres
à régler, plusieurs milliers de taches à ordonnancer
sur plusieurs centaines de machines) sont décrits.