Letteratura scientifica selezionata sul tema "Ordonnancement d’atelier de type job shop"

Les métaheuristiques sont des méthodes de résolution de problèmes d'optimisation qui se basent majoritairement sur une représentation abstraite des solutions sous forme de codage direct ou indirect. L’amélioration d’une solution ou d’un ensemble de solutions en parallèle se fait via des manipulations de ces codages et des algorithmes d’évaluation de la qualité des solutions associées. Le passage d'une solution à une autre implique l'utilisation d'un ou plusieurs opérateurs qui permettent d'explorer l'espace de recherche. En général, les métaheuristiques exploitent ces opérateurs pour améliorer itérativement les solutions jusqu'à l'atteinte d'un optimum local (ou global). Une pléthore de métaheuristiques a été proposée pour résoudre les problèmes d'optimisation combinatoire dont les problèmes d'ordonnancement de tâches. Elles sont souvent dédiées à des classes spécifiques d'instances. Dans ce contexte, les chercheurs proposent fréquemment des algorithmes qui combinent diverses méthodes, en s’attachant à ajuster au mieux les paramètres des différentes parties de leurs algorithmes, mais les performances obtenues restent souvent comparables et l’efficacité dépendante de la classe d’instances résolues. Bien que les codages de solutions et les opérateurs de voisinage soient reconnus comme étant des composants essentiels au sein des métaheuristiques, ils sont rarement examinés conjointement de manière analytique et scientifique.Cette thèse se propose de caractériser les codages de solutions et les opérateurs de voisinage usuellement utilisés en ordonnancement, et particulièrement pour le problème de type job shop et une de ses variantes, pour lesquels on cherche à minimiser le makespan. L'ambition est d'exploiter les propriétés des espaces de recherche induits par ces codages et opérateurs, dans le but d'améliorer la conception des métaheuristiques. La démarche que nous avons appliquée dans notre étude est structurée en deux volets principaux avec une gradation de la complexité du problème de job shop. Le premier volet porte sur la caractérisation d'espaces de recherche à travers une analyse de paysage de fitness, en utilisant des métriques issues de la littérature. Le second volet concerne l'évaluation des performances de diverses associations de codages et d'opérateurs de voisinage dans l'optique de dégager d'éventuelles corrélations avec les propriétés du paysage, pour l'émission de préconisations pour la conception de métaheuristiques. Cette démarche est utilisée dans un premier temps pour un job shop de base, puis pour une variante plus contrainte du job shop : le job shop flexible avec contraintes de transport. Nos travaux mettent en évidence la difficulté de lier les performances des associations testées avec les métriques usuelles. La comparaison des résultats obtenus pour le problème de base et sa variante plus contrainte nous amènent à émettre des réserves sur une généralisation systématique des caractéristiques des codages et des opérateurs pour cette catégorie de problème d'optimisation
Metaheuristics are optimization problem-solving methods that primarily rely on an abstract representation of solutions in the form of direct or indirect encoding. Improving a solution or a set of solutions in parallel is achieved through manipulations of these encodings and algorithms evaluating the quality of associated solutions. The transition from one solution to another involves the use of one or more operators to explore the search space. Generally, metaheuristics utilize these operators to iteratively enhance solutions until reaching a local (or global) optimum. A plethora of metaheuristics has been proposed to address combinatorial optimization problems, including task scheduling problems. These ones are often dedicated to specific classes of instances. In this context, researchers frequently propose algorithms that combine various methods, striving to optimize parameters across different parts of their algorithms. However, the achieved performance is often comparable, and efficiency depends on the class of instances addressed. While solution encodings and neighborhood operators are recognized as essential components within metaheuristics, they are rarely jointly examined in an analytical and scientific manner.This thesis aims to characterize solution encodings and neighborhood operators commonly used in scheduling, particularly for the job shop problem and for one of its variants, in which the objective is to minimize the makespan. The ambition is to exploit the properties of the search spaces induced by these encodings and operators to enhance the design of metaheuristics. The approach applied in our study is structured into two main parts, with a gradation in the complexity of the job shop problem. The first part focuses on characterizing search spaces through a fitness landscape analysis, using metrics from the literature. The second part involves evaluating the performance of various combinations of encodings and neighborhood operators with the aim of identifying potential correlations with landscape properties. This is done to provide recommendations for the design of metaheuristics. This approach is initially applied to a basic job shop and then to a more constrained variant: the flexible job shop with transportation constraints. Our work highlights the challenge of linking the performance of tested combinations with standard metrics. The comparison of results obtained for the basic problem and its more constrained variant leads us to express reservations about a systematic generalization of encoding and operator characteristics for this category of optimization problems

