Le problème de job-shop avec transport : modélisation et optimisation, Job-shop with transport : its modelling and optimisation

De
Publié par

Sous la direction de Philippe Lacomme
Thèse soutenue le 15 décembre 2010: Clermont Ferrand 2
Dans cette thèse nous nous sommes intéressés à l’extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l’existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu’un robot ne peut transporter qu’un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu’un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :• Une modélisation linéaire ;• Une modélisation sous forme de graphe disjonctif ;• Plusieurs heuristiques de construction de solutions ;• Plusieurs recherches locales qui améliorent les solutions obtenues ;• Utilisation des algorithmes génétiques / mémétiques comme schéma global d’optimisation ;• De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité.
-Job-shop
-Transport
-Robots
-Ordonnancement
-Capacité non unitaire
-Heuristiques
-Méta-heuristiques
-Voisinage
-Modélisation
-Optimisation
-Graphe disjonctif
-Graphe conjonctif
-Makespan
-Recherche locale
-Algorithme génétique
-Algorithme mémétique
In this thesis we are interested in the extension of the job-shop problem by adding the constraint of transport of jobs between different machines. In this study we used two types of robots, robots with unary loading capacity (capacity =1 means that each robot can carry only one job at a time,) and robots with non unary loading capacities (robot with capacity >1 can carry more than one job at time). Thus, the first step is devoted to the problem of job-shop with several robots with unary loading capacity. In the second step we extend the problem by adding the non-unary loading capacities to the robots. For both problems studied we have proposed :• A linear modeling ;• A Disjunctive graph Model ;• Several constructive heuristics ;• Several local searches methods that improve the obtained solutions ;• Use of genetic / memetic algorithms as a global optimization schema ;• New benchmarks, test results of our approaches on our benchmarks and those present in the literature and these results are commented and compared with those of literature. The results show the relevance of our model and its quality.
-Job-shop
-Transportation
-Robots
-Scheduling
-Non-unary loading capacities
-Heuristics
-Metaheuristics
-Neighborhood
-Modeling
-Optimization
-Disjunctive graph
-Conjunctive graph
-Makespan
-Local search
-Genetic algorithm
-Memetic algorithm
Source: http://www.theses.fr/2010CLF22092/document
Publié le : vendredi 28 octobre 2011
Lecture(s) : 167
Nombre de pages : 217
Voir plus Voir moins

N° d’Ordre : 2092
EDSPIC : 510
Université Blaise Pascal - Clermont Ferrand II
ECOLE DOCTORALE
SCIENCES POUR L’INGENIEUR DE CLERMONT FERRAND
THESE
Présentée par
Mohand LARABI
Diplômé d’Etudes Approfondies Linguistique, Logique et Informatique
Ingénieur en informatique industrielle
pour obtenir le grade de
Docteur d’Université
Spécialité : INFORMATIQUE
Le problème de job-shop avec transport :
modélisation et optimisation
Soutenue publiquement le 15 décembre 2010 devant le jury :

Monsieur Alain QUILLIOT Président
Monsieur Pierre CASTAGNA Examinateur
Monsieur Alexandre DOLGUI Rapporteur
Monsieur Aziz MOUKRIM Rapporteur
Monsieur Philippe LACOMME Co-Directeur de thèse
Monsieur Nikolay TCHERNEV Co- Directeur de thèse

tel-00625528, version 1 - 21 Sep 2011

tel-00625528, version 1 - 21 Sep 2011



A ma femme,
A toute ma famille, ma belle famille, mes amis et à
tous ceux qui ont supporté mon absence durant toutes
ces années et à tous ceux qui ont contribué de prés ou de
loin à l’aboutissement de cette thèse et à tous ceux qui
trouveront du plaisir à la feuilleter un jour.

tel-00625528, version 1 - 21 Sep 2011


tel-00625528, version 1 - 21 Sep 2011
Remerciements
En premier lieu mes remerciements vont pour mes deux directeurs de thèse Lacomme Philippe, et
Tchernev Nicolay, pour leurs conseils, leur disponibilité et leur accueil chaleureux au sein du laboratoire
LIMOS. Ils sont pour moi comme une seconde famille, tous les moments passés avec eux ont été très
enrichissants sur le plan professionnel et personnel.

