Ensemble des cliques maximales dans un graphe d’intervalles

Télécharger le fichier pdf d’un mémoire de fin d’études

Problème métier et contexte industriel

Les laboratoires pharmaceutiques qui souhaitent obtenir une autorisation de mise sur le marché pour un nouveau médicament doivent au préalable évaluer cliniquement tous ses eﬀets sur le corps humain. Pour cela, il est nécessaire de réaliser une étude pharmaceutique auprès d’un organisme indépendant et agréé par le Ministère de la Santé, tel que Biotrial [29]. Ainsi, lorsqu’un laboratoire souhaite réaliser une étude pharmaceutique, il transmet à Biotrial un protocole de tests décrivant en détail toutes les étapes permettant d’analyser précisément les eﬀets du médicament. Ce protocole est tout d’abord étudié et validé par le médecin en charge de l’étude afin de déterminer précisément tous les examens médicaux à réaliser. Ces examens sont fixés dans le temps à la minute près, ce qui permet, par exemple, de mesurer l’évolution de la concentration de certaines substances dans le sang. Après validation du protocole de tests, Biotrial prend en charge la conduite de l’étude.
La toute première étape d’une étude pharmaceutique est de recruter un groupe de volontaires souhaitant participer à l’étude. Le service d’accueil de Biotrial se charge de recevoir les volontaires et de vérifier leur état de santé afin de détecter d’éventuelles contre-indications médicales qui les empêcheraient de participer à l’étude. Les volontaires admis sont indemnisés pour leur participation
à l’étude. Une fois que le groupe de volontaires sains est complet, l’étude peut commencer. Le point de départ d’une étude correspond toujours à la phase d’administration : une partie des volontaires reçoit le médicament testé, alors que l’autre partie reçoit un placebo réalisé par le service pharmacie. Les études se déroulent en double aveugle ce qui signifie que ni les volontaires, ni les infirmiers ne connaissent la nature du produit administré (placebo ou médicament). Une série d’examens est alors réalisée sur chaque volontaire afin de surveiller tous les eﬀets du médicament. Ces examens peuvent être pratiqués en ambulatoire ou bien requérir une hospitalisation. Dans tous les cas, Biotrial garantit une surveillance médicale adéquate, au sein d’un environnement cliniquement sécurisé. La plupart des études ne durent que quelques jours ou semaines, mais certaines études peuvent s’étaler sur plusieurs mois. De telles études servent typiquement à mesurer les eﬀets d’un médicament sur le long terme. Dans ce cas, l’étude se compose d’une ou plusieurs visites médicales de quelques jours, eﬀectuées plusieurs mois après la première administration du médicament.
Puisque la charge de travail relative aux études découle entièrement des protocoles de tests, il est crucial pour notre partenaire de gérer très finement son eﬀectif de travail de manière à être capable de couvrir la charge de travail globale tout en maîtrisant les coûts en personnel et en respectant les contraintes organisationnelles et légales. Au fil de l’étude, les résultats cliniques sont systématique-ment reportés sur un document de référence, retourné au laboratoire client à la fin de l’étude. La rédaction de cette synthèse requiert un temps de travail non négligeable. De cette activité particulière émergent plusieurs problèmes complexes portant sur diﬀérents niveaux temporels :
• D’un point de vue stratégique, il est nécessaire de dimensionner l’eﬀectif requis en fonction de la charge de travail de l’entreprise. Ce processus de planification est réalisé sur un horizon de plusieurs mois ou années.
• D’un point de vue tactique, il est nécessaire de positionner les études pharmaceutiques de manière à ce que la charge de travail qui en résulte corresponde au mieux à la capacité de travail de l’entreprise. Ce processus de planification est réalisé sur un horizon de plusieurs semaines.
• D’un point de vue opérationnel, il est nécessaire de réaliser les plannings des employés de ma-nière à disposer du personnel adéquat à la réalisation de tâches prévues. Il s’agit d’un processus complexe faisant intervenir la législation du travail et les contraintes relatives à l’organisation interne de l’entreprise, ainsi que les compétences, les disponibilités et les préférences des em-ployés. Ce processus de planification du personnel est réalisé sur un horizon d’une semaine, en même temps que l’attribution des tâches aux employés. En cas de surcharge ponctuelle de travail, il peut être nécessaire de recourir à des intérimaires, ce qui revient à aﬃner les choix réalisés au niveau tactique et stratégique. Dans ce cas, l’objectif est de couvrir la charge de travail avec un nombre minimum d’intérimaires.
En ce qui concerne le dimensionnement de l’eﬀectif, Biotrial a fait le choix de conserver un eﬀectif minimum, quitte à recourir régulièrement à des intérimaires. De cette manière, les périodes de faible activité sont moins dommageables pour l’entreprise. Cette stratégie accentue en revanche la com-plexité des problématiques tactique et opérationnelle qui intègrent alors les prévisions d’embauches d’intérimaires.
Vis-à-vis du positionnement des études, Biotrial dispose en réalité d’une marge de manœuvre assez réduite. Les laboratoires clients imposent en eﬀet de plus en plus fréquemment une date de début donnée. Lorsque le début de l’étude n’est pas imposé, il est souvent fortement contraint. Plus généralement, notons que la durée de vie des brevets, relativement courte par rapport au temps de développement de nouveaux médicaments, pousse les laboratoires pharmaceutiques à prendre des risques vis-à-vis de leur gestion de projets, afin de réduire les délais de validation. Par exemple, il arrive fréquemment que les laboratoires anticipent les autorisations de réalisation des tests cliniques et demandent à notre partenaire de planifier des tests pour lesquels l’autorisation n’a pas encore été obtenue. Cela peut conduire à annuler ou reporter des études entières à la dernière minute lorsque l’autorisation n’est pas délivrée à temps. Par conséquent, la gestion des intérimaires s’eﬀectue presque exclusivement au niveau opérationnel.
Les plannings du personnel sont actuellement réalisés manuellement, ce qui mobilise deux déci-deurs très expérimentés à temps plein pour un eﬀectif permanent d’une trentaine d’employés, mais pouvant doubler suite à une embauche massive d’intérimaires. En raison de la grande précision des protocoles de tests et de la complexité des activités de travail à organiser, la construction hebdo-madaire des plannings est actuellement un processus très complexe. De plus, Biotrial a récemment entrepris des aménagements visant à accroître sa capacité d’accueil, notamment en doublant son nombre de lits, ce qui se traduira par un accroissement des données à prendre en compte au quoti-dien. Il est ainsi probable que les décideurs rencontrent de plus en plus de diﬃcultés à appréhender toutes les données du problème, ce qui risque de conduire à une baisse de la qualité des plannings ainsi qu’à un accroissement important des besoins en intérimaires.
De nombreux échanges avec Biotrial nous ont permis de conclure que les problèmes de dimen-sionnement de l’eﬀectif et de positionnement des études étaient moins adaptés à la mise en place d’un outil d’aide à la décision, notamment en raison de la faible marge de manœuvre. En revanche, le problème de gestion de l’eﬀectif de travail semble tout à fait adapté à la mise en place d’un outil d’aide à la décision, ce qui nous a conduit à favoriser cette problématique.

