Portal de Periódicos da CAPES

A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) (UN ALGORITMO HEURÍSTICO HÍBRIDO PARA LA SOLUCIÓN DEL PROBLEMA DE PROGRAMACIÓN DE TAREAS CON RECURSOS RESTRINGIDOS (RCPSP)

2014; EIA University; Volume: 10; Issue: 20 Linguagem: Espanhol

10.24050/reia.v10i20.517

2463-0950

Juan Carlos Rivera, Luis Fernando Moreno Velásquez, Francisco Javier Díaz Serna, Gloria Elena Peña Zapata,

Resource-Constrained Project Scheduling

Abstract: The Resource Constrained Project Scheduling Problem (RCPSP) is a problem of great interest for the scientific community because it belongs to the class of NP-Hard problems and no methods are known that can solve it accurately in polynomial processing times. For this reason heuristic methods are used to solve it in an efficient way though there is no guarantee that an optimal solution can be obtained. This research presents a hybrid heuristic search algorithm to solve the RCPSP efficiently, combining elements of the heuristic Greedy Randomized Adaptive Search Procedure (GRASP), Scatter Search and Justification. The efficiency obtained is measured taking into account the presence of the new elements added to the GRASP algorithm taken as base: Justification and Scatter Search. The algorithms are evaluated using three data bases of instances of the problem: 480 instances of 30 activities, 480 of 60, and 600 of 120 activities respectively, taken from the library PSPLIB available online. The solutions obtained by the developed algorithm for the instances of 30, 60 and 120 are compared with results obtained by other researchers at international level, where a prominent place is obtained, according to Chen (2011). El Problema de Programacion de Tareas con Recursos Restringidos (RCPSP) es de gran interes para la comunidad cientifica debido a que, por su pertenencia a la clase de problemas NP–Hard, no se conocen metodos que lo resuelvan de manera exacta en tiempos de procesamiento polinomial. Por esta razon, se utilizan metodos heuristicos para resolverlo de manera eficiente aunque no garantizan la obtencion de una solucion optima. En esta investigacion se presenta un algoritmo heuristico hibrido para resolver eficientemente el RCPSP, combinando elementos de las heuristicas Procedimiento de Busqueda Adaptativa Aleatoria Agresiva (GRASP), Busqueda Dispersa y Justificacion. La eficiencia obtenida se mide por la presencia de los nuevos elementos agregados al algoritmo de base GRASP: Justificacion y Busqueda Dispersa. Los algoritmos se evaluan usando tres bases de datos de instancias del problema, asi: 480 instancias de 30 actividades, 480 de 60 y 600 de 120 actividades respectivamente, tomadas de la libreria PSPLIB disponible en linea. Las soluciones obtenidas por el algoritmo desarrollado para las instancias de 30, 60 y 120 actividades se comparan con los resultados obtenidos por otros investigadores a nivel internacional, donde se obtiene un lugar prominente de acuerdo con Chen (2011). Sumario: O Problema da Programacao de Tarefas com Recursos Restringidos (RCPSP) e um problema de grande interesse para a comunidade cientifica devido a que, por a sua pertenca a classe de problemas NP–Hard, nao conhecem-se metodos que os solucionam de maneira exata em tempos de processamento polinomial. Por esta razao, utilizam-se metodos heuristicos para solucionar-o de maneira eficiente apesar de que nao garantam a obtencao duma solucao otima. Nesta investigacao apresenta-se um algoritmo heuristico hibrido para solucionar eficientemente o RCPSP, combinando elementos das heuristicas Procedimento de Busca Adatativa Aleatoria Agressiva (GRASP), Busca Dispersa e Justificacao. A eficiencia obteida conte-se por a presenca dos novos elementos agregados ao algoritmo de base GRASP: Justificacao e Busca Dispersa. Os algoritmos avaliam-se usando tres bases de dados de instâncias do problema, assim: 480 instâncias de 30 atividades, 480 de 60 e 600 de 120 atividades respectivamente, tomadas da livraria PSPLIB disponivel on-line. As solucoes obteidas por o algoritmo desenvolvido para as instâncias de 30, 60 y 120 atividades comparam-se com os resultados obteidos por outros investigadores a nivel internacional, onde obtem-se um lugar proeminente de acordo com Chen (2011).