Thesis (doctoral) - Universität, Darmstadt. / Includes bibliographical references.

Thesis (doctoral) - Universität, Darmstadt. / Includes bibliographical references.

Thèse (Ph. D.)--Université Laval, 2001. / Bibliogr.: f. [204]-226. Publié aussi en version électronique.

Au cours de cette thèse, l'exploration de l'espace de solutions par des métaheuristiques est abordée. Les métaheuristiques sont des méthodes d'optimisation utilisées pour résoudre des problèmes NP-difficile. Elles explorent aléatoirement l'espace de recherche pour trouver les meilleures solutions. Dans un premier temps, l'ensemble des solutions est modélisé par un espace unidimensionnel par une Méthode de Conversion de l'Espace de recherche (MCE). Des métriques sont proposées pour évaluer l'exploration de l'espace de recherche par une métaheuristique en identifiant les zones explorées et inexplorées. Ces métriques sont utilisées pour orienter l'exploration de l'espace de recherche d'une méthode d'optimisation.La convergence est améliorée en accentuant le recherche dans les zones explorées. Pour sortir des minimums locaux, l'exploration est diversifiée en la dirigeant vers les zones inexplorées. En associant l'exploration du voisinage des solutions et ces métriques cartographiques, il est possible d'améliorer les performances des métaheuristiques. Plusieurs algorithmes mono-objectifs et multiobjectifs sont implémentés en version classique, hybridé par la recherche locale et par la MCE. Le Flexible Job Shop Problem (FJSP) est utilisé comme problème de référence. Les expérimentations avec les algorithmes hybridés montrent une amélioration des performances / In this thesis, the solution space exploration by the metaheuristic is developed. The metaheuristics optimization methods are used to solve NP-hard problems. They explore randomly the search space to look for the best solutions. In a first step, the solution set is modeled by a one-dimensional space by a Mapping Method (MaM). Metrics are proposed to evaluate the search space exploration by a metaheuristic, identifying the explored and unexplored zones. These metrics are used to guide the search space exploration of an optimization method. The convergence is improved by emphasizing the research in the zones explored. To get out local minima, the exploration is diversified by pointing it towards the unexplored zones. Combining the neighbour discovery of the solutions and these mapping metrics, it is possible to improve the performance of metaheuristics. Several single-objective and multi-objective algorithms are implemented in the classic version, hybridized with local search and MaM. The Flexible Job Shop Problem (FJSP) is used as a reference problem. The experimentations with hybridized algorithms show performance improved

