A branch and bound hybrid algorithm with four deterministic heuristics for the resource constrained project scheduling problem (RCPSP)
En este artículo se aborda el problema de Programación de Tareas con Recursos Restringidos (RCPSP). Para su solución, se desarrolla y se implementa una metodología híbrida que usa como base un algoritmo de Ramificación y Acotamiento con potentes reglas de dominancia, y se combina con cuatro heurísti...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidad Nacional de Colombia
2015-01-01
|
| Series: | Dyna |
| Online Access: | http://www.redalyc.org/articulo.oa?id=49637154026 |
| _version_ | 1811245343026708480 |
|---|---|
| author | Daniel Morillo-Torres Luis Fernando Moreno-Velásquez Francisco Javier Díaz-Serna |
| author_facet | Daniel Morillo-Torres Luis Fernando Moreno-Velásquez Francisco Javier Díaz-Serna |
| author_sort | Daniel Morillo-Torres |
| collection | DOAJ |
| description | En este artículo se aborda el problema de Programación de Tareas con Recursos Restringidos (RCPSP). Para su solución, se desarrolla y se implementa una metodología híbrida que usa como base un algoritmo de Ramificación y Acotamiento con potentes reglas de dominancia, y se combina con cuatro heurísticas determinísticas cuyo objetivo es truncar ramas del árbol de búsqueda, pero, a su vez, minimizar la probabilidad de descartar ramales que contengan soluciones óptimas. En esencia, estas estrategias permiten la repartición de iteraciones en forma mayoritaria y organizada en las regiones más promisorias usando, únicamente, subconjuntos que tengan características similares o iguales a las de las soluciones óptimas en cada nivel del árbol, garantizando así una amplia exploración dentro de la región factible y al mismo tiempo una buena explotación. Finalmente se analiza el desempeño del algoritmo desarrollado mediante la solución de algunos problemas de la librería de prueba PSPLIB. |
| first_indexed | 2024-04-12T14:38:38Z |
| format | Article |
| id | doaj.art-301ff6172d4148fe93cd38c35efdf595 |
| institution | Directory Open Access Journal |
| issn | 0012-7353 |
| language | English |
| last_indexed | 2024-04-12T14:38:38Z |
| publishDate | 2015-01-01 |
| publisher | Universidad Nacional de Colombia |
| record_format | Article |
| series | Dyna |
| spelling | doaj.art-301ff6172d4148fe93cd38c35efdf5952022-12-22T03:28:58ZengUniversidad Nacional de ColombiaDyna0012-73532015-01-0182190198207A branch and bound hybrid algorithm with four deterministic heuristics for the resource constrained project scheduling problem (RCPSP)Daniel Morillo-TorresLuis Fernando Moreno-VelásquezFrancisco Javier Díaz-SernaEn este artículo se aborda el problema de Programación de Tareas con Recursos Restringidos (RCPSP). Para su solución, se desarrolla y se implementa una metodología híbrida que usa como base un algoritmo de Ramificación y Acotamiento con potentes reglas de dominancia, y se combina con cuatro heurísticas determinísticas cuyo objetivo es truncar ramas del árbol de búsqueda, pero, a su vez, minimizar la probabilidad de descartar ramales que contengan soluciones óptimas. En esencia, estas estrategias permiten la repartición de iteraciones en forma mayoritaria y organizada en las regiones más promisorias usando, únicamente, subconjuntos que tengan características similares o iguales a las de las soluciones óptimas en cada nivel del árbol, garantizando así una amplia exploración dentro de la región factible y al mismo tiempo una buena explotación. Finalmente se analiza el desempeño del algoritmo desarrollado mediante la solución de algunos problemas de la librería de prueba PSPLIB.http://www.redalyc.org/articulo.oa?id=49637154026 |
| spellingShingle | Daniel Morillo-Torres Luis Fernando Moreno-Velásquez Francisco Javier Díaz-Serna A branch and bound hybrid algorithm with four deterministic heuristics for the resource constrained project scheduling problem (RCPSP) Dyna |
| title | A branch and bound hybrid algorithm with four deterministic heuristics for the resource constrained project scheduling problem (RCPSP) |
| title_full | A branch and bound hybrid algorithm with four deterministic heuristics for the resource constrained project scheduling problem (RCPSP) |
| title_fullStr | A branch and bound hybrid algorithm with four deterministic heuristics for the resource constrained project scheduling problem (RCPSP) |
| title_full_unstemmed | A branch and bound hybrid algorithm with four deterministic heuristics for the resource constrained project scheduling problem (RCPSP) |
| title_short | A branch and bound hybrid algorithm with four deterministic heuristics for the resource constrained project scheduling problem (RCPSP) |
| title_sort | branch and bound hybrid algorithm with four deterministic heuristics for the resource constrained project scheduling problem rcpsp |
| url | http://www.redalyc.org/articulo.oa?id=49637154026 |
| work_keys_str_mv | AT danielmorillotorres abranchandboundhybridalgorithmwithfourdeterministicheuristicsfortheresourceconstrainedprojectschedulingproblemrcpsp AT luisfernandomorenovelasquez abranchandboundhybridalgorithmwithfourdeterministicheuristicsfortheresourceconstrainedprojectschedulingproblemrcpsp AT franciscojavierdiazserna abranchandboundhybridalgorithmwithfourdeterministicheuristicsfortheresourceconstrainedprojectschedulingproblemrcpsp AT danielmorillotorres branchandboundhybridalgorithmwithfourdeterministicheuristicsfortheresourceconstrainedprojectschedulingproblemrcpsp AT luisfernandomorenovelasquez branchandboundhybridalgorithmwithfourdeterministicheuristicsfortheresourceconstrainedprojectschedulingproblemrcpsp AT franciscojavierdiazserna branchandboundhybridalgorithmwithfourdeterministicheuristicsfortheresourceconstrainedprojectschedulingproblemrcpsp |