Modélisation du problème de planification des tâches de réglage de machines lors de changements de série Cédric Pessan 1,2, Jean-Louis Bouquard 1 et Emmanuel

Modélisation du problème de planification des tâches de réglage de machines lors de changements

de série

Cédric Pessan1,2, Jean-Louis Bouquard1 et Emmanuel Néron1

1 Laboratoire d’informatique (EA 2101) Université François-Rabelais de Tours

64 avenue Jean Portalis, 37200 Tours

2 SKF France SAIndustrial division / MDGBB* Factory

204 boulevard Charles de Gaulles 37540 Saint-Cyr-sur-Loire*Roulements à bille moyens à gorge profonde

Modélisation du problème de planification des tâchesde réglage de machines lors de changements de série

C. Pessan, J-L. Bouquard & E. Néron

GdR MACS STP - Bermudes 2

Plan

• Présentation du problème

– Contexte de l’étude

– Modèle et expression de la fonction de coût

• Méthodes de résolution

– Algorithme de descente locale

– Algorithme génétique

– Algorithme hybride

• Conclusion et perspectives




Contexte de l’etude

• le site SKF DGBB: – production de roulements à billes moyen à gorge

profonde– plusieurs références – production par grandes séries– le passage d’une référence de type A a une

référence de type B nécessite le réglage de toutes les machines de la ligne de production

• ex : changement des outils, mise au nouveau diamètre etc.• assurées par des opérateurs ayant des aptitudes différentes

selon les machines a régler => compétences ; indisponibilité




Exemple de chaîne de production

M1

M5

M2 M3

M6

M4

354 pièces / heure

473 pièces / heure

513 pièces / heure

408 pièces / heure

298 pièces / heure571 pièces / heure

ri qi

Distances en temps du début et de la fin de la ligne




Qu’est-ce qu’un changement de série ?

• La minimisation du temps perdu est vital à la flexibilité de la production– plus que le temps c’est la perte de production qui

est cruciale

• Objectif : Réduire la perte de production lors des changements de série– indispensable pour augmenter la réactivité de la

chaîne de production




Optimisation des changements de série

• La méthode SMED [Shingo, 1985] :– Amélioration de la technique de réglage– Principale méthode explorée par les industriels

depuis 20 ans– La méthode ne prend pas en compte les

contraintes humaines et l'optimisation sur une ligne complète

• Peut être compléter par un ordonnancement efficace des opérations de changements d’outils sur les machines




Optimisation des changements de série

• [Goubergen, 2004] « A quantitative approach for Set-Up reduction of machine lines »– Modélisation par un RCPSP d'une ligne de

production complète– Pas de compétences– Pas de problèmes d'indisponibilité– Ne traite que les lignes série




Modèle (1/3)

• Données des tâches – n opérations (1 par machine à régler)

• de 1 à n1 : machines prioritaires – indispensable a la reprise de la production – les plus efficaces– contraintes « métier » imposées

• de n1+1 à n : machines non prioritaires

– ri : dates de début au plus tôt– qi : temps de latence




Modèle (2/3)

• Données des opérateurs (ressources)– pi,m : temps de réglage pour un couple (machine /

opérateur) • modélise la compétence d’un opérateur pour un type de

machine

• Moyenne sur les X derniers mois des temps de réglage pour chaque machine et chaque régleur

• Si l’opérateur i n’a pas la compétence m : pi,m = +∞

– A(m,t) disponibilité de l’opérateur m à l’instant t




Modèle (3/3)

• les contraintes– Pas de préemption– Respect des disponibilités des ressources– Un seul réglage à la fois par opérateur– Un seul opérateur par machine– Respect de la date de début au plus tôt

R, MPM |ri, qi, indispo | f(Ci)




Exemple 1:

Machine 1

Machine 2

Machine 3

Machine 4

Opérateur 1

Opérateur 2

t

t

t

t

t

t

r1

r2

r3

r4

t

M4

M3

q1

q2

q3

q4

Ancienne sérieInterruption de production Nouvelle série

M1

M2

M1 M2 M3 M4

Indisponible




Exemple 2 : ligne série-parallèle

M1

M2

M3

M4

M5

M6

354 pièces / heure

473 pièces / heure

513 pièces / heure

408 pièces / heure

298 pièces / heure

571 pièces / heure




238

Exemple 2 :

t

t

t

t

t

t

Machine 1

Machine 2

Machine 3

Machine 4

Machine 5

Machine 6

354 p/h473 p/h513 p/h

408 p/h

238 p/h

571 p/h

513

r1

r3

354

M1

M2M3

M4

M5M6

Op1q1

Op1 q2

Op2 q3

Op1 q4