Diversité des activités de travail

Au cours d’une même semaine, chaque employé peut être amené à réaliser des activités de nature très diﬀérentes, telles que des formations professionnelles, des réunions d’équipe, des analyses d’échan-tillons et bien entendu des actes cliniques (prise de sang, électrocardiogramme, etc.), pratiqués direc-tement sur les volontaires, contrairement aux analyses d’échantillons qui se déroulent en laboratoire. Chaque étude est supervisée par une équipe-projet qui se réunit au début de l’étude pour valider le protocole de tests et construire le planning correspondant pour chaque volontaire. L’équipe-projet se charge également du bon déroulement de l’étude et de la rédaction du compte-rendu des résultats observés pour chaque volontaire. Ce compte-rendu est rempli au fil de l’étude par l’équipe-projet, ce qui requiert une part importante de leur temps de travail. Les activités du personnel peuvent se répartir en plusieurs catégories induisant chacune des contraintes de natures diﬀérentes. Nous avons donc choisi de distinguer trois types d’activités : les activités administratives, les activités obligatoires et les activités médicales.
Équipe-projet : il s’agit d’un groupe d’au moins trois employés en charge d’une étude donnée. Ce groupe comprend systématiquement un technicien, un infirmier et un médecin. Le technicien et l’infirmier supervisent le déroulement des activités techniques et cliniques, et se chargent de rédiger les compte-rendus des résultats, alors que le médecin supervise le déroulement global de l’étude, valide le protocole de test et rédige le compte-rendu de sécurité et de tolérance du produit testé (son avis est décisif pour la poursuite ou non de l’étude).
Activités administratives : il s’agit notamment des activités de rédaction de compte-rendus. Ces activités peuvent être réalisées à tout moment de la semaine et ne requièrent aucune compé-tence spécifique, mais nécessitent en revanche une certaine expérience. Ces activités sont par conséquent confiées en priorité aux employés les plus expérimentés, jamais aux intérimaires. Plus précisément, ces activités sont généralement confiées aux équipe-projets. D’autre part, ces activités ne faisant pas partie du protocole de tests, elles peuvent être préemptées si besoin. Les employés organisent leur temps de travail administratif de manière autonome ce qui signifie que ces plages de travail ne sont pas indiquées explicitement sur le planning des employés.
Activités obligatoires : il s’agit des réunions d’équipes et des formations professionnelles. Ces tâches sont fixées dans le temps et pré-aﬀectées à un employé donné en amont de la phase de planification du personnel. Les horaires de travail des employés doivent permettre aux employés de réaliser ces activités obligatoires, dans le respect des contraintes légales et organisationnelles. Activités médicales : il s’agit des actes cliniques et techniques, requérant des compétences précises. Ces actes sont très majoritairement fixés dans le temps pour chaque volontaire concerné (date de début et durée), mais certains actes peuvent éventuellement être retardés, dans une certaine mesure, par rapport à leur date de début prévue. L’analyse de certains prélèvements, par exemple, peut être diﬀérée sans nuire à la fiabilité des résultats. Le fait de retarder certaines tâches est un procédé à éviter, destiné uniquement à gérer les pics d’activités. Contrairement aux activités obligatoires, les activités médicales ne sont pas pré-aﬀectées à un employé donné et peuvent donc être réalisées par tout employé disponible et compétent, à condition bien sûr que toutes les contraintes légales et organisationnelles soient respectées. La gestion des activités médicales constitue le cœur du problème opérationnel de Biotrial, actuellement traité à la main, en même temps que la construction des horaires de travail des employés.
Pour chaque employé, la répartition du volume de travail total entre ces trois activités dépend des études pharmaceutiques en cours. Certaines études requièrent par exemple des compte-rendus très détaillés, ce qui accroît le temps de travail administratif. Notons également que le début de chaque nouvelle étude donne lieu à au moins une réunion de son équipe-projet afin de faire le point sur le protocole de tests de l’étude. Les périodes de travail correspondant au lancement de plusieurs études sont ainsi particulièrement chargées au niveau des activités obligatoires. Remarquons enfin que le nombre, la nature, ainsi que l’enchaînement des tâches médicales à réaliser varient entièrement d’une étude à une autre.

Particularités des activités médicales