Ce travail de thèse s'inscrit dans le cadre d'une collaboration industrielle avec la société Volume Software pour le développement du module d'ordonnancement du logiciel "DirectPlanning". Dans ce travail, nous étudions le problème de job shop flexible multicritère et le problème de job shop multiressource multicritère. Notre objectif est de déterminer une approximation du front de Pareto. Nous avons proposé des algorithmes de résolution approchés et plus particulièrement des algorithmes de recherche Tabou et des algorithmes génétiques. Nous avons proposé différentes versions de nos méthodes pour les deux problèmes considérés. Des expérimentations ont été réalisées et montrent les bonnes performances de nos algorithmes, à la fois d'un point de vue qualité des résultats et d'un point de vue de la rapidité des méthodes.

Intitulée Contribution au Pilotage des Systèmes de Production de Type Job Shop, cette thèse traite des problèmes d'ordonnancement de type job shop simple et job shop hybride. Ces problèmes appartiennent à la classe des problèmes NP Difficile de la combinatoire. Afin d'aborder progressivement la complexité inhérente au job shop, une• première heuristique est tout d'abord proposée pour résoudre le cas à trois machines. Ensuite, une généralisation de cette méthode est exposée pour résoudre le problème d'ordonnancement de type job shop hybride pour un nombre quelconque d'ateliers (c. à. D de machines), L'élaboration de notre méthode est basée sur deux phases principales. La première phase correspond à une procédure de transformation qui consiste à réduire le problème job shop en un problème flow shop à deux machines. La seconde phase permet de définir à l'aide de différentes règles de priorité plusieurs versions de l'algorithme pour résoudre le problème initial qui consiste en un problème de séquencement et un autre d'affectation. Des contraintes de capacité de stockage et de ressource auxiliaire limitées ont été modélisées et intégrées dans le calcul des plans de lancement. Des expérimentations et des comparaisons ont été effectuées sur un grand nombre de jeux d'essais. Différents objectifs de production ont été pris en compte correspondants soit à une gestion de production sur stock soit à une gestion de production à la commande. De nouvelles bornes inférieures pour les solutions optimales ont été définies afin de faciliter 1' évaluation des heuristiques proposées. Ces travaux de doctorat s'insèrent dans un travail plus global de conception d'un atelier de génie décisionnel de pilotage des systèmes de production, travail entrepris dans le cadre d'un projet de collaboration européen Tournesol
Titled Contribution to Production Control in Job Shop Environment, this thesis deals with scheduling problems in job shop and hybrid job shop environments. Job shop problems are known to belong to the NP-Hard class of combinatorial problems. In order to tackle progressively the problem complexity, a first heuristic is given in order to solve the three machines job shop problem. Than this method is generalised in order to solve the scheduling machines problem in hybrid job shop environment. Our method is based on two main phases. The first phase is a changing procedure which consists to reduce the job shop problem to a flow shop one with two machines. The second phase enables us various versions of the heuristic to solve the original problem, thanks to priority rules. The latter phase consists on solving two problems: the sequencing and the assignment problems. Buffer storage constraints and limited auxiliary resources have been modeled and integrated in scheduling planning calculation. Experiments and comparisons have been done on a large number of problem data. Various production objectives have been taken into account for make to stock production and for make to order production environments. New lower bounds for optimal solution have been defined to facilitate the method evaluation. These works have been done in the context of a more global project which consists in designing a workshop control case for production systems which has been initiated in a European project Tournesol

La thèse traite de l’ordonnancent d’ateliers de type « job shop » et « flow shop », deux problèmes largement étudiés dans la littérature sous leurs formes classiques. Notre contribution porte sur l’intégration des contraintes de transport des tâches entre les machines en utilisant un nombre fini de convoyeurs. Pour les deux problèmes nous avons donné une nouvelle modélisation mathématique en tenant compte des contraintes additionnelles qui portent, entre autres, sur les temps de transport et les différentes caractéristiques des ressources (capacités, nombre, temps de disponibilité, etc). Puis nous avons proposé une nouvelle approche de résolution basée sur l’algorithme des colonies de fourmis
The thesis concerns two scheduling problems, job shop scheduling and flow scheduling problem. Our contribution focuses on taking account transportation constraints of tasks between machines using a finite number of vehicles. For both problems we have given a new mathematical formulation that includes additional constraints about transportation time and different characteristics of resources (capacity, number, time availability, etc. ). We also give a new resolution algorithm based on ant colonies

