Dans cette thèse nous considérons une classe de problèmes d’optimisation ayant une particularité : des décisions à la fois discrètes et continues doivent être prises simultanément. Ces problèmes se posent dans de nombreuses applications pratiques, comme par exemple dans les réseaux de télécommunications à large bande passante et dans les problèmes de transport écologique, où les ressources disponibles peuvent être très légèrement consommées ou réparties. Ces problèmes se sont avérés être plus difficiles à résoudre que leurs homologues purement discrets. Des méthodes efficaces pour la résolution de ces problèmes sont proposées dans cette thèse. Notre approche est de prendre en compte des variantes de problèmes classiques d’optimisation combinatoire appartenant à trois domaines : packing, routage et routage/ packing intégré. Les résultats obtenus suggèrent l’existence de méthodes efficaces, réduisant l’effort de calcul nécessaire pour résoudre ce type de problème. La plupart du temps, ces méthodes sont basées sur l’exploitation de la structure des solutions optimales pour réduire l’espace de recherche. / In this thesis we consider a class of optimization problems having adistinctive feature : both discrete and continuous decisions need to betaken simultaneously. These problems arise in many practical applications,for example broadband telecommunications and green transportation problems, where resources are available, that can be fractionally consumed or assigned. These problems are proven of being harder than their purely discrete counterpart. We propose effective methodologies to tackle them. Our approach is to consider variants of classical combinatorial optimization problems belonging to three domains : packing, routing, and integrated routing / packing. Our results suggest that indeed effective approaches exist, reducing the computational effort required for solving the problem. Mostly, they arebased on exploiting the structure of optimal solutions to reduce the search space. / In questa tesi affrontiamo una classe di problemi di ottimizzazione con una caratteristica in comune : sia le decisioni discrete che quelle continue devono essere prese simultaneamente. Questi problemi emergono in molti campi, come ad esempio le nelle telecomunicazioni abanda larga e in problemi di trasporto ecologico, dove le risorse disponibili possono essere consumate o assegnate in modo frazionario.Questi problemi sono generalmente più difficili da risolvere rispetto alla loro controparte puramente combinatoria. Noi proponiamo metodologie efficaci per affrontarli. Con il nostro approccio consideriamo varianti di problemi classici nel campo dell’ottimizzazione combinatoriache appartengono a tre domini : impaccamento, instradamento einstradamento / impaccamento integrati. I nostri risultati suggeriscono l’esistenza di approcci efficienti che riducono lo sforzo computazionale necessario per risolvere questi problemi. Nella maggior parte deicasi, tali approcci sono basati sullo sfruttamento di particolari proprietà della struttura delle soluzioni ottime in modo da ridurre lo spaziodi ricerca.

Thèses (LL.M.)--Université de Sherbrooke (Canada), 1997. / Titre de l'écran-titre (visionné le 19 juillet 2006). Publié aussi en version papier.