Nous avons vu à la section précédente que les employés peuvent réaliser trois types d’activités : obli-gatoire, administrative et médicale. Nous avons également présenté les principales diﬀérences entre ces trois activités, ainsi que la manière dont ces activités sont gérées par le décideur (aﬀectation, pré-aﬀectation, préemption, etc.). Nous souhaitons à présent apporter quelques précisions sur les activités médicales dont la gestion constitue le cœur du problème étudié. Remarquons tout d’abord que la même notion d’acte médical peut renvoyer à diﬀérentes réalités selon le contexte et les interlocuteurs. Du point de vue des laboratoires pharmaceutiques, un acte médical correspond à la réalisation d’un acte précis sur un volontaire donné. On peut alors parler d’actes unitaires. Les décideurs visualisent le détail des actes unitaires sur un tableau Excel donnant les volontaires en colonne et les tâches médicales en ligne (cf. Figure 2.1 pour une version simplifiée). Ainsi, chaque cellule correspond à un acte unitaire, comme par exemple : Electrocardiogramme – Visite 7, réalisé sur le volontaire n°2 à 7h57. Afin de respecter les protocoles de tests, les infirmiers et les techniciens en charge des actes médicaux doivent disposer du même niveau de détail que les laboratoires. En revanche, les déci-deurs en charge des plannings du personnel ne peuvent pas gérer un tel niveau de détail. Ils ont par conséquent pris l’habitude de regrouper certains actes médicaux entre eux, de manière à réduire le nombre de données à gérer. Ainsi, au lieu de gérer des actes unitaires (un acte sur un volontaire), les décideurs gèrent des actes multiples (plusieurs actes sur plusieurs volontaires). De cette manière, en aﬀectant un seul acte multiple, le décideur peut aﬀecter directement plusieurs actes unitaires. Il ne s’agit pas seulement d’une astuce pour réduire la quantité de données gérée par les décideurs mais surtout d’une pratique métier consistant à aﬀecter une même personne sur une série d’actes médicaux communs à tout un groupe de volontaires. Bien sûr, les actes médicaux ne peuvent pas être regroupés n’importe comment et il faut une grande expérience pour déterminer les regroupements qui seront réalisables par les employés tout en minimisant les temps de battement entre deux actes unitaires. Remarquons en particulier que certains actes fixés au même horaire peuvent parfois être regroupés, car il est possible de les faire en même temps, alors que d’autres actes espacés de plusieurs minutes ne peuvent être regroupés, en raison d’une grande technicité par exemple. Cette distinction se fait sur la base d’une expertise métier très riche et en constante évolution puisqu’il est possible de modifier ce regroupement au cours d’une étude. D’un point de vue pratique, ce regroupement est réalisé sur le tableau Excel mentionné précédemment en attribuant une même couleur à plusieurs cellules. En reprenant l’exemple précédent, on peut ainsi voir que le décideur a regroupé tous les actes d’administration, de manière à ce qu’ils soient réalisés par un même employé (cf. Figure 2.2). De la même manière, les électrocardiogrammes, les pressions artérielles et les prélèvements sanguins des volontaires n°1, n°3 et n°5 ont été regroupés en un seul acte commençant à 7h30 et s’étalant sur 48 minutes.

Spécificités des employés

Le personnel de l’entreprise est réparti à travers quatre services : clinique, technique, accueil et pharmacie. Le service clinique se charge principalement des actes à réaliser sur les volontaires alors que le service technique s’occupe principalement des actes relatifs à l’analyse des prélèvements. Le service accueil gère l’arrivée des volontaires (inscription, bilan de santé, etc.) et pour finir, le ser-vice pharmacie est responsable de l’élaboration des préparations médicales destinées aux volontaires (médicament et placebo). Cette frontière entre les diﬀérents services repose essentiellement sur la maîtrise des compétences nécessaires à la réalisation des tâches aﬀectées aux diﬀérents services. En cas de besoin, il est cependant possible de réaliser des transferts d’employés d’un service à l’autre. Par exemple, les services cliniques et techniques peuvent s’échanger du personnel en cas de surcharge de travail de l’un ou l’autre des services, ce qui en pratique est très fréquent. En revanche, pour des raisons de respect du protocole, les employés du service pharmacie ayant participé à la préparation d’une étude donnée ne peuvent réaliser aucune des tâches cliniques ou techniques de cette étude puisqu’ils savent quels volontaires reçoivent le médicament et quels volontaires reçoivent le placebo. On parle alors d’étude « interdite » pour signifier qu’il est impossible d’assigner des tâches de cette étude à ces employés. Il leur est cependant possible d’assister le service accueil en cas de besoin. De manière générale, les employés préfèrent réaliser les tâches relatives à leur propre service.

Contraintes légales et organisationnelles

L’ensemble des contraintes à prendre en compte lors de l’élaboration des plannings hebdomadaires comprend d’une part les contraintes légales et d’autre part les contraintes organisationnelles, i.e. les contraintes relatives au fonctionnement interne de l’entreprise. Contraintes légales
La distribution des tâches étant très variable d’un jour à l’autre et d’une semaine à une autre, les horaires du personnel ne sont pas fixés à l’avance. La charge de travail médical de Biotrial est tellement variable qu’il est impossible de prévoir des roulements ou des horaires réguliers. Par conséquent, les plannings sont entièrement contruits chaque semaine en fonction de l’activité. Il est donc nécessaire de vérifier de nombreuses contraintes légales relatives au temps de repos et au temps de travail. Ces contraintes permettent de garantir que les plannings construits respectent la législation en vigueur au sein de l’entreprise. Toutes ces contraintes reposent sur quelques notions clés que nous identifions sous les termes suivants : vacation, temps présentiel, temps travaillé et jour de repos.
Vacation : il s’agit d’un horaire de travail journalier, attribué à un employé. Cet horaire peut comprendre des activités médicales et/ou obligatoires. Les activités administratives ainsi que les pauses n’apparaissent pas explicitement sur les vacations. Autrement dit, une vacation correspond à un horaire de présence minimum, pouvant être étendu au début ou à la fin, au gré des employés mais sous réserve de respecter les contraintes légales, de manière à réaliser leurs activités administratives. Pour cette raison, les vacations n’ont pas de durée minimale.
Temps présentiel : il s’agit de l’amplitude horaire d’une vacation. Le temps présentiel d’un employé travaillant de 8h à 16h est donc de 8h.
Temps travaillé : il s’agit du volume horaire travaillé durant une vacation. Le temps travaillé d’un employé présent de 8h à 16h avec une pause déjeuner d’une heure est donc de 7h.
Jour de repos : il s’agit d’un intervalle horaire entièrement non travaillé d’une durée de 24h. Dans l’intérêt du salarié, il est généralement préférable de placer ce repos le dimanche, mais cela n’est pas toujours possible, puisque l’activité de Biotrial est continue.
À partir de ces diﬀérentes notions, il est possible d’énoncer les principales contraintes légales du problème. Tout d’abord, le temps présentiel quotidien doit être inférieur à 11 heures et le temps travaillé quotidiennement ne doit pas dépasser 10 heures. De plus, les employés travaillant le matin bénéficient d’une pause de 18 minutes et d’une pause déjeuner d’une heure entre 12h et 14h30. Ces deux pauses sont décomptées du temps de travail, i.e. le temps travaillé d’un tel employé correspond au temps présentiel diminué de 1h18. D’autre part, les employés ne travaillant pas le matin mais travaillant sur plus de 6h bénéficient d’une pause de 30 minutes comptée dans le temps de travail, i.e. le temps travaillé d’un tel employé correspond à son temps présentiel. Remarquons dès à présent que le respect de ces pauses peut être problématique, puisque certaines activités médicales durent plusieurs heures. Ainsi, par exemple, un employé étant aﬀecté à une activité médicale commençant à 10h et se terminant à 15h, ne peut pas prendre une pause déjeuner « classique ». Ces contraintes sont donc considérées comme souples et les conflits sont arbitrés par l’infirmière en chef afin que les vacations des employés restent supportables, même si certaines « contraintes » sont violées. D’autres contraintes portent sur le temps de travail hebdomadaire des employés. Ainsi, le temps travaillé heb-domadairement ne doit pas dépasser 48 heures. Enfin, certaines contraintes glissantes sont également à prendre en compte. Par exemple, une période de repos hebdomadaire d’une durée minimale de 35 heures, ainsi qu’au moins un jour de repos, doivent être observés sur une période de 7 jours consécu-tifs. D’autre part, deux vacations consécutives doivent être séparées par un temps de repos minimum de 11 heures. Notons que le respect des contraintes glissantes nécessite de prendre en compte le planning de la semaine passée, afin de vérifier que le temps de repos entre la vacation du dimanche et celle du lundi est bien respecté, mais également que le jour de repos ainsi que le repos hebdomadaire de la semaine courante surviennent suﬃsamment tôt pour que la contrainte soit respectée, selon le placement du repos précédent.
Contraintes organisationnelles
Les horaires de travail d’un même employé peuvent être très diﬀérents d’un jour à l’autre de la semaine, car ils dépendent des tâches aﬀectées à cet employé. En théorie, n’importe quel horaire de travail respectant les contraintes relatives à la législation du travail peut être appliqué. En pratique, les horaires portant à la fois sur la nuit et sur le matin sont jugés trop pénibles pour être appliqués. Ainsi, un même employé ne peut être aﬀecté à deux tâches commençant par exemple à 5h et 8h le mardi matin car la première tâche est considérée par l’infirmière en chef comme une tâche de nuit, alors que la seconde est considérée comme une tâche de matin. Remarquons que certaines tâches peuvent commencer la nuit et finir le matin. Dans ce cas, l’infirmière en chef considère ces tâches comme étant des tâches de nuit, car les infirmières travaillant la nuit préfèrent souvent réaliser des vacations plus longues mais moins nombreuses.
Le respect des protocoles de tests entraîne de nombreuses contraintes organisationnelles. Tout d’abord, chaque tâche doit être aﬀectée à exactement un employé maîtrisant toutes les compétences nécessaires à la réalisation de cette tâche. De plus, les dates de début des tâches doivent être scru-puleusement respectées. D’autre part, les employés aﬀectés à une tâche doivent être disponibles sur toute la durée de cette tâche, ce qui nécessite de prendre en compte les indisponibilités des employés (congés, réunions, etc.). De plus, un même employé ne peut être aﬀecté à deux tâches concomi-tantes. Afin de garantir la fiabilité des résultats, les infirmières ayant participé à l’élaboration des préparations destinées aux volontaires ne peuvent être aﬀectées à aucune tâche médicale.

