Friday 28
Scheduling, planning and production management
Zakaria HAMMOUDAN
› 15:00 - 15:20 (20min)
› Bât. E - TD 39
limited discrepancy search pour le problème d'ordonnancement de rendez-vous
Agnès Le Roux  1, 2@  , Odile Bellenguez-Morineau  2, 1@  , Christelle Guéret  3@  
1 : École nationale supérieure des Mines de Nantes  -  Website
Groupe des Écoles des Mines (GEM), École Nationale Supérieure des Mines - Nantes
La Chantrerie - 4, rue Alfred Kastler - BP 20722 - 44307 Nantes cedex 3 -  France
2 : Institut de Recherche en Communications et en Cybernétique de Nantes  (IRCCyN)  -  Website
École Nationale Supérieure des Mines - Nantes, Ecole Centrale de Nantes, PRES Université Nantes Angers Le Mans [UNAM], CNRS : UMR6597, Ecole Polytechnique de l'Université de Nantes
1, rue de la Noë BP92101 44321 Nantes Cedex 03 -  France
3 : Laboratoire angevins de recherche en ingénierie des systèmes (EA 7315)  (LARIS)
LUNAM Université, Université d’Angers
4 boulevard lavoisier 49016 Angers -  France

Le speed-dating est un mode de rencontres rapides amicales ou amoureuses. Idéalement, lors de ces soirées, un nombre égal de femmes et d'hommes se rencontrent sur des créneaux de sept minutes. Toutes les rencontres qui s'effectuent sur le même créneau commencent et finissent au même moment. À la fin de chaque rencontre, les hommes se déplacent de manière à rencontrer une nouvelle personne, alors que les femmes restent assises. Il arrive souvent que les deux populations soient de tailles différentes ou que certaines rencontres soient interdites car les participants se sont déjà rencontrés lors d'une soirée précédente. De plus, certains participants arrivent en retard. Tous ces événements perturbateurs engendrent des attentes pour les participants ne pouvant ainsi pas enchaîner toutes leurs rencontres. L'objectif considéré ici est la minimisation du nombre maximum d'attentes des participants. Nous nous intéressons à la version statique du problème dans laquelle toutes les données (retards des participants, rencontres interdites) sont connues à l'avance. Nous avons démontré que le problème général de speed-dating est NP-difficile au sens fort [2]. Pour résoudre ce problème, nous proposons de développer une "limited discrepancy search" [1]. Le schéma et la stratégie de branchement sont basés sur une heuristique de liste donnant priorité aux rendez-vous des participants qui ont le plus de créneaux d'attente pour la solution partiellement instanciée. Cette heuristique nous a déjà donné d'assez bons résultats. Afin d'optimiser le parcours de l'arbre de recherche, nous exploitons des propriétés de symétrie du problème permettant d'éviter la création de nœuds dominés ou redondants. Par exemple, on introduit une règle de dominance visant à casser les symétries entre les participants possédant les mêmes caractéristiques (même date d'arrivée et même liste de rencontres). Les résultats obtenus par cette méthode sont comparés avec ceux obtenus par une approche exacte (PLNE).

References

[1] W.D. Harvey and M.L. Ginsberg. Limited discrepancy search. In Proceedings of the International

Joint Conference on Artificial Intelligence (IJCAI95), pages 607{613, aug. 1995.

[2] A. Le Roux, O. Bellenguez-Morineau, C. Guéret, and D. Prot. Complexity of speed-dating problems. Technical report of the École des Mines de Nantes, 12/1/AUTO, 2012.


Online user: 2