Metodologías Analíticas y Heurísticas para la Solución del Problema de Programación de Tareas con Recursos Restringidos (RCPSP): una revisión. Parte 1

Analytic and Heuristic Methodologies for Solving the Resource Constrained Project Scheduling Problem (RCPSP): a review Part 1

En este artículo se enuncian y describen los métodos de solución más relevantes para el Problema de la Programación de Proyectos con Recursos Restringidos, RCPSP. Se realiza una revisión crítica del estado del arte basado en los trabajos más significativos publicados en la literatura académica sobre el tema. Primero se explican varios métodos de solución exactos y se detallan sus principales ventajas y desventajas, donde se menciona que los mejores algoritmos exactos para la solución de este problema, son los métodos de ramificación y acotamiento o Branch and Bound. Posteriormente, se presentan diversos métodos heurísticos, especialmente aquellos que se han implementado para problemas de secuenciación.

1 INTRODUCCIÓN

Los problemas de secuenciación de actividades tienen como propósito la asignación óptima, en el tiempo, de los recursos escasos. De manera específica el término secuenciación, en investigación operativa, hace referencia a un caso particular de la programación que se entiende como la ordenación de una serie de actividades que guardan alguna relación; la programación, puede llevarse a un caso más general, donde, no sólo se asigne en el tiempo la ejecución de una actividad, sino, por ejemplo se puede asignar el uso de recursos como personas. Uno de los problemas más estudiados, en este contexto, es la programación de tareas con recursos restringidos (Resource Constrained Project Scheduling Problem: RCPSP).

En este trabajo se muestran los orígenes y la evolución de las metodologías de solución reportadas en la literatura más utilizadas para el RCPSP. Además, se propone una clasificación de estas metodologías como respuesta al uso de varios términos ambiguos y a la falta de claridad de algunos conceptos encontrados en la literatura. Se sintetiza la información encontrada, para brindar al lector una visión conceptual clara y objetiva de los métodos de solución tanto exactos como heurísticos.

El interés en este problema se debe, entre otras razones, a su gran aplicabilidad en la programación de tareas tanto a nivel empresarial como en el ámbito académico. Debido a su complejidad y naturaleza combinatoria, este tipo de problemas es conocido en la literatura como perteneciente a la clase NP-Hard [1], [2]; es decir, el espacio muestral de soluciones factibles crece de manera no polinomial con el número de actividades.

2 DESCRIPCIÓN DEL PROBLEMA

De manera formal puede definirse el RCPSP de la siguiente manera [3]: Sea un proyecto compuesto por un conjunto de n actividades X = (1,..., n), cada una de las cuales utiliza una cantidad de recursos r_ik para su realización, donde i es la actividad y k es el recurso.