TN3 ADM 1420
TD : TN3 ADM 1420. Recherche parmi 300 000+ dissertationsPar manoune55 • 26 Juillet 2019 • TD • 2 313 Mots (10 Pages) • 666 Vues
PROBLEME 1 : ORDONNANCEMENT (10 POINTS)
PARTIE A : ÉQUIPE α
a) Déterminons l'affectation qui permet de minimiser le temps total de traitement des 4 commandes du tableau suivant :
OP1 OP2 OP3
C1 6 4 5.5
C2 6.5 5 4
C3 7 4 7
C4 5 3.5 6
Puisqu'il y a plus de commandes que d'opérateurs disponibles, nous devons rendre la matrice carrée en créant un opérateurs fictif et en lui attribuant des temps plus élevés.
OP1 OP2 OP3 OP6
C1 6 4 5.5 7
C2 6.5 5 4 8
C3 7 4 7 9
C4 5 3.5 6 8
Appliquons intégralement l'algorithme d'affectation dans le tableau précédent :
Soustrayons la plus petite valeur de chaque rangée:
Dans la 1ère rangée, soustrayons 4, la plus petite valeur
Dans la 2ème rangée, soustrayons 4, la plus petite valeur
Dans la 3ème rangée, soustrayons 4, la plus petite valeur
Dans la 4ème rangée, soustrayons 3.5, la plus petite valeur
Nous obtenons le nouveau tableau suivant:
OP1 OP2 OP3 OP6
C1 2 0 1.5 3
C2 2.5 1 0 4
C3 3 0 3 5
C4 1.5 0 2.5 4.5
Soustrayons la plus petite valeur de chaque colonne:
Dans la 1ère colonne, soustrayons 1.5, la plus petite valeur
Dans la 2ème colonne, soustrayons 0, la plus petite valeur
Dans la 3ème colonne, soustrayons 0, la plus petite valeur
Dans la 4ème colonne, soustrayons 3, la plus petite valeur
Nous obtenons :
OP1 OP2 OP3 OP6
C1 0.5 0 1.5 0
C2 1 1 0 1
C3 1.5 0 3 2
C4 0 0 2.5 1.5
Recouvrons toutes le valeurs nulles par un minimum de lignes :
OP1 OP2 OP3 OP6
C1 0.5 0
1.5
0
C2 1 1 0 1
C3 1.5 0 3 2
C4 0
0 2.5 1.5
Nombre de lignes l = n
Nous avons donc trouvé l'affectation optimale :
C1 à OP6 ; C2 à OP3 ; C3 à OP2 ; C4 à OP1
Voici le tableau de départ avec la charge de travail optimale :
OP1 OP2 OP3 OP6
C1 7
C2 4
C3 4
C4 5
La commande C1 a un opérateur fictif donc elle pourra être traitée par le premier opérateur qui se sera libéré entre les deux opérateurs 2 et 3.
b) Mettons la charge de travail sous forme de Graphique de Gantt :
Périodes
1 2 3 4 5 6 7 8
Employé
OP1
OP2
OP3
OP6
c) Calculons la durée de traitement des quatre commandes :
OP1 OP2 OP3 OP6
C1 7
C2 4
C3 4
C4 5
DT = 5+4+4+7 = 20 heures.
Calculons le coût de traitement des commandes si chaque opérateur est payé 12$ de l'heure :
CT = 20 heures x 12$/h = 240$
PARTIE B : ÉQUIPE β
d) Trouvons la séquence qui minimise le temps total de traitement des sept commandes du tableau qui suit :
A B C D E F G
OP4 : cueillette 30 20 50 80 70 60 25
OP5 : préparation 40 50 10 40 25 40 50
Puisque nous avons deux opérations, nous pouvons utiliser l'algorithme de Johnson.
Choisissons le temps d'opération le plus court : dans ce cas, c'est 10 heures, à la commande C, "OP5 préparation"
Puisque la plus petite valeur (10 heures) correspond à une valeur de la seconde opération, on placera la commande à la fin de la séquence: elle sera la dernière à être procédée.
C
Choisissons la prochaine plus petite valeur. C'est 20 h pour la commande B et elle se trouve dans la rangée de la première opération (OP4: cueillette). Cette commande sera placée au début de la séquence. Elle sera donc la première à être procédée.
B C
Puis, nous avons G et E qui ont les prochaines plus petites valeurs (25 h). Puisque cette valeur se trouve à la première opération pour la commande G et à la seconde opération pour la commande E, nous allons placer la commande G au début de la séquence et la commande E à la fin.
B G E C
Pour
...