Thèse (de doctorat)--Université Laval, 2008. / Titre de l'écran-titre (visionné le 12 janvier 2009). Bibliogr.

Face à la complexité qui caractérise les problèmes d'optimisation de grande taille l'exploration complète de l'espace des solutions devient rapidement un objectif inaccessible. En effet, à mesure que la taille des problèmes augmente, des méthodes de solution de plus en plus sophistiquées sont exigées afin d'assurer un certain niveau d 'efficacité. Ceci a amené une grande partie de la communauté scientifique vers le développement d'outils spécifiques pour la résolution de problèmes de grande taille tels que les méthodes hybrides. Cependant, malgré les efforts consentis dans le développement d'approches hybrides, la majorité des travaux se sont concentrés sur l'adaptation de deux ou plusieurs méthodes spécifiques, en compensant les points faibles des unes par les points forts des autres ou bien en les adaptant afin de collaborer ensemble. Au meilleur de notre connaissance, aucun travail à date n'à été effectué pour développer un cadre conceptuel pour la résolution efficace de problèmes d'optimisation de grande taille, qui soit à la fois flexible, basé sur l'échange d'information et indépendant des méthodes qui le composent. L'objectif de cette thèse est d'explorer cette avenue de recherche en proposant un cadre conceptuel pour les méthodes hybrides, intitulé la recherche itérative de l'espace restreint, ±Iterative Restricted Space Search (IRSS)>>, dont, la principale idée est la définition et l'exploration successives de régions restreintes de l'espace de solutions. Ces régions, qui contiennent de bonnes solutions et qui sont assez petites pour être complètement explorées, sont appelées espaces restreints "Restricted Spaces (RS)". Ainsi, l'IRSS est une approche de solution générique, basée sur l'interaction de deux phases algorithmiques ayant des objectifs complémentaires. La première phase consiste à identifier une région restreinte intéressante et la deuxième phase consiste à l'explorer. Le schéma hybride de l'approche de solution permet d'alterner entre les deux phases pour un nombre fixe d'itérations ou jusqu'à l'atteinte d'une certaine limite de temps. Les concepts clés associées au développement de ce cadre conceptuel et leur validation seront introduits et validés graduellement dans cette thèse. Ils sont présentés de manière à permettre au lecteur de comprendre les problèmes que nous avons rencontrés en cours de développement et comment les solutions ont été conçues et implémentées. À cette fin, la thèse a été divisée en quatre parties. La première est consacrée à la synthèse de l'état de l'art dans le domaine de recherche sur les méthodes hybrides. Elle présente les principales approches hybrides développées et leurs applications. Une brève description des approches utilisant le concept de restriction d'espace est aussi présentée dans cette partie. La deuxième partie présente les concepts clés de ce cadre conceptuel. Il s'agit du processus d'identification des régions restreintes et des deux phases de recherche. Ces concepts sont mis en oeuvre dans un schéma hybride heuristique et méthode exacte. L'approche a été appliquée à un problème d'ordonnancement avec deux niveaux de décision, relié au contexte des pâtes et papier: "Pulp Production Scheduling Problem". La troisième partie a permit d'approfondir les concepts développés et ajuster les limitations identifiées dans la deuxième partie, en proposant une recherche itérative appliquée pour l'exploration de RS de grande taille et une structure en arbre binaire pour l'exploration de plusieurs RS. Cette structure a l'avantage d'éviter l'exploration d 'un espace déjà exploré précédemment tout en assurant une diversification naturelle à la méthode. Cette extension de la méthode a été testée sur un problème de localisation et d'allocation en utilisant un schéma d'hybridation heuristique-exact de manière itérative. La quatrième partie généralise les concepts préalablement développés et conçoit un cadre général qui est flexible, indépendant des méthodes utilisées et basé sur un échange d'informations entre les phases. Ce cadre a l'avantage d'être général et pourrait être appliqué à une large gamme de problèmes.

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.