Nous étudions dans cette thèse deux approches réduisant le temps de traitement nécessaire pour résoudre des problèmes de planification et d'ordonnancement dans un contexte de programmation par contraintes. Nous avons expérimenté avec plusieurs milliers de processeurs afin de résoudre le problème de planification et d'ordonnancement des opérations de rabotage du bois d'oeuvre. Ces problèmes sont d'une grande importance pour les entreprises, car ils permettent de mieux gérer leur production et d'économiser des coûts reliés à leurs opérations. La première approche consiste à effectuer une parallélisation de l'algorithme de résolution du problème. Nous proposons une nouvelle technique de parallélisation (nommée PDS) des stratégies de recherche atteignant quatre buts : le respect de l'ordre de visite des noeuds de l'arbre de recherche tel que défini par l'algorithme séquentiel, l'équilibre de la charge de travail entre les processeurs, la robustesse aux défaillances matérielles et l'absence de communications entre les processeurs durant le traitement. Nous appliquons cette technique pour paralléliser la stratégie de recherche Limited Discrepancy-based Search (LDS) pour ainsi obtenir Parallel Limited Discrepancy-Based Search (PLDS). Par la suite, nous démontrons qu'il est possible de généraliser cette technique en l'appliquant à deux autres stratégies de recherche : Depth-Bounded discrepancy Search (DDS) et Depth-First Search (DFS). Nous obtenons, respectivement, les stratégies Parallel Discrepancy-based Search (PDDS) et Parallel Depth-First Search (PDFS). Les algorithmes parallèles ainsi obtenus créent un partage intrinsèque de la charge de travail : la différence de charge de travail entre les processeurs est bornée lorsqu'une branche de l'arbre de recherche est coupée. En utilisant des jeux de données de partenaires industriels, nous avons pu améliorer les meilleures solutions connues. Avec la deuxième approche, nous avons élaboré une méthode pour minimiser les changements effectués à un plan de production existant lorsque de nouvelles informations, telles que des commandes additionnelles, sont prises en compte. Replanifier entièrement les activités de production peut mener à l'obtention d'un plan de production très différent qui mène à des coûts additionnels et des pertes de temps pour les entreprises. Nous étudions les perturbations causéees par la replanification à l'aide de trois métriques de distances entre deux plans de production : la distance de Hamming, la distance d'édition et la distance de Damerau-Levenshtein. Nous proposons trois modèles mathématiques permettant de minimiser ces perturbations en incluant chacune de ces métriques comme fonction objectif au moment de la replanification. Nous appliquons cette approche au problème de planification et ordonnancement des opérations de finition du bois d'oeuvre et nous démontrons que cette approche est plus rapide qu'une replanification à l'aide du modèle d'origine. / We study in this thesis two approaches that reduce the processing time needed to solve planning and ordering problems in a constraint programming context. We experiment with multiple thousands of processors on the planning and scheduling problem of wood-finish operations. These issues are of a great importance for businesses, because they can better manage their production and save costs related to their operations. The first approach consists in a parallelization of the problem solving algorithm. We propose a new parallelization technique (named PDS) of the search strategies, that reaches four goals: conservation of the nodes visit order in the search tree as defined by the sequential algorithm, balancing of the workload between the processors, robustness against hardware failures, and absence of communication between processors during the treatment. We apply this technique to parallelize the Limited Discrepancy-based (LDS) search strategy to obtain Parallel Limited Discrepancy-Based Search (PLDS). We then show that this technique can be generalized by parallelizing two other search strategies: Depth-Bounded discrepancy Search (DDS) and Depth-First Search (DFS). We obtain, respectively, Parallel Discrepancy-based Search (PDDS) and Parallel Depth-First Search (PDFS). The algorithms obtained this way create an intrinsic workload balance: the imbalance of the workload among the processors is bounded when a branch of the search tree is pruned. By using datasets coming from industrial partners, we are able to improve the best known solutions. With the second approach, we elaborated a method to minimize the changes done to an existing production plan when new information, such as additional orders, are taken into account. Completely re-planning the production activities can lead to a very different production plan which create additional costs and loss of time for businesses. We study the perturbations caused by the re-planification with three distance metrics: Hamming distance, Edit distance, and Damerau-Levenshtein Distance. We propose three mathematical models that allow to minimize these perturbations by including these metrics in the objective function when replanning. We apply this approach to the planning and scheduling problem of wood-finish operations and we demonstrate that this approach outperforms the use of the original model.

