1 Une approche basée sur les colonies de fourmis pour lordonnancement multiobjectif dun atelier dimpression Unité de Recherche en Automatique et Informatique

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


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)


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


5

Formulation du problèmeFonction coût

21111 ffd i


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


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


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


Minimiser la fonction coût Minimiser la fonction de robustesse Minimiser la fonction de flexibilité

Trois objectifs à optimiser

9

Mesure de Flexibilité: principe


)( 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


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


)( 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


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


Résolution du problème

14

Principaux travaux du domaine


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.


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.


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


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


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


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.


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


23

Formulation des directions


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.


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 :


20 50 70

Temps CPU (min)

2 24 47

NSP 45 55 100

26

Comparaison


- 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


28

Merci pour votre attention


Documents

1 Une approche basée sur les colonies de fourmis pour lordonnancement multiobjectif dun atelier dimpression Unité de Recherche en Automatique et Informatique