Pianificazione di un progetto (CPM)

P

Un progetto è un insieme di attività di durata nota legate da precedenze. Nel grafo del progetto ogni attività è un arco (i,j)(i,j) con durata dijd_{ij} e ogni nodo è un evento; i nodi sono in ordine topologico, da 1 (inizio) a nn (fine). Con tit_i istante dell'evento ii, si cerca la durata minima del progetto e le attività che non possono ritardare.

min⁡ tns.a. t1=0tj≥ti+dij∀ (i,j)∈At≥0\begin{aligned} \min\ & t_n\\ \text{s.a.}\ & t_1=0\\ & t_j\ge t_i+d_{ij} && \forall\,(i,j)\in A\\ & t\ge 0 \end{aligned}

Perché è facile

Il grafo del progetto è aciclico e la durata minima è la lunghezza del cammino più lungo da 1 a nn. Il CPM la calcola con una passata in avanti e una all'indietro, esaminando ogni arco una volta per passata: O(m)O(m).

Da ricordare

  • Un'attività (i,j)(i,j) è critica se lo slittamento tmax⁡[j]−tmin⁡[i]−dijt_{\max}[j]-t_{\min}[i]-d_{ij} vale 0; avere tmin⁡=tmax⁡t_{\min}=t_{\max} su entrambi gli estremi non basta.
  • Il cammino più lungo è un cammino minimo con costi −dij-d_{ij}: Dijkstra non si può usare, Floyd-Warshall sì ma costa O(n3)O(n^3).
  • Le precedenze che non si esprimono con i nodi diventano archi fittizi di durata 0.

Algoritmi

Fonti: dispensa §4.6, §4.6.1 e §4.6.2, appunti Lezione 11, §1-3.