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.

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.

L’allocation de ressources est un problème omniprésent qui survient dès que des ressources limitées doivent être distribuées parmi de multiples agents autonomes (e.g., personnes, compagnies, robots, etc). Les approches standard pour déterminer l’allocation optimale souffrent généralement d’une très grande complexité de calcul. Le but de cette thèse est de proposer des algorithmes rapides et efficaces pour allouer des ressources consommables et non consommables à des agents autonomes dont les préférences sur ces ressources sont induites par un processus stochastique. Afin d’y parvenir, nous avons développé de nouveaux modèles pour des problèmes de planifications, basés sur le cadre des Processus Décisionnels de Markov (MDPs), où l’espace d’actions possibles est explicitement paramétrisés par les ressources disponibles. Muni de ce cadre, nous avons développé des algorithmes basés sur la programmation dynamique et la recherche heuristique en temps-réel afin de générer des allocations de ressources pour des agents qui agissent dans un environnement stochastique. En particulier, nous avons utilisé la propriété acyclique des créations de tâches pour décomposer le problème d’allocation de ressources. Nous avons aussi proposé une stratégie de décomposition approximative, où les agents considèrent des interactions positives et négatives ainsi que les actions simultanées entre les agents gérants les ressources. Cependant, la majeure contribution de cette thèse est l’adoption de la recherche heuristique en temps-réel pour l’allocation de ressources. À cet effet, nous avons développé une approche basée sur la Q-décomposition munie de bornes strictes afin de diminuer drastiquement le temps de planification pour formuler une politique optimale. Ces bornes strictes nous ont permis d’élaguer l’espace d’actions pour les agents. Nous montrons analytiquement et empiriquement que les approches proposées mènent à des diminutions de la complexité de calcul par rapport à des approches de planification standard. Finalement, nous avons testé la recherche heuristique en temps-réel dans le simulateur SADM, un simulateur d’allocation de ressource pour une frégate. / Resource allocation is an ubiquitous problem that arises whenever limited resources have to be distributed among multiple autonomous entities (e.g., people, companies, robots, etc). The standard approaches to determine the optimal resource allocation are computationally prohibitive. The goal of this thesis is to propose computationally efficient algorithms for allocating consumable and non-consumable resources among autonomous agents whose preferences for these resources are induced by a stochastic process. Towards this end, we have developed new models of planning problems, based on the framework of Markov Decision Processes (MDPs), where the action sets are explicitly parameterized by the available resources. Given these models, we have designed algorithms based on dynamic programming and real-time heuristic search to formulating thus allocations of resources for agents evolving in stochastic environments. In particular, we have used the acyclic property of task creation to decompose the problem of resource allocation. We have also proposed an approximative decomposition strategy, where the agents consider positive and negative interactions as well as simultaneous actions among the agents managing the resources. However, the main contribution of this thesis is the adoption of stochastic real-time heuristic search for a resource allocation. To this end, we have developed an approach based on distributed Q-values with tight bounds to diminish drastically the planning time to formulate the optimal policy. These tight bounds enable to prune the action space for the agents. We show analytically and empirically that our proposed approaches lead to drastic (in many cases, exponential) improvements in computational efficiency over standard planning methods. Finally, we have tested real-time heuristic search in the SADM simulator, a simulator for the resource allocation of a platform.