Titre de l'écran-titre (visionné le 4 décembre 2023) / Nous étudions un problème apparaissant dans le système de santé qui consiste à affecter des chirurgiens à des salles d'opération d'un hôpital. Ce problème se survient notamment à l'Hôpital Général de Brockville et nous a été rapporté par notre partenaire industriel : Thales Digital Canada. L'affectation des chirurgiens à des salles d'opération est sujette à différentes contraintes. Les salles doivent être adéquatement équipées pour combler les besoins du chirurgien. La demande pour chaque spécialité de chirurgien doit être couverte. Les salles d'opération doivent être utilisées à leur plein potentiel. Finalement, les chirurgiens devraient avoir des horaires réguliers, c'est-à-dire qu'ils doivent être les plus semblables possible d'une semaine à l'autre. Ce problème a été étudié dans la littérature scientifique, mais comme c'est souvent le cas avec les problèmes de recherche opérationnelle en milieu médical, ce problème a seulement été étudié avec des variations qui ne conviennent pas à l'Hôpital Général de Brockville. Conséquemment, nous expliquons ce qui est fait de façon similaire et ce qui est fait différemment dans la littérature. Ce mémoire présente une méthodologie qui utilise la programmation par contraintes pour affecter des chirurgiens à des salles d'opération. Un logiciel spécialisé a été développé pour créer des horaires de tailles variables. Ce logiciel prend en entrée un ensemble de besoins et affecte ensuite les chirurgiens aux salles d'opération. Une recherche à voisinage large améliore itérativement la solution jusqu'à ce que sa qualité soit satisfaisante. Les expériences que nous avons conduites démontrent que l'on obtient une solution satisfaisante en seulement quelques minutes. Ces horaires améliorent significativement le taux d'utilisation des salles d'opération. Nous avons comparé deux versions de notre logiciel et nous avons démontré qu'aucune ne domine l'autre. Nous proposons comme travaux futurs de combiner ces deux versions en une seule afin de tirer avantage des deux techniques. / We study a problem arising in the health system that consists of assigning surgeons to operating rooms in a hospital. This problem occurs at the Brockville General Hospital and was brought to us by our industrial partner Thales Digital Canada. The assignment of surgeons to operating rooms is subject to different constraints. The rooms must be properly equipped to satisfy the needs of the surgeon. The demand for each surgeon specialty must be fulfilled. The operating room should be used at their full potential. Finally, surgeons should have regular schedules, i.e. they should have similar schedules week after week. This problem is studied in the literature, but as it is often the case with operation research problems that occur in the health system, it was studied with variations that are not suited for the Brockville General Hospital. We therefore explain what is done similarly and what is done differently in the literature. This thesis introduces a methodology that utilizes constraint programming to allocate operating rooms to surgeons. A specialized software has been developed to create schedules of variable lengths. This software takes as input a set of requirements and generates a schedule that assign surgeons to operating rooms. A Large Neighbourhood Search iteratively improves the solution until the quality of the solution is satisfactory. The experiments conducted demonstrate that one can obtain satisfactory results in a few minutes. These schedules significantly enhance the utilization rate of operating rooms. We compared two versions of our software and showed that none dominates the other. However, we propose as a future work that these two versions could be combined into one in order to take advantage of both techniques.

La transformation numérique et le mouvement « industrie 4.0 » reposent sur des concepts tels que l'intégration et l'interconnexion des systèmes utilisant des données en temps réel. Dans le secteur manufacturier, un nouveau paradigme d'allocation dynamique des ressources humaines devient alors possible. Plutôt qu'une allocation statique des opérateurs aux machines, nous proposons d'affecter directement les opérateurs aux différentes tâches qui nécessitent encore une intervention humaine dans une usine majoritairement automatisée. Nous montrons les avantages de ce nouveau paradigme avec des expériences réalisées à l'aide d'un modèle de simulation à événements discrets. Un modèle d'optimisation qui utilise des données industrielles en temps réel et produit une allocation optimale des tâches est également développé. Nous montrons que l'allocation dynamique des ressources humaines est plus performante qu'une allocation statique. L'allocation dynamique permet une augmentation de 30% de la quantité de pièces produites durant une semaine de production. De plus, le modèle d'optimisation utilisé dans le cadre de l'approche d'allocation dynamique mène à des plans de production horaire qui réduisent les retards de production causés par les opérateurs de 76 % par rapport à l'approche d'allocation statique. Le design d'un système pour l'implantation de ce projet de nature 4.0 utilisant des données en temps réel dans le secteur manufacturier est proposé. / The Industry 4.0 movement is based on concepts such as the integration and interconnexion of systems using real-time data. In the manufacturing sector, a new dynamic allocation paradigm of human resources then becomes possible. Instead of a static allocation of operators to machines, we propose to allocate the operators directly to the different tasks that still require human intervention in a mostly automated factory. We show the benefits of this new paradigm with experiments performed on a discrete-event simulation model based on an industrial partner's system. An optimization model that uses real-time industrial data and produces an optimal task allocation plan that can be used in real time is also developed. We show that the dynamic allocation of human resources outperforms a static allocation, even with standard operator training levels. With discrete-event simulation, we show that dynamic allocation leads to a 30% increase in the quantity of parts produced. Additionally, the optimization model used under the dynamic allocation approach produces hourly production plans that decrease production delays caused by human operators by up to 76% compared to the static allocation approach. An implementation system for this 4.0 project using real-time data in the manufacturing sector is furthermore proposed.

