Vai al contenuto

9.6 Il metodo del percorso critico

Parte 5 · Gestione dei progetti · Capitolo 9 · Capitolo 9: Gestione dei progetti · Dispensa, volume 5 (PDF) · Esercizi: Gestione dei progetti

Algoritmo: Metodo del percorso critico (CPM)

Input: un progetto con attività \(1,2,\dots,n\), durate \(d_j>0\) e precedenze
Output: i tempi \(\mathit{ES}_j\), \(\mathit{EF}_j\), \(\mathit{LS}_j\), \(\mathit{LF}_j\), i margini, la durata minima del progetto \(T\) e gli archi stretti
1Passaggio 0 (rete). Costruisci la rete del progetto \(G=(N,A)\) e un ordine topologico: rimuovi ripetutamente un nodo senza inserire archi (l'indice più piccolo, se più di uno).
2 Se i nodi vengono lasciati e tutti hanno archi entranti, STOP: le precedenze contengono un ciclo.
3Passaggio 1 (passaggio in avanti). Imposta \(\mathit{ES}_0:=0\). Per ogni nodo \(j \neq 0\) in ordine topologico, impostare \(\mathit{ES}_j:=\max_{(i,j) \in \delta^-(j)} \mathit{EF}_i\); impostare \(\mathit{EF}_j:=\mathit{ES}_j+d_j\) per ogni \(j\) e \(T:=\mathit{ES}_{n+1}\).
4Passaggio 2 (passaggio all'indietro). Imposta \(\mathit{LF}_{n+1}:=T\). Per ciascun nodo \(j \neq n+1\) in ordine topologico inverso, impostare \(\mathit{LF}_j:=\min_{(j,k) \in \delta^+(j)} \mathit{LS}_k\); impostare \(\mathit{LS}_j:=\mathit{LF}_j-d_j\) per ogni \(j\).
5Passaggio 3 (pantaloni). Per ogni attività \(j\), impostare \(\mathit{TS}_j:=\mathit{LS}_j-\mathit{ES}_j\) e \(\mathit{FS}_j:=\min_{(j,k) \in \delta^+(j)} \mathit{ES}_k-\mathit{EF}_j\); mark the tight arcs, \(\mathit{ES}_j=\mathit{EF}_i\). I percorsi critici sono i percorsi di archi stretti da START a FINE.
6STOP.

Teorema 9.16: tempo di esecuzione del metodo del percorso critico

Il metodo del percorso critico viene eseguito nel tempo \(O(n+m)\), dove \(m=|A|\).

Dimostrazione

  1. Passo 0 crea gli archi dagli elenchi dei predecessori immediati, più al massimo gli archi \(2n\) di INIZIO e FINE. L'ordine topologico richiede tempo \(O(n+m)\), con un contatore degli archi entranti di ogni nodo, come in Capitolo 3.

  2. Il passo 1 scansiona ogni arco una volta, come un arco entrante della sua testa; Il passo 2 scansiona ogni arco una volta, come arco uscente la sua coda.

  3. Il passo 3 scansiona ancora una volta gli archi uscenti di ogni attività e contrassegna gli archi stretti con un confronto per arco. □

  • L'output fornisce il sottografo degli archi stretti e i suoi percorsi da INIZIO a FINE sono i percorsi 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 una pianificazione \(\vet{t}\) ha un asse temporale e una riga per ogni attività: la riga dell'attività \(j\) ha una barra da \(t_j\) a \(t_j+d_j\).

  • Il grafo mostra a colpo d'occhio quali attività sono in corso in ogni momento. Disegniamo il primo programma \(\mathit{ES}\), con le barre delle attività critiche in blu, e un riquadro tratteggiato da \(\mathit{EF}_j\) a \(\mathit{LF}_j\) che mostra le rallentamento totale di ciascuna attività non critica.

Esempio 9.6: il diagramma di Gantt del caso di studio

Il diagramma di Gantt della prima pianificazione del caso studio, in settimane:

Figura 6

  • Le barre blu delle attività critiche si susseguono senza interruzioni dalla settimana \(0\) alla settimana \(44\): un ritardo su nessuno di loro ritarda il progetto.

  • Nella settimana \(16\) iniziano insieme le attività \(4\), \(5\) e \(9\): da (H2), tre squadre lavorano in parallelo.

  • Le caselle tratteggiate della catena \(4,7,8,13\) sono tutte \(4\) lunghe settimane, ma le barre della catena si susseguono: le settimane di rallentamento \(4\) sono condivise.

Il metodo del percorso critico costruisce la rete e un ordine topologico, esegue i passaggi in avanti e all'indietro e calcola i margini in tempo \(O(n+m)\). Il diagramma di Gantt mostra le attività in corso in ogni istante e mette in evidenza il percorso critico.

Avanti: 9.7 Il modello di programmazione lineare