21
Algorithme Génétique & Fouille de Données pour l’ordonnancement réactif d’un atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni Noureddine Lab. D’Automatique de Besançon, GROUPE de travail BERMUDES

Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

Embed Size (px)

Citation preview

Page 1: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

Algorithme Génétique & Fouille de Données

pour l’ordonnancement réactif d’un atelier

de type Job Shop

Harrath Youssef

Chebel-Morello Brigitte & Zerhouni Noureddine

Lab. D’Automatique de Besançon,École Nationale Supérieure de Mécanique et de Microtechnique

Besançon – France

GROUPE de travail BERMUDES

Page 2: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

2

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Plan

1. Problème étudié : Job Shop

1.1. Données et contraintes

1.2. État de l’art du Job Shop

2. Résolution approchée

2.1. Algorithmes Génétiques (AG) et Job Shop

2.2. Résultats expérimentaux

3. Caractérisation d’ordonnancement : Fouille de Données

3.1. Passage d’un ordre à un autre : Arbre de décision

3.2. Apprentissage à partir d’exemples

4. Conclusion & perspectives

Page 3: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

3

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Problème étudié

Ordonnancement de production de type job

shop,

Problème généralisé

Données statiques,

Pas de préemption,

Pas de parallélisme.

Optimisation mono critère : Cmax,

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 4: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

4

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Méthode proposée

Phase I : Résolution

Phase II : Fouille de Données

Job ShopJob Shop

Algorithme Génétique

Algorithme Génétique

Population de bonnes solutions Population de

bonnes solutions

Arbre de décision

Arbre de décision

Passage d’un ordre à un autre (Réactif)

Passage d’un ordre à un autre (Réactif)

Méthodes d’induction

Méthodes d’induction

Modélisation d'ordonnancement

Modélisation d'ordonnancement

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 5: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

5

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Job Shop : état de l’art

Job Shop : problème NP-Complet Résolution Optimale : difficile Instance 10x10 (Muth & Thomson 1963) n’est

totalement résolue qu’en 1986 (Carlier & Pinson)

Méthodes approchées Recherche locale (Shifting Botteleneck Procedure :

Adams, Balas et Zawak 1988) Branch and Bound (Carlier & Pinson 1989) Algorithmes génétiques

F. D. Croce (Codage % aux machines) Yamada & Nakano (Codage binaire)

Koonce D.A (Codage % job)

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 6: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

6

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Algo. Génétique : principes de base

POPULATION(Chromosomes)

POPULATION(Chromosomes)

EVALUATION(fitness)

EVALUATION(fitness)

OPERATEURSGENETIQUES

OPERATEURSGENETIQUES

Manipulation

Nouvelle génération

SELECTION(groupement)

SELECTION(groupement)

Parents

Reproduction

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 7: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

7

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

codageC

odage

indire

ct

Codage

dire

ct

Type de codage

Caractéristiques

Codage des opérations

- Tous les chromosomes sont valides,- Solutions redondantes.

Codage des machines

Chromosome non valide modification

Codage des jobs

Exploration incomplète de l’espace de solutions

Codage basé sur des listes

de préférences

- Chromosome = liste de préférences- Tous les chromosomes sont valides

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 8: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

8

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Algo. Génétique : opérateurs utilisés

Population initiale

Génération aléatoire

Génération aléatoire

Utilisation des heuristiques

Utilisation des heuristiques

Duplication et évaluation

Duplication et évaluation

Sélection

Sélection aléatoire (Goldberg)Sélection aléatoire (Goldberg) Sélection des p meilleurs individus

Sélection des p meilleurs individus

Génération aléatoire

Génération aléatoire

Sélection des p meilleurs individus

Sélection des p meilleurs individus

Sélection aléatoire (Goldberg)Sélection aléatoire (Goldberg)

Chromosome : (Job,Opération)

Job Shop : 3 Jobs et 3 machines

2 1 3 3 2 1 3 21

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 9: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

9

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Algo. Génétique : opérateurs utilisés

Fonction d’évaluation

max( ) ( )F x CM C x

Mutation

Opérateur de décalage

Opérateur de décalage

Échange réciproque Échange réciproque Opérateur d’insertion Opérateur d’insertion

Croisement Croisement d’ordre

minimal Croisement d’ordre

minimal Croisement

Cyclique Croisement

CycliqueCroisement à ordre

uniforme Croisement à ordre

uniforme Croisement d’ordre

minimal Croisement d’ordre

minimal

Opérateur de décalage

Opérateur de décalage

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 10: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

10

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Résultats expérimentaux

