Soutenance mémoire
Enjeux de la planification d’horaires
Depuis le début des années 80, dans le monde occidental la flexibilité du travail, et plus particulièrement la flexibilité du temps de travail, constitue aux yeux de tous une solution au moins partielle à de nombreux problèmes économiques et sociaux : chômage, compétitivité des entreprises, animation des cités, développement de pratiques culturelles et sportives,… [PAR 1998].
Des enjeux économiques : L’utilisation efficace de la force de travail est reconnue comme un facteur primordial de productivité aussi bien dans le secteur industriel que dans celui des services. Le problème est toutefois plus crucial dans les services. En effet, si les industries manufacturières sont capables de gains de productivité en substituant des équipements au travail, le recours à l’automatisation pour délivrer un service reste limité. D’où l’enjeu est encore plus important pour les sociétés de services dans la mesure où leur activité opérationnelle est directement liée à la demande. En effet, dans les services :
(a) le travail n’étant pas (ou peu) stockable, il est impossible de constituer des stocks de sécurité qui permettraient de lisser la demande en personnel ;
(b) le service doit être rendu dans une fenêtre de temps plus ou moins réduite selon l’urgence de la tâche ;
(c) production et consommation de services étant indissociables, les activités productives ne peuvent être effectuées qu’après l’apparition de la demande. Aussi, une capacité de services non exploitée est perdue ;
(d) la demande peut être extrêmement variable selon la saison, la semaine, le jour, l’heure et même sur des intervalles très courts.
De ce fait, les besoins en personnel dans certains services peuvent s’exprimer sur des périodes aussi courtes que cinq ou dix minutes. Ces caractéristiques typiques des services imposent des techniques de planification d’horaires adaptées et souvent plus sophistiquées que pour les industries manufacturières. Ainsi, la ressource travail est une composante essentielle de la productivité des entreprises et tout particulièrement dans le secteur des services.
Des enjeux sociaux : Les salariés trouvent un grand intérêt aux formes plus souples d’aménagement du temps de travail, mais cet intérêt ne coïncide pas toujours avec celui des entreprises. De plus, la flexibilité du temps de travail, parce qu’elle améliore la qualité de vie, favorise un meilleur « moral » des salariés avec un impact certain sur la motivation du capital humain en entreprise [PAR 1998] : moins d’absentéisme ou de retards, amélioration des performances,… La planification des horaires présente donc des enjeux à la fois sur un plan économique et un plan social. Toutefois, sa complexité, en particulier dans le secteur des services, impose de s’appuyer sur une démarche scientifique pour apporter des réponses pragmatiques à une catégorie générale de problèmes. Il s’agit donc de développer des outils de planification d’horaires, basés sur des techniques efficaces d’optimisation de ressources qui permettent de construire des programmes de travail individuels, respectant la réglementation du travail et autres accords avec les salariés et garantissant une bonne couverture de charge tout en limitant les coûts. Notons que ces outils pourront être utilisés à la fois dans un contexte opérationnel, c’està-dire pour effectivement établir des programmes de travail ou dans une démarche plus stratégique, pour évaluer les conséquences en termes de coût ou de qualité de service de modifications de la charge ou des contraintes de planification.
Le facteur humain dans les plannings
Malgré les progrès de la modélisation de plannings, le planificateur a toujours un rôle à jouer parce qu’il détient des connaissances sur le fonctionnement de l’entreprise ou de l’équipe. Ces connaissances sont difficiles à mettre en évidence car elles peuvent résulter des négociations ou du contexte spécifique à l’entreprise. En général, les fonctionnements spécifiques ne sont pas pris en compte par les logiciels standards et le planificateur doit contrôler le planning manuellement pour en assurer la conformité. Une collaboration réussie avec le logiciel de planification, doit permettre au planificateur de participer efficacement à l’élaboration des plannings. L’interface hommemachine joue un rôle primordial : il est indispensable pour le planificateur de comprendre la situation planifiée dans sa globalité et ses détails. Dans la pratique le planificateur cherche un outil qui peut rendre service dès le début, et ce, sans une formation approfondie. Un générateur automatique de plannings doit donc admettre des pré-affectations faites manuellement, pour que l’utilisateur puisse réagir avec les plannings automatiques. Très souvent les diverses contraintes applicables sont contradictoires : le planificateur doit choisir les contraintes à assouplir afin de produire des plannings.
Plannings pédagogiques
La confection d’horaires dans les établissements scolaires est un travail difficile à réaliser qui requiert généralement un investissement de temps considérable de la part d’une ou de plusieurs personnes. La diversification des plans d’études, l’interdépendance des programmes d’enseignement, l’apparition des cours à option, les exigences toujours plus nombreuses du corps enseignant, la disponibilité limitée des salles sont telles que les plannings scolaires deviennent avec le temps de plus en plus complexes à réaliser. Etant donné le volume d’information à traiter, les risques d’erreurs sont importants malgré toute la compétence et l’application des personnes impliquées. Il en résulte que des systèmes toujours plus performants sont développés pour concevoir des horaires qui tiennent compte de tous les éléments souhaités. Il existe deux types de problèmes différents dans le domaine de la planification des horaires scolaires : les horaires de cours hebdomadaires et les horaires d’examens. De nombreux modèles et algorithmes ont été proposés dans la littérature spécialisée pour confectionner de tels plannings. Parmi les techniques qui ont rencontré un certain succès, citons les méthodes constructives [OST 1982], séquentielles [ABR 1991], évolutives [COL 1996], ou d’autres méthodes plus spécifiques faisant appel à des modèles de flots [CHA 1989], de coloration de graphes [WER 1985], de relaxation lagrangienne [TRI 1980], et de réseaux de neurones [CAO 1991]. Schaerf [SCH 1995a] a utilisé une méthode tabou pour résoudre ce problème. Il emploi le codage matriciel Mj,k qui contient le nom de la classe du professeur j à la période k. Les voisinages proposés sont :
• Echanger deux cours pour un même professeur.
• Déplacer un cours à une autre période.
Pour des instances de tailles moyennes, les résultats obtenus ont été encourageants.
Méthodes heuristiques de type recherche tabou [JAU 2000]
L’idée est de développer une classe d’heuristiques pouvant s’adapter facilement aux différentes caractéristiques des unités de soins pour lesquels des horaires sont développés (unités de soins dans un hôpital avec des tailles variables, par exemple de 10 à parfois 100 infirmières, équipe d’infirmières dans une clinique, fonctionnement journalier d’un centre de prélèvements, fonctionnement 24h d’une urgence). Dans cette optique, l’idée est de regarder des mouvements très locaux du type échange de quarts de travail jusqu’à des mouvements du type changement de l’horaire d’une infirmière pour les grosses unités de soins. Dans une première étape, les différentes variantes ou heuristiques seront développées de façon indépendante, mais avec le souci de pouvoir les intégrer dans une même heuristique avec des stratégies variables dans une seconde étape. Malheureusement, la recherche tabou est une technique d’optimisation sans contraintes. Effectivement, les transitions d’un état à un autre peuvent engendrer des violations de contraintes, sauf si elles ont été conçues spécifiquement.
Conclusion générale et perspectives
Dans ce mémoire, nous nous sommes donnés comme objectif principal la résolution d’un problème de planification d’un ensemble de médecins – dans un service de radiologie – soumis à une variété de contraintes. Vu que le problème, par sa nature fortement combinatoire, ne peut admettre une procédure déterministe de résolution, nous avons orienté notre recherche vers les algorithmes génétiques qui, par leur mode aléatoire de balayage du domaine des solutions, permettent d’aboutir à une solution, même si elle n’est pas toujours optimale, elle est admissible selon un critère donné. Nous avons orienté notre recherche vers l’étude des paramètres de l’algorithme génétique, d’où nous avons intégré une méthode de propagation de contraintes avant l’étape de génération de la population initiale, afin de réaliser un filtrage pour réduire l’espace de recherche. Nous avons aussi défini un mode adéquat de sélection des parents afin de fournir de bons fils candidats à une nouvelle population. Le mode de croisement a été également étudié afin d’éviter la violation de certaines contraintes. Nous jugeons que l’algorithme génétique obtenu est un outil d’une grande efficacité pour la résolution de tout problème qui peut se formuler de la même manière que le notre. Rappelons que le problème étudié est NP-difficile, donc, toute heuristique bien fondée ne peut que contribuer à sa résolution. Par ailleurs ce travail nous a permis de constater la capacité des algorithmes génétiques à résoudre des problèmes NP-Complets avec une facilité remarquable. Leur efficacité, longtemps remise en cause par bon nombre de chercheurs, n’est plus à prouver. Les performances de l’algorithme génétique ne sont altérées que par le fait que le même genre de calcul se répète avec chaque individu de chaque population La parallélisation de l’algorithme peut être une solution à ce problème. Les algorithmes génétiques ne garantissent pas de trouver l’optimum global, bien que, théoriquement, il a été démontré qu’ils convergent vers cet optimum. En pratique, ils restent souvent inefficaces lorsqu’il s’agit de trouver la valeur exacte de cet optimum. Or c’est précisément ce que les algorithmes de recherche locale tel que tabou, réalisent le mieux. Il serait donc naturel de penser à un moyen d’hybridation en associant un algorithme local à l’algorithme génétique de façon à trouver la valeur exacte de l’optimum. On peut aisément le faire en appliquent à la fin de l’exécution de l’algorithme génétique un algorithme local afin que le meilleur individu soit trouvé, et s’assurer que la solution fournie sera optimale. Dans la dernière partie de cette thèse, nous avons projeté la lumière sur le phénomène de défaillance des ressources aussi bien humaines que matérielles. Nous avons présenté une méthode de gestion des conditions intempestives au sein de notre planning. La méthode proposée peut être appliqué à une large gamme de problèmes ayant une structure analogue à celle du notre. Vu la complexité et la difficulté du problème traité et le manque de travaux ayant abordé ce sujet, tout apport en terme d’approche ou solution ne peut qu’être louable. Nous jugeons les résultats obtenus comme encourageants.
|
Table des matières
Introduction
Chapitre I : La planification d’horaires de travail
1. Enjeux de la planification d’horaires
2. Problématique de la planification d’horaires
2.1 Un processus complexe
2.2 Qu’est-ce que la planification ?
2.3 Qu’est-ce qu’un bon planning ?
2.4 Le contexte de la planification
2.5 Le facteur humain dans les plannings
3. Types de plannings
3.1 Plannings sportifs
3.2 Plannings pédagogiques
3.3 Plannings aériens
4. La planification hospitalière
5. Types de plannings hospitaliers
6. Conclusion
Chapitre II : Choix de la méthode utilisée
1. Introduction
2. Analyse des approches utilisées pour résoudre les problèmes de planification
2.1. Exploitation et exploration
2.2. Quelle métaheuristique utiliser ?
2.3. Notre choix
Chapitre III : Proposition d’un algorithme génétique pour la résolution de notre problème de planning hospitalier
I. PRESENTATION DU PROBLEME ETUDIE
II. PRESENTATION DE L’ALGORITHME GENETIQUE CONÇUE
II.1 Alphabet de codage et fonction d’adaptation
a. L’alphabet de codage
b. La fonction d’évaluation
c. Modélisation des contraintes
d. Structure de données
II.2 Initialisation de la population
II.3 Les opérateurs utilisés
a. La sélection
b. Le croisement
c. La mutation
II.4 Condition d’arrêt
II.5 Les étapes de notre algorithme génétique
III. IMPLEMENTATION ET EXPERIMENTATION
Quelques résultats
Convergence de l’algorithme
Conclusion
Chapitre IV : Gestion des conditions intempestives
1. Introduction
2. Les défaillances au sein d’un planning
2.1 Défaillances humaines
2.1.1. Absences volontaires
2.1.2. Absences involontaires
2.1.2.a. Cas déterministe
2.1.2.b. Cas non déterministe
2.2. Défaillances matérielles
2.2.a. Cas déterministe
2.2.b. Cas non déterministe
3. Implémentation et critiques des résultats obtenus
4. Conclusion
Conclusion générale et perspectives
Télécharger le rapport complet
