Tn3 ADM 1420

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

...