Expérimentations numériques et comparaison du mode de construction à rebours vis-à-vis l’ACS

Expérimentations numériques et comparaison du mode de construction à
rebours vis-à-vis l’ACS

Un nouveau mode de construction de solutions avec TACS pour le problème de machine unique avec temps de réglage dépendants de la séquence

Introduction

L’ACS a été proposé dans la littérature par Dorigo et Gambardella [1997] et plusieurs travaux ont porté sur différents problèmes d’optimisation combinatoire dont le problème d’ordonnancement à machine unique avec temps de réglage dépendants de la séquence.
Toutefois, aucun de ces travaux ne s’est penché sur un mode de construction à rebours d’une solution pour résoudre un problème. Dans ce chapitre, un mode de construction à rebours d’une solution dans un ACS est proposé ayant comme objectif la minimisation du retard total. Nous estimons que cet objectif se prête très bien à une telle proposition d’algorithme car une construction classique favorise le respect des dates dues pour les tâches placées en début de séquence et les retards sont généralement obtenus pour les tâches restant à placer en fin de séquence.

L’ACS à rebours (ACS – R)

Compte tenu de l’objectif à optimiser et de la nature du problème étudié, plusieurs éléments de l’ACS doivent être revus pour une construction de solution commençant par la fin de la séquence. Les sections suivantes décrivent ces éléments.

Estimation de la date de fin

L’ACS classique construit les solutions en plaçant les tâches les unes après les autres en fonction des visibilités et de la trace accumulée. La date de fin de la dernière tâche détermine alors le «makespan» de l’ordonnancement et le calcul du retard total est obtenu en cumulant le retard de chacune des tâches.
Dans l’ACS – R, la construction d’une solution s’opère en plaçant les tâches en débutant par la fin de la séquence. Il faut, à priori, connaître la date de fin de la dernière tâche ou estimer celle-ci avant d’amorcer la construction d’une solution. Nous avons choisi d’estimer la date de fin d’un ordonnancement en construisant deux séquences. La première séquence est établie en utilisant la règle de priorité favorisant la plus petite date d’échéance (EDD) alors que la deuxième séquence est générée de façon entièrement aléatoire. Ces deux séquences permettent d’estimer un intervalle dans lequel la date réelle de fin de l’ordonnancement peut potentiellement se retrouver. Pour la construction de chaque fourmi, on tire la date de fin aléatoirement dans cet intervalle.
À chaque fois qu’une tâche est placée à l’aide de la règle de transition de l’ACS – R, la mise à jour de la date de fin est réalisée en soustrayant le temps de traitement de la tâche placée à la date de fin actuelle. On a donc date de fin = date de fin – pj où p;- est le temps de traitement de la tâche déjà placée. Le temps de réglages entre les tâches n’a pas été pris en compte dans la mise à jour de la date de fin parce que l’ordre de grandeur des valeurs associé aux réglages n’est pas significatif par rapport à la date de fin et au temps de traitement.

Définition d’un nouveau concept de visibilité

Pour le problème d’ordonnancement à machine unique avec temps de réglage dépendants de la séquence, l’ACS proposé par Gagné, Price et al. [2002] prend en compte, à titre de visibilité, le temps de réglage normalisé entre les tâches, la marge normalisée d’une tâche et la fonction de regard vers l’avant.Pour reproduire cet ACS aux fins de comparaison, nous n’avons pas inclus la fonction de regard vers l’avant. La règle de transition utilisée, présentée à l’équation 3.1, introduit le concept de marge tel que proposé par les auteurs et qui doit être redéfini dans une implementation à rebours de l’ACS. Rappelons que la marge d’une tâche est le délai d’une tâche par rapport à sa date d’échéance avant qu’elle ne soit en retard. Cette marge est calculée au début de l’algorithme pour chacune des tâches sans être mise à jour à chaque pas de la construction d’une fourmi.

Le concept de marge

arrière (MAt) a été développé de façon à privilégier les tâches à placer à la fin de la séquence. La marge arrière est le délai disponible pour placer une commande avant que celle-ci devienne en retard.La marge arrière est ainsi définie comme étant MAj – dj -datedefin + Sji, où d;- correspond à la date due de la tâche à placer, date de fin à la date de fin de la dernière tâche placée et Sjt au temps de réglage nécessaire lorsque la tâche j est placée avant la tâche  déjà placée.Le résultat du calcul du MA peut être positif, négatif ou nul. Un résultat positif exprime le fait que si la tâche est insérée dans la séquence, elle ne génère aucun retard. Si on prend l’exemple de la Figure 3.1, la tâche 15 est déjà placée dans la séquence et on calcule la marge de la tâche 8 pour l’insérer dans la séquence.On peut constater que si la tâche 8 est placée avant la tâche 15, elle ne sera pas en retard car sa date de fin sera à 1509 compte tenu du réglage 5 entre les tâches 8 et 15 et de sa date d’échéance de 1580. On a donc une MA de 71 pour la tâche 8. Si toutes les tâches non placées ont des marges arrières positives, on va privilégier celles qui ont la plus grande marge positive parce qu’elles seront placées le plus éloigné possible du début de la séquence sans qu’elles ne soient en retard.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Table des Matières
RÉSUMÉ
REMERCIEMENTS
Table des Matières
Liste des Tableaux
Liste des Figures
CHAPITRE 1 Introduction
CHAPITRE 2 Revue de la littérature
2.1 Introduction
2.2 Modèle à machine unique avec temps de réglage dépendants de la séquence
2.3 Les algorithmes de fourmis
2.3.1 Les différentes versions d’algorithmes d’optimisation par colonie de fourmis
2.3.2 L’ACS pour le problème de machine unique avec temps de réglage dépendants de
la séquence pour minimiser le retard total
2.4 Objectifs de la recherche
CHAPITRE 3 Un nouveau mode de construction de solutions avec l’ACS pour le problème
de machine unique avec temps de réglage dépendants de la séquence
3.1 Introduction
3.2 L’ACS à rebours (ACS – R)
3.2.1 Estimation de la date de fin
3.2.2 Définition d’un nouveau concept de visibilité
3.2.3 La liste de candidats
3.2.4 La règle de transition
3.3 Modifications proposées à l’ACS – R
3.3.1 ACS – R avec changements dynamiques des paramètres (ACS – RD)
3.3.2 ACS – R avec règle de priorité (ACS- RP)
3.4 Conclusion
CHAPITRE 4 Expérimentations numériques et comparaison du mode de construction à
rebours vis-à-vis l’ACS
4.1 Introduction
4.2 Analyse comparative entre l’ACS classique et l’ACS – R
4.2.1. Comparaison de la performance pour les problèmes de petite taille
4.2.2. Comparaison de la performance pour les problèmes de grande taille
4.3 Analyse comparative entre l’ACS classique et l’ACS – RD
4.3.1. Comparaison de la performance pour les problèmes de petite taille
4.3.2. Comparaison de la performance pour les problèmes de grande taille
4.4 Résultats de l’ACS à rebours avec règle de priorité
4.4.1. Comparaison de la performance pour les problèmes de petite taille
4.4.2. Comparaison de la performance pour les problèmes de grande taille
4.5 Réflexion sur les résultats obtenus
CHAPITRE 5 Conclusion
CHAPITRE 6 Bibliographie

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *