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 bk en cada intervalo de tiempo. Cada actividad i X tiene un tiempo de procesamiento constante di, cuya ejecución requiere de una cantidad constante rik 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.
Esta es una versión de prueba de citación de documentos de la Biblioteca Virtual Pro. Puede contener errores. Lo invitamos a consultar los manuales de citación de las respectivas fuentes.
Artículo:
Estudio comparativo de las herramientas empleadas para el diseño de procesos
Artículo:
Un modelo de programación no lineal para la planeación de la producción de gas y petróleo
Artículo:
Integración de la teoría de grafos y el enfoque matricial con un proceso analítico jerárquico difuso para selección de equipos
Video:
Introducción a flujos de redes y al algoritmo Ford-Fulkerson
Artículo:
Planificación Móvil: Nuevos Enfoques de la Dirección Estratégica en las Instituciones de Educación Superior
Folleto:
Análisis de rentabilidad económica y financiera
Artículo:
¿Por qué debemos conservar la fauna silvestre?
Artículo:
Control y vigilancia de la calidad del agua de consumo humano
Manual:
Deshidratación y desecado de frutas, hortalizas y hongos. Procedimientos hogareños y comerciales de pequeña escala