Dans le cadre de ce travail de thèse, nous avons conçu une plateforme de simulation permettant l’évaluation comparative de stratégies de pilotage pour la production de bois d’œuvre dans les scieries nord-américaines. Dans notre contexte, une stratégie de pilotage est composée de plusieurs paramètres tels que le choix des politiques d’acceptation des commandes, permettant d’accepter ou de refuser une commande en fonction de règles mises en place, le choix des modèles et algorithmes de planification utilisés à chaque étape de la production de bois d’œuvre, le choix du modèle au niveau tactique, les mécanismes de coordination utilisés, permettant de mieux coordonner les opérations de plusieurs entités distinctes ou de plusieurs niveaux de planification ; on parle notamment d’échange d’informations circulant entre les niveaux de planification tactique et opérationnel ou encore entre les entités/modèles utilisés au niveau opérationnel pour planifier la production de bois d’œuvre. Lors de la planification des opérations, les industriels doivent mettre en place ces stratégies de pilotage. Aujourd’hui, il est extrêmement compliqué de savoir quelle stratégie de pilotage mettre en place en fonction de son propre contexte de marché et de ses paramètres de production. L’objectif général est donc est de permettre d’évaluer et comparer des stratégies de pilotage aux niveaux tactique et opérationnel pour la production de bois d’œuvre, tout en tenant compte du contexte de marché de l’entreprise ainsi que de ses paramètres de production. Pour atteindre cet objectif, nous l’avons divisé en quatre objectifs spécifiques qui ont donnés lieu à trois publications. Pour notre premier objectif spécifique, nous avons développé un modèle de simulation permettant de représenter la génération, l’acceptation et la vente d’une commande pour une entreprise de sciage. Un module de planification de la production a également été couplé et est responsable de la gestion des stocks et de la génération des plans de production. Pour notre deuxième objectif spécifique, nous avons utilisons ce modèle de simulation pour pouvoir évaluer l’impact de politiques d’acceptation des commandes (telles que Availableto-promise (ATP), Capable-to-promise (CTP) ou encore On-Stock) sur les performances de l’entreprise en termes de volume de commandes acceptées dans un environnement à flux de produits divergent avec co-production. Bien que ces politiques d’acceptation des commandes aient été largement étudiées dans un contexte manufacturier traditionnel, le choix d’une politique plutôt qu’une autre est loin d’être trivial dans un tel contexte de divergence de flux physique. Nous montrons dans cette première contribution que dans ce type de contexte, le choix d’une politique d’acceptation de commande plutôt qu’une autre dépend fortement du marché et impacte fortement les performances de l’entreprise, en termes de commandes acceptées et de stock moyen annuel. Cet objectif spécifique a entrainé l’écriture d’un premier article. Pour notre troisième objectif spécifique, nous avons évalué des mécanismes de coordination mis en place au niveau opérationnel entre les différentes activités du processus de transformation de bois d’œuvre, qui est un processus décentralisé. La précédente plateforme de simulation a donc été adaptée et des mécanismes de coordination déjà publiés tels que « Twophases planning », ou « bottleneck-first planning » y sont évalués en utilisant un horizon roulant dans un environnement où les commandes sont générées dynamiquement. Nous montrons que les mécanismes de coordination déjà publiés et testés dans un environnement statique performent mal dans un environnement dynamique. Nous proposons donc un autre mécanisme de coordination « hybride flux poussé / flux tiré » exploitant le concept de point de découplage. Ce mécanisme s’avère meilleur que les précédents en permettant un plus grand nombre de ventes, ainsi qu’une réduction des stock moyens. Cet objectif spécifique a entrainé l’écriture d’un deuxième article. Enfin, pour notre quatrième objectif spécifique, nous nous intéressons à la planification de la production aux niveaux tactique et opérationnel. Nous utilisons le modèle de simulation pour comparer et évaluer l’impact de différents types d’informations transmises du niveau tactique au niveau opérationnel. Le niveau de planification tactique est alors pris en compte pour établir une planification à plus long terme. Nous montrons que le choix du type d’informations à transmettre du niveau tactique au niveau opérationnel varie selon plusieurs facteurs, tels que : la politique d’acceptation des commandes (ATP, CTP) utilisée par l’entreprise, l’ampleur de la saisonnalité des prix de vente, ou le fait d’être ou non dans un marché en surcapacité. Cet objectif spécifique a entrainé l’écriture d’un troisième article. / In this thesis, we designed a simulation platform to compare and evaluate production planning and order management strategies for lumber production in North American sawmills. In our context, a strategy is composed of several parameters such as the choice of order acceptance policies, allowing to accept or refuse an order based on implemented rules, the choice of planning models and algorithms used at each stage of timber production, the choice of model at the tactical level, the coordination mechanisms used, to better coordinate the operations of several distinct entities or of several planning levels; this includes the exchange of information between tactical and operational planning levels or between entities / models used at the operational level to plan timber production. Today, it is extremely difficult for a company to know which management strategy to put in place. The general objective is then to evaluate and compare tactical and operational planning strategies for timber production, taking into account the company's market context and its production parameters. To achieve this goal, we divided it into four specific objectives that resulted in three publications. In the first specific objective, we developed a simulation model to represent the generation, acceptance and sale of an order for a sawmill. We coupled a production planning module to this simulation model that is responsible for inventory management and the generation of production plans. In a second objective, we use this simulation model to be able to evaluate the impact of order acceptance policies such as Available-to-promise (ATP), Capable-to-promise (CTP) and Stock policies on the company’s performance in terms of volume of accepted orders in a product flow environment diverge with co-production. Although these order acceptance policies have been widely studied in a traditional manufacturing context, the choice of one policy over another is far from being trivial in such a context of divergence flow. We show that in this type of context, the choice of an order acceptance policy rather than another depends strongly on the market and impacts the performance of the company, in terms of accepted orders and average annual inventory. This specific objective leads to the first publication. In a third specific objective, we evaluated coordination mechanisms used at the operational level between the different activities of the timber processing process, which is a decentralized process. The previous simulation platform has been adapted and previously published coordination mechanisms such as "Two-phase planning" or "bottleneck-first planning" are evaluated using a rolling horizon in an environment where orders are generated dynamically. We show that coordination mechanisms already published and tested in a static environment perform poorly in a dynamic environment. We therefore propose another "hybrid push / pull" coordination mechanism exploiting the decoupling point concept. This mechanism is better than the previous ones by allowing a greater number of sales, as well as a reduction in average inventory. This specific objective leads to a second publication. Finally, in a fourth specific objective, we are interested in production planning at the tactical and operational levels. We use the simulation model to compare and evaluate different information transmitted from the tactical level to the operational level by simulating the production system, the planning process and the market behavior. The tactical planning level is then taken into account to establish longer-term production planning. We show that the choice of the type of information to be transmitted from the tactical level to the operational level varies according to several factors, such as: the order acceptance policy (ATP, CTP) used by the company, the extent of seasonality selling prices, or whether or not being in an overcapacity market. This specific objective leads to third publication

