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

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 :

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

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

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