Teoría de grafos en la gestión de proyectos

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Por qué un calendario es un grafo

Todo plan de proyecto hace dos tipos de afirmación. La primera trata del trabajo: esta tarea dura nueve días. La segunda trata del orden: esta tarea no puede empezar hasta que termine aquella. Escribe cien de cada tipo y no habrás escrito una lista, habrás escrito un grafo. Las tareas son los vértices, las restricciones de orden son las aristas dirigidas y las duraciones son los pesos.

No es una forma de mirar los planes de proyecto. Es lo que un plan de proyecto es, y reconocerlo cambia lo que puedes preguntar. Una lista de tareas te dice cuánto trabajo hay. Solo el grafo te dice cuánto dura el proyecto, que es un número distinto y normalmente mucho mayor, porque el trabajo que no puede hacerse en paralelo tiene que hacerse en secuencia.

Las consecuencias son inmediatas y algo sorprendentes. La duración de un proyecto no es la suma de las duraciones de sus tareas, ni tampoco la mayor de ellas. Es la longitud del camino más largo a través de la red. Por eso el proyecto de este artículo reúne setenta y dos días de trabajo y aun así termina en treinta y nueve. Por eso añadir personas no ayuda automáticamente, por eso la tarea que preocupa a todos a menudo no es la que importa, y por eso un plan puede ser contradictorio consigo mismo de una forma que ningún esfuerzo arreglará.

Las técnicas de este artículo se inventaron con un año de diferencia, ambas bajo presión comercial y militar, y ambas por personas que sabían que estaban resolviendo un problema de grafos. En 1959, James Kelley en Remington Rand y Morgan Walker en DuPont publicaron el método de la ruta crítica, desarrollado para planificar la parada y el rearranque de plantas químicas, donde cada día de inactividad costaba dinero de verdad. Ese mismo año, la Special Projects Office de la Marina de EE. UU. publicó PERT, creado para gestionar el programa de misiles Polaris, donde el problema no era el coste sino la pura incertidumbre de un trabajo que nadie había hecho antes. Ambos artículos describen redes de actividades, y ambos calculan el camino más largo.

Lo que sigue construye un proyecto pequeño de forma explícita, trece actividades con duraciones reales, y responde sobre él todas las preguntas habituales de la programación: cuánto dura, qué es crítico, qué puede retrasarse, cuánta confianza merece la fecha, cuánto cuesta ir más rápido y qué pasa cuando no hay suficientes personas. Cada número se calculó, y cada resultado se volvió a calcular con un segundo método antes de escribirlo.

2. Actividades, dependencias y los cuatro tipos de relación

Hay dos convenciones para dibujar un proyecto como grafo, y conviene conocer ambas porque la más antigua todavía aparece en los libros de texto.

En la red de actividades en nodos (AoN, activity-on-node), cada actividad es un vértice y cada flecha es una dependencia. Es lo que usa el software moderno y lo que usa este artículo en todo momento. En la red de actividades en flechas (AoA, activity-on-arrow), cada actividad es una flecha y los vértices son eventos, los instantes en que un conjunto de actividades ha terminado. AoA fue la convención original de PERT y CPM, y tiene un inconveniente real: expresar ciertos patrones de dependencia obliga a insertar actividades ficticias de duración cero, que solo existen para que la lógica cuadre. AoN no necesita actividades ficticias, y esa es una de las razones por las que desplazó a AoA en la práctica.

La dependencia en sí no siempre es la simple. Hay cuatro tipos de relación estándar:

• Fin a inicio (FS): B no puede empezar hasta que A termine. El tipo por defecto y el único que usa este artículo.
• Inicio a inicio (SS): B no puede empezar hasta que A haya empezado. Útil para trabajo que avanza en paralelo, como la documentación que va unos días por detrás del desarrollo.
• Fin a fin (FF): B no puede terminar hasta que A termine.
• Inicio a fin (SF): B no puede terminar hasta que A haya empezado. Poco frecuente, y normalmente señal de que el plan quiere decir otra cosa.