Au cours du siècle actuel, la mondialisation a poussé les unités de production traditionnelles à se transformer en réseaux de fabrication. Avec des demandes de marché diverses, des évolutions technologiques et des coûts de main-d'œuvre variables selon les régions, les usines décentralisées offrent une flexibilité pour s'adapter à ces variations et obtenir des avantages concurrentiels. Par conséquent, la littérature sur la gestion de la production distribuée est vaste ; cependant, elle repose sur l'hypothèse que chaque usine du réseau est capable d'effectuer diverses tâches. Cette thèse examine une nouvelle configuration multi-usines dans laquelle chaque usine se voit attribuer une tâche spécifique au sein du réseau. Dans ce scénario, les usines des fournisseurs non identiques produisent différents composants des produits finaux dans la première étape. Chaque fournisseur est qualifié pour fabriquer un ensemble spécifique de composants. Dans la deuxième étape, les composants sont assemblés en produits finaux dans l'usine d'assemblage. Cette configuration des usines peut être observée dans l'industrie électronique comme le processus de fabrication des ordinateurs portables. L'objectif principal de cette recherche est de planifier les tâches dans toutes les usines de manière à minimiser le temps de réalisation de l'ensemble du processus. À cette fin, un modèle de programmation en nombres entiers mixtes est proposé. Pour traiter des instances plus importantes, un algorithme par séparation et évaluation, ainsi que des méthodes heuristiques constructives, sont développés. Les études computationnelles mettent en évidence l'efficacité des méthodes proposées. Le deuxième objectif de cette thèse est de garantir des performances ponctuelles au sein du réseau, dans le but de satisfaire les clients grâce à une livraison juste-à-temps. À cette phase, une fenêtre de temps est considérée pour chaque produit final. Si un produit est terminé plus tôt que sa fenêtre de temps, une pénalité de précocité est imposée. Si un produit est terminé plus tard que sa fenêtre de temps, il y aura une pénalité de retard. L'objectif est de terminer les produits aussi près que possible de leur fenêtre de temps pour minimiser la somme des pénalités de précocité et de retard. Un modèle de programmation linéaire en nombres entiers mixtes est développé pour trouver la solution optimale pour des problèmes de petite taille. Pour traiter des instances plus importantes, une heuristique de recherche locale itérative sont proposées. Les expériences computationnelles montrent que les méthodes de recherche locale itérative sont très efficaces, surpassant la méthode de recherche itérative bien connue dans la littérature. Le troisième objectif de la thèse consiste à intégrer des activités de maintenance préventive et corrective dans le processus de prise de décision. À cette phase, on suppose que les machines chargées de traiter les composants sont susceptibles de tomber en panne, et que leur temps de défaillance suit une distribution de probabilité de Weibull. Face à la complexité des modèles d'optimisation stochastiques résultants, nous proposons un algorithme de décomposition utilisant un solveur exact. Cette approche décompose le modèle principal en sous-problèmes de plus petites tailles, réduisant ainsi les défis computationnels. L'efficacité de cet algorithme est comparée au logiciel CPLEX largement adopté, et ce, en utilisant diverses instances. Dans nos analyses de sensibilité, nous évaluons les performances de notre modèle stochastique intégré par rapport à des travaux issues de la littérature. Les résultats sont discutés de manière approfondie, offrant des éclairages sur les implications des contributions de la thèse en industrie manufacturière. / In the current century, globalization has prompted traditional production units to create a network for manufacturing. With diverse market demands, technological shifts, and labor expenses across regions, decentralized factories offer flexibility to adapt such variations and gain competitive advantages. Consequently, the literature on distributed production management is extensive; however, it relies on the assumption that each factory in the network is capable of performing various tasks. This thesis investigates a new multi-factory configuration in which each factory is preassigned a specific task within the network. In this scenario, the non-identical supplier factories produce different components of the final products in the first stage. Each supplier is qualified to manufacture a specific set of components, hence, there is no decision about assigning the components to potentially suitable factories. In the second stage, the components are assembled into final products in the assembly factory. This configuration of the factories can be observed in electronic industry such as laptop manufacturing process. The primary objective of this research is to schedule the jobs in all factories in a way that minimizes the makespan of the entire process. For this purpose, a mixed integer programming model is proposed. To deal with larger instances, a branch-and-bound algorithm, and constructive heuristic methods are developed. Computational studies highlight the accuracy of the proposed methods. The second objective of this thesis is to ensure timely performance within the network, aiming to fulfill customer satisfaction through just-in- time delivery. In this phase, for each final product a due window is considered. If a product is finished earlier than its due window, an earliness penalty occurs. If a product is finished later than its due window, tardiness penalty occurs. The objective is to complete the products as close as possible to their due window to minimize the sum of earliness and tardiness penalty. A mixed integer linear programming model is developed for this problem which can find the optimal solution for small-size problems. To deal with larger instances, iterated local search methods equipped with local search heuristic are proposed. Computational experiments show that the iterated local search methods are very efficient outperforming the well-known iterated greedy method in literature. The third objective of the thesis involves integrating both preventive and corrective maintenance activities into the decision-making process. In this phase, it is assumed that the machines responsible for processing components are susceptible to failure, and their failure time follows a Weibull probability distribution. To navigate the complexity of these optimization models, we propose a decomposition algorithm employing an exact solver. This approach breaks down the main model into smaller subproblems, reducing computational challenges. The effectiveness of this algorithm is compared against the widely adopted CPLEX software, including various instances. In our sensitivity analyses, we assess the performance of our integrated stochastic model against benchmarks from the literature. The findings are comprehensively discussed, offering insights into the implications for manufacturing industries.

