A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP)
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidad EIA
|
| Series: | Revista EIA |
| Subjects: | |
| Online Access: | http://www.scielo.org.co/scielo.php?script=sci_arttext&pid=S1794-12372013000200008&lng=en&tlng=en |
| _version_ | 1819294385495343104 |
|---|---|
| author | Juan Carlos Rivera Luis Fernando Moreno V. Francisco Javier Díaz S. Gloria Elena Peña Z. |
| author_facet | Juan Carlos Rivera Luis Fernando Moreno V. Francisco Javier Díaz S. Gloria Elena Peña Z. |
| author_sort | Juan Carlos Rivera |
| collection | DOAJ |
| description | 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). |
| first_indexed | 2024-12-24T04:25:29Z |
| format | Article |
| id | doaj.art-85413dc2ce6447b28f4fb8e0f4f61c8e |
| institution | Directory Open Access Journal |
| issn | 1794-1237 |
| language | English |
| last_indexed | 2024-12-24T04:25:29Z |
| publisher | Universidad EIA |
| record_format | Article |
| series | Revista EIA |
| spelling | doaj.art-85413dc2ce6447b28f4fb8e0f4f61c8e2022-12-21T17:15:39ZengUniversidad EIARevista EIA1794-12372087100S1794-12372013000200008A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP)Juan Carlos Rivera0Luis Fernando Moreno V.1Francisco Javier Díaz S.2Gloria Elena Peña Z.3Université de Technologie de TroyesUniversidad Nacional de ColombiaUniversidad Nacional de ColombiaUniversidad Nacional de ColombiaThe 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).http://www.scielo.org.co/scielo.php?script=sci_arttext&pid=S1794-12372013000200008&lng=en&tlng=enProgramação de projetosRCPSPHeurísticaGRASPBusca DispersaJustificação |
| spellingShingle | Juan Carlos Rivera Luis Fernando Moreno V. Francisco Javier Díaz S. Gloria Elena Peña Z. A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) Revista EIA Programação de projetos RCPSP Heurística GRASP Busca Dispersa Justificação |
| title | A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) |
| title_full | A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) |
| title_fullStr | A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) |
| title_full_unstemmed | A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) |
| title_short | A HYBRID HEURISTIC ALGORITHM FOR SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) |
| title_sort | hybrid heuristic algorithm for solving the resource constrained project scheduling problem rcpsp |
| topic | Programação de projetos RCPSP Heurística GRASP Busca Dispersa Justificação |
| url | http://www.scielo.org.co/scielo.php?script=sci_arttext&pid=S1794-12372013000200008&lng=en&tlng=en |
| work_keys_str_mv | AT juancarlosrivera ahybridheuristicalgorithmforsolvingtheresourceconstrainedprojectschedulingproblemrcpsp AT luisfernandomorenov ahybridheuristicalgorithmforsolvingtheresourceconstrainedprojectschedulingproblemrcpsp AT franciscojavierdiazs ahybridheuristicalgorithmforsolvingtheresourceconstrainedprojectschedulingproblemrcpsp AT gloriaelenapenaz ahybridheuristicalgorithmforsolvingtheresourceconstrainedprojectschedulingproblemrcpsp AT juancarlosrivera hybridheuristicalgorithmforsolvingtheresourceconstrainedprojectschedulingproblemrcpsp AT luisfernandomorenov hybridheuristicalgorithmforsolvingtheresourceconstrainedprojectschedulingproblemrcpsp AT franciscojavierdiazs hybridheuristicalgorithmforsolvingtheresourceconstrainedprojectschedulingproblemrcpsp AT gloriaelenapenaz hybridheuristicalgorithmforsolvingtheresourceconstrainedprojectschedulingproblemrcpsp |