Théorie des graphes : Td ordonnancement dut informatique mathematiques
Télécharger PDFphilippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
ordonnancement
Math ́ematiques
TD n◦ 6
Exercice1
Parmi lesntˆachesAi (i∈ {1; 2;. . .;n}) qui constituent un projet, on en consid`ere deux
distinctes :Ak etAj , de dur ́ees respectivesdk etdj ; leurs dates de d ́ebut d’ex ́ecution sont
not ́ees respectivementtk ettj . Traduire les contraintes suivantes :
•par une (ou plusieurs) in ́egalit ́e(s)
•par un (ou plusieurs) arc(s) dans un graphe≪ potentiel-tˆaches≫ .1.A j
commence au plus tˆot un tempsdapr`es le d ́ebut deAk .2.A j
commence au plus tˆot un tempsdapr`es l’ach`evement deAk .3.A j
commence au plus tˆot lorsque la fractionfde la dur ́ee deAk s’est ́ecoul ́ee
(0≤f≤1).4.A j
commence au plus tard un tempsdapr`es le d ́ebut deAk .5.A j
doit d ́ebuter au plus tˆot un tempsd1 apr`es le d ́ebut deAk et au plus tard untempsd 2
apr`es le d ́ebut deAk (d1 ≤d2 )6.A j
doit commencer d`es l’ach`evement deAk .7.A j
commence au plus tˆot `a la dateTet au plus tard `a la dateT′ (T≤T′ ).1 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
ordonnancement
Math ́ematiques
TD n◦ 6
Exercice2
On consid`ere deux projets compos ́es de 5 tˆaches (Si )
i=1...,5
plus deux tˆaches fictives,S0 etS f
, de d ́ebut et de fin de projet. Ces projets sont repr ́esent ́espar des graphes potentiel-
tˆaches et on noteti le d ́ebut de la tˆacheSi (ett0 = 0).
1.Projet 1S 0S 1S 2S 3S 4S 5S f0 32 22 41 26 (a) Lequel des ordonnancements suivants n’est pas compatible avec ce graphe ?
0 1 2 3 4 5 6 7 8 9 10 11 12t 1t 2t 3t 5t 4
0 1 2 3 4 5 6 7 8 9 10 11 12t 1t 2t 3t 5t 4
(b) Calculer l’ordonnancement au plus tˆot du projet et sa dur ́ee minimaleT1 .
(c) Donner l’ordonnancement au plus tard pour terminer le projet en 10 jours.
2.Projet 2S 0S 1S 2S 3S 4S 5S f0 2−3 22 41 21 (a) Lequel des ordonnancements suivants n’est pas compatible avec ce graphe ?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16t 1t 2t 3t 5t 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16t 2t 1t 3t 5t 4
(b) Calculer l’ordonnancement au plus tˆot du projet et sa dur ́ee minimaleT2 .
(c) Que peut on dire de la dur ́eedi de chaque tˆache (Si )
i=1...,5. 2
philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
ordonnancement
Math ́ematiques
TD n◦ 6
Exercice3
Construction d’une maison [12pts]
On s’int ́eresse `a la construction d’une maison dont les diff ́erentes ́etapes et contraintes
sont d ́ecrites dans le graphe potentiel-tˆachesGd ́ecompos ́e en niveaux ci-dessous :1234 56 789 02792 45764 16
Ce graphe correspond au cahier des charges suivant :
TˆachesOp ́erations et contraintesdi (jours)
1D ́ebut des travaux0
2Excavations2
3Fondations: commencent au plus tˆot `a la fin des excavations (2)4
4Construction des murs:
d ́ebute au plus tˆot 3 jours apr`es la fin des fondations (3)9 5Montage de la charpente:
d ́ebute au plus tˆot lorsque (4) est termin ́ee2 6Plˆatrage: la plomberie et le cˆablage ́electrique (7), la couverture
du toit (8) doivent ˆetre achev ́ees5 7Cˆablage ́electrique et plomberie: d ́ebutent au plus tˆot
- lorsque (3) est termin ́ee
- lorsque (4) est commenc ́ee depuis au moins 7 jours6 8Couverture du toit: la charpente doit ˆetre en place (5) et, `a
cause du d ́elai de livraison des tuiles, 16 jours au moins s ́eparent le
d ́ebut des travaux (1) et le d ́ebut de (8).4 9Fin des travaux0
1. (a) Donner les deux arcs du grapheGcorrespondant `a des contraintes implicites ?
(b) Calculer les distances maximales dans le grapheGdepuis le sommet 1 en uti-
lisant l’algorithme de Bellman Simplifi ́e. En d ́eduire l’ordonnancement auplus
tˆot et la dur ́ee totale minimaleTpour la construction de cette maison.
(c) Faire apparaitre les chemins critiques sur le grapheG, en d ́eduire une contrainte
redondante (c’est `a dire inutile) du cahier des charges.
(d) DessinerG−1 , le graphe r ́eciproque deG, d ́ecompos ́e en niveaux.
(e) Calculer Les distances maximales dans le grapheG−1 depuis le sommet 9 en
utilisant l’algorithme de Bellman Simplifi ́e. En d ́eduire l’ordonnancementau
plus tard si on souhaite que la construction soit achev ́ee le plus vitepossible
(donc pour une dur ́eeT, dont la valeur a ́et ́e calcul ́ee question 1b) .3 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
ordonnancement
Math ́ematiques
TD n◦ 6
2. On introduit dans le cahier des charges une nouvelle tˆache :A10 ,pose des gaines,
dont la dur ́ee pr ́evue estd10 = 5 jours, et les nouvelles les contraintes :
• A7 commence au plus tˆot `a la fin deA10 • A8 commence au plus tˆot 3 jours apr`es le d ́ebut deA10 • A10 commence au plus tˆot `a la fin deA4 • A6 commence au plus tard 4 jours apr`es le d ́ebut deA8 (a) Repr ́esenter ce nouveau projet `a l’aide d’un graphe potentiel-tˆachesK.
Indication :DessinerKen partant du grapheGet ajouter le nouveau sommet
et les nouveaux arcs (avec leurs valuations) en utilisantune autre couleur
pour les ́el ́ements ajout ́es.
(b) Justifier qu’on ne peut pas utiliser l’algorithme de Dijkstra ou celuide Bellman
simplifi ́e pour calculer les distances maximales dansK.
(c) On donne ci-dessous le calcul des distances maximales pour les graphesKetK −1
(obtenus avec l’algorithme de Bellman).` A partir de ces calculs, en d ́eduire
la dur ́ee minimale de r ́ealisation du nouveau projet et construire le tableau
r ́ecapitulant l’ordonnancement au plus tˆot, l’ordonnancement auplus tard pour
la dur ́eeT′ = 35 jours et les marges correspondantes.
tableau1:
DistPred
kx1234567891012345678910
000-∞-∞-∞-∞-∞-∞-∞-∞-∞0000000000
1100-∞-∞-∞-∞-∞16-∞-∞0100000100
12002-∞-∞-∞-∞16-∞-∞0120000100
130029-∞-∞616-∞-∞0123003100
14002918-∞1616-∞180123404104
15002918-∞1620-∞180123404504
17002918221620-∞180123474504
18002918241620-∞180123484504
110002918242321-∞18012348101004
270029182923212918012347101064
36002918292325341801234710664
tableau2:
DistPred
kx1234567891012345678910
00-∞-∞-∞-∞-∞-∞-∞-∞0-∞0000000000
19-∞-∞-∞-∞-∞5-∞-∞0-∞0000090000
26-∞-∞-∞-∞-∞51190-∞0000096600
27-∞-∞1518-∞51190160077096607
2825-∞15181151190168077896607
21025-∞152511511901680710896607
332517152511511901683710896607
342517322511511901683410896607
432534322511511901683410896607
523434322511511901623410896607(d) `
A partir de la question pr ́ec ́edente dire si un retard de 3 jours sur la tˆacheA4 retarde la fin du projet ? De mˆeme pour un retard de 3 jours sur la tˆacheA5 ?
Justifier.