Exercice 1 :

TD 2 et 3: Ordonnancement

Exercice 1 :

La réalisation d'un projet nécessite l'accomplissement d'un certain nombre de tâches qui ont été recensées ci-dessous:

Tâches	Tâches antérieures	Durée	Tâches	Tâches antérieures	Durée
A	D , H	13	H	J	5
B	-	12	I	F	10
C	M , I	15	J	K , B	15
D	J	11	K	-	7
E	M , D	16	L	-	6
F	L	12	M	F	14
G	E , A	26	N	C	28

1) Classer les sommets du graphe MPM correspondant par niveaux.

2) Tracer le graphe MPM.

3) Calculer les dates au plus tôt et les dates au plus tard de début des différentes tâches

4) Donner le chemin critique.

5) Calculer les marges totales et les marges libres des tâches non critiques.

Exercice 2 :

On considère un problème d'ordonnancement défini de la manière suivante:

tâche	Durée	conditions à satisfaire pour que puisse débuter la tâche
A	10	ne peut débuter que 2 jours après le début des travaux
B	4	suit D et doit commencer 10 jours au plus après le début de H
C	5	suit D et doit commencer 5 jours au plus après la fin de B
D	8	peut débuter 2 jours après le début de A
E	20	peut commencer 5 jours après la fin de G
F	10	suit H et peut commencer lorsque I est à moitié réalisé
G	12
H	7	suit J
I	20	suit J et suit A
J	6

1) Ecrire les contraintes de potentiel entre B et D, B et H, C et D , C et B

2) Construire le graphe MPM associé à ce projet.

3) Déterminer l'ordonnancement au plus tôt, puis l'ordonnancement au plus tard.

4) Donner les marges libres et les marges totales des différentes tâches.

5) Les tâches A et J utilisant la même machine ne peuvent être exécutées en même temps. Quelle décision doit-on prendre et que devient le temps total de réalisation de cet ouvrage?

Exercice 3:

Le GAEC « Les colombiers d’Ensérune » est spécialisé dans l’élevage et la commercialisation du pigeon de chair. Il exploite un vaste élevage moderne de pigeons adultes et lui applique une gestion rigoureuse.

Compte tenu de la nouvelle réglementation européenne, le GAEC décide la construction d’un nouvel abattoir aux normes européennes à la place de l’ancien. Ces travaux causent un dérangement important car ils concernent un point névralgique de l’exploitation. Le GAEC décide donc de les ordonnancer et obtient le tableau suivant, donnant les différentes tâches, leurs durées, leurs coûts, et les tâches immédiatement antérieures :

tâches

Tâches antérieures

Durées

( en jours)

coûts

C-E

F-H

A-I

1) Construire le graphe MPM pour traiter les questions suivantes

a) déterminer le chemin critique ainsi que la durée minimale de réalisation des travaux

b) donner la marge totale et la marge libre de chaque tâche

2) Toutes les entreprises retenues pour effectuer les travaux ont accepté de consentir une remise de 5% sur les coûts indiqués dans le tableau précédent, à condition de disposer chacune d’au moins 20% de temps en plus

a) Déterminer toutes les tâches dont la durée peut augmenter de 20% sans que cela empêche les tâches suivantes de commencer à leur date de début au plus tôt et sans que cela allonge la durée minimale de réalisation des travaux.

b) Déterminer la somme maximale que l’on peut ainsi économiser sur le coût total si l’on se fixe pour règle de commencer toutes les taches à leur date de début au plus tôt et de ne pas allonger la durée minimale de réalisation des travaux.

c) Peut-on augmenter de la même façon la durée d'autres tâches sans allonger la durée minimale de réalisation des travaux?

3) En fait, toutes les durées peuvent être considérées comme fixes sauf deux : celle de la tâche B, qui est une variable aléatoire notée , et celle de la tâche G, qui est une variable aléatoire notée . On admet que la variable aléatoire suit une loi normale d’espérance 4 jours et d’écart type 2,5 jours.

a) Montrer que le chemin (AFCB) devient le chemin critique si et seulement si les variables aléatoires et vérifient la relation

b) Déterminer, à 10^-2 près, la probabilité que le chemin (AFCB) devienne le chemin critique.

Exercice 4

Les données d'un programme d'ordonnancement sont les suivantes:

Tâches	A	B	C	D	E	F	G	H	I
Durées	15	8	5	8	12	9	11	7	8
Antériorités				A B	A C	B C	D	D E	E F
Délais				0 2	6 2	0 4	0	3 0	4 0
Ressources	7	6	5	8	5	4	6	7	4

Les délais représentent le temps minimum qui doit s'écouler entre la fin d'une tâche et le début de celle qui la suit, par exemple il doit s'écouler au moins 2 unités de temps entre la fin de B et le début de D.

1) Tracer le graphe Potentiel-Tâches associé à ce problème.

2) Déterminer l'ordonnancement au plus tôt et l'ordonnancement au plus tard (sans tenir compte des ressources).

3) Après en avoir rappelé les définitions précises donner le chemin critique ainsi que la marge totale et la marge libre de la tâche B.

4) Utiliser un algorithme de liste pour construire un ordonnancement compatible avec les antériorités (y compris les délais) et une disponibilité totale en main d'œuvre de 15. Cet ordonnancement est-il optimal? Pourquoi?

Exercice 5:

On considère le problème d'ordonnancement d'un projet composé de 11 tâches A,......,K défini par le tableau suivant:

Tâches	A	B	C	D	E	F	G	H	I	J	K
Durées	2	4	2	6	6	2	3	2	5	3	4
Antériorités	-	A	A	A	-	B	B , C	D	E , F	G , H	D

1) Tracer le graphe potentiel-tâches (M.P.M.) correspondant, donner l'ordonnancement au plus tôt et l'ordonnancement au plus tard.

2) Donner les tâches critiques et calculer les marges totales et libres des autres tâches.

3) Ces différentes tâches ont un coût de 10 par tâche (au début de celle-ci).

Le projet est financé en trois tranches successives de 40 à la date 0, 30 à la date 5 et enfin 40 à la date 10

Utiliser l’algorithme approprié pour construire un ordonnancement compatible avec ce financement et de durée globale la plus faible possible.