• Author / Uploaded
• Byron

Citation preview

UNIVERSIDAD DISTRITAL FRANCISCO JOSÉ DE CALDAS

FACULTAD DE INGENIERÍA INGENIERÍA INDUSTRIAL

TEORÍA DE GRAFOS

PROFESOR CESAR AMILKAR LÓPEZ

Distribución de recursos

PRESENTADO POR BYRON OMAR PARDO RUIZ

BOGOTÁ, COLOMBIA JUNIO 2019

20161015023

OBJETIVOS 

Reconocer la importancia del algoritmo de Brooks, Gray Kidd y RCPSP.



Utilizar los algoritmos de Brooks, Gray Kidd y RCPSP para encontrar una solución factible a un problema de asignación de recursos



Realizar los diagramas AOA y AON para para encontrar la ruta crítica de un proyecto a través de los métodos de Roy y Cpm.

INTRODUCCIÓN Cada vez es más frecuente que las organizaciones, independientemente de su naturaleza, pretendan logar sus objetivos mediante la realización de actividades a través de proyectos y no con esfuerzos aislados y dispersos. Por tanto, la administración de proyectos constituye una herramienta muy poderosa en los negocios ya que permite focalizar las acciones y estrategias de las organizaciones contribuyendo a la maximización de sus beneficios optimizando sus recursos. La planeación de tiempos y asignación de recursos es fundamental en la administración de un proyecto ya que permite incrementar las posibilidades de éxito durante la ejecución del mismo. Los algoritmos de Gray Kidd, Brooks y RCPSP son métodos iterativos útiles para planear un proyecto dados unos recursos limitados. El presente informe busca encontrar una solución factible a un problema de asignación de recursos en un proyecto. MARCO TEÓRICO Proyecto: Un proyecto en Administración de Negocios y en la Ciencia, se define generalmente como un emprendimiento colaborativo. Con frecuencia involucra la investigación o el diseño, que han sido cuidadosamente planificados, para lograr un objetivo particular. Los proyectos se pueden definir como algo temporal y no permanente. Los sistemas sociales están constituidos por equipos dentro o a través de las organizaciones, para llevar a cabo determinadas tareas, en virtud de las restricciones de tiempo. Conjunto de tareas planeadas e interrelacionadas, que se ejecutan en un período fijo y dentro de ciertos costos y otras limitaciones. Diagrama de Gantt Es una popular herramienta gráfica cuyo objetivo es mostrar el tiempo de dedicación prevista para diferentes tareas o actividades a lo largo de un

tiempo total determinado. A pesar de esto, el diagrama de Gantt no indica las relaciones existentes entre actividades. En un diagrama de Gantt, cada tarea es representada por una línea, mientras que las columnas representan los días, semanas, o meses del programa, dependiendo de la duración del proyecto. El tiempo estimado para cada tarea se muestra a través de una barra horizontal cuyo extremo izquierdo determina la fecha de inicio prevista y el extremo derecho determina la fecha de finalización estimada. Las tareas se pueden colocar en cadenas secuenciales o se pueden realizar simultáneamente. Un diagrama de Gantt es la representación gráfica del tiempo que dedicamos a cada una de las tareas en un proyecto concreto, siendo especialmente útil para mostrar la relación que existe entre el tiempo dedicado a una tarea y la carga de trabajo que supone. Una de sus limitaciones es que no muestra la relación de dependencia que pueda existir entre grupos de tareas. Los diagramas de Gantt fueron ideados por Henry L. Gantt en 1917 (un año antes de la creación del método de aprendizaje por proyectos) con la intención de ofrecer un método óptimo para visualizar la situación de un proyecto. El algoritmo de Brooks es un sistema iterativo en el que se programan actividades y su planeación especifica dependiendo de la limitación en la cantidad de recursos disponibles para cada una de las actividades que conforman el proyecto de estudio. Para decidir cada una de las secuencias que se trabajaran a lo largo de las iteraciones se hará uso de herramientas de tiempo llamadas “tiempos de control” que para el caso específico del algoritmo ACTIM. Paso a paso (Brooks): 

   

Establecer las rutas posibles de distribución en la red estableciendo la duración máxima en tiempo década una de ellas y además estableciendo sub rutas hasta llegar a las últimas actividades del proyecto. Ordenar las actividades por orden de ACTIM (Desde la mayor duración a la menor) Indicar la limitación de recursos que tiene el proyecto. Establecer para cada una de las actividades el uso de recursos Rn disponibles o necesarios para su ejecución. Verificar la disponibilidad de recursos disponibles en cada iteración, si el recurso es insuficiente, la actividad precedente continúa liberando recursos.

Notaciones usadas:

    

TEARL: Es el tiempo más rápido en el que se realizará la actividad y es igual a el TFIN solo para las actividades que son predecesoras. TSTART: Es el tiempo de iniciación normal cuando no existe limitación de recursos TFIN: Tiempo de terminación de cada actividad TNOW: Es el tiempo en el que se considera la asignación de recursos ACTALLOW: No es una notación obligatoria, pero en términos de planeación, indica que actividades han liberado o no recursos. Es una herramienta más de uso cualitativo que cuantitativo