L’évolution continue des environnements de production et l’augmentation des besoins des clients, demandent un processus de production plus rapide et efficace qui contrôle plusieurs paramètres en même temps. Nous nous sommes intéressés au développement de méthodes d’aide à la décision qui permettent d’améliorer l’ordonnancement de la production. L’entreprise partenaire (Norelem) fabrique des pièces de précision mécanique, il faut donc prendre en compte les différentes contraintes de ressources (humaines et d’outillage) existantes dans l’atelier de production.Nous avons abordé l’étude d’un atelier d’ordonnancement de type open shop ou chemin ouvert, où une tâche peut avoir de multiples séquences de production puisque l’ordre de fabrication n’est pas fixé et l’objectif à minimiser est le temps total de séjour. Des contraintes d’affectation de ressources humaines (multi-compétences) et de disponibilité d’outillage ont été prises en compte.Des modèles mathématiques linéaires et non-linéaires ont été développés pour décrire la problématique. Etant donné que les méthodes exactes sont limitées aux instances de petites tailles à cause des temps de calcul, des méthodes de résolution approchées ont été proposées et comparées. De plus, nous avons abordé l’optimisation multi-objectif en considérant trois objectifs, la minimisation du temps total de séjour et l’équilibrage de charge des ressources (humaines et machines).L’efficacité des méthodes est prouvée grâce à des tests sur des instances théoriques et l’application au cas réel / The continuous evolution of manufacturing environments and the growing of customer needings, leads to a faster and more efficient production process that controls an increasing number of parameters. This thesis is focused on the development of decision making methods in order to improve the production scheduling. The industrial partner (Norelem) produces standardized mechanical elements, so many different resource constraints (humans and tools) are presented in its workshop.We study an open shop scheduling problem where one job can follow multiple production sequences because there is no fixed production sequence and the objective function is to minimize the total flow time. In addition, multi-skilled personnel assignment and tool’s availability constraints are involved.Mathematical models: linear and non-linear formulations have been developed to describe the problem. Knowing the exact method limitations in terms of instance sizes because of the duration, heuristics methods have been proposed and compared. Besides that, the multi-objective optimization was exposed to deal with three objectives as total flow time minimization and workload balancing concerning both, humans and machines.The efficiency of these methods was proved by several theoretical instance tests and the application on the real industrial case