Las relaciones también pueden llevar un desfase (lag), un retraso aplicado a la restricción: el hormigón necesita fraguar tres días antes de construir nada encima, así que la arista lleva un desfase de tres aunque nadie esté trabajando. Los desfases son pesos de las aristas, y todo lo de este artículo funciona con ellos sin cambios. Un desfase negativo, llamado adelanto, permite que una actividad empiece antes de que termine su predecesora; es legal, y también es una forma habitual de construir un plan que en realidad no puede ejecutarse.

Hay una regla que importa más que todo esto: el grafo debe ser acíclico. Si A espera a B y B espera a A, no existe ningún orden, y la sección 4 muestra exactamente qué aspecto tiene eso cuando un planificador se topa con ello.

3. El proyecto que usamos en todo el artículo

El ejemplo es el lanzamiento de una app móvil: trece actividades, dieciséis dependencias, duraciones en días laborables. Es lo bastante pequeño para comprobarlo a mano y lo bastante estructurado para mostrar todo lo que importa, en particular varios caminos de casi la misma longitud, que es donde vive la mayor parte del comportamiento interesante.

Lee la estructura, no las etiquetas. Los requisitos (A) abren tres corrientes paralelas: el desarrollo del producto a través del esquema de base de datos (C), el trabajo de diseño (B) y el de marketing (G). La corriente de desarrollo se divide de nuevo tras la API de backend (D) en frontend (E), pagos (F) y revisión de seguridad (I), y luego confluye dos veces, primero en las pruebas de integración (H) y después en el programa beta (J). El marketing solo se reincorpora en el envío (L).

Esos puntos de confluencia son donde se concentra la dificultad. Una actividad con varias predecesoras espera a la más lenta, y cuál es la más lenta no está fijado de antemano cuando las duraciones son inciertas. Las secciones 9 y 11 tratan, en el fondo, de lo que ocurre en una confluencia.

4. ¿El plan es siquiera posible?

Antes de preguntar cuánto dura un proyecto, pregúntate si se puede hacer. Una red de precedencias describe un plan válido solo si es un grafo dirigido acíclico. Si las dependencias contienen un ciclo, no hay ningún orden en el que pueda hacerse el trabajo, y el plan no va con retraso: es imposible.

La prueba es una ordenación topológica, y el algoritmo de Kahn es la versión que merece la pena conocer porque su forma de fallar es muy informativa. Toma repetidamente cualquier actividad sin predecesoras pendientes, anótala y elimínala. En este proyecto eso produce el orden A, B, C, D, E, F, G, H, I, J, K, L, M, las trece actividades, así que el plan es programable.

Supón ahora que alguien añade una única dependencia que suena razonable: el esquema de base de datos (C) no debería cerrarse hasta que las pruebas de integración (H) hayan revelado los patrones reales de consulta. Añade la arista de H a C y vuelve a ejecutar. El algoritmo de Kahn produce cuatro actividades y luego se detiene: A, B, G y K, el único trabajo que no queda atrapado en el bucle. Las nueve restantes están bloqueadas, cada una esperando a otra. El algoritmo no se limita a fallar: el conjunto que no pudo producir es el interbloqueo, que es exactamente el diagnóstico que necesita un planificador.

Esto importa en la práctica porque los planes reales los arman muchas personas, cada una añadiendo restricciones sensatas a nivel local, y nadie tiene el grafo entero en la cabeza. Las dependencias circulares son frecuentes, y el grafo las encuentra en tiempo lineal.

El orden topológico hace algo más que validar el plan. Como garantiza que cada predecesora aparece antes que sus sucesoras, permite calcular todo el calendario en una sola pasada sobre las actividades, sin iteraciones ni búsqueda. Por eso el método de la ruta crítica era práctico ya en el hardware de 1959, y por eso sigue siendo instantáneo en proyectos con cien mil tareas.

5. La ruta crítica: dos pasadas sobre el grafo

El método de la ruta crítica calcula cuatro números para cada actividad y deduce todo lo demás a partir de ellos.

