Hybridation des métaheuristiques pour la résolution

de problème d’ordonnancement multi-objectif dans

un atelier flow-shop
JEBARI Hakim*, RAHALI EL AZZOUZI Saida, SAMADI Hassan
Laboratoire des technologies de l’information et de la communication (LABTIC)
Ecole nationale des sciences appliquées de Tanger (ENSAT)
Tanger, Maroc
hjebari1@yahoo.fr, rahali_elazzouzi@yahoo.fr, ha.samadi@gmail.com

Résumé— Cet article traite la résolution des problèmes  Les objectifs liés au coût : minimiser les coûts de
d’ordonnancement multi-objectifs dans un atelier complexe de lancement, de production, de stockage, de transport, etc.
type flow-shop par la construction des métaheuristiques hybridées
séquentiellement et des métaheuristiques hybridées parallèlement La satisfaction de tous les critères à la fois est souvent
synchrone basée sur la pondération de fonction objective : délicate, car elle conduit souvent à des situations contradictoires
l’algorithme génétique avec la recherche tabou, l’algorithme et à la recherche de solutions à des problèmes complexes
génétique avec le recuit simulé et l’algorithme génétique avec d’optimisation [2].
l’algorithme génétique. Ensuite une étude comparative est menée
sur les résultats de chaque type d’hybridation d’une part, d’autre Dans cet article, les méthodes de résolution des problèmes
part entre les résultats de ces deux types d’hybridation, afin d’ordonnancement sont basées sur l’hybridation séquentielle des
d’identifier la méthode et le type d’hybridation qui fournit la Métaheuristiques :
meilleure solution pour l’ordonnancement multi-objectif.
 Algorithme génétique avec la recherche tabou.
Mots clés— Ordonnancement ; métaheuristiques; algorithmes  Algorithme génétique avec le recuit simule.
génétiques; recherche tabou; recuit simulé; hybridation; flow-shop;  Algorithme génétique avec l’algorithme génétique.
multi-objectifs.
Une méthode hybride est une méthode de recherche
I. INTRODUCTION constituée d’au moins de deux méthodes de recherche distinctes.
Dans les dernières années, le développement rapide de la Elle consiste à exploiter les avantages respectifs de plusieurs
technologie de l'information avec l'intensification de la méthodes en combinant leurs algorithmes suivant une approche
tendance de la mondialisation économique, fait que les synergétique [3].
systèmes de production doivent faire face de plus en plus à la
compétition au niveau du délai d'achèvement de nouveaux Une méthode hybride peut être mauvaise ou bonne selon le
produits. choix et les rôles de ses composants. Pour définir une méthode
hybride efficace, il faut savoir caractériser les avantages et les
Les décisions des entreprises ont un impact significatif sur limites de chaque méthode.
la fabrication, le coût du produit, le délai de livraison, la
qualité… etc., pour les améliorés, elles doivent optimiser la Les origines des algorithmes hybrides remontent
planification et l'ordonnancement de la production, la tâche la probablement aux travaux décrits dans [4] [5].
plus difficiles. D'une manière générale, on distingue plusieurs Actuellement, les approches hybrides gagnent en popularité
classes d'objectifs concernant un ordonnancement [1] : car ce type d'algorithme produit généralement les meilleurs
résultats pour plusieurs problèmes d’optimisation combinatoire
 Les objectifs liés au temps : minimisation du temps total
[6]. En effet, selon [7], les approches hybrides ont permis
d'exécution, du temps moyen d'achèvement, des durées
d’obtenir de bons résultats dans une grande variété de problèmes
totales de réglage ou des retards par rapport aux dates de
théoriques d'optimisation combinatoire.
livraison.
 Les objectifs liés aux ressources : maximiser la charge II. MÉTHODES DE RESOLUTION
d'une ressource ou minimiser le nombre de ressources A. Les algorithmes hybrides
nécessaires pour réaliser un ensemble de tâches.
Le développement et l'application des méta-heuristiques
Xème Conférence Internationale : Conception et Production Intégrées, CPI 2015, 2-4
hybrides est de plus en plus susciter l'intérêt académique, ces
Décembre 2015, Tanger - Maroc. les méthodes hybrides combiner différents concepts ou des
Xth International Conference on Integrated Design and Production, CPI 2015, composants de divers méta-heuristiques [7] et à cette fin, ils
December 2-4, 2015, Tangier - Morocco. tentent de fusionner les points forts et éliminent les faiblesses
des différents concepts de méta-heuristiques. Par conséquent, l’algorithme génétique de tri non dominé (NSGA II),
l'efficacité de l'espace de solution rechercher peut être encore l’algorithme SPEA II et l’algorithme PAES.
améliorée et de nouvelles opportunités émergé ce qui peut • Les méthodes non agrégées et non Pareto comme
conduire à des méthodes de recherche encore plus puissante et l’algorithme VEGA.
plus flexible. Talbi [8] a proposé une taxonomie pour les
méta-heuristiques hybrides, [9], propose une classification des Les méthodes agrégées ou l’utilisation de la dominance de
techniques d’hybridation en les classifiant en trois Pareto traitent les objectifs simultanément, alors que, les
catégories selon leur architecture : méthodes dites non agrégées et non Pareto possèdent un
 Hybridation séquentielle processus de recherche qui traite séparément les objectifs.
 Hybridation parallèle synchrone En ce qui concerne le problème multi objectif, trois
 Hybridation parallèle asynchrone techniques différentes de résolution sont proposées.
