Aplicación de la metaheurística cromática al problema de secuenciación de proyectos con recursos limitados (RCPSP)

Desde un punto de vista más amplio, se considera al RCPSP como un problema de optimización combinatoria, debido a que se pueden codificar soluciones factibles mediante la combinación de las actividades que comprende el proyecto, o por decirlo de otra manera, mediante el intercambio de las posiciones en el orden de las actividades. Además puede catalogarse como un problema de naturaleza NP-hard (Blazewicz, Lenstra, & Rinnooy Kan, 1983), ya que para encontrar la solución óptima se requieren un tiempo considerable de procesamiento. Estos resultados obtenidos en tiempo no polinomial se perciben en proyectos de 30 actividades en adelante. Esta situación hace poco práctica la resolución del RCPSP a través de técnicas exactas, por ello se utilizan las metaheurísticas como una metodología de nivel superior que facilitan la obtención de soluciones satisfactorias para esta categoría de problemas. Numerosos autores en el tema han utilizado diferentes enfoques metaheurísticos clásicos como algoritmos genéticos, recocido simulado, búsqueda tabú, entre otros. Actualmente se está abordando el problema RCPSP a través de nuevas metaheurísticas como optimización por enjambre de partículas, colonias de hormigas, o combinaciones de todas las anteriormente mencionadas. En esta oportunidad, el medio que utilizaremos para llegar a la resolución del RCPSP será una nueva metaheurística llamada Cromática inspirada en la escala cromática de las notas musicales. Esta metaheurística es un método de optimización combinatoria basado en un algoritmo de búsqueda que hace una relación con las diferentes maneras con las que un músico u artista realiza y escoge la melodía más apropiada para una pieza musical, a partir de la combinación de distintas notas musicales de la escala cromática. Así mismo este procedimiento se puede aplicar al RCPSP para escoger la mejor secuencia del proyecto a partir de las posibles combinaciones de sus actividades respetando ciertos parámetros establecidos. Posteriormente a la obtención de resultados mediante la aplicación de la metaheurística cromática al Problema de Secuenciación de Proyectos con Recursos Limitados, se procederá a realizar una comparación de estos con los resultados de otros algoritmos como el genético, la búsqueda tabú y el recocido simulado, en el mismo problema, para medir la propia eficiencia.

• Autores: Hernández Fuentes, Fausto Javier; Poveda Gulfo, Juan Sebastián
• Tipo de recurso: Trabajo de grado de pregrado
• Fecha de publicación: 2018
• Institución: Universidad de Córdoba
• Repositorio: Repositorio Institucional Unicórdoba
• Idioma: spa
• OAI Identifier: oai:repositorio.unicordoba.edu.co:ucordoba/675
• Acceso en línea: https://repositorio.unicordoba.edu.co/handle/ucordoba/675
• Palabra clave: Secuenciación, Métodos Metaheurísticos, Algoritmía, RCPSP
• Rights: openAccess
• License: Copyright Universidad de Córdoba, 2020