L'industrie minière contribue de manière significative aux émissions mondiales de gaz à effet de serre (GES), posant des défis à l'objectif de l'Accord de Paris de limiter les émissions à 30 Gt équivalent CO₂ par an d'ici 2030. Ce mémoire vise à intégrer les considérations d'émissions de carbone dans la planification minière à court terme pour promouvoir des pratiques minières durables. La recherche commence par souligner les défis environnementaux posés par l'industrie minière, en particulier ses contributions significatives aux émissions de GES, puis détaille la méthodologie utilisée pour développer le cadre des travaux, en mettant l'accent sur l'intégration des facteurs économiques et environnementaux. Elle met en avant l'efficacité du cadre proposé pour réaliser des réductions substantielles des émissions, en montrant comment des calendriers de production optimisés peuvent s'aligner sur les objectifs de durabilité. De plus, l'étude aborde la nécessité de considérer des solutions innovantes pour réduire ces émissions. Appliquée à une étude de cas dans une mine de fer, cette étude démontre des réductions significatives des coûts opérationnels et des émissions de GES, prouvant que les pratiques minières durables peuvent être à la fois environnementalement et économiquement avantageuses. Les résultats soulignent l'importance d'intégrer les considérations environnementales dans les processus de planification minière, fournissant des informations précieuses et des outils pratiques pour les planificateurs et les décideurs miniers. Le mémoire conclut en discutant des implications plus larges pour l'industrie minière, en suggérant des voies pour de futures recherches et le développement continu de pratiques durables. / The mining industry significantly contributes to global greenhouse gas (GHG) emissions, posing challenges to the Paris Agreement's goal of capping emissions at 30 Gt CO₂-equivalent annually by 2030. This thesis aims to integrate carbon emission considerations into short-term mine planning to promote sustainable mining practices. The research begins by outlining the environmental challenges posed by the mining industry, particularly its significant contributions to GHG emissions, and then details the methodology used to develop the framework, emphasizing the integration of economic and environmental factors. It highlights the effectiveness of the framework in achieving substantial emissions reductions, showcasing how optimized production schedules can align with sustainability goals. Additionally, the study addresses the necessity of considering innovative solutions to reduce these emissions. Applied to a case study of an iron ore mine, this study demonstrates significant reductions in both operational costs and GHG emissions, proving that sustainable mining practices can be both environmentally and economically advantageous. The findings highlight the importance of incorporating environmental considerations into mine planning processes, providing valuable insights and practical tools for mine planners and decision-makers. The thesis concludes by discussing the broader implications for the mining industry, suggesting pathways for future research and the continued development of sustainable practices.

Cette recherche introduit un modèle de décision multiobjectif qui aide le gestionnaire de projets à allouer les ressources à son projet. Le modèle comporte trois axes de décision représentant les compromis à faire entre la durée du projet, le coût du projet et les quantités de ressources allouées. L'allocation des ressources est déterminée en considérant le coût de chaque ressource. Le modèle incorpore le processus d'assignation des ressources, une problématique typique de l'affectation des ressources en gestion projets, à celui de !'ordonnancement des activités. Pour le résoudre, il a fallu concevoir et expérimenter de nouveaux algorithmes. La recherche comporte trois volets où chacun des volets alimente le volet suivant. Le premier volet propose de nouvelles procédures pour minimiser la durée du projet sous contraintes de disponibilités variables de ressources, dans le cas de problèmes ayant des activités avec un seul mode de réalisation ou de problèmes ayant des activités avec plusieurs modes de réalisation. Ces procédures comprennent une nouvelle règle de priorité selon un schème que nous qualifions d'ensembliste et une adaptation de la méthode Tabou. Les résultats de l'expérimentation montrent l'efficacité de la nouvelle règle de priorité et de l'adaptation de la méthode Tabou. Le deuxième volet propose des procédures pour minimiser le coût de disponibilité et le coût d'assignation des ressources allouées sous contrainte d'une date d'échéance du projet. La procédure incorpore l'adaptation de la méthode Tabou élaborée au volet précédent. Les résultats de l'expérimentation montrent la bonne performance des procédures développées. Le troisième volet propose une approche interactive par laquelle le gestionnaire de projets évalue des choix d'allocation de ressources afin de parvenir à une solution de compromis entre les trois axes de décision. Pour y parvenir, on évalue des solutions dans une région délimitée par les buts du gestionnaire de projets au lieu d'effectuer une approximation de la frontière efficace. L'expérimentation montre la faisabilité de l'approche interactive ainsi que l'efficacité de l'adaptation proposée de la méthode Tabou. Ces trois volets permettent d'élaborer l'architecture d'un Système Interactif d'Aide à la Décision pour l'allocation multiobjective des ressources en gestion de projets.