1) Hybridation séquentielle : c’est le type d’hybridation L’agrégation en un seul objectif, les méthodes basées sur des
approches non Pareto et les méthodes basées sur la
le plus populaire. Elle consiste à appliquer plusieurs méthodes
dominance de Pareto. Les algorithmes MOGA [12], NPGA
de telle manière que le (ou les) résultat(s) d’une méthode [13], SPEA-II [14], NSGA-II [15] sont quelques méthodes
serve(nt) de solution(s) initiale(s) à la suivante.   proposées sur la dominance de Pareto pour résoudre des
2) Hybridation parallèle synchrone : cette hybridation problèmes multi objectifs.
est réalisée par incorporation d’une méthode de recherche III. RESOLUTION DU PROBLÈME DE L’ORDONNANCEMENT EN
particulière dans un opérateur. Elle est plus complexe à mettre INDUSTRIE AUTOMOBILE
en œuvre que la précédente. L’objectif est de combiner une Les industries doivent maintenir un taux de productivité en
recherche locale avec une recherche globale dans le but constante évolution pour faire face à la concurrence ; des
d’améliorer la convergence.  contraints peuvent toutefois apparaître au niveau du système de
3) Hybridation parallèle asynchrone (coopérative) : les production qui engendre des coûts de production ainsi que des
coûts de non utilisation relativement élevés.
méthodes hybrides appartenant à cette classe sont caractérisées
par une architecture telle que deux algorithmes A et sont Nous intéressons dans l’article au cas d’usine de fabrication
des câbles de banche de bord des voitures pour l’industrie
impliqués simultanément et chacun ajuste l’autre. Les
automobile, un cas similaire est déjà traité dans [16].
Algorithmes A et B partagent et échangent de l’information
tout au long du processus de recherche. L’atelier peut contenir une ou plusieurs chaînes de
production, chaque chaîne est composée de 4 Machines :
B. Méthodes multi objectifs  M1 : Machine de coupe et de torsion des fils simple.
L’optimisation multi objectif est un domaine fondamental de  M2 : Machine d’assemblage du câble.
l’aide à la décision multicritère, nécessaire aux nombreux
milieux scientifiques et industriels. Au cours des deux dernières  M3 : Machine de test électrique pour tester la
décennies, un très grand nombre de travaux, à la fois théoriques fonctionnalité de produit fini.
et appliqués, ont été publiés dans ce domaine.
 M4 : Machine d’emballage des produits finis.
La résolution d’un problème d’optimisation multi objectif
L’atelier étudié comporte 2 chaînes de production.
consiste à déterminer la solution correspondante au mieux aux
préférences du décideur parmi les solutions de bon compromis. Les produits passent par les quatre machines en série dans
L’une des questions les plus difficiles est donc liée à le même ordre. Il s’agit donc d’un atelier de type flow-shop.
l’identification de l’ensemble Pareto optimal, ou d’une
approximation de celui-ci pour des problèmes complexes. En Plusieurs opérations de changement des outils ou de
particulier, beaucoup de problèmes de mécanique rencontrés réglages sont à gérer sur les postes de l’atelier, conjointement
dans l’industrie sont de nature multi objectif. aux opérations de production. Les temps improductifs générés
par ces opérations sont assez importants, compte tenu du fait que
La classification des méthodes d’optimisation multi objectif le temps de lancement de la fabrication d’un produit dépend de
s’articule autour des notions de transformation et d’optimum de celui qui l’a précédé. Tous les arrêts et les changements
Pareto : survenant au cours d’une opération doivent être pris en compte
pour permettre un bon ordonnancement de l’atelier.
• Les méthodes agrégées qui sont La méthode de
pondération, la méthode de programmation par but, la méthode A. Problèmes d’ordonnancement de type flow-shop
du min-max et la méthode du ε contrainte. Dans le problème d'ordonnancement de systèmes de type
• Les méthodes fondées sur Pareto : proposée par flow shop chaque machine ne peut effectuer qu’une seule
opération à la fois et chaque job ne peut avoir qu’une seule
[10] pour résoudre les problèmes proposés par [11], qui sont opération en cours de réalisation simultanément. La capacité de
l’algorithme génétique à plusieurs objectifs (MOGA), stockage inter-machines est définie et la préemption
d’opérations n’est pas autorisée. Les problèmes
d'ordonnancement d'ateliers de type flow-shop, ou ateliers à coefficients de pondération par le décideur qui dispose des
cheminements uniques, sont parmi les problèmes les plus connaissances approfondies du problème étudié, en plus elle est
connus dans le domaine de l'ordonnancement. Ils ont fait l’objet aussi simple à utiliser en effet, le problème multi-objectif est
de nombreuses études dont l’objectif principal est la transformé en problème mono-objectif.
minimisation de la date de fin d’exécution [17] [18] [19].
L’hybridation séquentielle des deux métaheuristiques est
La résolution des problèmes d’ordonnancement de type utilisée aussi dans cet article pour faire l’optimisation multi-
flow-shop a connu plusieurs étapes. objective, la première pris en compte le critère C1 et la seconde
pris en compte le critère C2.
Depuis les travaux de Johnson [20], l'objectif le plus visé,
dans la résolution de ces problèmes d'ordonnancement est de L’atelier étudié possède deux chaînes Ch1 et Ch2
réduire au maximum le Makespan ou Cmax, temps de fin de fonctionnant en flow-shop. L’optimisation du passage des
fabrication du dernier produit. produits dans les chaînes consiste à minimiser les temps de
production (en minimisant les temps d’arrêt, de nettoyage et de
Diverses approches heuristiques [21] [22] [23] [24] ont été non utilisation des chaînes).
proposées pour réduire le Makespan [25].
Nous proposons de mettre en œuvre une méthode
Certain auteurs sont concentrés sur la résolution d’un seul d’optimisation multi-objective basée sur l’hybridation des
objectif [26] [27] [28] [29] [30] [31] [32], Cependant, la plupart métaheurstiques pour la résolution du problème
des problèmes réels impliquant des objectifs multiples. d’ordonnancement des produits.
D’autres auteurs ont abordés les problèmes
C. Formulation du problème
d'ordonnancement multi-objectifs de type flow-shop [33] [34]
[35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47].  F : opération de fabrication du produit i sur la ligne Ch .
Nous nous proposons de résoudre le problème  P : produit fini après l’opération F .
d’ordonnancement en industries automobile d’un point de vue
 P : temps de fabrication de l’opération F .
