Soutenance mémoire
Généralités sur l’ordonnancement
Ordonnancer le fonctionnement d’un system industriel de production consiste à gérer l’allocation des ressources au cours du temps, tout en optimisant au mieux un ensemble decritère. C’est aussi programmer l’exécution d’une réalisation en attribuant des ressources auxtaches et en fixant leurs dates d’exécution [1]. Ordonnancer peut également consister à programmer l’exécution des opérations en leur allouant les ressources requises et en fixant leurs dates de début de fabrication.
D’une manière plus simple, un problème d’ordonnancement consiste à affecter des tâches à des moyens de fabrication au cours du temps pour effectuer un ensemble de travaux de manière à optimiser certain critère, tout en respectant les contraintes techniques de fabrication [2]. L’ordonnancement se déroule en trois étapes qui sont: La planification, qui consiste à déterminer les différentes opérations à réaliser les dates correspondantes, et les moyens matériels et humains à y affecter. L’exécution, qui vise à mettre en œuvre les différentes opérations définies dans la phase de planification. Le contrôle, qui effectue une comparaison entre la planification et l’exécution soit au niveau des coûts, soit au niveau des dates de réalisation. Ainsi, le résultat d’un ordonnancement est un calendrier précis de tâches à réaliser qui se décompose en trois caractéristiques importantes :
– L’affectation, qui attribue les ressources nécessaires aux tâches.
– Le séquencement, qui indique l’ordre de passage des tâches sur les différentes ressources.
– Le datage, qui indique le temps de début et de fin d’exécution des tâches sur les différentes ressources. La solution d’un problème d’ordonnancement générale doit répondre à deux question :
– Quand ?
– Avec quels moyens ? .
Une solution répandant à ces questions est appelée ordonnancement. Une méthode permettant de construire un ordonnancement est appelée algorithme ou méthode de résolution. Un ordonnancement dit réalisable est un ordonnancement qui respecte toutes les contraintes du problème. Nous utilisons le terme «ordonnancement » pour simplifier, pour représenter un ordonnancement réalisable.
Différents paramètres de l’algorithme de luciole
Nombre de luciole Le nombre de lucioles aussi appelé la taille de la population initiale, à une influence directe sur l’algorithme de luciole pour cela il est très important de bienchoisir ce paramètre pour garantir un meilleur compromis entre la qualité de la solutionet la rapidité de l’exécution.D’après’ les différents tests effectués, on constate que plus la taille de la population est grande, sa diversité augmente est donc la qualité de solution est meilleure.Par conséquent si le temps d’exécution de l’algorithme augmente, il affecte l’efficacité de l’algorithme. Par contre si le nombre de luciole est petit, il y aura alors une probabilité de converger vers un optimum local et donc il est plus efficace d’avoir un nombre important de lucioles pour assurer une diversité et éviter le problème des minimas locaux.
Attraction de luciole Dans notre algorithme, il y a deux valeurs importantes : la variation de l’intensitélumineuse et la formulation de l’attractivité. L’attraction de luciole est proportionnelle à l’intensité de la lumière vue par leslucioles adjacentes. Cette attraction est diminuée avec la distance, c.-à-d. plus la distance entre deux lucioles augmente plus l’attraction diminue et que la lumière est également absorbée par le média.
Attraction initiale C’est l’attractivité quand la distance entre deux lucioles = 0. En général il s’agit d’un paramètre (beta0) ∈ [0,1]. Nous considérons deux valeurs limites de (beta0): (beta0 )= 0 indique une recherche aléatoire non coopérative distribuée. (beta0) = 1 signifie que la recherche coopérative locale où brillante des lucioles détermine les positions des autres lucioles dans son propre quartier.
La distance La distance entre deux lucioles est un paramètre très important, il est évalué de différentes manières. Pour notre algorithme, la distance entre deux lucioles est cartésienne adoptée dans un espace D-dimensionnel.
Coefficient d’absorption Le coefficient d’absorption ( gamma) contrôle la variation de l’attractivité en fonction de la distance entre deux lucioles communiquées. Il est dans l’intervalle [0, ∞]. gamma=0 correspond à aucun changement, pas de variation ou attractivité constante, gamma= ∞, correspond à une recherche aléatoire complète. Nous préférons garder la valeur de (gamma∈ [0,1]), gamma= 1 entraîne une attractivité proche de zéro qui est encore équivalente à la recherche aléatoire complète. Ce coefficient d’absorption personnalisé pourrait être basé sur la « longueur caractéristique » de l’espace de recherche optimisé.
Nombre de génération La convergence vers la solution optimale globale n’est pas garantie dans tous les cas même si les expériences dénotent la grande performance de la méthode. De ce fait, il est fortement conseillé de doter l’algorithme d’une portée de sortie en définissant un nombre maximum d’itération.
Adaptation de l’algorithme de lucioles
L’algorithme des lucioles est une métaheuristique récente bio inspirée.sa source d’inspiration est basée sur l’émission de la lumière, absorption de la lumière et le comportement attractif mutuelle entre les lucioles. Initialement, il a été développé pour résoudre les problèmes d’optimisation. La luminosité de la lumière clignotante peut être considérée comme une fonction objective qui devra être optimisé. Les étapes de l’algorithme de luciole sont résumées comme suit :
Créer la population initiale de lucioles (X) :Une étape importante lors du fonctionnement du processus de l‘algorithme luciole, le choix de la population initiale peut rendre la recherche de la solution optimale du problème traité plus facile et plus rapide, en écrit dans le programme du Matlab
Evaluez l’intensité de la lumière Ii de toutes les lucioles en utilisant la fonction objective (Cmax) pour chaque Xi Evaluation c’est-à-dire détermination de la l’intensité de tous les lucioles ou bien la fonction objective (Cmax), généralement est doit être on mesure la performancede chaque luciole
Déterminer le coefficient d’absorption (gamma) :Le coefficient d’absorption ( gamma) contrôle la variation de l’attractivité en fonction de la distance entre deux lucioles communiquées (gamma∈ [0,1]), nous avons fait une étude sur l’intervalle de la coefficient d’absorption pour trouver la bonne valeur qui correspond à la simulation de l’algorithme de luciole, nous voyons les résultats de cette étude dans les pages suivantes.
Déterminer le paramètre (beta0) :En général il s’agit d’un paramètre (beta0) ∈ [0,1], (beta0) est l’attractivité à r = 0 (r c’est la distance entre deux luciole).
Classer les Xi (luciole) :Ou bien classer les fonction objectif (Cmax) on ordre ascendante pour calculé les distances ou bien les déférences entre les résultats
Calculer r0=Cmax1-Cmax2 :Calculé r0 (distance entre les résultats pour calculé l’intensité de l’attractivité
Calcule l’attractivité :L’attraction de luciole est proportionnelle à l’intensité de la lumière vue par les lucioles adjacentes. Cette attraction est diminuée avec la distance, c-à-d plus la distance entre deuxlucioles augmente plus l’attraction diminue et que la lumière est également absorbée par le média
Pour i=1 à nombre d’itérations
Pour j=1 à Taille de population
Pour q=1 à Taille de population
If Ij<Iq
(I) représenté l’intensité de chaque luciole j ou luciole q Mais si l’intensité du lumière Ij>Iq, ici il y a une mutation entre j et q.
Évaluer les intensités ou bien les Cmax Détermination de la fonction objective
Classer tous les intensités (les fonction objectif) :Pour choisir la meilleure (ou les meilleurs) solution (minimiser la fonction objectif Cmax)
Adaptation de l’algorithme de génétique
L’Algorithme Génétique sont considérés par plusieurs chercheurs comme une méthode bien adaptée au problème de type Flow Shop, même si elle ne peut pas arriver à l’optimum dans certains cas difficiles. Notre application porte uniquement sur l’Algorithme Génétique standard, c-à-d, la version de base caractérisé par une population d’individus générés aléatoirement, un opérateur de sélection, un opérateur de croisement appliqué à un point, et un opérateur de mutation.
Les étapes de l’algorithme de génétique sont résumées dans l’algorithme suivant :
Génération de la population initiale :Une étape importante lors du fonctionnement du processus de l‘algorithme génétique, la première population est générée soit d‘une manière aléatoire, soit par des heuristiques ou des techniques spécifiques au problème.
Evaluation de la fonction objective :Evaluation c’est-à-dire détermination de la fonction d’adaptation (fitness) ou bien la fonction objective, généralement est doit être on mesure la performance de chaque individu
Sélection :La sélection est appliquée afin de favoriser au cours du temps les individus les mieux adaptés, à les faire se produire. Elle consiste à choisir deux individus (solutions) dits « parents » en but de créer deux autres individus dits « enfants ».
Recombinaison ou bien Croisement :Le croisement est un opérateur très important dans les Algorithmes Génétiques. Cet opérateur est appliqué sur chaque deux parents sélectionnés
Mutation :Il consiste à modifier quelques gènes des chromosomes des individus, dans le but d’intégrer plus de diversité au sein du processus de la recherche.
Algorithme génétique
L’algorithme génétique représente une célèbre métaheuristique évolutionnaire. Il a été proposé par Jhon Holland en 1975 [Holland, 1975]. L’algorithme génétique s’inspire des mécanismes biologiques tels que les lois de Mendel et la théorie de l’évolution proposée par Charles Darwin [Darwin, 1859]. Son processus de recherche de solutions à un problème donné imite celui des êtres vivants dans leur évolution. L’algorithme génétique c’est une techniques d‘optimisation itératives et stochastiques visant à résoudre des problèmes d‘optimisation NP difficiles, à utiliser le concept de populations d‘individus pour faire face à des problèmes qui émergent du secteur industriel, Il utilise les vocabulaires suivants : gène, chromosome, individu, population et génération .
Un gène : est un ensemble de symboles représentant la valeur d’une variable. Dans la plupart des cas, un gène est représenté par un seul symbole (un bit, un entier, un réel ou un caractère).
Un chromosome : est un ensemble de gènes, présentés dans un ordre donné de manière qui prend en considération les contraintes du problème à traiter. Par exemple, dans le problème du voyageur de commerce, la taille du chromosome est égale au nombre de villes à parcourir. Son contenu représente l’ordre de parcours de différentes villes. En outre, on doit veiller à ce qu’une ville (représentée par un nombre ou un caractère par exemple) ne doit pas figurer dans le chromosome plus qu’une seule fois.
Un individu : est composé d’un ou de plusieurs chromosomes. Il représente une solution possible au problème traité.
Une population : est représentée par un ensemble d’individus (i.e. l’ensemble des solutions du problème).
Une génération : est une succession d’itérations composées d’un ensemble d’opérations permettant le passage d’une population à une autre.
Classification des métaheuristique
Nous distinguons deux classes de métaheuristiques[25] : La première classe c’est les métaheuristique à solution unique basées sur une solution et dont le principe de recherche se base sur le voisinage de la solution trouvée. Ce sont des méthodes itératives, qui à partir d’une solution initiale cherchent une amélioration possible, (algorithme de recuit simulé, algorithme de la recherche tabou, …). Et la deuxième classe c’est les métaheuristique à population de solutionsont des algorithmes qui manipulent une population de solutions en utilisant des opérateurs. Dans cette optique, la structure générale des algorithmes évolutionnaires ou évolutionnistes enchaîne des étapes de sélection, de reproduction (ou croisement), de mutation et enfin de remplacement. Chaque étape utilise des opérateurs plus ou moins spécifiques, (algorithme génétique, algorithme colonie de fourmis, …).
|
Table des matières
Dédicace
Remerciement
Résumé
INTRODUCTION GENERALE
Chapitre 1 Formulation des problèmes d’ordonnancement
1.1 Introduction
1.2 Généralités sur l’ordonnancement
1.3 Les données d’un problème d’ordonnancement
1.3.1 Les tâches
1.3.2 Les ressources
1.3.2.1 Les ressources renouvelables
1.3.2.2 Les ressources consommables
1.3.3 Les contraintes
1.3.4 Les objectifs
1.4 Problèmes d’ordonnancement d’ateliers
1.4.1 Le type d’une machine unique
1.4.2 Le type des machines parallèles
1.4.3 Le type flow shop
1.4.4 Le type job shop
1.4.5 Le type open shop
1.5 Les critères d’optimisation
1.6 La complexité et la théorie de la complexité
1.6.1 Les problèmes de la classe P
1.6.2 Les problèmes de la classe NP
1.6.2.1 Les problèmes de la classe NP-Complets
1.6.2.2 Les problèmes de la classe NP-Difficiles
1.7 Méthodes de résolution
1.7.1 Méthodes exactes
1.7.1.1 La programmation linéaire
1.7.1.2 La programmation dynamique
1.7.1.3 Branch and Bound
1.7.2 Méthodes approches
1.8 Conclusion
CHAPITRE 2 Les Métaheuristiques
2.1 Introduction
2.2 Classification des méthodes de résolution
2.3 Méthodes approchées
2.3.1 Les heuristiques
2.3.2 Les Métaheuristiques
2.3.2.1 Propriétés des métaheuristiques
2.3.2.2 Classification des métaheuristique
2.3.2.2.1 Le recuit simulé
2.3.2.2.2 La recherche tabou
2.3.2.2.3 Les colonies de fourmis
2.3.2.2.4 Optimisation par Colonie d’abeilles
2.3.2.2.5 Algorithme génétique
2.3.2.2.5.1 Principe de fonctionnement de l’algorithme génétique
2.3.2.2.6 Algorithme des Lucioles
2.3.2.2.6.1 Paramétrages des algorithmes des Lucioles
2.4 Conclusion
CHAPITRE 3 Adaptation de l’algorithme de luciole et l’algorithme génétique et résultats de simulation
3.1 Introduction
3.2 différents paramètres de l’algorithme de luciole
3.3 Adaptation de l’algorithme de lucioles
3.4.1 L’études sur l’algorithme de luciole
3.4.2 Comparaison entre les deux techniques
3.5 Conclusion
CONCLUSION GENERALE
Bibliographies
Télécharger le rapport complet
