📝
Enunciado
notion image
En el ejemplo se muestra una tabla donde nos indican varias cosas
  • Número de actividad (k)(k) → Lo usaremos para dar un nombre al nodo que representa la actividad en el grafo
  • Duración → Este valor será importante y también aparecerá en el nodo para poder identificar el valor que hemos de añadir al tiempo total cuando recorremos una arista
  • Actividades precedentes → Dependencias del nodo actual, las aristas irán dirigidas desde los nodos que aparezcan en esta columna hasta el nodo actual.
      • ⚠️ Puede ser que en lugar de precedentes aparezca sucesivas u otro término que indique las actividades que dependen de la actividad actual
📝
Representación
notion image
  • Dibujamos un grafo dirigido
  • Intentaremos que los nodos aparezcan a la derecha de todas sus dependencias, intentando mantener la linealidad del grafo
  • Todas las aristas salientes de un grado tienen el mismo peso (duración de la actividad del nodo de origen)
  • Dibujaremos los pesos una esquina del nodo
  • Dibujaremos un nodo INICIO y un nodo FIN
    • El nodo INICIO apuntará a todas las actividades que no tienen precedentes, sus aristas tienen peso/duración 00
    • El nodo FIN será apuntado por todos los nodos que no sean predecesor de ningún otro nodo.

Cálculo del ES y EF de cada nodo

notion image
  • Dibujaremos una cruz junto a cada nodo
      • ES
      EF
      LS
      LF
  • El el ESES y EFEF del nodo inicio será siempre 00
  • El ESES será igual que el máximo valor de EFEF de los nodos precedentes
  • El EFEF será el ES+dES+d
  • El EFEF del nodo FIN será igual que su ESES

Cálculo de los LS y LF

💡 Este paso se calcula desde es final desde el nodo FIN hacia el INICIO
notion image
  • El valor del LSLS y LFLF del nodo FIN vale lo mismo que ESES y EFEF
  • El valor del LFLF de un nodo es el mínimo valor de LSLS de todos sus sucesores
  • El valor de LSLS será LF−dLF - d
  • El valor de LSLS y LFLF del nodo inicio será lo mismo
🧠
Camino crítico y Holguras
🔒
El camino crítico será aquellos nodos cuyos valores de ESES y LSLS sean iguales, así como los de EFEF y LFLF. Esto significan que estas serán actividades que no admitiran retrasos
notion image
📏
La holgura será la resta entre el LSLS y el ESES
Por ejemplo
  • H1=0H_1 = 0
  • H2=10H_2 = 10
  • H5=24H_5 = 24
📏
La holgura libre se calculará de la siguiente manera
HL=ESmin.sig−ES−dH_L = ES_{min.sig}-ES-d
💡 En este ejemplo, todos los nodos tienen HL=HH_L = H, ya que para que la holgura libre pueda ser diferente de la holgura normal, tiene que haber al menos dos nodos seguidos con holgura, osea, dos nodos seguidos que no formen parte del camino crítico
  • HL≤HH_L \leq H
🧮
Modelización
mint4s.a.t1≥0t2≥0t3≥t1+15t3≥t2+5t4≥t3+4...t10≥t9+20t10≤80t≥0\begin{matrix} min && t4\\ s.a. && t1 ≥ 0\\ && t2 ≥ 0\\ && t3 ≥ t1 + 15\\ && t3 ≥ t2 + 5\\ && t4 ≥ t3 + 4\\ && . . .\\ && t10 ≥ t9 + 20\\ && t10 ≤ 80\\ && t ≥ 0 \end{matrix}