restricted:alg-1:tp4.5 [WiKi informatique]

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

====== TP4.5 ======

Pour aller plus loin que le tp4. En est la suite directe et concerne les tâches à durées variables. On considérera le graphe de contraintes suivant : 

  * tâche : A ; tâches antérieures : D F R ; durée 5
  * tâche : B ; durée  4
  * tâche : C ; tâches antérieures :  A H B ; durée  4
  * tâche : D ; tâches antérieures :  R ; durée  2
  * tâche : E ; tâches antérieures :  G S R ; durée  3
  * tâche : F ; tâches antérieures :  B ; durée  3
  * tâche : G ; tâches antérieures :  R ; durée  3
  * tâche : H ; tâches antérieures :  B ; durée  4
  * tâche : R ; durée 3
  * tâche : S ; tâches antérieures :  D F ; durée 2

===== Structure de graphe =====

Les durées ne sont plus forcément unitaires. Il faut prendre cela en compte dans la structure de graphe. Pour cela, à la place d'utiliser des ensemble pour les voisins, on utilisera un autre dictionnaire.

Ainsi, pour modéliser le graphe de contraintes, le sommet B à 3 voisins : C, F, H et à une durée de 4. On le codera ainsi : 
<code python>
graphe_contrainte = dict()

graphe_contrainte['B'] = dict()

graphe_contrainte['B']['C'] = 4
graphe_contrainte['B']['F'] = 4
graphe_contrainte['B']['H'] = 4

# ... reste du graphe
</code>

Codez ce graphe. Et ajoutez lui les tâches de départ et de fin d'une durée de 0.

===== Chemin critique et début des tâches =====

Modifiez les algorithmes du tp4 pour prendre en compte la durée des tâches. Testez le tout sur notre graphe des contraintes.