Upload
willelm-charton
View
111
Download
2
Embed Size (px)
Citation preview
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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