Thèse (Ph. D.)--Université Laval, 2007. / Titre de l'écran-titre (visionné le 5 mai 2008). Bibliogr.

Cette thèse propose un outil d’aide à la décision pour la gestion de processus de maintenance basée surune affectation optimale des ressources humaines afin d’améliorer la performance de la maintenance.En effet, une bonne performance de la fonction maintenance est indispensable pour maintenir laproductivité des installations industrielles, et donc de la compétitivité des entreprises manufacturières.L’approche que nous développons dans ce manuscrit procure un cadre de référence des leviersd’actions envisageables pour mesurer, évaluer, améliorer et optimiser la performance de lamaintenance. Nous prenons en considération un problème d’affectation des ressources humaines, quiprend en compte non seulement leurs disponibilités et compétences, mais aussi la gestion des urgencesd’intervention sur terrain.La méthode que nous proposons est basée sur un modèle de simulation à événements discrets,reproduisant au mieux un service de maintenance. Ceci nous a permis d’évaluer la situation via desindicateurs de performance présélectionnés. Pour optimiser le système, nous proposons un couplagedu modèle de simulation avec un module d’optimisation indépendant qui se réfère à une métaheuristiquebasée sur une approche Pareto. Notre proposition a été testée dans une entrepriseindustrielle réelle.L’approche que nous proposons donne un ensemble de solutions d’affectation des ressourceshumaines, aidant le décideur à mieux gérer l’indisponibilité de ses outils. Nous obtenons de bonsrésultats en un temps raisonnable. / In this thesis, a decision-making tool for maintenance management process based on assignment ofhuman resources is proposed in order to improve maintenance performance. An optimal maintenanceperformance is indispensable to guarantee the productivity and competitiveness of manufacturingcompanies.The proposed approach provides a framework of different possible levers to measure, evaluate,improve and optimize the maintenance performance. The assignment of human resources problem isconsidered. It takes into account different constraints like human resources availability, competences,urgency degree management of interventions requests etc.The proposed method is based on a discrete event simulation model, providing a better presentation ofthe maintenance service and better comprehensive thanks to the performance indicators. To improveuntil optimize the model, a simulation-based Pareto optimization method is introduced. Optimizationmodule was coded on independent programs in order to provide an opportunity of control thesimulation based optimization process.The proposed simulation based optimization method find good solutions in a reasonable amount oftime. Applying this technique on an industrial case-study, we show that it is more effective indetecting real faults than existing alternatives. The approach can be extended to cover other domainsand other types of simulation models.

La gestion des activités de distribution dans le secteur forestier pose un enjeu de taille en raison de la décentralisation de la prise de décision, l'incertitude sur les opérations de production et la quantité massive de données. Dans ce contexte, le but de ce mémoire est de concevoir un système d'aide à la décision pour l'allocation de la production et la planification du transport. Il vise également à évaluer une approche à flux poussé-tiré de gestion de la chaîne de valeur. Ce projet est réalisé en collaboration avec Produits forestiers Résolu, permettant l'évaluation des solutions dans un cadre réel de grande envergure. Pour atteindre ces objectifs, une analyse du contexte de l'organisation a d'abord mis en évidence les modes de fonctionnement de l'entreprise, les caractéristiques d'un réseau de distribution dans l'industrie forestière et les interactions interdépartementales. Une revue de la littérature a ensuite été réalisée afin d'établir un état de l'art sur les approches de résolution des problèmes d'allocation, les mécanismes de coordinations et les stratégies d'intégration. Suite à l'acquisition et le traitement des données de l'entreprise, deux outils d'aide à la décision ont été développés pour des activités critiques de l'entreprise, actuellement réalisées entièrement manuellement. Un premier outil permet de déterminer l'allocation optimale des commandes aux centres de production et de distribution. La mise en œuvre de cet outil pour l'entreprise permet de réduire les coûts de transport jusqu'à 7.2%. Ce modèle permet également d'évaluer l'effet d'une stratégie hybride de flux poussé-tiré sur la performance de l'entreprise. Le second outil permet d'optimiser la sélection de routes et de transporteurs ferroviaires pour la distribution de marchandises dans le réseau nord-américain, pouvant conduire à une réduction des coûts de l'ordre de 6.6%. Finalement, le projet a permis de démontrer qu'il est possible pour l'entreprise de déplacer son point de découplage en amont du rabotage. L'intégration des deux modèles dans une stratégie hybride de production et distribution permet des économies de 12.3%. Ces résultats ont stimulé une réflexion stratégique chez le partenaire afin de revoir sa gestion des opérations de production, de distribution et de ventes. Ce travail contribue ainsi au domaine en évaluant les effets d'une approche à flux poussé-tiré ainsi que des outils pour faciliter la prise de décision dans un cas d'études du secteur forestier tout en répondant aux besoins pratiques du partenaire industriel.