La pasada hacia delante recorre las actividades en orden topológico y calcula lo pronto que puede ocurrir cada una. El inicio más temprano de una actividad es el mayor de los finales más tempranos de sus predecesoras, y su final más temprano es eso más su duración. Los requisitos empiezan el día 0 y terminan el día 4. El esquema de base de datos empieza entonces el 4 y termina el 7. La API de backend empieza el 7 y termina el 16. El desarrollo frontend espera tanto a la API (que termina el 16) como al diseño de UI (que termina el 14), así que empieza el 16, no el 14. Tras una pasada, el mayor final más temprano es la duración del proyecto: 39 días laborables.

La pasada hacia atrás recorre el mismo orden al revés y calcula lo tarde que puede ocurrir cada actividad sin empujar la fecha final. El final más tardío de una actividad es el menor de los inicios más tardíos de sus sucesoras. El lanzamiento debe terminar el 39, así que debe empezar el 38; el envío debe terminar el 38, así que empieza el 36; y así hasta el principio.

La diferencia entre ambas es la holgura total, lo que una actividad puede retrasarse antes de que se mueva el final del proyecto. Las actividades con holgura cero forman la ruta crítica.

La ruta crítica es A → C → D → E → H → J → L → M, y su longitud es exactamente los 39 días que dio la pasada hacia delante. No es una coincidencia sino un teorema: la duración del proyecto es igual a la longitud del camino más largo, y las actividades con holgura cero son exactamente las que están en un camino más largo. Cuando dos caminos empatan como los más largos, como ocurre en la sección 10, ambos son críticos.

De aquí se siguen dos cosas que conviene decir claramente. Primero, retrasar un día cualquier actividad crítica retrasa el proyecto un día, sin excepciones y sin amortiguación. Segundo, acelerar una actividad no crítica no cambia en absoluto la fecha final. La web de marketing podría terminarse en un solo día y el lanzamiento seguiría siendo el día 39. El esfuerzo fuera de la ruta crítica compra margen de seguridad, no tiempo.

Puedes ejecutar estas dos pasadas paso a paso sobre una red que dibujes tú mismo en el visualizador del método de la ruta crítica. Merece la pena fijarse en lo que es CPM matemáticamente. Encontrar un camino más largo es NP-difícil en un grafo general, porque permitiría resolver el problema del camino hamiltoniano. En un grafo dirigido acíclico se vuelve fácil, lineal en el número de actividades y dependencias, precisamente porque existe un orden topológico. Todo el valor práctico de CPM descansa en la aciclicidad que comprobó la sección 4.

6. La holgura, y a quién pertenece de verdad

La holgura es el número más útil de un calendario y el peor utilizado de forma sistemática. La confusión viene de que hay dos tipos.

La holgura total es lo que una actividad puede retrasarse sin empujar la fecha final del proyecto. La holgura libre es lo que puede retrasarse sin empujar el inicio más temprano de ninguna de sus sucesoras. En este proyecto, la revisión de seguridad (I) tiene 7 días de holgura total y 7 de holgura libre, porque el programa beta al que alimenta espera de todos modos a las pruebas de integración. El contenido (G) tiene 22 días de holgura total pero cero de holgura libre: retrásalo aunque sea un día y la web de marketing empieza un día más tarde.

Esa diferencia es exactamente la trampa. El contenido y la web de marketing muestran 22 días de holgura total cada una, y un responsable que lea el calendario fila a fila ve 44 días de margen aparente. Hay 22. La holgura pertenece al camino A → G → K → L → M, que dura 17 días dentro de un proyecto de 39, y las dos actividades la comparten.

El modelo lo hace tangible. Gasta los 22 días enteros en el contenido y el proyecto seguirá terminando el día 39, pero la holgura total de la web de marketing baja de 22 a cero: se ha vuelto crítica. Retrásala un día más y el proyecto pasa al día 40. No se sobrepasó nada, nada salió mal en ninguna tarea concreta, y la fecha se movió, porque el margen ya se había consumido antes.

La regla práctica es que la holgura total es una propiedad de un camino y la holgura libre es una propiedad de una actividad. La holgura libre es la parte que nadie más puede reclamar, y es el número que debes dar a un equipo como verdadero margen. En este proyecto solo cuatro actividades tienen alguna: B con 2 días, F con 1, I con 7 y K con 22.

7. La ruta crítica no siempre es crítica