L'objectif principal de cette thèse est d'étudier le problème de planification de la production dans le contexte d'une demande incertaine, d’un niveau de service variable et d’approvisionnements incontrôlables dans une usine de seconde transformation du bois. Les activités de planification et de contrôle de production sont des tâches intrinsèquement complexes et difficiles pour les entreprises de seconde transformation du bois. La complexité vient de certaines caractéristiques intrinsèques de cette industrie, comme la co-production, les procédés alternatifs divergents, les systèmes de production sur commande (make-to-order), des temps de setup variables et une offre incontrôlable. La première partie de cette thèse propose une plate-forme d'optimisation/simulation permettant de prendre des décisions concernant le choix d'une politique de planification de la production, pour traiter rapidement les demandes incertaines, tout en tenant compte des caractéristiques complexes de l'industrie de la seconde transformation du bois. À cet effet, une stratégie de re-planification périodique basée sur un horizon roulant est utilisée et validée par un modèle de simulation utilisant des données réelles provenant d'un partenaire industriel. Dans la deuxième partie de cette thèse, une méthode de gestion des stocks de sécurité dynamique est proposée afin de mieux gérer le niveau de service, qui est contraint par une capacité de production limitée et à la complexité de la gestion des temps de mise en course. Nous avons ainsi développé une approche de re-planification périodique à deux phases, dans laquelle des capacités non-utilisées (dans la première phase) sont attribuées (dans la seconde phase) afin de produire certains produits jugés importants, augmentant ainsi la capacité du système à atteindre le niveau de stock de sécurité. Enfin, dans la troisième partie de la thèse, nous étudions l’impact d’un approvisionnement incontrôlable sur la planification de la production. Différents scénarios d'approvisionnement servent à identifier les seuils critiques dans les variations de l’offre. Le cadre proposé permet aux gestionnaires de comprendre l'impact de politiques d'approvisionnement proposées pour faire face aux incertitudes. Les résultats obtenus à travers les études de cas considérés montrent que les nouvelles approches proposées dans cette thèse constituent des outils pratiques et efficaces pour la planification de production du bois. / The main objective of this thesis is to investigate the production planning problem in the context of uncertain demand, variable service level, and uncontrollable supply in a wood remanufacturing mill. Production planning and control activities are complex and represent difficult tasks for wood remanufacturers. The complexity comes from inherent characteristics of the industry such as divergent co-production, alternative processes, make-to-order, short customer lead times, variable setup time, and uncontrollable supply. The first part of this thesis proposes an optimization/simulation platform to make decisions about the selection of a production planning policy to deal swiftly with uncertain demands, under the complex characteristics of the wood remanufacturing industry. For this purpose, a periodic re-planning strategy based on a rolling horizon was used and validated through a simulation model using real data from an industrial partner. The computational results highlighted the significance of using the re-planning model as a practical tool for production planning under unstable demands. In the second part, a dynamic safety stock method was proposed to better manage service level, which was threatened by issues related to limited production capacity and the complexity of setup time. We developed a two-phase periodic re-planning approach whereby idle capacities were allocated to produce more important products thus increasing the realization of safety stock level. Numerical results indicated that the solution of the two-phase method was superior to the initial method in terms of backorder level as well as inventory level. Finally, we studied the impact of uncontrollable supply on demand-driven wood remanufacturing production planning through an optimization and simulation framework. Different supply scenarios were used to identify the safety threshold of supply changes. The proposed framework provided managers with a novel advanced planning approach that allowed understanding the impact of supply policies to deal with uncertainties. In general, the wood products industry offers a rich environment for dealing with uncertainties for which the literature fails to provide efficient solutions. Regarding the results that were obtained through the case studies, we believe that approaches proposed in this thesis can be considered as novel and practical tools for wood remanufacturing production planning.

