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

Mohand Larabi

Description

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

Sujets

• Transport
• Ordonnancement
• Modélisation
• Optimisation
• Recherche locale
• Algorithme génétique

Informations

• Publié par: Thesee
• Nombre de lectures: 127
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

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 int