Desarrollo de un algoritmo genético para resolver el problema de programación de proyectos con recursos restringidos (rcpsp) con duración de actividades aleatorias soportado en un método basado en duraciones redundantes

Abstract

Al abordar problemas de secuenciación de actividades, se encuentra que uno de los más estudiados es el problema de programación de proyectos con recursos restringidos (Resource Constrained Project Scheduling Problem: RCPSP), el cual consiste en secuenciar y dar orden a un conjunto de actividades sujetas a restricciones de recursos y precedencias con el objetivo de minimizar el tiempo de ejecución del proyecto (makespan). Dado que este problema está presente en cualquier tipo de industria, surge la necesidad de su investigación. Los procedimientos para abordar el RCPSP no determinístico se diseñan con base en estrategias predictivas, reactivas y proactivas. En suma, el presente trabajo resume la investigación que tuvo como objetivo desarrollar un algoritmo genético que pertenece a la fase proactiva; del cual se obtiene la mejor lista de actividades (mejor makespan), y la línea base asociada. Posteriormente se lleva a cabo como estrategia reactiva una simulación donde se prueba la robustez de las líneas bases obtenidas. Las instancias utilizadas se encuentran en la librería PSPLIB, la cual es una librería de benchmark para el problema RCPSP, aplicando la modificación de las duraciones redundantes, el cual consiste en adicionar tiempo extra a la duración original, esto para enfrentar las eventualidades que durante la ejecución del proyecto pueden suceder. Para analizar el comportamiento de los parámetros en el Algoritmo genético propuesto se realizó un diseño de experimentos mediante un diseño cuasi experimental, es decir, que no se realizarán experimentos aleatorios, debido a que existe una correlación entre el aumento numérico de los parámetros y el porcentaje de exactitud con respecto a los resultados esperados. Finalmente se compararon los resultados en términos de indicadores de robustez obtenidos de la programación reactiva del algoritmo genético con el método exacto utilizando los mismos parámetros