Op2 q5

Op2 q6r6




Formule complète du critère

• Expression valable pour tout graphe série / parallèle

• reprendre la production le plus vite possible sur les machines prioritaires

• assurer une montée en production rapide sur les machines en double

• une fois les dates de début des opérations fixées : O(n²)




Problème à affectation fixée

• Si l’on connaît les tâches affectées à un opérateur– Si le graphe est une ligne simple

• On doit résoudre le problème 1|ri,qi|Cmax• Ordre des ri croissants est égal à l’ordre des qi décroissants• O(n) en triant les tâches par ri croissants

– Dans le cadre général (liées à contraintes industrielles)• Machines prioritaires dans l’ordre de ri en premier• Machines en double dans l’ordre où elles éliminent les goulets

On se ramène a un problème d’affectation : quelles tâches sur quel opérateur




Plan

• Présentation du problème– Contexte de l’étude– Modèle et expression de la fonction de coût

• Méthodes de résolution– Algorithme de descente locale– Algorithme génétique– Algorithme hybride





Méthode de descente locale

• idée : changer l’affectation des opérations influant directement sur l’évaluation du critère de perte de production

• Le k-voisinage que nous utilisons, fournit des chaînes d’au plus k réaffectations de tâches




Exemple de voisin (3-voisinage)

Opérateur 1

Tâche 1

Opérateur 2

Tâche 2

Opérateur 3

Tâche 3Opérateur : Compétences:

Opérateur 1 Tâche 1, Tâche 3

Opérateur 2 Tâche 2, Tâche 1

Opérateur 3 Tâche 3, Tâche 2, Tâche 1




Modélisation par un graphe du k-voisinage

• Graphe biparti :• Sommets opérateurs

• Sommets tâches

• Arc opérateurs->tâches : enlever une tâche à un opérateur

• Arc tâches->opérateurs : ajouter une tâche à un opérateur

• Deux sommets supplémentaires S et P tous deux reliés à tous les opérateurs

• But: Trouver un chemin de S à P de longueur 2k+2 améliorant la solution




Exemple de construction de graphe

Opérateur: Compétences

O1 T1,T3

O2 T2,T5,T6

O3 T1,T4,T5,T6,T7

O4 T7

O4O3

O2

O1 T1 T3

T2 T5 T6

T4

T7

O1

O2

O3

O4

S

P

T1

T2

T3

T4

T5

T6

T7

Réaffecter T1 à O3 =Parcourir {S,O1,T1,O3,P}




Points de départs intéressants

• On cherche à optimiser les tâches critiques :– dernière machine prioritaire i– machines non prioritaires se terminant après i

• Les chemins intéressants commencent par un opérateur qui a une tâche critique




Cycles

• Détection des cycles qui passent deux fois par une tâche

• Détection des cycles de longueur 2 (réaffectation d’une tâche sur elle-même)

• Si un de ces deux types de cycle est détecté => on n’évalue pas




Éliminer les chemins équivalents

• Construction d’une clé pour chaque chemin (indices des jobs parcourus par ordre croissant)

• Clés stockées dans une structure avec table de hachage :– Si la clé est déjà présente, on n’évalue pas le

chemin, sinon on ajoute la clé

• L’ajout et la recherche se font en O(log(n))




Borne inférieure

• On regarde après α sommets où en sont les tâches critiques et on estime de combien on pourra améliorer leur date de fin au maximum– Permet d’éliminer plusieurs chemins d’un coup




Amélioration d’une tâche critique ?• Avant d’évaluer, on vérifie en construisant le

scénario que l’ordonnancement est réalisable et qu’au moins une des tâches critiques se termine plus tôt




Résultats expérimentaux

• 2 jeux de tests :– 1 jeu contenant 15 instances choisies pour

représenter un panel relativement complet : des instances faciles, difficiles, atteignant les limites rencontrées dans la réalité en terme de disponibilité, compétences…

– 1 jeu contenant 120 instances industrielles réelles

• On mesure la performance de chaque algorithme en calculant le % de déviation par rapport à la meilleure solution connue.





• les techniques de réduction du voisinage sont efficaces :– Sur un exemple, on passe de 1h30 initialement à

30s pour une profondeur de recherche de 4 réaffectation

• Testé en l’appliquant sur la solution trouvée par l’algorithme ECT (Earliest completion time)

• Utilisation des k-voisinage avec k compris entre 3 et 5.





ECT ECT + 3-voisinage

ECT + 4-voisinage

ECT + 5-voisinage

Jeu 1 (15 instances)

14.52% 5.96% 3.91% 3.25%

Jeu 2 (120 instances)

32.6% 18% 15.9% 15.5%




