TP3

Le but de ce TP est de résoudre des problèmes d'ordonnancement. Pour cela, on résoudra & implémentera l'exercice 2 du TD3.

Le fait de tester toutes vos créations n'est plus explicitement demandé car cela doit toujours être fait.

La donnée de départ n'est pas un graphe, mais le "tableau des contraintes" tel qu'il est donné en TD. Concrètement :

OBTENTION = "Obtention Permis"
ADDUCTION = "Adduction Eau EdF"
MURS = "Fondations + Murs"
CHARPENTE = "Charpente"
TOITURE = "Toiture"
PLAFOND = "Plafond"
CLOISONS = "Cloisons"
PLOMBERIE = "Plomberie"
ELECTRICITE = "Electricite"
PLATRE = "Platre"
 
DUREE = "duree"
PREDECESSEUR = "predecesseurs"
 
CONTRAINTES = {
    OBTENTION: {DUREE: 6, PREDECESSEUR: []},
    ADDUCTION: {DUREE: 3, PREDECESSEUR: []},
    MURS: {DUREE: 5, PREDECESSEUR: [OBTENTION, ADDUCTION]},
    CHARPENTE: {DUREE: 2, PREDECESSEUR: [MURS]},
    TOITURE: {DUREE: 2, PREDECESSEUR: [CHARPENTE]},
    PLAFOND: {DUREE: 2, PREDECESSEUR: [TOITURE]},
    CLOISONS: {DUREE: 3, PREDECESSEUR: [PLAFOND]},
    PLOMBERIE: {DUREE: 3, PREDECESSEUR: [PLAFOND, CLOISONS]},
    ELECTRICITE: {DUREE: 2, PREDECESSEUR: [PLAFOND, CLOISONS]},
    PLATRE: {DUREE: 3, PREDECESSEUR: [PLAFOND, CLOISONS, PLOMBERIE, ELECTRICITE]}
    }

On recopiera donc le code ci-dessus dans un fichier.

Les variables globales (CHARPENTE = "Charpente", …) permettent d'utiliser la complétion automatique de pycharm (celle-ci ne marche pas sur les chaines de caractères).

Dans un autre fichier, on écrira un programme qui, à partir de ces données, construira un graphe qui sera implémenté sous la forme d'un dictionnaire.
Les clés du dictionnaire seront (tous) les sommets, &, à chaque clé K sera associé un (sous-)dictionnaire. Les clés en seront (tous) les sommets. À chaque clé K' sera associé un nombre :

0 si K = K'
la longueur de l'arc K —> K' si celui-ci existe
-1 sinon.

On fera attention à ne pas oublier les sommets "alpha" (qui est relié aux sommets sans prédécesseurs) & "omega" (à qui sont reliés les sommets sans successeurs).

À partir de ce graphe, on calculera les dates au plus tôt & dates au plus tard de chaque tâche, & on déterminera les tâches critiques.