Solucionador RCPSP

Pseudocódigo

RCPSP es CPM más recursos limitados, y esa única añadidura lo lleva de lineal a NP-difícil. El enfoque práctico es una heurística de planificación en serie guiada por una regla de prioridad.

RCPSP(actividades, dependencias, capacidades):
    orden = ordenacionTopologica(actividades)
    ordenar el orden por una regla de prioridad
    // p. ej. holgura mínima, o mayor duración primero

    para cada actividad a en el orden priorizado:
        t = max(fin[p] para p predecesora de a)
        mientras algun recurso r esté saturado en
              [t, t + duracion[a]):
            t = t + 1        // retrasar hasta que quepa
        inicio[a] = t; fin[a] = t + duracion[a]
        reservar los recursos de a durante ese intervalo

    duracion del proyecto = max(fin[a])

La diferencia con CPM es que el inicio de una actividad ya no viene fijado únicamente por sus predecesoras: puede verse empujado más tarde porque otra actividad no relacionada está ocupando la máquina. Eso rompe la propiedad que hacía lineal a CPM, ya que la decisión sobre una actividad ahora afecta a actividades con las que no tiene ninguna dependencia. Por eso ninguna cantidad de programación dinámica sobre el orden topológico basta.

Ejemplo resuelto, paso a paso

Planifica cuatro actividades que compiten por un único recurso con capacidad 1, y compara el resultado con lo que predeciría CPM.

Grafo de ejemplo: Actividades A (3 días), B (2 días), C (4 días) y D (2 días), con A y B precediendo a C, y C precediendo a D. Todas requieren la misma máquina, de la que solo hay una unidad.

1. Lo que diría CPM. Sin límite de recursos, A y B se ejecutan en paralelo desde el instante 0, C empieza en 3 y D acaba en 9. Duración del proyecto: 9 días.
2. Aplicar el límite de recursos. A y B necesitan ambas la máquina y solo hay una. Ya no pueden solaparse, así que una debe esperar. La priorización decide cuál.
3. Regla de prioridad: mayor duración primero. A dura 3 y B dura 2, así que A va primero, ocupando la máquina de 0 a 3. B tiene que esperar y se ejecuta de 3 a 5.
4. Planificar C. C necesita que A y B hayan terminado, es decir el instante 5, y la máquina está libre entonces. C se ejecuta de 5 a 9.
5. Planificar D. D sigue a C y se ejecuta de 9 a 11. La duración del proyecto es de 11 días.

Con recursos ilimitados el proyecto dura 9 días; con una sola máquina dura 11. Los dos días adicionales no proceden de ninguna dependencia, sino puramente de la contención por el recurso. Fíjate además en que el concepto de camino crítico se vuelve resbaladizo aquí: la ruta que gobierna la fecha de fin ahora incluye la espera de B por la máquina, que no es una relación de precedencia en absoluto. Por eso los calendarios de CPM sobre proyectos con recursos escasos resultan sistemáticamente optimistas.

Complejidad y de dónde sale

Tiempo: NP-difícil; la heurística en serie es O(V^2 · R) · Espacio: O(V · R)

La heurística de planificación en serie procesa cada una de las V actividades una vez y, para cada una, puede tener que avanzar el instante de inicio comprobando la disponibilidad de los R recursos, lo que da del orden de O(V al cuadrado por R) en el peor caso con una implementación directa. Eso es rápido y escala a miles de actividades. Lo que no hace es garantizar el óptimo. El RCPSP exacto es NP-difícil, y de hecho está considerado uno de los problemas de planificación más duros de la investigación operativa: las instancias de referencia con solo 60 actividades siguieron sin resolverse durante años. La ramificación y acotación exacta es viable en torno a 30 o 60 actividades según la estructura, y más allá de eso se recurre a metaheurísticas como algoritmos genéticos o búsqueda tabú.

Cuándo usar RCPSP (Programación de Proyectos con Recursos Limitados) y cuándo no

Elige según si los recursos son realmente limitantes y si necesitas una garantía de optimalidad.

Errores frecuentes

• Planificar con CPM y añadir los recursos después. Un calendario de CPM supone paralelismo ilimitado. Intentar encajar después los límites de recursos casi siempre alarga el proyecto, como en el ejemplo donde 9 días pasan a ser 11. Los recursos deben formar parte del modelo desde el principio, no ser un ajuste posterior.
• Suponer que el camino crítico sigue significando lo mismo. Con recursos limitados, la secuencia que gobierna la fecha de fin puede incluir esperas por contención que no son relaciones de precedencia. El concepto análogo es la cadena crítica, que incorpora tanto dependencias como conflictos de recursos.
• Usar una única regla de prioridad y darlo por bueno. Reglas distintas, como holgura mínima, mayor duración primero o mayor número de sucesores, producen calendarios distintos y ninguna domina a las demás. Ejecuta varias y quédate con la mejor; es barato y suele mejorar el resultado de forma apreciable.
• Olvidar que los recursos pueden ser no renovables. Los recursos renovables, como máquinas o personas, se liberan al terminar la actividad. Los no renovables, como el presupuesto o el material, se consumen de forma permanente. Modelar los segundos como los primeros produce calendarios que gastan el presupuesto varias veces.
• Esperar que las instancias grandes se resuelvan de forma exacta. RCPSP es uno de los problemas duros clásicos. Las instancias de referencia de 60 actividades resistieron durante años a los métodos exactos. Si tu proyecto tiene cientos de tareas, planifica con heurísticas y valida por simulación en lugar de perseguir el óptimo.

Preguntas frecuentes

¿Qué es el RCPSP?

El problema de programación de proyectos con recursos limitados pide un calendario que respete tanto las relaciones de precedencia entre actividades como la disponibilidad limitada de recursos renovables, minimizando normalmente la duración total del proyecto. Es CPM con la hipótesis de recursos ilimitados eliminada.

¿Por qué el RCPSP es NP-difícil si CPM es lineal?

Porque los límites de recursos acoplan actividades que no tienen ninguna dependencia entre sí. En CPM el inicio de una actividad depende solo de sus predecesoras, lo que permite resolverlo con dos barridos en orden topológico. Con recursos, retrasar una actividad puede obligar a retrasar otra completamente ajena, y esa interacción global es la que hace explotar el espacio de búsqueda.

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

CPM supone que cualquier conjunto de actividades sin dependencias mutuas puede ejecutarse simultáneamente. RCPSP añade capacidades de recursos que impiden ese paralelismo. En el ejemplo anterior, el mismo proyecto dura 9 días bajo CPM y 11 bajo RCPSP con una sola máquina, y los dos días de diferencia son puramente contención de recursos.

¿Qué es una regla de prioridad en RCPSP?

Es la heurística que decide qué actividad planificar primero cuando varias están listas y compiten por el mismo recurso. Reglas habituales son holgura mínima, mayor duración primero, mayor número de sucesores o fecha de fin más tardía más temprana. Ninguna es siempre mejor, así que en la práctica se ejecutan varias y se conserva el mejor calendario.

¿Para qué se usa el RCPSP?

Para programar líneas de producción donde las máquinas son limitadas, asignar cuadrillas y equipos en construcción, planificar carteras de proyectos que comparten personal especializado, y en general en cualquier planificación donde las tareas compiten por una capacidad finita en lugar de poder ejecutarse libremente en paralelo.