Les travaux de cette thèse sont articulés autour du problème d’ordonnancement de tâches dans un type d’atelier de structure complexe peu étudié dans la littérature. Cet atelier est de composition hybride : chaque étage de l’atelier a une ou plusieurs machines. Les principales contraintes considérées sont le traitement par lots et la minimisation du retard total. Les méthodes de résolution de ce problème sont intégrées dans les systèmes d’aide à la décision du programme de recherche du Groupe SouffletEtant donné la structure complexe du type d’atelier considéré, nous avons décomposé ce dernier afin d’étudier plus particulièrement le problème d’ordonnancement sur machines parallèles identiques. Différentes méthodes de résolution sont testées. Les résultats sont analysés afin de proposer une classification d’instances et de méthodes de résolution. Les problèmes étudiés sont résolus de manière exacte et approchée. Différentes méthodes ont été testées : des recherches itératives, des algorithmes tabous, des méthodes évolutionnaires. Les conclusions de la résolution du problème d’ordonnancement des machines parallèles sont utilisées pour construire des méthodes à deux niveaux pour le problème complexe d’ordonnancement. Les résultats montrent que les algorithmes trouvent des solutions de bonne qualité pour le problème traité. De la même manière, de problématiques industrielles similaires sont traitées, dans l’objectif d’optimiser le fonctionnement du centre de recherche / This thesis considers a complex workshop scheduling problem, which is rarely studied to our knowledge. This workshop has a hybrid composition : one or several machines are available at each stage. Main considered constraints are batch processing and total tardiness minimization. Solution methods are embedded on the information system of research program of Soufflet Group. Given the complex structure of the workshop, it has been split in order to study the parallel machines scheduling problem individually. Different solution methods are developed. Obtained results are used to build a classification of instances and solution methods. To solve described problems, exact and approach solution methods are proposed. We have adapted iterated search, tabu search, genetic algorithms, … Findings from solving parallel machines scheduling problem are employed to develop a two levels solution method for the described flow shop problem. Results show the performance of developed algorithms to find good quality solutions for described scheduling problem. Similarly, industrial problems are considered, in order to optimize operational behavior of research center

Les travaux de ce mémoire traitent du problème d’ordonnancement et d’optimisation de la production dans un environnement de plusieurs machines en présence de contraintes sur les ressources matérielles dans une usine d’extrusion plastique. La minimisation de la somme pondérée des retards est le critère économique autour duquel s’articule cette étude car il représente un critère très important pour le respect des délais. Dans ce mémoire, nous proposons une approche exacte via une formulation mathématique capable des donner des solutions optimales et une approche heuristique qui repose sur deux méthodes de construction de solution sérielle et parallèle et un ensemble de méthodes de recherche dans le voisinage (recuit-simulé, recherche avec tabous, GRASP et algorithme génétique) avec cinq variantes de voisinages. Pour être en totale conformité avec la réalité de l’industrie du plastique, nous avons pris en considération certaines caractéristiques très fréquentes telles que les temps de changement d’outils sur les machines lorsqu’un ordre de fabrication succède à un autre sur une machine donnée. La disponibilité des extrudeuses et des matrices d’extrusion représente le goulot d’étranglement dans ce problème d’ordonnancement. Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec les différents algorithmes proposés. L’analyse des résultats a démontré que les méthodes de construction de solution ne sont pas suffisantes pour assurer de bons résultats et que les méthodes de recherche dans le voisinage donnent des solutions de très bonne qualité. Le choix du voisinage est important pour raffiner la qualité de la solution obtenue. Mots-clés : ordonnancement, optimisation, extrusion, formulation mathématique, heuristique, recuit-simulé, recherche avec tabous, GRASP, algorithme génétique / The thesis deals with the optimization of the production on a number of machines subject to limited availability of the resources in an extrusion facility. Because of its importance to meet deadlines, the objective is to minimize the sum of weighted tardiness. This work presents a linear formulation of the problem and a number of heuristic solution methods. The proposed heuristic solution methods can be divided into two main groups: construction methods and neighborhood search methods. Also solution construction methods are divided in two sub-groups: parallel construction heuristics and serial construction heuristics. Adaptations of the simulated annealing algorithm (SA), the genetic algorithm (GA), the Tabu search (TS) method and the Greedy randomized adaptive search procedure (GRASP) are developed. Five neighborhood structures are used within the four tested neighborhood search algorithms. In our problem, setup times are sequence dependent. Also, extruders and dies are the bottleneck piece of equipment in this industrial setting. Several problem instances were generated for the evaluation of heuristic scheduling algorithms. The experimental study shows that the construction heuristics are not sufficient to ensure good results, however the proposed neighborhood search methods perform very well. Also, the structure of neighborhoods plays an important role to guarantee better results. Keywords: scheduling, optimization, extrusion, mathematical formulation, heuristic, simulated-annealing, tabu-search, GRASP, genetic algorithm