multi-objectif tout en énonçant les différents critères et
contraintes s’y rattachant et en utilisant les algorithmes  CP : temps de fin d’exécution de P sur la chaîne Ch .
génétiques comme méthode de résolution.
 CP : coût de stockage par unité de temps du produit P .
B. Optimisation multi-objectifs
D’un point de vue mathématique, un problème  tp : temps de préparation de la chaîne Ch avant
d’optimisation multi-objectif, se présente, dans le cas où le l’opération F .
vecteur f regroupe k fonctions objectif, de la façon suivante [7] :  tp : Temps d’arrêt durant l’opération F sur la chaîne
Ch .
minimiser f x x ∈ R , f x ∈
avec g x 0 g x ∈  tp : Temps de non utilisation de la chaîne Ch avant
l’opération Fik.
et h x 0 h x ∈
Pour mieux résoudre ces problèmes d’optimisation multi-  C : Coût total de production.
objectifs, il est nécessaire de simplifier les différentes fonctions  C : Coût unitaire de production du produit i sur la
objectives pour faciliter leur traitement. Parmi les différentes
chaîne Chk.
méthodes utilisées, la méthode de pondération des fonctions
objectives qui se présente est comme suit : à chacune des  D : Durée des opérations de nettoyage sur la chaîne
fonctions objectives, est appliqué un coefficient de pondération Ch .
et la somme pondérée de fonctions objectives est effectuée. Une
nouvelle fonction objective est ainsi obtenue [48].  D : Durée des changements de format sur la chaîne
Ch .
Formulation du problème avec la méthode de pondération
des fonctions objectives :  C : Coûts d’arrêt et de non utilisation de la chaîne
Ch par unité de temps.

miminiser f x w f x x ∈  C : Coût total d’arrêt et de non utilisation des chaînes

par unité de temps.
 trop_Ch : Les temps de production exprimés en unité de
w 0 ∀ i ∈ 1, … . . , k et w 1 temps.
 tarr_Ch : Les temps d’arrêt exprimés en unité de temps.
avec g x 0 g x ∈
et h x 0 h x ∈  tnett_Ch : Les temps de nettoyage exprimés en unité de
temps.
Cette approche est très efficace algorithmiquement par
rapport aux autres méthodes compte tenu du fait qu’elle permet Les dates sont calculées à partir d’un temps initial t0 :
de retrouver la surface de compromis, en faisant varier les
  Cpro_Ch : Les coûts de production. gouvernée par un opérateur de sélection et un opérateur de
croisement alors que la phase d'adaptation individuelle fait appel
 Cnou_Ch : Les coûts de non utilisation des chaines. à un opérateur de mutation. La création d'une nouvelle
D. Critères à minimiser génération est obtenue par itération de l'algorithme génétique qui
va créer de nouveaux individus et en détruire d'autres ce qui
Les critères à minimiser sont ceux relatifs aux coûts de permet le renouvellement de la population. L’exploration de
fabrication et aux coûts des temps engendrés par les opérations l'espace de recherche est alors réalisée par les opérateurs de
de nettoyage ainsi que des temps d’arrêt et de non utilisation des mutation et assure la diversification des individus de la
chaînes. population. L'exploitation, quant à elle, est assurée par les
Ils s’expriment respectivement par les deux fonctions opérateurs de croisement, qui recombinent les solutions, afin de
objectives suivantes : F1 et F2, correspondant respectivement au les améliorer en conservant leurs meilleures caractéristiques.
coût total de production et au coût d’arrêt et de non utilisation Les algorithmes génétiques présentent plusieurs avantages
des chaînes. tels que :
F C W P C ,  La simplicité de l’approche ;
1: si le produit est fabriquer dans la chaine  La possibilité de paralléliser l’algorithme ;
W 1
0 ∶ sinon
 La facilité d’implémentation ;
F C C W tp tp tel que tp D D ,
 La flexibilité : peut être facilement modifié pour d’autres
1: si le produit est fabriquer dans la chaine problèmes ;
W 2
0 ∶ sinon
 Il gère les problèmes d’optimisation multi-objectifs et
