Cuadernos del CIMBAGE N°7 (2005) 103-126 UN ALGORITMO PARA LA REALIZACIÓN DE GRAFOS CON LAS ACTIVIDADES EN LOS ARCOS –GRAFOS PERT– Angel M. Gento Municio ETS Ingenieros Industriales Universidad de Valladolid Paseo del Cauce s/n 47011 – Valladolid - España [email protected] Recibido 15 de noviembre 2004, recibido con modificaciones 16 de febrero 2005, aceptado 24 de febrero 2005 Resumen El problema de dibujar redes con las actividades en los arcos (redes PERT) es un problema NP-completo. Diferentes autores (Syslo, 1984) han establecido límites al mismo. En primer lugar debemos diferenciar entre redes con actividades en los nudos y redes con actividades en los arcos. Si las actividades están en los nudos, el dibujo de la red es muy fácil, pero cuando las actividades están en los arcos, generalmente es necesaria la utilización de actividades ficticias para mantener de forma correcta las relaciones entre las actividades. En este artículo se propone un sencillo y didáctico algoritmo para el caso de un pequeño número de nodos donde es necesario un algoritmo intuitivo. En el algoritmo se definen cuatro tipos diferentes de nodos que pueden aparecer en el grafo, permitiéndonos identificar las actividades ficticias tal y como se muestra en un ejemplo. Palabras clave: redes PERT, actividades ficticias. 104 A. M. Gento / Cuadernos del CIMBAGE N°7 (2005) 103-126 AN ALGORITHM TO MAKE ACTIVITY ON ARROW NETWORK Angel M. Gento Municio ETS Ingenieros Industriales Universidad de Valladolid Paseo del Cauce s/n 47011 – Valladolid - España [email protected] Received 15 november 2004 , received in revised form 16 february 2005, accepted 24 february 2005 Abstract When there are activities in the nodes, it is easy to draw the graph of the network. But when there are activities in the arcs, we generally need dummy activities to keep the relations between activities. In this paper we propose a simple and didactic algorithm with a small number of nodes where an intuitive algorithm is needed. There are four different types of nodes that could appear in the graph. They are used to identify the dummy activities as it is shown in the example. Key words: PERT networks, dummy activity. A. M. Gento / Cuadernos del CIMBAGE N°7 (2005) 103-126 105 1. INTRODUCCIÓN El problema de dibujar redes con las actividades en los arcos (redes PERT) es un problema muy complejo en el que el tiempo de resolución aumenta más que polinomialmente que el número de actividades implicadas en el mismo. Este tipo de problemas se conocen con el nombre de NP-completos. Para la representación de grafos PERT deben seguirse una serie de reglas de obligado cumplimiento: 1. En un grafo PERT sólo puede existir un suceso de inicio y uno de fin. 2. Toda actividad debe poseer, al menos, una actividad precedente y una posterior, salvo, lógicamente, las actividades que parten del suceso inicio del proyecto (que tienen actividades siguientes pero no precedentes) y las que llegan al suceso final (que tendrán actividades precedentes pero no siguientes). 3. Toda actividad ij llega a un suceso j de orden superior al suceso i del que parte. (recordamos la notación: la actividad ij parte del suceso i para llegar al suceso j). 4. No pueden existir dos (o más) actividades que, partiendo del mismo suceso inicial i, lleguen al mismo suceso final j o viceversa. Esto es, no puede haber dos (o más) actividades denominadas de la misma forma ij. Por supuesto, no hay inconveniente en que existan varias actividades ij, ik,..., im –caso de divergencia- o bien ij, kj,…, mj –caso de convergencia-. La primera condición implica que tanto el comienzo como el fin del proyecto deben ser únicos. Entonces, si un proyecto puede comenzar con la ejecución de varias tareas de forma simultánea, todas ellas 106 A. M. Gento / Cuadernos del CIMBAGE N°7 (2005) 103-126 deben partir de un mismo suceso inicio y análogamente ocurre para las actividades que concluyen el proyecto: todas ellas mueren en un mismo suceso de fin. Las restricciones segunda y tercera suponen que toda actividad ij –es decir, todo arco ij en el grafo- forma parte de uno o varios caminos que conectan el nodo de inicio con el de fin del proyecto; además, el sentido de recorrido de estos caminos es el mencionado: de suceso de inicio a suceso de fin del proyecto. Por tanto, no existe posibilidad de hacer recorridos con retorno hacia el origen (ya que el grafo PERT es un grafo dirigido). Y la última condición impide que surja una posible confusión entre actividades que, siendo diferentes, se denominan de la misma manera. El cumplimiento de las normas y el respeto de las prelaciones existentes conducen, en ocasiones, al empleo de ciertas conexiones lógicas denominadas actividades ficticias. Estas actividades no consumen recursos de ningún tipo ni tienen duración alguna; funcionan como puentes que permiten reflejar correctamente las relaciones entre actividades. El objetivo de este trabajo es proponer un algoritmo intuitivo y fácilmente comprensible para la resolución de este tipo de problemas de forma didáctica. 2. DEFINICIONES Para empezar a tomar datos se necesitan las actividades que forman parte de la red (del proyecto) y las siguientes. Las actividades precedentes son fáciles de deducir con los datos pedidos. A. M. Gento / Cuadernos del CIMBAGE N°7 (2005) 103-126 107 En la matriz de precedencia, se definen las actividades “madre” y las que las siguen tal y como se muestra en la Tabla 1. Actividades “madre” A B C D E F Siguientes C C, D, E F F - - Tabla 1. Matriz de precedencia. A lo largo de la explicación del algoritmo se denotarán las actividades “madre” mediante la letra A con un subíndice, A, y las actividades i siguientes con la letra S más dos subíndices, S , indicando el primero ij la actividad “madre” a la que pertenece. Así las actividades siguientes a la actividad A son Φ={S , S , …, S }. i i i1 i2 im Se van a distinguir 4 patrones en una red: • Tipo I. • Tipo II. • Coincidencias. • Cadenas. Cada uno de estos patrones son excluyentes, o sea que si una actividad y sus siguientes pertenecen a un patrón, no pueden pertenecer a otro (excepto para los patrones de Tipo II incompletos y para las cadenas, pues tienen asociada una coincidencia). Una de las premisas fundamentales para desarrollar este método es introducir, en cada paso que sea necesario, el menor número de elementos (nodos y actividades ficticias) posibles, de modo que las relaciones entre las actividades se respeten sin generar elementos superfluos. 108 A. M. Gento / Cuadernos del CIMBAGE N°7 (2005) 103-126 2.1. Patrón de Tipo I. En este caso, se tiene una actividad, S , o un conjunto de actividades i1 Φ = {S , S , …, S } que solo siguen a una actividad “madre” A, por lo i i1 i2 im i que en la matriz de precedencia todas las actividades siguientes a A i están exclusivamente en la fila de la actividad A. i Este conjunto de actividades {S , S , …, S } sólo siguen a A por lo que i1 i2 im i su nodo inicial es igual al nodo final de A, y no es necesario introducir i actividades ficticias para unirlos. Por ejemplo, si tenemos en la matriz de preferencia la fila mostrada en la Tabla 2, y esas actividades siguientes no aparecen de nuevo en la matriz, tendremos un patrón de Tipo I, tal y como se muestra en la Figura 1. A S , S , S i i1 i2 i3 Tabla 2. Ejemplo de patrón de Tipo I. 33 SSii11 AA SS 11 ii 22 ii22 44 SS ii33 55 Figura 1. Mejor solución para el ejemplo de la Tabla 2. 2.1. Patrón de Tipo II. Con este patrón, determinaremos si varias actividades “madre” pueden tener el mismo nodo final. Tendremos este patrón si dos (o más) A. M. Gento / Cuadernos del CIMBAGE N°7 (2005) 103-126 109 actividades “madre” tienen las mismas actividades siguientes sin diferencias. Se pueden distinguir dos casos: 1. Patrón de Tipo II Completo 2. Patrón de Tipo II Incompleto o Coincidencias. En el primer caso, las actividades siguientes implicadas sólo aparecen con esas actividades “madre”. Esto permite asegurar que el nodo inicial de estas siguientes será el mismo que el final de las actividades “madre”. Por ejemplo, si tenemos las filas mostradas en la Tabla 3 en la matriz de precedencia, formarán un patrón de Tipo II Perfecto y su representación gráfica será la Figura 2. A S , S , S i 1 2 3 A S , S , S j 1 2 3 Tabla 3. Ejemplo de patrón de Tipo II Perfecto. 44 11 SS11 AA ii SS 33 22 55 AA jj SS 22 33 66 Figura 2. Mejor solución para el ejemplo de la Tabla 3. Mientras que en el patrón de Tipo II Incompleto, al menos una de las actividades siguientes es también siguiente de otra u otras actividades 110 A. M. Gento / Cuadernos del CIMBAGE N°7 (2005) 103-126 “madre” que no pertenecen a este patrón. Por ello, no se puede afirmar que el nodo de inicio de las actividades siguientes sea el nodo final de las actividades “madre”, pudiendo aparecer actividades ficticias. 2.3. Coincidencias Esta situación aparece cuando 2 (o más) actividades tienen una (o más) actividades siguientes en común y una (o más) actividades siguientes diferentes, por lo que serán necesarias actividades ficticias. En el ejemplo mostrado en la Tabla 4, necesitaremos una actividad ficticia para unir el nodo final de A con el nodo de inicio de la actividad j siguiente en común S, con sentido tal que respete las relaciones en la matriz de precedencia (ver Figura 3). A S i A S, S , S j j2 j3 Tabla 4. Ejemplo de patrón de Coincidencia. AA SS 11 ii 44 55 ff 66 SS jj22 AA 22 jj 33 SS jj33 77 Figura 3. Mejor solución para el ejemplo de la Tabla 4. 2.4. Cadenas En este caso, para tener un número mínimo de actividades ficticias, éstas deben estar concatenadas. A. M. Gento / Cuadernos del CIMBAGE N°7 (2005) 103-126 111 Por ejemplo, en la matriz de precedencias mostrada en la Tabla 5, la representación gráfica que necesita el menor número de actividades ficticias es la mostrada en la Figura 4. A S 1 1 A S , S 2 1 2 A S , S , S 3 1 2 3 A S , S , S , S 4 1 2 3 4 Tabla 5. Ejemplo de patrón de Cadena. AAA SSS 111000 111 111111 111 111222 AAA SSS 777 222 888 222 999 AAA SSS 444 333 555 333 666 AAA SSS 111 444 222 444 333 Figura 4. Mejor solución para el ejemplo de la Tabla 5. 3. ALGORITMO Los pasos a seguir en el algoritmo propuesto son: 1. Búsqueda de actividades que comiencen en el nodo inicial. 2. Búsqueda de actividades que finalicen en el nodo final. 3. Búsqueda de patrones de Tipo I. 112 A. M. Gento / Cuadernos del CIMBAGE N°7 (2005) 103-126 4. Búsqueda de patrones de Tipo II. 5. Búsqueda de Coincidencias. 6. Identificación de los nodos de inicio en las actividades de los patrones Coincidencia. 7. Búsqueda de Cadenas. 8. Identificación de los nodos finales del resto de actividades y determinación de las actividades ficticias. 9. Asignación de los nodos finales de los patrones de Tipo II Incompletos. 3.1. Búsqueda de actividades que comienzan en el nodo inicial Las actividades que parten del nodo inicial son aquellas que no poseen tareas precedentes, o lo que es lo mismo, no aparecen en ninguna ocasión como actividad siguiente de ninguna otra, de forma que su identificación es sencilla con el vector NP porque podemos identificar las actividades A tales que NP[A] = 0. i i Se puede disponer una matriz de nodos en la que se van apuntando los nodos de inicio y de fin para cada actividad. Para cada tarea madre en el proyecto debe responderse a la pregunta de la Figura 5 en orden a determinar su posible inicio en el nodo 0 del proyecto. NO SI NP[A] = 0 i A no parte del A parte del i i nodo inicial nodo inicial Figura 5. Búsqueda de actividades que parten del nodo inicial.