La ruta crítica invita a una conclusión cómoda: vigila estas ocho actividades y el proyecto estará bajo control. La estructura de caminos de este proyecto muestra por qué eso no basta.

Hay cinco caminos. El crítico dura 39 días. El siguiente dura 38, pasando por los pagos en lugar del frontend. El tercero dura 37, pasando por el diseño de UI en lugar de la base de datos y la API. Esos dos no son críticos, pero su holgura es de uno y dos días, menos que el error de redondeo de la mayoría de las estimaciones.

Los profesionales lo llaman el problema del camino casi crítico (near-critical path), y tiene una consecuencia tajante: un plan puede tener varios caminos que en la práctica son todos críticos, y un responsable que solo vigile el oficial se verá sorprendido por un retraso en un camino que parecía seguro. Dos días de holgura en una tarea de diseño de diez días no son margen, son ruido.

La disciplina útil es ordenar los caminos por holgura en lugar de dividirlos en críticos y no críticos. En este proyecto, la clasificación 39, 38, 37, 32, 17 dice algo que un resaltado en rojo no puede decir: tres de los cinco caminos necesitan gestión activa y dos no. La sección 9 cuantifica exactamente con qué frecuencia cada uno acaba decidiendo la fecha.

8. PERT: ponerle una probabilidad a la fecha

CPM supone que todas las duraciones se conocen. Las duraciones de nadie se conocen. PERT, desarrollado para el programa Polaris en 1959, lo aborda pidiendo tres estimaciones por actividad en lugar de una: un tiempo optimista a, un tiempo más probable m y un tiempo pesimista b.

A partir de ellas calcula una duración esperada y una varianza para cada actividad:

t_e = (a + 4m + b) / 6   y   σ² = ((b − a) / 6)²

Los pesos vienen de aproximar la duración de cada actividad con una distribución beta, lo bastante flexible para ser asimétrica y acotada por ambos extremos, a diferencia de una distribución normal, que admitiría duraciones negativas. Las fórmulas son aproximaciones, y se eligieron en parte porque podían calcularse a mano en 1959.

Sumar a lo largo de la ruta crítica da una duración esperada del proyecto de 39 días con una varianza total de 3,778, es decir, una desviación típica de 1,944 días. A continuación se invoca el teorema central del límite: una suma de varias duraciones independientes es aproximadamente normal aunque las actividades individuales no lo sean, lo que permite leer probabilidades directamente de la curva.

El resultado es mucho más útil que una fecha. Terminar en 40 días tiene una probabilidad del 69,7 %; en 41 días, 84,8 %; en 42 días, 93,9 %. Dicho al revés: comprometerse a 39 días es comprometerse a lanzar una moneda, comprar tres días de contingencia eleva la confianza a cerca del 94 %, y un cuarto día la lleva al 98 %.

El visualizador de PERT hace este cálculo de forma interactiva, incluida la probabilidad de terminar para cualquier fecha objetivo. Ese cambio de enfoque es la verdadera aportación de PERT. Un calendario que da una sola fecha invita a la pregunta «¿llegaremos?», que no tiene respuesta honesta. Un calendario que da una distribución invita a «¿cuánta confianza quieres y cuánto va a costar?», que sí la tiene.

9. El sesgo de fusión: por qué PERT es optimista

PERT tiene un defecto: se identificó a los pocos años de su publicación y todavía hoy se ignora de forma rutinaria. El problema es que PERT calcula la distribución de la ruta crítica y luego la trata como la distribución del proyecto. No son lo mismo.

El proyecto no espera a la ruta crítica. Espera al camino que resulte ser el más largo en la práctica. Cuando varios caminos confluyen en una actividad, esa actividad empieza cuando llega el más lento de ellos, y el valor esperado de un máximo es mayor que el máximo de los valores esperados. Es la desigualdad de Jensen, y en programación de proyectos se llama sesgo de fusión. Van Slyke lo demostró mediante simulación de Monte Carlo en 1963, y MacCrimmon y Ryavec analizaron el tamaño del error en 1964.