Appréciation d’un planning

Un planning est considéré comme réalisable s’il respecte toutes les contraintes légales et organisa-tionnelles de l’entreprise. Plus particulièrement, il est nécessaire d’obtenir une aﬀectation complète des tâches aux employés. Il s’agit par conséquent de regrouper les tâches en horaires de travail et de les aﬀecter aux employés adéquats, i.e. compétents et disponibles, de manière à ce que les plannings individuels qui en résultent respectent les diﬀérentes contraintes. Une illustration de ce problème sur un horizon d’une journée est donnée à la Figure 2.3.
La qualité d’un planning réalisable dépend de la charge de travail globale des employés. Plus précisément, il s’agit de répartir équitablement la charge de travail globale, de manière à éviter que certains employés soient en surcharge alors que d’autres seraient en sous-charge. Afin de prendre en compte toutes les activités réalisées par les employés, cette charge de travail globale inclut la charge médicale, la charge obligatoire et la charge administrative. Puisque les activités ad-ministratives n’apparaissent pas sur le planning du personnel, afin de laisser la liberté aux employés d’organiser ce temps de travail, l’infirmière en chef ne peut pas vérifier directement sur le planning la charge de travail globale des employés. Elle doit donc garder à l’esprit cette charge administrative, diﬀérente pour chaque employé, de manière à solliciter davantage les employés qui ont une faible charge administrative.

Hypothèses de travail

L’entreprise estimant que certaines données ne peuvent être formalisées parfaitement, nous avons décidé de nous concentrer sur le cœur du problème industriel afin de répondre au mieux aux besoins opérationnels. Cela nous a conduits à exclure certains cas particuliers que l’entreprise traitera soit en amont par une réorganisation, soit en aval par un ajustement du planning au cas par cas, en prenant en compte une expertise métier parfois très diﬃcile à généraliser. L’outil d’aide à la décision développé pour Biotrial prendra cependant en compte un maximum de données et de critères métier (cf. Chapitre 8).

Simplification des données

Sur les quatre services du personnel (accueil, pharmacie, clinique et technique, cf. Section 2.1.3, p. 25), nous avons décidé d’un commun accord avec l’entreprise de focaliser notre étude sur les services clinique et technique. Ces deux services sont en eﬀet en charge des activités médicales qui requièrent une attention particulière, notamment en raison de la précision des tâches à attribuer et des grandes fluctuations d’activité aﬀectant ces services. Le service pharmacie n’étant pas pris en compte, il devient alors inutile de gérer les études interdites (cf. Section 2.1.3 p. 25). Puisque le fait de retarder certaines tâches est un procédé à éviter, nous considérons ici que toutes les tâches doivent être planifiées à leur date de début prévue. La durée et la date de début de toutes les tâches médicales sont ainsi fixées dans le temps avec une précision d’une minute afin de respecter les protocoles établis par les laboratoires. Si besoin, les tâches qui auraient pu être retardées pourront être déplacées manuellement par le décideur.

Gestion des contraintes

