mpm.py

Note de lecture générée automatiquement

Le vrai fichier est scripts/maths/mpm.py (Obsidian n’affiche pas les scripts eux-mêmes). Ne modifie pas cette note : modifie le script, puis relance python3 generer_vues_obsidian.py dans le dossier scripts.

• À quoi il sert : Ordonnancement MPM complet
• Lancer (dans le dossier scripts/maths/) : python3 mpm.py "A:3: B:2:A C:4:A D:1:B,C"
• Fiche : M08 - Ordonnancement MPM
• Retour : 00 - Tous les scripts

Code

#!/usr/bin/env python3
"""
mpm.py — Ordonnancement par la méthode MPM (potentiels-tâches) :
dates au plus tôt, au plus tard, marges totales et libres, chemin critique.
 
Utilisation :
    python3 mpm.py "A:3: B:2:A C:4:A D:1:B,C"
    Format de chaque tâche  ->  Nom:Durée:Antériorités(séparées par des virgules, vide si aucune)
"""
import sys
 
 
def lire_taches(texte: str) -> dict:
    taches = {}
    for bloc in texte.split():
        nom, duree, anteriorites = (bloc.split(":") + [""])[:3]
        taches[nom] = {"duree": float(duree),
                       "pred": [p for p in anteriorites.split(",") if p]}
    return taches
 
 
def ordre_topologique(taches: dict) -> list:
    ordre, places = [], set()
    while len(ordre) < len(taches):
        prets = [t for t in taches if t not in places and all(p in places for p in taches[t]["pred"])]
        if not prets:
            raise ValueError("Antériorités circulaires : impossible d'ordonnancer.")
        for t in sorted(prets):
            ordre.append(t)
            places.add(t)
    return ordre
 
 
def mpm(taches: dict) -> None:
    ordre = ordre_topologique(taches)
    successeurs = {t: [s for s in taches if t in taches[s]["pred"]] for t in taches}
 
    # Passage AVANT : date au plus tôt = max(tôt(pred) + durée(pred))
    tot = {}
    for t in ordre:
        tot[t] = max((tot[p] + taches[p]["duree"] for p in taches[t]["pred"]), default=0)
    fin_projet = max(tot[t] + taches[t]["duree"] for t in taches)
 
    # Passage ARRIÈRE : date au plus tard = min(tard(succ)) - durée(t)
    tard = {}
    for t in reversed(ordre):
        limite = min((tard[s] for s in successeurs[t]), default=fin_projet)
        tard[t] = limite - taches[t]["duree"]
 
    print(f"{'Tâche':<6}{'Durée':>6}{'Tôt':>6}{'Tard':>6}{'M.tot':>7}{'M.lib':>7}  Antériorités")
    for t in ordre:
        marge_totale = tard[t] - tot[t]
        debut_succ = min((tot[s] for s in successeurs[t]), default=fin_projet)
        marge_libre = debut_succ - tot[t] - taches[t]["duree"]
        critique = "  ← critique" if marge_totale == 0 else ""
        print(f"{t:<6}{taches[t]['duree']:>6g}{tot[t]:>6g}{tard[t]:>6g}{marge_totale:>7g}{marge_libre:>7g}"
              f"  {','.join(taches[t]['pred']) or '-'}{critique}")
 
    print(f"\nDurée minimale du projet : {fin_projet:g}")
    critiques = [t for t in ordre if tard[t] - tot[t] == 0]
    print(f"Tâches critiques (chemin critique) : {' → '.join(critiques)}")
 
 
if __name__ == "__main__":
    if len(sys.argv) != 2:
        sys.exit(__doc__)
    mpm(lire_taches(sys.argv[1]))