Para medirlo, cada actividad de este proyecto se muestreó 200.000 veces de la distribución beta cuya media es exactamente su duración esperada de PERT, de modo que cualquier diferencia en el resultado es solo el sesgo de fusión y no un conjunto distinto de supuestos. La duración media simulada es de 39,34 días frente a los 39,00 de PERT. Más útil todavía: la probabilidad de terminar en 39 días es del 43,8 %, no del 50 % que sugiere PERT.

La estadística de caminos explica de dónde sale eso. En el conjunto de simulaciones, la ruta crítica nominal fue la más larga solo en el 64,0 % de las ejecuciones. El camino de los pagos ganó el 26,1 % de las veces, y el camino del diseño el 9,9 %. Uno de cada tres proyectos termina tarde por un motivo que el análisis de la ruta crítica nunca mencionó.

Un tercio de día de sesgo parece despreciable, y en este proyecto lo es. En general no lo es, y crece justo en las situaciones que describen los grandes programas: muchos caminos paralelos de longitud parecida, muchos puntos de confluencia y mucha varianza. Un calendario con veinte caminos casi iguales que confluyen en un hito puede estar sesgado en semanas.

De ahí salen dos respuestas prácticas. Primero, si la red tiene un paralelismo significativo, simúlala en lugar de propagar la varianza a lo largo de un camino; el cálculo son unas pocas líneas y tarda segundos. Segundo, da un percentil, no una media. El P80 de este proyecto es de 41,1 días y el P90 de 42,0. Esos son números con los que un equipo puede comprometerse. La media es el número que fallará la mitad de las veces, y algo más de la mitad cuando se cuenta el sesgo de fusión.

10. Compresión: comprar tiempo es un corte mínimo

Supón que 39 días son demasiados. Muchas actividades pueden acortarse gastando dinero: más personas, horas extra, un proveedor más rápido. En programación de proyectos esto se llama compresión (crashing), y cada actividad recibe dos números más: el máximo de días en que puede acortarse y el coste por día, su pendiente de coste.

El enfoque ingenuo es comprimir la actividad crítica más barata. Funciona exactamente una vez. El desarrollo frontend tiene la pendiente más baja de la ruta crítica, 350 $ al día, así que acortarlo lleva el proyecto de 39 a 38 días por 350 $. El esquema de base de datos es el siguiente, a 400 $, y lo lleva a 37.

Entonces la regla ingenua se rompe. A 37 días hay dos caminos críticos a la vez: el original y el de los pagos, que ahora duran 37 días cada uno. Acortar otra vez el desarrollo frontend no ahorra nada, porque los pagos seguirían con toda su duración y el proyecto seguiría tardando 37 días. Para ganar un día tienes que acortar todas las rutas críticas a la vez.

Esta es la estructura. Un conjunto de actividades cuyo acortamiento reduce todas las rutas críticas es un conjunto que toca todos los caminos del inicio al final del proyecto dentro de la subred crítica. Esa es la definición de un corte s-t. Da a cada actividad una capacidad igual a su coste por día, y la forma más barata de comprar un día es el corte mínimo de esa red. Por el teorema de flujo máximo y corte mínimo puede encontrarse en tiempo polinómico, que es la observación que Fulkerson y Kelley publicaron ambos en 1961.

Si el argumento de flujos no te resulta familiar, conviene repasar el teorema de flujo máximo y corte mínimo antes de seguir, ya que la compresión es una de sus aplicaciones más limpias fuera de las redes. Como las actividades son vértices y no aristas, cada una se divide en una copia de entrada y otra de salida unidas por un arco que lleva su pendiente de coste, mientras que las dependencias reales reciben capacidad infinita. El corte mínimo tiene entonces que estar formado por actividades, que es lo que realmente se puede comprar.

Aplicarlo al proyecto da el tercer paso: pasar de 37 a 36 días cuesta 650 $, y exige comprimir el desarrollo frontend y los pagos a la vez. Ninguno de los dos gana un día por sí solo, así que ninguna regla del tipo «elige la tarea crítica más barata» habría encontrado nunca la pareja. Las pruebas de integración sí funcionan solas, porque están en las dos rutas críticas, pero cuestan 800 $ frente a los 650 $ de la pareja.

