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

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