Les structures d'hospitalisation rencontrent de nombreux problèmes de niveau opérationnel. Cette thèse propose une investigation des problématiques d'aide à la décision pour le pilotage des ressources humaines en HAD. Suite à l'étude des processus d'une structure HAD identifiant les différentes décisions logistiques dans le cadre d'une certification qualité, deux problématiques principales ont été identifiées. L'investigation du premier domaine, a permis de concevoir un outil d'aide à la décision calculant les emplois du temps des infirmiers d'une structure de soins à domicile. Il a été expérimenté pour l'HAD EOVI Drôme nord. Plusieurs modèles de décision ont été comparés à l'aide de deux méthodes de résolution : une résolution par programmation linéaire entière et une résolution par programmation par contraintes. Une deuxième problématique a été étudiée : le circuit du médicament d'une HAD, ceci en collaboration avec l'HAD Soins et Santé de Lyon afin de les aider dans la gestion de leurs livraisons urgentes à partir d'une pharmacie à usage intérieur. L'HAD rencontre en moyenne une quarantaine de livraisons urgentes par jour et ces livraisons coûtent très chers en raison des prestataires externes employés et des frais de taxi éventuels. Un outil d'aide à la décision décliné selon trois stratégies de livraisons différentes (par tranches horaires, par nombre de médicaments à livrer, par nombre de livraisons par tournées) a été développé et a été proposé à l'HAD. Une fois la stratégie choisie, cet outil a été utilisé en exploitant les données réelles de l'HAD pour comparer les coûts entre l'emploi de prestataires externes ou de livreurs salariés. Il a permis de démontrer que l'emploi de livreurs salariés serait nettement plus rentable.

Disponible dans le fichier attaché

