1Page de garde présentation

Obtention des cycles de production pour les cellules robotisées

Agustin Pecorari

Fabien Mangione

Bernard Penz

2

Ateliers de traitement de surfaces

• Galvanoplastie

• Microprocesseurs...

rail

porteur

Cuve 0 (de chargement)

Cuve 1 Cuve 2 Cuve 3 Cuve m-1 Cuve m Cuve m+1 (de déchargement)

3

Problèmes spécifiques au HSP

• Marges sur les durées de trempe– borne minimum: temps nécessaire au traitement

– borne maximum: éviter les dégradations éventuelles et les coûts élevés

• Disponibilité du robot

• Disponibilité des cuves

4Etat de l’art

• Hoist Scheduling Problem

– Heuristiques: [Yih 94]

– Branch and Bound: [Ng 96]

– PLC: [Baptiste et al 96]

• Flow Shop robotisé

– Complexité: [Crama et van de Klundert 96]

– Cas particuliers: [Finke et Brauner 96], [Agnetis 00]

5Notations

• m nombre de cuves

• temps de déplacement de la cuve i à i+1

• li temps de trempe minimal dans la cuve i

• ui temps de trempe maximal dans la cuve i

• pi temps de trempe effectif dans la cuve i

• i ou Ai activité i

Cuve i Cuve i+1

6Objectif

• Comment obtenir l'ensemble des cycles de production.

• Quels sont les cycles de production optimaux?

7Cycles de production

• Définition d’un k-cycle:

Cycle dont toutes les activités sont répétées exactement k fois

• Exemple : Différence entre cycle 0213, 2031 et 02132031.

– 0 2 1 3 0 2 1 3

– 2 0 3 1 2 0 3 1

8δ

0

- 0 2 1 3 2 0 3 1 0 2

4δ 4δ

8Représentation

Mouvement en charge (activité 1)Mouvements à vide

Temps de process minimal

9

Calcul du temps de cycle

• Décomposer en deux parties :

– Temps de déplacement du robot Algorithme polynomial : O(k(m+1)) :

Pour chaque activité (Ai) :

Si activité suivante (Aj) supérieure : tps = (j-i)δ

Si activité suivante (Aj) inférieure : tps = (i-j+2)δ

10

Calcul du temps de cycle

– Temps d'attente

– t1=max(0;p

2-4δ)

– t2=max(0;p

1-4δ-t

1)

– t3=max(0;p

3-4δ-t

2)

t1

t2

t3 t

1t4

t5

t6

11

Programme linéaire obtenu

t1=max(0;p

2-4δ)

t2=max(0;p

1-4δ-t

1)

t3=max(0;p

3-4δ-t

2)

t4=max(0;p

2-4δ-t

3)

t5=max(0;p

3-6δ)

t6=max(0;p

1-6δ-t

5)

t1 ≥ p

2-4δ

t2 + t

1 ≥ p

1- 4δ

t3 + t

2 ≥ p

3- 4δ

t4 + t

3 ≥ p

2- 4δ

t5 ≥ p

3- 4δ

t6 + t

5 ≥ p

1- 6δ

– min Σti

12

Problèmes

• Besoin de plusieurs cycles avant de revenir à la position initiale

• Période transitoire

• Pas de solution

t1

t2

t3 t

7t4

t5

t6

13Obtention des cycles

• Comment obtenir les cycles réalisables

• Connaissance du nombre de cycles pour k et m fixés (Brauner)

14Graphe d’état

0,1,01,1,1

1,1,0

1,0,1

0,1,1

1,0,0

0,0,1

0,0,0

A2

A0

A3

A3

A3A3

A2

A0

A0A0

A1

A1

Cuve 0 Cuve 1 Cuve 2 Cuve 3 Cuve 4

15Line-Graph

0,1,01,1,1

1,1,0

1,0,1

0,1,1

1,0,0

0,0,1

0,0,0

A2

A0

A3A3

A3A3

A2A0

A0A0

A1

A1

A3

A0

A2

A0

A0 A1

A0

A3

A3A3 A2

A1

16

Intérêts du Line Graph

• A tout cycle dans le line-graph équivaut un cycle de production réalisable et inversement

A3

A0

A2

A0

A0 A1

A0

A3

A3A3 A2

A1

Cycle A0, A2, A1, A3

17

Pourquoi le line-graph

• Pourquoi utiliser un line-graph plutôt que le graphe d’état ?

– 0213, 2031 et 02132031.

A0 A1

A0

A0

A3

A3 A2

A1

A2 A3

A3

A0

0,1,01,1,1

1,1,0

1,0,1

0,1,1

1,0,0

0,0,1

0,0,0

A2

A0

A3A3

A3

A2

A0A0

A1

A1

18Algorithmes

• Recherche dans une arborescence avec backtrack

– Algorithme fortement exponentiel

• Suppression des sommets inaccessibles

1001

1000

0101

1100

0011

1111 00000110

1010

1101

1110

1011

0111

0100

0010

0001

19Amélioration des algorithmes

• Algorithme supprimant les arcs déjà étudiés

• Algorithme avec distance de retour

– k-cycles : k(m+1) activités

– Calcul des distances retour

20Résultats

• Nombre de cycles obtenus

2,9 1073,56 . 107

3,56 . 107

1,18 . 108

1,18 . 1085

1400

4952282

Arcs étudiés

80046004200

Tps

calcul

394049521144011440426284040322222

Nombre optimal

Distances

retour

Suppression

sommets

Algo brut

m

21Conclusions et perspectives

• Calcul des temps de cycles par programmation linéaire– Impossibilité de faire ce calcul avant d’avoir construit tout

le cycle

• Méthode permettant d’obtenir les cycles de production– Combinaison des deux travaux : cycle optimal– Algorithmes exponentiels

• Ajout de contraintes sur les temps de process– Suppression d’arcs dans le graphe