E. Fonction fitness à optimiser
multimodales ;
Etant donné que la minimisation du coût de production est
plus importante que la minimisation des coûts de non utilisation  Il permet une bonne exploration de l’espace de recherche
des chaînes, la fonction fitness F à minimiser dans le premier ;
type de l’hybridation correspond à la somme pondérée des deux D’autre part, il existe des limites pour cet algorithme tels
fonctions objectifs F1 et F2, avec des poids β et β définis en que :
fonction de l’importance de ces deux critères :
F F β F β 3 , β β 1, β 0, β 0 3
 Le problème de représentation de la solution.
F β C β C , β β 1, β 0, β 0 4  L’ajustement de différents paramètres : taille de
population, taux de mutation,…etc.
F β W P C β C W tp tp ,  Son exécution qui est lente par rapport à d’autres
méthodes.
β β 1, β 0, β 0 5
 Sa convergence prématurée.
Pour le deuxième type de l’hybridation correspond à la
fonction objective F1 pour la première méta-heuristique et la  Il ne peut pas garantir des temps de réponse constants.
fonction objective F2 pour la deuxième méta-heuristique.
Pour utiliser un algorithme génétique pour un problème
Les coûts sont calculés en fonction des formules (1) et (2) particulier, on doit donc disposer des cinq éléments suivants
et la fonction fitness déduite à partir de la formule (3), (4) et (5). [51] :
F. Adaptation d’algorithme génétique :  Le codage des solutions : associe à chacun des points de
Les algorithmes génétiques sont des algorithmes l’espace d’états une structure de données. Elle vient
d’optimisation inspirés de la théorie de l’évolution des espèces généralement après une phase de modélisation
de Charles Darwin. Les premier travaux de John Holland mathématique du problème traité. La qualité du codage
remontent aux années 1960 et ont trouvé un premier conditionne le succès de l’algorithme.
aboutissement en 1975 avec la publication de [49]. C’est  Une méthode de génération de la population initiale : la
cependant l’ouvrage de David Goldberg qui a largement population d’individus produite initialement qui servira
contribué à développer les algorithmes génétiques [50]. Un de base pour les générations futures doit être non
algorithme génétique est basé sur une population d’individus homogène.
dont chacun est une solution candidate du problème. Chaque
solution doit être codée. Cette représentation codée est appelée  Une fonction à optimiser : Cette fonction retourne une
chromosome, et est composée de gènes. Le degré d'adaptation valeur réelle appelée fitness, qui va permettre de
d'un individu à l'environnement est exprimé par la valeur de la déterminer la probabilité de sélection d’un individu [52].
fonction objective correspondante. La taille de la population
 Les opérateurs génétiques : permettent de diversifier la
reste constante tout au long de l’algorithme génétique. La
population au cours des générations et d’explorer
recherche de la solution est réglée par trois opérateurs qui sont
l’espace d’états. Le croisement recompose les gènes
appliqués successivement. La phase de coopération est
d’individus de la population. La mutation entraîne des
 altérations minimes sur les individus pour éviter la puis la température est abaissée. Le procédé est répété à des
convergence rapide de la population. La sélection températures successivement plus basses jusqu’à ce que l’état
favorise les meilleurs individus. congelé soit atteint. Cette procédure permet au système de se
déplacer à la baisse des états d’énergie, tout en sautant hors des
 Les paramètres de dimensionnement : taille de la minima locaux (en particulier à des températures plus élevées)
population, nombre total de générations ou critère en raison de l’acceptation probabiliste de quelques mouvements
d’arrêt, probabilités d’application des opérateurs de à la hausse.
croisement et de mutation.
Le logigramme du recuit simulé adapté est décrit comme suit :
Le logigramme de l’algorithme génétique adapté est décrit
comme suit :

Fig 2. Logigramme de la recuit simulé adapté

H. Adaptation de la méthode Tabou

La recherche tabou (TS) est une méthode d’optimisation
Fig 1. Logigramme de l’algorithme génétique adapté
mathématique, appartenant à la classe des techniques de
G. Adaptation du recuit simulé : recherche locale [56], [57], [58]. La recherche tabou améliore
les performances d’une méthode de recherche locale en utilisant
Dans le recuit simulé (SA), un système est initialisé à une des structures adaptées de mémoire : une fois une solution
température T avec une configuration dont l’énergie est évaluée potentielle a été déterminée, elle est marquée comme taboue afin
comme [53], [54], [55]. Une nouvelle configuration est réalisée que l’algorithme ne visite pas cette possibilité à plusieurs
en appliquant une variation aléatoire, et la variation de l’énergie reprises. Pour explorer les régions de l’espace de recherche qui
ΔE est calculée. La nouvelle configuration est seraient laissées inexplorées par la procédure de recherche
inconditionnellement acceptée si elle diminue l’énergie du locale, la recherche tabou modifie la structure du voisinage de
système ΔE. Si l’énergie du système est augmentée par le chaque solution au fur et à mesure que la recherche progresse.
changement, la nouvelle configuration est acceptée avec une Les solutions admises sont déterminées par l’utilisation de
certaine probabilité aléatoire. Dans le schéma original de structure de mémoire.
Metropolis, la probabilité est donnée par le facteur de Boltzmann
/
. Ce processus est répété plusieurs fois à la température Dans sa forme la plus simple, une liste taboue est une
actuelle afin de parcourir efficacement l’espace de recherche, mémoire à court terme qui contient les solutions qui ont été
visitées dans le passé récent. C’est le type le plus important de I. Application de la 1er approche de l’hybridation des méta
la structure de la mémoire utilisée pour déterminer les solutions heuristiques
admises pour la liste taboue. L’hybridation séquentielle consiste à appliquer plusieurs
Les concepts de base de la recherche tabou sont : méthodes de telle façon que les résultats d’une méthode servent
de solutions initiales à la suivante.
 Liste tabou : utilisation d’une structure de mémoires