Améliorer la coordination et la planification de la production vis-à-vis des activités logistiques des ateliers de production réel (à savoir les ressources : machines et engins de transport) est devenu une grande nécessité pour la diminution des coûts et la réduction des délais de livraison. La présente thèse est scindée en quatre parties. La première partie est un tour d’horizon des problèmes d’ordonnancement, l’accent est mis essentiellement sur les environnements Job Shop. Dans la deuxième partie, nous présentons une étude plus détaillée de ces environnements :problématique, état de l’art, modélisation et méthodes de résolution. Dans le cadre de la logistique interne des ateliers de production de type Job Shop, nous étudions dans la troisième partie, deux problématiques, le Job Shop avec transport dans un environnement ‘’juste à temps’’ et le Job Shop à flexibilité partielle avec maintenance préventive. La dernière partie est consacrée au problème d’atterrissage d’avions multipistes que nous avons modélisé sous forme de problème de Job Shop. Dans les différents cas d’études présentés, notre travail s’articule autour d’une étude systématique à base de trois fondamentaux, une formulation mathématique et/ou graphique du problème puis une résolution par une approche d'optimisation à base de métaheuristiques hybrides et enfin une validation des résultats par des simulations numériques. Notre objectif était de développer des systèmes d’ordonnancement dynamique d’aide à la décision capables de supporter la nature NP-complet des problèmes étudiés
In most real shop floor, improving the coordination and the planning of the production with respect to the logistic activities, namely resources : machines and material handling equipments, became a great necessity for the lowering of costs and reducing of lead-times delivery. The present thesis is split into four parts. The first one is a survey of the scheduling problems ; the emphasis is on the Job Shop environments. In the second part, we provide a more detailed study of these environments : problematic, state of the art, modelling and methods of resolution. As part of the internal logistics of the production facilities in Job Shop Scheduling Problem, the third part is devoted to showing two problems, the Job Shop Scheduling Problem with transportationfor just-in-time production as well as the flexible Job Shop Scheduling problem with machines availability constraints. Finally, the last part addresses the aircraft landing problem that we formulated as a Job Shop problem. In the various study cases previously cited, our work revolves around a systematic study based on three fundamental processes, a mathematical and/or graphical formulations, and then an approach for resolution optimization based on hybrid metaheuristics, finally a validation of the results by numerical simulations. The objective is to develop dynamic scheduling systems to resolve these NP-hard problems

Cette thèse a pour objet la conception d'un système adaptatif par agents avec utilisation des algorithmes génétiques multi objectifs. L'application consiste en l'ordonnancement d'atelier de type job-shop nm. Dans un premier temps, nous avons cherché à déterminer une représentation calculable efficace pour nos problèmes d'ordonnancement. Du fait d'un problème np-difficile, la méthode du placement par lots a été retenue afin de diminuer la complexité. Afin d'améliorer des solutions existantes, nous avons utilisé les algorithmes génétiques multi objectifs. Ils consistent en l'amélioration d'une population de solutions possibles, ou, en fonction des résultats obtenus, les solutions les moins bonnes sont vouées à disparaitre au profit des meilleures. Celles-ci sont alors choisies pour les étapes de croisements et de mutations afin d'aboutir à une nouvelle population. Vu le nombre de critères retenus, nous ne cherchons pas à déterminer la meilleure solution possible mais obtenir le meilleur compromis possible en utilisant la notion de Pareto. Bien que cette méthode fournisse de bons résultats statistiquement, nous avons réalisé un système basé sur la notion d'agents, afin d'introduire une approche dynamique, avec une évolution génétique de ceux-ci. Nous avons défini une modélisation du problème par agents afin qu'ils puissent collaborer pour aboutir à une bonne solution. Pour définir une évolution de notre système d'agents, nous avons mis en place une méthode d'analyse en composante principale afin de déterminer des groupes d'agents selon les divers paramètres. A partir des groupes, nous réalisons des croisements entre ceux-ci pour renforcer les groupes et les agents qui les composent. Afin de ne pas perdre de spécificités, nous avons défini les notions de groupe moyen et d'agent moyen dans un groupe. Cette méthode nous permet d'aboutir plus rapidement vers une bonne solution, laquelle est généralement meilleure.

Un des résultats les plus importants dans le domaine de l'ordonnancement, au moins par l'étendue de ses applications, est issu des méthodes basées sur la détermination du chemin critique (P. E. R. T. , C. P. M. , M. P. M. ). En effet ces méthodes ont résolu les problèmes à contraintes de succession et de localisation temporelle. Le contexte récent de la production flexible, où une machine donnée peut usiner un nombre important de pièces différentes, rend indispensable la résolution rigoureuse des problèmes d'ordonnancement et d'affectation qui en découlent. La méthodologie d'ordonnancement présentée dans ce mémoire résout conjointement ces problèmes d'ordonnancement et d'affectation en minimisant les temps d'attente et de transit. Le choix de ce critère permet de préserver au maximum les marges restantes des produits et permet en phase d'exploitation (pilotage) de résorber les perturbations. La méthode d'ordonnancement proposée est décomposée en quatre étapes. Tout d'abord, l'horizon d'ordonnancement est découpé en «paquets» de produits le plus possible indépendants afin de limiter l'explosion combinatoire. Chaque paquet est ensuite ordonnancé par une méthode arborescente utilisant la relaxation de certaines contraintes. Une procédure d'amélioration locale permet ensuite d'optimiser l'ordonnancement trouvé. Enfin, en phase d'exploitation, un opérateur de correction dynamique réactualise l'ordonnancement en fonction des aléas de production. La modélisation est effectuée à l'aide d'un réseau de Petri temporisé (RdPT) qui permet de représenter la base de données du problème dont la mise à jour (introduction des contraintes supplémentaires, changement d'affection, etc. ) peut s'effectuer aisément. La méthodologie proposée est illustrée par un exemple d'ordonnancement des tâches pour un problème de dimension industrielle