Calculadora de Ruta Crítica

Pseudocódigo

Dos barridos sobre la red de actividades en orden topológico: hacia adelante para lo más pronto que puede ocurrir cada tarea, hacia atrás para lo más tarde que puede ocurrir sin retrasar el proyecto.

CPM(actividades, dependencias):
    orden = ordenacionTopologica(actividades)

    // Barrido hacia adelante: inicio y fin más tempranos
    para cada actividad a en orden:
        ES[a] = max(EF[p] para p predecesora de a), o 0
        EF[a] = ES[a] + duracion[a]
    T = max(EF[a] sobre todas las a)   // duración del proyecto

    // Barrido hacia atrás: inicio y fin más tardíos
    para cada actividad a en inverso(orden):
        LF[a] = min(LS[s] para s sucesora de a), o T
        LS[a] = LF[a] - duracion[a]

    holgura[a] = LS[a] - ES[a]
    camino crítico = actividades con holgura 0

El camino crítico es el camino más largo por la red, no el más corto, lo que convierte esto en un problema de maximización sobre un DAG y no en uno de camino mínimo. Como la red es acíclica, ambos barridos son simplemente programación dinámica en orden topológico y no hace falta ninguna cola de prioridad. Holgura cero significa que la actividad no tiene margen: retrásala un día y el proyecto entero se desplaza un día.

Ejemplo resuelto, paso a paso

Planifica un proyecto de cuatro actividades donde dos tareas pueden ejecutarse en paralelo pero ambas deben terminar antes de que empiece la tercera.

Grafo de ejemplo: Actividades con duraciones A (3 días), B (2 días), C (4 días) y D (2 días). Dependencias: A y B deben preceder a C, y C precede a D.

1. Barrido hacia adelante, A y B. Ninguna tiene predecesora, así que ambas empiezan en el instante 0. A termina en 3, B termina en 2. Se ejecutan en paralelo.
2. Barrido hacia adelante, C. C espera a ambas, así que su inicio más temprano es el máximo de 3 y 2, es decir 3. Dura 4 días y termina en 7. Fíjate en que B acabó un día antes y simplemente espera.
3. Barrido hacia adelante, D. D empieza en 7 y termina en 9. Nada la sigue, así que la duración del proyecto es de 9 días.
4. Barrido hacia atrás. Retrocediendo desde 9: D debe empezar como muy tarde en 7, así que C debe terminar en 7 y empezar en 3. Tanto A como B deben terminar, por tanto, en 3, lo que da a A un inicio más tardío de 0 y a B un inicio más tardío de 1.
5. Calcular la holgura. A tiene inicio más tardío 0 frente a inicio más temprano 0, así que holgura 0. B tiene inicio más tardío 1 frente a inicio más temprano 0, así que holgura 1. C y D tienen ambas holgura 0.

El proyecto dura 9 días y el camino crítico es A a C a D. B tiene un día de margen, es decir puede empezar un día tarde o alargarse un día sin afectar a la fecha de fin. Este es el resultado práctico: le dice a un gestor exactamente dónde concentrar la atención. Acortar B no sirve de nada, mientras que acortar cualquiera de A, C o D acorta el proyecto entero, al menos hasta que el camino crítico se desplace y pase por B.

Complejidad y de dónde sale

Tiempo: O(V + E) · Espacio: O(V)

Una ordenación topológica cuesta O(V + E), y cada uno de los dos barridos visita cada actividad una vez y cada arista de dependencia una vez, así que ambos son también O(V + E). El espacio son cuatro números por actividad, el inicio y el fin más tempranos y más tardíos, es decir O(V). Todo el método es lineal, y por eso escala a redes de proyecto con cientos de miles de actividades. La red de dependencias debe ser un grafo dirigido acíclico: una dependencia circular no tiene orden topológico y, correspondientemente, ningún calendario válido, así que la detección de ciclos es un requisito previo real y no una formalidad.

Cuándo usar Método de la Ruta Crítica (CPM) y cuándo no

CPM supone duraciones conocidas y recursos ilimitados. Relajar cualquiera de esas dos hipótesis cambia el problema.

Errores frecuentes

• Tomar el mínimo en lugar del máximo en el barrido hacia adelante. Una actividad no puede empezar hasta que todas sus predecesoras hayan terminado, así que el inicio más temprano es el máximo sobre los finales de las predecesoras. Usar el mínimo produce un calendario imposiblemente corto y silenciosamente incorrecto.
• Suponer que el camino crítico es único. Varios caminos pueden empatar como los más largos, y entonces toda actividad de todos ellos tiene holgura cero. Acortar solo uno no sirve de nada, porque el otro camino crítico sigue gobernando la fecha de fin.
• Olvidar que el camino crítico se desplaza. Acorta lo suficiente una actividad crítica y otro camino pasa a ser el más largo. La compresión debe reevaluarse tras cada cambio en lugar de aplicarse de golpe a partir del análisis original.
• Ignorar los límites de recursos. CPM supone que A y B realmente pueden ejecutarse a la vez. Si ambas necesitan la misma máquina o a la misma persona, el calendario es ficción y hace falta RCPSP en su lugar.
• Ejecutarlo sobre una red con un ciclo. Una dependencia circular significa que no existe orden topológico y que ningún calendario es válido. Detecta el ciclo e infórmalo en lugar de producir números a partir de un orden parcial.

Preguntas frecuentes

¿Qué es el método del camino crítico?

CPM halla el camino más largo por una red de actividades y dependencias, lo que determina la duración mínima posible del proyecto. Las actividades de ese camino tienen holgura cero, de modo que cualquier retraso en ellas retrasa todo el proyecto. Se calcula con un barrido hacia adelante para los tiempos más tempranos y otro hacia atrás para los más tardíos.

¿Qué es la holgura o margen en CPM?

La holgura es el tiempo que una actividad puede retrasarse sin empujar la fecha de fin del proyecto, y se calcula como inicio más tardío menos inicio más temprano. Las actividades con holgura cero son críticas. En el ejemplo anterior, la actividad B tiene un día de holgura mientras que A, C y D no tienen ninguna.

¿Cuál es la complejidad temporal del método del camino crítico?

O(V + E), donde V son las actividades y E las dependencias. Es una ordenación topológica seguida de dos barridos lineales sobre la red, así que escala sin problema a planes de proyecto muy grandes.

¿Cuál es la diferencia entre CPM y PERT?

CPM usa una única duración determinista por actividad y se centra en identificar el camino crítico y las holguras. PERT usa tres estimaciones por actividad, optimista, más probable y pesimista, para calcular una duración esperada y una varianza, lo que permite indicar la probabilidad de terminar en una fecha dada. El análisis de la red en sí es el mismo.

¿Puede cambiar el camino crítico durante un proyecto?

Sí, y esa es la principal trampa práctica. Si una actividad crítica se acorta o una no crítica agota su margen, otro camino puede pasar a ser el más largo. El análisis debe rehacerse a medida que se conocen las duraciones reales, en lugar de tratarse como fijo en el momento de la planificación.