Plan







Codage des solutions

• Rappel : on cherche une affectation (à affectation fixée, le séquencement des tâche est connu)

• Méthode de codage :– Un tableau d’entiers– 1 case par tâche– Chaque case contient le numéro de l’opérateur qui exécute

la tâche

• Exemple :– [4 2 4 2 3 1 4 3 1]– Le job 1 est affecté à l’opérateur 4, – Le job 2 est affecté à l’opérateur 2…




Exemple de croisement

• Chromosome 1 :• Chromosome 2 :

• Fils 1 :• Fils 2 :

i1 i2

4 2

4 2 3 14 3 11 32 4 1 31 2 4

4 2

2 4 1 34 3 1

1 3 1 2 44 2 3 1




Opérateur de mutation

• Choix d’un chromosome• Tirage aléatoire d’un gène• On affecte le job à un opérateur différent du

précédent• Exemple :

[4 2 4 2 3 1 4 3 1]=> [4 2 1 2 3 1 4 3 1]

gène choisi gène modifié




Critère pour les individus non valides• Des solutions ne respectant pas les

indisponibilité des personnes peuvent être générées

• fonction de coût pénalisant les solution non valides– On maximise le nombre de pièces produites pour les

individus valides– On minimise la somme des jobs hors périodes de

disponibilité pour les individus non valides (qui violent les contraintes de disponibilité)

– Ce qui revient à maximiser : -∑(temps_hors_dispo)




Résultats expérimentaux (1/3)

• Paramètres de l’algorithme génétique « standard »– déterminés expérimentalement – Taille de la population : 50 individus– Probabilité de mutation : 10%

• Mesure de la performance à 15s, 30s, 60s, 120s.• L’algorithme est testé 10 fois sur chaque

instance pour estimer la moyenne sur les résultats.




Résultats expérimentaux (2/3)

• plusieurs variantes de l’algorithme génétique – POP100 : population de 100 individus

– MUT35 : probabilité de mutation de 35%

– RENF : mécanismes de diversification • s’il n’y a pas d’améliorations : augmentation de la

probabilité de mutation et du nombre d’individus générés par itération

– BRASSAGE : si les mécanismes de diversification n’ont pas d’effet, on régénère aléatoirement tous les individus sauf le meilleur.




Résultats expérimentaux (jeu 1)

15s 30s 60s 120s

Normal 23,85% 20% 14,69% 10,48%

POP100 24,78% 20,92% 16,49% 11,92%

MUT35 15,06% 10,63% 8,03% 6,02%

RENF 13,39% 9,03% 6,93% 4,58%

BRASSAGE

14,62% 9,68% 5,98% 4,23%




Résultats expérimentaux (jeu 2)

15s 30s 60s 120s

BRASSAGE

9,35% 6,5% 4,3% 2,4%




Plan







Algorithme hybride

• Combiner l’efficacité de l’algorithme génétique génétique et de la descente locale

• On peut utiliser la descente locale:– À chaque fois que l’algorithme génétique améliore

la meilleure solution : – Sur un individu aléatoirement avec

éventuellement une plus grand probabilité sur les meilleurs individus

Opérateur d’intensification





• plusieurs techniques d’hybridation– Intens : utilisation de la descente locale (2 ou 3-

voisinage) aléatoirement avec une probabilité de 2%

– Intens_roul : une plus grande probabilité d’intensification pour les meilleurs individus

– Intens_renf : utilisation de la descente locale que si l’algorithme génétique n’améliore plus

– Intens5 : probabilité d’intensification de 5%




Resultats experimentaux (jeu 1)

15s 30s 60s 120s

Intens 7,04% 5,1% 3,04% 1,57%

Intens_roul

6,46% 5,13% 3,59% 2,15%

Intens_renf

9,27% 7,12% 5,49% 3,12%

Intens5 8,73% 5,44% 3,76% 2,88%

BRASSAGE (algo

génétique sans intensification)

14,62% 9,68% 5,98% 4,23%




Resultats experimentaux (jeu 2)

15s 30s 60s 120s

Intens 6,72% 4,5% 2,7% 1,2%

BRASSAGE (algo

génétique sans

intensification)

9,35% 6,5% 4,3% 2,4%




Plan







Conclusion

• Méthode efficace – en production sur site : gain de production sur un

an

• Perspective – évaluation de la robustesse des solutions fournies

(simulation)– critère d’entraînement : les opérateurs doivent

entretenir les compétences acquises en réglant périodiquement les machines

Documents

Modélisation du problème de planification des tâches de réglage de machines lors de changements de série Cédric Pessan 1,2, Jean-Louis Bouquard 1 et Emmanuel