Algoritmo de Gray-Kidd Gray Kidd es un algoritmo usado para asignar y distribuir óptimamente los recursos limitados en el tiempo, basado en prioridades. Los criterios de distribución que establece son que se le da mayor prioridad a las actividades que: 1.) Tengan la iniciación más temprana 2.) Tengan la menor holgura total 3.) Pidan la mayor cantidad de recursos La integración de las herramientas se obtiene inicialmente representado la red de actividades del proyecto PDM (precedence diagram method)por medio de un modelo dinámico, con limitantes de recurso renovable, al cual posteriormente se unen las reglas de prioridad de Gray Kidd. RCPSP (resource constrained project scheduling problem.) Diferentes metodologías han sido propuestas para encontrar soluciones para el RCPSP. Dichos métodos pueden ser clasificados en dos categorías principales: métodos exactos y los métodos heurísticos o meta heurísticos. Uno de los algoritmos ampliamente usado para el RCPSP es el denominado Justificación. La Justificación es una técnica sencilla y rápida que al aplicar sobre una solución del RCPSP produce otra de igual o menor duración (Valls et al., 2003a). El problema de programación de proyectos con recursos limitados (RCPSP) puede ser descrito matemáticamente de la siguiente manera: Se tiene un conjunto J = {1, . . ., n} de n actividades a ser procesadas. Asociada a cada actividad j ∈ J, existe una duración dj. Además, las actividades están relacionadas mediante restricciones de precedencia, siendo Pj ∈ J \ {j} el conjunto de todas las actividades predecesoras inmediatas de la actividad j, es decir, actividades que deben ser

completadas antes de iniciar la ejecución de la actividad j. Las restricciones de precedencia pueden estar representadas por un grafo dirigido cíclico G = (J, H) donde H = {(i, j) |i ∈ Pj , j ∈ J}. Adicionalmente, existe un conjunto K = {1, . . ., m} de m tipos de recursos renovables, donde cada tipo de recurso k ∈ K tiene una disponibilidad (capacidad) total Rk durante cada intervalo de tiempo del periodo de programación, es decir, la suma de la cantidad utilizada del tipo de recurso k en el periodo t, Rk(t), no debe exceder Rk para todo t. Cada actividad j requiere una cantidad constante de rjk unidades del recurso de tipo k durante todo el intervalo de su duración. Se asume, sin pérdida de generalidad, que rjk ≤ Rk, lo cual garantiza la existencia de soluciones factibles. Todas las cantidades dj, rjk y Rk son números enteros no negativos para todo j ∈ J y todo k ∈ K. DESARROLLO La tabla 1 muestra las actividades, tiempos y recursos que conforman un determinado proyecto.

Tabla 1. Ejercicio propuesto

Diagramas AON, AOA y Gantt El primer paso es realizar los diagramas AON y AOA para encontrar el tiempo de inicio y de finalización de cada actividad, los tiempos de holgura y el tiempo total de la realización del proyecto. Cabe destacar que este diagrama no tiene en cuenta los recursos, es decir, funciona bajo la premisa de que se tienen recursos ilimitados.

Figura 1. Diagrama AOA

Figura 2. Diagrama AON

Con la información de los diagramas AON y AOA se construye la tabla 2, que enseña el tiempo de inicio de cada actividad y el tiempo de finalización.

Tabla 2. Tiempo de inicio y finalización de cada actividad

Donde la duración del proyecto es el tiempo máximo del tiempo de finalización de las actividades, es decir, 135 unidades de tiempo que

corresponden a la actividad V. A continuación, se presenta el diagrama de Gantt, donde la línea horizontal verde representa la cantidad o disponibilidad de recurso que se tiene (para este caso 18). Las zonas rojas corresponden a las actividades que no se pueden realizar con la cantidad de recurso disponible.

Figura 3. Diagrama de Gantt fase 1

Algoritmo Gray-Kidd Se analiza el intervalo de tiempo (0,20), que es el intervalo que dura la actividad C. Donde TRT es el tiempo de reserva, rij es el recurso necesario para llevar a cabo la actividad y OP es el orden de prioridad

Tabla 2. Fase 1

La actividad C deberá ser desplazada 23 unidades de tiempo, pues en ese momento los recursos de B serán liberados. Obteniendo la siguiente situación:

Figura 4. Diagrama de Gantt fase 2

Cabe destacar que las actividades que dependen de C se corren, tales como I,H y G, alargando así el tiempo del proyecto a 150 unidades de tiempo. Se analiza el intervalo de tiempo (24,28), que es donde se acaba la actividad D.

Tabla 3. Fase 2

La actividad F deberá posponerse hasta el instante 28 debido a que en este momento los recursos de la actividad D serán liberados. Obteniendo la siguiente situación:

Figura 5. Diagrama de Gantt fase 3

