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 2

Analytic and Heuristic Methodologies for Solving the Resource Constrained Project Scheduling Problem (RCPSP): a Review. Part 2

En este artículo se exponen y detallan los métodos de solución metaheurísticos más relevantes para el Problema de Programación de Tareas con Recursos Restringidos, RCPSP. Se realiza una revisión crítica del estado del arte, basada en el análisis de los trabajos más significativos publicados en la literatura académica sobre el tema. Inicialmente se presentan diversos métodos metaheurísticos, especialmente aquellos que se han implementado para problemas de secuenciación, destacando sus principales características, así como sus ventajas y desventajas. Además, se presentan los llamados Esquemas Generadores de Secuencias y los índices de complejidad más comúnmente utilizados. Finalmente, se muestra la librería de prueba PSPLIB, usada en la mayoría de trabajos académicos.

1 INTRODUCCIÓN

Dentro de los problemas de secuenciación de actividades, uno de los más estudiados es el de programación de tareas con recursos restringidos (Resource Constrained Project Scheduling Problem: RCPSP). Este es un problema combinatorio NP-hard cuyo propósito es encontrar los tiempos de inicio de un conjunto de actividades que constituyen un proyecto, con la finalidad de minimizar su tiempo de ejecución total, a la vez que deben cumplir dos conjuntos de restricciones: el primero, denominado de relaciones de precedencia y el segundo, de capacidad de recursos renovables.

De acuerdo a [1], el RCPSP puede definirse de la siguiente manera: sea un proyecto constituido por un conjunto X = (1, ... , n) de actividades y un conjunto de S = (1, ... ,m) de recursos, donde cada recurso k  S tiene una disponibilidad total b_k en cada intervalo de tiempo. Cada actividad i  X tiene un tiempo de procesamiento constante di, cuya ejecución requiere de una cantidad constante r_ik del recurso k. Las interrupciones de las actividades no son permitidas y los tiempos de preparación se asumen dentro de los tiempos de procesamiento e independientes de las actividades. Las actividades ficticias 1 y n representan el inicio y la finalización del proyecto, con duración y consumo de recursos iguales a cero.

2 ENFONQUES DE SOLUCIÓN

Los enfoques que se han usado para la solución del RCPSP son exactos y de aproximación. Los primeros garantizan una solución óptima, siempre que ésta exista; sin embargo, en problemas grandes o muy complejos podría hacerse inviable ya que el tiempo de cómputo crece en forma exponencial con el tamaño del problema.