La gestion des activités de distribution dans le secteur forestier pose un enjeu de taille en raison de la décentralisation de la prise de décision, l'incertitude sur les opérations de production et la quantité massive de données. Dans ce contexte, le but de ce mémoire est de concevoir un système d'aide à la décision pour l'allocation de la production et la planification du transport. Il vise également à évaluer une approche à flux poussé-tiré de gestion de la chaîne de valeur. Ce projet est réalisé en collaboration avec Produits forestiers Résolu, permettant l'évaluation des solutions dans un cadre réel de grande envergure. Pour atteindre ces objectifs, une analyse du contexte de l'organisation a d'abord mis en évidence les modes de fonctionnement de l'entreprise, les caractéristiques d'un réseau de distribution dans l'industrie forestière et les interactions interdépartementales. Une revue de la littérature a ensuite été réalisée afin d'établir un état de l'art sur les approches de résolution des problèmes d'allocation, les mécanismes de coordinations et les stratégies d'intégration. Suite à l'acquisition et le traitement des données de l'entreprise, deux outils d'aide à la décision ont été développés pour des activités critiques de l'entreprise, actuellement réalisées entièrement manuellement. Un premier outil permet de déterminer l'allocation optimale des commandes aux centres de production et de distribution. La mise en œuvre de cet outil pour l'entreprise permet de réduire les coûts de transport jusqu'à 7.2%. Ce modèle permet également d'évaluer l'effet d'une stratégie hybride de flux poussé-tiré sur la performance de l'entreprise. Le second outil permet d'optimiser la sélection de routes et de transporteurs ferroviaires pour la distribution de marchandises dans le réseau nord-américain, pouvant conduire à une réduction des coûts de l'ordre de 6.6%. Finalement, le projet a permis de démontrer qu'il est possible pour l'entreprise de déplacer son point de découplage en amont du rabotage. L'intégration des deux modèles dans une stratégie hybride de production et distribution permet des économies de 12.3%. Ces résultats ont stimulé une réflexion stratégique chez le partenaire afin de revoir sa gestion des opérations de production, de distribution et de ventes. Ce travail contribue ainsi au domaine en évaluant les effets d'une approche à flux poussé-tiré ainsi que des outils pour faciliter la prise de décision dans un cas d'études du secteur forestier tout en répondant aux besoins pratiques du partenaire industriel.

