métodos del camino crítico - fing.edu.uy · 1 métodos del camino crítico introducción a la...
TRANSCRIPT
![Page 1: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/1.jpg)
1
Métodos del Camino Crítico
Introducción a la Investigación de Operaciones– año 2007
I.O.-InCo-Facultad de Ingeniería-UDELAR
![Page 2: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/2.jpg)
2
Contenido y Bibliografía•Introducción al problema del ordenamiento.
•Métodos del Camino Crítico.
•Función económica- Optimización.
•Hillier & Lieberman : Introducción a la Investigación de Operaciones, Mc Graw Hill, 1997.•Kaufmann & Desbazeille: Métdodo del Camino Crítico, Sagitario S.A. Barcelona, 1971.
![Page 3: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/3.jpg)
3
IntroducciónOrdenar es programar la ejecución de la realización de un trabajo.
•Se establecen tareas•Se asignan recursos•Se fijan fechasde ejecución para las tareas que componen el trabajo o proyecto.
Los problemas de ordenamiento son inherentes a toda organización.
![Page 4: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/4.jpg)
4
EjemploOrganización: hogar.
Proyecto:preparar cena
Problema deordenamiento.
Se listan:
•tareas,
•tiempos y
•restricciones de precedencia.
![Page 5: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/5.jpg)
5
Tarea nro.
Tarea Tiempo precedentes
1 Comprar queso muzarella 30 2 Rayar el queso 5 1 3 Batir 2 huevos 2 4 Mezclar huevos y queso ricotta 3 3 5 Picar cebollas y hongos 7 6 Cocinar la salsa de tomate 25 5 7 Hervir agua en una vasija 15 8 Hervir la pasta de lasaña 10 7 9 Enjuagar la pasta de lasaña 2 8 10 Unir los ingredientes 10 9,6,4,2 11 Precalentar el horno 15 12 Hornear la lasaña 30 10,11
Ejemplo(cont.)
![Page 6: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/6.jpg)
6
Formular el problema.
Modelarlo (p ej) con un grafo.
Encontrar para cada actividad:
• el tiempo de ejecución,
• las holguras que tienen ,
• si componen el camino crítico.
Procedimiento
![Page 7: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/7.jpg)
7
� Una llamada telefónicainterrumpió el proceso durante seis minutos cuando debíaestar picando las cebollas y hongos
� Cuanto tiempo se retrasará la cena?
�Si usa procesador de alimentos, el tiempopara picar se reduce de siete minutos a dos. Con esto, todavía se retrasará la cena?
Preguntas posibles
![Page 8: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/8.jpg)
8
•Informática (jobs scheduling, gestión de recursos: procesos, memoria en sistemas operativos, desarrollo de software),
•Construcción (seguimiento de proyectos),
•Industria (problemas de talleres, gestión de la producción),
•Administración (empleo de tiempo).
Problemas de ordenamiento –Areas de aplicación
![Page 9: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/9.jpg)
9
Problemas de ordenamiento con restricciones temporales y de precedencia
Empírico: diagramas de Gantt, hasta 1958. Método gráfico de representar duración y sucesión de tareas,
y visualizar posibles soluciones
Metódicos:• PERT: Program Evaluation &
ReviewTechnique (americano), • CPM: Critical Path Method (de los
potenciales B. Roy).
Métodos de Solución
![Page 10: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/10.jpg)
10
Representación de las soluciones (diagrama de Gantt)
Es un método gráfico de representar la solución (el ordenamiento);
Valiosa herramienta para resolver el problema, en forma empírica.
Se visualizan
tiempos, duraciones,
sucesión de tareas y
utilización de recursos.
![Page 11: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/11.jpg)
11
Ejemplo: Diagrama de Gantt
Sean 5 tareas I = (1, 2, 3, 4, 5)
de duraciones d = (6, 3, 4, 5, 5)
que usan, {4, 1, 3, 2, 3} unidades de recurso 1
y {8, 7, 10, 10, 4} unidades de recurso 2,
fechas de inicio ejecución
t i: {0, 3, 6, 8, 10}
![Page 12: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/12.jpg)
12
Sucesión y tiempos
![Page 13: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/13.jpg)
13
Utilización de Recursos
![Page 14: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/14.jpg)
14
Método de Camino CríticoEl método del camino crítico resuelve problemas donde solo se consideran restricciones potenciales (sucesión y ubicación temporal, en el tiempo). Es un caso particular de problemas de ordenamiento, los más simples.Es un método polinomial.Las Redes de Petri permiten incluir restricciones de recursos, pero no siempre se obtiene la optimalidad.
![Page 15: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/15.jpg)
15
Nociones elementalesde ordenamiento
�las tareas,
�las restricciones potenciales,
�los recursos y
�la función económica.
![Page 16: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/16.jpg)
16
Son el común denominador de los problemas de ordenamiento, su definición no es siempre inmediata, ni trivial.
Cuando la duración y las fechas mas tempranas de comienzode una tarea son conocidas, estamos ante un problema estático.
Por el contrario, cuando el conjunto de tareas evoluciona con el tiempo, estamos ante problemas dinámicos.
Y si lo hacen de forma no determinista, son estocásticos.
Tareas
![Page 17: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/17.jpg)
17
Tareas: Modos de ejecución
a) continua (sin interrupción) o
b) discontinua.La tarea en este caso es "preemtable" (interrumpible)
El poder interrumpir tareas, disminuye la
complejidad de los problemas de ordenamiento. Eso ocurre, p, ej. cuando una tarea j de mayor prioridad necesita de un recurso qué está siendo usado por otra tarea i, si esta tarea puede ser interrumpida , el recurso pasa a ser utilizado por j.
![Page 18: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/18.jpg)
18
Inciden en la sucesión y la ubicación de las tareas en el tiempo.
Ejemplos:
•Restricciones de sucesión: construir primero los cimientos de un edificio, luego las paredes, etc.
• Restricciones de ubicación temporal: tal tarea no puede comenzar antes de tal fecha, o debe terminar antes que tal otra tarea.
Restricciones potenciales
![Page 19: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/19.jpg)
19
Tareas: Restricciones potenciales�Si dos tareas NO pueden ejecutarse simultáneamente, (p.ej, cuando requieren el
mismo recurso al mismo tiempo), NO se usanlas restricciones potenciales.
� El conjunto de restricciones potencialesse puede representar por un grafo ponderado.
� El Método de Camino Crítico trabaja esencialmente sobre ese grafo.
![Page 20: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/20.jpg)
20
RecursosSon los medios necesarios para que las
tareas se ejecuten.
Determinan dos tipos de restricciones:
1. Disjuntas. cuando, p. ej. dos tareas usan la misma máquina y no se pueden ejecutar simultáneamente.
2. Acumulativas: p. ej. :3 procesadores para ejecutar 4 tareas; una se retrasaráy deberá necesariamente esperar la finalización de alguna de las otras.
![Page 21: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/21.jpg)
21
Recursos1. Renovable: después de haber sido usado en
una tarea, es utilizable totalmente en las tareas posteriores. Ejemplos: máquinas, procesadores, archivos, personal, etc.
2. Consumible: después de haber sido utilizado en una tarea, ya no esta más disponible para las posteriores. Ejemplos: materias primas, dinero, etc.
Los recursos, sean renovables o no, pueden estar disponibles solamente durante ciertos períodos, sujetos a una curva de disponibilidad.
![Page 22: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/22.jpg)
22
Criterios de optimización
Los factores más importantes en la evaluación de un ordenamiento son:
�la utilización eficaz de los recursos,
�la disminución de la demora global
�el respeto del mayor número posible de restricciones introducidas.
![Page 23: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/23.jpg)
23
Función objetivoOrdenar es programar las tareas de manera de
optimizar “algo”
sujeto a restricciones.Ejemplo:
�Optimizar el uso de recursos,
�Optimizar la demora en la de ejecución de las tareas,
�Optimizar el cumplimiento de las fechas de finalización.
Criterio más usado: minimizar la duración total del programa respetando las fechas de los pedidos.
Otro criterio: minimizar el costo de operación, etc.
![Page 24: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/24.jpg)
24
Notación-conceptos generalesI = {conjunto de tareas},
n = número de tareas a ejecutar (card I),
di = duración de la tarea i,
ci = fecha de disponibilidad, o
comienzo mas temprano de la tareai
Fi = fecha finalización forzada ("deadline") tarea i
t i = fecha de comienzo de ejecuciónde la tarea i,
T i = fecha de fin de ejecuciónde la tarea i.
![Page 25: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/25.jpg)
25
Tareas y Tiempos
�Si la tarea iNO se interrumpe,
T i = ti + di.
�Una condición necesaria para que un ordenamiento sea realizable es:
ci ≤≤≤≤ t i <<<< T i ≤≤≤≤ Fi, ∀∀∀∀ i ∈∈∈∈ I
�En ciertos casos, si hay un retardo
tal que T i >>>> Fi, se podrá considerar un costo asociado a la tarea i.
![Page 26: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/26.jpg)
26
Tareas: Restricción Potencial
En general, dos tareas cualesquiera i, j ∈∈∈∈ I ,
no son independientes y pueden estar ligadas por restricciones de anterioridad (sucesión).
Notaremos una restricción potencial entre las tareas j e i de la sg manera:
t j - t i ≥≥≥≥ aij
Si aij = di , la sucesión es simple.
![Page 27: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/27.jpg)
27
Criterios de optimización-MCCDuración total del ordenamiento:
Tmax = max {Ti}, ∀∀∀∀ i∈∈∈∈I.
(fecha de fin de la tarea que termina último)
Obs: Fecha de comienzo del proyecto t0= 0,
Criterio mas utilizado:min Tmax
según restricciones potenciales
Generalmente con este criterio se asegura además una utilización eficaz de los recursos.
![Page 28: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/28.jpg)
28
Otro criterio de optimización: Respetar las fechas mas tardías de finalización
Es decir, minimizar el retraso mayor.
Las demoras se relacionan con las fi fechas obligatorias y que deben ser respetadas.
Sea el retraso de i: Ri = max (0, Ti - Fi)entonces el retraso mayor es
Rmax = max {Ri} i∈∈∈∈I .
El criterio sería min (Rmax)
![Page 29: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/29.jpg)
29
Otros criterios: Minimizar costos , Minimizar número de interrupciones
a) La suma ponderada de las fechas de finalización de tareas; es usado para minimizar costos de inventarios
b) Si una tarea es interrumpida n veces, la suma del número total de interrupciones para todas las tareas (criterio secundario y complementario). En multiprogramación, a cada interrupción de tarea, se asocia un cambio de contexto con duración no despreciable.
![Page 30: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/30.jpg)
30
El problema central de los ordenamientos
Se trata de ordenar
un conjunto de tareas I={1,...n}
de modo de obtener
una duración minimal del proyecto.
![Page 31: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/31.jpg)
31
El problema central de los ordenamientos
Las tareas están sujetas a restricciones temporales del tipo
t j - t i ≥≥≥≥ aij , i, j ∈∈∈∈ I desigualdad potencial
t i es la fecha de comienzo de la tarea i (respectivamente tj y j)
aij es un número real.
![Page 32: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/32.jpg)
32
El problema central de los ordenamientos
Objetivo: min (Tmax):
tiempo de fin de la última tarea
Min (max i∈∈∈∈X(t i +di)) sujeto a: tj - t i ≥≥≥≥ aij ,
aij Real, Ti=ti+di
Se modela mediante grafos ponderados. Se calculan caminos en grafos.
![Page 33: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/33.jpg)
33
Modelado: grafo potencial-tareas
Se modela como un problema de optimización combinatoria mediante
un grafo ponderado G = (X,U,W)
llamado de potencial-tareas.
X = I ∪∪∪∪ {0, n+1} ,
conjunto de tareas I , más dos tareas adicionales, ficticias, una de inicio llamada tarea 0 y una de fin, la tarea n+1.
![Page 34: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/34.jpg)
34
Modelado: grafo potencial-tareas
G = (X,U,W), potencial-tareas.
X = I ∪∪∪∪ {0, n+1} ,
Las tareas 0 y (n+1) tienen una duración nula.
U : {arcos (0, i), donde w(0,i) = 0,
arcos (i, j) asociados a las restricciones potenciales, con w(i,j) = aij , y
arcos (i,n+1) con w(i,n+1) = di }.
![Page 35: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/35.jpg)
35
Ejemplo
m
0
i
j
k
n+1
0
0
aik
dj
aij
amj
dk
0
0
di
dm
dk
![Page 36: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/36.jpg)
36
Propiedades
1) t0 = 0, para asegurar la positividadde una solución.
2) Restricciones potenciales t j-t i ≥≥≥≥ aij
3)Restricciones redundantes : si existen (i,j), (j,k) y (i,k),
tal que aik ≤≤≤≤ aij + ajk , (i, k) puede suprimirse.
![Page 37: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/37.jpg)
37
Ejemplo - redundancia
aijajk
aik
i
j
k
Min {max i (t i + di)}t j - t i ≥≥≥≥ aijtk - t j ≥≥≥≥ ajk
tk - t i ≥≥≥≥ aij + ajkpor otro lado
tk - t i ≥≥≥≥ aik
Si aij + ajk ≥≥≥≥ aik entonces
puedo eliminar (i,k)
![Page 38: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/38.jpg)
38
Ejemplo-redundancia
![Page 39: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/39.jpg)
39
Aplicando redundancia
![Page 40: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/40.jpg)
40
Modelado de restricciones por desigualdades de potencial
ci: Fecha de disponibilidad,
t i ≥≥≥≥ ci, implica la restricción potencial
(t i-t0) ≥≥≥≥ ci
0
i
ci
![Page 41: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/41.jpg)
41
Deadline Fi
Fi: Fecha mas tardía admitida de
finalización,
(t i + di)≤≤≤≤ Fi, ���� (t0 - t i) ≥≥≥≥ (di - Fi)
i0
(di - Fi)
![Page 42: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/42.jpg)
42
Sucesión Larga o Simple
La tarea j no puede comenzar antes del fin de la tarea i:
t j ≥≥≥≥ t i + di,
���� t j-t i ≥≥≥≥ di
![Page 43: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/43.jpg)
43
Sucesión inmediata
La tarea j empieza exactamentecuando termina la tarea i:
t j = ti + di, t j - t i = di
(t j - t i ≥≥≥≥ di) y t j - t i ≤≤≤≤ di
����(t j - t i) ≥≥≥≥ di y
(t i - t j) ≥≥≥≥ -di
![Page 44: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/44.jpg)
44
Ejemplo
I = {1, 2, 3, 4, 5} ; d = {1, 3, 1, 2, 1}
La tarea 2 comienza en la fecha 3;
Las tareas 3 y 4 deben superponerse por al menos una unidad de tiempo;
La tarea 4 puede comenzar solamente despues del fin de las tareas 1 y 2;
La tarea 5 no puede empezar antes del comienzo de la tarea 3.
![Page 45: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/45.jpg)
45
EjemploLas duraciones de las 5 tareas I = {1, 2, 3, 4, 5},son d = {1, 3, 1, 2, 1}
Restricciones temporales:
1. la tarea 2 comienza en la fecha 3: [t2 - t0 = 3]
restricción potencial[t2 - t0 ≥≥≥≥ 3] y [t0 - t2 ≥≥≥≥ - 3]
![Page 46: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/46.jpg)
46
Ejemplo
![Page 47: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/47.jpg)
47
Aplicando redundanciaGrafo potencial-tarea
![Page 48: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/48.jpg)
48
2. las tareas 3 y 4 deben superponerse por al menos una unidad de tiempo:[t3 ≤≤≤≤ t4 + d4 -1] y [t4 ≤≤≤≤ t3 + d3 - 1]t4 - t3 ≥≥≥≥ 1 - d4=-1 y t3 - t4 ≥≥≥≥ 1 - d3 =0
d = {1, 3, 1, 2, 1}
![Page 49: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/49.jpg)
49
d = {1, 3, 1, 2, 1}3. la tarea 4 puede comenzar solamente
después del fin de las tareas 1 y 2: [t4 - t1 ≥≥≥≥ d1] y [t4 - t2 ≥≥≥≥ d2]
4. la tarea 5 no puede empezar antes del comienzo de la tarea 3 [t5 ≥≥≥≥ t3] ==> t5 - t3 ≥≥≥≥ 0
![Page 50: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/50.jpg)
50
Problema simple
tarea duración restricciones potenciales 1 3 2 7 3 4 la tarea 1 precede a la tarea 3 4 6 las tareas 1 y 2 preceden a la 4 5 5 la tarea 3 precede a la 5 6 3 las tareas 3 y 4 preceden a la 6 7 2 la tarea 6 precede a la 7
![Page 51: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/51.jpg)
51
Grafo potencial tareas.Redundancia aplicada
(7,
![Page 52: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/52.jpg)
52
Método Cam.CríticoConceptos generales
Grafo conjuntivo: es un grafo G=(X, U,W), (ponderado)
con un nodo raiz 0 y otro final n+1, tal que
existe un camino de valor positivo entre la raiz y todo otro nodo del grafo,
y un camino de valor positivo entre todo nodo distinto del nodo final y el nodo final del grafo.
![Page 53: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/53.jpg)
53
Grafo Conjuntivo
0 n+1
i∈∈∈∈I
![Page 54: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/54.jpg)
54
Conjunto de potencialesen G
Un conjunto de potenciales en un grafo conjuntivo G = (X, U, W), es una aplicación t : X→→→→R,
tal que t0 = 0 y que
∀ (i,j) , arco conjuntivo, con ponderación
w(i,j) = w ij , se aplica la restricción potencial
(t j - t i) ≥≥≥≥ wij .
![Page 55: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/55.jpg)
55
Teorema de Existencia
Una condición necesaria y suficiente
para que exista un conjunto de potenciales sobre un
grafo conjuntivo G=(X ,U, W)
es que este grafo no contenga circuitos de
valor estrictamente positivo.
![Page 56: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/56.jpg)
56
Sea [1,2,...r,1] un circuito de valor estrictamente positivo: w12 +....+ wr1 >>>> 0.Por H. existe un conjunto de potenciales sobre G, t2 - t1 ≥≥≥≥ w12
……...….... tr- tr-1 ≥≥≥≥ w(r-1)r
t1- tr ≥≥≥≥ wr1Sumando tenemos w12 + ...+ wr1≤≤≤≤ 0,
absurdo.
Demostración: (⇒⇒⇒⇒) Por absurdo.
![Page 57: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/57.jpg)
57
Demostración (⇐⇐⇐⇐)H: G conjuntivo: ∃∃∃∃ al menos un camino
de valor positivo, de 0 a i. No ∃∃∃∃ circuitos de valor positivo.
T: ∃∃∃∃ conjunto de potenciales.
Tomemos un camino de 0 a i y suprimamos circuitos negativos. Así puedo extraer un camino de 0 a i, elemental, de valor por lo menos el del camino original ( ≥≥≥≥ ).
![Page 58: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/58.jpg)
58
Demostración (⇐⇐⇐⇐)Tomemos un camino de 0 a i y suprimamos circuitos negativos. Así obtengo un camino de 0 a i, elemental, de valor por lo menos el del camino original ( ≥ ).
0 i
![Page 59: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/59.jpg)
59
Cont. Demostración (⇐⇐⇐⇐)El nro. de caminos elementales es finito.
Por eso, ∃∃∃∃ algun camino de 0 a i que es máximo.
Sea r i el valor máximo de entre los caminos elementales de 0 a i;
Además r0 = 0.
![Page 60: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/60.jpg)
60
Cont. Demostración (⇐⇐⇐⇐)
r i + w(i,j) = valor de un camino de 0 a jpasando por i con un valor ri,
Por lo tanto r i + w(i,j) ≤≤≤≤ r j���� r j – r i ≥≥≥≥ wij , ∀∀∀∀ i, j∈∈∈∈ I .
R={ r i } ∀∀∀∀ i ∈∈∈∈ I es un conjunto de potenciales LQQD.
![Page 61: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/61.jpg)
61
Corolario 1: Si un grafo conjuntivo no tiene circuitos, existe siempre al menos un conjunto de potenciales asociados.
Corolario 2: Si las ponderaciones de los arcos de un grafo conjuntivo son positivas o nulas, existe al menos un conjunto de potenciales sii todos los circuitos son de valor nulo.
![Page 62: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/62.jpg)
62
Notaciones y definiciones
De ahora en adelante, suponemos que el grafo conjuntivo no contiene circuitos de valor positivo.
Sea V(i,j) el valor maximal de un caminode i a j,
V(i,i) = 0 y V(i,j) = -∞∞∞∞ si NO hay camino de i a j.
���� r i = V(0,i).
![Page 63: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/63.jpg)
63
Lema 1∀pareja i, j ∈∈∈∈ I y (i,j) ∈∈∈∈U:
t j - t i ≥≥≥≥ V(i,j).Demo: Sea [i, h,...,k, j] un camino de
i a j de valor V(i,j) (max),Por def. de potencial en G:
th-t i ≥≥≥≥ wih, tr-th ≥≥≥≥ whr , ..., tk-ts≥≥≥≥ wsk, tj-tk ≥≥≥≥ wkj .
sumando todos los términos:t j - t i ≥≥≥≥ wih + ...+ wkj = V(i,j). L.Q.Q.D.
![Page 64: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/64.jpg)
64
Proposición 1∀conjunto de potenciales T = {ti},
r i ≤≤≤≤ t i.
Dem: Según el lema anterior, ti - t0 ≥≥≥≥ V(0,i),V(0,i) = ri y t 0= 0,
ri ≤≤≤≤ ti L.Q.Q.D.
Esta propiedad muestra que para el conjunto de potenciales R, las tareas se ejecutan lo más temprano posible.
![Page 65: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/65.jpg)
65
Conjunto de potenciales optimales,Camino Crítico
En los métodos de potenciales se buscará un ordenamiento de duración total minimal.
Este ordenamiento corresponderá a un conjunto de potenciales tal que tn+1 sea minimal (obs. Tn = tn+1 ).
![Page 66: Métodos del Camino Crítico - fing.edu.uy · 1 Métodos del Camino Crítico Introducción a la Investigación de Operaciones – año 2007 I.O.-InCo-Facultad de Ingeniería-UDELAR](https://reader034.vdocumento.com/reader034/viewer/2022052518/5f0d91b77e708231d43b019b/html5/thumbnails/66.jpg)
66
Conjunto de potenciales optimalesCamino Crítico
Según la proposición 1, ri ≤≤≤≤ ti,
cuándotn+1 es minimal? tn+1 = rn+1
tn+1 = rn+1 = V(0,n+1) valor maximal de uncamino que va de 0 a n+1.
Es el camino crítico y notamos t* su valor.