Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

RCP106 - MOCAB2 1 Fiche d’exercices n°3 Ordonnancements Corrigé Exercice 1 – Tâ

RCP106 - MOCAB2 1 Fiche d’exercices n°3 Ordonnancements Corrigé Exercice 1 – Tâches préemptives indépendantes – Algorithme de Mac Naughton On considère un ensemble de 7 tâches morcelables de durées ݀ଵൌ5, ݀ଶൌ3, ݀ଷൌ2, ݀ସൌ 6, ݀ହൌ3, ݀଺ൌ2, ݀଻ൌ1. 1. Déterminer, à l’aide de l’algorithme de Mac Naughton un ordonnancement optimal sur 4 machines. ܤൌ݉ܽݔ൬݉ܽݔ௜∈ூ݀௜, ሺ∑ ݀௜ ௡ ௜ୀଵ ሻ ݉ ൗ൰ൌmaxቀ6, ହାଷାଶା଺ାଷାଶାଵ ସ ቁൌ6 Un ordonnancement optimal, de durée 6 est : 2. Déterminer, à l’aide de l’algorithme de Mac Naughton un ordonnancement optimal sur 3 machines. ܤൌ݉ܽݔ൬݉ܽݔ௜∈ூ݀௜, ሺ∑ ݀௜ ௡ ௜ୀଵ ሻ ݉ ൗ൰ൌmax ቀ6, ହାଷାଶା଺ାଷାଶାଵ ଷ ቁൌ22 3 ሺ≃7,33ሻ Un ordonnancement optimal, de durée 22/3 ሺ≃7,33ሻ est : RCP106 - MOCAB2 2 Exercice 2 – Flow-shop sur 2 machines – Algorithme de Johnson On considère un ensemble de 8 travaux constitués chacun de deux tâches ܽ et ܾ. La tâche ܽ de chaque travail s’exécute sur une machine 1, la tâche ܾ sur une machine 2. La tâche ܽ de chaque travail précède la tâche ܾ. On note ܽ௜ la durée d’exécution de la tâche ܽ du travail ݅ et ܾ௜ la durée d’exécution de la tâche ܾ du travail ݅. Les durées des tâches sont les suivantes : ܽଵൌ3, ܾଵൌ4, ܽଶൌ2, ܾଶൌ4, ܽଷൌ2, ܾଷൌ2, ܽସൌ 4, ܾସൌ3, ܽହൌ5, ܾହൌ1, ܽ଺ൌ3, ܾ଺ൌ3, ܽ଻ൌ1, ܾ଻ൌ4, ଼ܽൌ2, ଼ܾൌ3. Déterminer à l’aide de l’algorithme de Johnson un ordonnancement de durée minimale pour ces 8 travaux. ݅ 1 2 3 4 5 6 7 8 ܽ௜ ሺ݇ൌ1ሻ 3 2 2 4 5 3 1 2 ܾ௜ ሺ݇ൌ2ሻ 4 4 2 3 1 3 4 3 Avec l’algorithme de Johnson-1 on obtient comme valeurs successives de ሺ݅∗, ݇∗ሻ : (5,2), (7,1), (2,1), (3,1), (8,1), (1,1), (4,2), (6,1) d’où la liste ܮଵൌሺ7,2,3,8,1,6,4,5ሻ et un ordonnancement optimal, de durée 25 est donc : Avec l’algorithme de Johnson-2, on obtient :  ܷൌሼ1,2,7,8ሽ et ܮܷൌሺ7,2,8,1ሻ  ܸൌሼ3,4,5,6ሽ et ܮܸൌሺ4,6,3,5ሻ  ܮଶൌሺ7,2,8,1,4,6,3,5ሻ On obtient un autre ordonnancement, également optimal, de durée 25 : Remarque : dans le déroulement des deux algorithmes des choix arbitraires ont été effectués en cas d’égalité de deux valeurs, d’autres listes étaient donc possibles. Exercice 3 – Tâches unitaires sur 1 machine Soit ܫൌሼ1, … , ݊ሽ un ensemble de tâches unitaires devant s’exécuter sur 1 machine. À chaque tâche ݅ sont associés une date d’échéance ߠ௜ et un poids ݓ௜. Une tâche ݅ est dite en retard si sa date de fin d’exécution est supérieure à sa date d’échéance ሺݐ௜൅1 ൐ߠ௜ሻ. Si une tâche ݅ est en retard, un coût ݓ௜ est à payer, si ݅ est en avance ሺݐ௜൅1 ൑ߠ௜ሻ, aucun coût n’est à payer. L’objectif est de déterminer un ordonnancement de coût minimal, c’est-à-dire minimiser la somme des coûts des tâches en retard. RCP106 - MOCAB2 3 1. Montrer qu’il existe un ordonnancement optimal tel que la machine n’a pas de période d’inactivité. Considérons une période d’inactivité ሾݐ; ݐ൅1ሿ de la machine. Si l’on décale d’une unité vers le début du projet chaque tâche dont la date de début d’exécution est ൒ݐ൅1, alors on obtient un ordonnancement de coût moindre ou égal. En effet, avancer le début d’une tâche ne peut occasionner de surcoût (on ne met aucune tâche en retard). Il est donc possible de supprimer ainsi toute période d’inactivité de la machine, puisque ces périodes sont en nombre fini. En partant d’un ordonnancement optimal, on aboutit à un ordonnancement de même coût, sans période d’inactivité. Nous considérons l’algorithme glouton suivant pour calculer un ordonnancement : les tâches sont d’abord triées de sorte que ݓଵ൒ݓଶ൒⋯൒ݓ௡. Pour la tâche ݅, ݅ variant de 1 à ݊, on détermine, si elle existe, la dernière période libre de la machine telle que ݅ ne soit pas en retard. Si cette période existe alors ݅ est affectée à cette période, sinon ݅ est affectée à la dernière période libre de la machine 2. Appliquer cet algorithme à l’exemple suivant : ߠଵൌ4, ݓଵൌ70, ߠଶൌ2, ݓଶൌ 60, ߠଷൌ4, ݓଷൌ50, ߠସൌ3, ݓସൌ40, ߠହൌ1, ݓହൌ30, ߠ଺ൌ4, ݓ଺ൌ20, ߠ଻ൌ 6, ݓ଻ൌ10. Nous allons maintenant montrer que cet algorithme construit un ordonnancement optimal. La démonstration se fait par récurrence sur le numéro des tâches. 3. Montrer qu’il existe un ordonnancement optimal pour lequel la tâche 1 est exécutée à la période déterminée par l’algorithme. Pour cela on utilisera un argument d’échange en considérant le cas où la tâche 1 est en retard et le cas où la tâche 1 est en avance. Considérons un ordonnancement ߪ optimal. Supposons que la tâche 1 est en retard dans ߪ et soit j la tâche exécutée entre ߠଵെ1 et ߠଵ (d’après la question 1, les ݊ créneaux sont utilisés) : RCP106 - MOCAB2 4 D’après l’algorithme utilisé, on a : ࢝૚൒࢝࢐. Échangeons j et 1 : Soit Δ la variation de coût induite par cet échange. Si j passe de l’état « non en retard » à l’état « en retard », alors Δ ൌݓ ௝െݓଵ൑0, sinon Δ ൌ0 െݓଵ൑0. Dans tous les cas, Δ est négatif ou nul. On aboutit donc à un ordonnancement meilleur au sens large. Donc, dans tout ordonnancement optimal, il est possible de considérer que la tâche 1 est exécutée à la période déterminée par l’algorithme. Supposons maintenant que la tâche 1 n’est pas en retard dans ߪ. Soit ݆ la tâche exécutée entre ߠଵെ1 et ߠଵ : On a toujours : ݓଵ൒ݓ ௝. Echangeons à nouveau les tâches j et 1. On obtient : Soit Δ la variation de coût induite par cet échange. La tâche 1 n’était pas en retard, et elle reste dans cet état. L’exécution de la tâche j est avancée. Si j passe de l’état « en retard » à l’état « non en retard », alors Δ ൌെݓ ௝൑0, et si j ne change pas d’état, Δ ൌ0 (il n’est pas possible que j passe de l’état non en retard à l’état en retard). Dans tous les cas, Δ est négatif ou nul. On aboutit donc à un ordonnancement meilleur au sens large. Donc, dans tous les cas, dans tout ordonnancement optimal, il est possible de considérer que la tâche 1 est exécutée à la période déterminée par l’algorithme. Nous supposons maintenant qu’il existe un ordonnancement optimal pour lequel les tâches 1, … , ݅െ1 sont exécutées à la période déterminée par l’algorithme. Nous allons montrer qu’il existe un ordonnancement optimal pour lequel la tâche ݅ est exécutée à la période déterminée par l’algorithme. Supposons qu’à l’étape ݅ de l’algorithme il n’y a plus de période libre sur la machine telle que ݅ ne soit pas en retard. 4. Montrer que dans ce cas, il existe un ordonnancement optimal pour lequel la tâche ݅ est exécutée à la période déterminée par l’algorithme. Pour cela on utilisera un RCP106 - MOCAB2 5 argument d’échange en considérant les tâches placées après ݅ par l’algorithme. Ensuite, on utilisera un argument d’échange en considérant les tâches placées avant ݅ par l’algorithme. On suppose que les tâches 1 à ݅െ1 sont situées à la place déterminée par l’algorithme. D’après l’hypothèse de récurrence, il existe un ordonnancement optimal ߪ dans lequel ces tâches d’indice ൏݅ ont précisément ces dates de début d’exécution. Supposons qu’à l’étape ݅ de l’algorithme glouton il n’y a plus de période libre telle que ࢏ ne soit pas en retard. On a donc : Si, dans ߪ, la période ሾ߬; ߬൅1ሿ est occupée par une tâche ݆൐݅ (avec donc ݓ௜൒ݓ ௝), cela signifie que ݅, située après ߠ௜ et donc en retard dans ߪ, peut être échangée avec la tâche ݆ : le coût ne peut que décroître au sens large puisque ݅ est déjà en retard dans ߪ et l’échange ferait avancer la tâche ݆. Supposons qu’à l’étape ݅ de l’algorithme il y a une période libre sur la machine telle que ݅ ne soit pas en retard. 5. Montrer, en utilisant des arguments similaires à ceux utilisés pour la question précédente, que dans ce cas il existe un ordonnancement optimal pour lequel la tâche ݅ est exécutée à la période déterminée par l’algorithme. On suppose que les tâches 1 à ݅െ1 sont situées à la place déterminée par l’algorithme. D’après l’hypothèse de récurrence, il existe un ordonnancement optimal ߪ dans lequel ces tâches d’indice ൏݅ ont précisément ces dates de début d’exécution. Supposons qu’à l’étape ݅ de l’algorithme glouton il y a bien une période libre telle que ࢏ ne soit pas en retard. Appelons ߬ le début de la dernière des périodes laissant i non en retard. On a ߬൑ ߠ௜െ1. Si, dans ߪ, la période ሾ߬; ߬൅1ሿ est occupée par une tâche ݆൐݅ (avec donc ݓ௜൒ݓ ௝), échanger les tâches i et j fait à nouveau décroître le coût au sens large : si dans ߪ la tâche ݅ est en retard, la placer à ߬ fait gagner ݓ௜ et éventuellement perdre ݓ ௝ mais comme ݓ௜൒ݓ ௝, l’échange est bien profitable. Si dans ߪ la tâche ݅ n’était pas en retard, ݅ est nécessairement placée dans ߪ avant ߬ d’après le choix de ߬, ainsi placer ݅ à uploads/Management/ exercices-fiche3-corrige.pdf