En ce qui concerne les pauses de 18 et 30 minutes, nous avons décidé de ne pas les garantir car nous avons estimé avec l’infirmière en chef que ces pauses seraient automatiquement respectées dans la quasi totalité des cas, en raison des dates de début des tâches, fixées dans le temps. Il est en eﬀet très peu probable d’arriver à produire des plannings ne présentant aucun temps d’attente entre les diﬀérentes tâches aﬀectées à un même employé. De plus, même les plannings qui ne respectent pas ces temps de pause peuvent finalement être acceptés si besoin.
Vis-à-vis des pauses déjeuner, afin de pallier certains cas pathologiques (cf. Section 2.1.4), nous avons décidé de les prendre en compte de manière assouplie : les vacations de plus de 5 heures, commençant avant 12h et terminant après 14h30 donnent accès à un temps de repos d’une heure pouvant éventuellement être morcelé. Cette durée limite de 5 heures s’explique en deux temps. Premièrement, nous avons estimé qu’en-dessous de 5 heures, il n’était pas nécessaire de garantir un temps de pause, celui-ci pouvant être pris en fin de vacation. Encore une fois, il s’agit d’un arrangement pouvant également être appliqué en pratique. Deuxièmement, les tâches médicales les plus longues durant jusqu’à 5 heures, il ne serait pas possible de respecter le temps de pause des employés aﬀectés à ces tâches sans compléter leur vacation, déjà chargée, en y ajoutant une autre tâche. Considérons en eﬀet un employé aﬀecté à une seule tâche commençant à 10h et se terminant à 15h. Si on souhaite que cet employé bénéficie d’une heure de pause déjeuner, il faut alors lui aﬀecter une autre tâche se terminant à 9h ou commençant à 16h. Cela conduirait cependant à une vacation encore plus pénible que la vacation initiale de 10 à 15 heures. Le fait d’autoriser les pauses morcelées permet de mieux couvrir la charge de travail, ce qui reste la préoccupation principale de l’entreprise. D’autre part, le respect de la pause déjeuner entraîne de nombreux cas pathologiques pour lesquels il n’existe pas vraiment de solution idéale, comme cela a été signalé à la Section 2.1.4.

Critères d’appréciation d’un planning

L’une des contraintes principales du problème industriel étant d’aﬀecter toutes les tâches au per-sonnel disponible, il semblerait naturel de considérer l’aﬀectation des tâches comme une contrainte inviolable. En pratique, il peut cependant arriver qu’il soit impossible de trouver une telle aﬀectation. L’entreprise complète alors son eﬀectif au moyen d’intérimaires afin de réaliser les tâches restantes. Biotrial ayant fait le choix stratégique de travailler avec un eﬀectif permanent minimum, la gestion de ces pics d’activité peut la conduire, dans les cas extrêmes, à doubler son eﬀectif de travail en engageant des intérimaires. Remarquons que le recours aux intérimaires est préjudiciable à l’entre-prise à plus d’un titre. En eﬀet, outre les coûts financiers, le recours aux intérimaires conduit à des problèmes de maîtrise des compétences demandées, ce qui requiert de planifier des formations en doublon. D’autre part, les intérimaires ont parfois du mal à s’adapter au rythme de l’entreprise, ce qui peut entraîner des départs impromptus, ou des périodes d’adaptation relativement peu produc-tives.
Après plusieurs échanges avec le décideur il est apparu que ce dernier souhaitait conserver la main sur l’utilisation des intérimaires. Il est en eﬀet diﬃcile de définir un profil type de compétences pour les intérimaires, car leurs compétences ainsi que leur aptitude à s’adapter au rythme soutenu de l’entreprise varient énormément. De plus, il est diﬃcile de construire un horaire de travail type pour les intérimaires, car la durée de leur embauche peut aller de la demie journée à plusieurs semaines, selon les besoins. Par ailleurs, selon la complexité de l’activité, il peut être intéressant d’embaucher un intérimaire sur une période plus longue que nécessaire, de manière à capitaliser sur sa forma-tion. Pour autant, lorsqu’il est impossible d’aﬀecter toutes les tâches, le décideur souhaite qu’on lui propose un planning initial, de manière à pouvoir évaluer les besoins minimum en intérimaires. Ce planning initial doit être construit de manière à apporter au décideur un maximum d’information sur les besoins en intérimaires. Idéalement, il s’agirait de construire un planning dont l’eﬀectif de travail pourrait être complété par un nombre minimum d’intérimaires, sans qu’il y ait besoin de modifier les aﬀectations des autres employés. Le profil de compétences ainsi que l’horizon de recrutement des intérimaires étant inconnus, la construction d’un tel planning semble cependant particulièrement diﬃcile. Considérons par exemple la minimisation du nombre de vacations permettant de couvrir les tâches restantes. Cet objectif présente l’avantage de prendre en compte le positionnement tem-porel des tâches, permettant ainsi de gérer certains cas pathologiques. Par exemple, si trois tâches ne peuvent être aﬀectées, cet objectif favorisera les solutions pour lesquelles ces trois tâches sont suﬃsamment proches pour être regroupées dans une même vacation, sans pour autant être conco-mitantes, de manière à pouvoir être aﬀectées à un unique intérimaire. L’inconvénient de cet objectif est qu’il ne tient pas compte des compétences requises pour réaliser les tâches restantes, pouvant ainsi favoriser des solutions pour lesquelles les tâches restantes requièrent des compétences rares, non maîtrisées par les intérimaires. Si l’objectif est de minimiser le nombre et la rareté des compétences requises pour réaliser les tâches non attribuées, il sera alors plus facile d’aﬀecter les tâches restantes aux intérimaires, mais il est possible que ces tâches soient éparpillées sur toute la semaine, ou au contraire concomitantes, ce qui conduirait à surestimer soit le nombre d’intérimaires, soit le temps pendant lequel mobiliser des intérimaires. Une autre option pourrait être de minimiser la charge mé-dicale non attribuée, de manière à ce que la charge à réaﬀecter soit faible. Cela conduirait à favoriser l’attribution des tâches les plus longues au détriment des tâches les plus courtes. Un tel objectif ris-querait donc d’accroître le nombre de tâches non attribuées, augmentant potentiellement le nombre de compétences diﬀérentes associées aux tâches non aﬀectées. Ces diﬀérents exemples montrent qu’il est diﬃcile de concevoir une stratégie générale permettant de construire un planning dont l’eﬀectif de travail pourrait être complété par un nombre minimum d’intérimaires, sans qu’il y ait besoin de modifier les aﬀectations des autres employés. Par conséquent, nous optons ici pour une autre stra-tégie consistant à construire un planning facilement interprétable par le décideur. Afin de réduire la quantité d’information à prendre en compte, nous cherchons à minimiser le nombre de tâches non aﬀectées. Le décideur peut alors réaliser des arbitrages sur les quelques tâches restantes de manière à trouver une solution complète, ou bien ajouter des intérimaires et replanifier, de manière à obtenir un planning satisfaisant au bout de quelques itérations. Notons que les intérimaires pourront être mobilisés sur une ou plusieurs plages horaires, en fonction des besoins, et que le décideur pourra également positionner les plages de formation nécessaires. De cette manière, un planning pour lequel toutes les tâches sont aﬀectées est toujours préféré à un planning pour lequel certaines tâches ne sont pas aﬀectées, mais pour autant, en cas d’irréalisabilité, le décideur bénéficie d’une base de départ pour évaluer les besoins en intérimaires.
Lorsque toutes les tâches sont aﬀectées, il convient de répartir équitablement la charge de travail globale entre les employés, ce qui requiert de prendre en compte les activités médicales, obligatoires et administratives (cf. Section 2.1.5). Pour répartir équitablement la charge de travail globale, les infirmières en chef prennent en compte les activités administratives de manière informelle. Notre partenaire souhaite conserver ce fonctionnement, pour éviter de contraindre davantage les horaires de travail des employés en positionnant leur travail administratif. Cela nous a conduit à définir pour chaque employé une charge médicale idéale qui interviendra dans la répartition équitable de la charge de travail médicale. Pour un employé donné, cette charge idéale est d’autant plus grande que les charges administrative et obligatoire sont faibles sur la période considérée. Cette notion permet de traduire simplement le fait qu’un employé fortement chargé en activités administratives et obligatoires ne doit pas être trop chargé en activités médicales. Nous capturons ainsi ce que le décideur prend en compte de manière informelle lors de la construction du planning. À partir de cette notion de charge idéale de travail médical, il est possible de définir les notions de surcharge médicale et de sous-charge médicale. Plus un employé est en surcharge médicale, moins il aura de temps pour réaliser le reste de ses activités. À l’inverse, plus un employé est en sous-charge médicale, plus il aura de temps pour réaliser le reste de ses activités. Par conséquent, la répartition de la charge de travail globale est d’autant plus équitable que les employés ayant la plus grande surcharge médicale et ceux ayant la plus grande sous-charge médicale sont proches de leur charge idéale. Ainsi, par exemple, une solution où tous les employés respectent leur charge médicale idéale correspond à une répartition idéale du travail. De la même manière, si tous les employés sont en surcharge médicale à hauteur de deux heures par exemple, cela correspond également à une répartition idéale de la charge de travail, car cela signifie que la surcharge globale d’activité est équitablement répartie entre les employés.
À l’inverse, si certains employés sont en surcharge médicale d’une heure, alors que d’autres sont en sous-charge médicale d’une heure, alors cela n’est pas équitable. Autrement dit, nous considérons que la répartition de la charge globale est d’autant plus équitable que la diﬀérence de traitement entre les employés les plus pénalisés et les employés les moins pénalisés est faible. Charge médicale idéale : il s’agit d’un volume de travail, donné en minutes. Ce volume dépend de la charge administrative de l’employé correspondant. Ainsi, plus un employé à une charge administrative importante, plus sa charge médicale idéale est faible. Il s’agit donc d’une donnée du problème, définie par le décideur, de manière à estimer les proportions à respecter entre la charge médicale et les charges administratives et obligatoires pour chaque employé. Il ne s’agit donc pas d’une valeur maximale.
Sur/Sous charge médicale : se dit de l’activité médicale d’un employé dont la charge de travail médical aﬀectée est supérieure/inférieure à sa charge médicale idéale.

Périmètre du problème

Nous résumons ici les diﬀérentes hypothèses de travail établies avec notre partenaire afin d’uniformiser les données tout en gardant à l’esprit que les cas spécifiques seront gérés par le décideur :
R 1: seuls les services clinique et technique sont pris en compte ;
R 2: les études interdites ne sont pas prises en compte de façon spécifique ;
R 3: les tâches sont toutes considérées comme étant entièrement fixées dans le temps ;
R 4: les pauses de 18 et 30 minutes ne sont pas prises explicitement en compte ;
R 5: les pauses déjeuner sont vérifiées pour les vacations de plus de 5h et peuvent être morcelées.
Ces restrictions portent à la fois sur les données d’entrées et les contraintes du problème. Notons que la restriction R 2 n’impacte pas la modélisation du problème puisque les études interdites peuvent être aisément prises en compte via des compétences particulières. En revanche, la restriction R 3 impacte fortement la modélisation du problème puisqu’elle permet de s’aﬀranchir complétement du positionnement des tâches. Conceptuellement, il s’agit de la restriction la plus forte réalisée dans le cadre de l’étude. Cependant, cette restriction n’a que peu d’impact sur la qualité des plannings puisque les tâches pouvant être retardées sont assez rares et qu’il est préférable de ne pas les retarder. Les restrictions R 4 et R 5 s’expliquent par les temps de battement entre les tâches, ainsi que par la possibilité de réaliser des arbitrages reposant sur une expertise métier impossible à saisir parfaitement.

Données de test

Au regard des nombreuses spécificités du problème, il ne nous semble pas possible de trouver dans la littérature des jeux de tests suﬃsamment proches de notre cas d’étude pour être pertinents. Le pro-blème étudié étant issu d’une étude industrielle, il est cependant crucial de vérifier le comportement des méthodes de résolution sur des données susceptibles de correspondre à la réalité de l’entreprise. Étant donné que l’entreprise partenaire ne pouvait pas nous fournir de données réelles comprenant les diﬀérents éléments de décision, nous proposons par conséquent un nouveau jeu de données générées de manière à correspondre aux données industrielles. Il est regrettable que nous n’ayons pu bénéficier de données réelles, mais cela s’explique par le fait que tout le processus de planification du personnel est réalisé à la main par les infirmières en chef, ce qui requiert d’ailleurs une très grande expertise métier.

Caractéristiques des données industrielles

Une semaine classique correspond environ à 200 tâches dont la durée varie entre quelques minutes et plusieurs heures. Ces tâches sont distribuées sur toute la semaine et peuvent commencer à toute heure du jour ou de la nuit. Les tâches à réaliser le week-end ou durant la nuit sont cependant beaucoup plus rares alors qu’il est fréquent d’observer un pic d’activité à 8h. En tout, plus d’une trentaine d’actes cliniques diﬀérents sont répertoriés (analyses médicales, prises de sang, pipetages, électrocardiogrammes, encéphalogrammes, pressions artérielles, etc.). En temps normal, l’entreprise dispose d’une trentaine d’employés très polyvalents pour suivre les protocoles de tests. Chaque employé présente des indisponibilités non travaillées (congés posés, absences, contrats particuliers, etc.) ainsi que des indisponibilités travaillées (formations et réunions).

