Résumé Dans cette thèse, nous étudions la gestion des blocs opératoires, et plus particulièrement la planification et l’ordonnancement de ces blocs. Le choix d’études de ce secteur hospitalier est lié au fait qu’il est réputé comme un lieu hautement stratégique dans un établissement hospitalier, surtout en terme de coûts. Il est dès lors utile de s’intéresser à l’optimisation de l’utilisation des ressources hospitalières. Etant donné que l’optimisation du fonctionnement des blocs opératoires est un problème vaste et complexe, nous nous focalisons sur deux sous-problèmes déjà réputés difficiles : la planification et l’ordonnancement des interventions chirurgicales. Ce sont des problèmes centrés sur la programmation opératoire et dont l’objectif est d’obtenir un programme opératoire réalisable et efficace du bloc. Les problèmes de planification sont premièrement formalisés comme des modèles mathématiques en nombres entiers et puis résolus par des procédures heuristiques et par un « Branch-and-Price » basés sur la génération de colonnes qui est utilisée pour résoudre les relaxations linéaires des modèles concernés afin de trouver les bornes inférieures. Les modèles d’ordonnancement sont traités comme des variantes de modèles de « flow shop » hybride à deux étages et résolus par des algorithmes génétiques hybrides. Finalement, nos modèles ont été testés et validés sur un cas réel. ABSTRACT This thesis presents our studies on the operating theatre management, especially on the operating theatre planning and scheduling problem in case that this surgical sector is always regarded as the kernel in a hospital in terms of the expenditure. Therefore, it’s necessary to optimize the assignment of hospital resources in the operating theatre. Since this type of problem is extremely complex, we concentrate on just two sub-problems that are also considered difficult ones by researchers: the surgical cases planning and scheduling problem, which aim to make a surgical cases programming with an objective of obtaining a realizable and efficient surgical cases operating schedule. At first the weekly planning problems of surgical cases are formulated as a mathematical integer programming, and then they are solved by heuristic procedures and Branch-and-Price one. All these procedures are based on the column generation procedure, which is used to solve the linear relaxation of each model for a lower bound. The scheduling models are treated as variants of hybrid two-stage flow shop problem and are solved by proposed hybrid genetic algorithms. Finally, our models are tested and validated in a real case.

La gestion des blocs opératoires est actuellement l'objet de multiples questionnements, aussi bien sur le court terme que sur le long terme. Elle se heurte en effets aux problèmes aigus d'emploi des ressources aussi bien humaines que matérielles, qui sont aujourd'hui toutes deux disponibles en capacité finie. Dans l'investigation de cette problématique, nos travaux de recherche ont été effectués selon trois axes principaux. En premier lieu, dans une perspective initiale descriptive, nous avons analysé les différentes activités, ressources et flux du processus opératoire. Cette analyse nous a permis d'identifier les forces et faiblesses d'un existant et de modéliser ses différentes entités de gestion. Ensuite, nous avons proposé les différentes étapes d'une organisation de gestion d'un processus opératoire. Nous nous sommes limités dans notre étude aux périodes pré- (avant l'intervention) et per-opératoire (pendant l'intervention). Enfin, nous avons proposé des outils de résolution et expérimenté la capacité de ceux-ci à répondre aux différents problèmes de gestion. Quatre problèmes de gestion ont été identifiés : la programmation des interventions, la définition des plages horaires d'ouverture des salles d'opérations, la planification du bloc opératoire et enfin l'ordonnancement des salles d'opérations. Nous avons conçu une extension de la méthode Hongroise pour la résolution des problèmes de programmation et de planification opératoire. La définition des plages horaires d'ouverture des salles d'opérations a été définie comme un problème linéaire. L'ordonnancement des salles d'opérations a été identifié comme un problème de type Flow-Shop Hybride à trois étages sans temps d'attente avec contraintes de précédences. Il a été résolu à l'aide des règles connues d'ordonnancement et d'affectation.<br />Ces travaux nous ont permis de démontrer que des méthodes d'analyse et outils de résolution issus du manufacturier peuvent être appliqués au domaine hospitalier.

