Desarrollo de un algoritmo genético para resolver el problema de programación de proyectos con recursos restringidos (rcpsp) y duración aleatoria, soportado en un esquema de generación de secuencias en paralelo

Abstract

En la presente investigación se aborda el Problema de Programación de Proyectos con Recursos Restringidos (Resource Constrained Project Scheduling Problem, RCPSP) con duración de actividades aleatoria, el cual consiste en programar actividades de un proyecto cumpliendo las restricciones de precedencias y la disponibilidad de recursos, a fin de obtener una programación base, que logre minimizar el tiempo de ejecución del proyecto bajo diferentes escenarios simulados. Para dar solución a este problema se diseñó un algoritmo genético (AG) soportado en un esquema de generación de secuencias (SGS) en paralelo, en donde se representó el cromosoma como una lista de actividades. La población inicial se generó mediante un esquema generador de secuencias (SGS) en serie, usando como reglas de prioridad el tiempo de finalización más lejano de la actividad (LFT) y el mayor peso posicional de rango de la actividad (GRPW). Para evaluar la aptitud de cada individuo se usó un esquema generador de secuencias (SGS) en paralelo, que utilizó como regla de prioridad una lista de actividades para calcular en n diferentes escenarios el makespan esperado. Como operadores genéticos se utilizaron el cruce y la mutación. El algoritmo propuesto se comparó con un procedimiento de optimización basado en el método de duraciones redundantes propuesto en el artículo titulado An optimization model to solve the resource constrained project scheduling problem RCPSP in new product development projects (Ortíz Pimiento & Diaz Serna, 2020), utilizando 10 instancias de prueba j30 y 10 instancias de prueba j60 de la librería PSPLIB, los resultados obtenidos demuestran un rendimiento similar en ambos métodos, para la mayoría de los criterios evaluados