Nociones de programación de proyectos 1.1 Introducción 1.1.1 Objetivos Objetivos de la lección Tras esta lección, el alumno conocerá: • Los antecedentes históricos de las técnicas de expresión del cronograma más comúnmente utilizadas y sus principios básicos • Cómo construir un diagrama de Gantt y un grafo pert • Cuándo resulta más ventajosa la utilización de un método u otro • Los distintos tipos de enlaces y prelaciones que aparecen entre las distintas actividades del cronograma • Cómo resolver solapamientos y desplazamientos • Cómo medir el progreso del avance del proyecto en un diagrama de Gantt • Cómo calcular tiempos tempranos, tardíos, máximos y mínimos • Cómo calcular los distintos tipos de holgura; y su significado • Cómo determinar las fechas de comienzo y finalización tempranas y tardías de las actividades del cronograma • El efecto que tiene sobre el coste la reducción del plazo, y viceversa • El significado del coste unitario de reducción y las posibles causas que determinan su signo • El método de Ackoff–Sasieni para la reducción de plazos a mínimo coste • El contexto de la programación de proyectos con recursos limitados • El algoritmo de Burgess–Killebrew para la nivelación de recursos • Un algoritmo heurístico para la asignación de recursos 1.2 Los diagramas Gantt 1.2.1 Antecedentes históricos Desde la introducción de la máquina de vapor y el advenimiento de la revolución industrial, comienza el interés por la programación y secuenciación de las tareas productivas a fin a conseguir una mayor eficiencia. Así, ya en 1760 Perronet estudió los tiempos necesarios para la fabricación de alfileres. Sin embargo, no es hasta el siglo xix cuando Frederick W. Taylor inicia sus estudios de sistematización de métodos y tiempos, presentando en 1895 los resultados del estudio a la ASME (American Society of Mechanical Engineers). El conjunto de estos estudios podrían bien ser considerados como los fundamentos de los sistemas organizativos de los sistemas productivos en la industria. Posteriormente, discípulos suyos continúan con estos trabajos y así, en 1909, Gilbreth publica su trabajo sobre la colocación de ladrillos, para interesarse posteriormente por el análisis de los movimientos, publicando en 1917 «Aplicaciones del estudio de movimientos». Otro de sus discípulos, Henry Gantt (1861–1919) señaló que un proceso lo forma una combinación de operaciones. Esta observación le condujo a desarrollar métodos gráficos que permitían visualizar la simultaneidad y secuenciación de las operaciones. 1.2.2 Principios básicos La forma más intuitiva de representación gráfica de la planificación son los diagramas de barras. Los diagramas de barras son muy utilizados en proyectos porque proporcionan una representación fácil de entender por personas de procedencia muy diferente, pero aportando simultáneamente datos precisos. La forma básica de un diagrama de barras consiste en una lista de actividades en el lado izquierdo, cada una de las cuales tiene asociada una barra horizontal de longitud proporcional a su duración. Dentro de estos diagramas destacan los diagramas de hitos y, especialmente, el diagrama de Gantt. Utiliza la base normal de un calendario con barras para cada actividad, tal como se ve en la figura [fig:ejemploGantt0]. Sobre el Gantt suelen marcarse los hitos. [flotante Figura: [Figura 1.1: Diagrama de Gantt que muestra los plazos de realización de varias actividades ] ] Tipos de enlaces entre actividades Una vez que se ha definido la estructura del proyecto y se han dado valores a las duraciones de las diferentes actividades, es el momento de introducir las dependencias entre actividades. La figura [fig:prelacionesGantt] muestra los principales tipos de enlaces: • Inicio—Inicio Las dos actividades deberán comenzar simultáneamente (por ejemplo, la tarea «trabajos pintura» sólo puede iniciarse una vez iniciada la tarea «montar andamio»). • Fin—Fin Las actividades implicadas deberán terminar simultáneamente (por ejemplo, la tarea «desmontar andamio» sólo puede terminarse una vez finalizada la tarea «trabajos de pintura»). • Fin—Inicio Es el más habitual e indica que la actividad actual deberá esperar a que termine la predecesora, pues probablemente sus resultados serán parte del material de partida de ésta (por ejemplo, la tarea «instalar equipo» sólo puede iniciarse una vez terminada la tarea «reparar equipo»). • Inicio—Fin Esta vinculación permite el cierre del ciclo, indicando que no puede finalizar una actividad sin que comience la siguiente (por ejemplo, la tarea «puesta en servicio» sólo puede terminarse una vez inicidada la tarea «aceptación»). [flotante Figura: [Figura 1.2: Tipos de enlaces entre actividades ] ] Ventajas e inconvenientes La utilización de los diagramas de Gantt proporciona grandes ventajas siempre que se sepa cuando se deben usar y cuando deben verse relegados por otras alternativas de representación. A continuación se comentan las ventajas e inconvenientes del método. Ventajas • Es una representación fácil de comprender Los elementos de representación son simples y su interpretación es inmediata. • Sirve de base para la planificación de recursos Como veremos en los apartados correspondientes a la nivelación de recursos, el diagrama de Gantt permite perfilar de forma sencilla la utilización de los recursos y su evolución a lo largo del ciclo de vida del proyecto. • Muestra el progreso de las actividades de forma clara y simple Junto con la planificación, el Gantt también puede ser utilizado para el seguimiento del progreso del proyecto. En general, se asume que existe relación directa entre porcentaje completo y duración restante. Por ejemplo, cuando una actividad de 4 días está completa al 50%, la duración restante es 2 días. Así, en la figura [fig:EjemploProgresoGantt], se ha marcado a modo de ejemplo el desarrollo de cada una de las tareas con un rectángulo verde en el interior de cada una de ellas. En esa figura, se observa como al terminar el quinto periodo la actividad a está totalmente terminada, la b está en plazo, la c va más avanzada de lo que le correspondería y la d va retrasada. • Se puede apreciar la holgura En el diagrama de la figura [fig:ejemploGantt0] se pueden apreciar de forma muy evidente las relaciones existentes entre actividades, algo que no era posible ver en la tabla inicial. Así mismo se comprueba que la duración total del proyecto será de 12 periodos. De igual forma se comprueba que existen unas actividades (a c, d, f y h ), para las que cualquier aumento de su duración, o en un retraso en la fecha de comienzo supondría un retraso en la duración total del proyecto. Por el contrario, existen otras actividades (b, e, g e i) en las que este retraso no sería tan crítico[nota al pie: Así, por ejemplo, las actividades b y e podrían alargar su duración un periodo sin afectar a la duración total. ]. Las actividades a c, d, f y h forman lo que se denominará posteriormente camino crítico. [flotante Figura: [Figura 1.3: Diagrama de Gantt mostrando el progreso de los trabajos ] ] Inconvenientes • Tamaño A medida que el proyecto crece, este método se muestra menos aplicable. En general no se utiliza para más de 25 actividades y desde luego no es aplicable para más de 100. • Incertidumbre El método no es adecuado para observar sobre él actividades cuando se considera de éstas su posible variación de duración. Muchos de estos problemas se resuelven con la utilización conjunta de los diagramas de Gantt con un método más complejo como, por ejemplo, los grafos pert. 1.3 Los grafos PERT 1.3.1 Antecedentes históricos Desde su aparición, en el año 1958, las modernas técnicas de programación y control de proyectos se han aplicado con éxito a campos muy diversos, tales como explotaciones de recursos naturales, construcciones de barcos o aviones, proyectos de ingeniería civil, introducción en el mercado de un nuevo producto, puesta en órbita de satélites, edición y lanzamiento de libros, instalación y puesta a punto de computadores, etc. El método pert (Program Evaluation and Review Technique) y el método cpm (Critical Path Method) constituyen las dos técnicas pioneras en el campo de la moderna programación y control de proyectos. Tanto el pert como el cpm hicieron su aparición aproximadamente en la misma época (1958). Aunque estas dos técnicas se gestaron a partir de investigaciones totalmente independientes, en sus formas esenciales son idénticas, existiendo sólo ligeras diferencias en sus aspectos formales y de notación. El desarrollo del método pert se inició en 1957, cuando la Marina de los Estados Unidos se enfrentó a los tremendos problemas de coordinación y control que surgieron en la realización del proyecto de submarinos atómicos armados con proyectiles Polaris. Aparte de los problemas técnicos y científicos propios de un proyecto de estas características, surgieron los problemas referentes a la coordinación y al control del mismo. En este proyecto, la Marina de los Estados Unidos debía mantener relación con 250 contratistas directos, con más de 9.000 subcontratistas, además de con un número elevado de agencias gubernamentales, todo lo cual suponía la coordinación de una gran cantidad de recursos y esfuerzos humanos. Los responsables del proyecto vieron enseguida que las técnicas de planificación y control de que podían disponer resultaban insuficientes para aplicarlas con éxito a un proyecto de esta envergadura. Prácticamente, el único método de planificación y control de proyectos que existía en esa época era el diagrama de barras de Gantt. Ante la imposibilidad de programar el proyecto Polaris por medio de un diagrama de Gantt y sobre todo ante la enormidad de la estructura de control y seguimiento que significaba, la Marina de los Estados Unidos decidió emprender una investigación con objeto de obtener una nueva técnica más perfeccionada de programación y control de proyectos. La aplicación del método pert [8, 12, 11, 1] a la programación y al control del proyecto Polaris constituyó un enorme éxito[nota al pie: La duración prevista inicialmente era de cinco años. Su coordinación mediante grafos pert logró que se desarrollara en sólo tres. ] que supuso una rápida difusión del nuevo método de planificación al campo comercial e industrial. Paralelamente, en 1957, la empresa E.I. Du Pont quiso desarrollar un método que le permitiera programar y controlar los proyectos de mantenimiento en sus plantas de fabricación. Con este objeto, Morgan R. Walker, de la división de Ingeniería de la Dupont y James E. Kelley, que trabajaba en el Remington Rand-Univac, desarrollaron el método de planificación de proyectos conocido por cpm o método del camino crítico. Si bien el método cpm fue concebido un año antes, se puede considerar que ambas técnicas son similares y responden a un problema similar que se plantea en ámbitos muy distintos. En lo que sigue y para facilitar la lectura se expondrá un sistema combinado de cpm y pert que permita una mejor comprensión de las técnicas, obviando la génesis original pues ambos métodos son muy similares. 1.3.2 Principios básicos Elementos del grafo El método pert se sirve de los grafos para expresar la planificación temporal del proyecto. Los arcos del grafo representan las actividades del cronograma y los vértices los sucesos. Dentro de cada nodo se suele consignar información asociada al suceso: Índice del nodo: Índice único que identifica al nodo. Ocupa el sector superior del nodo. Al considerar la pareja de índices (nodo inicio, nodo fin) de una actividad se obtiene un identificador de tareas frecuentemente utilizado. Como podemos ver en la ilustración [fig:Esquema-Aij], la actividad A_{ij} parte del suceso inicio i y termina en el suceso fin j . Tiempo temprano: Indica el tiempo mínimo necesario para llegar a ese suceso. Ocupa el sector izquierdo del nodo y, para un cierto nodo k nos referiremos a él como t_{k} . Tiempo tardío: Indica el tiempo límite disponible para la ocurrencia del suceso. Ocupa el sector derecho del nodo y, para un cierto nodo k, nos referiremos a él como t_{k}^{*} . [flotante Figura: [Figura 1.4: Esquema de una actividad A_{ij} ] ] Además, la construcción de un grafo pert que represente el desarrollo de un proyecto requiere inevitablemente la presencia de dos nodos fundamentales: los sucesos de inicio del proyecto y de fin del proyecto. El suceso inicio del proyecto vendrá representado por un nodo del que salen, pero al que no llegan, arcos. El suceso fin del proyecto se representa por un nodo al que llegan, pero del que no salen, arcos. Representación de las prelaciones El método pert permite, de un modo sencillo, establecer las prelaciones existentes entre las diferentes actividades. Estas prelaciones nos indican el orden en que deben ejecutarse dichas actividades. En efecto, por razones de tipo técnico, económico o jurídico, las diferentes actividades que constituyen un proyecto deben ejecutarse según un cierto orden. Así, por ejemplo, en un proyecto de construcción, para poder iniciar la actividad montar las cerchas es necesario que previamente se haya finalizado la actividad montar pilares; para poder iniciar la fase de excavación es necesario que previamente se haya finalizado la actividad de nivelación, etc. Los ejemplos que acabamos de comentar corresponden a prelaciones de carácter técnico. Ahora bien, en ocasiones son condicionantes de tipo económico o jurídico los que imponen las prelaciones, como ocurre cuando, para poder iniciar las obras, se haya tenido que conseguir previamente el correspondiente permiso administrativo. Vamos a estudiar seguidamente de qué manera podemos pasar al grafo las prelaciones. Es decir, cómo conseguiremos que el grafo refleje las prelaciones existentes entre las diferentes actividades que constituyen el proyecto. Comenzaremos por el caso más sencillo, que son las prelaciones lineales. Estas prelaciones se presentan cuando, para poder iniciar una determinada actividad, es necesario que haya finalizado previamente una única actividad (la precedente). Existen prelaciones lineales; por ejemplo, donde para poder iniciar la actividad A_{jk} es necesario que haya finalizado la actividad A_{ij}. Es decir, el vértice j representa el suceso fin de la actividad A_{ij} y, a la vez, el suceso inicio de la actividad A_{jk} (figura [fig:SucesoMultiple] ).[flotante Figura: [Figura 1.5: Prelación lineal: A_{jk} comienza cuando termina A_{ij}. ] ] Existen también prelaciones que originan una convergencia. Este caso se presenta cuando, para poder iniciar una cierta actividad, es necesario que hayan finalizado previamente dos o más actividades precedentes. El caso opuesto es el de las prelaciones que originan una divergencia. Este caso se presenta cuando, para poder iniciar un conjunto de varias actividades, es necesario que haya finalizado previamente la actividad precedente. Nada impide la ocurrencia simultanea de convergencia y divergencia cuando es necesario esperar a la finalización de varias actividades para poder iniciar otro conjunto de ellas.[flotante Figura: [Figura 1.6: Prelación convergente—divergente. ] ]En la figura [fig:convergencia-Divergencia] se ha representado un caso de convergencia-divergencia. Para poder iniciar las actividades c y d es necesario que hayan finalizado las actividades a y b. Es decir, el vértice 3 representa simultáneamente el suceso fin de las actividades a y b y el suceso inicio de las actividades c y d. La construcción del grafo PERT puede resultar más o menos difícil en función de las distintas prelaciones que el grafo deba satisfacer. Consideremos a modo de ejemplo la prelaciones expresadas en la figura [fig:PertFicticia]. Para satisfacer las prelaciones, en la construcción del grafo se ha debido introducir una actividad adicional inexistente que recibe el nombre de ficticia. La actividad ficticia anterior no consumirá tiempo ni recursos, pues su introducción tan sólo sirve par el propósito de reflejar con fidelidad las prelaciones establecidas; únicamente es un enlace lógico que nos permite reflejar formalmente las prelaciones existentes entre las diferentes actividades que constituyen el proyecto. Sí pueden consumir tiempo y recursos aquellas otras actividades ficticias que se utilicen para resolver desplazamientos, esperas, etc. [flotante Figura: --------------------------- Sucesora Predecesora --------------------------- C a D a, b --------------------------- [Figura 1.7: Ejemplo de uso de una actividad ficticia. ] ]. Otro problema que debe tenerse en cuenta en la construcción de grafos PERT es el de las actividades en paralelo. Muchos algoritmos matriciales de planificación temporal, como el de Zaderenko, al igual que la mayor parte de las herramientas software disponibles a tal efecto, codifican las diferentes actividades del cronograma mediante la pareja de indicadores de sus nodos de inicio y fin. Consideremos, a modo de ejemplo, el grafo correspondiente a la figura [fig:Fusionadas]. No es posible asignar el identificador 2—3 simultáneamente a tres actividades[nota al pie: Las que comienzan en el nodo 2 y terminan en el nodo 3: b, c y d. ].[flotante Figura: [Figura 1.8: Ambigüedad en la codificación de actividades mediante identificadores inicio—fin. ] ] Para eliminar la ambigüedad se puede recurrir nuevamente a las actividades ficticias (figura [fig:RompeZaderenko]). La adición de un par de actividades ficticas y sus sendos nodos fin permite distinguir, ahora sí, entre las actividades B, C y D, pues aún naciendo en el mismo vértice, mueren en vértices distintos.[flotante Figura: [Figura 1.9: Códificación unívoca de actividades mediante identificadores inicio—fin. ] ] El entramado de relaciones que deberán reflejarse en las actividades que se desarrollan entre el inicio y el final del proyecto pueden venir recogidas, para mayor conveniencia, en una matriz como la representada en el cuadro [tab:Matriz-de-prelaciones] y en la que nos basaremos para construir su grafo (figura [fig1:PertEjemplo] ).[flotante Cuadro: | A | B | C | D | E | F | G | H | I | J | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ A | | | | | | | | | | | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ B | | | | | | | | | | | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ C | \bigotimes | | | | | | | | | | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ D | \bigotimes | | | | | | | | | | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ E | | \bigotimes | \bigotimes | | | | | | | | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ F | | \bigotimes | \bigotimes | \bigotimes | | | | | | | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ G | | | | | | \bigotimes | | | | | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ H | | | | | \bigotimes | | | | | | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ I | | | | | | | \bigotimes | | | \bigotimes | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ J | | | | | | \bigotimes | | | | | -----+-------------+--------------+--------------+--------------+--------------+--------------+--------------+----+----+--------------+ [Cuadro 1.1: Matriz de prelaciones entre actividades. ] ] Es interesante destacar que aquellas filas de la matriz de prelaciones en las que no aparece ninguna marca se corresponden precisamente con las actividades que no tienen ningún precedente, las tareas iniciales del proyecto[nota al pie: El nodo inicio del proyecto hará las funciones de nodo de inicio de estas actividades, como se puede fácilmente comprender con tan sólo reparar en el hecho de que el proyecto realmente comenzará cuando comience alguna de estas actividades. ]. En nuestro ejemplo (cuadro [tab:Matriz-de-prelaciones]) puede verse cómo las dos primeras filas de la matriz no tienen ninguna marca y, por tanto, a y b son las actividades inicio del proyecto. Por otra parte, aquellas columnas de la matriz en las que no aparece ninguna marca se corresponden con aquellas actividades que no tienen ninguna actividad siguiente, las tareas finales del proyecto[nota al pie: Cuyo suceso final coincide con el suceso fin del proyecto. ]. En este caso se aprecia cómo las columnas correspondientes a las actividades h e i no tienen ninguna marca y, por tanto, éstas son las actividades finales del proyecto.[flotante Figura: [Figura 1.10: Ejemplo de grafo pert ] ] Solapamientos y desplazamientos Es posible definir otro tipo de relaciones entre las actividades, además de las ya vistas de convergencia, divergencia y lineales. Estas relaciones son las denominadas solapamientos y desplazamientos. Los solapamientos ocurren cuando es posible realizar más de una tarea al mismo tiempo. Por ejemplo, se parte de un grafo PERT como el de la figura [fig:solapamiento][flotante Figura: [Figura 1.11: Indefinición en el solapamiento de las actividades A y C. ] ] y se desea representar que la tarea C no tiene por qué esperar a que termine por completo la tarea A, sino que puede comenzar a los tres días de haber comenzado la A. Esto se representaría dividiendo la tarea A en dos subtareas, de forma que una de ellas tenga una duración de 3 y la otra de 2, tal como se muestra en la figura [fig:representacion-solapamiento].[flotante Figura: [Figura 1.12: Representación de un solapamiento mediante la subdivisión de tareas. ] ] En la figura [fig:representacion-solapamiento] también se puede ver como la tarea B sí espera a que termine por completo la tarea A. Por el contrario, los desplazamientos se producen cuando una tarea no puede comenzar inmediatamente después de que haya terminado su predecesora, sino que debe esperar un cierto tiempo. Esto se representaría en el método PERT mediante una tarea ficticia que no consuma recursos, pero si tiempo. En la figura [fig:representacion-desplazamiento] se ha representado el que la tarea B deba esperar 2 unidades de tiempo antes de poder empezar, mientras que por el contrario, la tarea C puede comenzar inmediatamente. La tarea ficticia es la representada por f(2). [flotante Figura: [Figura 1.13: Representación de un desplazamiento mediante la utilización de actividades ficticias. ] ] Una vez construido el grafo pert se procederá a calcular los tiempos tempranos y tardíos de cada uno de los nodos del grafo. Cálculo de los tiempos tempranos El cálculo de los tiempos tempranos permitirá conocer el mínimo tiempo que por fuerza habrá de transcurrir para poder llegar a un determinado nodo. En particular, el tiempo temprano del suceso fin del proyecto tiene una importancia especial pues nos indica el tiempo mínimo necesario para poder finalizar el proyecto, es decir, su duración estimada. Su cálculo se puede efectuar sobre el propio grafo, comenzando por el suceso inicio del proyecto al que se asigna un tiempo temprano de valor 0. A continuación, se recorren los nodos del grafo en orden creciente determinando para cada uno de ellos su tiempo temprano hasta llegar al suceso fin del proyecto. El tiempo temprano de un determinado nodo se determina como el mayor valor de entre los que se obtienen al sumar, para cada actividad que termina en ese nodo, su duración más el tiempo temprano de su nodo de inicio. Es decir, para un cierto suceso j , su tiempo temprano t_{j} se calculará mediante la expresión: La figura [fig:Grafo-2Pert] facilita la comprensión del procedimiento descrito al mostrar su aplicación al grafo de ejemplo recogido en la anterior figura [fig1:PertEjemplo]. Para cada actividad se ha indicado entre paréntesis, y al lado de su nombre, su duración estimada. Además, para ilustrar el procedimiento, se han consignado bajo cada arco las sumas correspondientes a la expresión [eq:For1] a fin de facilitar la reconstrucción del cálculo por parte del alumno.[flotante Figura: [Figura 1.14: Cálculo de los tiempos tempranos. ] ] Cálculo de los tiempos tardíos Los tiempos tardíos de los sucesos tienen una importancia fundamental en la ejecución del proyecto, puesto que si no se llega a un nodo antes de que se cumpla su tiempo tardío, el proyecto verá aumentada su duración estimada lo que, salvo oportuna intervención del dirección del proyecto, derivará en un retraso del proyecto y posiblemente, por tanto, en su fracaso. El procedimiento de cálculo de estos tiempos comienza por el nodo fin del proyecto, cuyo tiempo tardío coincide con su tiempo temprano. A continuación, se recorren los nodos en orden decreciente determinando para cada uno de ellos su tiempo tardío hasta llegar al suceso inicio del proyecto. El tiempo tardío de un determinado nodo se determina como el menor valor de entre los que se obtienen al restar, para cada actividad que termina en ese nodo, el tiempo tardío de su nodo de finalización menos su duración. Es decir, para un cierto suceso i , su tiempo tardío t_{i}^{*} se calculará mediante la expresión: La figura [fig:Grafo-3Pert] facilita la comprensión del procedimiento descrito para el cálculo de los tiempos tardíos al mostrar su aplicación al grafo cuyos tiempos tempranos ya calculamos en el apartado anterior. De forma semejante, se han consignado bajo cada arco las restas correspondientes a la expresión [eq:For2] a fin de facilitar la reconstrucción del cálculo por parte del alumno.[flotante Figura: [Figura 1.15: Cálculo de los tiempos tardíos. ] ] Algoritmo de Zaderenko El procedimiento descrito para el cálculo de los tiempos tempranos y tardíos es sencillo y fácil de aplicar si el grafo correspondiente no es muy complejo. En grafos pert formados por numerosas actividades, el procedimiento anterior puede volverse engorroso. A tal efecto, Zaderenko propuso un modo matricial de cálculo de tiempos tempranos y tardíos que resulta muy sencillo, tanto en grafos pequeños como en grafos muy grandes. Comenzaremos construyendo una matriz cuadrada cuya dimensión sea igual al número de nodos que posea el grafo (figura [tabla:Zaderenko] ). Los elementos de esta matriz indican los tiempos pert de las actividades que nacen en el vértice que corresponde a la fila que cruza ese elemento y finalizan en el vértice que corresponde a la columna que cruza dicho elemento.[flotante Cuadro: +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | \downarrow t_{i} | i\diagdown i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | 0 | 1 | \times | 2 | 3 | | | | | | | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | 2 | 2 | | \times | 7 | 8 | | | | | | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | 9 | 3 | | | \times | 0 | 3 | | | | | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | 10 | 4 | | | | \times | | 9 | | | | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | 12 | 5 | | | | | \times | | | | 2 | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | 19 | 6 | | | | | | \times | 10 | 8 | | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | 29 | 7 | | | | | | | \times | 0 | | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | 29 | 8 | | | | | | | | \times | 2 | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | 31 | 9 | | | | | | | | | \times | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ | | \underleftarrow{t_{i}^{*}\quad} | 0 | 2 | 10 | 10 | 29 | 19 | 29 | 29 | 31 | +-------------------+----------------------------------+----------+----------+----------+----------+----------+----------+----------+----------+---------+ [Cuadro 1.2: Matriz de Zaderenko para el cálculo de los tiempos tempranos y tardíos del proyecto del ejemplo. ] ] Para calcular los tiempos tempranos se comienza por agregar una columna adicional en la parte izquierda de la matriz, en la que se irán escribiendo los valores de los tiempos tempranos. El primer elemento de esa columna es 0, ya que éste es el valor del tiempo temprano del suceso inicio del proyecto. Para calcular los tiempos tempranos de los demás sucesos se opera de la siguiente manera: se suman los elementos de la columna que corresponde al suceso cuyo tiempo temprano estamos calculando, a los elementos de la columna adicional que representen sucesos en los que comienzan actividades que finalizan en el suceso del que estamos calculando su tiempo tempranos. De todas las sumas obtenidas, la mayor nos indicará el tiempo temprano buscado. Para calcular los tiempos tardíos se comienza por agregar una fila adicional en la parte inferior de la matriz, en la que se irán escribiendo los valores de los tiempos tardíos. El primer elemento de esa fila (contando por la derecha) tendrá el valor del suceso fin del proyecto, que, como sabemos, coincide con su tiempo temprano. Para calcular los tiempos tardíos de los demás sucesos se opera de la siguiente manera: se restan los elementos de la fila que corresponde al suceso cuyo tiempo tardío estamos calculando, a los elementos de la fila adicional que representan sucesos en los que finaliza la actividad que comienza en el suceso cuyo tiempo tardío estamos calculando. De todas las diferencias obtenidas, la menor nos indicará el tiempo tardío buscado. La figura [fig:Grafo-PERT-COMPLETO] muestra los tiempos tempranos y tardíos para el grafo del ejemplo.[flotante Figura: [Figura 1.16: Grafo pert con tiempos tempranos y tardíos. ] ] Sobre ella trabajaremos a continuación para determinar las holguras y el camino crítico. Holgura de un suceso La verdadera importancia de los tiempos temprano y tardío reside en que constituyen la base para el cálculo de las holguras, que son la pieza fundamental en todo el proceso de análisis del método pert. Comenzaremos definiendo el concepto de holgura de suceso. La holgura de un cierto suceso i, que representaremos por H_{i}, se define como la diferencia entre los tiempos tardío y temprano de dicho suceso, es decir: La holgura de un suceso nos indica el tiempo en que puede retrasarse la ocurrencia del mismo, de manera que la duración del proyecto no experimente ningún retraso. A continuación, vamos a definir el concepto de holgura total de una actividad. Holgura total de una actividad La holgura total de una cierta actividad A_{ij} , que representaremos por H_{ij}^{T}, se define como el tiempo que resulta de restar al tiempo tardío del suceso final el tiempo temprano del suceso inicial y la duración de la actividad, es decir: La holgura total de una actividad nos indica el número de unidades de tiempo en que puede retrasarse la realización de la actividad con respecto al tiempo previsto, de manera que la duración del proyecto no experimente ningún retraso. Es muy importante tener en cuenta que si una actividad A_{ij} consume la totalidad o parte de su holgura total, este hecho puede producir una disminución en la holgura total de la actividad siguiente, al aumentar el temprano t_{j} . Aquellas actividades cuya holgura total sea cero se denominan actividades críticas. Para que una actividad sea crítica es condición necesaria, aunque no suficiente, que la holgura de los sucesos inicio y fin de la actividad sea cero. Los caminos desde el nodo inicio del proyecto al nodo fin del proyecto formados por las actividades críticas reciben el nombre de caminos críticos y resultan esenciales para efectuar el control del proyecto. En efecto, el responsable del proyecto deberá extremar la vigilancia de estas actividades críticas, pues un retraso en la realización de cualquiera de ellas producirá un retraso en la finalización del proyecto. Por otra parte, el responsable del control del proyecto no debe desatender a las actividades no críticas, pues un retraso excesivo en su ejecución puede llegar a convertirlas en críticas, cambiando la estructura del camino crítico del grafo.[flotante Figura: [Figura 1.17: Determinación del camino crítico en el grafo pert del ejemplo. ] ] Una vez establecidos e interpretados los conceptos de holgura de suceso, holgura total de una actividad y camino crítico de un grafo PERT, pasamos a estudiar los conceptos de holgura libre y holgura independiente de una actividad.[nota al pie: Estos conceptos no son específicos del método pert, sino que pertenecen al método cpm, aunque con el nombre de flotantes libres e independientes. No obstante, como ya habíamos comentado en el apartado anterior, estas holguras, pese a no ser propias del pert, proporcionan una información complementaria muy útil, por lo que las vamos a incorporar a la fase de análisis del método pert. ] Holgura libre de una actividad Comenzaremos por el concepto de holgura libre de una actividad. La holgura libre de una cierta actividad A_{ii} , que representaremos por H_{ij}{}^{L}, se define como el tiempo que resulta de restar al tiempo temprano del suceso final el tiempo temprano del suceso inicial y la duración de la actividad, es decir: La holgura libre de una actividad nos indica la cantidad de tiempo disponible después de haber realizado la actividad, si todas las actividades del proyecto han comenzado en sus tiempos tempranos. Es decir, la holgura libre representa la parte de la holgura total que puede ser consumida sin perjudicar a las siguientes actividades. De la observación de las ecuaciones [eq:For4] y [eq:For5], se deduce que la holgura libre de una cierta actividad será siempre menor o igual[nota al pie: Para que ambas holguras sean iguales es condición necesaria y suficiente que la holgura del suceso fin de la actividad sea cero, pues en tal caso los tiempos temprano y tardío del suceso fin de la actividad coinciden, t_{j}=t_{j}^{*}, por lo que las ecuaciones [eq:For4] y [eq:For5], se hacen iguales. ] que su holgura total. Holgura independiente de una actividad Finalmente, vamos a establecer el concepto de holgura independiente de una actividad. La holgura independiente de una cierta actividad A_{ij} , que representaremos por H_{ij}^{I}, se define como el tiempo que resulta de restar al tiempo temprano del suceso final el tiempo tardío del suceso inicial y la duración de la actividad, es decir: La holgura independiente de una actividad nos indica la cantidad de tiempo disponible después de haber realizado la actividad, si todas las actividades del proyecto han comenzado en sus tiempos tardío. Esta holgura es escasa y a veces negativa. De la observación de las ecuaciones [eq:For5] y [eq:For6] se deduce que la holgura independiente de una cierta actividad será siempre menor o igual[nota al pie: Para que ambas holguras sean iguales es condición necesaria y suficiente que la holgura del suceso inicio de la actividad sea cero, pues en tal caso los tiempos temprano y tardío del suceso inicio de la actividad coinciden t_{i}=t_{j}^{*}, por lo que las ecuaciones [eq:For5] y [eq:For6] se hacen iguales. ] que su holgura libre. La condición necesaria y suficiente para que las tres holguras de actividad coincidan es que las holguras del suceso inicio y del suceso fin de una actividad sean nulas. El cuadro [tabla:HolgurasTable] recoge los tiempos y holguras del proyecto considerado en la figura [fig:GraficoCC] a modo de ejemplo.[flotante Cuadro: i—j A_{ij} t_{ij} t_{i} t_{j} t_{i}^{*} t_{j}^{*} H_{i} H_{j} H_{ij}^{T} H_{ij}^{L} H_{ij}^{I} Crítica ----------------------------------------------------------------------------------------------------------------------------------------------- 1—2 A 2 0 2 0 2 0 0 0 0 0 Sí 1—3 B 3 0 9 0 10 0 1 7 6 6 No 2—3 C 7 2 9 2 10 0 1 1 0 0 No 2—4 D 8 2 10 2 10 0 0 0 0 0 Sí 3—5 E 3 9 12 10 29 1 17 17 0 -1 No 4—6 F 9 10 19 10 19 0 0 0 0 0 Sí 5—9 H 2 12 31 29 31 17 0 17 17 0 No 6—7 J 10 19 29 19 29 0 0 0 0 0 Sí 6—8 G 8 19 29 19 29 0 0 2 2 2 No 8—9 I 2 29 31 29 31 0 0 0 0 0 Sí ----------------------------------------------------------------------------------------------------------------------------------------------- [Cuadro 1.3: Holguras de las actividades del proyecto del ejemplo ] ] Establecimiento de un calendario de ejecución del proyecto Este calendario establece para cada actividad A_{ij} cuatro fechas: \Delta_{ij} : Fecha de comienzo más temprana Será igual a la dada por el tiempo temprano del suceso inicio de la actividad, es decir: \Delta_{ij}^{*} : Fecha de comienzo más tardía Indica lo más tarde que puede comenzarse la actividad A_{ij}, de manera que la duración prevista del proyecto no se retrase en ninguna unidad de tiempo. Dicha fecha será igual a la dada por la suma del tiempo temprano del suceso inicial y la holgura total de la actividad, es decir: Teniendo en cuenta la fórmula de la holgura total de una actividad, dada por la ecuación [eq:For4], convertimos la expresión [eq:For8] en: \nabla_{ij} : Fecha de finalización más temprana Dicha fecha será igual a la dada por la suma del tiempo temprano del suceso inicial y el la duración prevista para esa actividad, es decir: \nabla_{ij}^{*} : Fecha de finalización más tardía. Indica la fecha tope en que puede finalizarse la actividad A_{ij} , de manera que la duración prevista del proyecto no aumente. Obviamente, dicha fecha será igual a la dada por el tiempo tardío del suceso final de la actividad, es decir: Como es fácil comprobar mediante simple substitución de las anteriores expresiones: La ecuación [eq:ht_interesante] permite constatar cómo para una actividad crítica las fechas de comienzo más temprana y más tardía coinciden; como también coinciden en ese caso las fechas de finalización más temprana y más tardía. El cálculo del calendario de ejecución del proyecto permite representar, por ejemplo, un diagrama de Gantt más completo, como el mostrado en la figura [fig:calendario] correspondiente al grafo pert de la figura [fig:Grafo-PERT-COMPLETO].[flotante Figura: [Figura 1.18: El diagrama de Gantt permite visualizar con claridad el calendario ] ] El cuadro [tabla:calendatabla], por otra parte, detalla las fechas concretas de ejecución del proyecto mencionado considerando que comienza el 17 de octubre y que no serán laborables ni los sábados, ni el 1 de noviembre. Así, por ejemplo, para la actividad c tendremos: \Delta_{2\ 3}=2 19 octubre \Delta_{2\ 3}^{*}=2+1=3 20 octubre \nabla_{2\ 3}=2+7=9 28 octubre \nabla_{2\ 3}^{*}=10 31 octubre [flotante Cuadro: Actividad Fecha de comienzo Fecha de finalización ----------------------------------------------------------------- A 17 octubre 19 de octubre B 17–26 octubre 20–31 octubre C 19–20 octubre 28–31 octubre D 19 octubre 31 octubre E 28 octubre–23 noviembre 2–28 noviembre F 31 octubre 14 noviembre G 14–16 noviembre 24–28 noviembre H 3–28 noviembre 7–30 noviembre I 28 noviembre 30 noviembre J 14 noviembre 28 noviembre ----------------------------------------------------------------- [Cuadro 1.4: Calendario de ejecución del proyecto del ejemplo ] ] 1.4 La programación y el coste 1.4.1 El problema del plazo y el coste La duración de una actividad se comporta como una variable aleatoria. Esto quiere decir que, dentro de un contexto determinado y para los parámetros que son válidos en dicho contexto, esta duración puede tomar valores mayores o menores. Sin embargo, a parte de las naturales oscilaciones respecto a un valor central debidas a fenómenos aleatorios que podríamos considerar debidas a perturbaciones, el equipo de dirección de proyectos debería disponer de medios eficaces para alterar el curso que, por natura, seguiría el desarrollo de las actividades. Por lo general, estas medidas conducen a una reducción del plazo necesario para ejecutar una tarea, habitualmente mediante: • La mejora de los procesos productivos Aplicar procesos de calidad refinada permite evitar retrasos debidos a pérdidas de tiempo innecesarias o a reprocesos • La mejora del perfil de los recursos aplicados en el desarrollo de las actividades La utilización de los recursos más idóneos permite una mayor eficacia en el desempeño de los trabajos • Un cambio en el grado de utilización de los recursos Con frecuencia, la modificación del número de recursos empleados acelera su ejecución. La modificación puede suponer un aumento, con lo que se pretende acelerar una actividad cuya lentitud se debía a la falta de recursos; o puede ser también un decremento, con lo que se pretende evitar obstáculos en la comunicación y coordinación de la actividad. Naturalmente, la aplicación de estas medidas puede conllevar un coste asociado, apareciendo entonces una relación funcional entre el coste y el tiempo de ejecución de una actividad. De esta forma surge la programación de proyectos a coste mínimo, también llamada técnica mce (Minimum Cost Expediting). La naturaleza discontinua y temporal hace que, con frecuencia, sea la tercera de estas medidas la adoptada por el director de proyectos[nota al pie: La mejora de los procesos entraría dentro de los aspectos de mejora continua del sistema de gestión de la calidad de las organizaciones ejecutantes de las actividades y sus resultados probablemente fueran percibidos superado ya el plazo admisible. La mejora del perfil de los recursos aplicados en el desarrollo de las actividades tampoco parece ser un medio del que siempre pueda disponer el director de proyectos: las características del mercado de trabajo y el hecho de que el director de proyectos no siempre escoge a los miembros de los equipos que realizan las actividades hacen que esta opción tampoco sea la más frecuente. ] a fin de modificar los plazos de ejecución de las actividades y así dotar al proyecto de unas condiciones más idóneas. El método mce considerará pues diferentes posibles duraciones del proyecto según sean los niveles elegidos de utilización de los recursos[nota al pie: Supondremos entonces, sin falta de generalidad, que estos sobrecostes son debidos a un diferente grado de utilización de los recursos disponibles. ]. Para cada uno de estos niveles, el mce pretende determinar el tiempo de ejecución de las diferentes actividades, de forma que el coste global de ejecución del proyecto sea mínimo. En el método mce se considera que para cada actividad en que se descompone el proyecto existen dos tiempos de ejecución distintos: el tiempo normal y el tiempo tope. A cada uno de estos tiempos les corresponde un coste de ejecución diferente. Situemos pues, en unos ejes de coordenadas, en abscisas las duraciones de las actividades y en ordenadas los costes inherentes a la ejecución de las mismas (figura [fig:curvaCCTT]) y llamemos, para una actividad genérica A_{ij} : T_{ij} : Tiempo normal de ejecución de la actividad A_{ij} C_{ij}^{\ T} : Coste inherente a la ejecución de la actividad A_{ij} en el tiempo normal T_{ij} t_{ij} : Tiempo tope de ejecución de la actividad A_{ij} C_{ij}^{\ t} : Coste inherente a la ejecución de la actividad A_{ij} en el tiempo tope t_{ij} x_{ij} : Posible duración de la actividad A_{ij} determinada a partir del grado de utilización de los recursos El punto A\left(T_{ij},\ C_{ij}^{\ T}\right) es el llamado punto normal, que corresponde a la duración y coste de ejecución de la actividad estimados éstos con el grado de utilización de recursos inicialmente considerado. El punto B\left(t_{ij},\ C_{ij}^{\ t}\right) es el llamado punto tope, que corresponde a la mínima duración factible de la actividad (tiempo tope) y a su coste asociado. Los puntos A y B estarán unidos por una cierta curva. C_{ij}^{x_{ij}}=g\left(x_{ij}\right) llamada curva coste–duración. [flotante Figura: [Figura 1.19: Curva coste–duración. ] ] Al llegar a este punto del razonamiento el método mce establece una hipótesis que resulta básica en este procedimiento. Según esta hipótesis se admite la existencia de una ley homotética entre la disminución de los tiempos de ejecución de las actividades y sus correspondientes costes suplementarios, es decir, existe una proporcionalidad estricta entre las disminuciones de los tiempos de ejecución y los costes inherentes a estas reducciones. Indudablemente, este supuesto es muy fuerte y poco realista en la mayor parte de los casos. En efecto, normalmente conforme va disminuyendo el tiempo de ejecución de las actividades, los correspondientes costes van aumentando de una manera más que proporcional (costes marginales crecientes)[nota al pie: Puede darse el caso inverso, a menor duración menor coste. Piénsese, por ejemplo, en una actividad cuyo coste de ejecución dependa fuertemente del número de periodos en que se contrate un alquiler. ]. Así, en un ejemplo de alicatado de un edificio, la reducción en el tiempo de ejecución de las actividades podría hacerse por medio de la introducción de horas extraordinarias. Ahora bien, el coste de las horas extraordinarias suele ser mayor que el de las horas normales. Por tanto, la reducción en el tiempo de ejecución de esta actividad implicará un coste marginal creciente (por ejemplo, es muy probable que la reducción del tiempo de ejecución de esta actividad de 25 a 23 semanas suponga un coste suplementario inferior al de reducir dicho tiempo de ejecución de 23 a 21 semanas), por lo que no se cumplirá el supuesto básico del método mce. No obstante, la hipótesis anterior se introduce como una aproximación a la realidad, que nos permitirá abordar el problema de la reducción de los tiempos de ejecución de las actividades de una manera operativa. En efecto, la introducción de esta hipótesis nos permitirá convertir el problema de la programación de proyectos a coste mínimo en un problema de programación lineal paramétrica. Ahora bien, si por el contrario no introdujéramos este supuesto simplificativo y trabajáramos con diferentes tipos de funciones de costes (cuadráticas, cúbicas, etc.), el método mce nos obligaría a abordar complicados problemas de optimización no lineal. La hipótesis que acabamos de comentar implica que las curvas coste–duración son líneas rectas. Para la actividad A_{ij} la ecuación de la recta que une los puntos A y B y, por tanto, la correspondiente función coste–duración, es igual a: [flotante Figura: [Figura 1.20: Coste suplementario por la reducción del tiempo de ejecución de la actividad A_{ij} . ] ] Otra manera de plantear el problema del coste podría ser el de relacionar las duraciones de las actividades con los costes suplementarios inherentes a las correspondientes reducciones. En este caso la ordenada del punto A (punto normal) de la recta coste suplementario-duración sería cero, ya que para el tiempo normal de ejecución no se incurre en ningún sobrecoste adicional. En cuanto a la ordenada del punto B (punto tope) de la recta coste suplementario-duración será igual al sobrecoste en que se incurre por reducir el tiempo de ejecución de la actividad A_{ij} desde su tiempo máximo T_{ij} a su tiempo mínimo t_{ij}. Este coste suplementario S_{ij}^{\ t} se obtendría restando al coste máximo C_{ij}^{\ t} el coste mínimo C_{ij}^{\ T}, es decir: Por tanto, la correspondiente ecuación de la recta coste suplementario-duración, que está representada en la figura  [fig:CosteSuplementarioAij] , será igual a: La pendiente de las rectas [eq:RectaC] y [eq:RectaS], que obviamente es la misma, representa el coste suplementario en que se incurre por reducir la duración del proyecto en una unidad de tiempo; es decir, el coste marginal en concepto de reducción. Este coste marginal se denominará en lo sucesivo coste unitario de reducción. 1.4.2 El algoritmo de Ackoff y Sasieni En la figura [fig:PERTejemploMaximos] hemos representado el grafo pert de un proyecto descompuesto en nueve actividades: A, B, C, D, E, F, G, H e I. Asimismo, en dicha figura están reflejados los tiempos tempranos de los diferentes sucesos, que se han calculado de acuerdo con los tiempos normales de ejecución de las actividades. Estos tiempos normales están contenidos en la columna T_{ij} de la figura [tab:DatosPERT]. Como el tiempo temprano del suceso fin del proyecto es 35, podemos afirmar que si las actividades se realizan en sus tiempos normales, la duración del proyecto será de 35 unidades de tiempo. [flotante Figura: [Figura 1.21: Grafo PERT con duraciones máximas ] ] Por otra parte, en la figura [fig:PERTejemploTopes] están reflejados los tiempos temprano de los diferentes sucesos, calculados esta vez de acuerdo con los tiempos tope de ejecución de las actividades. Estos tiempos tope están contenidos en la columna t_{ij} de la tabla [tab:DatosPERT]. En este caso, el tiempo temprano del suceso fin del proyecto es de 21. Es decir, para los tiempos tope, la duración del proyecto será de 21 unidades de tiempo. Del razonamiento efectuado hasta ahora, se desprende que es posible elegir cualquier duración del proyecto comprendida entre 21 y 35 unidades de tiempo. Una vez elegida la duración correspondiente, se deberá determinar el tiempo de ejecución de las diferentes actividades, de manera que el correspondiente coste suplementario en concepto de reducción del tiempo de ejecución del proyecto sea mínimo. Para poder programar estos tiempos de ejecución deberemos conocer los costes unitarios de reducción de las diferentes actividades. Estos costes están contenidos en la columna CUR_{ij} de la tabla [tab:DatosPERT].[flotante Figura: [Figura 1.22: Grafo PERT con duraciones tope. ] ][flotante Cuadro: i–j T_{ij} t_{i} CUR_{ij} -------------------------------------- 1-2 8 4 2 1-3 10 5 4 1-4 12 6 3 2-4 10 6 4 2-5 14 9 3 3-4 7 5 5 3-6 12 8 2 4-5 7 4 5 5-6 10 7 1 -------------------------------------- [Cuadro 1.5: Datos del ejemplo de reducción de la duración del proyecto con mínimo coste. ] ] Aunque el método mce nos lleva a la resolución de un programa lineal paramétrico, en la práctica suele resolverse este problema mediante algoritmos específicos, que resultan más sencillos de aplicar que los algoritmos propios de la programación lineal paramétrica. Vamos a exponer un algoritmo heurístico, muy sencillo, debido a Ackoff y Sasieni, que resulta muy práctico en proyectos descompuestos en un número no demasiado elevado de actividades. Para explicar este algoritmo nos vamos a apoyar en los datos del proyecto del apartado anterior. Para aplicar el algoritmo de Ackoff y Sasieni a la programación de nuestro proyecto, comenzaremos por construir un cuadro, con arreglo, a la estructura que del cuadro [tab:AckoffSassieni] que vamos a comentar seguidamente:[flotante Cuadro: A B C D G E H F I \wp_{0} \wp_{1} \wp_{2} \wp_{3} \wp_{4} \wp_{5} \wp_{6} -------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------- \pi_{1} 3 5 1 29 26 26 23 23 23 21 \pi_{2} 4 5 5 1 34 31 31 28 25 23 21 \pi_{3} 2 4 5 1 35 32 31 28 25 23 21 \pi_{4} 2 3 1 32 29 28 28 25 23 21 \pi_{5} 4 2 22 22 22 22 19 17 17 -------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------- \wp_{0} 4 5 6 4 5 2 4 3 3 \wp_{1} 4 5 6 4 5 2 4 3 0 {\scriptstyle \Delta\mathrm{I}=-3} {\scriptstyle \Delta S=3\times1=3} \wp_{2} 3 5 6 4 5 2 4 3 0 {\scriptstyle \Delta\mathrm{A}=-1} {\scriptstyle \Delta S=1\times2=2} \wp_{3} 3 5 6 4 5 2 4 0 0 {\scriptstyle \Delta\mathrm{F}=-3} {\scriptstyle \Delta S=3\times5=15} \wp_{4} 0 2 6 4 5 2 4 0 0 {\scriptstyle \Delta\mathrm{A,B}=-3} {\scriptstyle \Delta S=3\times\left(4+2\right)=18} \wp_{5} 0 0 6 2 3 2 4 0 0 {\scriptstyle \Delta\mathrm{B,D,G}=-2} {\scriptstyle \Delta S=2\times\left(4+4+3\right)=22} \wp_{6} 0 0 4 0 1 0 4 0 0 {\scriptstyle \Delta\mathrm{C,D,E,G}=-2} {\scriptstyle \Delta S=2\times\left(3+4+3+5\right)=30} -------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------- [Cuadro 1.6: Algoritmo de Ackoff–Sasieni aplicado al grafo pert del ejemplo ] ] En la primera columna aparece el nombre \pi_{i} de todos los posibles caminos que van desde el vértice que representa el suceso inicio del proyecto al vértice que representa el suceso fin del proyecto —parte superior— así como también la indicación del número de paso \left(\wp_{i}\right) en el algoritmo —parte inferior—. Las nueve columnas siguientes se utilizan para representar las diferentes actividades en que se ha descompuesto el proyecto. Debajo de cada actividad se escribe el coste unitario de reducción (tabla [tab:DatosPERT]) siempre que esa actividad forme parte del camino \pi_{i} correspondiente. Si, por el contrario, la actividad no forma parte de dicho camino, se deja en blanco el espacio correspondiente. En cada iteración rellenaremos una fila y una columna \wp_{i} El cuadro se completa, inicialmente, con una columna y una fila que marcarnos con un \wp_{0} . Los elementos de la columna \wp_{0} son las longitudes generalizadas de los caminos representados en las filas correspondientes, calculadas en base a los tiempos normales de ejecución (tabla [tab:DatosPERT]). Los elementos de la fila \wp_{0} representan las reducciones posibles \left(T_{ij}-t_{ij}\right) de las diferentes actividades. De la observación de la columna \wp_{0} se deduce que la duración del proyecto es de 35 unidades de tiempo y que si queremos reducir dicha duración habrá que reducir la duración del camino \pi_{3} , ya que este camino es el crítico. Para reducir la duración de este camino será necesario reducir el tiempo de ejecución de alguna de las actividades que lo forman. Para ello elegiremos aquella actividad cuyo coste unitario de reducción sea más pequeño. En nuestro, caso, se trata de la actividad i, ya que su coste unitario de reducción es uno. La reducción máxima que puede efectuarse en la duración de esta actividad es de 3 unidades de tiempo, según nos lo indica el elemento correspondiente de la fila \wp_{0}. Esta reducción origina un cambio en las longitudes generalizadas de aquellos caminos que contienen a la actividad i. Estas nuevas longitudes generalizadas están reflejadas en la columna marcada con \wp_{1}  . De esta columna se deduce que la duración del proyecto ha pasado a ser de 32 unidades de tiempo.[flotante Figura: [Figura 1.23: Evolución del sobrecoste a medida que se reduce la duración del proyecto. ] ] El sobrecoste en concepto de reducción lo obtendremos multiplicando el coste unitario de reducción (que es 1) por la correspondiente reducción de tiempo (que es de 3); es decir, en este caso el sobrecoste debido, a la reducción es de 3 unidades monetarias. En la figura [fig:EvolucionSobrecoste] hemos representado el punto de la función sobrecostes–tiempos de ejecución del proyecto, que acabamos de obtener (la abscisa de este punto es de 32, y la ordenada de 3). Para completar esta etapa del algoritmo agregamos al cuadro una nueva fila, que marcamos con un \wp_{1}, en la que figuran las reducciones posibles que presentan ahora las diferentes actividades. De la observación de la columna \wp_{1} se deduce que la duración del proyecto es ahora de 32 unidades de tiempo, y que el camino, crítico sigue siendo el \pi_{3}. Para reducir la duración de dicho camino, reduciremos el tiempo de ejecución de aquella actividad que, formando parte de ese camino, tenga el coste unitario de reducción más pequeño, siempre que sea todavía susceptible de reducción. En nuestro caso se trata de la actividad A, ya que su coste unitario de reducción es de 2. En efecto, la actividad i tiene un coste unitario de reducción más pequeño, pero según nos indica el correspondiente cero de la fila \wp_{1} , la duración de esta actividad no puede reducirse más. En cuanto a la reducción máxima posible de la actividad a, en principio es de 4 unidades de tiempo, según nos indica el correspondiente elemento de la fila \wp_{1} . Ahora bien, hay que tener en cuenta que cualquier reducción que hagamos del tiempo de ejecución de la actividad a superior a la unidad no repercutirá en el tiempo de ejecución del proyecto, pues la longitud generalizada del camino \pi_{2} es de 31 unidades de tiempo, es decir, una unidad inferior a la del camino \pi_{3}. Por tanto, la reducción máxima que podemos efectuar en la actividad a es de 1 unidad de tiempo. Las nuevas longitudes generalizadas de los diferentes caminos están reflejadas en la columna marcada con un \wp_{2} . De esta columna se deduce que la duración del proyecto ha pasado a ser de 31 unidades de tiempo. En este caso, el sobrecoste debido a la reducción es de 2 unidades monetarias (ya que el coste unitario de la reducción es de 2, y la reducción introducida, de 1 unidad de tiempo). En la figura [fig:EvolucionSobrecoste] representamos el punto de la función sobrecostes–tiempos de ejecución del proyecto que acabamos de obtener (la abscisa de este punto es 31 y la ordenada 5, que es la suma de los sobrecostes, que hemos calculado hasta ahora). Para completar esta segunda etapa del algoritmo agregamos al cuadro una nueva fila que marcamos con un \wp_{3} y que representa las nuevas reducciones posibles de las diferentes actividades. De la observación de la columna \wp_{3} se deduce que la duración del proyecto es ahora de 31 unidades de tiempo, existiendo dos caminos críticos, que son el \pi_{2} y el \pi_{3} . Para reducir la duración de dichos caminos a mínimo coste, aparentemente bastaría con disminuir el tiempo de ejecución de las actividades a y b, pues siendo todavía susceptibles de disminución, son las que poseen el coste unitario de reducción más bajo. Ahora bien, si actuáramos de esta forma llegaríamos a una solución equivocada. En efecto, observemos que la actividad f forma parte de los dos caminos críticos, por lo que una disminución de su tiempo de ejecución produce una disminución simultánea del tiempo de ejecución de dichos caminos. Como el coste unitario de disminución de la actividad f es inferior al de reducir simultáneamente las actividades a y b (ya que 5<2+4), la reducción a mínimo coste en esta iteración se efectuará disminuyendo el tiempo de ejecución de la actividad f, que es de 3. Por tanto, la duración del proyecto pasa a ser de 28 días, tal como indican las longitudes generalizadas de los diferentes caminos reflejadas en la columna marcada con un \wp_{4}. En esta iteración, el sobrecoste debido a la reducción es de 15 unidades monetarias. En la figura [fig:EvolucionSobrecoste] hemos representado el punto correspondiente de la relación sobrecoste–tiempo de ejecución. Para completar esta iteración agregamos al cuadro una nueva fila que marcamos con un \wp_{4} y que representa las nuevas reducciones posibles de las diferentes actividades. Repitiendo el mismo proceso completaríamos las demás etapas del algoritmo, tal como quedan reflejadas en el cuadro de la figura [tab:AckoffSassieni] y en la figura [fig:EvolucionSobrecoste]. Al determinar la columna y la fila marcadas con un \wp_{6} se ha llegado al final del algoritmo. En efecto, según nos indican los elementos de la fila \wp_{6} , ninguna actividad de las que forman parte de los caminos críticos \pi_{2} y \pi_{3} es susceptible de reducción. Una vez finalizada la fase algorítmica, el cuadro [tab:AckoffSassieni] y la figura [fig:EvolucionSobrecoste] contienen toda la información necesaria para efectuar la programación del proyecto a coste mínimo. Así, por ejemplo, si el responsable del proyecto desea finalizar el mismo en 28 unidades de tiempo (es decir, reducir el tiempo de ejecución del proyecto en 7 unidades de tiempo), la figura [fig:EvolucionSobrecoste] indica que el sobrecoste mínimo para conseguir ese tiempo de ejecución es de 20 unidades monetarias (ordenada correspondiente al punto de abscisa 28). Por otra parte, restando en el cuadro [tab:AckoffSassieni] , a los elementos de la fila marcada con un \wp_{0} los de la fila marcada con un \wp_{3} , obtenemos que los tiempos de ejecución de las diferentes actividades deberán coincidir con sus tiempos normales excepto: el de la actividad a, que deberá reducirse en una unidad de tiempo, y los de las actividades f y i que deberán reducirse en tres unidades de tiempo. Con los nuevos tiempos de ejecución se procederá al control del proyecto por medio de los métodos usuales: pert, etc. 1.5 La programación y los recursos 1.5.1 El problema de los recursos limitados En efecto, supongamos que en un proyecto de explotación de un determinado recurso, dos de las actividades, la c y la d, puedan ejecutarse simultáneamente con unos tiempos de cinco y siete días respectivamente. Imaginemos que para el cálculo de los tiempos anteriores no se han tomado en cuenta que se va a emplear un solo equipo disponible, por lo que que las actividades c y d no podrán ejecutarse simultáneamente[nota al pie: Supongamos que sólo disponemos de uno de estos equipos y que su capacidad se agota al ser empleado en una actividad. ], aunque así nos los indique el grafo de prelaciones. En este caso, el recurso equipo automático juega un papel condicionante en la programación, pues originará un retraso en la ejecución de al menos una de las actividades. El hecho de que la técnica pert se base en el supuesto de que los recursos se encuentran disponibles en cantidades ilimitadas supone una clara debilidad de este método, por lo que se hace necesario adaptarlo a este nuevo contexto. La necesidad de esta adaptación fue observada rápidamente por los estudiosos del tema. Así, en el año 1962 se publicaron los primeros trabajos en los que se pretende situar a los métodos modernos de programación y control de proyectos en un contexto de recursos limitados. Dentro del contexto general de los recursos limitados existen dos problemas claramente diferenciados: la nivelación y la asignación de recursos. Los métodos de nivelación de recursos, en líneas generales, pretenden: • Que la duración del proyecto no exceda de la prevista; es decir, la duración dada por el camino crítico. • Que los consumos de los diferentes tipos de recursos, durante el período de ejecución del proyecto sean lo más uniformes posible. La situación óptima, a la que en la mayor parte de los casos no podrá llegar, es aquella en la que el consumo de cada uno de los recursos coincida exactamente en cada uno de los períodos de tiempo en los que se ejecuta el proyecto. Por otra parte, los métodos de asignación de recursos pretenden minimizar la duración del proyecto, de forma que en ninguno de los períodos de tiempo en los que se ejecuta el proyecto, el consumo de algún recurso supere a las disponibilidades existentes del mismo. Nótese que esa corrección puede significar un incremento de la duración sobre la inicialmente identificada en el camino crítico, incluso éste puede cambiar como consecuencia de la reconsideración de las limitaciones impuestas por los recursos limitados. 1.5.2 La nivelación de recursos El problema de nivelar los recursos surge cuando el consumo que de ellos se hace a lo largo del proyecto no es uniforme. Si, por ejemplo, consideramos obreros, puede que al principio del proyecto se necesiten 30, luego 15, luego 5, luego 25 y por último 5. El no hacer un consumo uniforme de los recursos plantea problemas. En este caso la empresa objeto del estudio necesitará disponer de 30 obreros, de los cuales sólo estarán trabajando todos en el primer periodo de tiempo. Si la distribución de recursos se hubiera realizado de forma más uniforme, por ejemplo 15 obreros a lo largo de todo el proyecto, el reparto de trabajo estaría más optimizado: se reducirían los tiempos de espera como consecuencia de la disminución de recursos ociosos, y se obtendría un dimensionamiento óptimo del número de trabajadores necesario en el proyecto. La nivelación de recursos consiste en hacer una redistribución de las tareas sin que afecte a la duración total del proyecto. Ante la dificultad de aplicar métodos exactos en la resolución de los problemas de nivelación y de asignación de recursos han surgido una serie de algoritmos heurísticos que resuelven, aunque de una manera aproximada, los problemas anteriormente planteados. Estos algoritmos heurísticos no aseguran el hallazgo de un óptimo, pero sí de un subóptimo, reduciendo considerablemente el trabajo de cálculo. En la mayor parte de las aplicaciones reales, este subóptimo proporciona una aproximación suficiente. En este apartado vamos a presentar un algoritmo de nivelación de recursos, el de Burgess–Killebrew[3], que siendo uno de los algoritmos pioneros en este campo, está considerado también como uno de los más eficientes. Sin entrar en una discusión matemática del algoritmo, nos vamos a limitar a explicar su mecánica operativa, apoyándonos para ello en la nivelación del recurso mano de obra del proyecto de un proyecto ficticio cuyos datos básicos recogemos en la tabla [tab:Ejemplo_Nivelacion].[flotante Cuadro: Tarea Duración Precedente Recursos Holgura Total Holgura Libre ---------------------------------------------------------------------------------- A 3 - 10 0 0 B 2 - 5 1 0 C 4 A 5 0 0 D 2 C 5 0 0 E 7 B 5 1 1 F 1 D 5 0 0 G 8 - 5 2 2 H 2 E,F,G 5 0 0 I 2 - 10 10 10 ---------------------------------------------------------------------------------- [Cuadro 1.7: Datos del ejemplo de nivelación ] ][flotante Figura: [Figura 1.24: Diagrama PERT sobre vista de Gantt del proyecto del ejemplo. ] ] La realización de las actividades de este proyecto tiene asociada la carga de recursos que se muestra en la figura [fig:Gantt_0]. Como se puede ver la utilización de recursos no es todo lo uniforme que sería deseable. El nivel de utilización óptimo sería 15 recursos en cada periodo: La aplicación del algoritmo se efectúa en las fases que describimos seguidamente. Fase 1 Nos fijamos en el calendario de ejecución del proyecto, buscando la actividad no crítica que tenga la fecha temprana de finalización más avanzada. En esta actividad se retrasa su finalización unidad por unidad de tiempo, de acuerdo con lo que permite su holgura[nota al pie: Aunque el algoritmo lo apliquemos utilizando la holgura total de una actividad, también es posible utilizar su holgura libre: un retraso equivalente a la holgura total de una actividad no afecta a la duración del proyecto, pero sí a la holgura total de las actividades siguientes; mientras que, un retraso equivalente a la holgura libre no afecta ni a la duración del proyecto ni a la holgura total disponible de las actividades siguientes. ]. Se elegirá como fecha más temprana de finalización de la actividad la que haga mínima la suma de los cuadrados de las cargas. Así, en nuestro ejemplo, comenzaremos por analizar la actividad e, pues es la que posee la fecha temprana de finalización más avanzada. Como la holgura total de esta actividad es de 1 semana, retrasaremos su finalización en una semana, comprobando la repercusión que tiene esta acción en la suma de los cuadrados de las cargas. Como dicha suma se reduce, conviene retrasar la ejecución de la actividad e en una semana. La nivelación parcial que hemos conseguido con esta primera iteración queda reflejada en el diagrama de cargas. Después de aplicar el algoritmo el diagrama de Gantt resultante se muestra en la figura [fig:Gantt_1] .[flotante Figura: [Figura 1.25: Diagrama PERT tras haber desplazado la actividad e un periodo. ] ] Fase 2 Entre todas las actividades no críticas, excluida la actividad que hayamos estudiado en la primera fase, se vuelve a elegir la que tenga la fecha temprana de finalización más avanzada. Una vez encontrada esta actividad, se le aplica el mismo tratamiento que el descrito en la primera fase. En este caso retrasamos la tarea g primero un periodo y después otro (figura [fig:Gantt_2] y [fig:Gantt_3] ).[flotante Figura: [Figura 1.26: Diagrama PERT tras haber desplazado la tarea g un periodo. ] ][flotante Figura: [Figura 1.27: Diagrama PERT tras haber desplazado la tarea g dos periodos. ] ] El movimiento que más nos interesa es retrasar la duración de la tarea en 2 unidades de tiempo, con lo que se obtiene una suma del cuadrado de las cargas de 3100. Seguidamente continuaremos el proceso hasta llegar a la actividad que posea una fecha temprana de finalización más retrasada, aplicándole el mismo tratamiento. Cuando dos o más actividades tengan la misma fecha temprana de finalización, se actuará prioritariamente sobre la actividad cuya holgura permita un retraso mayor en su finalización. Así en nuestro ejemplo, una vez analizada la actividad G, pasaríamos a estudiar la actividad I, pues de entre las actividades no críticas restantes es la que posee la fecha temprana de finalización más avanzada. Como la holgura total disponible de esta actividad es de diez semanas, retrasamos su finalización primero en una semana y después en otra y otra, etc, comprobando la repercusión que tiene esta acción en la suma de los cuadrados de las cargas Obviamente, conviene retrasar la ejecución de la actividad I en diez periodos, pues de esta forma la suma de los cuadrados de las cargas desciende a 2700 unidades (figura [fig:Gantt_4]).[flotante Figura: [Figura 1.28: Diagrama PERT tras haber desplazado la tarea I diez periodos. ] ] Fase 3 Una vez analizada la actividad con una fecha temprana de finalización más retrasada, se vuelve a iniciar un nuevo ciclo de iteraciones. El proceso de cálculo se detendrá cuando, finalizado un ciclo, no resulte posible disminuir la suma de los cuadrados de las cargas. En nuestro ejemplo ha bastado efectuar un primer ciclo de iteraciones para llegar al alisado óptimo. Aunque el algoritmo lo hemos aplicado a un calendario de ejecución del proyecto basado en las fechas tempranas, puede aplicarse de igual forma a un calendario que esté basado en las fechas tardías. En ambos casos, como es lógico, se llega a la misma solución, aunque el número de ciclos e iteraciones puede cambiar. Es conveniente tener en cuenta que nunca sabremos si hemos llegado a una solución óptima, excepto en aquellos casos en los que se alcanza un alisado óptimo. Una de las ventajas que presenta este algoritmo es el de ser factible de procesar en ordenador, lo cual permite su aplicación a proyectos complejos. Uno de sus principales inconvenientes es el de estar pensado fundamentalmente para la nivelación de un único[nota al pie: Para el caso de nivelación simultánea de varios recursos resulta bastante útil el algoritmo Multi–Ship Multi–Shop. ] recurso. Otros procedimientos heurísticos han sido propuestos por Galbreath[5], Wiest y Levy[16], Moder et al.[9], Ciobanu[4], Newmann y Morlock[10], si bien todos ellos referidos a casos simplificados o bien apoyándose en técnicas de reglas de priorización. Otras técnicas heurísticas para problemas modificados de nivelación con duraciones de actividades dependientes del uso de recursos, o uso de recursos dependiente del tiempo, se han propuesto por Leachman[7], Seibert y Evans[14], Takamoto et al.[15] , etc., si bien ninguno de estos estudios desarrollan casos experimentales con más de 20 tareas. Recientemente se han propuesto técnicas heurísticas para nivelar recursos con desplazamientos máximos entre tareas además de valores mínimos en esos desplazamientos[2]. Esto se puede emplear para modelar una gran variedad de situaciones como fechas de finalización de proyectos o de actividades individuales, solapamiento total o parcial de actividades, problemas con recursos dependientes del tiempo, así como problemas de lanzamiento de órdenes de fabricación. 1.5.3 La asignación de recursos La asignación de recursos es un problema parecido al de nivelación pero con algunas particularidades. El problema surge cuando, según la planificación del proyecto, en alguna etapa del proyecto el nivel de utilización de recursos teóricos supera a los disponibles realmente. Entonces hay que ajustar la planificación de las tareas de forma que en cada periodo de tiempo no se utilicen más recursos que los existentes, retrasando la realización de ciertas tareas. Puede ocurrir incluso que el retraso de estas tareas origine una mayor duración del proyecto. A partir de los datos de entrada (relación de tareas, dependencias entre ellas, duración y recursos que utilizan) se construirá un cuadro similar al [tab:plantilla_asignacion].[flotante Cuadro: +-----------------------------------------------------------------------------------------------------------------------------------------------+----+----+----+----+----+----+----+----+ | Periodos | 1 | 2 | 3 | 4 | 5 | 6 | 7 | … | +-----------------------------------------------------------------------------------------------------------------------------------------------+----+----+----+----+----+----+----+----+ | Recursos disponibles | | | | | | | | | +-----------------------------------------------------------------------------------------------------------------------------------------------+----+----+----+----+----+----+----+----+ | Candidatos • Con indicación de su holgura | | | | | | | | | +-----------------------------------------------------------------------------------------------------------------------------------------------+----+----+----+----+----+----+----+----+ | Lista clasificada • Con indicación de los recursos • Respetando dependencias • Prioridad: – Menor holgura – Menor duración | | | | | | | | | +-----------------------------------------------------------------------------------------------------------------------------------------------+----+----+----+----+----+----+----+----+ | Tareas programadas | | | | | | | | | +-----------------------------------------------------------------------------------------------------------------------------------------------+----+----+----+----+----+----+----+----+ | Recursos consumidos | | | | | | | | | +-----------------------------------------------------------------------------------------------------------------------------------------------+----+----+----+----+----+----+----+----+ [Cuadro 1.8: Plantilla para desarrollar el algoritmo de asignación de recursos ] ] En la primera fila se representan los diferentes periodos de tiempo dentro del proyecto. Inmediatamente debajo se anota la cantidad de recursos disponibles en cada periodo. Lo normal es que el número de recursos disponible sea uniforme a lo largo de todo el proyecto. Debajo se anotará la lista de todas las tareas que son candidatas a ejecutarse en ese periodo de tiempo, escribiendo entre paréntesis al lado de cada tarea su holgura. Estos candidatos serán ordenados por prioridad para seleccionar qué tareas serán ejecutadas en ese periodo de tiempo. Esta ordenación se realizará en primer lugar respetando las dependencias marcadas para las tareas. Siempre que se respeten las dependencias originales las tareas con mayor prioridad para ejecutarse en el periodo actual serán aquellas con una menor holgura, y en caso de igualdad las que tengan menor duración. Al lado de cada tarea se anotarán los recursos que consumirá su ejecución en ese periodo de tiempo. Atendiendo a la ordenación anterior se seleccionarán las tareas a ejecutar en el periodo de tiempo. Para programar las tareas se irá cogiendo por orden de prioridad mientras la suma de recursos que consumen sea menor o igual a los recursos de que se dispone en ese periodo. Se supone que las tareas son indivisibles[nota al pie: La razón fundamental surge de que son los recursos los que construyen los entregables y su agrupación temporal forma las tareas. Si una actividad puede ser dividida es porque el trabajo de sus recursos asociados es segmentable y nada impediría entonces considerar cada segmento como una tarea independiente con vinculación fin–comienzo respecto de la anterior, lo que reduce el problema al caso aquí estudiado. ], por lo que una vez que se programa el comienzo de una tarea, si esta no finaliza en este periodo de tiempo, automáticamente es programada también en lo periodos siguientes hasta que termina. Las tareas que no puedan ser programadas pasan automáticamente a ser candidatas en el próximo periodo de tiempo, decrementando su holgura. Este proceso se repetirá hasta que sean programadas todas las tareas. Veamos la aplicación del algoritmo con el ejemplo cuyos datos recoge la tabla [tab:DatosAsignacion].[flotante Cuadro: Tarea Dependencias Duración Recursos Holgura Total Holgura Libre ------------------------------------------------------------------------------------ A - 1 2 0 0 B A 1 2 5 1 C A 2 3 0 0 D B,C 1 2 4 1 E C 2 2 3 0 F C 3 2 0 0 G D,E 1 2 3 3 H F 3 2 0 0 I G,H 1 3 0 0 ------------------------------------------------------------------------------------ [Cuadro 1.9: Datos del ejemplo correspondiente al algoritmo de asignación. ] ] Supongamos que el recurso que queremos asignar es el de mano de obra, y que en cada periodo no podemos disponer de más de 4 personas. Si analizamos cual es el consumo actual de recursos que se está realizando obtenemos el perfil que aparece recogido en la tabla [tab:EvolucionRecursos0].[flotante Cuadro: +-----------+----+-------+----+-----------+-------+-------+----+----+----+-----+ | Periodo | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | +-----------+----+-------+----+-----------+-------+-------+----+----+----+-----+ | Programa | A | B C | C | D E F | E F | F G | H | H | H | I | +-----------+----+-------+----+-----------+-------+-------+----+----+----+-----+ | Recursos | 2 | 5 | 3 | 6 | 4 | 4 | 2 | 2 | 2 | 3 | +-----------+----+-------+----+-----------+-------+-------+----+----+----+-----+ [Cuadro 1.10: Evolución original de la utilización de los recursos del proyecto del ejemplo. ] ] Se puede observar que en los periodos 2 y 4 se está superando el número de recursos existentes, por lo que debemos aplicar el algoritmo para asignación de recursos (tabla [tab:ResultadoAsignacion] ).[flotante Cuadro: +------------------------+-------+------------+-------------------+-----------------------------+-------------------------+-----------------------------------+-----------------------+-------------------+-------+-------+ | Periodos | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | +------------------------+-------+------------+-------------------+-----------------------------+-------------------------+-----------------------------------+-----------------------+-------------------+-------+-------+ | Recursos Disponibles | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | +------------------------+-------+------------+-------------------+-----------------------------+-------------------------+-----------------------------------+-----------------------+-------------------+-------+-------+ | Candidatos | A(0) | B(5) C(0) | C(0) – – B(4) | B(3) E(3) F(0) — D(4) | F(0) – – E(2) D(3) | F(0) E(2) – – D(2) — G(3) | D(1) H(0) — G(2) | H(0) – – G(1) | H(0) | I(0) | +------------------------+-------+------------+-------------------+-----------------------------+-------------------------+-----------------------------------+-----------------------+-------------------+-------+-------+ | Lista clasificada | A(2) | C(3) B(2) | C(3) – – B(2) | F(2) B(2) E(2) | F(2) – – E(2) D(2) | F(2) E(2) – – D(2) | H(2) D(2) | H(2) – – G(2) | H(2) | I(3) | +------------------------+-------+------------+-------------------+-----------------------------+-------------------------+-----------------------------------+-----------------------+-------------------+-------+-------+ | Programa | A | C | C | F B | F E | F E | H D | H G | H | I | +------------------------+-------+------------+-------------------+-----------------------------+-------------------------+-----------------------------------+-----------------------+-------------------+-------+-------+ | Recursos Utilizados | 2 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 2 | 3 | +------------------------+-------+------------+-------------------+-----------------------------+-------------------------+-----------------------------------+-----------------------+-------------------+-------+-------+ [Cuadro 1.11: Desarrollo del algoritmo de asignación sobre los datos del ejemplo. ] ] En este caso la solución obtenida no ve retrasada la duración del proyecto, que sigue siendo de 10 unidades de tiempo, pero podría haber ocurrido que el proyecto sufriera un retraso motivado por la insuficiencia de recursos. 1.6 Conclusiones 1.6.1 Puntos tratados Se describen en primer lugar los diagramas de Gantt. Tras una somera introducción en la que se comentan los antecedentes históricos de esta técnica de expresión del cronograma, se presentan sus principios básicos. Se describen los elementos de que consta un diagrama Gantt y se proporciona una primera introducción a los diferentes tipos de enlaces que pueden presentarse entre tareas. A continuación se relatan las ventajas e inconvenientes que conlleva la utilización de estos diagramas en distintos contextos. Seguidamente, se describen los diagramas pert. Siguiendo el mismo esquema, se proporciona una somera introducción en la que se comentan los orígenes de esta técnica; tras lo cual, se presentan sus principios básicos. Se detallan los elementos constitutivos de los grafos pert y el distinto significado de los conceptos que conlleva su uso. Se indica la manera de resolver solapamientos y desplazamientos de actividades en los grafos. Se explica el significado de los tiempos tempranos, tardíos y de las distintas holguras, proporcionando, en base a un ejemplo, detalles acerca del procedimiento a seguir para su cálculo. Adicionalmente al método tradicional de cálculo sobre el propio grafo se presenta el algoritmo de Zaderenko para el cálculo de los tiempos tempranos y tardíos mediante operaciones, no ya sobre el propio grafo, sino sobre una matriz. Conociendo estos concepto nada impide avanzar un paso más y comprender el significado, importancia y método de cálculo del calendario de ejecución del proyecto. Se explica en este apartado el significado de las fechas de comienzo y finalización tempranas y tardías, así como también se pone de relevancia la ventajosa perspectiva que el diagrama de Gantt proporciona sobre este calendario. Después se progresa para estudiar el efecto que sobre el coste tiene la reducción del plazo y viceversa, como la reducción de plazos conlleva un cambio en el coste estimado del proyecto. A pesar del posible complejo comportamiento, se acepta en este primer contacto con el problema su linealización. Tal aproximación permitirá comprender el concepto de coste unitario de reducción y reflexionar acerca de las razones que pueden hacer que éste tenga uno u otro signo. Conocido el coste unitario de reducción, éste da paso a plantear las reglas que deben regir la metodología que debe seguirse a fin de reducir la duración estimada del proyecto con el mínimo perjuicio posible sobre el coste estimado del mismo. Seguidamente se describe el algoritmo de Ackoff y Sasieni para la reducción de la duración del proyecto con mínimo coste, utilizando para ello un sencillo ejemplo. A partir de los datos básicos de un proyecto simple se construye el grafo pert correspondiente a las prelaciones establecidas, primero haciendo el cálculo de la estimación de la duración del proyecto tal y como se configuró inicialmente para, posteriormente, realizar el mismo cálculo ahora con las duraciones tope de todas sus actividades. Tras comprobar la posibilidad de reducir los plazos necesarios para ejecutar el proyecto, se determinan todos los posibles caminos desde el nodo Inicio hasta el nodo Fin del proyecto realizando una búsqueda en anchura. Seguidamente, se calculan los costes unitarios de reducción de cada una de las actividades, el número de periodos que admiten ser reducidas y la duración de cada uno de los caminos del grafo pert. Se procede en la iteración identificando el conjunto de caminos de mayor duración y modificando la duración de aquel conjunto de tareas que proporcione un recorte de la duración eficaz y eficiente. Esta iteración va acompañada del trazado de la evolución de la curva de sobrecostes que, a modo ilustrativo, facilita la interpretación y da sentido al método. A continuación se presenta el problema que presenta la realización de proyectos en el contexto de recursos limitados y como, a pesar de que las técnicas hasta ahora vistas no habían entrado a tratar la influencia de estos aspectos en sus desarrollos, sí parece conveniente reparar ahora esa falta y complementar lo visto con la introducción de estas consideraciones. Se comienza pues planteando el escenario de los recursos limitados. A partir de un proyecto sencillo a modo de ejemplo se determina el perfil de utilización de recursos asociado a la configuración inicial del cronograma. Mediante el algoritmo de Burgess–Killebrew se desplazan las tareas convenientemente a lo largo del cronograma y se constata numérica y gráficamente la bondad de las alternativas que se van presentando en la aplicación del algoritmo.En la presente lección se han presentado las técnicas más comúnmente utilizadas en la expresión del cronograma del proyecto: los diagramas de Gantt y el grafo pert. 1.6.2 Preguntas abiertas 1. Ante el cronograma de la figura [fig:EjemploProgresoGantt], ¿cómo valoraría la labor del director del proyecto? 2. ¿En qué consiste el camino crítico y las actividades críticas? 3. Identifica en el gráfico pert de la figura [fig:GraficoCC] qué ocurriría si la actividad g se retrasa 3 unidades de tiempo por causas no previstas cuando se desarrolló el pert. 4. Explica la diferencia entre holgura libre y total de una actividad. 5. ¿Cómo representaría los solapamientos y desplazamientos en un diagrama pert? 6. ¿Qué ocurre si no consideramos los recursos como limitados en un proyecto? 7. ¿Cuáles son los dos problemas a abordar en el contexto general de recursos limitados? 8. Configure y resuelva una situación en la que un director de proyectos se encuentre simultáneamente con la necesidad de aplicar los tres algoritmos vistos en esta lección. 1.6.3 Lecturas recomendadas La lectura comprensiva de las referencias [1, 8] permitirá al alumno profundizar en los aspectos correspondientes al método pert. La referencia [12] proporcionará una perspectiva más amplia acerca de los conceptos vistos en esta lección. Aquellos alumnos interesados en conocer métodos más sofisticados, como por ejemplo el método gert, encontrarán en la referencia [11] un interesante enfoque de las nuevas tendencias en programación de proyectos, lo que, sin duda, redundará en una mejor preparación del alumno frente a los problemas que pudieran surgirle respecto a la dirección de plazos. El alumno interesado encontrará en artículos como el indicado en la referencia [#Azaron:2006a, #golenko:1998a] una visión moderna de cuales son las tendencias en la implementación de algoritmos de planificación temporal bajo restricciones. Para completar lo aquí recogido, puede encontrar especialmente útiles las referencias [11] y [13]. En la primera encontrará la descripción de una interesante colección de técnicas de programación. En la segunda, un enfoque sistemático de como se integran los conceptos de plazos, costes y recursos de acuerdo a la metodología propuesta por pmi. Los interesados en la algoritmia de las técnicas de control sobre diagramas de redes pueden acudir a la referencia [6]. Referencias Bibliografía [1] BENDICHO-JOVEN, Jose. P., Manual de Planificación y Programación Para Obras Públicas y Construcción:Camino Crítico (PERT/CPM) (Editorial Rueda, 1999). [2] BRINKMANN, K. and NEWMANN, K., "Heuristic procedures for resource constrained project", Journal of Decision Systems 5 (1996), pp. 129-155. [3] BURGESS, A.R and KILLEBREW, J.B., "Variation in activity level on a cyclical arrow", Journal of Industrial Engineering 13 (1962), pp. 76-83. [4] CIOBANU, G., "A multiproject programming model with resource levelling", Economic Computation and Economic Cybernetics Studies and Research 3 (1972), pp. 61-68. [5] GALBREATH, R.V, "Computer program for levelling resource usage", Journal of the Construction Division 91 (1965), pp. 107-124. [6] HAGA, WAYNE and MAROLD, KATHRYN, "Monitoring and control of PERT networks", The business review, Cambridge 3, 2 (2005), pp. 240. [7] LEACHMAN, R.C., "Multiple resource levelling in construction systems through variation ofactivity intensities", Naval Research Logistics Quarterly 39 (187-198), pp. 1983. [8] MATEOS-PERERA, JESÚS, La Programación en la Construcción (2ª Edición). El PERT en versión completa. (Editorial Bellisco, 2003). [9] MODER, J.J., PHILIPS, C.R., and DAVIS, E.W, Project management with CPM, PERT and precedence diagramming (Van Nostrand Reinhold, 1968). [10] NEWMANN, K. and MORLOCK, M., Operations Research (Hanser, München, 1993). [11] ORDIERES MERÉ, JOAQUÍN B., Programación de Proyectos (Servicio de Publicaciones de la Universidad de La Rioja, 1999). [12] ROMERO LÓPEZ, CARLOS, Técnicas de Programación y Control de Proyectos (Editorial Pirámide, 2002). [13] SCHWALBE, KATHY, Introduction to project management (Thomson course technology, 2006). [14] SEIBERT, J.E. and EVANS, G.W., "Time constrained resource levelling", Journal of Construction Engineering and Management 117 (1991), pp. 503-520. [15] TAKAMOTO, M., YAMADA, N., KOBAYASHI, Y., and NONAKA, H., "Zero-one quadratic programming algorithm for resource levelling in multi-projectmulti-resource scheduling", Decision Sciences 6 (1995), pp. 525-540. [16] WIEST, J.D. and LEVY, F.K, A management guide to PERT/CPM (Prentice-Hall. Englewood Cliffs, NJ, 1969).