flexibles pour mémoriser les configurations ou bien les L’algorithme génétique possède une connaissance globale
zones visitées et inclure des mécanismes permettant explore l’espace de recherche tandis que la recherche tabou
d’interdire à l’algorithme certains mouvements pour ne détient une connaissance locale et exploite le voisinage. La
pas retourner trop rapidement (temporairement) vers les résolution par l’approche d’hybridation séquentielle se fait en
zones visitées. deux étapes :

 Critère d’aspiration : (assouplissement du mécanisme de La première étape est une application directe de
la liste taboue) autorisation et acceptation de certains l’algorithme génétique pour la prise en compte de critère F1.
mouvements tabous. Dans cette étape la population initiale est générée aléatoirement,
l’opérateur de sélection permet de choisir les meilleurs individus
 L’alternance entre ces deux premiers concepts dans le de la population courante, les opérateurs de croisement et de
processus est réalisée à l’aide d’un mécanisme de mutation permettent la génération de nouvelles solutions, à la fin
contrôle. de cette étape, une population d’individus qui satisfait le critère
F1 est obtenue.
 Stratégie d’intensification : exploitation plus approfondie
des zones prometteuses trouvées (visitées) récemment et Dans une deuxième étape, on a recours à la recherche tabou
renforcement de la recherche dans ces régions. pour optimiser le critère F2. Dans ce cas, un individu
quelconque de la population finale, obtenue dans la première
 Stratégie de diversification : exploration des zones qui étape, est choisi comme solution initiale. Cet individu servira de
n’ont pas encore été visitées. base pour la détermination des solutions ultérieures, une
Le logigramme de la recherche Tabou adaptée est décrit fonction voisine permet de générer des nouvelles solutions à
comme suit : partir de la solution courante. La liste tabou permet de conserver
la trace des dernières solutions déjà visitées. Le critère
d’aspiration permet de revenir à une solution déjà visitée et de
redémarrer la recherche dans une autre direction. A la fin de cette
deuxième étape, on obtient une solution qui satisfait le deuxième
critère. Finalement, on obtient une solution qui satisfait les deux
critères. La technique d’hybridation adoptée dans notre travail
est celle décrite par figure 4.

Fig 4. Hybridation sequentiel de l’algorithme génétique avec la recherche

tabou

De la même manière on hybride l’algorithme génétique

avec le recuit simulé et l’algorithme génétique avec l’algorithme
génétique comme le montre la figure 5 et la figure 6.

Fig 3. Logigramme de la recherche Tabou adaptée

 Fig 7. Hybridation parallèle synchrone de l’algorithme génétique avec la
recuit simulé et avec la recherche tabou

IV. SIMULATION ET ANALYSE

Tous les méthodes décrit dans cet article ont été
programmées en Java et exécutées dans un Core ™ i5 CPU avec
1.9 GHz 2.5 GHz et 4 Go de RAM.
Fig 5. Hybridation sequentiel de l’algorithme génétique avec la recuit Les valeurs de tarr_Ch et tnett_Ch de chaque produit sur
simulé
chaque chaîne sont attribuées aléatoirement entre 1 et 10.
∀ i 1,2 tarr_Ch P Random 1,5
∀ i 1,2 tnett_Ch P Random 1,5
La valeur de trop_Ch de chaque produit sur chaque chaîne
est attribuée aléatoirement entre 20 et 90.
∀ i 1,2 trop_Ch P Random 20,90
Les valeurs de Cpro_Ch et Cnou_Ch de chaque produit sur
chaque chaîne calculées en fonction des formules (1) et (2) et la
fonction fitness déduite à partir des formules (3) et (4).
Ces valeurs sont ensuite stockées dans un fichier pour leur
utilisation dans tous les programmes, ils sont exprimés en
minute.
Fig 6. Hybridation sequentiel de l’algorithme génétique avec la
l’algorithme génétique Les paramètres de la configuration de l’algorithme
génétique, la recherche tabou et le recuit simulé sont les mêmes
J. Application de la 2 ème approche de l’hybridation des méta dans les deux types d’hybridation.
heuristiques Après la construction des ordonnancements qui satisfaits les
L’algorithme se compose de deux phases qui alternent critères citées au-dessus en utilisent les deux types
régulièrement les progrès génétiques. Dans la première, seule la d’hybridation, la première est l'hybridation parallèle synchrone
partie pure de l’AG est active à objectif d’explorer l’espace des avec l’utilisation de la fonction de pondération (de fonction
solutions pour détecter les zones d’intérêt où les solutions fitness F), et la deuxième est l'hybridation séquentielle (de
peuvent être réglées. La deuxième phase est l’endroit où l’AG fontion fitness F1 pour la 1er métaheuristique et F2 pour la 2éme
est hybride (l’opérateur de mutation qui est remplacé par d’autre métaheuristique), on obtient les résultats montrer dans les
algorithme). figures 8 et 9 respectivement.
Certaines régions prometteuses de l’espace de recherche
vont être atteintes et donc vont être exploitées par le recuit
simulé [59] et la recherche tabou. L’équilibre entre l’exploration
et l’exploitation va être optimisé.
La technique d’hybridation adoptée dans notre travail est
celle décrite par la figure 7 :
 837 853
811
777
719
690
653
608 619
559 571
527
482
403 821 842
765 800
709
338 648 686
568 603 614
525 555
478
400
336

25 40 60 85 110 130 160 190 230 270 310 350 400 450 500
 Cmax obtenu par l'hybridation
parallèle synchrone 338 403 482 527 559 571 608 619 653 690 719 777 811 837 853
(AG+RS)
 Cmax obtenu par l'hybridation
parallèle synchrone 336 400 478 525 555 568 603 614 648 686 709 765 800 821 842
(AG+RT)

Fig 8. Hybridation parallèle synchrone de l’algorithme génétique avec le recuit simulé et avec la recherche tabou en utilisant la fonction de pondération

829
795 814
755
681 703
644
600 610
563
522 552 785 806
477 732 772
684
635 673
398 556 591 601
518 545
335 470
393 752 762 783
330
547 582 591 625 663 666 710
463 512 537
323 387

25 40 60 85 110 130 160 190 230 270 310 350 400 450 500
 Cmax obtenu par l'hybridation
séquentielle 335 398 477 522 552 563 600 610 644 681 703 755 795 814 829
(AG+AG)
 Cmax obtenu par l'hybridation
séquentielle 330 393 470 518 545 556 591 601 635 673 684 732 772 785 806
(AG+RS)
 Cmax obtenu par l'hybridation
séquentielle 323 387 463 512 537 547 582 591 625 663 666 710 752 762 783
(AG+RT)

Fig 9. Hybridation séquentielle de l’algorithme génétique avec le recuit simulé, avec la recherche tabou et avec l’algorithme génétique
 L’étude comparative des solutions obtenues par [4] H. Mühlenbein, M. Gorges-Schleuter & O. Krämer, Evolution algorithms
