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.

Chapitre 1

Problèmes d'ordonnancement

Problèmes d'ordonnancement 4

Introduction

Ce chapitre se propose de présenter les constituants et la classification des problèmes d'ordonnancement ainsi qu'une codification très répandue dans la littérature. Quelques notions de complexitésont exposées afin de mieux comprendre la difficultéde la résolution de certains problèmes. Nous présenterons le problème considérédans ce présent mémoire ainsi que ces particularité. La fin de se chapitre se focalise sur un état de l'art pour les problèmes de type Flow Shop et les méthodes de résolution utilisées dans la littérature.

1.1 Notions préliminaires 1.1.1 Définitions

En logistique de production comme en gestion de projets, il est difficile de se passer de l'ordonnancement vue son rôle capital, intervenant dans des niveaux de décision à la fois tactiques et opérationnels. L'ordonnancement vise à contrôler, à court ou moyen terme, l'activitéd'un ensemble de ressources disponibles en quantitélimitée, en gérant les conflits d'utilisation que pose la réalisation d'un ensemble d'activités sur un horizon de temps généralement imposé.[47]

Plusieurs définitions d'un problème d'ordonnancement sont données dans la littérature, nous retenons ici celle proposée par P. Esquirol [19] :

« Le problème d'ordonnancement consiste à organiser dans le temps la réalisation de tâches, compte tenu de contraintes temporelles (délais, contraintes d'enchaînement, ...) et de contraintes portant sur l'utilisation et la disponi-bilitéde ressources requises.»

Un problème d'ordonnancement peut être considérécomme un sous-problème de planification dans lequel il s'agit de décider de l'exécution opérationnelle des tâches (jobs) planifiées, et ainsi d'établir leur planning d'exécution et leur allouer des ressources visant à satisfaire un ou plusieurs objectifs sous une ou plusieurs contraintes. En se basant sur les concepts de tâche, ressource, contrainte et objectif, l'ordonnancement peut également être défini comme :

« Ordonnancer un ensemble de tâches, c'est programmer leur exécution en leur allouant les ressources requises et en fixant leur date de début.»[9]

Problèmes d'ordonnancement 5

FIGURE 1.1 - Problèmes d'ordonnancement d'atelier d'après J.C Billaut [4]

Un job i, appartenant à un ensemble J de jobs à ordonnancer, est une entitéélémentaire de travail représentée dans le temps par une date d'entrée dans l'atelier et une date de sortie de l'atelier, caractérisée par une gamme de production et un ensemble de ressources spécifiques à sa réalisation.

La réalisation d'un job nécessite l'exploitation d'un ensemble de ressource de disponibilitélimitée dont une gestion optimale de leurs utilisations représente le but de la résolution de certains problèmes d'ordonnancement.

Notons que dans le cas de l'ordonnancement d'atelier, le terme machine est généralement utiliséà la place de ressource.[47]

1.1.2 Classification

La classification des problèmes d'ordonnancement se fait généralement selon la nature des variables mises en jeu, la nature des contraintes, ou encore le type d'organisation ainsi que les gammes de production.

Nous retenons une classification proposée par J.C Billaut [4], qui a ^étécitée à plusieurs reprises dans la littérature.

Problèmes d'ordonnancement 6

On peut distinguer plusieurs types de problèmes d'ordonnancement d'atelier dont:

- le problème à une machine oùchaque job est assimiléà une opération unique, exécutée par une seule et même machine.

- le problème Job Shop oùchaque job a sa propre gamme opératoire.

- le problème Flow Shop oùtous les jobs ont la même gamme de production.

Un Flow Shop Hybrid FSH se compose d'une série d'étages de production, dont chacun comprend des machines parallèles. Certains étages peuvent avoir une seule machine, mais au moins un étage doit avoir plusieurs machines.

Le passage des jobs dans l'atelier est unidirectionnel, et chaque job est exécutésur une seule machine par étage [17]. Les machines à chaque étage peuvent

être identiques, uniformes ou non reliées.

En revanche, s'il n'y a qu'une seule machine à chaque étage, alors on se ramène à un problème traditionnel de flow shop sériel .

1.1.3 Codification

Plusieurs codifications ont étéproposées dans la littératures, elles servent à décrire l'atelier et ses caractéristiques (nombres de machines, nombre d'étage, type de machine, etc . . .), les contraintes et les spécificités des jobs et leurs natures d'exécution (préemption, ressources auxiliaires, contraintes de précédence, date de disponibilité, etc . . .), et aussi les critères d'optimisation considérés (minimisation des coûts, du temps, du retard, etc . . .).

Nous utiliserons la codification à trois champs proposée par R. Graham [31] et reprise ensuite par Blazewicz [5] : á â ã.

Le champ á correspond à la description physique de l'atelier (machine environment) , ce champ est généralement composéde deux éléments décrivant le type de l'atelier et le nombre des machines utilisées.

Par exemple, pour á = P_m : atelier à m machines parallèles identiques, et pour á = F2 : Flow shop à deux machines .

Le deuxième champ â décrit les contraintes et les caractéristiques des jobs (Job characteristics). Il peut être vide, comme il peut contenir plusieurs champs.

Par exemple, pour â = ri : chaque job i a sa propre date de disponibilitéri, et pour â = qi : c'est le délais de livraison, indique que chaque job i a une durée donnée à passer avant de quitter l'atelier.

Problèmes d'ordonnancement 7

Le troisième champ renseigne sur les critères d'optimisation choisis, ces

critères se basent généralement sur les indicateurs suivants :

- Ci : date de sortie du job i de l'atelier

- Li et Ti = max(Li, 0) : le retard du job i

- Ui : indiquant si le job i est en retard ou non

Ces critères varient selon l'objectif de l'optimisation à savoir la minimisation du coût de production, de stockage, du respect des délais de livraisons ou le taux du temps d'immobilisation des ressources.

Notons ici que le critère le plus utiliséest celui de la minimisation de la durée totale d'achèvement (makespan).

1.1.4 ComplexitéLa complexitédes problèmes ordonnancement est définie suivant la com-

plexitédes méthodes de résolution et celle des algorithmes utilisés .

Selon Garey et Johnson [21], la complexitéd'un algorithme est exprimée par le nombre d'instructions élémentaires exécutées pendant son exécution. C'est une fonction exprimant le temps d'exécution au pire des cas, en fonction de la taille de l'instance étudiée du problème.

On distingue les algorithmes selon leurs complexités par :

- Algorithme polynomial : c'est un algorithme dont le nombre d'instruc-tion est expriméen fonction de n (oùn est la taille du problème) de la manière suivante : O(n^x) (pour un certain x).

- Algorithme exponentiel : un algorithme dont le nombre d'instruction s'exprime comme suit : O(xⁿ) (avec x est un entier), i.e. le nombre d'instruction n'est pas bornépar un polynôme de n.

Par ailleurs, la complexitédes problèmes de décision est classéessentielle-ment selon deux classes :

- Classe P : classe des problèmes pouvant être résolus en un temps polynomial, i.e. on a trouvéun algorithme de complexitéO(n^x) (pour un certain x) qui les résout. la classe P comprend les problèmes dits Facile.

- Classe NP (Non-Deterministic Polynomial Time) : c'est la classe des problèmes qu'on a pas encore trouvédes algorithmes polynomial qui les résout (ou qu'il n'existe pas des algorithmes polynomiales pour les

Problèmes d'ordonnancement 8

Problèmes d'ordonnancement 9

résoudre) , ces problèmes sont en fait associéa des algorithmes exponentiels .

Un problème de décision est un problème admettant uniquement deux réponses possibles : «oui», ou «non», alors que pour un problème d'optimi-sation on doit chercher à déterminer une solution qui optimise un critère donné, notons qu'àchaque problème d'optimisation on peut associer un problème de décision. On peut donc classéles problèmes d'optimisation selon les problèmes de décisions qui leur sont affectés; on dit par exemple qu'un problème d'optimisation est NP-difficile si le problème de décision associéest NP-Complet.

1.1.5 Représentation des problèmes d'ordonnancement