Au sein d’un établissement hospitalier, le bloc opératoire représente un des secteurs les plus emblématiques et les plus coûteux. Le fonctionnement du bloc opératoire est orchestré par un programme opératoire qui consiste à construire un planning prévisionnel des interventions chirurgicales à réaliser pendant un horizon donné. La littérature abondante sur le sujet est unanime sur le fait que la construction du programme opératoire est une tâche complexe, car il s’agit non seulement de planifier et d’ordonnancer les interventions, mais aussi de satisfaire des exigences souvent antagonistes. Ce projet est le fruit d’une collaboration entre la Communauté d’Agglomération de Sarreguemines Confluences et la Région Lorraine, des membres du secteur hospitalier (Hôpital Robert Pax de Sarreguemines) et l’équipe Gestion Industrielle et Logistique (GIL) du Laboratoire de Génie Industriel, de Production et de Maintenance (LGIPM). L’objectif de cette recherche est d’apporter une aide aux gestionnaires du bloc opératoire, qui ont besoin de plus en plus des méthodes et des outils d’aide à la décision en vue d’optimiser leur fonctionnement. Pour répondre à ce besoin nous nous intéressons dans la première partie de cette thèse à la gestion des opérations électives en prenant en compte différentes contraintes et en particulier la disponibilité des chirurgiens. Nous nous plaçons dans le contexte d’une stratégie « open scheduling » et nous proposons deux modèles mathématiques permettant d’élaborer le programme opératoire. La complexité des modèles mathématiques et leur explosion combinatoire rendent difficile la recherche de l’optimum pour des tailles réalistes. Ceci nous a donc amené à proposer une heuristique constructive utilisant le modèle proposé et permettant d’obtenir des solutions là où la méthode exacte ne nous le permettait pas. Dans la seconde partie de cette thèse, nous considérons l’intégralité du processus opératoire (brancardage vers le bloc opératoire, préparation et anesthésie, acte chirurgicale et réveil). Nous modélisons ce processus comme un flow shop hybride à 4 étages avec contrainte de blocage de type RSb, et nous le résolvons à l’aide d’un algorithme génétique dont l’objectif est de synchroniser toutes les ressources nécessaires, en respectant au mieux le programme opératoire prévisionnel. Outre les opérations électives, nous nous intéressons dans la dernière partie aux opérations urgentes. Nous proposons un outil d’aide à la décision pour la gestion des opérations urgentes. En prenant en considération la pathologie et la gravité de l’état du patient, nous distinguons principalement 3 degrés d’urgences et proposons pour chacune un algorithme permettant d’intégrer en temps réel ces opérations dans le programme prévisionnel, tout en minimisant différents critères (temps d’attente avant affectation, heures supplémentaires, décalage par rapport aux anciennes dates de débuts) / The operating theater is one of the most critical and expensive hospital resources. Indeed, a high percentage of hospital admissions are due to surgical interventions. Rising expenditures spur health care organizations to organize their processes more efficiently and effectively. This thesis is supported by the urban community of Sarreguemines-France and the region of Lorraine-France, and is carried out in collaboration with the Centre Hospitalier de Sarreguemines - Hôpital Robert Pax. In the first part of this work, we propose two mathematical programming models to help operating theater managers in developing an optimal operating rooms scheduling. We also propose a constructive heuristic to obtain near optimal results for realistic sizes of the problem. In the second part of our work, the whole scheduling process is modeled as a hybrid four-stage flow shop problem with RSb blocking constraint, and is solved by a genetic algorithm. The objective is to synchronize all the needed resources around the optimal daily schedule obtained with the proposed mathematical model. The last part of our work is dedicated to non-elective surgeries. We propose a decision support tool, guiding the operating room manager, to handle this unpredictable flow of patients. Non-elective patients are classified according to their medical priority. The main contribution of the proposed decision support tool is to provide online assignment strategies to treat each non elective patient category. Proposed assignments are riskless on patient’s health. According to non-elective surgery classes, the proposed adjusted schedule minimizes different criteria such as patient’s waiting time, deviation from the firstly scheduled starting time of a surgery and the amount of resulting overtime