l’hybridation parallèle synchrone de l’algorithme génétique avec in combinatorial optimization. Parallel Computing 7 : 65-85, 1988.
le recuit simulé et de l’algorithme génétique avec la recherche [5] J.J. Grefenstette, Incorporating problem specific knowledge into genetic
algorithms, L.Davis (Ed.) Genetic Algorithms and Simulated Annealing,
tabou en utilisant la fonction de pondération preuve que cette Morgan Kaufmann Publishers, p.42-60, 1987.
dernière méthode fournit des meilleures solutions comme le [6] Talbi, E.G., S. Cahon & N. Melab, Designing cellular networks using a
montre la figure 8. parallel hybrid metaheuristic, Journal of Computer Communications
30(4): 698-713, 2007.
Concernant l’hybridation séquentielle de l’algorithme
[7] Talbi, E.-G. Metaheuristics: From Design to Implementation, Wiley 2009.
génétique avec le recuit simulé, de l’algorithme génétique avec
la recherche tabou et de l’algorithme génétique avec [8] Talbi E.G., A taxonomy of hybrid metaheuristics. Journal of Heuristics
8(5), pp.541-565, 2002.
l’algorithme génétique leur étude comparative des solutions
[9] D. Duvidier, Etude de l’hybridation des méta-heuristiques, application à
obtenues fournit le classement suivant au niveau de la qualité un problème d’ordonnancement de type jobshop, Thèse de Doctorat,
comme le montre la figure 9 : université du littoral France, décembre 2000.
L’hybridation séquentielle de l’algorithme génétique avec la [10] D.E. Goldberg. Genetic algorithms for search, optimization, and machine
learning. In : Addison-Wesley, MA : (ed), Reading, 1989.
recherche tabou puis l’hybridation séquentielle de l’algorithme
[11] D. Schaffer. Multiple objective optimisation with vector evaluated genetic
génétique avec le recuit simulé enfin ’hybridation séquentielle algorithm. In genetic Algorithm and their Applications : Proceedings of
de l’algorithme génétique avec l’algorithme génétique. the First International Conference on Genetic Algonthm, pages 93–100,
1985.
Cette étude montre que l’hybridation séquentielle de ces
[12] C. M. Fonseca and P. J. Fleming. Genetic algorithm for multiobjective
trois métaheuristiques donnes des meilleures solutions par optimization formulation, discussion and generalization. In Proceedings
rapport à l’hybridation parallèle synchrone des mêmes of the Fifth International Conference on Genetic Algorithms, San Mateo.
métaheuristiques (en utilisant la fonction de pondération) pour California, pages 416–423, 1993.
résoudre le problème traiter dans cet article. [13] Horn, J., Nafpliotis, N., and Goldberg, D. (1994). A niched Pareto genetic
algorithm for multiobjective optmization. In First IEEE Conference on
V. CONCLUSION Evolutionary Computation, IEEE World Congress on Computational
Intelligence, Volume 1.
Le problème d’ordonnancement multi-objectif dans un [14] Zitzler, E. and Thiele, L. (1999). Multiobjective evolutionary algorithms:
atelier flow-shop est un problème extrêmement difficile à A comparative case study and the strength pareto approach. Evolutionary
résoudre et pour améliorer les solutions qui fournissent les Computation, IEEE, 3(4):257–271.
métaheuristiques, nous avons appliqué deux approches [15] Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and
d’hybridation séquentielle et parallèle synchrone (en utilisent la elitist multiobjective genetic algorithm : NSGA-II. Evolutionary
méthode de pondération des fonctions objectives) entre Computation, IEEE Transactions on, 6(2):182–197.
l’algorithme génétique et les métaheuristiques à solution unique [16] H. Jebari, S. Rahali El azzouzi, H. Samadi. Algorithmes évolutionnaires
(la recherche tabou et le recuit simulé). Les résultats obtenus par pour la résolution de problèmes d’ordonnancement multi-objectifs dans
un atelier Flow-Shop. SITA14, 9th International Conference on
la 1er méthode sont nettement meilleurs que ceux obtenus par la Intelligent Systems: Theories and Applications, 07-08 May 2014, Rabat,
2éme méthode. Morocco.
[17] E. G. Negenman, « Local search algorithms for the multiprocessor flow-
Ainsi, l’hybridation séquentielle de l’algorithme génétique shop scheduling problem ». European Journal of Operational Research,
avec la recherche tabou a amélioré la qualité des solutions vol. 128, pp. 147-158, 2001.
obtenues. [18] J. Breit, « A polynomial-time approximation scheme for the two-machine
flowshop scheduling problem with an availability constraint ». Computers
Parmi les perspectives de ce travail est de généraliser cette & Operations Research, vol. 33, pp. 2143–2153, 2006.
démarche pour la résolution de problème d’ordonnancement
[19] R. Ruiz, C. Maroto et J. Alcaraz, « Two new robust genetic algorithms for
multi-objectif sur d’autre type d’atelier de production. the flow-shop scheduling problem ». Omega, vol. 34, pp. 461 – 476, 2006.
D’autres part notre travail peut s’étaler à étudier, à [20] S.M. Johnson, « Optimal two and three stage production schedules with
setup times included ». Naval Research and Logistics Quarterly, vol. 1,
développer, à exploiter et à hybrider d’autres métaheuristiques à 1954.
population de solutions (la méthode de la colonie de fourmis, la
[21] D. G. Dannenbring, « An evaluation of flow-shop sequencing heuristics
recherche par dispersion, l’algorithme à essaim de particules, la ». Management Science, vol. 23, pp. 1174-1182, 1977.
recherche par dispersion, le système immunitaire artificiel [22] M. Nawaz, E.E. Enscore et I. Ham, « A heuristic algorithm for m-
…etc) séquentiellement avec les métaheuristiques à solution machine, n-job flow-shop sequencing problem ». OMEGA, vol. 11, pp.
unique et à comparer leurs résultats pour trouver ceux qui 91 98, 1983.
fournissement les meilleurs solutions. [23] I.H. Osman et C.N. Potts, « Simulated annealing for permutation flow-
shop scheduling ». OMEGA, vol. 17, pp. 551-557, 1989.
Références [24] M. Widmer et A. Hertz, « A new heuristic method for the flow-shop
sequencing problem ». European Journal of Operational Research, vol. 4,
[1] Esquirol P. et Lopez P., L'ordonnancement. Economica, 1999. pp. 186-193.1990.
[2] Souier, M., Métaheuristiques pour la manipulation de routages alternatifs [25] T. Murata, H. Ishibuchi et H. Tanaka, « Multi-objective genetic algorithm
en temps réel dans un Job Shop, Mémoire de Magister,Université Abou and its applications to flow-shop scheduling ». Computers Industrial
Bakr Belkaid, Tlemcen, 2009. Engineering, vol. 30, n° 4, pp. 957-968, 1996.
[3] Günther R. Raidl , A Unified View on Hybrid Metaheuristics, Institute of [26] Pan JC-H, Chen J-S, Chao C-M. Minimizing tardiness in a two-machine
Computer Graphics and Algorithms Vienna University of Technology, flow shop. Computers and Operations Research 2002; 29(7):869–85.
Vienna, Austria, 2006.
[27] Fink A, Vob S. Solving the continuous flow shop scheduling problem by [48] Y. Collette et P. Siarry, « Optimisation Multiobjectif ». Editions Eyrolles,
metaheuristics. European Journal of Operational Research 2003; Paris, 2002.
151(2):400–14. [49] Holland J. H., Genetic algorithms and the optimal allocation of trials,
[28] Bulfin RL, M’Hallah R. Minimizing the weighted number of tardy jobs SIAM Journal on Computing 2, 1973
on a two-machine flow shop. Computers and Operations Research 2003; [50] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and
30(12):1887–900. Machine Learning, Addison-Wesley, Reading, MA, 1989
[29] Blazewicz J, Pesch E, Sterna M,Werner F. A comparison of solution [51] Randy L. Haupt & Sue Ellen Haupt, practical genetic algorithms, 2nd ed.
procedures for two-machine flow shop scheduling with late work John Wiley & Sons, Inc., New Jersey 2004.
criterion. Computers and Industrial Engineering 2005; 49(4):611–24.
[52] D. Duvivier, Ph. Preux, C. Fonlupt, D. Robilliard, E-G. Talbi, The
[30] Choi B-C, Yoon S-H, Chung S-J. Minimizing maximum completion time fitness.function and its impact on Local Search Methods, IEEE Systems,
in a proportionate flow shop with one machine of different speed. Man. and Cybernetics (IEEE SMC'98), pp. 2478-2483, San Diego, USA,
European Journal of Operational Research 2007; 176 (2): 964–74.  1998.
[31] Grabowski J, Pempera J. Some local search algorithms for no-wait flow [53] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimation by Simulated
shop problem with makespan criterion. Computers and Operations Annealing, Science 220 (1983) pp. 671–680
Research 2005; 32(8):2197–212.
[54] Bohachevsky I., Jonhson M. E., Stein M.L., Generalized simulated
[32] Wang J-B, Daniel Ng.CT, Cheng TCE, Li-Li Liu. Minimizing total annealing for function optimization, Technometrics 28 (1986) pp. 209–
completion time in a two machine flow shop with deteriorating jobs. 217
Applied Mathematics and Computation 2006;180(1):185–93.
[55] Dimitris Bertsimas, John Tsitsiklis, Simulated annealing, Statistical
[33] J.C. Ho et Y.L. Chang, « A new heuristic for the n-job, m-machine flow- Science, vol. 8, No. 1 (1993) pp. 10–15
shop problem ». European Journal of Operational Research, vol.52, pp.
194-202, 1991. [56] Glover F., Tabu search—part I, ORSA Journal on Computing, 1(3) (1989)
pp. 190–206
[34] R. Gangadharan et C. Rajendran, « A simulated annealing heuristic for
[57] Glover F., Tabu search—part II, ORSA Journal on Computing, 2(1)
scheduling in a flow-shop with bi-criteria ». 16th International
(1990) pp. 4–32
Conference on Computers Industrial Engineering, pp. 345-348, 1994.
[35] M. Mabed, M. Rahoual, E. Talbi et C. Dhaenens, « Algorithmes [58] Tai-Hsi Wu, Jinn-Yi Yeh, Chin-Chih Chang, A hybrid Tabu Search
génétiques multicritères pour les problèmes de flow-shop ». 3e Algorithm to Cell Formation Problem and its Variants, World Academy
of Science, Engineering and Technology 53 (2009) pp. 1090–1094
Conférence Francophone de Modélisation et SIMulation MOSIM’01 – du
25 au 27 avril 2001 – Troyes. [59] H. Jebari, S. Rahali El azzouzi, H. Samadi. The Hybrid Genetic
Algorithm for Solving Scheduling Problems in a Flexible Production
[36] S. Bertel et J. C. Billaut, « Problème d’ordonnancement multicritère dans
System. International Journal of Computer Applications 110(12):22-29,
un flow-shop hybride avec recirculation ». 3ème Conférence Francophone
January 2015.
de Modélisation et SIMulation, MOSIM’01, 25-27 avril 2001, Troyes.
[37] K. Neumann, C. Schwindt et N. Trautmann, « Scheduling of continuous
and discontinuous material flows with intermediate storage restrictions ».
European Journal of Operational Research, vol. 165, pp. 495–509, 2005.
[38] G. Onwubolu et D. Davendra, « Scheduling flow shops using differential
evolution algorithm ». European Journal of Operational Research, vol.
171, pp. 674–692, 2006.
[39] Toktas B, Azizoglu M, Koksalan S.K. Two-machine flow shop
scheduling with two criteria: maximum earliness and makespan.
European Journal of Operation Research 2004;157(2):286- 95.
[40] Arroyo JEC, Armentano VA. Genetic local search for multi-objective
flowshop scheduling problems. European Journal of Operational
Research 2005; 167 (3): 717–38.
[41] Noorul Haq A, Radha Ramanan T. A bicriterian flow shops scheduling
using artificial neural network. The International Journal of Advanced
Manufacturing Technology 2006; 30(11- 12):1132-8.
[42] Rahimi-Vahed R, Mirghorbani S.M. A multi-objective particle swarm for
a flow shop scheduling problem. Journal of Combinatorial Optimization
2007;13(1):79-102.
[43] Yagmahan B, Yenisey M.M. A multi-objective ant colony system
algorithm for flow shop scheduling problem. Expert Systems with
Applications 2010;37(2):1361–1368.
[44] Shahul Hamid Khan, B., Prabhaharan, G., & Asokan, P. (2007). A grasp
algorithm for m-machine flowshop scheduling problem with bicriteria of
makespan and maximum tardiness. International Journal of Computer
Mathematics, 84(12), 1731–1741.
[45] Arroyo, J. E. C., & de Souza Pereira, A. A. (2010). A GRASP heuristic
for the multi-objective permutation flowshop scheduling problem. The
International Journal of Advanced Manufacturing Technology, 55(5-8),
741–753.
[46] Dubois-Lacoste, J., López-Ibáñez, M., & Stützle, T. (2011). A hybrid
TP+PLS algorithm for bi-objective flow-shop scheduling problems.
Computers & Operations Research, 38(8), 1219–1236.
[47] Ciavotta, M., Minella, G., & Ruiz, R. (2013). Multi-objective sequence
dependent setup times permutation flowshop: A new algorithm and a
comprehensive study. European Journal of Operational Research, 227(2),
301–313.