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)
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 method...
Saved in:
| Institution: | Universidad EIA |
|---|---|
| Main Authors: | , , , |
| Format: | Artículo de revista |
| Language: | Español |
| Published: |
Fondo Editorial EIA - Universidad EIA
2014-01-29
|
| Subjects: | |
| Online Access: | https://repository.eia.edu.co/handle/11190/4858 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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).
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).
|
|---|---|
| ISSN: | 1794-1237 |