Le regroupement des blocs opératoires au sein d'un Plateau Médico-Technique (PMT) présente des enjeux dans la phase de conception (dimensionnement des ressources et choix d'organisation) et dans la phase de pilotage (planification de l'activité et affectation des ressources humaines et matérielles) face auxquels les décideurs hospitaliers manquent d'outils. En réponse à ces besoins, cette thèse propose une démarche globale d'aide à la décision pour la conception du PMT et le pilotage des ressources humaines mutualisées de ce secteur. Cette démarche aborde trois principaux problèmes. Dans un premier temps, nous nous intéressons à la modélisation des processus de PMT existants, dont le but est de faire émerger un diagnostic et d'engager une démarche d'amélioration de la performance. Ces modèles sont réutilisés dans un second temps pour la modélisation des processus cibles qui nous permettent d'obtenir, par simulation de l'activité, les courbes de charge exprimant les besoins en personnel. Nous abordons la question du dimensionnement du personnel regroupé du PMT par la construction des vacations couvrant cette charge prévisionnelle, à l'aide de la Programmation Linéaire en Nombres Entiers (PLNE) couplée à la simulation de flux. Dans un troisième temps, nous étudions deux problèmes de planication d'horaires de travail : celui des infirmiers anesthésistes et celui des médecins anesthésistes, pour lesquels nous développons plusieurs approches de résolution basées sur la Programmation Linéaire Mixte (PLM) et sur la Programmation Par Contraintes (PPC), expérimentées et validées dans le cadre d'applications réelles.

Cette thèse s'intéresse aux problématiques fondamentales d'optimisation combinatoire qui se dégagent de la modélisation structurelle et algorithmique du dimensionnement des réseaux d'infrastructure de télécommunication. L'optimisation de ces réseaux est essentielle aux opérateurs de télécommunication, qui demandent la garantie d'une exploitation efficace des ressources déployées.<br /><br />Nous donnons une nouvelle modélisation des réseaux optiques WDM multifibres. En considérant un routage agrégé au niveau des câbles, nous optons pour une nouvelle lecture des contraintes d'affectation de longueurs d'onde fondée sur des conflits de groupe.<br /><br />Nous étudions aussi le problème de coloration de chemins, issu de l'affectation de longueurs d'onde dans les réseaux optiques monofibres. Nous développons, pour la relaxation linéaire de ce problème, un algorithme polynomial efficace dans les arbres de degré borné, puis, par extension, dans les graphes de largeur arborescente bornée. Nous majorons le coût d'une telle coloration dans les arbres binaires et donnons une (1+5/(3e)+o(1))-approximation aléatoire pour la coloration entière dans les arbres de degré borné, ce qui améliore le meilleur algorithme connu pour ce cas.<br /><br />Nous présentons enfin des avancées algorithmiques pour les problèmes de multiflot entier et fractionnaire. Nous donnons un algorithme d'arrondi aléatoire incrémental pour l'approximation du multiflot entier. Motivés par le besoin d'un calcul rapide de multiflot fractionnaire pour l'algorithme précédent, nous nous intéressons aux approximations combinatoires de ce problème. En employant des techniques de calcul dynamique des plus courts chemins, nous améliorons l'un des meilleurs algorithme de la littérature.<br />Webstats4U - Free web site statistics

Cette thèse s'inscrit dans le cadre du développement d'outils d'aide à la décision pour la configuration des lignes d'usinage modulaires à partir d'équipements standard. Le problème de configuration se pose en termes de sélection d'un sous-ensemble d'unités d'usinage et de leur affectation aux postes de travail définissant ainsi la structure de la ligne. Le problème revient à trouver la meilleure solution en termes de coût de mise en oeuvre en prenant en compte différents types de contraintes : productivité minimum à assurer, précédence, incompatibilité et capacité de stations et ligne. Le cœur de la thèse est dédié à l'étude des lignes avec un mode d'activation parallèle des unités d'usinage dans les stations. Dans ce cas, le début d'un cycle est marqué par l'enclenchement simultané de toutes les unités d'usinage de la ligne. Pour ce problème, nous avons proposé un modèle générique pour une approche par programmation par contraintes et deux modèles linéaires en nombres entiers.

Cette thèse CIFRE, en collaboration avec le constructeur automobile français PSA Peugeot Citroën, a pour but de proposer des solutions novatrices de gestion de production appliquée aux usines de mécanique, et plus particulièrement des politiques de planification et d'ordonnancement de la production des ateliers. Nous apportons des solutions pour résoudre la problématique de la planification de la production avec un redimensionnement des ressources au sein de l'usine de mécanique des amortisseurs. Nous étudions également la problématique de l'ordonnancement et du lissage de la production au sein des usines de mécanique des moteurs. Nous proposons deux approches différentes qui sont testées et comparées sur des données réelles. Nous proposons finalement un outil d'aide à la décision qui a pour objectif de fournir un ordonnancement des montages de moteurs tout en respectant les contraintes industrielles et le lissage de la production. Nos travaux ont été intégrés au sein du système d'information de PSA Peugeot Citroën. / This CIFRE thesis, in partnership with the French car manufacturer PSA Peugeot Citroën, aims to propose innovative solutions of production management applied to components manufacturing plants, and more particularly planning and scheduling policies of production workshops. We provide solutions for the production planning problem with a sizing of resources within a plant producing dampers. We also study the scheduling problem and production leveling problem in engines plants. We propose two different approaches which are tested and compared with real data. We finally propose a tool for decision support that aims to provide a scheduling of engines assembly workshops while respecting the industrial constraints and the production leveling. Our works have been integrated within the PSA Peugeot Citroen information system.

Dans un marché électrique concurrentiel, EDF a adapté ses outils de gestion de production pour permettre une gestion optimale de son portefeuille, particulièrement sur les horizons journaliers et infra-journaliers, derniers leviers pour une gestion optimisée de la production. Et plus l'horizon d'optimisation s'approche du temps réel, plus les décisions prises aux instants précédents deviennent structurantes voire limitantes en terme d'actions. Ces décisions sont aujourd'hui prises sans tenir compte du caractère aléatoire de certaines entrées du modèle. En effet, pour les décisions à court-terme, la finesse et la complexité des modèles déjà dans le cas déterministe ont souvent été un frein à des travaux sur des modèles tenant compte de l'incertitude. Pour se prémunir face à ces aléas, des techniques d'optimisation en contexte incertain ont fait l'objet des travaux de cette thèse. Nous avons ainsi proposé un modèle robuste de placement de la production tenant compte des incertitudes sur la demande en puissance. Nous avons construit pour cette fin un ensemble d'incertitude permettant une description fine de l'aléa sur les prévisions de demande en puissance. Le choix d'indicateurs fonctionnels et statistiques a permis d'écrire cet ensemble comme un polyèdre d'incertitude. L'approche robuste prend en compte la notion de coût d'ajustement face à l'aléa. Le modèle a pour objectif de minimiser les coûts de production et les pires coûts induits par l'incertitude. Ces coûts d'ajustement peuvent décrire différents contextes opérationnels. Une application du modèle robuste à deux contextes métier est menée avec un calcul du coût d'ajustement approprié à chaque contexte. Enfin, le présent travail de recherche se situe, à notre connaissance, comme l'un des premiers dans le domaine de la gestion optimisée de la production électrique à court terme avec prise en compte de l'incertitude. Les résultats sont par ailleurs susceptibles d'ouvrir la voie vers de nouvelles approches du problème. / Robust Optimization is an approach typically offered as a counterpoint to Stochastic Programming to deal with uncertainty, especially because it doesn't require any precise information on stochastic distributions of data. In the present work, we deal with challenging unit-commitment problem for the French daily electricity production under demand uncertainty. Our contributions concern both uncertainty modelling and original robust formulation of unit-commitment problem. We worked on a polyhedral set to describe demand uncertainty, using statistical tools and operational indicators. In terms of modelling, we proposed robust solutions that minimize production and worst adjustment costs due to uncertainty observation. We study robust solutions under two different operational contexts. Encouraging results to the convex unit-commitment problems under uncertainty are thus obtained, with intersting research topics for future work.

Le présent travail propose d’étudier les problèmes de coordination en se plaçant dans un contexte de planification decentralisée, partant du postulat qu’une gestion centralisée n’est pas pertinente au regard des enjeux de confidentialité qu’affichent chaque partenaire d’une même chaîne logistique. Plus précisément, l’objectif du travail réside dans l’élaboration d’un protocole de négociation tendant à rechercher une solution de planification « gagnant-gagnant », i.e. l’élaboration de plans satisfaisant le producteur (clients du service transport) tout en augmentant le profit des prestataires de transport. La méthodologie suivie pour le développement de ce travail s’articule autour de deux étapes. Le contexte de planification decentralisée des activités d’un producteur avec celles d’un opérateur de transport est dans un premier temps étudié. L’objectif est de caractériser les modèles de programmation linéaire et les raisonnement nécessaires au développement du protocole de coordination et à la mise en œuvre de la simulation du comportement des deux partenaires, de manière à mettre en exergue les facteurs influant la performance globale. L’expérimentation conduite dans ce cadre s’appuie sur la notion de plans d’expériences. Le problème est dans un second temps étendu à la coordination des activités de plusieurs opérateurs de transport avec un producteur. Dans ce nouveau contexte, la résolution du problème de répartition de charges de transport entre les différents acteurs est intégrée dans le processus de négociation. Les modèles et protocole ainsi enrichis sont validés sur la base de plusieurs cas de tests. / The present work aims to study the coordination problems in the context of decentralized planning, based on the postulate that centralized management is not suitable regarding the confidentiality objectives of each partner of the same supply chain. More specifically, the aim of this work is to develop a negotiation protocol seeking to reach a “win-win” planning solution, i.e. the development of plans satisfying the producer (the customer of transportation service) while increasing profit of transport operators. The development methodology of this work contains two phases. The context of decentralized planning of activities of one producer and one transport operator is firstly studied. The main objective is to characterize the linear programming models and the key determinants to develop the coordination protocol and also to implement the simulation of both partners in order to identify the factors affecting the overall performance. The conducted experimentation in this context is based on the concept of the design of experiments. The problem is extended in a second phase to the coordination of several transport operators with one producer. In this new context, the problem of allocating transport load to different transport operators is integrated into the negotiation process. The complemented models and protocol are validated based on test cases.

Les réseaux de transport optiques constituent aujourd'hui l'infrastructure de base des systèmes de communications modernes. Etant donné les investissements colossaux nécessaires au déploiement de ces réseaux, liés en particulier aux coûts des équipements (fibres optiques, cartes, transpondeurs,...), l'optimisation du routage et de l'allocation de ressources est indispensable pour maitriser les coûts d'exploitation. Dans ce contexte, ces travaux de thèse étudient un ensemble de problèmes d'allocation de ressources qui se posent lors de la planification des réseaux SDH (Synchronous Digital Hierarchy) et WDM (Wavelength Division Multiplexing), mais aussi lors de celle des réseaux multicouches basés sur une couche de transport optique. Dans un premier temps, nous étudions le problème du routage des circuits dans les réseaux SDH avec pour objectif principal de minimiser la fragmentation de la bande passante. Nous formulons ce problème comme un programme linéaire en nombres entiers intégrant un ensemble de contraintes réalistes de routage, de transmission et de brassage et utilisant des coûts de ressources granulaires. Un algorithme exact et deux heuristiques sont proposés pour résoudre ce problème. Nous abordons également le problème du reroutage des circuits SDH qui se pose aux opérateurs lorsqu'il devient indispensable de réduire la fragmentation de la bande passante. Nous montrons sur des instances réelles des problèmes étudiés que les méthodes proposées permettent des gains économiques considérables. Dans un deuxième temps, nous étudions deux problèmes de planification pour l'optimisation des réseaux WDM. Le premier problème est celui du design de la topologie logique, c'est à dire celui de la définition des circuits (chemins) optiques permettant de router un ensemble de demandes en trafic avec un coût de transpondeurs minimal. Le second problème est celui du routage et de l'affectation de longueurs d'onde: comment router les circuits optiques définis précédemment pour minimiser le nombre de longueurs d'onde utilisées tout en respectant un ensemble de contraintes technologiques? Nous formulons ces deux problèmes comme des programmes linéaires en nombres entiers et proposons des heuristiques efficaces, de type approximation successive pour le premier problème et utilisant une approche par décomposition pour le second problème. Là encore, les résultats expérimentaux montrent que les méthodes proposées permettent d'obtenir des approximations de qualité pour des instances de très grandes tailles. Enfin, nous abordons l'allocation de ressources dans les réseaux multicouches de nouvelle génération IP/MPLS sur OTN (Optical Transport Network) sur DWDM (Dense WDM). Dans ce cas, la question à laquelle la majorité des opérateurs cherchent une réponse est celle du routage des demandes en trafic de niveau 3 permettant d'optimiser l'allocation des ressources non seulement dans la couche IP/MPLS mais aussi dans les couches sous-jacentes OTN et DWDM. Pour répondre à cette question, nous proposons un nouveau modèle d'optimisation multicouche qui tient compte d'une hiérarchie de contraintes matérielles et définit un compromis entre les coûts des ressources dans les trois couches de réseau. L'ensemble des algorithmes d'optimisation proposés ont été intégrés dans l'environnement de planification et d'optimisation de réseaux NEST de la société QoS Design, utilisé par de grands opérateurs pour planifier leurs réseaux. / Optical transport networks currently constitute base infrastructures for modern day telecommunications systems. Given the huge investments required for deploying these networks, and in particular concerning equipment costs (fiber optics, cards, transponders, etc.), routing optimization and resource allocation are indispensable issues for mastering the operational expenditures (OPEX). In this context, the work conducted in this thesis handle a set of resource allocation problems which arise while planning not only optical SDH (Synchronous Digital Hierarchy) and WDM (Wavelength Division Multiplexing) networks, but also multilayer ones based on an optical transport layer. First, the circuit routing problem in SDH networks is tackled with the main objective of minimizing the bandwidth fragmentation. This problem is formulated as an Integer Linear Program (ILP) integrating a set of realistic routing, transmission and cross-connect constraints and using granular resource costs. An exact algorithm and two heuristics are proposed to solve this problem. The rerouting problem of SDH circuits, which faces operators when it becomes absolutely necessary to reduce the bandwidth fragmentation in the network, is also addressed. For real instances of the studied problems, it is shown that the proposed methods provide considerable economic gains. Second, two planning problems for WDM network optimization is tackled. The first problem is that of the logical network design, or in other words that concerned with the definition of lightpaths to route a set of traffic demands with a minimum transponder cost. The second problem is related to the routing and the wavelength assignment: how to route the previously defined lightpaths so as to minimize the total number of assigned wavelengths while respecting a set of technological constraints? These two problems are formulated as Integer Linear Programs (ILPs) and are solved using efficient heuristics, based on a successive approximation for the first problem and a decomposition approach for the second one. Here again, experimental results show that the proposed methods allow obtaining good quality approximations for large scale instances. Finally, resource allocation in new generation multilayer networks, that is IP/MPLS over OTN (Optical Transport Network) over DWDM (Dense WDM), is addressed. In this case, the question that most of the operators seek to answer is how to route layer 3 traffic demands while optimizing resource allocation, not only in the IP/MPLS layer, but also in the underlying OTN and DWDM layers. For this purpose, a new multilayer optimization model is proposed. It takes into account a hierarchy of material constraints and defines a tradeoff between the resource costs in the three network layers. The set of proposed optimization algorithms have been integrated into the network planning and optimization environment NEST of QoS Design, which is used by major operators to plan their network.

Dans cette thèse, nous étudions des Hoist Scheduling Problems (HSP) qui se posent fréquemment dans des lignes automatiques de traitement de surface. Dans ces lignes, des ponts roulants sont utilisés pour transporter les pièces entre les bains. Ainsi, les ponts roulants jouent un rôle essentiel dans la performance de ces lignes ; et un ordonnancement optimal de leurs mouvements est un facteur déterminant pour garantir la qualité des produits et maximiser la productivité. Les lignes que nous étudions comportent un seul pont roulant mais peuvent être des lignes de base ou des lignes étendues (où des bains sont à fonctions et/ou capacités multiples). Nous examinons trois Hoist Scheduling Problems : l’optimisation robuste d’un HSP cyclique, l’ordonnancement dynamique d’une ligne étendue de type job shop et l’ordonnancement cyclique d’une telle ligne.Pour l’optimisation robuste d’un HSP cyclique, nous définissons la robustesse comme la marge dans le temps de déplacement du pont roulant. Nous formulons le problème en programmation linéaire en nombres mixtes à deux objectifs pour optimiser simultanément le temps de cycle et la robustesse. Nous démontrons que le temps de cycle minimal augmente avec la robustesse, et que par conséquent la frontière Pareto est constituée d’une infinité de solutions. Les valeurs minimales et maximales des deux objectifs sont établies. Les résultats expérimentaux à partir de benchmarks et d’instances générées aléatoirement montrent l’efficacité de l’approche proposée.Nous étudions ensuite un problème d’ordonnancement dynamique dans une ligne étendue de type job shop. Nous mettons en évidence une erreur de formulation dans une un modèle existant pour un problème similaire mais sans bains multi-fonctions. Cette erreur peut rendre l’ordonnancement obtenu sous-optimal voire irréalisable. Nous construisons un nouveau modèle qui corrige cette erreur. De plus il est plus compact et s’applique au cas avec des bains à la fois à capacités et à fonctions multiples. Les résultats expérimentaux menés sur des instances avec ou sans bains multi-fonctions montrent que le modèle proposé conduit toujours à une solution optimale et plus efficace que le modèle existant.Nous nous focalisons enfin sur l’ordonnancement cyclique d’une ligne étendue de type job shop avec des bains à fonctions et capacités multiples. Nous construisons un modèle mathématique en formulant les contraintes de capacité du pont roulant, les intervalles des durées opératoires, et les contraintes de capacité des bains. Nous établissons également des contraintes valides. Les expériences réalisées sur des instances générées aléatoirement montrent l’efficacité du modèle proposé. / This thesis studies hoist scheduling problems (HSPs) arising in automated electroplating lines. In such lines, hoists are often used for material handing between tanks. These hoists play a crucial role in the performance of the lines and an optimal schedule of the hoist operations is a key factor in guaranteeing product quality and maximizing productivity. We focus on extended lines (i.e. with multi-function and/or multi-capacity tanks) with a single hoist. This research investigates three hoist scheduling problems: robust optimization for cyclic HSP, dynamic jobshop HSP in extended lines and cyclic jobshop HSP in extended lines.We first study the robust optimization for a cyclic HSP. The robustness of a cyclic hoist schedule is defined in terms of the free slacks in hoist traveling times. A bi-objective mixed-integer linear programming (MILP) model is developed to optimize the cycle time and the robustness simultaneously. It is proved that the optimal cycle time strictly increases with the robustness, thus there is an infinite number of Pareto optimal solutions. We established lower and upper bounds of these two objectives. Computational results on several benchmark instances and randomly generated instances indicate that the proposed approach can effectively solve the problem.We then examine a dynamic jobshop HSP with multifunction and multi-capacity tanks. We demonstrate that an existing model for a similar problem can lead to suboptimality. To deal with this issue, a new MILP model is developed to generate an optimal reschedule. It can handle the case where a multi-function tank is also multi-capacity. Computational results on instances with and without multifunction tanks indicate that the proposed model always yields optimal solutions, and is more compact and effective than the existing one.Finally, we investigate a cyclic jobshop HSP with multifunction and multi-capacity tanks. An MILP model is developed for the problem. The key issue is to formulate the time-window constraints and the tank capacity constraints. We adapt the formulation of time-window constraints for a simpler cyclic HSP to the jobshop case. The tank capacity constraints are handled by dealing with the relationships between hoist moves so that there is always an empty processing slot for new parts. Computational experiments on numerical examples and randomly generated instances indicate that the proposed model can effectively solve the problem.