Scheduling of flexible production systems subject to different blocking constraints

Ce sujet de thèse concerne de manière générale l'évaluation des performances et l'ordonnancement dans des systèmes de production flexibles et principalement les problèmes d'ordonnancement d'atelier de type Flow-Shop et Flow-Shop hybride. Le problème d'ordonnancement d'un Flow-Shop peut être défini ainsi : un ensemble de N jobs composés chacun de M opérations, doivent passer sur M machines dans le même ordre. Une machine peut exécuter une seule opération à la fois, chaque job ne peut avoir qu'une seule opération en cours de réalisation simultanément et la préemption n'est pas autorisée. Dans le cas des Flow-Shops hybrides, Mk machines identiques sont disponibles à chaque étage k en un ou plusieurs exemplaires. Pour cette étude, notre objectif est toujours de minimiser le temps total d'exécution aussi appelé makespan. Les problèmes d'ordonnancement les plus répandus sont de type Flow-Shop classique où les espaces de stockage entre les machines sont considérées comme infinies. D'autres problèmes sont caractérisés par des capacités de stockage limitées ou nulles qui engendre une seule contrainte de blocage. Cette contrainte peut être un blocage classique (de type RSb) ou particulier (de type RCb ou RCb*). Dans nos travaux de recherche, nous présentons un cas général qui peut être tiré de l'industrie et modélisé sous forme de systèmes de type Flow-Shop et Flow-Shop hybride soumis simultanément à plusieurs types de blocage. Pour résoudre ce genre de problèmes, nous avons étudié dans cette thèse la complexité de ces systèmes et nous avons proposé des méthodes exactes, des méthodes approchées ainsi que des bornes inférieuresThis thesis deals mainly with makespan minimization in Flow-Shop and hybrid Flow-Shop scheduling problems where mixed blocking constraints are considered. In Flow-Shop scheduling problem, a set of N jobs must be executed on a set of M machines. All jobs require the same operation order that must be executed according to the same manufacturing process. Each machine can only execute one job at any time. Pre-emptive operation is not authorized in presented work. In case of hybrid Flow-Shop, at any processing stage k, there exist one or more identical machines Mk. Objective function consists in determining best schedule in order to reduce makespan, i.e. time where all operations are completed. The most common scheduling problem is classical flowshop where buffer space capacity between machines is considered as unlimited. Other problems are characterized by the fact that the storage capacity is limited or null and which generates one blocking constraint. This constraint can be a classical blocking (RSb) or particular blocking (RCb or RCb*). In our works, we present a general case which can be derived from industry and modeled as Flow-Shop and hybrid Flow-Shop systems subject simultaneously to different blocking. To solve these problems, we studied in this thesis complexity of these systems and we proposed exact methods, approached methods and lower bound