En second lieu je remercie les rapporteurs de cette thèse : Aziz Moukrim Professeur d'Informatique à
l’Université de Technologie de Compiègne (UTC) et Alexandre Dolgui Directeur du Laboratoire en
Sciences et Technologies de l'Information (LSTI) et responsable du département Méthodes
Scientifiques pour la Gestion Industrielle (MSGI) pour la rapidité avec laquelle ils ont lu mon manuscrit
et l’intérêt qu’ils ont porté à mon travail.
Mes remerciements vont ensuite aux autres membres du jury qui ont accepté de consacrer une partie de
leur temps pour l’évaluation de mon travail :
• A Pierre Castagna Professeur à l’Université de Nantes,
• A Alain Quilliot directeur du LIMOS : tout d’abord pour avoir accepté de présider mon jury de
thèse, mais aussi pour de nombreuse discussions constructives et amicales que j’ai eu avec lui
au sein de LIMOS.
Je tiens également à remercier Zhao, Alexandre, Olivier, Sylverin, Eilishe, Amine, Aziz, Nassima, Leila,
Adelaïde, Nassim et mes collègues de L’IUP management de Clermont-Ferrand pour tous les bons
moments que nous avons partagé ensemble.
Et mes remerciements vont aussi à celles et ceux, très nombreux, qui ont participé de prés ou de loin à
mener à terme ce travail de recherche.

Mes derniers mots sont réservés à ma famille :
• A ma femme qui a tant sacrifier pour l’aboutissement de cette thèse, qui a été toujours
présente à mes cotés malgré la distance : son soutien m’était d’un grand apport.
• A ma famille qui m’a soutenu et encourager sans relâche durant toutes ces années.
• A ma belle famille qui m’a épaulé durant les moments difficiles.


tel-00625528, version 1 - 21 Sep 2011



tel-00625528, version 1 - 21 Sep 2011Sommaire

Introduction générale.................................................................................................................. 9
Chapitre I : Présentation de la problématique .......................................................................... 11
1. Introduction ...................................................................................................................... 15
2. Le domaine d’étude : les systèmes flexibles de production ............................................. 16
3. Les problèmes d’ordonnancement ................................................................................... 27
4. Présentation des problèmes d’optimisation...................................................................... 41
5. Conclusion........................................................................................................................ 51
Chapitre II : Le problème de job-shop ..................................................................................... 53
1. Introduction ...................................................................................................................... 57
2. Le job-shop : présentation ................................................................................................ 58
3. Les méthodes d’optimisation ........................................................................................... 66
4. Les principaux voisinages proposés pour le Job-Shop..................................................... 84
5. Les extensions possibles................................................................................................... 87
6. Conclusion........................................................................................................................ 89
Chapitre III : Le problème de Job-shop avec transport............................................................ 91
1. Introduction ...................................................................................................................... 95
2. Le job-shop avec transport : présentation ........................................................................ 96
3. Formalisation linéaire....................................................................................................... 98
4. Modélisation du job-shop avec transport ....................................................................... 109
5. Algorithme génétique..................................................................................................... 133
6. Application numérique................................................................................................... 145
7. Conclusion...................................................................................................................... 158
Chapitre IV : Job-shop avec transport avec des robots de capacité non unitaire ............. 161
1. Introduction .................................................................................................................... 165
2. Définition du Job-shop avec un robot de capacité non unitaire ..................................... 165
3. Le Job-shop avec plusieurs robots de capacités non unitaires ....................................... 191
4. Conclusion du chapitre................................................................................................... 207
Conclusion générale ............................................................................................................... 209
Bibliographie.......................................................................................................................... 211


tel-00625528, version 1 - 21 Sep 2011