Un problème d'ordonnancement peut être représenter à l'aide de plusieurs méthodes, à savoir la méthode PERT(Program Evaluation and Review Technique , la méthode MPM (Méthode des Potentiels Métra) et le diagramme de Gantt.

La solution d'un problème d'ordonnancement est généralement représentée par le digramme de Gantt, ce diagramme a étéinventéen 1917 par Henry L. Gantt pour modéliser la planification des tâches nécessaires à la réalisation d'un projet. Grâce à sa facilitéde lecture et mise en place ce diagramme est toujours le plus utilisé.

1.2 Méthodes de résolution

Plusieurs spécialistes à savoir P. Lopez [51] et G. Cavory [11] ont ^distinguéessentiellement deux classes de méthodes de résolution :

- Les méthodes de résolution exactes permettant de donner des solutions optimales en un temps polynomial avec une taille limitédu problème. - Les méthodes approchées dont les heuristiques et les méta-heuristiques qui donnent des solutions approchées en un temps raisonnable.

Pour les méthodes exactes, I.Kacem [42] a distinguétrois sous classes dont la procédure par séparation et d'évaluation (Branch & Bound), la programmation dynamique et la programmation linéaire. Bien que ces méthodes fournissent des solutions optimales, leurs performances notamment en ce qui concerne le temps de calcul diminue proportionnellement avec la taille des problèmes.

Les méthodes approchées toutefois ne donnent aucune garantie d'opti-malitémais elles demeurent les plus utilisées pour la majoritédes problèmes d'ordonnancement et «la plus part des spécialistes ont orientéleurs recherche vers le développement des méthodes heuristiques» [51, 37].

Les méthodes approchées englobent les heuristiques et les méta-heuristiques, Y. Harrath [37] définie ces termes comme suit : «Une heuristique est une méthode de calcul pour un problème générique d'optimisation produisant une solution non nécessairement optimale. Par contre, une méta-heuristique est un ensemble de concepts applicables à un large ensemble de problèmes d'optimisation combinatoire pour créer de nouvelle heuristiques.»

Une classification des différents types de méta-heuristiques est présentépar Widmer et al. [68], les auteurs considèrent qu'ils existe trois types de

méta-heuristiques, les méta-heuristiques constructives basées sur l'idée de la diminution progressive de la taille du problème, les méta-heuristiques évolutives inspirées des phénomènes réels telles que l'algorithme génétique et les colonies de fourmis et les méta-heuristiques de recherche locale dont la recherche taboue et le Recuit Simulé.

La recherche taboue a étéprésentée pour la première fois par Glover [22], la formulation finale de cette méta-heuristiques est apparue en deux partie [23, 24], cette méthode se base sur deux principe. le premier principe consiste à crée le voisinage de la solution courante à chaque itération et choisir le meilleur voisin et le deuxième principe consiste à garder en mémoire les dernières solutions visitées afin d'interdire le retour vers des régions visitées pour un nombre d'itérations fixé.

Le recuit simuléest une méthode de recherche locale dont le mécanisme de recherche est calquésur l'algorithme de Metropolis et al. [53] et les principes du recuit thermodynamique. L'idée se base sur une analogie entre l'énergie du système physique et la fonction objectif du problème d'optimisation et entre les états de ce système physique et les solutions réalisable du problème. Kirkpatrick et al. [44] et Cerny [12] ont étéles premiers à s'inspirer d'une telle technique pour résoudre des problèmes d'optimisation combinatoire.

Plusieurs problèmes de flow shop sont traités par ces deux méta-heuristiques (voir section état de l'art).

Problèmes d'ordonnancement 10

FIGURE 1.2 - Sous permutation au second étage

1.3 Présentation du problème étudié

Dans cette section, nous cherchons à présenter le problème considérépar le présent mémoire. En effet, il s'agit d'un problème de flowshop hybride avec machines dédiées, avec dates de disponibilitéet délais de livraison :

Fm+1 | T = m, ri, qi | Cmax

Ce problème décrit un atelier qui se compose de deux étages, avec une seule
machine au premier étage appelée machine commune M_c et m machines

au deuxième étages appelées machines dédiées. Les jobs sont disponibles ^àl'atelier à des dates appelées dates de disponibilitéri, ils s'exécutent en pre-

mier lieu sur la machine commune puis suivant le type de job Typek (avec k E {1, . . . , m}), le job sera exécutésur une seule machine au deuxième étage. Enfin tous les jobs ont des durées appelées délais de livraison qi à passer avant de quitter l'atelier. Les temps opératoires ainsi que les dates ri et délais qi sont supposés supérieurs à zéro, et les machines du deuxième étage sont indépendantes les unes des autres. Notons ici qu'une machine ne peut exécuter qu'un seul job à la fois. Le passage des jobs est unidirectionnel et chaque jobs doit ainsi s'exécuter sur deux machines.

D'autre part, dans cette configuration les jobs seront répartis, au second étage, en sous permutations selon leurs Type notée ð^k oùk E {1, . . . , m}, d'oùtout job peut être identifier par une sous permutation et une position correspondante.

Soient S une sous permutation de ð et ñ la position du job j dans S, le job j peut être identifiépar ð^ä _ñ. A ` titre d'exemple, soit la permutation suivante : ð =? J1J6J5J3J2J4 ?, les jobs seront répartis sur les machines du second étage comme indique la Figure 1.2.

Problèmes d'ordonnancement 11

Le job J3 peut être identifiépar sa sous permutation à savoir Ir¹ et sa position dans cette sous permutation 2, on note Ir¹₂.

1.3.1 Calcul du makespan

Pour le problème _Fm+1 T = m, ri, qi _Cmax, le calcul du makespan pour une solution donnée passe par la recherche du chemin critique sur la succession des opérations qui se définit comme étant le chemin le plus long sur l'ensemble des chemins possibles. Un chemin peut être définit par la donnée de trois jobs Ir_u, Ir_v et Ir^k_w avec 1 < u < v < net 1 < w < nk (voir Figure 1.3) qui vont définir une succession d'opérations des jobs sur les machines M_c et Mk. L'ordre de passage des ces jobs en partant de la date de disponibilitédu premier job r_u, en passant par les durées opératoires sur la machine commune (on tient compte des jobs ordonnancés entre Ir_u et Ir_v), ainsi que celles sur la machine Mk (Ir_v ... Ir^k_w) constitue un chemin d'opération dont la longueur Cl(u, v, w, k) constitue une borne inférieure sur le makespan de la solution. La formule de calcul de la longueur du chemin l(u, v, w, k) est donc la suivante :

Cl(u, v, w, k) = (rðu +

?v i=u

aði +

?w i=v^'

bðk i + qðkw) (1.1)

Avec

1 < u < v < n

k

Ir_v = Ir_v'

v' < w < nk

Oùv' est la position du job Ir_v sur la machine Mk, i.e Ir_v = Ir^k_v'

Le makespan d'un ordonnancement est égale à la date de sortie du dernier job de l'atelier, c'est à dire qu'il correspondent au chemin le plus long. On peut ainsi écrire :

Cmax = Max(Cl(u, v, w, k)) (1.2)

1<u<v<n

ð_v=ðk

_v'

v<w<n_k 1<k<m

Problèmes d'ordonnancement 12

- _?v aði = 2 aji = 6

i=u i=1

-

?w i=v^'

bðk i =

2 ? i=1

bð2 i = 6 + 1 + 5 = 12

FIGURE 1.3 - Calcul du makespan

(avec v^' = 1 et w = 2 : positions des jobs j2 et j4 sur la machine M2 )

Exemple

Afin de mieux illustrer le mode de calcul, on considère une instance à 5 jobs et 2 machines au second étage, cherchons le makespan de la solution ð =? j1j2j3j4j5 ?.

Jobs ri ai bi qi Type

1	2	4	4	5	1
2	5	2	6	6	2
3	3	3	5	5	1
4	4	4	5	14	2
5	6	4	7	4	1

Soit un chemin critique définissant le makespan caractérisépar les trois jobs ð_u, ð_v et ð_w (avec ð_u = j1, ð_v = j2 et ð_w = j4).

en appliquant la formule précédente on obtient :

- r_u = r1 = 2

Problèmes d'ordonnancement 13

Problèmes d'ordonnancement 14

- qðk w = q?k 4 = 14

En faisant la somme on obtient Cmax = 34, la Figure 1.4 représente cette solution à l'aide du diagramme de Gantt.

FIGURE 1.4 - Exemple pour le calcul du makespan

1.3.2 Solutions de permutation

Nous allons prouver la non dominance des solutions de permutation ^àl'aide de l'instance suivante du F2 ri, qi Cmax :

Jobs ri ai bi qi

j1	10	3	13	5
j2	14	3	1	12

Pour cette instance on considère les solutions réalisables suivantes :

1. ð^' = -< _j1j2 >- pour les deux machines (solution de permutation).

2. ð^?= -< _j2j1 >- pour les deux machines (solution de permutation).

3. ð^''' = -< _j1j2 >- sur la machine M_c puis -< _j2j1 >- pour la machine du second étage.

En calculant les valeurs de makespan pour chacune de ces solutions on obtient :

- Cmax(ð^') = 39 - Cmax(ð^?) = 39 - C_max(ð^''') = 36

On constate que le makespan de la solution du non permutation C_max(ð^''') est inférieur aux makespan des deux solutions de permutation, on peut ainsi conclure quant à la non dominance des solutions de permutation pour le problème du Flow Shop à deux machines F2 ri, qi _Cmax, par conséquence, les solutions de permutation ne sont pas dominantes pour _Fm+1 T = m,ri,qi Cmax.

Bien qu'elles ne sont pas dominantes, nous avons fait le choix de travailler avec les solutions de permutation, d'une part pour des raisons de simplification du problème, et d'autre part car dans l'industrie on choisit naturellement les solutions de permutation pour leurs facilitéde mise en oeuvre.

Nous rajoutons finalement que la coexistence des deux paramètres (date de disponibilitéet délais de livraison) sont à l'origine de la non dominance des solutions de permutation. En revanche les solutions de permutation sont dominantes pour les problèmes F2 ri _Cmax et F2 qi Cmax.

Problèmes d'ordonnancement 15

En ce qui concerne les rapports d'approximation, Potts a proposéune heuristique avec un rapport d'approximation de 4 3 pour le problème 1 ri

1.4 État de l'art

L'étude d'un problème nécessite une revue bibliographique des travaux antérieurs portants sur le même problème étudiéou plus généralement sur le même axe de recherche.

Bien qu'il existe une importante littérature qui traite les problèmes de flow shop ( Gupta et Stafford [33] l'estiment à 1200 articles), les papiers traitant le flow shop avec prise en compte des dates de disponibilitéet des délais de livraison sont rares.

Compte tenu de la particularitéde notre problème et l'absence -ànotre connaissance- d'articles traitant ce problème, on va s'intéresser aux travaux qui ont traitédes problèmes semblables au notre. En effet, la revue des travaux qui ont traitéle problème de flow shop sériel que ce soit à deux machine ( F2 _Cmax ) ou à in machine ( F_{m Cmax)} ainsi que le flow shop hybride avec machines dédiées _Fm+1 T = in _Cmax nous sera très utile.

Dans ce qui suit, nous exposerons une revue de littérature pour ces problèmes.

1.4.1 Problèmes de flow shop avec prise en compte des dates de disponibilitéet des délais de livraison

Le problème que nous considérons _Fm+1 T = in, ri, qi _Cmax est une généralisation du problème de flow shop à une machine 1 ri, qi _Cmax et ce dernier est équivalent à 1 ri _Lmax [71].

Selon deux revues proposées par Nowicki et al. [56] et Grabowski et al.[30], ces problèmes ont reçu une considérable attention depuis les années 70. Bien que Lenstra et al. [50] ont montréque le problème 1 ri, qi Cmaxest NP-difficile au sens fort, il existe des algorithmes polynomial pour certains cas particuliers [49].

Les méthodes énumératives pour résoudre les problèmes 1 ri, qi Cmax et 1 ri _Lmax ont étéétudiés dans [30, 8, 3, 52]. Les tests ont mis l'accent sur l'algorithme de Carlier [8] qui s'est avéréle plus prometteur notamment pour les grandes tailles des problèmes (il a réussi à résoudre des problèmes de tailles allant jusqu'à10.000 jobs).

Grabowski [30] a proposéune PSE pour le problème 1 ri _Lmax basésur la notion des blocs de jobs, il affirme que son approche a réussi à résoudre les problèmes F2 ri _Lmax et F ri Lmax.

Problèmes d'ordonnancement 16

L'auteur a proposéune règle permettant d'avoir un ordonnancement op-

Cmax. Ce résultat a étéamélioréavec un rapport de⁵ ₄. Dans ce contexte, Hall et Shmoys [35] ont proposéun algorithme avec un rapport d'approximation de ⁴ ₃. Ils ont également proposédeux schémas d'approximation. D'autres algorithmes approximatifs pour ce même problème ont étéétudiés dans [56, 64, 60, 45, 8].

1.4.2 Méthodes heuristiques

Les méthodes heuristique sont les plus utilisées pour la majoritédes problèmes d'ordonnancement, et elles semblent être la seule approche de résolution des problèmes de grande taille. Les travaux sont nombreux, nous ne rappelons ici que ceux qui ont influencénos travaux, en commençant par Johnson [40], Palmer 1965 [59], Campbell et al. 1970 [7], Nawaz et al. 1983 [55] et Potts 1985 [60].

+ Heuristique de Johnson [40]

S. M Johnson présentait en 1954 un papier qui a traitéles problèmes de flow shop à deux machines ayant pour objectif la minimisation du makespan F2 || Cmax et celui à trois machines F3 || Cmax. Cet article est probablement le plus citédans la littérature.

Algorithme 1.1: Algorithme de Johnson

début

Soient, 81 et 82 deux séquences partielles.

-, Étape 1 :

81 = Ø et 82 = Ø

-, Étape 2 :

Chercher dans J le job _Ji0 tel que :

ai0 = min{ai, bi} ou bi0 = min{ai, bi}

i?J i?J

-, Étape 3 :

si ai0 = min{ai, bi} alors

i?J

Placer _Ji0 à la fin de 81

si bi0 = min{ai, bi} alors

i?J

Placer _Ji0 au début de 82

si J =? Ø alors Aller à l'étape 2

retourner solution optimale en concaténant 81 et 82.

Problèmes d'ordonnancement 17

timal, elle peut être décrite comme suit : soient ai et bi les durées opératoires respectivement pour la première et la deuxième machine, si pour deux job i et j on a min(ai, bj) min(aj, bi) alors il existe une solution optimale oùle job i précède j.

L'Algorithme 1.1 formulépar Carlier et al. [9] illustre cette règle.

Selon Conway et al. [14], cet article a pousséla communautédes chercheurs en ordonnancement à accepter le makespan comme critère d'optimi-sation. La complexitéde l'algorithme de Johnson est de O(nlogn).

+ Heuristique de Palmer [59]

Cette heuristique a étéaussi proposéparmi les premières heuristiques développées pour le F_m || Cmax, elle est une extension de la règle SPT (Shortest Processing Time) dans la mesure oùles jobs sont classés dans l'ordre croissant de leur tendance à avoir des temps opératoires plus long à la fin de la séquence d'opération.

Cette heuristique consiste à calculer pour chaque job un indice comme suit :

f(i) = _?n (m - 2j + 1).Pij Vi E {1,...,n} j=1

Les jobs seront ensuite ordonnancés selon l'ordre croissant de leurs indices. La complexitéde cette heuristique et de O(nlogn + n.m).

+ Heuristique NEH [55]

Nawaz et al. ont proposéune heuristique de construction pour le F_m || Cmax. L'idée consiste à construire itérativement une solution complète en cherchant à chaque fois d'insérer un job non ordonnancéau meilleur emplacement dans une séquence partielle. Cette heuristique a une complexitéde O(m x n²).

De nombreux chercheurs notamment Taillard [66] et Framinan et al. [20] ont confirméla supérioritéde cette heuristique (pour plus de détails veuillez consulter [43]).

On peut illustrer cette procédure comme elle a étéprésentée par M. Nawaz par les étapes de l'Algorithme 1.2.

Problèmes d'ordonnancement 18

Algorithme 1.2: Heuristique NEH

_?m Pij j=1

Étape O

Pour chaque jobs j calculer : Ti =

Étapes

Ordonnancer les jobs selon l'ordre décroissant de Ti

'Etape ?

Prendre les deux premiers jobs de la liste triée à l'étape 2 et trouver la meilleur séquence en calculant le makespan des deux séquence

possibles. Ne pas changer l'ordre relatif des deux jobs dans le reste de

la procédure.

Soit j = 3; Étape O

Prendre le job de la j^eme position de la liste générée à l'étape 2 et

trouver la meilleure séquence en l'insérant dans toutes les positions possibles de la séquence partielle obtenue à l'étape précédente sans changer l'ordre des jobs déjàfixés. 'Etape @

Si j = n alors Arrêter la procédure, sinon retourner à l'étape 4.

+ Heuristique de Potts [60]

C. N. Potts [60] présente des heuristiques pour le problème F2 ri Cmax dont l'heuristique RJ qui est une combinaison des heuristiques suivantes : L'heuristique R qui consiste à ordonnancer les jobs selon l'ordre croissant des ri et l'heuristique J pour ordonnancer selon l'ordre de Johnson. L'euristique RJ consiste à ordonnancer les jobs selon l'ordre croissant des ri puis chaque fois oùun job est disponible on l'injecte dans la séquence en appliquant l'ordre de Johnson, l'Algorithme 1.3 décrit cette heuristique.

L'auteur a aussi proposéune heuristique appelée RJ^' qui consiste ^àexécuter l'heuristique RJ en mettant à jour la date de disponibilitéri ^àchaque itération.

Grabowzki [26] affirme qu'il a testécette heuristique et qu'elle fournit des résultats spectaculaires, ainsi elle a donné238 solutions optimales pour 240 problèmes testés.

Problèmes d'ordonnancement 19

Algorithme 1.3: Heuristique RJ de Potts

Étape O

Soit S : l'ensemble des jobs, K = 0

Trouver T = min{ri}

iES

Étape ?

Trouver : S^' = {j j E S, ri < T, ai < bi}

S^?= {j j E S, ri < T, ai > bi}

si S^' =? 0 alors

Trouver le job i E S^' avec az le plus faible possible

si S^' = 0 alors

Trouver le job i E S^?avec bz le plus grand possible

Étape ?

K +- K + 1;

Ordonnancer i à la position K ;

T +- T + az ;

S +- S - {i};

Étape O

si S = 0 alors

Arrêter l'algorithme

sinon

T = max{T, min{ri}};

iES

Aller à l'étape (c) ;

1.4.3 Méthodes méta-heuristique

La résolution méta-heuristique des problèmes de flow shop fait souvent intervenir la recherche Taboue (RT), le Recuit simulé(RS), les algorithmes génétiques (AG) et les colonies de fourmis. Nous présenterons brièvement quelques travaux traitant avec les AG puis nous parlerons des travaux faisant intervenir la RT et le RS.

Selon une revue proposée dans [63], l'algorithme génétique a étéutilisépar Xiao et al. [70] pour traiter le problème de flow shop à m étage, le même

problème avec des durées de chargement (Setup times) a étéabordépar Kurz et Askin [46] en proposant aussi un AG. Un problème de flow shop hybride à trois étage inspiréd'un problème réel dans l'industrie de fabrication des circuits a étéétudiépar Jin et al. [39] en présentant un AG. Dans [58], Oguz

Problèmes d'ordonnancement 20

Problèmes d'ordonnancement 21

el al. ont comparéune recherche Taboue avec un AG similaire à celui présentédans [70], les tests ont confirméque l'AG a obtenu des meilleurs résultats.

Un autre AG a étéproposépar Ruiz et Maroto [62] pour la minimisation du makespan dans un problème de flow shop à in étage avec machines parallèles,

cet algorithme a prouvésa supérioritépar rapport à d'autres approches ^àsavoir le RS, la RT et d'autres AG. Un problème similaire avec des machines indépendantes dans chaque étage ainsi que des durées de chargement a ^étéabordédans [41], les auteurs ont proposéun AG, une RT et une procédure de

RS, les tests ont étéeffectuépour comparer ces approches entre elles avec des tailles dépassant les 50 jobs et 20 étages, la procédure du RS s'est avérée la plus performante, l'objectif étant la minimisation du makespan et le nombre des jobs en retard.

Concernant la RT et le RS, Houari et Mhallah [36] ont étudiéun problème de flow shop hybride à deux étage avec in machines parallèles dans chaque étage. Ils ont présentédeux méta-heuristiques, une procédure de recherche Taboue et une procédure de Recuit Simulé. Nowicki et Smutnicki [57] ont aussi proposéune méthode de recherche Taboue pour le problème de flow shop hybride à in étages qui utilise un opérateur d'insertion pour générer le voisinage de la solution courante. Dans [67] Wardono et Fathi ont pro-poséune méthode constructive dans une procédure de recherche Taboue. Pour ce même problème, Jin et al. [38] ont proposée deux procédures de Recuit Simuléqui diffèrent l'une de l'autre par la façon d'affection des jobs au différents étages. Grabowski et Wadecki [29] ont présentéune recherche Taboue pour le problème F_m || Cmax, la génération du voisinage repose sur le calcul des bornes inférieures pour évaluer les mouvements afin de sélectionner le meilleur, dans cette procédure la liste taboue avait une longueur dynamique qui est modifiée de manière cyclique, les auteurs affirment qu'ils ont com-parécette procédure avec d'autre procédures discutées dans la littérature et qu'elle fournit des résultats sensiblement meilleurs. Chen et al. [13] ont présentéune recherche Taboue pour le flow shop flexible à deux étages, Une autre recherche Taboue a étéprésentépar Grabowski et Pempera [27] pour un problème de flow shop hybride sans attente inspiréd'un vrai problème industriel.

Dans la suite nous reprenons les travaux de Houari et Mhallah qui ont présentéune étude comparative entre deux méta-heuristiques à savoir le Recuit Simuléet la recherche Taboue pour le problème de flow shop hybride ^àin étage.

Pour le Recuit Simulé, les auteurs ont utilisédeux opérateurs de changement à savoir l'opérateur a - opt et ma - opt, bien que le premier opérateur est un cas particulier du deuxième opérateur, il est utiliséau début de la recherche pour éviter de détruire la structure de la solution de départ, ensuite

le deuxième opérateur est utilisépour explorer le grand voisinage ce qui augmente la probabilitéde trouver une meilleure solution [36].

La valeur du paramètre de contrôle T (température) est : T0 = 1.1 X ?0 ^où?0 > 0 est la différence entre le makespan de la solution voisine et le ma-

kespan de la solution courante, les auteurs affirment que cette température garantit une probabilitéd'acceptation égale à 0.4. Le critère d'arrêt admit est le suivant : arrêter la procédure si après trois plateaux (de longueurs L) consécutives on n'enregistre pas d'amélioration d'au moins 2%, avec L = (n - 1)(n + 1)/2. La température est dégradée de l'ordre de 5% toute les L itérations. La recherche Taboue présentépar Houari et Mhallah a aussi utiliséles deux opérateurs de changement, en premier lieu l'opérateur a-opt est utilisé, lorsqu'il explore tout le voisinage en donnant la meilleur solution, la procédure est relancée en utilisant le deuxième opérateur na - opt, selon les auteurs, l'avantage d'adopter une telle approche est de limiter le nombre de solutions examinées dans la première phase pour permettre l'ex-ploration du grand voisinage dans la seconde phase à partir de la meilleur solution donnée précédemment.

La longueur L de la liste taboue est fixée à 10. Cette longueur semble fournir le meilleur compromis pour éviter le phénomène cyclique et le temps de calcul qui augmente avec la longueur L. La liste taboue enregistre la valeur de la fonction objectif de la solution et non pas la solution elle même. L'algo-rithme est redémarrési pour 3 itérations consécutives on n'enregistre aucune amélioration, l'ensemble du processus est réitérétrois fois.

Les tests ont montréque la recherche Taboue proposée donne une solution optimale dans 35% des cas alors que le Recuit simulédonne une solution optimale dans 15% des cas. Concernant l'écart par rapport à la solution optimale, la recherche Taboue étéla meilleur avec un écart inférieur à 1% dans 70% des cas.

1.4.4 Bornes inférieures et PSE

1.4.4.1 Bornes inférieures

Les bornes inférieures proviennent dans la plupart des cas des ordonnancement partiels [10]. Pour le problème F2 ri _Cmax, Tadei et al. [65] proposent cinq bornes inférieures applicables après la division de l'ensemble des jobs en deux sous ensembles de séquences partielles, un sous ensemble des jobs qui ont étédéjàordonnancés et un sous ensemble des jobs à ordonnancer. Ces bornes sont particulièrement utiles pour l'élaboration de PSE performante.

Problèmes d'ordonnancement 22

Dridi et al. [15] se sont inspiréde Oguz et al. pour proposer des bornes inférieures pour le problème _Fm+1 T = m _Cmax, nous ne décrivons ici que les bornes inférieures qui nous seront utiles par la suite.

Soit la première borne donnée par :

?BIDHH0 = JiEJ

ai + min JiEJ

bi

L'auteur affirme que si on considère chaque type k E {1, ... , m} séparément alors forcément la somme de ses durées opératoires sur la machine dédiée avec _minJiEk ai est inférieure à la valeur de makespan optimale. Soit BI0k = minJiEk ai + _>JiETk bi la borne inférieure qu'on vient de décrire, la borne BIDHH1 est donc la suivante :

BIDHH1 = max{ max (BI0_k); BI0; max(ai + bi)}

1<k<m JiEJ

La borne _BIDHH2 est donnée par :

BIDHH2 = E 1<k<m

min JiETk

( ? ai + min bi) ^1<k<mJiETk0

La troisième borne proposée dans [34] repose sur l'ordre de Johnson, elle consiste à créer k sous problèmes (k = {1, ... , m}) à deux machines (la machine M_c et une machine dédiée MK à chaque sous problème notéP^k), l'application de la règle de Johnson fournisse pour chaque sous problème Pk une valeur de makespan notéC^Joh

max(Pk), la borne _BIDHH3 est donc la

suivante :

BIDHH3 = max {C^Joh

max(P k)}

1<k<m

Carlier et Rebai [10] ont proposédes bornes inférieures pour la résolution du problème F_m ri, qi _Cmax, ces bornes ont étéobtenues à l'aide de l'algo-rithme de Johnson et celui de Jackson.

La première borne est obtenue par l'application du JPS (Jackson's preemptive schedule) en considérant le problème F_m ri, qi _Cmax, elle s'écrit comme suit, soient I l'ensemble de tous les jobs et k C I un ordonnancement partiel

LBCR1 = max(min jEk

rj,M+i jEk

pj,M + min qj,M) V M = 1, ... ,m (1.3) jEk

Une autre borne _LBCR2 est obtenue en appliquant l'ordre de Johnson sur deux machines consécutives M et M + 1, elle s'écrit comme suit :

LBCR1 = max(min

iEJ

ri_,M+Johnson(J, M, M+1)+min _iEJqi,M+1) V M = 1, ... , m-1

(1.4)

OùJohnson(J, M, M + 1) représente la valeur de makespan de l'ensemble des jobs J sur les deux machines M et M + 1.

Problèmes d'ordonnancement 23

1.4.4.2 Procédure par séparation et évaluation PSE

Sans aucun doute, la procédure de séparation et évaluation (Brunch & Bound) est la technique préférée pour la résolution optimale des problèmes de flow shop hybride, mais la plupart des recherches ont portésur les versions simplifiées du problème [63]. L'une de ces version simplifiée est le flow shop à deux étages avec une seule machine au premier étage et deux machines au second étage. Selon Ruiz et al. [63] la première procédure traitant ce problème a étéproposépar Rao [61], plus tard, Bolat et al. [6] ont étudiéle même problème en présentant une PSE, des heuristiques et un algorithme génétique. Le problème inverse ou «miroir» de ce dernier (deux machines au premier étage et une seule au second étage) a étéétudiépar Arthanary et Ramaswamy [1] puis par Mittal et Bagga [54]. Les problèmes avec deux étages et in machines parallèles au second étage ont étéétudiés par Lee et Kim [48] en proposant une PSE avec l'objectif de minimiser la somme total des retards. le problème d'assemblage (in machine au premier étage et une seule au second étage) a étéétudiépar Gupta et al. [32] en proposant une PSE générant de bonnes solutions en un temps raisonnable.

Les travaux traitants les problèmes du flow shop avec la prise en compte des dates disponibilitéou des délais de livraison sont très rare notamment en ce qui concerne la résolution exactes utilisant une PSE. Nous présentons dans la suite les travaux de Tadeiet al. [65] et Grabowski qui ont proposédes PSE pour ces problèmes.

Grabowski [25] a proposéune PSE pour le problème F2 ri _Cmax puis il a étendu ses recherches dans [28] pour étudier le problème F_m ri, qi _Cmax, il a présentéun schéma de branchement reposant sur des bornes inférieures obtenues en relaxant la contrainte de capacitédes machines (une machine peut exécuter deux jobs à la fois au lieu d'un seul jobs). La séquence initiale du noeud racine a étéobtenue en appliquant une heuristique. Dans chaque noeud de l'arbre de recherche on a une séquence complète, un chemin critique et une borne inférieure. A ` chaque permutation, une nouvelle séquence est générée en affectant un changement dans le chemin critique, l'auteur affirme que cette approche simplifie les calculs et l'obtention des bornes inférieures.

Tadeiet al. ont présentédeux schémas de branchement pour le problème F2 ri _Cmax. Pour les deux schémas, l'obtention d'une séquence de départ repose sur la règle ERT (Earliest Release Time) qui consiste à ordonnancer les jobs selon l'ordre croissant des dates de disponibilitéri.

Pour le premier schéma de branchement, chaque noeud correspond à une sous séquence de j jobs, les nouveaux noeuds sont générés par l'ajout d'un

Problèmes d'ordonnancement 24

nouveau job à la position j + 1 après l'application des propriétés de dominance, pour la phase de l'évaluation une parmi cinq bornes proposées sera calculée.

Pour la phase de sélection du nouveau noeud, on cherche le noeud avec la borne inférieure la plus faible et on commence une nouvelle phase de génération.

Pour le schéma de branchement dichotomique, chaque noeud correspond ^àun ensemble de contraintes de priorité, les nouveaux noeuds sont générés par

l'ajout de nouvelles contraintes de priorité, ce schéma utilise le même principe que le schéma précédent pour l'initialisation de la sous séquence optimale de départ, puis une propriétéde dominance est appliquée pour la détermination de l'ensemble des contraintes de prioritédu noeud racine, ensuite pour une sous séquence satisfaisant ces contraintes on détermine un chemin critique contenant deux blocs critiques, pour la phase de génération, de nouveaux noeuds sont générés en examinant les deux blocs dérivés.

Les tests effectués pour plusieurs classes d'instances (10 classes) sur des tailles différentes des problèmes (jusqu'à200 jobs) indiquent que le premier schéma était plus performant que le schéma dichotomique (notons que le temps de calcul était limitéà 300 secondes).

conclusion

Après avoir présentéles notions de base pour l'ordonnancement, nous avons présentéle problème étudié, en effet, le présent mémoire considère un problème de flow shop hybride avec machines dédiées, avec dates de dis-ponibilitéet délais de livraison. Bien que les problèmes de flow shop sont les plus étudiés dans la littérature, les travaux portant sur des problèmes semblables au notre sont très rares. Nous avons orienténos travaux vers

le développement et l'adaptation des méthodes de résolution approchées ^àsavoir les heuristiques et le méta-heuristiques.

Chapitre 2

Présentation des méthodes de

résolution

Présentation des méthodes de résolution 26

Introduction

Pour la résolution de notre problème, on a optépour les méthodes approchées étant donnéles avantages qu'elles offrent telles que la rapiditéde leurs exécutions, leurs flexibilité¹.

Dans le présent mémoire, on a travailléavec des méta-heuristiques bien confirmées notamment la recherche taboue et le recuit simulé. En ce qui concerne les heuristiques, on a adaptéet implémentédes heuristiques spécifiques très connues à savoir le fameux algorithme de Johnson, l'heuristique de Palmer, l'heuristique NEH et l'heuristique de Potts. On a aussi établie sept heuristiques qui se basent essentiellement sur les principes des heuristiques spécifiques de la littérature.

Afin d'évaluer les heuristiques et les méta-heuristiques, et en absence d'une approche exacte, on avait besoin de borner les résultats pour pouvoir évaluer leurs qualités, on a donc établie des bornes inférieures qui seront notre repère d'évaluation.

1. La possibilitéde l'adaptation d'une heuristique à plusieurs problèmes différents ainsi que la possibilitéd'hybridation avec d'autres méthodes.

Présentation des méthodes de résolution 27

2.1 Bornes Inférieures

On utilise la borne inférieure afin de pouvoir borner la solution optimale d'une instance et par la suite évaluer les solutions données par les heuristiques et les méta-heuristiques. Même dans les méthodes de résolution exactes notamment les procédures par séparation et évaluation, la notion de borne inférieure est primordiale car elle permet d'évaluer les racines non prometteuses et par la suite éviter de perdre un temps de calcul important.

En vue d'évaluer les heuristiques et les méta-heuristiques utilisées on a établie cinq bornes inférieures.

2.1.1 Borne inférieure 1

On part du principe qu'on ne peut pas échapper aux maximums des temps d'achèvement lorsque les jobs sont pris un à un.

BI1 = max{ri + ai + bi + qi} (2.1)

i?J

2.1.2 Borne inférieure 2

Il est clair qu'on ne peut pas échapper à l'ensemble des temps opératoires sur la machine commune. Cette borne est améliorépar la prise en compte des minimums des autres durées. Cette borne s'écrit comme suit :

BI2 = min{ri} + i?J

?n i=1

ai + min{bi + qi} (2.2) i?J

OùC* _max(1 ri _Cmax) est la date d'achèvement optimale si on considère uniquement la machine commune et la date de disponibilité.

2.1.3 Borne inférieure 3

Le principe consiste à trier les jobs selon l'ordre croissant des dates de disponibilité, puis calculer le makespan de cette séquence en ne prenant compte que des dates de disponibilitéet des durées opératoires sur la machine commune seulement, ainsi on réduit le problème à un atelier 1 ri _Cmax pour lequel l'ordre croissant des ri est optimal. On y ajoute les minimums des durées opératoires sur les machines du deuxième étage et des délais de livraison. Cette borne s'écrit comme suit :

BI3 = C* max(1 ri _Cmax) + min{bi + qi} (2.3)

i?J

Présentation des méthodes de résolution 28

2.1.4 Borne inférieure 4

Si on considère uniquement les jobs de type k oùk E {1, . . . , m} et en ignorant les paramètres ri et qi, le problème se réduit à un F2 || Cmax avec les machines (M_c, Mk) pour lequel l'ordre de Johnson est optimal.

La borne peut alors s'écrire comme suit :

BI4 = min{ri} + max (C^Joh

max(Mc, Mk)Typek) + min _iEJ {qi} V 1 i n (2.4)

iEJ 1<k<m

OùC^Joh

max (M_c, Mk) est le makespan correspondant à l'ordre de Johnson

pour le problème F2 || Cmax avec les machines (M_c, Mk).

2.1.5 Borne inférieure 5

Le principe est le même que la borne BI2, sauf qu'au lieu de considérer la machine commune M_c, on considère l'une des machines du deuxième étage. Cette borne s'écrit de la façon suivante :

BI5 = min {ri + ai} + max ( bi) + min {qi} (2.5)

iET ypek1<k<miET ypek

Typek

Présentation des méthodes de résolution 29

Les temps opératoires sur les deux machines virtuelles sont décrit dans le Tableau 2.2.

2.2 Heuristiques

Les heuristiques qu'on a implémentées sont dérivées de certaines heuristiques connues pour le F_m || Cmax et le F2 || Cmax tels que l'heuristique de Potts, NEH, l'heuristique de Palmer et la règle de Johnson.

Nous avons tout d'abord implémentéces dernières heuristiques (Johnson, Palmer, NEH) tels qu'elles sont (sans aucune modification), puis nous avons cherchéà les adapter à notre problème dont la configuration est particulière. On a commencépar tester 15 procédures différentes pour en finir avec sept procédures relativement prometteuses.

2.2.1 Heuristique H1

Cette heuristique consiste à modifier la configuration de notre problème pour qu'on puisse appliquer l'algorithme de Johnson. Le problème doit être écrit sous la forme de F2 || Cmax, ce qui nécessite la création de deux machines virtuelles. Avec le but de prendre en compte les paramètres spécifiques de notre problème à savoir la date de disponibilitéri et la date de livraison qi, les durées opératoires av i et bv i des jobs i J sur ces deux machines virtuelles sont définies comme suit :

av i = ri + ai V 1 < i < n
bv i = bi + qi V 1 < i < n

Une fois les deux machines virtuelles sont crées, on applique l'algorithme de Johnson.

Exemple Soit l'instance suivante :

Tableau 2.1 - Exemple d'instance avec n = 5 et m = 5

Jobs	ri	ai	bi	qi
J1	8	4	2	4
J2	6	6	4	10
J3	2	5	9	2
J4	9	6	3	4
J5	9	2	11	1

Présentation des méthodes de résolution 30

Présentation des méthodes de résolution 31

Tableau 2.2 - Machines virtuelles pour l'instance 2.1, H1

Jobs av _i bv _i

J1 12 6

J2 12 14

J3 7 11

J4 15 7

J5 11 12

Maintenant on peut appliquer l'algorithme de Johnson en considérant le problème F2 || Cmax, on obtient l'ordonnancement suivant :

SH1 =< J3J5J2J4J1 >.-

Le makespan de cette solution est Cmax(SH1) = 33.

2.2.2 Heuristique H2

Le principe de cette heuristique est semblable à celui de l'heuristique H1, mais cette fois la première machine virtuelle aura comme durées opératoires les dates de disponibilité, et la seconde machine virtuelle aura comme durées opératoires la somme des durées ai, bi et qi pour chaque job i E [1, n] :

av i = ri V 1 < i < n

bv i = ai + bi + qi V 1 = i = n

Une fois les deux machines virtuelles sont crées, on applique l'algorithme de Johnson.

Exemple Soit les valeurs de l'instance donnés dans le Tableau 2.1, les durées opératoires sur les machines virtuelles sont données dans le Tableau 2.3.

Tableau 2.3 - Machines virtuelles pour H2

Jobs av _i bv _i

J1 8 10

J2 6 20

J3 2 16

J4 9 13

J5 9 14

Maintenant on peut appliquer l'algorithme de Johnson en considérant le problème F2 || Cmax, on obtient l'ordonnancement suivant :

SH2 =? J3J2J1J4J5 ?

Le makespan de cette solution est Cmax(SH2) = 37.

2.2.3 Heuristique H3

Cette Heuristique fait appel au principe de l'heuristique de Palmer, mais avec l'intégration des dates de disponibilitéri et les délais de livraisons qi en combinant ces deux paramètres respectivement avec les durées opératoires de la machine commune et celles des machines du second étage.

L'indice de Palmer se calcul comme suit :

Palmeri = (ri + ai) - (bi + qi) ? 1 = j = n

Finalement, on ordonnance les indices de Palmer selon l'ordre croissant.

Exemple Reprenant l'exemple donnédans le Tableau 2.1, les indices de Palmer sont donnés dans le Tableau 2.4 :

Tableau 2.4 - Indice de Palmer Heuristique H3

Jobs Palmeri

J1 6

J2 -2

J3 -4

J4 8

J5 -1

En triant les indices selon l'ordre croissant on obtient :

SH3 =? J3J2J5J1J4 ?

Le makespan de cette solution est Cmax(SH3) = 32.

2.2.4 Heuristique H4

L'heuristique H4 reprend le même principe que l'heuristique précédente, sauf que l'on ignore le paramètre qi. L'indice de Palmer se calcul donc comme suit :

Palmeri = (ri + ai) - bi ? 1 = j = n

Finalement, on ordonnance les indices de Palmer selon l'ordre croissant.

Présentation des méthodes de résolution 32

Exemple Reprenant l'exemple donnépar le Tableau 2.1, les indices de Palmer sont :

Tableau 2.5 - Indice de Palmer pour H4

Jobi Palmeri

J1 10

J2 8

J3 -2

J4 12

J5 0

En triant les indices selon l'ordre croissant on obtient :

SH4 = < J3J5J2J1J4 >

Le makespan de cette solution est Cmax(SH4) = 34.

2.2.5 Heuristique H5

Cette heuristique s'inspire de celle proposée par Potts [60] pour le F2 | ri | Cmax. L'idée consiste à ordonnancer les jobs disponibles selon l'ordre de Johnson. La création des deux machines virtuelles s'impose afin d'appliquer l'algorithme de Johnson, leur configuration est la suivante :

av i = ai + ri V 1 < i < n

bv i = bi V 1 < i < n

Pour chaque itération, on prend les jobs disponibles et on applique l'ordre de Johnson, ce qui nous nous fournit une exploitation optimale de la date de disponibilité.

Exemple Soit l'exemple décrit dans le tableau 2.1 :

Jobs	ri	ai	bi	qi
J1	8	4	2	4
J2	6	6	4	10
J3	2	5	9	2
J4	9	6	3	4
J5	9	2	11	1

Présentation des méthodes de résolution 33

les durées opératoires sur les machines virtuelles sont données dans le Tableau 2.6

Tableau 2.6 - Machines virtuelles pour l'instance 2.1, H5

Jobs av i 1 bv _i

J1 12 2

J2 12 4

J3 7 9

J4 15 3

J5 11 11

Pour la première itération, on sélectionne le job J3 étant donnéqu'il est le 1^er à être disponible, à la date 7, la machine M_c termine l'exécution de J3 et devient de nouveau disponible pour exécuter. L'inspection des dates de disponibilitérévèle que J2 est le seul job disponible dans l'atelier, on l'ordonnance directement après J3 ce qui nous donne la séquence partielle -< _J3J2 >-, à la date 13 la machine M_c termine l'exécution de J2 et devient de nouveau disponible. L'inspection des dates de disponibilitérévèle que tous les jobs sont prêt à être exécuter. On applique alors l'ordre de Johnson en considérant les machines virtuelles ce qui donne :

SH5 =-< _J3J2J5J4J1 >-

Le makespan de cette solution est Cmax(SH5) = 31.

2.2.6 Heuristique H6

Cette heuristique suit presque le même principe de l'heuristique H1, sauf qu'un contrôle sur la date de disponibilitéet la durée opératoire sur la machine commune s'effectue pour la construction de la première machine virtuelle qu'on utilisera pour l'ordre de Johnson, ce contrôle s'effectue de la manière suivante :

_j

ai + r si ri ~ a

av i = V 1 = i = n

a sinon

La deuxième machine virtuelle est définie par :

bv i = bi + q V 1 = i = n

Présentation des méthodes de résolution 34

les durées opératoires sur les machines virtuelles sont données dans le Tableau 2.8.

Exemple Soit l'exemple décrit dans le Tableau 2.1, les durées opératoires sur les machines virtuelles sont données dans le Tableau 2.7

Tableau 2.7 - Machines virtuelles pour l'instance 2.1, H6

Jobs	Mv1	Mv2
J1	12	6
J2	12	14
J3	8	11
J4	15	7
J5	11	12

Maintenant on peut appliquer l'algorithme de Johson en considérant le problème F2 || Cmax, on obtient l'ordonnancement suivant :

SH6 = < J3J5J2J4J1 -

Le makespan de cette solution est Cmax(SH6) = 33.

2.2.7 Heuristique H7

Cette heuristique est une variante de l'heuristique H5, elle suit le même principe: ordonnancer à chaque itération les jobs disponibles selon l'ordre de Johnson, mais en prenant seulement compte des durées opératoires sur la machine commune en ignorant les dates de disponibilité, les durées opératoires sur la deuxième machine virtuelle est la somme des bi et qi.

La configuration des deux machines est donc la suivante :

av i = ai V 1 < i < n

bv i = bi + qi V 1 < i < n

Exemple Soit l'exemple décrit dans le tableau 2.1 :

Jobs	ri	ai	bi	qi
J1	8	4	2	4
J2	6	6	4	10
J3	2	5	9	2
J4	9	6	3	4
J5	9	2	11	1

Présentation des méthodes de résolution 35

Tableau 2.8 - Machines virtuelles pour l'instance 2.1, H7

Jobs a^v_i b^v_i

J1 4 6

J2 6 14

J3 5 11

J4 6 7

J5 2 12

L'application de l'heuristique H7 donne :

SH7 =< J3J2J5J1J4 >

Le makespan de cette solution est Cmax(SH7) = 32.

Le Tableau 2.9 résume les sept heuristiques proposées. Tableau 2.9 - Résumédes heuristiques proposées

Heuristique	Principe	Paramètres
H1	Johnson	a^vi = ri + ai b^vi = bi + qi
H2	Johnson	a^vi = ri b^vi = ai + bi + qi
H3	Palmer	Palmeri = (ri + ai) - (bi + qi)
H4	Palmer	Palmeri = (ri + ai) - bi
H5	Potts	a^vi = ri + ai b^vi = bi
H6	Johnson	az = r ai + ri si ri > ai l ai sinon b^vi = bi + qi
H7	Potts	a^vi = ai b^vi = bi + qi
Johnson	-	a^vi = ai b^vi = bi
Palmer	-	Palmeri = ai - bi
NEH	-	a^vi = ai b^vi = bi

Présentation des méthodes de résolution 36

2.3 Méta-Heuristiques

Les méta-heuristiques sont des approches de résolution globale que l'on peut adapter à différents problèmes. Elles sont souvent le seul moyen disponible pour chercher des solutions satisfaisantes au problèmes NP-difficile. Cependant, elle prennent nettement plus de temps de calcul que les heuristiques spécifiques.

Les méta-heuristiques qu'on a implémentées se basent sur la notion de voisinage et les opérateurs de changements.

2.3.1 Notions de base

Étant donnéune solution S0 ; on définit l'opérateur de changement comme étant toute transformation qui génère une autre solution réalisable S'. L'en-semble des solutions obtenues par cet opérateur est appeléVoisinage de S0 (notéVS₀). On peut établir plusieurs opérateurs de changement et ainsi construire pour chaque solution de départ son voisinage spécifique.

Nous avons utilisétrois opérateurs de changement² : 2.3.1.1 Opérateur de changement (a - opt)

Le principe de cet opérateur consiste à permuter deux jobs voisins, l'en-semble des solutions voisines qui constituent le voisinage de la solution de départ S0 est égale à (n - 1) voisins (avec n est le nombre des jobs de la solution S0 )

Exemple : Pour n = 4 et S0 =-< _J2J3J1J4 >- on a : :

VS0 =

? ?? ??

S' 1 =-< J3J2J1J4 >- S' 2 =-< J2J1J3J4 >-S^'3 =-< J2J3J4J1 >-

Selon Houari et Mhallah [36], le but de l'utilisation de cette opérateur est d'éviter de détruire la structure de la solution de départ en la modifiant légèrement à chaque étape.

2. Ces opérateurs ont étéutilisés dans [36, 16, 2].

Présentation des méthodes de résolution 37

2.3.1.2 Opérateur de changement (na - opt)

Le principe de cet opérateur consiste à permuter deux Jobs non nécessairement

voisins. Cet opérateur donne un voisinage de n(n-1)

₂ solutions réalisables.

Exemple : Pour n = 4 et S0 =-< _J2J3J1J4 >- on a :

VS0 =

{ Si =-< J3J2J1J4 >- S2 =-< J1J3J2J4 >- S3 =-< J4J3J1J2 >- S4 =-< J2J1J3J4 >- S5 =-< J2J4J1J3 >- S^'6 =-< J2J3J4J1 >-

Notons que le voisinage générépar l'opérateur a - opt est entièrement contenu dans le voisinage générépar l'opérateur na - opt.

2.3.1.3 Opérateur de changement (opt3)

Le principe de cet opérateur consiste à insérer un job en une position donnée et à décaler les autres jobs en gardant leur ordre de départ. Cet opérateur donne un voisinage de n(n - 2) + 1 solutions réalisables.

Exemple : pour n = 3 et S0 =-< _J1J2J3 >-, le voisinage de S0 est :

VS0 =

{ S1. =-< J2J1J3 >- S2 =-< J3J1J2 >- S3 =-< J1J3J2 >- S4 =-< J2J3J1 >-

2.3.1.4 Algorithme de Descente

En se basant sur les opérateurs de changement, les algorithmes de descente permettent d'intensifier la recherche de meilleurs voisins en partant de S0. Ils permettent ainsi l'obtention des minimums locaux.

L'Algorithme 2.1 décrit une descente (en considérant un problème de minimisation) :

Présentation des méthodes de résolution 38

Algorithme 2.1: Algorithme de descente

Soit F : La fonction objectif

Fixer S_o;

Scourante <-- S_o ;

répéter

Chercher _Ssuivante Tel que F(Ssuivante) < F(Svoisine)

V _Svoisine E VScourante

si F(Ssuivante) < F(Scourante) alors

Scourante <--- Ssuivante

jusqu'à(F(Scourante) < F(Ssuivante); SFinale <-- Scourante

2.3.1.5 Critères d'arrêt

Il évident que la méta-heuristique nécessite un critère prédéfini pour arrêter la recherche. Ce critère peut être :

- Un nombre maximal d'itérations.

- Un taux d'amélioration donné.

- Un nombre donnéd'itérations sans amélioration.

Les critères qu'on a adoptéseront décrits dans les sections 3.2.1.3 et 3.2.2.3.

2.3.2 Recherche Taboue

Cette méta-heuristique a étéproposée parmi les premières et «elle se montre très performante sur un nombre considérable de problèmes d'optimi-sation combinatoire, en particulier les problèmes d'ordonnancement» [51]. Le principe consiste à générer le voisinage à partir d'une solution de départ et à enregistrer momentanément ses traces ( ou encore l'historique des derniers mouvements) afin de ne pas y revenir, à chaque itération elle retient le meilleur voisin (non nécessairement meilleur que la solution de départ) et elle examine le nouveau voisinage pour en retenir un autre meilleur voisin.

La recherche taboue, et comme indique son nom, est basée sur la gestion des listes taboue. Plusieurs méthodes et approches on étéabordées pour gérer ces listes que se soit en ce qui concerne leurs modes d'actualisation ou encore leurs longueurs. On a adoptédeux méthodes de gestion de la liste taboue qu'on illustrera dans le paragraphe suivant.

Présentation des méthodes de résolution 39

2.3.2.1 Gestion de la liste taboue

Une bonne gestion de la liste taboue est primordiale pour qu'elle puisse bien remplir son rôle. On a fait le choix d'adopter deux méthodes de gestion de la liste taboue à savoir l'enregistrement des traces des derniers mouvements et l'enregistrement de la valeur de la fonction objectif.

Méthode d'interdiction des mouvements : On enregistre à chaque itération les jobs dont la permutation a menéà la solution voisine, on illustre la démarche par l'exemple suivant :

Soit une solution initiale S0 =? J3J2J1J4 ?

Si on travail avec l'opérateur de changement a-opt (permuter deux jobs voisins) et qu'on retienne la solution voisine S' 1 =? J2J3J1J4 ?, la liste Taboue de longueur Lliste = 3 étant initialement vide sera remplie comme suit :

( )

3 . .

Taboue 2 . .

Pour la génération des prochain voisins, si les deux jobs à permuter sont présents dans la liste sur la même colonne, on interdit le changement.

Une fois que toutes les cases de la liste ne sont plus vides, on écrasera le plus ancien élément suivant la règle FIFO.

Méthode d'interdiction par la fonction objectif: On utilise la valeur du makespan comme paramètre pour la liste taboue, de façon d'interdire l'adoption d'un voisin si son makespan se trouve dans la liste taboue. Exemple :

Soit S' 1 un voisin retenu avec un makespan = 560. La liste taboue est donc:

Tabouemakespan = (560 . . . .)

Désormais, aucun voisin avec un makespan égale à 560 ne sera retenu tant que cette valeur est enregistrédans la liste. Le mode d'actualisation de cette liste est le même que la liste précédente (règle FIFO).

Après avoir présentéles différentes propriétés de cette méta-heuristique, l'Algorithme 2.2 donne l'adaptation retenue.

2.3.2.2 Variantes de recherche taboue

Présentation des méthodes de résolution 40

Algorithme 2.2: Recherche Taboue

Soit _Scourante une solution de départ.

Fixer Nbriteration ;

Initialiser MeilleurC_max, MeilleurSolution, ListeTaboue;

i ? 1;

tant que (i = Nbriteration) faire

- Chercher _Ssuivante Tel que

( F(Ssuivante) = F(Svoisine) ) Et ( Svoisine ?? ListeTaboue ) ? Svoisine ? VScourante

- Mettre à jour ListeTaboue

- Scourante ?- Ssuivante

- si F(Ssuivante) = F(Scourante) alors MeilleurC_max ?- F(Ssuivante) MeilleurSolution ?- Ssuivante)

i ? i + 1;

retourner MeilleurSolution

On a implémentécinq variantes de recherche taboue dont chacune opère avec une combinaison spécifique des opérateurs de changement et des méthodes de gestion les listes taboue. Le Tableau 2.10 résume ces variantes.

Tableau 2.10 - Procédures de recherche taboue

Opérateurs de changement ??????????????????????? Liste taboue	a - opt	na - opt	opta
Gestion par mouvement	RT1	RT2	RT4
Gestion par makespan	.	RT3	RT5

Ainsi par exemple, la première procédure RT1 consiste à générer le voisinage à l'aide de l'opérateur de changement a - opt et à gérer la liste taboue en utilisant la méthode d'interdiction des mouvements déjàeffectués.

2.3.2.3 Procédure RTG

Après avoir testéles cinq procédures précédentes et étudiéleurs comportement pour faire le bon choix notamment en ce qui concerne la gestion taboue et les opérateurs de changement, on les a réunie dans une même procédure afin de pouvoir exploiter tous leurs avantages, cette procédure s'appelle RTG. L'idée consiste en premier lieu à exécuter les cinq procédures RT1, RT2, RT3,

Présentation des méthodes de résolution 41

RT4 et RT5 avec la même solution de départ, puis évaluer les cinq résultats obtenus, ensuite la meilleur séquence sera introduite dans les cinq procédures de manière à maximiser la probabilitéde trouver une solution meilleure (un résultat provenant de la RT1 a plusieurs chances d'être améliorési on l'in-troduit dans RT2, RT3, RT4 ou encore RT5).

Une approche semblable a étéutilisédans [36] qui consiste à générer en premier lieu un voisinage à l'aide de l'opérateur de changement a - opt pour en retenir la meilleur solution, puis un deuxième voisinage sera généréà partir de cette meilleur solution à l'aide de l'opérateur de changement ma - opt, cette approche a pour but d'augmenter la probabilitéd'améliorer le résultat. la RTG s'arrête si on a atteint un nombre d'itération sans amélioration. Le résultat est évaluéen calculant l'écart par rapport la borne inférieure, si cet écart est inférieur à 1% ou si le nombre d'itération fixéa étéatteint alors on arrête la recherche.

L'Algorithme 2.3 décrit la procédure RTG.

Algorithme 2.3: Algorithme RTG

Soient F : La fonction objectif, _Scourante une solution de départ.

Fixer Nbriteration

Fixer T = 1% (Taux d'amélioration)

Calculer BI (Borne inférieure)

i --- 1;

tant que (i _Nbriteration ) Et (Taux ~ T) faire

- Lancer RT1, RT2, RT3, RT4 et RT5 avec Scourante

- Déterminer la Meilleure solution SMeilleure

- Scourante --- SMeilleure

- Calculer Taux = F(SMeilleure)-BI x 100

BI

i -- i + 1

retourner SMeilleure

Présentation des méthodes de résolution 42

2.3.3 Recuit simulé

On a fait le choix de développer une procédure de recuit simulédont l'al-gorithme est synthétisédans l'Algorithme 2.4.

Algorithme 2.4: Pseudo code Recuit Simulé

F : Fonction objectif;

Fixer Scourante, Kmax, T, À;

Initialiser SMeilleure ;

k ? 0;

tant que (k = Kmax) faire

Générer aléatoirement un voisin S^' ;

si F(S^') = F(Scourante) alors

Scourante ? S^' ;

sinon

Calculer ?f = (F(S^') - F(Scourante)); Générer un nombre aléatoire Z ? [0, 1];

si Z = e

-?f T alors

Scourante ? S^' ;

si F(S^') = F(SMeilleure) alors SMeilleure ? S^' ;

T ? À.T ; k ? k+1;

retourner SMeilleure

La génération de voisinage se fait aléatoirement à l'aide du troisième opérateur de changement (opt3). 'Etant donnéle nombre très limitédes so-

lutions générées (une seule par itération) on a élevéle nombre d'itérations ^àdeux milles.

Conclusion

Ce chapitre a portésur les méthodes de résolution retenues pour notre problème. En effet, nous avons adoptécinq bornes inférieurs qui serviront de repère pour l'évaluation des résultats des différentes procédures qu'on a implémenté. Nous avons aussi adaptédes heuristiques spécifiques inspirées de la littérature, ensuite nous avons présentéles notions de bases des méta-heuristiques ainsi que les procédures qu'on a retenues à savoir la recherche taboue et le Recuit Simulé.

Chapitre 3

Résultats expérimentaux

Résultats expérimentaux 44

Introduction

Après avoir présentéles différentes méthodes de résolution qu'on a adoptées pour le problème considéré, ce chapitre se focalise sur le paramétrage des ces méthodes et l'analyse des résultats expérimentaux. Nous décrivons d'abord les familles d'instances pour les tests qu'on a effectués, ensuite nous présentons les choix des paramètres pour les méta-heuristiques, enfin nous exposons et interprétons les résultats expérimentaux.

3.1 Génération des instances tests

Afin de tester les différentes heuristiques ainsi que les méta-heuristiques qu'on a implémentées, nous avons générédes instances aléatoires appartenant à des classes différentes, oùchaque classe contient quatre tailles (n = 20, 50, 100 et 150). pour chaque taille, 20 instances ont étégénérées et les jobs sont, tant que possible, équitablement divisées entre les différents types de jobs. Le nombre des machines au deuxième étage in E {5, 10} .

Les temps opératoires des différents jobs suivent une distribution uniforme. Dans la famille F1 et la famille F2, les temps opératoires a et b , les dates disponibilitér et les délais de livraison q sont générés dans les mêmes intervalles : [1, 20] pour F1 et [1, 100] pour F2.

Pour la famille F3, les temps opératoires sur la machine M_c, les dates r et les délais q sont générés dans [1, 100], et les durées opératoires sur les machines dédiées dans [1, in x 100].

Dans les familles F4 et F5, les temps opératoires sur la machine M_c, les dates r et les délais q sont générés dans [1, 20], mais les temps opératoires sur les machines du deuxième étage sont générés dans [20, 40] pour la famille F4, et pour la famille F5 elle prennent toujours les valeurs des temps opératoires a sur la machine commune M plus un temps supplémentaire 'y = 10 (a + 'y). Ainsi, pour les deux premières familles, les temps opératoires ont les mêmes ordres de grandeur, quant à F3, F4 et F5, les temps opératoires sur les machines dédiées sont plus importants que ceux sur M_c, ce qui tend à équilibrer la charge globale sur les différentes machines.

L'ensemble des familles générées, est résumédans le tableau 3.1.

Résultats expérimentaux 45

Tableau 3.1 - Familles des instances tests

Famille	r	a	b	q
F1	[1,20]	[1,20]	[1,20]	[1,20]
F2	[1,100]	[1,100]	[1,100]	[1,100]
F3	[1,100]	[1,100]	[1,m × 100]	[1,100]
F4	[1,20]	[1,20]	[20,40]	[1,20]
F5	[1,20]	[1,20]	a + 10	[1,20]

Tous les tests qu'on a effectués ont étéfait sur ces cinq familles d'ins-tances avec 20 instances pour chaque famille, quatre tailles différentes des problèmes : n E {20, 50, 100, 150} et deux valeurs pour les machines dédiées m E {5,10}.

Résultats expérimentaux 46

3.2 Paramétrage des méta-heuristiques

Le paramétrage des méta-heuristiques est une tâche critique car elle influence le comportement des procédures et par conséquence les résultats. Une méta-heuristique se base sur plusieurs paramètres parmi les suivants :

- Critère d'arrêt

- Longueur des listes taboue et leurs modes de gestion

- Application de l'aspiration

- Application de la descente

- Schéma de refroidissement

Les décisions concernant ces paramètres doivent ainsi être justifiées et prises avec soin. On a effectuéplusieurs tests sur les procédures de la recherche taboue ainsi que le recuit simulépour justifier les choix qu'on a fait.

3.2.1 Recherche Taboue

3.2.1.1 Longueur des listes taboue

Comme dans [36], une liste Taboue de longueur fixe L = 10 a étémainte-nue. Cette longueur semblait offrir le meilleur compromis entre la nécessit^éd'éviter le phénomène de l'allure cyclique et le temps de calcul qui augmente avec la longueur de L.

3.2.1.2 Application de l'aspiration

Après l'implémentation des différents procédures de la recherche taboue, on a testéleurs comportements en essayant de détecter les traces d'un cyclage possible. Pour le faire on a associéà chaque solution ir une emprunte W_ð calculée comme suit :

Wð =

?n i=1

(iri) × j

Bien que cette emprunte peut ne pas être unique pour une solution donnée, elle a étéretenue pour sa facilitéd'utilisation.

RT1

La Figure 3.1 présente les empruntes des solutions examinées par cette procédure pour une seule instance avec 200 itérations :

Résultats expérimentaux 47

FIGURE 3.1 - Empruntes des solutions de la RT1

On constate que les solutions suivent un cycle de 66 itérations, ce qui veut dire que chaque 66 itérations, la procédure revient au même point puis elle passe par les même solutions donnant ainsi une allure cyclique.

D'autre part, on a établie dans la Figure 3.2 la courbe de l'évolution du makespan pendant 200 itérations.

FIGURE 3.2 - Évolution du makespan de la RT1 pour 200 itérations

On constate que le makespan reste figédès les toutes premières itérations, d'oùla stagnation de la courbe. En d'autre terme, après les premières itérations, la procédure n'a pas pu améliorer ses résultats et par conséquence, la majo-ritédominante des itérations n'étaient qu'une perte de temps de calcul.

Ces constations ont mis l'accent sur le phénomène de l'allure cyclique que l'on peut justifier par le comportement des opérateurs de changement notamment le a - opt qui n'offre pas une exploration importante de l'espace de recherche (ce qui justifie d'ailleurs la stagnation de la courbe du makespan) et par l'absence d'un caractère de diversification dans notre procédure.

La solution était d'appliquer une aspiration pour éviter ce phénomène d'al-lure cyclique et pour donner plus de chance à la procédure afin qu'elle puisse

Résultats expérimentaux 48

RT3

Vu que cette procédure utilise le même opérateur de changement que la RT2

explorer de nouvelles zones de l'espace de recherche.

Le problème alors devient la détermination du nombre d'itérations au bout duquel on peut appliquer l'aspiration.

Pour avoir la réponse nous avons cherchéà savoir au bout de quelle itération la valeur de makespan reste figée, et cela en testant la RT1 sur les cinq familles d'instances pour n = 50 et n = 100 jobs avec in = 5. Le Tableau 3.2 résume ces résultats.

Tableau 3.2 - Nombres moyens d'itérations pour avoir la stagnation pour

RT1, 20 instances

	RT1
	n= 50		n= 100
	Moyenne	Ecart Type	Moyenne	Ecart Type
Famille 1	12.2	14.2	10.8	12.3
Famille 2	9.6	8.9	12.8	9.7
Famille 3	13.2	12.7	24.2	20
Famille 4	10.4	8.1	11.8	7.8
Famille 5	11.5	11.7	10.6	8.3

RT2

Bien que la RT2 ne présente pas vraiment un phénomène d'allure cyclique, on a bien remarquéune stagnation des valeurs des makespans.

Comme pour la RT1, le Tableau 3.3 illustre le nombre moyen d'itération au bout duquel on obtient une stagnation du makespan (on obtient le meilleur makespan pour la première fois).

Tableau 3.3 - Nombres moyens d'itérations pour avoir la stagnation pour

RT2, 20 instances

	RT2
	n= 50		n= 100
	Moyenne	Ecart Type	Moyenne	Ecart Type
Famille 1	3.5	1.6	3.9	3.3
Famille 2	9.6	8.9	4.6	2
Famille 3	16.5	29.6	19.1	31.2
Famille 4	6.5	9.1	3.6	1.6
Famille 5	3.7	2.1	4.1	3.5

Résultats expérimentaux 49

(ma - opt), elle aura le même paramétrage que cette dernière.

RT4

Comme pour la procédure RT2, la RT4 ne présente pas un phénomène d'al-lure cyclique.

De même, on a testéles numéros d'itérations au bout des quelles la procédure obtient sa meilleure solution ( voir Tableau 3.4 ).

Tableau 3.4 - Nombres moyens d'itérations pour avoir la stagnation pour RT4, 20 instances

	RT4
	n= 50		n= 100
	Moyenne	Ecart Type	Moyenne	Ecart Type
Famille 1	4.1	2	3.9	2.6
Famille 2	4.5	3.7	5.4	4
Famille 3	6.8	4.2	7.6	5.9
Famille 4	5.7	4.4	3.9	1.9
Famille 5	5.8	2.6	5.5	2.5

RT5

Vu que cette procédure utilise le même opérateur de changement que la RT4 (opt3), elle aura le même paramétrage que cette dernière.

En se basant sur les Tableaux 3.2, 3.3 et 3.4 on a fait le choix d'appliquer une aspiration dans chacune des procédures de recherche taboue et cela après un nombre d'itérations comme décrit dans le Tableau 3.5.

Tableau 3.5 - Nombre d'itération pour appliquer l'aspiration

	RT1	RT2 & RT3	RT4 & RT5
F1	28	8	6
F2	24	19	10
F3	45	50	14
F4	20	15	10
F5	24	8	9

L'Algorithme 3.1 décrit la démarche adoptée pour les procédures de recherche taboue.

Résultats expérimentaux 50

Algorithme 3.1: Recherche Taboue avec aspiration

Fixer _Nbriteration pour aspiration;

Initialiser MeilleurC_max, MeilleurSolution ; Asp - 0;

tant que (Critère d'arrêt non atteint) faire - Chercher Meilleur voisin Meilleurvoisin - Mettre à jour la liste taboue

- si F(Meivoisin) < MeilleurC_max alors

MeilleurC_max +- F(Meilleurvoisin)

MeilleurSolution ?- Meilleurvoisin - si Asp = Nbriteration alors

- Appliquer Aspiration - Asp - 0

Asp - Asp + 1;

retourner MeilleurSolution

À titre de confirmation, on a essayéde voir l'apport d'une telle approche. On a comparéla RT1 avant et après l'application d'une aspiration sur une seule instance appartenant à la famille F3 avec n = 100 jobs et in = 5 machines. Les Figures 3.3 et 3.4 comparent son comportement avec et sans aspiration.

FIGURE 3.3 - Évolution du makespan de la RT1 sans aspiration

Résultats expérimentaux 51

FIGURE 3.4 - Évolution du makespan de la RT1 avec aspiration

Sachant que la borne inférieure BI = 6007 on peut constater que l'aspi-ration a ététrès bénéfique et a améliorél'écart entre la solution de la RT1 et la valeur de BI de 3.44 % (sans aspiration) à 1.16 % (avec aspiration).

3.2.1.3 Critères d'arrêt

Pour les procédure unitaires de la recherche taboue on a fait le choix d'arrêter le processus après un nombre d'itération choisit de manière à permettre à la procédure de faire au moins cinq aspiration ou d'avoir une bonne solution.

Pour la procédure RTG on a établie un double critère d'arrêt expliquépar l'Algorithme 3.2.

Algorithme 3.2: Critères d'arrêt pour RTG

Initialiser Taux;

i ? 0;

tant que (i = 5) Et (Taux = 1%) faire

Exécuter RTG

Calculer Taux d'amélioration

i ? i + 1;

Toutes les méta-heuristiques s'arrêtent automatiquement si elles tiennent un makespan égale à la borne inférieur.

Résultats expérimentaux 52

3.2.2 Recuit Simulé

«La performance du Recuit Simuléest étroitement liée au schéma de refroidissement considéré» [51].

3.2.2.1 Variance de ?f

Une solution qui ne minimise pas le makespan doit valider le critère de Metropolis pour qu'elle puisse être acceptée, ce critère se base sur l'inverse de l'exponentielle du rapport entre ?f et T, s'il est proche de zéro alors cette solution a une grande probabilitéd'être acceptée, c'est d'ailleurs une des propriétés de cette méta-heuristique oùles premières itérations semblent être une diversification et les dernières itérations semblent être une intensification. La dégradation de la température s'avère donc une tâche très critique dont le choix doit être pris avec soin.

On doit fixer la valeur initiale de la température de façon de garantir que le rapport ?! T soit très proche de zéro au début de la recherche, T doit donc être très importante par rapport à ?f, pour cela on a effectuédes test pour estimer les valeurs moyennes du gain ?f sur les cinq familles d'instance avec quatre tailles de problème (20, 50, 100 et 150 jobs), le Tableau 3.6 synthétise la moyennes des résultats sur 20 instances et 2000 itérations pour chaque instance. Les résultats sont simplifiés dans le Tableau 3.7.

Tableau 3.6 - Valeurs moyennes de ?f pour cinq familles d'instance

	n = 20		n = 50		n = 100		n = 150
	moyenne	u	moyenne	u	moyenne	u	moyenne	u
F1	6.7	0.2	6.5	0.2	6.5	0.2	6.2	0.1
F2	30.3	1.1	30.6	1.1	31.5	1.1	29.8	1
F3	63.7	9.4	80.5	3.5	73.2	11.4	76.4	5.7
F4	9.1	27.2	9.9	0.7	10.3	15.7	9.9	14
F5	6.6	0.2	6.7	0.2	6.6	0.2	6.8	0.5

Tableau 3.7 - Résumédu tableau 3.6

n	20	50	100	150
F1	8	7	7	7
F2	32	32	32	30
F3	73	84	84	84
F4	40	10	26	25
F5	7	7	7	7

Résultats expérimentaux 53

Maintenant qu'on a une idée sur les valeurs de ?f on peut fixer les valeurs initiales de la température T de manière a ce que pour les premières itérations on ait une probabilitéimportante d'accepter les mouvements (0.99).

Si on prend l'exemple de la famille F2, et pour une probabilitéde 0.99 on a,

Tinitiale =

-?f Ln(0.99)

-32 Ln(0.99) ? 3184

Le Tableau 3.8 synthétise les différents valeurs de la température pour toutes le familles d'instance.

Tableau 3.8 - Valeurs initiales de T pour les cinq familles d'instances

Familles d'instance	Température initiale
F1	796
F2	3184
F3	8356
F4	3980
F5	696

3.2.2.2 Dégradation de la température

La construction d'un schéma de refroidissement qui garantisse une dégradation équilibrée et adéquate du paramètre de contrôle T sur les 2000 itérations prévues repose essentiellement sur le coefficient de dégradation (coefficient À de Boltzmann), mais avant de fixer ce coefficient on doit choisir le mode de dégradation qu'on adoptera.

En effet, le mode de dégradation de la température est en relation directe avec le nombre de fois qu'on doit vérifier le critère de Metropolis, on va donc estimer la probabilitépour que la différence ?f soit positive, les calculs ont étéfait sur 20 instances avec 2000 itérations pour chaque instance (voir Tableaux 3.9 et 3.10).

Résultats expérimentaux 54

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

	n = 20		n = 50		n = 100		n = 150
	moyenne	u	moyenne	u	moyenne	u	moyenne	u
F1	87.45	21.39	94.2	40.14	97.1	63.23	97.90	67.69
F2	86.80	11.59	93.8	33.89	96.85	44.98	97.9	66.62
F3	74.5	11.88	78.1	3.53	80.7	9.6	80.45	6.24
F4	81.10	18.46	88.05	4.11	92.6	17.17	94.45	12.81
F5	85.05	17.15	92.7	25.61	96.2	33.88	97.3	62.63

Tableau 3.10 - Résume du tableau 3.9

n	20	50	100	150
F1	90 %	95 %	97%	97%
F2	90%	95%	97%	97%
F3	80%	80 %	80%	80%
F4	90%	90 %	97%	95%
F5	90%	93 %	93%	97%

Le tableau 3.10 nous renseigne sur le pourcentage pour lequel ?f soit supérieur à zéro, autrement dit, au bout de 2000 itérations, combien de fois peut-on calculer le rapport ?! T ? Le Tableau 3.11 illustre la réponse.

Tableau 3.11 - Nombre de vérifications du critère de Metropolis sur 2000 itérations

n	20	50	100	150
F1	1800	120	1940	1940
F2	1800	160	1940	1940
F3	1600	1600	1600	1600
F4	1800	1800	1940	1900
F5	1800	1860	1860	1940

On remarque que la probabilitépour que ?f soit positive est très importante, dans ce cas, on doit imposer un mode de dégradation par palier, c'est à dire qu'on va «refroidir le système» toutes les 20 itérations et cela au cours des 200 premières itérations de façon de garantir que le début de recherche assure une importante exploration de l'espace de recherche, ensuite on va dégrader la température au cours des 1800 dernières itérations de façon

Résultats expérimentaux 55

À2 = ( Tfinal)

Tinitial

1

89

de diminuer la probabilitéd'acceptation afin d'assurer l'intensification de la recherche. Pour cela, la probabilitéd'acceptation x sera établie comme suit :

_f

[0.4, 0, 9] V 1 iteration 200

x E [0.1, 0.4] V 201 iteration 2000

La question qui se pose désormais, c'est comment va-t-on dégrader la température?

ou encore, quelle est la valeur de À à fixer? Pour répondre à cette question, on doit calculer les valeurs finales de la température qui assurent une proba-bilitéd'acceptation x appartenant à une plage donnée de valeur, reprenant l'équation suivante :

Tfinale =

-~f Ln(0.1)

Le Tableau 3.12 illustre les valeurs finales approchées de la températures pour les cinq familles d'instance :

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

	Températures finales
Familles	x E [0.4,0,9]	x E [0.1,0,4]
F1	8.73	3.47
F2	34.92	13.89
F3	91.67	36.48
F4	43.65	17.37
F5	7.63	3.04

Si pour les 200 premières itérations, on dégrade la température toutes les 20 itérations alors on va dégrader 9 fois, le coefficient de dégradation s'écrit donc comme suit :

À1 = ( Tfinal) Tinitial

1 9

Pour les 1800 dernières itérations, on va appliquer 89 dégradations d'oùÀ s'écrit comme suit :

Résultats expérimentaux 56

FIGURE 3.6 - Dégradation de T pour la famille F3, 1800 dernières itérations

A` titre d'exemple, calculons les deux valeurs de A pour la famille F3 :

?

?

?

A =

1

(91.67 8356 )9 ? 0.60 V 1 < iteration < 200
1

(36.48 91.67) 89 ? 0.989 V 201 < iteration < 2000

Finalement, et en faisant les mêmes calculs pour toutes les familles d'ins-tance, on a choisit les valeurs A1 = 0.60 pour i E [1, 200] et A2 = 0.989 pour i E [201, 2000].

A ` titre de confirmation, les figures 3.5 et 3.6 illustrent cette dégradation pour

la famille F3, et la figure 3.7 page suivante décrit l'évolution de la probabilitéd'acceptation d'une solution voisine toujours pour la famille F3.

FIGURE 3.5 - Dégradation de T pour la famille F3, 2000 itérations

Résultats expérimentaux 57

FIGURE 3.7 - Probabilitéd'acceptation pour la famille F3 3.2.2.3 Critère d'arrêt

Le Recuit Simulés'arrête après un nombre d'itération de 2000 ou si la procédure tient une solution dont le makespan est égale à la borne inférieure.

Résultats expérimentaux 58

3.3 Résultats des expérimentations

Dans cette section, nous entreprenons d'analyser les performances des différentes approches de résolution présentées précédemment. Notons que les simulations numérique ont étéfaites sur un micro-processeur de 1.46 GHz. Les heuristiques et les méta-heuristiques ont étéprogrammées en langage C++.

3.3.1 Heuristiques

Afin d'identifier les meilleurs heuristiques, on a effectuédes tests sur les cinq familles de problèmes avec 20 instances pour chaque taille. L'évaluation était basée sur la moyenne des écarts par rapport à la borne inférieur BI.

Cmax - BI

Ecart = BI × 100

Les Tableaux 3.13 et 3.14 illustrent les moyennes des écarts pour l'en-semble des heuristiques avec in = 5 et les Tableaux 3.15 et 3.16 avec in = 10.

Tableau 3.13 - Résultats des heuristiques, Familles F1, F2 et F3 (in = 5)

		F1				F2				F3
n	20	50	100	150	20	50	100	150	20	50	100	150
H1	1.08	0.23	0.09	0.04	1.76	0.47	0.11	0.08	17.21	5.96	2.06	2.00
H2	7.87	3.18	1.19	0.68	6.94	2.36	0.92	0.45	28	16	12	12
H3	3.67	1.53	0.80	0.47	5.43	1.90	0.63	0.39	8.78	5.09	2.52	3.16
H4	5.78	2.45	1.28	0.87	7.76	2.52	1.37	0.93	8.12	4.11	2.65	2.77
H5	3.00	1.13	0.65	0.58	3.03	1.21	0.90	0.62	11.00	5.48	1.98	1.85
H6	1.12	0.21	0.08	0.03	1.68	0.40	0.11	0.05	23	10	6.90	5.28
H7	0.99	0.13	0.05	0.01	1.72	0.13	0.01	0.00	18	5.55	1.97	1.45
Johnson	8.50	3.99	2.07	1.40	9.42	4.12	2.37	1.57	19	6.17	2.18	1.50
NEH	3.30	1.78	0.98	0.72	2.84	1.46	0.86	0.58	6.85	2.98	1.99	2.75
Palmer	8.64	4.26	2.38	1.58	10	4.47	2.20	1.50	12	6.01	3.00	2.91

Résultats expérimentaux 59

Tableau 3.14 - Résultats des heuristiques Familles F4 et F5 (in = 5)

		F4				F5
n	20	50	100	150	20	50	100	150
H1	6.72	1.18	0.24	0.21	7.44	2.85	1.21	0.91
H2	8.40	4.98	3.51	2.12	8.35	3.66	1.96	1.27
H3	3.73	1.98	0.70	0.47	4.98	3.01	1.11	0.86
H4	6.16	2.14	1.10	0.77	8.35	3.70	2.01	1.30
H5	4.82	1.76	0.88	0.58	6.48	3.90	2.14	1.66
H6	9.61	2.79	1.07	0.65	6.88	2.76	1.12	0.85
H7	7.07	3.46	1.75	1.27	10.04	4.63	2.57	1.65
Johnson	11.20	5.36	2.95	2.04	14.47	7.11	3.51	2.39
NEH	5.22	2.43	1.28	0.84	4.33	2.32	1.13	0.80
Palmer	8.83	3.34	1.54	1.13	11.13	4.94	2.58	1.78

Tableau 3.15 - Résultats des heuristiques, Familles F1, F2 et F3 (in = 10)

		F1				F2				F3
n	20	50	100	150	20	50	100	150	20	50	100	150
H1	1.03	0.21	0.09	0.04	1.76	0.47	0.11	0.08	20.76	10.80	3.87	2.95
H2	7.87	3.00	1.05	0.64	6.74	2.35	0.83	0.35	22.38	20.41	11.78	13.49
H3	3.67	1.53	0.80	0.47	5.43	1.90	0.63	0.39	6.41	6.44	2.48	2.56
H4	5.78	2.45	1.28	0.87	7.76	2.52	1.37	0.93	6.70	6.15	2.30	2.45
H5	3.00	1.13	0.65	0.58	3.03	1.21	0.90	0.62	18.28	9.79	3.30	2.76
H6	1.07	0.19	0.08	0.03	1.68	0.40	0.11	0.05	24.70	18.09	8.12	6.18
H7	0.99	0.13	0.05	0.01	1.72	0.13	0.01	0.00	20.26	12.54	3.50	2.18
Johnson	8.50	3.99	2.07	1.40	9.42	4.12	2.37	1.57	23.25	12.84	3.74	2.57
NEH	3.10	1.78	0.97	0.72	2.83	1.45	0.85	0.57	3.90	4.18	1.67	2.71
Palmer	8.64	4.26	2.38	1.58	10.65	4.47	2.20	1.50	8.00	7.20	2.80	2.88

Résultats expérimentaux 60

Tableau 3.16 - Résultats des heuristiques Familles F4 et F5 (m = 10)

		F4				F5
n	20	50	100	150	20	50	100	150
H1	5.20	0.66	0.17	0.12	6.69	2.07	0.63	0.42
H2	7.24	3.84	2.31	1.44	7.96	3.24	1.80	1.19
H3	3.58	1.41	0.59	0.39	4.84	2.15	1.01	0.69
H4	5.56	1.82	1.00	0.71	7.96	3.28	1.85	1.23
H5	3.89	1.44	0.83	0.48	5.07	2.21	1.43	0.96
H6	6.07	2.19	0.54	0.32	5.93	1.74	0.56	0.40
H7	6.75	2.85	1.60	1.17	10.04	4.49	2.49	1.59
Johnson	10.70	4.83	2.75	1.91	14.32	6.63	3.43	2.39
NEH	3.31	1.55	0.96	0.64	3.29	1.77	0.81	0.61
Palmer	8.39	3.04	1.53	1.12	11.13	4.94	2.58	1.78

En se basant sur les tableaux précédents, on peut évaluer les heuristiques qu'on a testépour en tirer les plus performantes.

Pour les familles d'instances F1 et F2, m E {5,10} et pour toutes les tailles des problèmes (20, 50,100 et 150 jobs) on remarque que les heuristiques H1, H6 et H7 on étéles meilleures parmi les dix heuristiques implémentées. Pour les familles F3 et F4 on remarque une diversification des heuristiques en passant de m = 5 à m = 10, en effet pour m = 5 les meilleures heuristiques étaient H1, H3, H4, H5 et NEH pour n E {20, 50}, pour n E {100,150} on constate l'apparition des heuristiques H7 et Johnson.

Pour la famille F5, les meilleurs heuristiques sont H1, H3, H5, H6, H7 et NEH.

Les Tableaux 3.17 et 3.18 illustrent les meilleurs heuristiques par famille d'instances pour m = 5 et m = 10.

Tableau 3.17 - Meilleurs heuristiques pour m = 5

	H1	H2	H3	H4	H5	H6	H7	Jonhson	NEH	Palmer
F1	X					X	X
F2	X					X	X
F3			X	X	X		X		X
F4	X		X		X				X
F5	X		X		X	X	X		X

Résultats expérimentaux 61

Tableau 3.18 - Meilleurs heuristiques pour m = 10

	H1	H2	H3	H4	H5	H6	H7	Jonhson	NEH	Palmer
F1	X					X	X
F2	X					X	X
F3			X	X			X	X	X
F4	X		X		X	X			X
F5	X		X		X	X			X

Les tableaux précédents indiquent les meilleures heuristiques (dont l'écart avec la borne inférieure BI est faible par rapport autres heuristiques). En effet, on constate que l'adaptation de la règle de Johnson à notre problème a ététrès efficace notamment pour les familles F1 et F2 oùles heuristiques H1 et H6 et H7 avaient les écarts les plus faibles.

En revanche, pour les familles F3, F4 et F5 on constate que l'heuristique NEH avait l'écart le plus faible et cela pour presque toutes les tailles des problèmes.

Par ailleurs, la différence entre les tests effectués avec un nombre de machine au second étage m = 5 et m = 10 n'était pas très considérable d'oùle choix qu'on fait était le même pour ces deux valeurs.

En se basant sur ces résultats on va sélectionner sept heuristiques afin de fournir les solutions de départ pour les méta-heuristiques. Notre choix s'est portésur les heuristiques H1, H3, H4, H5, H6, H7 et NEH.

Résultats expérimentaux 62

3.3.2 Méta-heuristiques

Après avoir sélectionnéles meilleures heuristiques qu'on a implémentées, nous avons effectués des tests sur les différentes méta-heuristiques.

Pour chaque familles d'instance, le test consiste en premier lieu à calculer les cinq bornes inférieures et en tirer la meilleure borne BI. Ensuite on exécute les sept meilleures heuristiques puis on retient la séquence ayant la meilleure valeur de makespan. Cette séquence sera injectée dans la procédure du Recuit Simulé(RS) ainsi que dans les cinq procédures de recherche taboue (RT1, RT2, RT3, RT4 et RT5),la meilleure séquence provenant de l'une des cinq dernières sera introduite dans la procédure RTG.

Notons que si une méta-heuristiques tient une séquence dont le makespan est égale à BI alors elle arrête la recherche, sinon on calcul l'écart entre la solution provenant des méta-heuristiques et la borne BI.

Les tests ont étéeffectués sur 20 instances avec quatre tailles des problèmes (n = 20, 50, 100 et 150) pour chaque famille.

Les Tableaux 3.19, 3.20, 3.21, 3.22 et 3.23 synthétisent les résultats des différentes méta-heuristiques pour chaque famille, les moyennes des écarts

ainsi que le nombre de fois oùles procédures avaient des solutions égales ^àla borne BI sur les 20 instances.

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

	Famille F1
	n = 20		n=50		n = 100		n = 150
	Ecart	BI	Ecart	BI	Ecart	BI	Ecart	BI
RT1	0.05	18	0.02	18	0.01	17	0.00	20
RT2	0.02	19	0.01	19	0.01	18	0.00	20
RT3	0.02	19	0.02	18	0.01	18	0.00	20
RT4	0.02	19	0.02	18	0.01	18	0.00	20
RT5	0.02	19	0.02	18	0.01	18	0.00	20
RTG	0.02	19	0.02	18	0.01	18	0.00	20
RS	0.11	17	0.20	11	0.15	8	0.28	2

Résultats expérimentaux 63

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

	Famille F2
	n = 20		n=50		n = 100		n = 150
	Ecart	BI	Ecart	BI	Ecart	BI	Ecart	BI
RT1	0.28	13	0.04	17	0.00	19	0.00	19
RT2	0.21	17	0.01	18	0.00	20	0.00	20
RT3	0.21	17	0.01	18	0.00	20	0.00	20
RT4	0.21	17	0.01	17	0.00	20	0.00	20
RT5	0.21	17	0.01	17	0.00	20	0.00	20
RTG	0.21	17	0.01	18	0.00	20	0.00	20
RS	0.21	17	0.25	9	0.18	2	0.40	1

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

	Famille F3
	n = 20		n=50		n = 100		n = 150
	Ecart	BI	Ecart	BI	Ecart	BI	Ecart	BI
RT1	2.63	1	1.05	3	0.38	1	0.57	0
RT2	1.59	2	0.48	6	0.15	6	0.13	3
RT3	1.58	2	0.54	6	0.16	7	0.17	3
RT4	1.91	1	0.52	6	0.18	4	0.25	2
RT5	1.92	1	0.58	5	0.17	5	0.27	1
RTG	1.51	3	0.45	7	0.14	7	0.13	3
RS	1.75	1	0.92	1	0.70	1	0.75	0

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

	Famille F4
	n = 20		n=50		n = 100		n = 150
	Ecart	BI	Ecart	BI	Ecart	BI	Ecart	BI
RT1	1.02	9	0.41	7	0.12	9	0.07	11
RT2	0.02	19	0.03	17	0.02	17	0.01	18
RT3	0.22	16	0.03	17	0.04	17	0.02	17
RT4	0.04	18	0.02	18	0.01	19	0.00	20
RT5	0.04	18	0.01	19	0.01	19	0.00	19
RTG	0.02	19	0.01	19	0.01	19	0.00	20
RS	0.18	17	0.26	8	0.34	1	0.34	1

Résultats expérimentaux 64

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

	Famille F5
	n = 20		n=50		n = 100		n = 150
	Ecart	BI	Ecart	BI	Ecart	BI	Ecart	BI
RT1	1.43	6	0.71	3	0.38	2	0.20	5
RT2	0.46	13	0.20	11	0.08	12	0.06	9
RT3	0.47	13	0.23	9	0.14	7	0.11	6
RT4	0.42	14	0.20	9	0.06	13	0.06	8
RT5	0.45	13	0.23	8	0.11	7	0.09	5
RTG	0.35	14	0.16	12	0.06	13	0.04	12
RS	0.48	13	0.58	4	0.46	0	0.44	0

Nous remarquons tout d'abord que la procédure RTG a les écarts les plus faible notamment en la comparant avec les autres procédures de recherche taboue.

Bien que le Recuit simuléa fait un écart au pire des cas qui soit meilleur que celui de RT1 pour certaines instances (pour F3, RS donne un écart de 1.75% alors RT1 donne 2.63%), il s'avère que la recherche taboue notamment la RTG est plus performante que le RS et ce pour toutes les familles d'instances et toutes les tailles des problèmes.

Un résultat similaire a étédonnépar Houari et al. [36] qui ont effectuéune étude comparative entre ces deux méta-heuristiques et oùla recherche taboue était la plus performante.

On remarque aussi que pour les familles F1 et F2, une solution optimale est vite trouvée et cela dans la majoritéécrasante des instances testées et pour toutes les tailles des problèmes. D'autre part, on constate que plus la taille du problème augmente plus il est facile d'avoir une solution optimale et cela en tenant une solution égale à la borne BI (àl'exception de la famille F3). Ces résultats confirment le constat déjàétabli pour des problèmes similaires par H. Hadda [34] et Xi et al. [69] qui affirment que plus la taille des instances augmente, plus ils sont facilement solubles.

En revanche, les familles F3 et F5 se sont montrées très difficile à résoudre avec un nombre très faible de solutions optimales et des écarts relativement importants.

En se penchant sur les cinq procédures de la recherche taboue, on remarque que la RT1 est la moins performante avec le plus grand écart et le plus faible nombre de solutions optimales, on peut expliquer ce résultat par

Résultats expérimentaux 65

l'opérateur de changement utiliséà savoir le a-opt qui n'offre pas une exploitation importante de l'espace de recherche. De plus, la permutation des jobs voisins n'a pas un effet considérable sur la performance de la solution du fait que la majoritéde ces mouvements sont inutiles car ils ont une forte chance de ne pas agir sur le chemin critique. Par ailleurs, les procédures RT2 et RT3 ont donnéde bons résultats notamment pour la famille F3, mis à part cette famille spécifique, on constate que ces deux procédures n'ont pas dépasséun écart de 0.47% dans le reste des familles d'instances. Nous pouvons conclure d'une part quant à la performance de l'opérateur de changement na - opt que même s'il détruit la structure de la séquence il s'est avérétrès efficace, et d'autre part quant à la gestion de la liste taboue par la méthode d'inter-diction des mouvements qui a dominél'autre méthode du fait que la RT2 est plus performante que la RT3.

En ce qui concerne RT4 et RT5, on remarque une légère dominance de la RT4 par rapport à la RT5 pour les familles F5 et F3, pour le reste des familles les deux procédures ont donnédes résultats très similaires.

En ce qui concerne les bornes inférieures, on peut conclure qu'elles ont ^étébien efficaces étant donnéqu'elle ont coïncidéavec des makespans optimaux.

Dans ce contexte, les bornes BI4 et BI5 données par les équations (2.4) et (2.5) ont étéles plus performantes.

Nous avons enregistréle temps de calcul moyens pour toutes les heuristiques et les méta-heuristiques retenues à la fois pour chaque famille. Le Tableau 3.24 illustre ces temps de calcul.

Tableau 3.24 - Temps de Calcul pour m = 5

n

	20	50	100	150
F1	0.2 sec	5.55 sec	48.8 sec	8.6 sec
F2	1.5 sec	6.55 sec	3.8 sec	12.6 sec
F3	8.7 sec	1.4 min	5.2 min	18.5 min
F4	0.3 sec	6.3 sec	46.7 sec	1.6 min
F5	2.9 sec	25.3 sec	3.1 min	12.1 min

Comme on peut le constater, à l'exception des familles F3 et F5, le temps de calcul était très raisonnable ne dépassant pas 1.6 minutes pour la famille

F4 pour n = 150. Notons ici que les temps de calcul pour les familles F3 et

F5 sont important du fait qu'on ne touche pas souvent la borne inférieure.

Résultats expérimentaux 66

Par ailleurs, en passant de m = 5 à m = 10 machines au deuxième étage, on n'a pas constatéune différence considérable concernant le temps de calcul et les écarts des méta-heuristiques, en revanche, plus la taille de l'instance augmente, sa résolution requière un temps de calcul plus important.

Conclusion

Ce chapitre s'est focalisésur les tests expérimentaux des méthodes que nous avons adoptées pour la résolution du problème considéré. Après avoir justifiéles décisions portant sur le paramétrage des méta-heuristique, nous avons procédéà des tests expérimentaux pour les cinq familles d'instances. Nous avons interprétéles résultats obtenus, puis nous avons évaluéet com-paréles différentes méta-heuristiques en se basant sur les résultats des simulations et enfin nous avons présentéles temps de calculs qu'on a enregistrés pour chaque famille d'instance.

67

Conclusion générale

Dans ce travail, nous avons traitéun problème d'ordonnancement de type flow shop hybride avec machines dédiées, avec dates de disponibilitéet délais de livraison, cette configuration bien que trouvée dans le milieu industriel,

n'a pas ététraitée dans la littérature spécialisée. Le type d'atelier considérése compose de deux étages, le premier étage comprend une seule machine

commune et le deuxième étage se compose de in machines dédiées, tous les jobs ont des dates de disponibilitéauxquels ils rentrent dans l'atelier et des délais de livraison qui correspondent à des durées à passer avant de quitter l'atelier. Ce problème est NP-difficile au sens fort, notre objectifs était la minimisation du temps d'achèvement (makespan).

Nous avons dresséun état de l'art sur les problèmes de flow shop en se concentrant sur les méthodes de résolution approchées tels que les heuristiques spécifiques, la recherche taboue et le Recuit Simulé. Cette revue bibliographique nous a permis de constater le manque des travaux traitant cette configuration malgréla concurrence des techniques d'optimisation et la rapiditédes calculateurs de nos jours.

En absence d'une approche exacte, nous avons élaborédes bornes inférieures afin de pouvoir évaluer les résultats des autres méthodes approchées. Ces bornes se sont montrées très efficaces en particulier celle inspirée de l'ordre de Johnson. Des heuristiques inspirées de celles présentées dans la littérature ont étéimplémentées et adaptées à notre problème à savoir les heuristiques de Potts, NEH, Johnson et Palmer. En effet, après avoir testéces heuristiques nous avons constatéque les heuristiques qui se basent sur l'ordre de Johnson ou inspirées de l'heuristique NEH ont donnéles meilleurs écarts par rapport à la borne inférieure. Ces derniers ont étéimplémentées avec les méta-heuristiques retenues (recherche taboue RT et Recuit SimuléRS) pour leurs fournir les solutions de départ.

Opérant chacune avec une combinaison spécifique des opérateurs de changement des méthodes de gestion de la liste taboue, plusieurs variantes de la recherche taboue ont étécomparées entre elles puis avec le RS, le constat

Conclusion générale 68

était que la RT est plus performante que le RS pour le problème considéré. Par ailleurs, nous constatons que ce problème est facilement soluble pour des familles d'instances données alors qu'il reste difficile pour d'autres familles, et que plus la taille des problèmes augmente plus on a des chances pour trou-

ver une solution optimale. Notons que le temps de calcul était raisonnable ^àl'exception des familles d'instance difficiles qui requièrent un temps de calcul plus important.

Pour des travaux futurs, il serait très intéressant de développer une procédure par séparation et évaluation (PSE) afin de mieux évaluer les méta-heuristiques implémentées. De plus, ces méta-heuristiques peuvent être testées avec d'autres jeux de données comportant des familles d'instances différentes de celles présentées dans ce mémoire. Par ailleurs, l'élaboration d'heuristiques spécifiques performantes pour ce problème sera un apport considérable surtout quand il s'agit de résoudre des familles difficiles sachant que même les approches exactes ont leurs limites. Finalement, une application réelle de ce problème sera d'une grande importance et qui nous permettra de se rapprocher de la réalitéindustrielle.

69

Bibliographie

[1] ARTHANARY T.S., R. K. An extension of two machine sequencing problem. Journal of the Operational Research Society of India (1971), 10-22.

[2] ASMA, K. Contribution a l'ordonnancement d'ateliers agroalimen-taires utilisant des méthodes d'optimisation hybrides, Thèse de Doctorat, Ecole Centrale de Lille et l'Ecole Nationale d'Ingénieurs de Tunis, 2011.

[3] BAKER K.R., S. Z.-S. Sequencing with due-dates and early start times to minimize maximum tardiness. Naval Research Logistics Quarterly 21 (1974), 171-176.

[4] BILLAUT, J.-C. Recherche opérationnelle et aide à la décision pour les problèmes d'ordonnancement., Habilitation à diriger des recherche, UniversitéFrançois Rabelais, Tours, France, 1999.

[5] BLAÿZEWICZ, ECKER J., K. H. Scheduling computer and manufacturing processes. Springer-Verlag New York, Inc., New York, NY, USA, 1996.

[6] BOLAT A., AL-HARKAN I., A.-H. B. Flow-shop scheduling for three serial stations with the last two duplicate. Computers & Operations Research (2005), 647-667.

[7] CAMPBELL H. G., DUDEK R., S. M. A heuristic algorithm for the n job, m machine sequencing problem. Management Science 16, 10 (1970), B630-B637.

[8] CARLIER, J. The one-machine sequencing problem. European Journal of Operational Research 11, 1 (1982), 42 - 47.

[9] CARLIER J., C. P. Problèmes d'ordonnancement: modélisation, complexité, algorithmes. Masson, Paris, 1988.

[10] CARLIER J., R. I. Two branch and bound algorithms for the permutation flow shop problem. European Journal of Operational Research 90, 2 (1996), 238 - 251.

[11]

BIBLIOGRAPHIE 70

BIBLIOGRAPHIE 71

BIBLIOGRAPHIE 72

BIBLIOGRAPHIE 73

CAVORY, G. Une approche génétique pour la résolution d'ordonnance-ments cycliques, thèse de doctorat, Thèse de Doctorat, Universitéd'Ar-tois, 2000.

[12] CERNY, V. Thermodynamical approach to the traveling salesman problem : an efficient simulation algorithm. Journal of optimization theory and applications 45, 1 (1985), 41-51. eng.

[13] CHEN L., BOSTEL N., D. P. C. J. X. L. A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal. European Journal of Operational Research 181, 1 (2007), 40 - 58.

[14] CONWAY R.W., MAXWELL W.L., M. L. Theory of Scheduling. Addison-Wesley Publishing Company, 1967.

[15] DRIDI N., HADDA H., H.-G. S. Méthode heuristique pour le problème de flow shop hybride avec machines dédiées. RAIRO - Operations Research 43, 4 (2009), 421-436.

[16] DRÉO J., PETROWSKI A., T. . S. P. Métaheuristiques pour l'optimi-sation difficile. 2003.

[17] EL MAGHRABY S.E, K. R. The Planning and Scheduling of Production Systems. Chapman & Hall, UK, 1997, ch. 6, Production control in hybrid flowshops : an example from textile manufacturing.

[18] ERSCHLER J., FONTAN G., R. F. Ordonnancement en ateliers spécialisés. In Encyclopédie du management, P. Vuibert, Ed., vol. 2. Helfer et Orsoni, 1992, pp. 208-229.

[19] ESQuIROL P., L. P. L'ordonnancement. Economica, Paris, 1999.

[20] FRAMINAN JM., GuPTA JND., L. R. A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. Journal of the Operational Research Society (2004).

[21] GAREY M. R., J. D. S. Computer and Intractability : a Guide to the Theory of NP- Completeness. W. H. Freeman and Company, San Francisco, USA, 1979.

[22] GLOVER, F. Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13, 5 (1986), 533 - 549. Applications of Integer Programming.

[23] GLOVER, F. Tabu search - part I. ORSA Journal on Computing 1, 3 (1989), 190-206.

[24] GLOVER, F. Tabu search - part II. ORSA Journal on Computing 2, 1 (1990), 4-32.

[25] GRABowSKI, J. On two-machine scheduling with release and due dates to minimize maximum lateness. Opsearch, Journal of the Operations Research Society of India 17 (1980), 133-154.

[26] GRABowSKI J., E. A. Algorithms for job scheduling problems with application to discrete production processes control. Reports of the Institute of Engineering Cybernetics, Technical University of Wroclaw, 8 (1983).

[27] GRABowSKI J., P. J. Sequencing of jobs in some production system. European Journal of Operational Research 125, 3 (2000), 535 - 550.

[28] GRABowSKI J., SKUBALSKA E., S. C. On flow shop scheduling with release and due dates to minimize maximum lateness. The Journal of the Operational Research Society 34, 7 (1983), 615-620.

[29] GRABowSKI J., W. M. A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Computers & Operations Research 31, 11 (2004), 1891 - 1909.

[30] GRABowSKI J., NowIcKI E., Z. S. A block approach for single-machine scheduling with release dates and due dates. European Journal of Operational Research 26, 2 (1986), 278 - 285.

[31] GRAHAM R.L, LAwLER E.L., L. J. R. K. Optimization and approximation in deterministic sequencing and scheduling : a survey. Annals of Discrete Mathematics 5 (1979), 287-326.

[32] GUPTA JND, HARIRI A., P. C. Scheduling a two-stage hybrid flow shop with parallel machines at the first stage. Annals of Operations Research (1997), 171-191.

[33] GUPTA JND, S. E. Flowshop scheduling research after five decades. European Journal Of Opereration Research 169, 3 (2006), 699-711.

[34] HADDA, H. Contribution à l'étude et à la résolution des problèmes d'ordonnancement de flow shops d'assemblage et de flow shops hybrides à machines dédiées, Thèse de Doctorat, Ecole National d'ingénieurs de Tunis, 2009.

[35] HALL L.A., S. D. Jackson's rule for single-machine scheduling: Making a good heuristic better. Mathematics of Operations Research 17, 1 (1992), 22-35.

[36] HAoUARI M., M. R. Heuristic algorithms for the two-stage hybrid flowshop problem. Operations Research Letters 21, 1 (1997), 43 - 53.

[37] HARRATH, Y. Contribution a l'ordonnancement conjoint de la production et de la maintenance :application au cas d'un job shop, Thèse de

Doctorat, UFR des Sciences et Techniques de l'Universitéde Franche-Comté, 2003.

[38] JIN Z., YANG Z., I. T. Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem. International Journal of Production Economics 100, 2 (2006), 322 - 334.

[39] JIN Z.H., OHNO K., I. T. E. S. Scheduling hybrid flowshops in printed circuit board assembly lines. Production & Operations Management (2002), 216-230.

[40] JOHNSON, S. M. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1, 1 (Mar. 1954), 61-68.

[41] JuNGWATTANAKIT J., REODECHA M., C. P. W. F. A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Computers & Operations Research 36, 2 (2009), 358 - 378.

[42] KACEM, I. Ordonnancement multicritère des job-shops flexibles : formulation, bornes inférieures et approche évolutionniste coopérative, Thèse de Doctorat, Ecole Centrale de Lille, Universitéde Lille 1, 2003.

[43] KALCzYNSKI J., K. J. An improved neh heuristic to minimize ma-kespan in permutation flow shops. Computers & Operations Research 35, 9 (2008), 3001 - 3008. Part Special Issue : Bio-inspired Methods in Combinatorial Optimization.

[44] KIRKPATRICK S., GELATT JR., V. M. Optimization by simulated annealing. Science 220, 4598 (1983), 671-680.

[45] KISE H., IBARAKI T., M. H. Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times. Journal of Opereration Research Society Of Japan 22 (1979), 205-224.

[46] KuRz M.E., A. R. Scheduling flexible flow lines with sequence-dependent setup times. European Journal of Operational Research 159, 1 (2004), 66-82.

[47] LA, H. T. Utilisation d'ordres partiels pour la caractérisation de solutions robustes en ordonnancement, Thèse de Doctorat, Laboratoire d'Analyse et d'Architecture des Systèmes du CNRS, 2005.

[48] LEE G.-C., K. Y.-D. A branch-and-bound algorithm for a two-stage hybrid flowshop scheduling problem minimizing total tardiness. International Journal of Production Research (2004), 4731-4743.

[49] LENSTRA, J. Sequencing by enumerative methods. Mathematical Centre Tracts 69, Amesterdam, 1977.

[50] LENSTRA J.K., KAN RiNNooY A.H.G., B. P. Complexity of machine scheduling problems. , 1977.

[51] LoPEz P., R. F. Ordonnancement de la production. Hermes Science Publications, 2000.

[52] McMAHoN G., F. M. On scheduling with ready times and due dates to minimize maximum lateness. Journal of operation research. 23 (1975), 475-482.

[53] METRoPoLiS, RoSENBLuTH N., R. A. W. Equation of state calculations by fast computing machines. Journal of Medical Physics 21, 6 (1953), 1087-1092.

[54] MiTTAL B.S., B. P. Two machine sequencing problem with parallel machines. Journal of the Operational Research Society of India (1973), 50-61.

[55] NAwAz M., ENScoRE JR., H. I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. 91-95.

[56] NowicKi E., S. C. An approximation algorithm for a single-machine scheduling problem with release times and delivery times. Discrete Applied Mathematics 48, 1 (1991), 69 - 79.

[57] NowicKi E., S. C. The flow shop with parallel machines : A tabu search approach. European Journal Of Opereration Research 106, 2-3 (1998), 226-253.

[58] Ocentsguz C., ZiNDER Y., D. V. J. A. L. M. Hybrid flow-shop scheduling problems with multiprocessor task systems. European Journal of Operational Research 152, 1 (2004), 115 - 131.

[59] PALMER, D. S. Sequencing jobs through a multi-stage process in the minimum total time - a quick method of obtaining near optimum. Operational Research Quarterly 16, 1 (1965), 101-107.

[60] PoTTS, C. Analysis of heuristics for two-machine flow-shop sequencing subject to release dates. Mathematics of Operations Research 10 (1985), 576-584.

[61] RAo, T. Sequencing in the order a, b, with multiplicity of machines for a single operation. Journal of the Operational Research Society of India (1970), 135-144.

[62] Ruiz R., M. C. A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research 169, 3 (2006), 781 - 800.

[63]

BIBLIOGRAPHIE 74

Ruiz R., V. R. The hybrid flow shop scheduling problem. European Journal Of Opereration Research 205, 1 (2010), 1-18.

[64] SCHARGE, L. Obtaining optimal solution of resource constrained network scheduling problem. Unpublished manuscript (1971).

[65] TADEi R., GuPTA JND, D. F. C. M. Minimising makespan in the two-machine flow-shop with release times. Journal of the Operational Research Society 49, 1 (1998), 77-85.

[66] TAiLLARD, E. Some efficient heuristic methods for the flow shop sequencing problem. European Journal Of Operational Research 47, 1 (1990), 65-74.

[67] WARDoNo B., F. Y. A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities. European Journal of Operational Research 155, 2 (2004), 380 - 401.

[68] WiDMER M., HERTS A., C. D. Les m'etaheuristiques. Hermes edition, 2001, ch. 3, pp. 55-93.

[69] Xi S., KAzuKo M., H. N. Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flowshop scheduling. European Jounal Of Operation research 146, 3 (2003), 498-516.

[70] XiAo W., HAo P., Z. S. X. X. Hybrid flow shop scheduling using genetic algorithms. In Intelligent Control and Automation, 2000. Proceedings of the 3rd World Congress on (2000), vol. 1, pp. 537 -541 vol.1.

[71] ZDRzA LKA, S. Scheduling jobs on a single machine with release dates, delivery times and controllable processing times : Worst-case analysis. Operations Research Letters 10, 9 (1991), 519-523.

Résumé

Dans ce travail nous traitons un problème d'ordonnancement du type flow shop hybride avec machines dédiées, avec dates de disponibilitéet délais de livraison, l'objectif est de minimiser la date d'achèvement (makespan). Nous avons abordéce problème avec des méthodes de résolution approchées. Nous avons adaptéquelques heuristiques connues de la littérature. Deux méta-heuristiques à savoir la recherche taboue et Recuit simuléont étédéveloppées. L'évaluation des ces différentes méthodes a étéfaite à l'aide des bornes inférieures que nous avons élaborées. Les résultats expérimentaux montrent l'efficacitédes bornes inférieures et la dominance de la recherche taboue par rapport au Recuit Simulé.

Mots clés : Flow Shop hybride, Recuit Simulé, Recherche taboue.

Abstract

In this work, we consider the two-stage hybrid flow shop problem with dedicated machines, release and delivery times. The objestive is to minimize the maximum completion time (i.e. the makespan). Several heuristics inspired from the literature have been adapted. Two metaheuristic approachs based on Simulated Annealing and Tabu Search are also proposed. The results are compared to several newly developed lower bounds. These results show the efficiency of the lower bounds and the superiority of the tabu search approach.

Keywords : Hybrid Flowshop scheduling, Simulated annealing, Tabu search.