Optimisation de la confection d'horaires de médecins urgentistes : application à l'hôpital Maisonneuve-Rosemont

Au département d'urgence de l'hôpital Maisonneuve Rosemont (HMR) à Montréal, les horaires de l'équipe de médecins sont réalisés à la main à l'image de beaucoup d'autres établissements. Pour réaliser un horaire, il faut affecter à la fois les quarts de travail et les postes à occuper (tâches) entre les différents médecins disponibles sur une période donnée (ici quatre semaines). Il s'agit de respecter un grand nombre de contraintes, tout en recherchant la meilleure qualité possible des horaires. La confection d'un horaire est fastidieuse et consomme beaucoup de temps. Ce projet a pour objectif de développer une solution transférable, capable de produire les horaires des médecins urgentistes de HMR en économisant le temps de planification manuel, tout en assurant une résolution quasi-optimale du problème défini en collaboration avec le chef de service, le Docteur Gagnon. Nous avons dans ce cadre développé un modèle linéaire mixte (MIP) pour résoudre le problème d'horaire. Nous résolvons à la fois le problème d'affectation de quarts et le problème d'affectation de tâches. Le modèle s'articule autour des variables représentant l'affectation, chaque jour, pour chaque médecin à un poste donné. Les contraintes sont réparties en deux groupes : les contraintes dures comme le respect des disponibilités des médecins; les contraintes relaxées selon deux approches. La première approche de relaxation consiste à fixer une valeur cible et à autoriser une déviation par rapport à cette valeur, par exemple les quarts affectés de manière isolée sont autorisés dans la limite de un par médecin et par mois. La seconde approche consiste à inclure dans la fonction objectif les occurrences de situations bénéfiques ou néfastes (en les maximisant ou les minimisant respectivement). Le modèle tient ainsi compte de l'ensemble des règles opérationnelles du département d'urgences régissant les horaires des médecins. Le problème d'horaire instancié est résolu grâce aux solveurs CPLEX et COIN Branch and Cut (CBC) (solveur gratuit). Au fil du développement du modèle, une dizaine d'horaires ont pu être comparés aux réalisations manuelles pour atteindre la forme finale présentée dans ce mémoire, capable de générer des horaires prêt à l'emploi. La solution transférée est basée sur le solveur CBC et les horaires produits satisfont le Docteur Gagnon à la fois en termes de qualité et en temps de réalisation.

Abstract

Physician schedules are manually developed at the emergency room of the Maisonneuve Rosemont hospital (HMR) in Montreal, as in many other hospitals. In this case, the department chief Doctor Gagnon is in charge of the scheduling. To produce a schedule, both shifts and jobs (tasks) have to be assigned to the available physicians of the team on a defined period (e.g. four months). The process of making a schedule is a very tedious and time consuming task. One has to respect a large amount of constraints while looking for the best schedule. This project's goal is to develop a transferable tool capable of producing the physician schedules of the emergency room of HMR. It has to save time by removing manual scheduling and to guarantee the optimal resolution of the problem for main objectives. The problem and objectives are defined with the collaboration of the chief of the emergency department, Doctor Gagnon. In this context, a mixed integer programming (MIP) model has been built to solve the scheduling problem. We both solve the shift assignment problem and the task assignment problem. The modeling is built around the main variables standing for the assignment of each physician, each day on each task. Constraints are separated in two groups: some are hard constraints as the respect of physician's availabilities and the others are soften by two different methods. The first one is to give a target value and to authorize a deviation to this value for the criterion. For example, isolated shifts are accepted within the limit of one per physician and per month. The second is to put the criterion in the objective function to maximize or minimize the occurrences of good or bad features. The resulted modeling takes into account all operational rules of the emergency room scheduling. Instantiated models are solved both by the commercial solver CPLEX and the license's free solver COIN Branch and Cut (CBC). During the development of the model, more than ten schedules have been compared to manual ones to lead to the final model proposed in this thesis. This resulting modeling is capable to produce ready to use schedules satisfying Doctor Gagnon both in terms of quality and processing time.