La recherche abordée dans le cadre de cette thèse s'intéresse à la gestion des ressources humaines opérationnelles, et plus spécifiquement aux problèmes de planification de ces ressources dans un contexte dynamique. Un intérêt particulier est porté au problème d'ordonnancement en temps réel du personnel travaillant sur une chaîne d'assemblage. Nous abordons cette problématique dans une perspective de gestion par compétences et ce, en nous basant sur le profil de compétences dans la modélisation de l'offre et de la demande en main-d'oeuvre. Quatre principaux axes de recherche sont exploités. Le premier axe vise l'aspect théorique de la modélisation du problème d'ordonnancement du personnel. A cet effet, nous proposons un modèle mathématique du problème d'affectation dynamique des employés sur une chaîne d'assemblage avec la prise en considération des préférences, des compétences et des déplacements inter-postes des employés. En nous basant sur ce modèle, et grâce à l'utilisation du solveur commercial de type Cplex, nous avons pu résoudre des instances de problèmes de petite taille. Les résultats obtenus démontrent que la production d'une solution optimale requiert un temps de calcul important, ce qui risque de générer une rigidité et une moindre réactivité de la fonction d'ordonnancement face à des perturbations d'un environnement dynamique. Le deuxième axe de recherche porte sur l'élaboration d'une approche distribuée à base d'agents pour la résolution du problème d'ordonnancement du personnel. L'approche proposée se base sur l'utilisation de plusieurs catégories d'agents intelligents qui coopèrent entre eux à travers la formation de coalitions. Chaque coalition est formée de deux agents-employés qui auront décidé de coopérer entre eux en s'échangeant une partie de leurs activités d'assemblage afin d'améliorer leur profit et en conséquence, la qualité de la solution globale d'ordonnancement. Les résultats d'ordonnancement du personnel obtenus à partir des premiers tests sont encourageants. Ils démontrent que notre approche à base d'agents permet d'obtenir des solutions de bonne qualité en des temps raisonnables. Le troisième axe de recherche porte sur le réordonnancent du personnel en temps réel face aux aléas liés à l'absence d'employés. À cet effet, nous proposons une extension de l'approche à base d'agents ainsi que deux variantes de l'approche de recuit simulé, qui permettent de résoudre le problème de réordonnancement. Nous avons pu tester les performances de ces deux approches sur plusieurs cas du problème d'ordonnancement et de réordonnancement du personnel. L'ensemble des résultats démontre que l'algorithme à base d'agents conduit à de très bonnes solutions en comparaison avec le recuit simulé. Enfin, nous avons exploité les algorithmes à base d'agents et de recuit simulé, qui sont développés dans cette recherche, pour étudier deux aspects de la gestion stratégique des ressources humaines : la flexibilité dans l'élaboration des horaires de travail et l'impact de la prise en considération des préférences dans le processus d'ordonnancement du personnel. Dans les deux cas, les résultats de simulation obtenus corroborent les hypothèses initiales de recherche, à savoir la pertinence et l'intérêt de la notion de flexibilité et de la prise en compte des préférences dans le processus d'ordonnancement du personnel.