Determinación de los K caminos más críticos en las redes PERT

Determination of K most critical paths in PERT networks

Este trabajo presenta un estudio sobre los principales métodos para identificar los caminos más largos en redes PERT, denominados caminos k-críticos en la literatura (cuando k = 1, existe el camino más largo, tradicionalmente conocido como camino crítico; cuando k = 2, existe el segundo camino más largo, y así sucesivamente). Se discuten tres algoritmos presentados en la literatura y se propone un nuevo procedimiento, denominado algoritmo de mínima holgura, que presenta algunas ventajas sobre los anteriores. El comportamiento del algoritmo de mínima holgura, cuando se aplica a redes PERT, se verifica mediante simulación.

1. INTRODUCCIÓN

Uno de los factores decisivos para la competitividad de las empresas de proyectos es el factor tiempo, que, al igual que el factor coste, se considera un criterio para ganar pedidos. Por ello, la reducción del plazo de ejecución de los proyectos es un objetivo importante para estas empresas.

Para obtener una ventaja competitiva en el tiempo de ejecución de un proyecto, la planificación del mismo suele hacerse primero en función de la duración prevista de sus actividades, generando así la duración prevista del proyecto (Te), dada por la duración de su camino más largo. A continuación, se establece un objetivo, T*

Un camino k-crítico en una red se refiere al camino con la k-ésima mayor duración. Cuando k = 1, es el camino con la duración más larga, tradicionalmente conocido como camino crítico; cuando k = 2, es el camino con la segunda duración más larga, y así sucesivamente. Por tanto, es interesante conocer los caminos P_k del proyecto, k=1, 2,..., n, cuyas duraciones T(P_k) son superiores a T*.

La literatura proporciona tres algoritmos importantes para determinar los caminos k-críticos en las redes. Basándose en un procedimiento de enumeración selectiva de caminos, Dodin (1984) presenta un método aproximado para identificar los caminos k-críticos más largos en redes probabilísticas, es decir, redes en las que la duración de las actividades es una variable aleatoria. Yen et al. (1989) presentan varios algoritmos para redes deterministas, todos ellos basados en un proceso de ramificación y corte de caminos parciales, que conduce a una baja eficiencia computacional, ya que muchos caminos parciales ramificados inicialmente se abandonan a lo largo del proceso. Ju y Saleh (1991) presentan un procedimiento que evita este inconveniente, lo que lo convierte en el algoritmo más eficiente entre los disponibles en la literatura. En este trabajo se analizarán estos tres trabajos.