Un problème d'ordonnancement de projet à ressources limitées (POPRL) consiste en l'ordonnancement d'un ensemble de tâches, nécessitant un ou plusieurs types de ressources, renouvelables ou non renouvelables, en quantités limitées. La résolution d'un POPRL a pour but la détermination des dates d'exécution des tâches en tenant compte des contraintes de préséance et de disponibilité des ressources et ayant comme objectif la minimisation de la durée totale du projet. Le POPRL est un problème d'optimisation combinatoire de complexité NP-dur (Blazewicz et al. 1983). Une revue de littérature du (POPRL) est présentée au chapitre 2. Plus de 125 articles scientifiques sont analysés. Les contributions relatives à ce problème portent sur les méthodes exactes de résolution, la détermination de bornes inférieures sur la durée du projet et les méthodes heuristiques (approchées) de résolution. L'aspect pratique de ce problème dans des contextes industriels divers a conduit à de nombreuses généralisations du problème classique. On constate que malgré les efforts déployés pour définir des POPRL plus généraux, les contraintes de transfert des ressources continuent à être ignorées, nous constatons aussi que l'optimisation du problème en considérant les coûts a été très peu traitée dans la littérature. Ce qui forcent les gestionnaires dans la plus part des cas à se baser uniquement sur leur expérience pour réaliser ou ajuster manuellement les ordonnancements produits par des heuristiques conçues pour résoudre des versions simplifiées du problème. Cette thèse tente de combler partiellement ces lacunes. Le chapitre 3 traite le problème d'ordonnancement de projet à ressources limitées POPRLTT avec des temps de transfert des ressources. Un temps de transfert est le temps nécessaire pour transférer une ressource du lieu d'execution d'une activité vers un autre. Ainsi, le temps de transfert d'une ressource dépend des lieux des activités à exécuter, ainsi que des caractéristiques des ressources à transférer. L'objectif dans un POPRLTT est la détermination des dates d'exécution des tâches en tenant compte des contraintes de préséance et de disponibilité des ressources et les temps de transfert des ressources. L'objectif est de minimiser la durée totale du projet. Nous proposons un nouvel algorithme génétique basé sur un opérateur de croisement de deux positions. L'étude expérimentale menée sur un grand nombre de problèmes test prouve que l'algorithme proposé est meilleur que les deux méthodes déjà existantes dans la littérature. Une généralisation du problème d'ordonnancement de projet à ressources limitées et des temps de transfert des ressources au contexte multi mode (POPRL=PMETT) est présentée au chapitre 4. Dans ce problème, nous supposons que la préemption est non autorisée, et les ressources utilisées sont renouvelables et non renouvelables, chaque activité a plusieurs modes d'exécution, et les relations de préséance sont de type dit début-fin sans décalage. L'objectif est de choisir un temps de début (ou de fin) et un mode d'exécution pour chaque tâche du projet, pour que la durée du projet soit minimisée tout en respectant les contraintes de préséance, de disponibilité de ressources et les temps de transfert. Au meilleur de notre connaissance, cette version du problème n'a jamais été abordée auparavant. Nous proposons une formulation mathématique de ce problème, ensuite nous présentons un algorithme génétique, que nous avons conçu pour résoudre les instances de grandes tailles. Pour tester les méthodes proposées nous développons des nouveaux ensembles de problèmes-tests pour le POPRL=PMETT, qui pourront être utilisés dans l'avenir pour mener des recherches dans ce domaine. Dans le chapitre 5, nous définissons une nouvelle généralisation du problème d'ordonnancement de projet à ressources limitées en considérant l'objectif de minimiser le coût total d'exécution du projet. Celui-ci est composé de deux éléments principaux: le coût direct des ressources à utiliser et les frais généraux qui ne dépendent pas de la quantité de ressources allouées, mais qui sont proportionnels à la durée du projet. Ce problème, que nous appelons Problème général d'allocation et de nivellement des ressources d'un projet (PGANRP) est très commun en pratique, mais très peu de recherche est consacrée à ce problème. Dans un PGANRP, nous devons simultanément déterminer les quantités des ressources à allouer au projet au cours de son exécution et réduire la variabilité de l'utilisation des ressources au minimum tout en essayant de terminer le projet à une date de fin acceptable. Les quantités des ressources à allouer au projet devraient permettre l'accomplissement du projet à cette date et devient une limite sur la disponibilité de ces ressources durant toute l'exécution du projet. Nous proposons, une formulation mathématique du problème et deux approches de recherche dans le voisinage pour les instances de grandes tailles. / The resource-constrained project scheduling problem (RCPSP) consists of scheduling a set of activities or tasks using one or more resource types available in limited quantity. In the standard version of this problem, pre-emption is not allowed, precedence relations are of the no-lag, finish-to-start type, and the used resources are renewable meaning that the same resources quantity are available each time period. Solving this NP-hard optimization problem requires the determination of tasks execution date such that the project duration is minimized without using more than the available resource quantities. In the first chapter of this thesis, the research problem and research objectives are presented while chapter 2 reviews the literature and contributions to the RCPSP and some of its extended versions. More than 125 published papers are reviewed. These contributions are divided into 4 groups of contributions. Those proposing optimal solution methods, those developing lower bounds on the project duration, those proposing heuristic and approximate solution methods, and those extending the standard version of the problem in order to make it closer to the real-life problem. This literature review revealed that very few contributions explicitly take into consideration the time required to transfer resources between execution sites of the project. Only three such contributions are published and none of these three publication deal with the case where tasks have more than one execution mode. This review also revealed that the large majority of the published research deals with the problem where the objective is to minimize the duration of the project. However, in almost all real-life situations, the objective is to minimise the total cost of the project. That is why this thesis is dedicated to solve these neglected extensions of the RCPSP. Chapter 3 deals with the resource-constrained project scheduling problem with transfer times (RCPSPTT). Thus the goal in this case is to determine execution dates that allows for resources to be transferred between execution sites while respecting the precedence relations between these tasks as well as resources availability. A new genetic algorithm (GA) is developed to solve the RCPSPTT. This algorithm uses a new and efficient crossover operator. The chapter also study the performance of the proposed genetic algorithm and shows that it produces better results than the two previously published solution heuristics. It is to notice that the proposed GA considers renewable resource types and assume that tasks have only one execution mode. Chapter 4 deals with the multi-mode resource-constrained project scheduling problem with transfer times (MRCPSPTT). Thus, it extends the problem studied in the previous chapter to the multi-mode case under the assumptions of no pre-emption while using renewable and non-renewable resources. This problem has never been the subject of any published research before. An integer linear mathematical formulation of the problem is given as well as new genetic algorithm is developed to solve it. An extensive empirical analysis is then presented and shows that the proposed GA is able to produce the optimal solution for 529 test instances with 10, 20 and 30 activities. Chapter 5 introduces the generalized resource allocation and leveling problem (GRALP). This problem can be stated as follows. Given a set of project tasks to execute, their possible execution modes and precedence relations, an upper bound on the amount of resources that can be made available to the project, a project due date, the cost of resource utilization and the overhead cost; determine the execution date and mode for each task and the amount of resources to allocate to the project. The objective is to minimize the total project execution cost while respecting precedence constraints, project due date and not using more than the amount of resources that we decided to allocate to the project. Again we notice that this problem has never been the subject of any published research work. Chapter 5 presents an integer linear formulation of the problem, a neighborhood search solution heuristic, a genetic algorithm to solve it and an empirical experiment to evaluate the proposed heuristics showing the superiority of the proposed GA. Finally, the conclusions of the thesis and some propositions for future research are given.

