Contribution à la résolution des problèmes de flow shop avec machines dédiées, avec dates de disponibilité et délais de livraison

République Tunisienne
Ministère de l'Enseignement Supérieur et
de la Recherche Scientifique
Université de Sousse

****

Institut Supérieur du Transport et de la Logistique de Sousse

MÉMOIRE

Présenté par

Mohamed Karim Hajji

POUR OBTENIR LE DIPLÔME DE

Mastère de recherche en Logistique et Gestion de Transport

Intitulé

Contribution à la résolution des problèmes de Flow
Shop avec machines dédiées, avec dates de
disponibilité et délais de livraison

Encadré par : M. Hatem Hadda

Année universitaire 2011 - 2012

Remerciement

Je tiens à remercier Monsieur Hadda Hatem maître assistant à l'ISTLS pour qui les mots ne suffiraient pas à lui témoigner ma profonde gratitude et ma reconnaissance, pour sa disponibilité et ses précieux conseils ainsi que le temps qu'il m'a consacré tout au long de la réalisation de ce mémoire, pour sa générosité et la grande patience dont il a su faire preuve malgré ses charges académiques et professionnelles.

Je remercie les membres de jury qui m'ont honoré en acceptant de juger ce travail.

Mes remerciements s'adressent également à ma famille, mes oncles et mes tantes qui ont su me donner le réconfort tout au long de mon cursus universitaire.

À mes parents et mes grands-parents

À mes oncles, mes tantes et mes frères

À Nassim et Rima

i

Table des matières

Introduction générale 1 Problèmes d'ordonnancement			1 3
	1.1	Notions préliminaires	4
		1.1.1 Définitions	4
		1.1.2 Classification	5
		1.1.3 Codification	6
		1.1.4 Complexité	7
		1.1.5 Représentation des problèmes d'ordonnancement . . .	8
	1.2	Méthodes de résolution	8
	1.3	Présentation du problème étudié	10
		1.3.1 Calcul du makespan	11
		1.3.2 Solutions de permutation	13
	1.4	'Etat de l'art	15
		1.4.1 Problèmes de flow shop avec prise en compte des dates
		de disponibilitéet des délais de livraison	15
		1.4.2 Méthodes heuristiques	16
		1.4.3 Méthodes méta-heuristique	19
		1.4.4 Bornes inférieures et PSE	21
2	Présentation des méthodes de résolution		25
	2.1	Bornes Inférieures	27
		2.1.1 Borne inférieure 1	27
		2.1.2 Borne inférieure 2	27
		2.1.3 Borne inférieure 3	27
		2.1.4 Borne inférieure 4	28
		2.1.5 Borne inférieure 5	28
	2.2	Heuristiques	29
		2.2.1 Heuristique H1	29
		2.2.2 Heuristique H2	30
		2.2.3 Heuristique H3	31

ii

2.2.4 Heuristique H4 31

2.2.5 Heuristique H5 32

2.2.6 Heuristique H6 33

2.2.7 Heuristique H7 34

2.3 Méta-Heuristiques 36

2.3.1 Notions de base 36

2.3.2 Recherche Taboue 38

2.3.3 Recuit simulé 42

3 Résultats expérimentaux 43

3.1 Génération des instances tests 44

3.2 Paramétrage des méta-heuristiques 46

3.2.1 Recherche Taboue 46

3.2.2 Recuit Simulé 52

3.3 Résultats des expérimentations 58

3.3.1 Heuristiques 58

3.3.2 Méta-heuristiques 62

Conclusion générale 67

Bibliographie 68

iii

Table des figures