Dado que el tiempo de reserva de la actividad F es mayor al tiempo que se desplazó las actividades que dependen de F no se ven afectadas y por ende el tiempo de ejecución del proyecto sigue siendo 150 unidades de tiempo. Se analiza el intervalo de tiempo (43,44) pues en este intervalo se presentan problemas por falta de recursos.

Tabla 4. Fase 3

Debido a que las actividades E, F, G, H e I requieren de una cantidad de recursos mayor que las actividades ya analizadas, se deben posponer tanto la actividad H como la actividad I una unidad de tiempo, pues en ese instante las actividades E y F liberan recursos. Obteniendo la siguiente situación:

Figura 6. Diagrama de Gantt fase 4

Los tiempos de reserva de H e I son 5 y 3 respectivamente. Como estos tiempos de reservas son mayores a 1 (cantidad de tiempo que se desplazaron las actividades), las actividades que dependen de H e I no se van a desplazar y por lo tanto el tiempo total del proyecto no se verá afectado, es decir, sigue siendo 150 unidades de tiempo. Se analiza el intervalo de tiempo 45 a 64.

Tabla 5. Fase 4

La actividad N deberá posponerse hasta el instante de tiempo 65, cuando I libera recursos.Obteniendo la siguiente situación:

Figura 7. Diagrama de Gantt fase 5

Aunque el tiempo de reserva es menor a la cantidad de tiempo que se desplazó N las actividades que depende de N tenían suficiente tiempo de reserva para que el proyecto no se extendiera, es decir, el proyecto sigue durando 150 unidades de tiempo. Se analiza el intervalo de tiempo (94,111), donde se realizan las actividades O, P, Q, R, S.

Tabla 6. Fase 5

Para este caso, se deben aplazar las actividades O, P, y Q hasta el instante de tiempo 112, cuando la actividad S termina y libera recurso. Obteniendo la siguiente situación:

Figura 8. Diagrama de Gantt fase 6

El tiempo de reserva de las actividades O, P y Q es menor a la cantidad de tiempo que se vieron obligadas a ser desplazadas, por lo que las actividades dependientes, T, U, V, W, se desplazaron también, alargando el proyecto a 169 unidades de tiempo. Se analiza el intervalo de tiempo (112,116) donde intervienen las actividades O, P, Q, R.

Tabla 7. Fase 6

Las actividades O y P deberán desplazarse hasta el instante de tiempo 117 cuando la actividad R finaliza y libera recursos. Obteniendo la

siguiente situación:

Figura 9. Diagrama de Gantt fase 7

El desplazamiento de las actividades O y P tiene como consecuencia la postergación de las actividades T y U, extendiendo la duración del proyecto a 170 unidades de tiempo. Se analiza el intervalo (117,170), donde intervienen las actividades O, P y Q.

Tabla 8. Fase 7

La actividad O deberá desplazarse hasta el instante de tiempo 142, cuando la actividad Q libere recursos. Obteniendo lo siguiente:

Figura 10. Diagrama de Gantt fase 8

El desplazamiento de la actividad O tiene como consecuencia la postergación de las actividades T y U, extendiendo la duración del proyecto a 192 unidades de tiempo. Se analiza el intervalo de tiempo (142,143).

Tabla 9. Fase 8

La actividad V deberá desplazarse hasta el instante de tiempo 144, cuando la actividad P libere recursos. Obteniendo lo siguiente:

Figura 11. Diagrama de Gantt fase 9

La actividad V tiene tiempo de reserva suficiente, por lo que el proyecto no se verá afectado y seguirá en 192 unidades de tiempo. Como en ningún instante de tiempo se utilizan más de 18 unidades de recurso, el algoritmo Gray Kidd finaliza.

CONCLUSIONES/APLICACIONES 



Entre las aplicaciones más comunes del RCPSP se encuentran proyectos civiles de construcción, industriales, investigación, desarrollo de software, operaciones de mantenimiento, entre otras. el RCPSP es una generalización de otros problemas de programación de producción como Flow Shop, Job Shop y Open Shop

REFERNCIAS Material de apoyo otorgado por Cesar Amilcar López Perossa, M (2015). EL P.E.R.T. COST. UNA HERRAMIENTA PARA MAXIMIZAR TIEMPO Y REDUCIR COSTOS. Recuperado el 12 de Junio de 2019 de https://www.researchgate.net/publication/282723300_EL_PERT_COST_ UNA_HERRAMIENTA_PARA_MAXIMIZAR_TIEMPO_Y_REDUCIR_CO

STOS Sanchez, E (2007). Método de estimación paramétrica de costos en construcción de viviendas de interés social. Recuperado el 12 de Junio de 2019 de http://www.redalyc.org/articulo.oa?id=46712106 Martinez, M (2003). Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 CPM y PERT. Recuperado el 12 de Junio de 2019 de https://www.inf.utfsm.cl/~esaez/fio/s2_2003/apuntes/pert-2003-2.pdf