Continuar hasta el límite produce la curva tiempo-coste completa: 27 días es la duración más corta alcanzable, con un coste total de compresión de 11.950 $. La curva es convexa, es decir, cada día extra cuesta al menos tanto como el anterior, lo que es una propiedad general de esta construcción y una comprobación útil de cualquier análisis de compresión que te presenten.

El entregable es la curva, no el punto final. Convierte una discusión sobre si el equipo puede «ir más rápido» en una lista de precios: tres días por 1400 $, seis días por 3650 $, doce días por 11.950 $. Si alguno merece la pena es una cuestión de negocio, pero ahora es una cuestión con números.

11. Recursos: donde la teoría deja de bastar

Todo lo anterior supone que, si dos actividades pueden ir en paralelo, van en paralelo. Eso supone personas ilimitadas, y ningún proyecto tiene personas ilimitadas. Decidir qué personas trabajan en qué turnos, en lugar de qué tareas se hacen cuándo, es el problema de cuadrantes relacionado que se resuelve en planificación de turnos de empleados.

Asigna a cada actividad una necesidad de personal y vuelve a mirar el calendario CPM. Si todo empieza lo antes posible, la demanda en este proyecto alcanza un máximo de siete personas del día nueve al día catorce, cuando la API de backend, el diseño de UI y la web de marketing están en marcha a la vez. Si el equipo tiene cinco personas, el calendario es ficción.

Añadir límites de recursos convierte el grafo de precedencias en el problema de programación de proyectos con recursos limitados (RCPSP), y el cambio de dificultad no es gradual. CPM es de tiempo lineal. RCPSP es NP-difícil, como demostraron Blazewicz, Lenstra y Rinnooy Kan en 1983, y es difícil en la práctica además de en la teoría: instancias de 60 actividades de la biblioteca de referencia PSPLIB siguieron sin resolverse durante años.

Merece la pena detenerse en los números. Con cinco personas el proyecto sigue terminando en 39 días: el pico de siete era un artefacto de la planificación, y mover trabajo a la holgura lo absorbe por completo. Con cuatro, el óptimo es de 49 días, un sobrecoste de plazo del 26 % que no aparece en ninguna parte del análisis de la red. Ambas cifras se verificaron con un branch and bound exhaustivo sobre todos los calendarios activos, algo viable solo porque el proyecto tiene trece actividades.

El visualizador de programación con recursos limitados te permite fijar una capacidad y ver cómo se estira el calendario. Como las soluciones exactas no escalan, en la práctica se usan reglas de prioridad: programar una y otra vez la actividad elegible mejor clasificada según alguna regla. La elección de la regla importa más de lo que parece. Con capacidad cuatro, la mínima holgura total da 49 días, que aquí resulta ser óptimo, mientras que el inicio tardío más temprano, la mayor duración primero y más sucesores primero dan todos 53. El mismo proyecto, la misma restricción, una diferencia del 8 % por una decisión de modelado que la mayoría de las herramientas toman en silencio por ti.

El punto más profundo es que, con restricciones de recursos, la ruta crítica pierde su significado. Dos actividades sin ninguna dependencia entre ellas pueden no poder ejecutarse a la vez, así que la cadena que realmente determina la fecha final puede incluir pares de actividades unidas solo por una persona compartida. Los valores clásicos de holgura ya no describen lo que puede retrasarse.

12. La cadena crítica, en breve

Esa observación es el punto de partida de la gestión de proyectos por cadena crítica, presentada por Eliyahu Goldratt en 1997. La cadena crítica es la secuencia de actividades más larga que tiene en cuenta tanto las precedencias como la competencia por los recursos, que es el objeto adecuado que vigilar cuando las personas escasean.

Su segunda idea se refiere a dónde se guarda el tiempo de seguridad. Las estimaciones individuales suelen ir acolchadas, y ese colchón se consume de todos modos, ya sea porque el trabajo se expande hasta llenar el tiempo disponible o porque se aprovecha una fecha de inicio cómoda. La cadena crítica quita el colchón de las actividades individuales y lo agrupa en colchones explícitos: un colchón de proyecto al final de la cadena y colchones de alimentación donde los caminos no críticos se unen a ella. Agruparlos es estadísticamente sólido, aunque por una razón distinta del sesgo de fusión: la desviación típica de una suma de duraciones independientes crece como la raíz cuadrada de cuántas hay, así que un colchón compartido puede ser más pequeño que los márgenes individuales que sustituye y aun así dar la misma protección.