tel-00625528, version 1 - 21 Sep 2011 9
Introduction générale
La gestion des systèmes de production, de biens ou de services pose de très nombreux
problèmes touchant la gestion de production, le marketing, la gestion des ressources humaines.
La résolution de ces problèmes nécessite l’utilisation de techniques d’optimisation et/ou
d’évaluation de performances issues de domaines très variés. Nous nous intéressons dans cette
thèse, aux problèmes d’optimisation discrets, c’est-à-dire à la résolution de problèmes que l’on
peut traiter par des techniques d’optimisation et qui sont généralement, ou le plus souvent liées à
des problèmes de planification et/ou d’ordonnancement.
La difficulté de résolution de ces problèmes d’ordonnancement vient du grand nombre
d’entités à gérer et de la nécessité de construire un planning comportant un grand nombre de
taches et ceci avec de nombreuses contraintes comme par exemple des contraintes de
précédence, de transport, de date, de délais et/ou de disponibilité de ressource.
La première étape dans la résolution de l’un de ces problèmes, consiste à définir et à
construire un modèle du système qui est utilisé par la suite pour construire, rechercher et
améliorer des solutions. La construction et l’élaboration d’un modèle constitue la première
difficulté à résoudre. On peut remarquer que pour tous les problèmes « classiques »
d’optimisation, des modèles efficaces sont connus et qu’ils reposent dans la majorité des cas, sur
un usage intensif de la théorie des graphes.
La deuxième étape consiste à proposer et concevoir des méthodes efficaces tirant profit de
la modélisation et permettant de définir des techniques d’amélioration itérative pour la recherche
locale, des techniques de diversification pour l’exploration de l’espace et des techniques globales
d’exploration de l’espace des solutions.
Dans la majorité des cas, on ne travaille pas directement sur le modèle à cause de la
difficulté liée à la complexité du modèle. Cette remarque s’applique à d’autres domaines que celui
de l’ordonnancement comme par exemple le domaine des tournées de véhicules. Sur les tournées
de véhicules beaucoup de méthodes travaillent sur un tour géant (solution du TSP) qui est ensuite
découpé (optimalement) pour obtenir une solution du problème de VRP, de LRP etc. Dans le
cadre du job-shop par exemple il est courant d’utiliser des vecteurs par répétition (séquence de
Bierwith) et de définir une méthode permettant d’associer à une séquence une solution du
problème. Cela revient à dire qu’on travaille sur deux espaces différents : l’espace des solutions et
l’espace (ou ensemble) des objets qui par une fonction (que l’on cherche définir la plus efficace
possible) donne une solution de l’espace. Ces méthodes alternent alors entre les deux espaces et il
s’agit, le plus souvent de tirer profit des ces deux espaces pour obtenir un schéma algorithmique
performant.
Dans cette thèse nous nous intéressons à un problème d’ordonnancement particulier : le
problème du job-shop auquel nous ajoutons des contraintes de transport. Notre apport consiste
en l’ajout de contraintes de deux types :
• la prise en compte de plusieurs moyens de transport de capacité unitaire ;
• la prise en compte de plusieurs moyens de transport de capacité non unitaire.
Pour la résolution de ces problèmes, nous généralisons la démarche classique appliquée au
job-shop et qui repose :
• sur la notion de graphe disjonctif non orienté pour modéliser un problème ;
• sur la notion de graphe disjonctif orienté pour modéliser une solution ;

tel-00625528, version 1 - 21 Sep 2011Introduction générale 10
• sur la notion de plus long chemin pour le calcul des dates au plus tôt des opérations.
Dans la suite, nous utilisons le schéma ci-dessus pour proposer des heuristiques et des
métaheuristiques pour les problèmes de job-shop avec transport.

Figure 1-1 : Le schéma de modélisation du Job-Shop tel que résumé par Caumond (2008)
Cette thèse est structurée en 4 chapitres.
Le chapitre 1 présente le domaine d’étude : les systèmes flexibles de production. Après une
présentation générale nous donnons une présentation des problèmes d’ordonnancement, et
donnons quelques modèles théoriques d’ordonnancement.
Le chapitre 2 aborde le problème du job-shop en tant que problème théorique. Nous
présentons pour ce problème, un état de l’art, les principaux algorithmes de la littérature. Nous
rappelons la modélisation sous la forme de graphe disjonctif de ce problème et nous présentons
les principes de base des principales méta-heuristiques.
Le chapitre 3 aborde le problème du job-shop avec transport. Une nouvelle modélisation
est présentée. Tous les éléments d’une méthode d’optimisation sont proposés et présentés. Les
résultats numériques concernent des instances de la littérature et permettent d’évaluer les
performances des méthodes proposées.
Le chapitre 4 aborde le problème du job-shop avec des robots de capacité non unitaire.
Une nouvelle modélisation est présentée. En particulier, nous présentons une modélisation
linéaire en nombres entiers et une modélisation sous la forme d'un graphe conjonctif-disjonctif.
Cette thèse se termine par une conclusion dans laquelle nous rappelons les principales
propositions que nous avons faites et dans laquelle, nous proposons des pistes de recherche dans
la continuité de nos travaux.

tel-00625528, version 1 - 21 Sep 2011

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi