1
Une approche basée sur les colonies de fourmis pour
l’ordonnancement multiobjectif d’un atelier
d’impression
Unité de Recherche en Automatique et Informatique Industrielle
Doctorante : Feïza GHEZAIL
Codirecteurs : Sonia HAJRI-GABOUJ (URAII, INSAT Tunis)
: Henri PIERREVAL (LIMOS, IFMA Clermont Fd)
Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
2
Plan Introduction : présentation du problème Formulation du problème Approche développée
Objectifs considérés Colonies de fourmis Algorithme
Résultats Perspectives
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
3
Présentation de l’atelier d’impression
Imprimer les décors clients
couleurs taille Passage d’un décor à l’autre : changer
les encres et les mandrins (support dépendant de la taille du produit)
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
4
Particularité du problème Problème à une machine avec des temps de setup
dépendants de la séquence (changements d’encre et de support « mandrin ») → Problème NP-difficile
D’où le développement d’une méthode approchée (solution proche de l’optimale en un temps raisonnable)
Objectifs basés sur la pondération entre le nombre de changements d’encre et la somme des retards
Deux perturbations possibles de l’atelier : Pannes de la machine (aléatoires) Non disponibilité de mandrins
Contrainte de production : regroupement des produits par taille
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
5
Formulation du problèmeFonction coût
21111 ffd i
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
nij nombre de couleurs différents entre les commandes i et j;Ci completion time de la commande i;
n nombre de commandes à ordonnancer; di date due de la commande i; α1 et β1 sont des poids donné par le décideur
sinon 0
j commande lat directemen précède i commande la si 1 xij
Selon la classification de Graham, le problème considéré peut être représenté ainsi:
Minimiser le nombre de changements d’encre et la somme des retards
n
i
n
iijijiijijj xspCpxC
1 1
)()1(
6
Formulation du problèmeSous les contraintes
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
Les commandes de même format sont groupées ensemble.
Un groupe (resp. commande ) ne succède qu’à un(e) et un(e) seul(e) groupe (commande).
Un groupe (commande) n’est succédé(e) que par un(e) et un(e) seul(e) groupe (commande).
Respect du nombre de groupes (commandes).
Solutions non cycliques.
7
Système de production non stable
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
Risque de pannes de la machine Trouver un ordonnancement qui ne perde pas
beaucoup de performances en cas de pannes (mesure de robustesse)
Risque d’indisponibilité de mandrins Trouver un ordonnancement qui permette de
fournir une bonne solution de rechange en cas de non disponibilité de mandrin (mesure de flexibilité)
8
Objectifs considérés
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
Minimiser la fonction coût Minimiser la fonction de robustesse Minimiser la fonction de flexibilité
Trois objectifs à optimiser
9
Mesure de Flexibilité: principe
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
)( prsF Mandrin 2
indisponible
J1 J2 J3
(1)
J4 J5
(2)
J6
(3)
J1 J2 J3
(1)
J4 J5
(2)
J6
(3)
Permuter mandrin 2 et 3
Permuter mandrin 2 et 4
Ji
Mandrin (m)
Pré ordonnancement
J1 J2 J3
(1)
J4 J5
(2)
J6
(3)
J7 J8
(4)
J9
J7 J8
(4)
J9
J7 J8
(4)
J9
Mandrin indisponible Au lieu d’arrêter la production, on permute un groupe avec un autre (une seule permutation à la fois est autorisée)
10
Mesure de Flexibilité: formulation
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
Mandrin r indisponible (Nombre de mandrins limité à 10) Évaluer toutes les permutations possibles pour le groupe utilisant le mandrin r
avec ceux qui ne sont pas encore exécutés (utilisant le mandrin p) et mesurer leurs performances
Choisir la solution ayant les meilleures performances
))((max)( *
,...,11 r
nrsFsFsR
gr
F(s) fonction coût de l’ordonnancement s
F(sr*) fonction coût de la meilleure solution permutée
Mesure de flexibilité
11
Mesure de Robustesse: principe
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
)( prsF
J1 J2 J3 J4M
Ordonnancement initial
J1 J2 J3 J4M
Ordonnancement réel
Changement des dates de début des commandes restantes (exécutées après l’arrivée de la panne)
12
Mesure de Robustesse: formulation
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
Selon un échantillon de pannes variées Changer les dates de début des commandes restantes (exécutées
après l’arrivée de la panne) Évaluer la performance de chaque solution s’ modifiée par la panne
Fb(s’) Répliquer des scénarios de pannes Nbrep fois.
rep
Nb
bb
Nb
sF
sFsR
rep
1
2
)'(
)(
Mesure de robustesse
Fb(s’) fonction de performance de l’ordonnancement s’ perturbé par une panne
Nbrep nombre de réplications des pannes
13
Résoudre un problème d’ordonnancement multi objectif NP-diffcile avec des temps setup dépendant de la séquence :
Problème particulier d’impression avec différentes contraintes (exemple contrainte de groupe)3 objectifs à optimiserRécupérer un ensemble de solutions
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
Résolution du problème
14
Principaux travaux du domaine
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
Auteurs Référence
Gravel, M., Gagné, C., and Price, W. L.(2002)
Algorithme d’optimisation par colonies de fourmis avec matrices de visibilité multiples pour la résolution d’un problème d’ordonnancement industriel, INFOR, 40(3), 259-276
McMullen, P.R. (2001) An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives, Artificial Intelligence in Engineering, 15, 309-317
Gajpal, Y., and Rajendran, C. (2006) An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops, International Journal of Production Economics 101, pp 259-272
Fayad, C., Petrovic, S. (2005) A Genetic Algorithm for Real-World Fuzzy Job Shop Scheduling, http://www.ascap.cs.nott.ac.uk/publications/pdf/cxf_iea05.pdf
Johtela, T., Smed, J., Jhonson, M., Nevalainen, O. (1998)
Single Machine Scheduling with Fuzzy Multiple Criteria Optimization in Electronic Assembly, http://www2.cs.utu.fi/staff/jouni.smed/papers/toolmet98.pdf
Musselman, K.J., (2001) Complex scheduling of a printing process, Computers and industrial Engineering, 39, pp 273-291
Orcun, S., Discioglu, A, Altinel, K, Hortacsu, O. (1997)
Scheduling Of Batch Processes: An Industrial Application In Paint Industry, Computers and chemical Engineering, 21(1), pp 673-678
15
Colonies de fourmisTrouver un chemin entre les commandes à ordonnancer tout en optimisant des critères de performances
Visibilité selon les critères de performances : Les fourmis « voient » la distance en terme de objectifs de performance entre les commandes
Désirabilité : Attraction d’un chemin selon la quantité de phéromone présente (ij).
Utilisation d’une liste tabou relative à chaque fourmis pour éviter de re-sélectionner une commande déjà exécutée.
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
16
?
Illustration des fourmisOn dispose de 5 groupes Gi (i=1, .. 5) composés relativement des commandes (i1, … in) où n = respectivement 4, 2, 3, 1 et 3:
G1(11, 12, 13, 14); G2(21, 22); G3(31, 32, 33); G4(41); G5(51, 52, 53)
G4
G3
G2G1
G5
Construction progressive des solutions:?
?
17
Approche proposée Construction progressive des solutions en intégrant les
contraintes du problème notamment la contrainte de groupe
Prise en compte du multiobjectif : Proposition de mesures de visibilité Développement d’une stratégie de mise à jour de la
phéromone afin de prendre en compte la robustesse et la flexibilité en plus des performances
Utilisation d’un ensemble Pareto pour archiver les solutions non dominées.
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
18
Gestion des groupesAfin de prendre en compte la contrainte de regrouper les commandes ayant le même format, ces variantes sont considérées :Utilisation d’une phéromone entre les groupes : (grgp) entre les groupes utilisant les mandrin r et pUtilisation d’une liste tabou tabouMk des groupes déjà sélectionnés relatifs à chaque fourmis k.Utilisation d’une visibilité entre groupes pour la sélection du prochain groupe à exécuter et ce selon les critères de performance
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
19
Construction des solutions (groupes)Construction progressive selon la désirabilité et la visibilitéVisibilité : on utilise 2 mesures de visibilité entre les groupes
Une mesure concernant la distance entre la dernière commande exécutée dans le groupe courant et la première du prochain groupe ( ) du nombre de changement d’encres
Une mesure selon la somme des marges absolues des commandes du groupe afin de prendre en compte la somme des retards
2
minmax
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
pG
sinon G
qq si 11
.t max arg
p
0gg
1
tabuMgrr
kp
pp
pr
gggg ngmg
sinon 0
tabuMg si 11
.t
11.t
kp
gg
1
gg
1
rr
rr
kl tt
tr
pp
pr
tabuMg gggg
gggg
ngmg
ngmg
gp =
kgg pr
p = Où Gp est donné selon la probabilité suivante:
20
Construction des solutions (commandes)
Construction progressive selon la désirabilité et la visibilitéVisibilité : selon les 2 objectifs de performance on utilise 2 mesures de
visibilité entre les commandes Une mesure concernant le nombre de changements d’encre Une mesure selon les marges absolues afin de prendre en compte la
somme des retards
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
Où J est donné selon la probabilité suivante
j =
pijk =
Dorigo M.
21
Évaluation des solutions
Fonction d’amélioration : 2-opt. Une fois un ensemble de solutions est obtenu, la fonction d’amélioration tente d’améliorer les performances par des permutations.
Pareto : archivage des solutions non dominées selon : performance, robustesse et flexibilité pour que le décideur puisse avoir un ensemble diversifié de solutions pour faire son choix.
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
22
Mise à jour de la phéromone Pour chaque solution obtenue, on l’évalue selon les 3 objectifs considérés et on
en sélectionne les meilleures pour la mise à jour globale de la phéromone.
Les 3 objectifs sont pris en compte selon des vecteurs de poids définissant des directions dans l’espace de recherche des solutions obtenues.
→ Cette considération est possible grâce au nombre réduit d’objectifs.
Selon des directions de recherche, on détermine les meilleurs solutions trouvées à chaque cycle des colonies de fourmis et on renforce la phéromone sur ces chemins (entre les commandes et entre les groupes de commandes)
Quadrillage de la surface de Pareto par des directions de recherche
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
23
Formulation des directions
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
w différents vecteurs
w différentes fonctions d’évaluation
Tel que:
=
Renforcement de w chemins
24
Algorithme1. Initialiser la phéromone et l’ensemble Pareto à l’ensemble vide2. - Pour chaque fourmis, déterminer les mesures de visibilités associées à
chaque objectif et ainsi sélectionner la prochaine commande à exécuter selon la visibilité et le taux de phéromone- Mise à jour locale de la phéromone Jusqu’à ce que toutes les commandes sont exécutées.
3. Utiliser une fonction d’amélioration pour toutes les solutions obtenues4. Évaluer les solutions obtenues selon les différents objectifs et mettre à jour
l’ensemble Pareto avec les solutions non dominées
5. Identifier les meilleurs solutions selon différentes directions de recherche6. Mettre à jour la phéromone selon une mise à jour globale en considérant les
meilleures solutions obtenues dans l’étape 5
Itérer depuis l’étape 2 jusqu’à ce qu’un nombre d’itérations max est atteint.
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
25
Résultats Nous obtenons un ensemble de solutions sur le
front Pareto: Tests sur des problèmes avec 20, 50 et 70 jobs En moyenne :
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
20 50 70
Temps CPU (min)
2 24 47
NSP 45 55 100
26
Comparaison
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
- 2%PERTE
+ 6%GAIN
+ 4%GAIN
Solution avec meilleurs performancesMeilleures caractéristiques du Pareto
1729.5
1757.5 1850.391959.89
2231.742312.71
Performances
En comparant les meilleurs caractéristiques des solutions trouvées dans l’ensemble Pareto avec la solution le plus performante obtenue en utilisant le même algorithme, on trouve :
En cas de non disponibilité d’outil
En cas de pannePerformances initiales
27
Proposer une approche d’évaluation quantitative des résultats plus développée.
Évaluer la qualité obtenue à l’aide de bornes inf pour les objectifs considérés
Proposer une méthode plus efficace pour résoudre le problème
Améliorer la recherche multiobjectif : Fonction d’amélioration multi objective Améliorer les mesures de visibilité afin d’améliorer la diversité
des solutions. Considérer de nouvelles mesures pour la prise en
compte de la robustesse et de la flexibilité.
Perspectives
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris
28
Merci pour votre attention
GDR-MACS journées des 8 , 9 et 10 mars 2006 à Paris