1.1	Classification des problèmes d'ordonnancement d'atelier . . . .	5
1.2	Sous permutation au second étage	10
1.3	Calcul du makespan	12
1.4	Exemple pour le calcul du makespan	13
3.1	Empruntes des solutions de la RT1	47
3.2	'Evolution du makespan de la RT1	47
3.3	'Evolution du makespan de la RT1 sans aspiration	50
3.4	'Evolution du makespan de la RT1 avec aspiration	51
3.5	Dégradation de T pour la famille F3	56
3.6	Dégradation de T pour la famille F3, Palier 2	56
3.7	Probabilitéd'acceptation pour la famille F3	57

iv

Liste des tableaux

2.1 Exemple d'instance avec n = 5 et m = 5 29

2.2 Machines virtuelles pour l'instance 2.1, H1 30

2.3 Machines virtuelles pour H2 30

2.4 Indice de Palmer Heuristique H3 31

2.5 Indice de Palmer pour H4 32

2.6 Machines virtuelles pour l'instance 2.1, H5 33

2.7 Machines virtuelles pour l'instance 2.1, H6 34

2.8 Machines virtuelles pour l'instance 2.1, H7 35

2.9 Résumédes heuristiques proposées 35

2.10 Procédures de recherche taboue 40

3.1 Familles des instances tests 45

3.2 Nombres moyens d'itérations pour avoir la stagnation, RT1 . 48

3.3 Nombres moyens d'itérations pour avoir la stagnation, RT2 . 48

3.4 Nombres moyens d'itérations pour avoir la stagnation, RT4 . 49

3.5 Nombre d'itération pour appliquer l'aspiration 49

3.6 Valeurs moyennes de ?f pour cinq familles d'instance . . . 52

3.7 Résumédu tableau 3.6 page 52 52

3.8 Valeurs initiales de T pour les cinq familles d'instances . . . 53

3.9 Probabilitépour ?f = 0 en pourcentage sur 2000 itérations 54

3.10 Résume du tableau 3.9 page 54 54

3.11 Nombre de vérifications du critère de Metropolis 54

3.12 Valeurs finales de T pour les cinq familles d'instances 55

3.13 Résultats des heuristiques, Familles F1, F2 et F3 (m = 5) . 58

3.14 Résultats des heuristiques Familles F4 et F5 (m = 5) . . . 59

3.15 Résultats des heuristiques, Familles F1, F2 et F3 (m = 10) 59

3.16 Résultats des heuristiques Familles F4 et F5 (m = 10) . . . 60

3.17 Meilleurs heuristiques pour m = 5 60

3.18 Meilleurs heuristiques pour m = 10 61

3.19 Résultats méta-heuristiques pour F1, m = 5 62

3.20 Résultats méta-heuristiques pour F2, m = 5 63

3.21 Résultats méta-heuristiques pour F3, m = 5 63

v

3.22 Résultats méta-heuristiques pour F4, in = 5 63

3.23 Résultats méta-heuristiques pour F5, in = 5 64

3.24 Temps de Calcul pour in = 5 65

vi

Liste des Algorithmes

1.1	Algorithme de Johnson	16
1.2	Heuristique NEH	18
1.3	Heuristique RJ de Potts	19
2.1	Algorithme de descente	38
2.2	Recherche Taboue	40
2.3	Algorithme RTG	41
2.4	Pseudo code Recuit Simulé	42
3.1	Recherche Taboue avec aspiration	50
3.2	Critères d'arrêt pour RTG	51

0

Notation

Notations générales

n Nombre de jobs à ordonnancer

J L'ensemble des n jobs,J = {J1, J2, ... Jn}

Pik Temps opératoire du job i sur la machine k

Ci Date de sortie du job i de l'atelier

Cmax(7r) Makespan de la solution 7r

C^*Makespan optimal.

max

ri Date de disponibilitédu job i (Release Date)

qi Date de livraison du job i (Delivery Time)

7r(k) ou 7rk k^eme job de la permutation 7r .

Fm+1 | T = m | Cmax Flow shop hybride à deux étages avec machines dédiées.

Fm+1 | T = m, ri, qi | Cmax Flow shop hybride à deux étages avec machines dédiées, avec dates de disponibilitéet délais de livraison

