Loading presentation...
Prezi is an interactive zooming presentation

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

PJM-algorithme génétique

No description
by

Sana Ben Taher

on 26 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of PJM-algorithme génétique

Résolution d'un problème d’ordonnancement des ateliers flexibles de types Job-Shop par un algorithme génétique
Projet métier
Encadré par:
- Mme Fkih Asma
- Mr Htiwech Skander
- Mr Jbailia Mohamed
Définition du problème

Etant donnés un ensemble de n jobs: J={J1, J2, ..., Jn};
A réaliser sur un ensemble de m machines: M={M1, M2, ..., Mm}.
Chaque job Ji est composé d’une séquence linéaire de ni opérations: O1={O11,O12,..., O1ni}.
Chaque machine peut effectuer une seule opération à la fois.
Chaque opération Oij requiert uniquement une machine pour sa réalisation pendant dij unités de temps.
Les opérations ne peuvent pas être interrompues (ou diviser sur plusieurs machines ).

Objectif:
minimiser la somme des dates de fin des jobs.
Qu'est-ce que c'est un problème d’ordonnancement?
Types:
Machine unique
Machine parallèles
Ateliers à cheminements unique (Flow Shop)
Ateliers à cheminements multiples (Job Shop)
Ateliers à cheminements libre (Open Shop)
Étant donnés:
Un ensemble de tâches à accomplir.
Un ensemble de ressources permettant leur réalisation.

Il faut:
Affecter les différentes ressources aux tâches.
Déterminer les dates d’exécution de ces tâches
En optimisant une fonction objectif.
Algorithme Génétique
Procédures et opérateurs
Codage de chromosomes
Sélection d’individus
Croisement
Mutation
Évaluation
Création de la nouvelle génération

Les différentes procédures qui ont lieu dans un algorithme génétique sont:
Codage des chromosomes

Un vecteur « ordonnancement »
Un vecteur «machine »
Attribuer à chaque chromosome (individu) une probabilité de sélection proportionnel à sa performance (calculé par la fonction fitness).
Croisement
Croisement simple :

Un seul point de croisement (dans notre algorithme il est choisi aléatoirement ).
Résultats numériques

Introduction
Objectif du projet
Développer un algorithme génétique capable de résoudre de façon efficiente le problème du job shop flexible avec contrainte de précédence .
Méthodes de résolution
Méthodes exactes:

fournissent une solution optimale pour un problème d’optimisation.
intéressantes dans les cas des problèmes de petites tailles.
Exemples : Procédure par séparation et évaluation, programmation linéaire en nombres entiers et la programmation dynamique.

Méthodes approchées :

exploitent au mieux la structure du problème.
trouvent une solution aussi proche que possible de l 'optimum dans un temps de calcul aussi faible que possible.
intéressantes pour les problèmes plus complexes.
Exemples : Recherche Tabou,
algorithmes génétiques
.
Sélection de parents
Par rapport à la qualité du chromosome .
Les chromosomes choisis vont participer dans la procédure de croisement.
La méthode utilisée:
Sélection par roulette
Mutation
A l’aide d’une fonction RANDOM, deux points de mutation seront fixés.
Sur le vecteur ordonnancement et le vecteur machines les deux cases seront permutées .
Remplir à nouveau le tableau X
Plan
Sélection par roulette
Objectif: diversifier la recherche dans l’espace de solutions.
Introduction
Problème d'ordonnancement
Définition du problème
Algorithme Génétique
Conclusion
Conclusion
Projet très intéressant
Découverte d’une nouvelle méthode d’optimisation par les algorithmes génétiques
Sensibilisation au problème concret d’ordonnancement du job shop flexible
Merci pour votre attention
2013-2014
Un tableau à deux dimensions «X »
Croisement double:

Deux points de croisement


Modélisation mathématique

sous contrainte:

C : temps de fin d’exécution d’une opération j sur une machine k
P : durée qu’occupe une opération j sur une machine k
Avec:
X_(i,j)^k=1 si l’opération i du job j est traitée par la machine k,
X_(i,j)^k=0 si non

Évaluation

On obtient deux nouveaux chromosomes qu’on leurs calcule la fonction fitness.
Après l’évaluation du chromosome enfant un test sera établi.
l’enfant ne sera pris en compte que s’il présente une valeur de somme des dates de fin inférieur à celle des parents.
Création de la nouvelle génération
les enfants crées ,ayant une meilleur fonction fitness , seront ajoutés automatiquement à la population initiale.

conserver les parents d’où une probabilité plus grande d’avoir des enfants meilleurs.
Condition d'arrêt: arrêt de l’évolution de la population.
Application
Instance

Deux chromosomes parents donnés par la Sélection.
Les chromosomes issus du croisement ne peuvent jamais respecter les contraintes posées par le nombre d’opérations de chaque job shop donné.
Le nombre des itérations à effectuer est 15
la somme des dates de fin des jobs est 44 unité de temps.

Manque de temps pour améliorer l’algorithme
1
2
3
4
5

6
7
8
9
10
12
13
14
15
16
17
18
19
Appliquer une procédure de réparation .
Croisement simple
20
21
23
24
25
26
"Entreprendre consiste à changer un ordre existant"
Joseph Schumpter
Full transcript