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)
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)
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright statement
The authors exclusively assign to the Universidad EIA, with the power to assign to third parties, all the exploitation rights that derive from the works that are accepted for publication in the Revista EIA, as well as in any product derived from it and, in in particular, those of reproduction, distribution, public communication (including interactive making available) and transformation (including adaptation, modification and, where appropriate, translation), for all types of exploitation (by way of example and not limitation : in paper, electronic, online, computer or audiovisual format, as well as in any other format, even for promotional or advertising purposes and / or for the production of derivative products), for a worldwide territorial scope and for the entire duration of the rights provided for in the current published text of the Intellectual Property Law. This assignment will be made by the authors without the right to any type of remuneration or compensation.
Consequently, the author may not publish or disseminate the works that are selected for publication in the Revista EIA, neither totally nor partially, nor authorize their publication to third parties, without the prior express authorization, requested and granted in writing, from the Univeridad EIA.
Show authors biography
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 Programación de Tareas con Recursos Restringidos (RCPSP) es de gran interés para la comunidad científica debido a que, por su pertenencia a la clase de problemas NP–Hard, no se conocen métodos que lo resuelvan de manera exacta en tiempos de procesamiento polinomial. Por esta razón, se utilizan métodos heurísticos para resolverlo de manera eficiente aunque no garantizan la obtención de una solución óptima. En esta investigación se presenta un algoritmo heurístico híbrido para resolver eficientemente el RCPSP, combinando elementos de las heurísticas Procedimiento de Búsqueda Adaptativa Aleatoria Agresiva (GRASP), Búsqueda Dispersa y Justificación. La eficiencia obtenida se mide por la presencia de los nuevos elementos agregados al algoritmo de base GRASP: Justificación y Búsqueda Dispersa. Los algoritmos se evalúan usando tres bases de datos de instancias del problema, así: 480 instancias de 30 actividades, 480 de 60 y 600 de 120 actividades respectivamente, tomadas de la librería PSPLIB disponible en línea. 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).
Sumário: O Problema da Programação de Tarefas com Recursos Restringidos (RCPSP) é um problema de grande interesse para a comunidade científica devido a que, por a sua pertença à classe de problemas NP–Hard, não conhecem-se métodos que os solucionam de maneira exata em tempos de processamento polinomial. Por esta razão, utilizam-se métodos heurísticos para solucionar-o de maneira eficiente apesar de que não garantam a obtenção duma solução ótima. Nesta investigação apresenta-se um algoritmo heurístico híbrido para solucionar eficientemente o RCPSP, combinando elementos das heurísticas Procedimento de Busca Adatativa Aleatória Agressiva (GRASP), Busca Dispersa e Justificação. A eficiência obteida conte-se por a presenca dos novos elementos agregados ao algoritmo de base GRASP: Justificação e Busca Dispersa. Os algoritmos avaliam-se usando três 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 disponível on-line. As soluções 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 nível internacional, onde obtem-se um lugar proeminente de acordo com Chen (2011).
Article visits 397 | PDF visits 221