Un Un Job Shop Benchmark 6x6 (Muth & Thomson,

1963),

L’AG est exécuté 1000 fois,

92.7 % des 1000 chromosomes sont optimaux,

Dont 106 ne sont pas redondants,

Durée d’exécution : 2 min

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 11: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

11

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

À partir des 106 individus (séquences), nous avons

déterminé toutes les séquences possibles

(ordonnancements effectifs) : 22 en total

465415246333M6

166536455323M5

562614446232M4

664351221131M3

351352614121M2

552564344212M1

OrdresMachines

Résultats expérimentaux

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 12: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

12

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Fouille de Données

Acquisition

Données Connaissances

Pré-traitement Post-traitementFouille de données

Recherche des structures sous

jacentes

Création de modèles explicatifs/prédictifs

Fouille de données

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 13: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

13

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Caractérisation

Pour chaque machine, on a déterminé les différents ordres

possibles

L’ordre le plus fréquent est considéré comme l’ordre de

base Machines

Ordre 1 Ordre 2 Ordre 3 Ordre 4

M1 19 2 1 -

M2 9 5 4 4

M3 12 10 - -

M4 22 - - -

M5 18 3 1 -

M6 12 10 - -

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 14: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

14

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

OrdresMachines

562614446232M4

55

55

55

25

25

25

64

64

64

34

34

12

42

12

34

12

42

42

M1

Les ordres des machines M1 et M4

Caractérisation

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 15: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

15

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Les 22 séquences sont étudiées à fin de générer des

règles de transition d’un ordre vers un autre pour une

machine donnée,

Des variables caractérisant la transition des ordres ont été

déterminées,

Les règles de décision sont ensuite transformées sous

forme d’arbre permettant à partir des variables et des

ordres de base de chaque machine de générer les 22

séquences précédentes,

Caractérisation

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 16: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

16

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Arbre de décision résultant de l’étude précédente

Var1

O1 O2 . . . O22

.

.

.

M6Var5

(2,5)

321

(3,5) (2,5)(2,5)

111

Var2 Var2Var2

M2

M1

Var5

Arbre de décision

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 17: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

17

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Méthode d'apprentissage à partir d'exemples

y1 y2 . . . yp classew1 a b c 1w2 b c a 2...

wn c a a 4

Attributs (Caractéristiques)

Exem

ple

s d’a

ppre

ntissa

ge

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Logiciel Utilisé : C45 & See5

Page 18: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

18

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Transformation de la population en exemples d'apprentissage

La partie supervisée : les classes les positions des opérations sur les machines,

Les exemples d’apprentissage : les opérations du benchmark étudié,

Les attributs caractérisant :

Durées opératoires,

Charge machine,

Position de l’opération dans le job,

Temps restant du job,

. . .

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 19: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

19

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Modélisation

- Nous cherchons des règles de décision permettant de déduire P pour chaque opération ;

- Les règles se basent sur les caractéristiques des opérations telles que : Temps opératoire, Position dans le Job et le Temps Restant.

Si (Opération = x) & (Temps Opératoire(x) = long) & (Position Job(x) = première) & (Temps Restant(x) = grand) Alors P = 0

Le problème est formulé comme suit :

Chaque opération peut avoir 6 positions possibles sur sa machine

P = (0,1,2,3,4,5).

Chaque opération peut avoir 6 positions possibles sur sa machine

P = (0,1,2,3,4,5).

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 20: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

20

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Conclusion

Une étude du problème de Job Shop à été réalisée en

proposant une nouvelle approche de résolution,

La méthode proposée se base sur les Algorithmes

génétiques et la Fouille de Données,

Un arbre de décision a permis la transition d’un ordre

à un autre,

Une modélisation à l’aide des techniques

d’apprentissage à partir d’exemples a été proposée.

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Page 21: Algorithme Génétique & Fouille de Données pour lordonnancement réactif dun atelier de type Job Shop Harrath Youssef Chebel-Morello Brigitte & Zerhouni

21

Bermudes - Paris le, 06 juin 2002Bermudes - Paris le, 06 juin 2002

Perspectives

Etudier des job shop dynamiques,

Optimisation multicritère,

Méta heuristique pour résoudre le job shop,

Une autre manière de caractérisation (plusieurs

heuristiques),

Prise en compte de la maintenance.

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives

Plan

1.Job Shop1.1. Contraintes

1.2. État de l’art

2.Résolution

2.1.AG & Job Shop

2.2. Résultats

3.F de Données

3.1Arbre de décision

3.1 Apprentissage

3.Conclusion & perspectives