Méthodes d'Optimisation Méthod Recherche Tabou Exercice Corrigé Ordonnancement de Tâches Partie 13

Types de mouvements Trois mouvements possibles sur les permutations:[8] Inversion : 1 2 3 4 5 6 7 8 ------------ 1 2 4 3 5 6 7 8 (n-1) mouvements possibles pour chaque solution. Echange (Transposition) : 1 2 3 4 5 6 7 8 ------------ 1 2 7 4 5 6 3 8 n(n-1)/2 mouvements possibles pour chaque solution. Déplacement : 1 2 3 4 5 6 7 8 ------------ 1 2 3 7 4 5 6 8 Ces 4 objets changent de place  n(n-2)/2 mouvements possibles pour chaque solution. Représentation des solutions(variables) sk pour 5 tâches : sk = 2. Voisinage N(sk) : Pour définir ou structurer N(sk), on peut par exemple inverser (Permuter) deux tâches, (mouvement par échange ou transposition): Chaque solution a 10 voisins: l’ensemble de voisinage N(sk) est déterminé par la permutation entre une tâche sk et ses voisins: On a 5 variables (tâches) chaque variable a 4 cas possibles de permutations: 5x4=20. On ne considère pas la symétrie: permuter 3 et 5 c’est la même chose que permuter 5 et 3: donc (5x4)/2 = 20/2 = 10 voisins possibles. Remarque; ce n’est pas toujours le cas, selon le problème, on peut avoir 3 et 5 différent e 5 et 3 3 5 1 4 2 si on échange 3 par 1 on obtient 1 5 3 4 2 si on échange 1 par 3 on obtient 1 5 3 4 2 Donc : La taille du voisinage N(sk) d’une solution sk est n(n-1)/2 avec n = 5 on a la Taille = 5*4/2=10 voisins. L’espace de recherche S5 est l'ensemble des permutations de {1,2, 3,4,5}. Cardinal (S)=n factoriel=5*4*3*2*1=20*6=120 solutions. Sk 10 solutions comme voisins de sk 3. Fonction objectif: min f (sk) =∑▒𝑐_𝑖𝑗 avec 𝑐_𝑖𝑗est le coût entre la tâche i et la tâche j 4. Solution initiale complète s0 Choix aléatoire : s0 = 5. L’opérateur de voisinage Le voisinage est défini comme l’ensemble des solutions accessibles en échangeant 2 objets. Tous les mouvements sont autorisés. N(sk) est l'ensemble des solutions obtenues en échangent à chaque fois deux positions de sk. 6.Taille de voisinage candidat : aléatoire n(n-1)/2 = (5*4)/2 = 10, on peut prendre un nombre inférieur à 10. 7. Taille de la mémoire ou liste tabou L/ égale à la taille du voisinage. Taille = n(n-1)/2 = (5*4)/2 = 10, Les 3 dernières échanges ou permutations sont considéré tabou, donc La tenue de la liste tabou est au bout de 3 itérations 8. Les critères d’aspiration : a(sk,m) = 3 9. Le critère d’arrêt : k=50

الفئة