Notations pour Fm+1 T = m, ri, qi Cmax

Typek Ensemble des jobs de type k, k E {1,... , m}

M_c L'unique machine du premier étage (la machine commune)

Mk La machine du second étage dédiée aux jobs de type k, k E {1, ... m}

nk Le nombre de jobs de type k, k E {1, ... m}

ai Temps opératoire du job i sur M_c

bi Temps opératoire du job i sur Mk, oùJi E Tk

7r^k Une sous permutation de 7r contenant les jobs de Tk.

C^kmax(⁷r) Date d'achèvement du dernier job de la séquence 7r sur Mk

1

Introduction générale

La fonction Production est un maillon important de la chaine logistique agissant directement sur la performance de l'entreprise. La maitrise de cette fonction est tributaire des méthodes d'organisation et d'exploitation des ressources dont l'entreprise dispose. En effet, l'amélioration de la performance des entreprises est une nécessitépréoccupante qui passe par l'optimisation de l'exploitation des ressources, la maitrise des coûts de production et le respect des délais. Pour faire face à une telle situation, l'entreprise doit agir sur le système de production en particulier sur les niveaux tactique et opérationnel oùse situe la fonction de l'ordonnancement, « qui consiste à organiser dans le temps l'exécution d'opérations interdépendantes à l'aide de ressources disponibles en quantitélimitépour réaliser un plan de production »[18].

Le travail présentédans ce présent mémoire traite le problème d'ordon-nancement de type Flow Shop hybride avec machines dédiées, avec dates de disponibilitéet délais de livraison.

Le premier chapitre permet d'introduire la problématique de l'ordonnan-cement. Nous présentons en premier lieu les notions de base et les différents éléments qui composent un problème d'ordonnancement. Après avoir rap-peléla codification utilisée permettant de les caractériser, nous présentons une classification des problèmes d'ordonnancement, leurs complexitéainsi que les méthodes de résolutions. En second lieu, nous présentons le problème étudiéainsi que ces différentes propriétés particulières, nous nous pencherons ensuite sur la non dominance des solutions de permutation qu'on a adoptées pour ce problème. Bien qu'il existe une importante littérature qui traite les problèmes de flow shop, les papiers traitant le flow shop avec prise en compte des dates de disponibilitéet des délais de livraison sont rares. Un état de l'art sera dressépour les problèmes semblables au notre dans le but d'approfondir nos connaissances et mieux guider nos recherches notamment sur le choix des méthodes de résolution à adopter.

Le deuxième chapitre présente les méthodes de résolution adoptées pour

Introduction 2

notre problème. En premier lieu nous décrivons les bornes inférieures que nous avons établies pour évaluer les résultats des heuristiques et des méta-heuristiques que nous avons implémentés. Ensuite nous proposons des heuris-

tiques inspirées de celles présentées dans la littérature que nous avons adaptéà notre problème. Nous présentons les méta-heuristiques en commençant par des notions de bases pour décrire ensuite les méta-heuristiques qu'on a retenues à savoir la recherche Taboue et le Recuit Simulé. Nous avons développédifférentes variantes de la recherche taboue afin d'en tirer la meilleure, nous

avons ainsi fusionner ces variantes dans une seule procédure qu'on comparera avec la procédure du Recuit Simulé. L'ensemble des bornes inférieures et des différentes méta-heuristiques ont étéimplémentées en utilisant le C++.

Le troisième chapitre s'intéresse au paramétrage des méta-heuristiques et des résultats expérimentaux. En effet, les décisions concernant le paramétrage des méta-heuristiques doivent être prises avec soin, nous présentons une étude empirique pour les deux procédures afin de justifier les choix qu'on a adoptés. En second lieu, nous exposons et interprétons les résultats des heuristiques et des méta-heuristiques.

Finalement, nous clôturons ce présent mémoire par une conclusion et des perspectives de recherche.