Ordonnancement sur les machines à traitement par batches et contraintes de compatibilité, Scheduling batching machines with compatibility constraints

AVERTISSEMENT



Ce document est le fruit d’un long travail approuvé par le jury de
soutenance et mis à disposition de l’ensemble de la communauté
universitaire élargie.
Il est soumis à la propriété intellectuelle de l’auteur au même titre que sa
version papier. Ceci implique une obligation de citation et de
référencement lors de l’utilisation de ce document.
D’autre part, toute contrefaçon, plagiat, reproduction illicite entraîne une
poursuite pénale.

Contact SCD INPL: mailto:scdinpl@inpl-nancy.fr




LIENS




Code de la propriété intellectuelle. Articles L 122.4 e la propriété intellectuelle. Articles L 335.2 – L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm
Departement de formation doctorale en informatique
Institut National Ecole doctorale IAEM Lorraine
Polytechnique de Lorraine
Ordonnancement sur les machines a
traitement par batches et contraintes
de compatibilite.
THESE
presentee et soutenue publiquement le 23 novembre 2009
pour l’obtention du
Doctorat de l’Institut National Polytechnique de Lorraine
(specialite informatique)
par
Adrien Bellanger
Composition du jury
President : Christian PRINS Professeur, Universite de Technologique, Troyes
Rapporteurs : Pierre LOPEZ Charge de recherche CNRS, Toulouse (HDR)
Bernard PENZ Professeur, Grenoble INP
Examinateurs : Jean-Charles BILLAUT Professeur, Polytech’Tours
Emmanuel JEANNOT Charge de recherche INRIA, Bordeaux (HDR)
Francis SOURD SNCF - Direction Innovation & Recherche (HDR)
Marie-Claude PORTMANN Professeur, Ecole des Mines de Nancy
Directeur de these
Ammar OULAMARA Ma^ tre de conference, Ecole des Mines de Nancy
Co-directeur de these (HDR)
Laboratoire Lorrain de Recherche en Informatique et ses Applications | UMR 7503Mis en page avec la classe thloria.Remerciements
Ce travail a ete nance par une allocation a la formation recherche (AFR) du Fonds national
de la recherche (FNR) du Luxembourg. Je tiens donc a remercier le gouvernement du Grand
Duche de Luxembourg pour m’avoir permis d’e ectuer ces travaux de recherches dans de bonnes
conditions.
Par ailleurs, je tiens avant tout a remercier Ammar Oulamara sans qui je n’aurais pas pu
mener a bien cette these. En e et, non content de m’avoir accorde sa con ance durant ces 3
annees, il m’a appris a structurer mes idees, en etant, notamment, a l’ecoute de mes pensees les
plus confuses. Je tiens egalement a le remercier pour m’avoir entra^ ne sur des pistes de travail tres
interessantes, et pour s’^etre fortement investi dans cette these. Je souhaite egalement remercier
Marie-Claude Portmann pour les nombreuses pistes d’amelioration qu’elle m’a proposees, pour
son regard critique sur le travail e ectue et sur les orientations a envisager. Je les remercie
egalement pour leur disponibilite, leurs conseils avises - scientiques comme professionnels - et
leur bonne humeur.
De plus, je remercie les rapporteurs, Pierre Lopez et Bernard Penz, pour leur lecture attentive
de ce manuscrit et pour leurs rapports detailles et pertinents. Je remercie egalement les autres
membres du jury, Jean-Charles Billaut, Emmanuel Jeannot, Christian Prins et Francis Sourd
qui ont accepte d’evaluer mon travail.
Je tiens egalement a remercier les collegues de l’equipe ORCHIDS pour la bonne ambiance
dans l’equipe : merci donc, a Wahiba, Suzana, Khalida, Zerouk, Henri et Ayman sans oublier
Francoise Laurent pour son aide precieuse dans les demarches administratives.
Je n’aurais pas pu e ectuer cette these sans le precieux soutien de ma famille. Merci Claudia.
Merci papa et maman, Loulou, Titi et Jojo. Merci aux papys et mamies.
Merci Arnaud et Julie pour votre presence amicale durant ces annees de collocation. Je tiens
egalement a remercier les copains handballeurs pour les bons moments passes ensemble. Et
surtout un grand merci aux Fraisiens pour leur amitie qui perdure depuis tant d’annees.
iiiTable des matieres
Introduction generale 1
Chapitre 1 Le probleme et ses applications 3
1.1 La gestion de production . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 L’ordonnancement de la production . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Les problemes d’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Typologie des ordonnancements de la production . . . . . . . . . . . . . . 5
1.2.3 Representation des problemes d’ordonnancement . . . . . . . . . . . . . . 7
1.3 Problemes etudies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Flowshop hybride . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.2 Les machines a traitement par batches . . . . . . . . . . . . . . . . . . . . 8
1.3.3 Batches et compatibilite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Application industrielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Processus de fabrication d’un pneu . . . . . . . . . . . . . . . . . . . . . . 11
1.4.2 Description de l’atelier de production . . . . . . . . . . . . . . . . . . . . 11
1.4.3 Du probleme industriel au probleme scienti que . . . . . . . . . . . . . . 12
Chapitre 2 Modeles et travaux anterieurs 13
2.1 Classi cation des problemes et methodes de resolution . . . . . . . . . . . . . . . 14
2.1.1 Notations des problemes d’ordonnancement presentes . . . . . . . . . . . 14
2.1.2 Classication des problemes d’ordonnancement . . . . . . . . . . . . . . . 14
2.1.3 Classication de methodes de resolution . . . . . . . . . . . . . . . . . . . 18
2.2 Machines a traitement par batch . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 Problemes sans contraintes de compatitibilite . . . . . . . . . . . . . . . . 23
2.2.2 Problemes avec contraintes de compatibilite . . . . . . . . . . . . . . . . . 31
2.3 Flowshop Hybride classique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4 Flowshop et batches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.5 Conclusion du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
iiiTable des matieres
Chapitre 3 Methodes approchees 41
3.1 Heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.1 Schemas generiques des heuristiques proposees . . . . . . . . . . . . . . . 42
3.1.2 Bornes inferieures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.1.3 Heuristiques pour machines paralleles a traitement par batches . . . . . . 45
3.1.4 Heuristiques pour le owshop hybride a deux etages . . . . . . . . . . . . 49
3.1.5 Resultats experimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.2 Durees d’execution identiques au premier etage . . . . . . . . . . . . . . . . . . . 68
3.2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2.2 Transformation des donnees . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.2.3 Ordonnancement des t^aches courtes . . . . . . . . . . . . . . . . . . . . . 72
3.2.4 Ordonnancement des t^aches longues . . . . . . . . . . . . . . . . . . . . . 73
3.2.5 Schema d’approximation polynomial (PTAS) . . . . . . . . . . . . . . . . 74
3.3 Conclusion du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Chapitre 4 Methodes Exactes 77
4.1 Methodes par separation evaluation pour le owshop hybride . . . . . . . . . . . 78
4.1.1 Methode de Carlier et Neron . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.1.2 Adaptation au probleme de owshop hybride avec machines a traitement
par batches au second etage . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Methode directe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.2.1 Premiere etape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.2.2 Seconde etape. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.3 Methode inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.3.1 Premiere etape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.3.2 Seconde etape. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.4 Resultats Experimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.4.1 Performances des heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.4.2 Comparaison des bornes inferieures . . . . . . . . . . . . . . . . . . . . . . 91
4.4.3 Comparaison des deux methodes exactes . . . . . . . . . . . . . . . . . . . 93
4.5 Conclusion du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Chapitre 5 Autres criteres reguliers 105
5.1 Proprietes des ordonnancements optimaux . . . . . . . . . . . . . . . . . . . . . . 106
5.2 Minimisation du Makespan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.3 Minimisation de la somme des dates de n d’execution . . . . . . . . . . . . . . . 107
5.3.1 Nombre de batches reportes . . . . . . . . . . . . . . . . . . . . . . . . . . 108
iv