Publicación:

Solución al problema de programación de proyectos con restricción de recursos(rcpsp) mediante un algoritmo hibrico genético

Resumen

En la presente investigación se presenta el Problema de Programación de Proyectos con Restricción de Recursos (Resource Constrained Project Scheduling Problem, RCPSP), el cual consiste en ordenar y secuenciar un conjunto de actividades que están sujetas a restricción de recursos y de precedencia entre cada una de estas, con el objetivo de minimizar el tiempo de ejecución del proyecto (Makespan). Este problema pertenece a los de tipo NP Hard, ya que al aumentar el número de actividades a procesar y estar limitado por la disponibilidad de recursos aumenta la complejidad computacional, por tal razón es necesario ser desarrollado mediante la implementación de métodos de aproximación (Metaheurísticas) que, si bien no dan la solución óptima, se puede llegar a una mejor solución en términos de tiempo computacional razonable. Para dar solución a este tipo de problema se diseñó un Algoritmo Híbrido Genético, En el que el algoritmo principal es el Algoritmo Genético donde la población inicial es generada de forma aleatoria, el criterio de selección aplicado fue el de selección por torneo, posteriormente el operador de cruce fue por un punto, como operador de mutación se implementó el Algoritmo de Recocido Simulado, el cual modifica la secuenciación de las actividades respetando la restricción de precedencia y de recursos. Se realizó un diseño experimental con el objetivo de determinar como influyen los factores en la variable respuesta Makespan, finalmente se validó el algoritmo propuesto con 10 instancias de cada tamaño (J30, J60, J90 y J120) encontrados en la librería PSPLIB, obteniendo buenas soluciones para las instancias de menor tamaño, aunque para las soluciones de mayor tamaño también se llegó a la solución de la librería, aunque en menor proporción respecto a las instancias inferiores. *