Programación de proyectos con recursos limitados mediante algoritmos paralelos

Abstract

Abordamos el Problema de la Programación de Proyectos con Recursos Limitados en su versión estándar, con el objetivo de obtener una programación para las actividades que minimice la duración del proyecto. Este problema es de naturaleza combinatorioa y pertenece a la clase de problemas NP-duros, por ello, el espacio de soluciones posibles crece de forma exponencial conforme aumenta el tamaño del problema. Aunque la aparición en la última década de máquinas cada vez más potentes ha permitido aumentar el tamaño y el número de los problemas resueltos de forma óptima, la resolución de estos problemas siguen demandando mayor velocidad de proceso. La computación en paralelo aparece como un posible camino para abordar estos problemas, ya que explota la idea de dividir el trabajo entre un conjunto de procesadores que colaboran en la solución de un único problema. Los objetivos de este trabajo se centran en el desarrollo, adaptación e implementación de algoritmos paralelos para resolver de forma óptima este problema, estudiando las ventajas e inconvenientes que los mismos presentan. Ha sido necesario reformular e introducir nuevos conceptos para permitir la correcta aplicación de algunas reglas de dominancia que dejan de ser válidas cuando se realiza una búsqueda en paralelo de la solución óptima. La construcción de un cluster de ordenadores personales nos ha permitido diseñar un entorno de programación en paralelo en el que desarrollar nuestro trabajo sin la necesidad de recurrir a costosas máquinas paralelas. Los resultados obtenidos al resolver los proyectos de 30 y 60 actividades de la librería estándar PSPLIB han permitido evaluar el comportamiento de los algoritmos paralelos branch&bound desarrollados. Estos resultados ponen de manifiesto como la computación en paralelo es una técnica adecuada para resolver de forma óptima el problema de la programación de proyectos con recursos limitados. Además