Dans ce mémoire, nous concevons un plan d'ordonnancement de la production dans un contexte d'industrie 4.0. L'environnement de travail est un atelier de soudure doté de trois stations pour le chargement et le déchargement des pièces, d'un robot de transport, d'un robot positionneur, de deux robots soudeurs et de gabarits sur lesquels sont montées les pièces. Dans un souci de construction de modèles reflétant la réalité de l'usine de production, des caractéristiques et des contraintes ont été considérées. Il s'agit entre autres des caractéristiques liées au type et aux temps de changement de gabarit, des contraintes d'entreposage, de ressources matérielles limitées (machines) et de recirculation. Le problème considéré est un problème de job shop flexible dont l'objectif est de minimiser la durée totale des opérations. Différentes variantes de la méthode exacte basée sur la programmation linéaire mixte en nombres entiers sont présentées. Ces méthodes sont de deux catégories à savoir les méthodes en une étape de résolution et les méthodes en deux étapes de résolution. La comparaison de ces différentes méthodes proposées montre que les méthodes en une étape de résolution offrent les meilleures valeurs de la fonction objectif mais sont plus lents dans la résolution tandis que les méthodes en deux étapes de résolution sont plus rapides dans la résolution mais n'ont pas les meilleures valeurs de la fonction objectif. / In this master's thesis, we design a production scheduling plan in an Industry 4.0 context. The working environment is a welding shop with three stations for loading and unloading parts, a transport robot, a positioner robot, two welding robots and jigs on which parts are mounted. In order to build models that reflect the reality of the production plant, additional characteristics and constraints were considered. These include characteristics related to the type and duration of jig change, constraints of storage, limited material resources (machines) and recirculation. The problem considered is a flexible job shop problem with the objective to minimize the total execution time (the makespan). Different variants of the exact method based on mixed integer linear programming are presented. These methods are of two categories, namely the one-step and the two-step methods. The comparison of these different proposed methods shows that the one-step method yields the best objective function values but requires relatively long computing times while the two-step method is faster but does not give the best objective function values.

Nous étudions la modélisation et la validation hors-ligne des applications temps-réel en environnement monoprocesseur, qui prend explicitement en compte l'échange des messages, le partage des ressources et les instructions conditionnelles entre les tâches. Notre objectif est de mettre en évidence l'impact de ces paramètres sur l'analyse des applications. Classiquement, ces applications sont modélisées de façon linéaire, en encapsulant les blocs conditionnels, et les séquences sont utilisées pour leur validation. Nous proposons une approche de modélisation et de validation arborescente, qui permet de considérer de façon explicite les blocs conditionnels, et qui utilise les arbres d'ordonnancement pour la validation. Nous comparons ensuite ces deux approches, et prouvons que les premières sont parfois trop pessimistes, c'est à dire qu'elles peuvent conduire à déclarer certaines applications comme non ordonnançables, alors qu'en réalité elles le sont. Nous commençons par construire un générateur d'arbres d'ordonnancement valides. La complexité du générateur étant exponentielle en fonction du nombre de tâches, cette approche est di cile à mettre en ÷uvre dans la pratique. Nous proposons donc une approche de modélisation bas ée sur les réseaux de Petri. Ce réseau sera utilisé pour générer les arbres valides, par construction du graphe de marquages, et la complexité pourra être réduite grâce à des heuristiques.

Thèse de doctorat : Informatique : Lille 1 : 2000. / Résumé en français et en anglais. Bibliogr. p. 177-188.