Search

International audience

In this paper, we consider a job-shop scheduling problem with mixed blocking constraints. Contrary to most previous studies, where no blocking or only one type of blocking constraint was used among successive operations, we assume that, generally, we may address several different blocking constraints in the same scheduling problem depending on the intermediate storage among machines, the characteristics of the machines, the technical constraints, and even the jobs. Our objective was to schedule a set of jobs to minimize the makespan. Thus, we propose, for the first time, a mathematical model of the job-shop problem taking into account the general case of mixed blocking constraints, and the results were obtained using Mosel Xpress software. Then, after explaining why and how groups of jobs have to be processed, a blocking constraint conflict-free warranted evaluation function is proposed and tested with the particle swarm optimization and genetic algorithm methods. The results prove that we obtained a near-optimal solution to this problem in a very short time.

International audience

International audience

This 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 bounds, 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érieures

International audience

This 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 bounds.; 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érieures.

International audience