9.6 Il metodo del cammino critico¶
Parte 5 · Gestione dei progetti · Capitolo 9 · Capitolo 9: Gestione dei progetti · Dispensa, volume 5 (PDF) · Slide · Esercizi: Gestione dei progetti · App: Il metodo del cammino critico (CPM)
Algoritmo: Metodo del cammino critico (CPM)
STOP: le precedenze contengono un ciclo.STOP.Teorema 9.16: tempo di esecuzione del metodo del cammino critico
Il metodo del cammino critico richiede tempo \(O(n+m)\), dove \(m=|A|\).
Dimostrazione
-
Il Passo 0 costruisce gli archi dalle liste dei predecessori immediati, più al massimo \(2n\) archi di START e FINISH. L'ordine topologico richiede tempo \(O(n+m)\), con un contatore degli archi entranti di ogni nodo, come nel Capitolo 3.
-
Il Passo 1 esamina ogni arco una volta, come arco entrante nella sua testa; il Passo 2 esamina ogni arco una volta, come arco uscente dalla sua coda.
-
Il Passo 3 esamina ancora una volta gli archi uscenti da ogni attività, e segna gli archi stretti con un confronto per arco. □
- Il risultato fornisce il sottografo degli archi stretti, e i suoi cammini da START a FINISH sono i cammini critici (Teorema 9.15). Elencarli uno per uno può richiedere più tempo, quando sono molti.
9.6.1 Il diagramma di Gantt¶
Definizione 9.17: diagramma di Gantt
Il diagramma di Gantt di un calendario \(\vet{t}\) ha un asse dei tempi e una riga per ogni attività: la riga dell'attività \(j\) ha una barra da \(t_j\) a \(t_j+d_j\).
- Il diagramma mostra a colpo d'occhio quali attività sono in corso in ogni istante. Disegniamo il calendario al più presto \(\mathit{ES}\), con le barre delle attività critiche in blu e, per ogni attività non critica, un riquadro tratteggiato da \(\mathit{EF}_j\) a \(\mathit{LF}_j\) che ne mostra la scorta totale.
Esempio 9.6: il diagramma di Gantt del caso di studio
Il diagramma di Gantt del calendario al più presto del caso di studio, in settimane:
-
Le barre blu delle attività critiche si susseguono senza interruzioni dalla settimana \(0\) alla settimana \(44\): un ritardo su una qualsiasi di esse ritarda il progetto.
-
Alla settimana \(16\) le attività \(4\), \(5\) e \(9\) iniziano insieme: per (H2), tre squadre lavorano in parallelo.
-
I riquadri tratteggiati della catena \(4,7,8,13\) sono tutti lunghi \(4\) settimane, ma le barre della catena si susseguono: le \(4\) settimane di scorta sono condivise.
Il metodo del cammino critico costruisce la rete e un ordine topologico, esegue la passata in avanti e quella all'indietro e calcola le scorte, in tempo \(O(n+m)\). Il diagramma di Gantt del calendario al più presto mostra le attività in corso in ogni istante, il cammino critico e le scorte.