El método es objeto de debate real. Herroelen y Leus, entre otros, han argumentado que sus afirmaciones sobre programación son más débiles de lo que se presentan y que reglas de dimensionado de colchones como «la mitad de la longitud de la cadena» no tienen base analítica. La idea de agrupar colchones es sólida; el marco que la rodea es un método de gestión y no un teorema, y conviene mantener ambas cosas separadas.

13. Qué es fácil y qué es difícil

La programación de proyectos tiene una frontera de complejidad inusualmente nítida, y saber dónde cae te dice qué promesas puede cumplir una herramienta.

Fácil, es decir, polinómico e instantáneo a cualquier tamaño realista. Detectar ciclos y producir un orden topológico. La pasada hacia delante y hacia atrás, y por tanto la duración del proyecto, la ruta crítica y todos los valores de holgura. Enumerar por holgura los caminos que importan. El corte mínimo para un día de compresión, y repitiéndolo, toda la curva tiempo-coste. La simulación de Monte Carlo de la distribución de la duración. Todo esto es lineal o casi lineal, y un proyecto con cien mil actividades no es ningún problema.

Difícil, es decir, NP-difícil y sin ningún algoritmo polinómico previsible. La programación con restricciones de recursos, en prácticamente todas sus variantes: capacidad fija, varios tipos de recursos, con o sin interrupción. La nivelación de recursos, que busca el perfil más suave en lugar del calendario más corto. Los compromisos tiempo-coste con opciones discretas por actividad en lugar de una pendiente continua, lo que hace perder la formulación de flujos. Enumerar todos los caminos, cuyo número puede crecer exponencialmente con el número de actividades.

El patrón es casi una regla práctica: pedir un calendario óptimo solo en tiempo es fácil, y añadir un recurso limitado y compartido lo vuelve difícil. Las dos excepciones de la lista difícil confirman la regla en lugar de romperla, porque ninguna pide un único óptimo: la enumeración de caminos pide todas las respuestas, y el compromiso discreto pide elegir de un menú en cada actividad. Las restricciones temporales son un orden parcial, y los órdenes parciales son lo que los grafos dirigidos acíclicos manejan bien. Un recurso compartido crea restricciones entre actividades sin ninguna dependencia entre ellas, y la estructura acíclica que lo hacía todo tratable ya no describe el problema.

Por eso el software de planificación da una ruta crítica exacta y un plan nivelado por recursos aproximado, normalmente sin decirlo. Lo primero es un teorema; lo segundo es una heurística cuya calidad nadie informa. Esto es un rincón de un campo mucho más amplio: la investigación operativa abarca los métodos de optimización que necesita la mitad difícil de esta lista.

14. Errores de modelado y cómo evitarlos

Cinco errores explican la mayoría de los malos calendarios, y ninguno tiene que ver con estimar mal.

Tratar la holgura como un colchón propio. La holgura total se comparte a lo largo de un camino. Dos equipos a los que se les dice que tienen tres semanas de margen, en el mismo camino, consumirán seis entre los dos y se sorprenderán cuando la fecha se mueva. Comunica a los equipos la holgura libre y guarda la holgura total como número de planificación.

Vigilar solo la ruta crítica. Un camino con dos días de holgura no es seguro, es casi crítico, y en este proyecto la ruta crítica nominal decide el resultado solo en dos de cada tres ejecuciones. Ordena los caminos por holgura y gestiona todo lo que esté a pocos días de cero.

Dar la media como fecha. La duración esperada es aproximadamente lanzar una moneda incluso antes del sesgo de fusión, y algo peor después. Si una fecha va a un contrato, debe ser un percentil, y hay que decir cuál.

Suponer independencia. Tanto la suma de varianzas de PERT como la simulación de la sección 9 suponen que las duraciones de las actividades son independientes. Normalmente no lo son: el mismo estimador optimista produjo varias, el mismo equipo ejecuta varias, y un mal proveedor afecta a varias a la vez. La correlación infla la varianza del total muy por encima de lo que indica cualquiera de los dos métodos, así que trata la dispersión como un mínimo y no como una estimación.

