A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP)
Fuente:
Redalyc
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Artículo científico |
| Langue: | en |
| Publié: |
Escuela de Ingeniería de Antioquia
2013
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1876425617638948864 |
|---|---|
| author | Juan Carlos Rivera |
| author_facet | Juan Carlos Rivera |
| contents | A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) Juan Carlos Rivera Luis Fernando Moreno V. Francisco Javier Díaz S. Gloria Elena Peña Z. Ingeniería RCPSP GRASP Heuristic Justification Scatter Search 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). 2013 artículo científico 1794-1237 https://www.redalyc.org/articulo.oa?id=149229801007 en http://www.redalyc.org/revista.oa?id=1492 Revista EIA application/pdf Escuela de Ingeniería de Antioquia Revista EIA (Colombia) Num.20 Vol.10 |
| format | Artículo científico |
| id | redalyc_149229801007 |
| institution | Redalyc |
| language | en |
| publishDate | 2013 |
| publisher | Escuela de Ingeniería de Antioquia |
| spellingShingle | A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) Juan Carlos Rivera Ingeniería RCPSP GRASP Heuristic Justification Scatter Search A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) Juan Carlos Rivera Luis Fernando Moreno V. Francisco Javier Díaz S. Gloria Elena Peña Z. Ingeniería RCPSP GRASP Heuristic Justification Scatter Search 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). 2013 artículo científico 1794-1237 https://www.redalyc.org/articulo.oa?id=149229801007 en http://www.redalyc.org/revista.oa?id=1492 Revista EIA application/pdf Escuela de Ingeniería de Antioquia Revista EIA (Colombia) Num.20 Vol.10 |
| title | A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) |
| topic | Ingeniería RCPSP GRASP Heuristic Justification Scatter Search |
| url | https://www.redalyc.org/articulo.oa?id=149229801007 |