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
Fm || 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.
| 