Planificar como si las personas fueran ilimitadas. Una fecha CPM calculada sin límites de recursos es una cota inferior, no un plan. Revisa el perfil de recursos antes de publicar la fecha; en este proyecto, la diferencia entre revisarlo y no hacerlo fue de diez días.

Un sexto merece mención porque es invisible: una dependencia que no es real. Los planes acumulan restricciones añadidas por comodidad, secuencias que reflejan cómo está organizado el equipo más que algo técnico. Añadir una arista solo puede alargar el camino más largo o dejarlo igual, nunca acortarlo, así que cada dependencia innecesaria es una apuesta de un solo sentido contra el calendario. Revisar la ruta crítica arista por arista, preguntando si cada una es una restricción real, suele ser la compresión de calendario más barata disponible, y a diferencia de la compresión con dinero, no cuesta nada.

16. Referencias

Los artículos detrás de los métodos de este artículo, en orden cronológico.

1. Clark, W. (1922). The Gantt Chart: A Working Tool of Management. Ronald Press.
2. Kelley, J. E. y Walker, M. R. (1959). “Critical-path planning and scheduling.” Proceedings of the Eastern Joint Computer Conference, 160–173.
3. Malcolm, D. G., Roseboom, J. H., Clark, C. E. y Fazar, W. (1959). “Application of a technique for research and development program evaluation.” Operations Research, 7(5), 646–669.
4. Fulkerson, D. R. (1961). “A network flow computation for project cost curves.” Management Science, 7(2), 167–178.
5. Kelley, J. E. (1961). “Critical-path planning and scheduling: mathematical basis.” Operations Research, 9(3), 296–320.
6. Ford, L. R. y Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.
7. Van Slyke, R. M. (1963). “Monte Carlo methods and the PERT problem.” Operations Research, 11(5), 839–860.
8. MacCrimmon, K. R. y Ryavec, C. A. (1964). “An analytical study of the PERT assumptions.” Operations Research, 12(1), 16–37.
9. Klingel, A. R. (1966). “Bias in PERT project completion time calculations for a real network.” Management Science, 13(4), B194–B201.
10. Wiest, J. D. (1967). “A heuristic model for scheduling large projects with limited resources.” Management Science, 13(6), B359–B377.
11. Elmaghraby, S. E. (1977). Activity Networks: Project Planning and Control by Network Models. Wiley.
12. Blazewicz, J., Lenstra, J. K. y Rinnooy Kan, A. H. G. (1983). “Scheduling subject to resource constraints: classification and complexity.” Discrete Applied Mathematics, 5(1), 11–24.
13. Kolisch, R. y Sprecher, A. (1997). “PSPLIB: a project scheduling problem library.” European Journal of Operational Research, 96(1), 205–216.
14. Goldratt, E. M. (1997). Critical Chain. North River Press.
15. Brucker, P., Drexl, A., Möhring, R., Neumann, K. y Pesch, E. (1999). “Resource-constrained project scheduling: notation, classification, models, and methods.” European Journal of Operational Research, 112(1), 3–41.
16. Herroelen, W. y Leus, R. (2001). “On the merits and pitfalls of critical chain scheduling.” Journal of Operations Management, 19(5), 559–577.
17. Demeulemeester, E. y Herroelen, W. (2002). Project Scheduling: A Research Handbook. Kluwer Academic Publishers.
18. Herroelen, W. y Leus, R. (2005). “Project scheduling under uncertainty: survey and research potentials.” European Journal of Operational Research, 165(2), 289–306.
19. Kolisch, R. y Hartmann, S. (2006). “Experimental investigation of heuristics for resource-constrained project scheduling: an update.” European Journal of Operational Research, 174(1), 23–37.
20. Hartmann, S. y Briskorn, D. (2010). “A survey of variants and extensions of the resource-constrained project scheduling problem.” European Journal of Operational Research, 207(1), 1–14.
21. Trietsch, D. y Baker, K. R. (2012). “PERT 21: fitting PERT/CPM for use in the 21st century.” International Journal of Project Management, 30(4), 490–502.