Générations de jeux d’instances

Étant donné que la création des plannings du personnel repose actuellement sur l’expérience de quelques décideurs qui conservent peu de traces des contraintes considérées au niveau opération-nel, nous n’avons pas pu bénéficier de jeux de données sous un format directement exploitable. En consultant d’anciens plannings, nous avons cependant pu estimer la charge de travail moyenne des employés, ainsi que la distribution globale de la charge de travail. À partir de ces observations, nous avons généré plusieurs instances correspondant à une semaine de travail en fonction des paramètres It, Ivet Ic, correspondants respectivement au nombre de tâches, à la charge de travail moyenne, et à la distribution de compétences. Les caractéristiques principales de ces paramètres sont récapitulées à la Table 2.1. En croisant toutes les configurations de ces diﬀérents paramètres, nous obtenons 24 jeux d’instances. De manière à pouvoir étudier chaque jeu d’instances, nous avons généré 30 instances de chaque configuration, soit un total de 720 instances, disponibles en téléchargement [167].
It : nombre de tâches cliniques sur une semaine. Ce paramètre permet de faire varier la taille des instances étudiées, ce qui nous permet d’évaluer le comportement des méthodes de résolution face à une instance de taille classique, mais également d’évaluer leurs capacités de passage à l’échelle. Nous proposons d’étudier des jeux de données avec 100, 200, 300 et 400 tâches cli-niques. Nous estimons en eﬀet qu’une instance classique comprend environ 200 tâches cliniques.
Iv : volume de travail clinique moyen des employés sur une semaine, en minutes. Un volume de travail moyen classique correspond à une valeur de 800 minutes. Par conséquent, nous proposons d’étudier trois configurations particulières : 600 minutes (faible), 800 minutes (classique) et 1 000 minutes (important). Ces trois configurations nous permettent de vérifier le comportement des méthodes en cas de sous-charge, de surcharge ou d’équilibre entre la capacité de travail et la demande.
Ic : répartition des compétences au sein de l’eﬀectif disponible. Nous proposons d’étudier deux configurations diﬀérentes. La première configuration, notée Icc, correspond à une répartition homogène des compétences, ce qui nous permet de prendre en compte le cas pratique où toutes les compétences requises sont jugées « communes », i.e. maîtrisées par un grand nombre d’em-ployés. La seconde configuration, notée Icr, complète la première configuration en y ajoutant la notion de « compétences rares », ce qui arrive lors de certaines études requérant des compé-tences particulières pour lesquelles peu d’employés sont formés.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1 Introduction
1.1 Contexte de l’étude
1.2 Objectifs de la thèse
1.3 Plan de la thèse
2 Présentation du problème
2.1 Problème métier et contexte industriel
2.1.1 Diversité des activités de travail
2.1.2 Particularités des activités médicales
2.1.3 Spécificités des employés
2.1.4 Contraintes légales et organisationnelles
2.1.5 Appréciation d’un planning
2.2 Hypothèses de travail
2.2.1 Simplification des données
2.2.2 Gestion des contraintes
2.2.3 Critères d’appréciation d’un planning
2.2.4 Périmètre du problème
2.3 Données de test
2.3.1 Caractéristiques des données industrielles
2.3.2 Générations de jeux d’instances
3 État de l’art 37
3.1 Panorama de problèmes de planification de personnel
3.1.1 Périmètre, classifications et contextes applicatifs
3.1.2 Besoins exprimés par vacations, cas du Nurse Rostering Problem
3.1.3 Besoins flexibles, cas du Tour Scheduling Problem
3.1.4 Besoins sous forme de tâches, cas du Crew Scheduling Problem
3.1.5 Gestion de l’équité en planification de personnel
3.2 Panorama de problèmes d’affectation de tâches fixées
3.2.1 Problèmes d’affectation avec ressources obligatoires
3.2.2 Problèmes d’affectation avec tâches obligatoires
3.3 Conclusion
4 Formalisation du problème
4.1 Définition du problème
4.1.1 Notations générales
4.1.2 Contraintes du problème
4.1.3 Gestion de l’objectif
4.1.4 Représentation d’une solution
4.1.5 Variantes étudiées
4.2 Pré/Post traitements et calcul d’une borne inférieure
4.2.1 Ensemble des cliques maximales dans un graphe d’intervalles
4.2.2 Borne inférieure pour SDPTSP||U
4.2.3 H∆, une descente locale pour réduire ∆
4.3 Modèles PLNE autour de SDPTSP
4.3.1 Modélisation PLNE pour SDPTSP|U = 0|∆
4.3.2 Modélisation PLNE autour de SDPTSP||U
4.4 Résultats expérimentaux
4.4.1 Preuves d’infaisabilité pour SDPTSP|U=0|-
4.4.2 Intérêt de la descente locale H∆
4.5 Conclusion
5 Une méthode en deux phases
5.1 Utilisations des méthodes en deux phases
5.2 Structure de M2P
5.2.1 Fonctionnement général de M2P
5.2.2 Phase 1 : construction des horaires de travail du personnel
5.2.3 Phase 2 : affectation des tâches à horaires de travail fixés
5.2.4 Obtention d’une solution initiale
5.2.5 Fonctionnement détaillé de M2P
5.3 Paramétrage de M2P
5.3.1 Paramétrage de la phase 1
5.3.2 Paramétrage de la phase 2
5.4 Analyse des résultats expérimentaux
5.4.1 Résultats globaux
5.4.2 Qualité de la solution initiale
5.4.3 Impact de H∆
5.4.4 Impact des différents opérateurs de voisinage (Phase 1)
5.4.5 Efficacité des différentes stratégies Sc et Sp (Phase 2)
5.5 Conclusion
6 Une approche par contraintes
6.1 Utilisation de la Programmation par Contraintes
6.2 Un modèle PPC pour SDPTSP|U = 0|∆
6.2.1 Choix de la modélisation
6.2.2 Variables du modèle PPC|U=0|∆
6.2.3 Contraintes du modèle PPC|U=0|∆
6.3 Modélisations PPC autour du SDPTSP
6.3.1 Modèles PPC pour SDPTSP||U et SDPTSP||U,∆
6.4 Stratégies de recherche
6.5 Résultats expérimentaux
6.5.1 Impact des stratégies de recherche
6.5.2 Impact de H∆
6.5.3 Résultats globaux
6.5.4 Combinaison des stratégies de recherche
6.6 Conclusions et perspectives
7 Une recherche à voisinage large
7.1 Introduction aux recherches à voisinages larges
7.2 Structure et fonctionnement de la LNS proposée
7.2.1 Opérateurs de destruction
7.2.2 Exploration du voisinage
7.2.3 Gestion de l’objectif
7.2.4 Fonctionnement détaillé de la LNS
7.3 Résultats expérimentaux
7.3.1 Résultats globaux
7.3.2 Qualité de la solution initiale
7.3.3 Intérêt des opérateurs de destruction
7.3.4 Gestion de l’objectif
7.3.5 Impact de H∆
7.3.6 Comparaison des méthodes
7.4 Conclusions et perspectives
8 MAESTRO, un logiciel de gestion et d’optimisation
8.1 Données opérationnelles et processus actuels
8.1.1 Données générales
8.1.2 Données spécifiques à l’activité
8.1.3 Processus actuel
8.2 MAESTRO, un outil d’aide à la decision
8.2.1 Périmètre et structure de l’application
8.2.2 Détail des fonctionnalités
8.2.3 Moteur de planification
8.3 Retour sur le projet MAESTRO
8.3.1 Déroulement du projet
8.3.2 Validation itératives des fonctionnalités
8.3.3 Réflexion sur les process
8.3.4 Mise en place de MAESTRO
8.3.5 Perspectives
9 Résolution du problème tactique
9.1 Description du SMPTSP
9.1.1 Notations et modélisation PLNE
9.1.2 Exemple de référence
9.1.3 Liens avec le SDPTSP||U,∆
9.2 Modélisation PPC avec la contrainte atMostNValue
9.2.1 Modélisation PPC & Fonctionnement de atMostNValue
9.2.2 Filtrer atMostNValue en présence de contraintes de différence
9.2.3 Diversification du filtrage avec l’algorithme Rk
9.3 Une stratégie de branchement pour le SMPTSP
9.3.1 Un branchement adapté aux règles de filtrage
9.3.2 Brancher, c’est parier.
9.4 Résultats expérimentaux
9.4.1 Un nouveau jeu d’instances
9.4.2 Intérêt du graphe contraint d’intersection GCI
9.4.3 Filtrage, temps de calcul et branchement
9.4.4 Passage à l’échelle
9.4.5 Comparaison à la littérature
9.5 Conclusions et perspectives
10 Conclusion
10.1 Travaux de thèse
10.2 Perspectives
A Lexique de contraintes
B Résultats des méthodes
B.1 Résultats de l’approche PPC
B.2 Résultats de l’approche M2P
B.3 Résultats de l’approche LNS
B.4 Résultats détaillés
C Publications scientifiques
C.1 Journaux internationaux
C.2 Conférences internationales avec actes
C.3 Conférences nationales
C.4 Soumissions en cours
1 Notations générales
2 Notations générales (suite)
2.1 Caractéristiques principales des instances.
3.1 Exemple d’un Nurse Rostering Problem
3.2 Exemple d’un Tour Scheduling Problem
3.3 Nomenclature pour le PTSP.
3.4 Positionnement de notre cas d’étude dans la littérature.
4.1 Variables du modèle PLNE|U=0|∆ pour SDPTSP|U = 0|∆
4.2 Nombre d’instances infaisables pour SDPTSP|U=0|-
4.3 Répartition des instances infaisables selon It et Iv.
4.4 Répartition des instances infaisables selon Ic et Iv.
4.5 Valeur moyenne de ∆ après 10 min
5.1 Opérateurs de voisinage sur les horaires du personnel
5.2 Sp : stratégies de calcul du poids W (w, t) des arêtes (w un employé, t une tâche)
5.3 Sc : stratégies d’exploration des cliques
5.4 Nombre de solutions complètes selon les valeurs de ρ et γ (5 min)
5.5 Équité moyenne des solutions complètes selon les valeurs de ρ et γ (5 min)
5.6 Nombre de solutions complètes selon λ
5.7 Équité moyenne des solutions complètes selon λ
5.8 Solutions finales de M2P (5 min)
5.9 Solutions initiales de M2P
5.10 Équité moyenne avant H∆ – après H∆ (en minutes)
5.11 Pourcentage moyen de meilleures solutions locales obtenues par opérateur de voisinage
5.12 Pourcentage moyen de sélection des variantes de l’Algorithme 5.1
6.1 Variables du modèle PPC|U=0|∆
6.2 Nombre de solution complètes selon les stratégies de recherche (sur 618 instances)
6.3 Inéquité des solutions complètes selon les stratégies de recherche (en minutes)
6.4 Pourcentage de tâches affectées selon les stratégies de recherche.
6.5 Temps d’obtention moyen de la meilleure solution (en secondes)
6.6 Variation de l’inéquité moyenne des solutions complètes durant la résolution
6.7 Variations du nombre de solutions complètes durant la résolution
6.8 Moyenne de l’inéquité (avant H∆ – après H∆) selon les stratégies de recherche.
6.9 Meilleurs résultats M2P (5 min)
6.10 Résultats PPC||U,∆ (LW-LN, 5 min)
6.11 Meilleures solutions obtenues avec PPC||U,∆ (All-All-H∆)
7.1 Résultats de la LNS (5 min)
7.2 Résultats M2P (5 min)
7.3 Solutions initiales PPC||U,∆ (LW-LN-H∆)
7.4 Solutions initiales LNS (dom/deg + last conflict-min value-H∆)
7.5 Résultats de la LNS avec l’opérateur Top uniquement (5 min)
7.6 Résultats de la LNS avec l’opérateur Pop uniquement (5 min)
7.7 Meilleure équité moyenne (avant H∆ – après H∆) des solutions complètes
7.8 Nombre de meilleurs résultats pour U
7.9 Nombre de meilleurs résultats pour (U,∆)
9.1 Caractéristiques principales des instances du SMPTSP.
B.1 CP-MW-LN-H∆
B.2 CP-LW-LN-H∆
B.3 CP-MW-BO-H∆
B.4 CP-LW-BO-H∆
B.5 CP-MW-ID-H∆
B.6 CP-LW-ID-H∆
B.7 CP-MW-BT-H∆
B.8 CP-LW-BT-H∆
B.9 Solutions finales de M2P (5 min)
B.10 Solutions initiales de M2P
B.11 LNS avec H∆ sur chaque solution.
B.12 Meilleurs résultats de la LNS.
B.13 LNS avec portée fixe.