Soutenance mémoire
Parmi les thématiques d’intérêt majeur en optimisation, figurent les problèmes d’ordonnancement qui répondent à des besoins essentiels d’organisation et de réduction des coûts pour les entreprises. De manière générale, les problèmes d’ordonnancement traitent de l’attribution de dates d’exécution à des tâches nécessitant des ressources limitées sous des contraintes spécifiques. Le but est de positionner l’ensemble de ces tâches de manière à leur allouer les ressources nécessaires et respecter toutes les contraintes en optimisant un (ou des) objectif(s) fixé(s). Les applications sont nombreuses notamment dans les domaines de l’industrie, de l’informatique ou la gestion de projets.
Assez récemment, un nouveau type de problèmes d’ordonnancement est apparu qui a pour but de planifier des rendez-vous en tête-à-tête. Il s’agit d’organiser en parallèle des rendez-vous de courte durée prédéterminée réunissant deux participants. Ce genre de problème se rencontre dans diverses applications telles que des forums pour l’emploi où des recruteurs rencontrent des demandeurs d’emploi, des salons professionnels organisant des rendez-vous d’affaires, des réunions parents-professeurs ou des soirées de speed-dating. La planification de tels événements à la main est souvent une tâche longue et fastidieuse en raison du grand nombre de participants et des nombreuses contraintes à respecter. Il faut par ailleurs chercher à satisfaire les participants au mieux dans le nombre et le choix des rendez-vous planifiés car les rencontres peuvent avoir de gros enjeux pour les participants (signature de contrats, recherche de partenariats, vente de produits, recherche de travail).
Définition des problèmes d’ordonnancement de rendez-vous en tête-à-tête
Dans un problème d’ordonnancement de rendez-vous en tête-à-tête, différents participants souhaitent se rencontrer au cours de rendez-vous de courte durée. Les contraintes sont les suivantes :
• deux participants se rencontrent au plus une fois ;
• une rencontre implique exactement deux participants ;
• deux participants ne peuvent pas faire plus d’une rencontre à la fois.
Les rencontres s’effectuent en parallèle et en général ont lieu au même endroit.
Selon le type de problème, plusieurs spécificités sont prises en compte. Les participants peuvent se scinder en deux populations distinctes. Dans ce cas, une rencontre ne se fait qu’entre deux participants de populations différentes. Dans le cas où la population est homogène, il n’y a pas de restrictions sur les rencontres admissibles. Cependant, dans tous les cas, des rencontres peuvent être interdites si des participants n’ont pas d’intérêt à se rencontrer. On peut également envisager de donner une priorité aux rencontres les plus intéressantes. Certains participants peuvent aussi arriver en retard ou indiquer des créneaux d’indisponibilité pendant lesquels ils ne peuvent pas effectuer de rencontres. On peut envisager la possibilité de créneaux de durée non unitaire si certains rendez-vous nécessitent plus de temps que d’autres. Dans certains cas, le lieu des rendez-vous est trop étendu pour que le déplacement entre deux rencontres quelconques se fasse rapidement. Il est alors possible d’ajouter des contraintes limitant les déplacements entre les rendez-vous ou allouant un temps spécifique à ces déplacements. Selon le problème étudié, l’objectif peut être de maximiser le nombre de rencontres sur un nombre de créneaux fixés. On peut chercher à maximiser la satisfaction des participants en donnant priorité aux rencontres qu’ils demandent en premier. On peut également souhaiter minimiser les créneaux d’attente des participants.
Dans cette thèse, nous nous intéressons à un cas particulier de problème d’ordonnancement de rendez-vous en tête-tête dont l’application est l’organisation de soirées de speed-dating. Nos travaux sont menés en collaboration avec la société lespeeddating.com qui organise des soirées de speed-dating.
Caractéristiques du problème de speed-dating
Une soirée de speed-dating organisée par lespeeddating.com permet à des hommes et des femmes de se rencontrer durant de courts créneaux. Chaque créneau horaire a une durée de 7 min. On a, dans ce cas, des contraintes spécifiques :
• certaines rencontres sont interdites si deux participants se sont déjà rencontrés lors d’une soirée précédente ;
• certains participants arrivent en retard et ne sont donc pas disponibles durant les premiers créneaux de la soirée.
La soirée se termine lorsque toutes les rencontres possibles ont eu lieu. L’objectif est de satisfaire au mieux les participants en minimisant le plus grand nombre de créneaux d’attente. On distingue deux types de problèmes de speed-dating :
• les problèmes de type dynamique dans lesquels on ne connaît la date d’arrivée des participants qu’au fur et à mesure de la soirée ;
• les problèmes de type statique dans lesquels on considère que l’on connaît tous les paramètres de la soirée à l’avance, en particulier les dates d’arrivée de tous les participants.
Problèmes d’ordonnancement de rendez-vous en tête-à-tête
La littérature compte plusieurs cas d’étude de problèmes d’ordonnancement en tête-à-tête même si ceux-ci ne sont pas classifiés. Nous référençons des articles qui étudient différents cas de ce type de problèmes et montrons comment ils peuvent entrer dans notre classification. Nous présentons leur complexité lorsqu’elle est connue et les approches qui ont été employées pour les résoudre.
Dans (Rinaldi et Serafini, 2007), les auteurs étudient un problème d’ordonnancement de rendez-vous en tête-à-tête entre environ 60 parents et 30 professeurs. Une liste de rencontres est fixée à l’avance, celle-ci est élaborée à partir du choix de rencontres des parents. Les objectifs sont de minimiser la durée de l’événement et les temps d’attente des parents, ceux-ci sont traités de manière lexicographique. Si l’on reprend les notations que nous avons proposées, ce problème s’écrit 1-1MS|(U ∪ V, E)|Cmax, γ où γ est un objectif de minimisation des temps d’attente des parents uniquement. À noter que cet objectif supplémentaire n’est pas un objectif Lmax car les parents n’ont pas de date d’échéance prédéterminée et que leur date d’arrivée n’est prise en compte qu’à travers la date fixée pour le premier rendez-vous. Les créneaux considérés comme attente sont les créneaux sans rencontre entre le premier rendez-vous et le dernier. Les auteurs proposent une extension de ce problème dans lequel certaines rencontres peuvent durer deux fois le temps de base. Ce problème d’ordonnancement de rencontres parents–professeurs est N P-difficile quelle que soit la durée des rencontres. Ce résultat provient d’une réduction du problème N P-difficile d’open shop avec contraintes de non-attentes : O|no-wait, pij ∈ {0, 1}|Cmax. Les auteurs résolvent ce problème de manière approchée en deux phases. Dans un premier temps, il résolvent le problème de minimisation de fin de soirée de manière exacte par recherches successives de couplages maximums dans un graphe biparti. Dans un second temps, ils minimisent les attentes des parents par une recherche locale en échangeant deux rencontres d’un parent ou deux rencontres d’un professeur.
Dans (Ernst et al., 2003), les auteurs implémentent un outil d’organisation de rencontres en tête-à-tête lors de salons commerciaux pour la promotion du tourisme australien. Environ 600 vendeurs (groupes hôteliers, voyagistes. . .) et 700 acheteurs (agences de voyages. . .) se rencontrent. Chaque participant choisit une liste de participants de l’autre type triée par ordre de préférence. Les organisateurs en déduisent un indice de satisfaction pour chaque rencontre. L’objectif est de maximiser le nombre de rencontres ainsi que la satisfaction totale des participants. Chaque vendeur est affecté à un lieu fixé et étant donnée la taille de l’événement, il n’est pas possible pour un acheteur de se déplacer d’un vendeur à n’importe quel autre en trois minutes (temps imparti entre deux créneaux de rencontres). Les auteurs ont donc ajouté des contraintes de déplacements qui obligent deux rencontres successives à être positionnées suffisamment proches l’une de l’autre. Ce problème est un cas particulier de 1-1MS|(U ∪ V, E)|γ1, γ2 avec des contraintes limitant les déplacements et où les objectifs γ1 et γ2 sont respectivement la maximisation du nombre de rencontres et la maximisation de la somme des indices de satisfaction des rencontres planifiées. Ce problème, sans les contraintes de déplacement, est similaire à un sous-problème d’affectation en trois dimensions (three-dimensional assignment problem) polynomial car la satisfaction engendrée par une rencontre ne dépend pas de l’heure à laquelle est affectée la rencontre. Les auteurs résolvent ce problème séquentiellement : pour chaque créneau de rencontres, sont déterminées les rencontres possibles (qui n’ont pas déjà été affectées et réalisables en terme de déplacements) puis le problème d’affectation (problème de couplage maximum de poids maximal dans un graphe biparti) induit par ces rencontres est résolu.
Dans (Huang et al., 2012), les auteurs développent un programme de planification de “business dating”. Ce problème est le même que le problème précédent sans les contraintes de déplacement. Des vendeurs et des acheteurs se rencontrent. Le nombre de participants est variable, des applications réelles testées par les auteurs contiennent entre 30 et 42 vendeurs et de 46 à 84 acheteurs. De manière préliminaire, chacun des participants fournit à l’organisateur une liste des rencontres qu’il souhaite effectuer par ordre de priorité dont sont déduits des indices de préférence pour chaque rencontre. L’objectif est également de maximiser le nombre de rencontres et de maximiser la satisfaction totale des participants. Ce problème se note 1-1MS|(U ∪ V, E)|γ1, γ2 avec γ1 et γ2 définis de la même manière que précédemment. Bien qu’un algorithme polynomial soit connu pour ce problème, les auteurs utilisent une approche heuristique plus facile à implémenter. De la même manière que dans (Ernst et al., 2003), ils résolvent successivement des problèmes d’affectation pour chaque créneau de rencontres.
Dans (Gandibleux et al., 2006) and (Guéret et al., 2009), les auteurs s’intéressent à un problème d’ordonnancement de rencontres dans le cadre d’une bourse d’échanges de technologies. Dans ce type d’événement, entre 100 et 200 participants (académiques et industriels) se rencontrent. Chaque participant fournit une liste de priorités sur les rencontres qu’il souhaite effectuer. De nombreuses contraintes additionnelles sont prises en compte. Notamment, il y a un nombre limite de rencontres pouvant avoir lieu en même temps et chaque participant a un nombre maximal de rencontres consécutives qu’il peut effectuer. Plusieurs objectifs sont considérés : maximiser le nombre de rencontres planifiées, maximiser les premiers choix des participants, minimiser le coût de location des salles et minimiser la distance totale de trajet entre les rencontres entre autres. Ce problème est un cas particulier de 1-1MS|(U ∪ V, E)|γ avec de nombreuses contraintes additionnelles et où γ agrège plusieurs objectifs. Les auteurs de (Gandibleux et al., 2006) montrent que ce problème est une généralisation du problème N P-difficile de set-packing. Ils modélisent ce problème à l’aide d’un programme linéaire en nombres entiers. Les auteurs de (Guéret et al., 2009) proposent de résoudre ce problème en trois phases : maximiser le nombre de rencontres planifiées (par PLNE), minimiser le coût des salles louées (algorithme de programmation dynamique) et minimiser les déplacements entre les tables (recherche taboue).
Dans (Bartholdi et McCroan, 1990), les auteurs développent une application pour planifier des entretiens d’embauche entre des étudiants et des entreprises dans le domaine du droit dans un forum pour l’emploi. Entre 25 et 50 entreprises et 100 à 200 étudiants participent au “Southern Public Interest Job Fair” chaque année, événement se tenant pendant deux jours. Les étudiants et les recruteurs déterminent à l’avance les rencontres qu’il souhaitent effectuer. Le nombre de créneaux disponibles pour les entretiens étant limité à 23, chacun des participants peut former une liste de 23 rencontres souhaitées au maximum. L’application ordonnance l’ensemble des rencontres (demandées par les deux parties) avec pour objectif de créer des plannings compacts à la fois pour les étudiants et les recruteurs. Le problème de base se modélise comme un problème de coloration d’arêtes dans un graphe biparti. Il est toujours possible de planifier toutes les rencontres demandées d’après le théorème de König (König, 1916). Ce problème est polynomial sans recherche de compacité des plannings. Les auteurs résolvent ce problème par l’affectation séquentielle des rencontres ; si dans ce processus, une infaisabilité est détectée, la solution est réparée par une recherche de chemin augmentant dans le graphe biparti. Ce problème se note 1-1MS|(U ∪ V, E)|γ où γ est un objectif de compacité des plannings des participants (cependant, cet objectif n’est pas explicité dans la modélisation proposée).
|
Table des matières
INTRODUCTION
I Présentation du problème et état de l’art
1 Présentation du problème
1.1 Définition des problèmes d’ordonnancement de rendez-vous en tête-à-tête
1.2 Caractéristiques du problème de speed-dating
1.3 Notations
1.3.1 Données
1.3.2 Variables
1.3.3 Notations à trois champs α|β|γ
1.3.4 Représentation d’une solution
1.4 Génération d’instances
1.5 Conclusion
2 État de l’art
2.1 Introduction
2.2 Problèmes d’ordonnancement de rendez-vous en tête-à-tête
2.3 Autres problèmes de rencontres
2.4 Problèmes proches du problème de speed-dating
2.4.1 Problème d’open shop
2.4.2 Problème d’emploi du temps
2.4.3 Problèmes d’ordonnancement par fournées avec incompatibilités entre les jobs
2.4.4 Coloration d’arêtes d’un graphe par intervalles
2.4.5 Problème de multiflot entier
2.5 Conclusion
II Résultats de complexité
3 Résultats généraux de complexité
3.1 Introduction
3.2 Réductions évidentes
3.2.1 Réductions dans le cas général
3.2.2 Réductions dans le cas où des rencontres sont interdites
3.2.3 Rôles symétriques des femmes et des hommes
3.3 Conclusion
4 Problèmes polynomiaux
4.1 Introduction
4.2 Cas sans rencontres interdites et sans retards des participants
4.3 Cas sans rencontres interdites avec retards pour la population la moins nombreuse
4.4 Cas sans rencontres interdites et avec retards pour une population
4.5 Cas particulier : minimisation de la date de fin globale
5 Problèmes N P-difficiles
5.1 Introduction
5.2 Cas avec rencontres interdites et retards autorisés
5.3 Cas avec rencontres interdites et retards pour une population
5.4 Cas avec rencontres interdites et sans retards
5.5 N P-difficulté au sens fort
5.6 Non approximabilité
III Bornes inférieures et bornes supérieures
6 Bornes inférieures
6.1 Introduction
6.2 Borne inférieure dépendant des dates d’échéance des rencontres
6.3 Borne inférieure dépendant des dates d’arrivée des participants
6.4 Borne inférieure issue de couplages maximums
6.5 Condition nécessaire de non attente des participants
6.6 Résultats expérimentaux
6.7 Conclusion
7 Bornes supérieures
7.1 Introduction
7.2 Bornes déterminées par des heuristiques d’ordonnancement en série
7.3 Bornes déterminés par des heuristiques d’ordonnancement en parallèle
7.4 Résultats expérimentaux
7.4.1 Bornes déterminées par des heuristiques d’ordonnancement en série
7.4.2 Bornes déterminées par heuristiques d’ordonnancement en parallèle
7.4.3 Comparaison bornes inférieures/bornes supérieures
7.5 Conclusion
IV Modélisation et résolution
CONCLUSION