Les problèmes militaires sont très complexes et plusieurs d'entre eux ne peuvent être résolues en utilisant les techniques d'optimisation classiques. Le problème visé par ce travail de maîtrise, est celui de la gestion en temps réel des ressources d'une frégate. Ces ressources doivent être assignées convenablement et dans les délais requis de manière à contrer les menaces et augmenter ainsi la probabilité de survie de la frégate. Pour contribuer à résoudre un tel problème, nous avons convenu tout d'abord, d'analyser les menaces une à une et de déterminer lesquelles sont les plus importantes et quel plan d'attaque il convient d'élaborer pour les contrer. Nous avons introduit à cet effet, l'évaluation de ``l'engageabilité'' qui permet de considérer différents facteurs déterminants dans l'allocation des ressources. Nous avons ensuite formalisé le problème en question, en utilisant un modèle formel emprunté à la satisfaction des contraintes (CSP=constraint Satisfaction problem). Finalement, nous avons montré dans quelles circonstances il est avantageux d'utiliser cette évaluation de l'engageabilité dans un processus d'allocation de ressources en temps réel et dans un environnement stochastique, le tout relativement à la survie de la frégate. / Military problems are very complex and they can be solved by different artificial intelligence techniques. In this thesis, we address the problem of weapon-targets assignment for a frigate. To defend efficiently the ship, we have to analyze each threat and determine which resource assigns against it. For that purpose, we utilize the engageability assessment to consider different characteristics; useful in the resources assignment. To this end, a mathematical model named Constraint Satisfaction Problem (CSP) is employed. This framework allows formalizing the problem to ensure the constraint consistency and to sort threats in importance order. We tried this algorithm on different types of weapon-target assignment problems. Finally, we demonstrate the advantage of engageability assessment on the weapon-target assignment problem in real time and stochastic environment.