Nuevos métodos de resolución del problema de secuenciación de proyectos con recursos limitados

Resumen

El Problema de Secuenciación de Proyectos con Recursos Limitados (RCPSP) está considerado como el problema básico más importante dentro de la secuenciación con recursos limitados. Entre sus aplicaciones prácticas podemos citar la construcción de edificios, la planificación de la producción y el desarrollo de grandes sistemas de transporte y energía. Dado que es la base de numerosos problemas de secuenciación, cualquier avance en la resolución de este problema puede repercutir rápidamente en la resolución de muchos otros problemas. El RCPSP consiste en realizar un proyecto o conjunto de actividades sujetas a dos tipos de restricciones. Por una parte, las relaciones de precedencia fuerzan a algunas actividades a comenzar después de la finalización de otras. Por otra parte, procesar cada actividad requiere consumir recursos, los cuales están disponibles en una cantidad fija y limitada en cada unidad de tiempo. El objetivo del RCPSP consiste en encontrar tiempos de inicio para las actividades de manera que se minimice la longitud del proyecto o makespan. El RCPSP es un problema NP-duro, por lo que son necesarios algoritmos heurísticos para proporcionar soluciones de buena calidad para instancias grandes. En el capítulo 1 de la memoria se realiza una revisión bibliográfica del problema, englobándolo dentro de la secuenciación de proyectos. En el capítulo 2 se describen dos nuevos algoritmos heurísticos para el problema y se demuestra su calidad: CARA e HIAC. El algoritmo CARA se basa en las relaciones de precedencia (análisis temporal del proyecto). El procedimiento consiste en una implementación no estándar, dentro de un marco de poblaciones, de los conceptos fundamentales de la búsqueda tabú, que no utiliza explícitamente las estructuras de memoria. El segundo procedimiento (HIAC) emplea poblaciones e información sobre utilización de recursos. Otros elementos incluidos son un eficiente procedimiento de mejora para mejorar localmente la utilización de recursos, la búsqueda dispersa y el reencadenamiento de trayectorias. Además, dentro del capítulo 2, se definen distintas distancias en el RCPSP y un esquema algorítmico (MetaRCPSP) capaz de producir algoritmos heurísticos para el RCPSP al especificar cada uno de sus componentes. En el capítulo 3 se demuestra la utilidad de una técnica denominada justificación. La justificación puede ser incorporada fácilmente a muy diversos algoritmos para el RCPSP sin que ello requiera, en general, un incremento en el tiempo de cómputo. Los resultados obtenidos indican que la justificación aumenta considerablemente la calidad de los algoritmos hasta tal punto que su sola inclusión permite a algoritmos sencillos mejorar a los mejores algoritmos publicados hasta el momento. En el capítulo 4 se definen diferentes generalizaciones de la justificación, se estudia las relaciones entre ellas y se demuestra que este campo de estudio es atractivo a nivel práctico. Así mismo, se describe cómo adaptar la justificación a otros problemas de secuenciación de proyectos con recursos limitados y se demuestra con un ejemplo que esta técnica puede ser muy útil en algunas extensiones del RCPSP. En el capítulo 5 diseñamos un nuevo algoritmo genético denominado HGA. HGA emplea el operador de cruce de los picos, que permite combinar partes de buenas soluciones que realmente han contribuido a su calidad: los picos o agrupaciones de actividades con una utilización alta de recursos. El algoritmo desarrollado es mejor que todos los publicados. En el capítulo 6 hemos desarrollado una teoría y una metodología que permite seleccionar un conjunto de picos provenientes de distintas secuencias y construir, a partir de ellos, nuevas secuencias. Los resultados desarrollados constituyen una base teórica para futuras técnicas y nuevos algoritmos donde se combinen picos de varias soluciones. Por último, en el capítulo 7, se exponen las conclusiones y las líneas futuras de investigación. ______________________________________________________________________________________________________