Universidad Aut´onoma de Yucat´an Facultad de Ingenier´ıa Qu´ımica Investigaci´on de Operaciones II Notas del Curso L.
Views 98 Downloads 1 File size 757KB
Universidad Aut´onoma de Yucat´an Facultad de Ingenier´ıa Qu´ımica
Investigaci´on de Operaciones II Notas del Curso
L.C.C. Jos´e Felipe Golib Dzib Act. Guadalupe Siordia Montero para la licenciatura en: Ingenier´ıa Industrial Log´ıstica Sexto Semestre
M´erida, Yucat´an, M´exico Septiembre, 2007
´Indice general 1. Introducci´ on a la Administraci´ on de Proyectos 1.1. Construcci´on de Redes . . . . . . . . . . . . . . . 1.2. An´alisis de Redes . . . . . . . . . . . . . . . . . . 1.2.1. Problema de la Ruta m´as Corta . . . . . . 1.2.2. Problema del Flujo M´aximo . . . . . . . . ´ 1.2.3. Problema del Arbol de Expansi´on M´ınima 1.2.4. Problema del Flujo de Costo M´ınimo . . . 1.3. Introducci´on a la Ruta Cr´ıtica . . . . . . . . . . . 1.4. M´etodos para Determinar la Ruta Cr´ıtica . . . . 1.5. Gr´aficas de Gantt . . . . . . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
1 1 6 6 8 14 17 19 22 24
. . . . . . . . . . . . . . . . . . . . de Incertidumbre . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
33 33 37 41 42
3. Teor´ıa de Colas o L´ıneas de Espera 3.1. Introducci´on a los Modelos de Colas . . . . . . . . . . . . . . . 3.1.1. Caracter´ısticas B´asicas . . . . . . . . . . . . . . . . . . . 3.1.2. Clasificaci´on de los Modelos de Colas . . . . . . . . . . . 3.1.3. Medidas de Rendimiento . . . . . . . . . . . . . . . . . . 3.1.4. Papel de la Funci´on Exponencial . . . . . . . . . . . . . 3.2. Proceso de Colas Basado en el Proceso de Nacimiento y Muerte 3.3. Modelos con Distribuci´on de Poisson . . . . . . . . . . . . . . . 3.3.1. Modelo M/M/s . . . . . . . . . . . . . . . . . . . . . . . 3.3.2. Modelo M/M/s/K . . . . . . . . . . . . . . . . . . . . . 3.3.3. Variaci´on de Fuente de Entrada al Modelo M/M/s . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
45 45 45 48 53 54 55 60 60 63 67
. . . . .
69 69 72 73 81 81
2. Toma de Decisiones 2.1. Cadenas de Markov 2.2. Teor´ıa de Juegos . 2.3. Toma de Decisiones ´ 2.4. Arboles de Decisi´on
. . . . . . . . . . . . . . . . . . . . bajo Condiciones . . . . . . . . . .
. . . . . . . . .
4. Secuenciaci´ on 4.1. Definiciones, notaci´on y conceptos de secuenciaci´on. 4.2. Medidas de Desempe˜ no . . . . . . . . . . . . . . . . 4.3. Secuenciaci´on en una M´aquina . . . . . . . . . . . . 4.4. Secuenciaci´on en dos M´aquinas . . . . . . . . . . . 4.5. Extensiones a tres o m´as M´aquinas . . . . . . . . . Bibliograf´ıa
. . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
85
i
Cap´ıtulo 1 Introducci´ on a la Administraci´ on de Proyectos Objetivo Al finalizar la unidad, el alumno o la alumna construir´a el diagrama de redes del problema que se le presente y aplicar´a el m´etodo de la ruta cr´ıtica para planear y administrar un proyecto determinado.
1.1.
Construcci´ on de Redes
Una representaci´on de redes proporciona un panorama general tan poderoso y una ayuda conceptual para visualizar las relaciones entre los componentes de los sistemas que se usa casi en todas las ´areas cient´ıficas, sociales y econ´omicas. Ejemplo 1. (Tomado de [1]) Sara se acaba de graduar de la prepa. Como regalo de graduaci´ on, sus padres le han dado $21,000 para que compre y mantenga un carro que ha sido usado por tres a˜ nos para ir a la universidad. Como los gastos de operaci´on y mantenimiento aumentan r´apidamente a medida que el carro es m´as viejo, los pap´as de Sara le dicen que puede vender su carro y comprar otro auto de tres a˜ nos de uso una o m´as veces durante los siguientes tres veranos si considera que esto minimiza su costo total neto. Ellos le informan que le dar´an un nuevo carro en cuatro a˜ nos por lo que debe definitivamente vender su carro entonces. El Cuadro 1.1 da los datos relevantes para cada momento que Sara compra un carro de tres a˜ nos de uso. Por ejemplo, si ella vende su carro despu´es de dos a˜ nos, el siguiente carro ser´a suyo durante un a˜ no, etc. 1
´ A LA ADMINISTRACION ´ DE PROYECTOS2 CAP´ITULO 1. INTRODUCCION
Precio de compra $12,000
Costos de mantenimiento y operaci´on al final del a˜ no 1 2 3 4 $2,000 $3,000 $4,500 $6,500
Valor en el mercado al final del a˜ no 1 2 3 4 $8,500 $6,500 $4,500 $3,000
Cuadro 1.1: Datos para Sara cada vez que compra un carro de tres a˜ nos de uso.
¿Cu´ando debe Sara vender su carro (si es que debe hacerlo) durante los siguientes tres veranos para minimizar su costo total neto de compra, operaci´on y mantenimiento de los carros durante los siguientes cuatro a˜ nos? Soluci´on. Este problema se puede plantear usando una red. Para resolverlo necesitamos encontrar el camino m´as corto del 0 al 4. Esto se logra pasando de 0 al 2 y luego al 4. Este camino se traduce en un costo de $21,000. 25,000
10,500
0
5,500
1
10,500
5,500
17,000
2
10,500
5,500
3
5,500
4
17,000
Figura 1.1: Red para el Ejemplo 1. Una red consiste en un conjunto de puntos y un conjunto de l´ıneas que unen ciertos pares de puntos. Los puntos se llaman nodos (o v´ertices). La red del Ejemplo 1 tiene cinco nodos. Las l´ıneas se llaman arcos (o ligaduras, aristas o ramas). El Ejemplo 1 tiene diez arcos. Los arcos se etiquetan dando los nombres de los nodos en sus puntos terminales. Por ejemplo, 0 → 1 es el arco que une el nodo 0 y el nodo 1. Otra forma de etiquetarlo es 01. Los arcos de una red pueden tener un flujo de alg´ un tipo que pasa por ellos. Por ejemplo, en la red del Ejemplo 1, los arcos tienen un flujo que significa los costos netos de las operaciones posibles para Sara. Si el flujo de un arco se permite en s´olo una direcci´on, se dice que el arco es dirigido. La direcci´on se indica agregando una cabeza de flecha al final de la l´ınea que representa el arco. Al etiquetar un arco
´ A LA ADMINISTRACION ´ DE PROYECTOS3 CAP´ITULO 1. INTRODUCCION dirigido con el nombre de los nodos que une, siempre se pone primero el nodo de donde viene y despu´es el nodo a donde va. Dirigido (flujo). Arco No dirigido (ligadura). Si el flujo del arco se permite en ambas direcciones, se dice que es un arco no dirigido. Para ayudar a distinguir entre los dos tipos de arcos, con frecuencia se har´a referencia a los arcos no dirigidos como ligaduras. Observaci´ on 1. Aunque se permita que el flujo a trav´es de un arco no dirigido ocurra en cualquier direcci´on, se supone que ese flujo ser´a en una direcci´on, la seleccionada, y no se tendr´an flujos simult´aneos en direcciones opuestas. Para eso se requerir´ıa un par de arcos dirigidos en direcciones opuestas. Una red que tiene s´olo arcos dirigidos se llama red dirigida. Cuando todos sus arcos son no dirigidos, se trata de una red no dirigida Dirigida. Red No dirigida. Observaci´ on 2. Una red con una mezcla de arcos dirigidos y no dirigidos (o incluso todos sus arcos no dirigidos) se puede convertir en una red dirigida, se se desea, sustituyendo cada arco no dirigido por un par de arcos dirigidos en direcciones opuestas. Cuando dos arcos no est´an unidos por un arco surge la pregunta de si est´an conectados por una serie de arcos. Una trayectoria entre dos nodos es una sucesi´on de arcos distintos que conectan esos nodos. Por ejemplo, una trayectoria que conecta los nodos 0 y 4 en el Ejemplo 1, es 0 → 1 → 2 → 4 y viceversa. Cuando algunos o todos los arcos de una red son arcos dirigidos, se hace la distinci´on entre trayectoria dirigida o trayectoria no dirigida. Dirigida. Trayectoria No dirigida. Una trayectoria dirigida del nodo i al nodo j es una sucesi´on de arcos cuya direcci´on (si la tienen) es hacia el nodo j, de modo que el flujo del nodo i al nodo j es factible. Una trayectoria no dirigida del nodo i al nodo j es una sucesi´on de arcos cuya direcci´on (si la tienen) puede ser hacia o desde el nodo j.
´ A LA ADMINISTRACION ´ DE PROYECTOS4 CAP´ITULO 1. INTRODUCCION A
D
C
B
E
Figura 1.2: La red del Ejemplo 2. Observaci´ on 3. Una trayectoria dirigida tambi´en satisface la definici´on de trayectoria no dirigida, pero el inverso no se cumple. Ejemplo 2. Consideremos la red dirigida que se muestra en la Fig. 1.2, para responder lo siguiente: 1. ¿Cu´al es una trayectoria dirigida de A a E? 2. ¿Es BC − AC − AD una trayectoria dirigida del nodo B al nodo D? Soluci´on. Tomando en cuenta la Fig. 1.2: 1. La sucesi´on de arcos AB − BC − CE, o bien, A → B → C → E es una trayectoria dirigida del nodo A al nodo E, ya que flujo hacia el nodo E a lo largo de toda esta trayectoria es factible. 2. No es una trayectoria dirigida del nodo B al nodo D, porque la direcci´on del arco AC es en sentido opuesto. Sin embargo, B → C → A → D es una trayectoria no dirigida del nodo B al nodo D, debido a que la secuencia de arcos BC − AC − AD conecta a estos nodos. Un ciclo es una trayectoria que comienza y termina en el mismo nodo. En una red dirigida, un ciclo puede ser dirigido o no dirigido, seg´ un si la trayectoria en cuesti´on es dirigida o no dirigida. Ciclo
Dirigido. No dirigido.
Por ejemplo, en la Fig 1.2, DE − ED es un ciclo dirigido. Pero AB − BC − CA no es un ciclo dirigido.
´ A LA ADMINISTRACION ´ DE PROYECTOS5 CAP´ITULO 1. INTRODUCCION Observaci´ on 4. La definici´on de trayectoria (una sucesi´on de arcos distintos) elimina la posibilidad de retroceder al formar un ciclo. Se dice que dos nodos est´an conectados si la red contiene al menos una trayectoria no dirigida entre ellos. Observaci´ on 5. Para que dos nodos est´en conectados no es necesario que la trayectoria que los une sea dirigida a´ un cuando la red sea dirigida. Una red conexa es una red en la que cada par de nodos est´a conectado. La red de la Fig. 1.2 es conexa, pero dejar´ıa de serlo si se eliminan los arcos AD y CE. Un ´arbol es una red conexa que carece de ciclos no dirigidos. Cuando la red tiene n˜ nodos podemos crear un ´arbol que una a cada par de nodos. Para esto ser´an necesarios n − 1 arcos y a ese ´arbol se le llama ´arbol de expansi´on. El proceso de expansi´on se ilustra en la Fig. 1.3. A
D
A
C
B
C
E
B
(1) A
A
C
D
C
E (2)
E (3)
D
B
D
B
E (4)
Figura 1.3: Proceso de expansi´on para hacer crecer un ´arbol. La cantidad m´axima de flujo (que puede ser infinita) que puede circular en un arco dirigido se conoce como capacidad del arco. Entre los nodos, se pueden distinguir
´ A LA ADMINISTRACION ´ DE PROYECTOS6 CAP´ITULO 1. INTRODUCCION los que son generadores de flujo, absorbedores netos o ninguno de los dos. Fuente (origen). Demanda (destino). Nodos Trasbordo (intermedio).
Un nodo fuente (o nodo origen) tiene la propiedad de que el flujo que sale del
nodo excede el flujo que entra a ´el. El caso contrario es un nodo demanda (o nodo destino), en el cual el flujo entrante excede al saliente. Un nodo de trasbordo (o nodo intermedio) satisface la conservaci´on del flujo, as´ı el flujo que entra es igual al que sale.
1.2.
An´ alisis de Redes
En una gran variedad de situaciones podemos encontrar a los problemas de redes. Por ejemplo, tenemos las redes de transporte, el´ectricas, de mercadeo y de comunicaciones. Uno de los desarrollos m´as significativos de la Investigaci´on de Operaciones es el r´apido avance tanto en la metodolog´ıa como en la aplicaci´on de los modelos de optimizaci´on de redes. La aparici´on de algunos algoritmos ha tenido un impacto vital, al igual que las ideas en el ´area computaci´on sobre estructuras de datos y la manipulaci´on eficiente de los mismos [2]. Muchos modelos de optimizaci´on de redes son, en realidad, casos especiales de problemas de programaci´on lineal. Por ejemplo, el problema de transporte y el problema de asignaci´on tambi´en se pueden ver como problemas de optimizaci´on de redes que se pueden resolver con la metodolog´ıa de redes.
1.2.1.
Problema de la Ruta m´ as Corta
Una versi´on simplificada de este problema consiste en una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cada una de las ligaduras se le asigna un distancia no negativa. El objetivo es encontrar la ruta m´as corta (la trayectoria con la m´ınima distancia total) que va del origen al destino. El algoritmo para resolver este problema consiste en que para la n-´esima iteraci´on, nuestro objetivo ser´a encontrar el n-´esimo nodo m´as cercano al origen. Este paso se
´ A LA ADMINISTRACION ´ DE PROYECTOS7 CAP´ITULO 1. INTRODUCCION repetir´a para n = 1, 2, . . . hasta que el n-´esimo nodo m´as cercano al origen sea el destino. Esto se logra conforme a las siguientes reglas: 1. Si estamos en la iteraci´on n, entonces hay n − 1 nodos m´as cercanos al origen (que se encontraron en las iteraciones previas), incluyendo su ruta m´as corta y la distancia desde el origen a cada uno de ellos. A estos nodos y al nodo origen se les llama nodos resueltos, el resto de los nodos son no resueltos. 2. Para calcular el n-´esimo nodo m´as cercano, tenemos que para cada nodo resuelto y sus candidatos (nodos no resueltos conectados al dicho nodo resuelto), se suma la distancia entre ellos y la distancia de la ruta m´as corta desde el origen a este nodo resuelto. El candidato con la distancia total m´as peque˜ na es el n-´esimo nodo m´as cercano al origen y su la ruta m´as corta es la que genera esta distancia. Los empates generan nodos resueltos adicionales. Ejercicio 1. Un cami´on debe viajar de M´erida a Temoz´on. Existen varias rutas, como se muestra en la Fig. 1.4. El n´ umero en cada arco es el n´ umero de litros de combustible que requiere el cami´on para atravesar el arco. 1. Aplica el algoritmo del camino m´as corto para encontrar la ruta de M´erida a Temoz´on que utiliza la cantidad m´ınima de combustible. 2. ¿Qu´e ruta debe llevar el cami´on? 3. Considerando que el litro de combustible cuesta $ 5.67, ¿Cu´anto es lo m´aximo que estar´ıa dispuesto a pagar por un viaje de M´erida a Temoz´on? Otra versi´on (m´as general) del problema de la ruta m´as corta se describe a continuaci´on. Supongamos que queremos encontrar la trayectoria m´as corta del nodo 1 al nodo j en una red en la que los arcos tienen longitudes no negativas. Usaremos el algoritmo de Dijkstra: 1. Etiquetamos el nodo 1 con una etiqueta permanente de 0. Luego marcamos cada arco conectado al nodo 1 mediante un solo arco con una etiqueta ”temporal” igual a la longitud del arco que une al nodo 1 con el nodo i. Los dem´as nodos tendr´an la etiqueta temporal ∞. Elegimos el nodo con la etiqueta temporal m´as peque˜ na y hacemos permanente esta etiqueta.
´ A LA ADMINISTRACION ´ DE PROYECTOS8 CAP´ITULO 1. INTRODUCCION
Motul
180
Tizim´ın
90
40
40 90
110 M´erida
95
Tixcocob
60
Tuncas
130
Temoz´on
60 100 60
80 Hocab´a
120
Valladolid
Figura 1.4: Red para el ejercicio 1. 2. Supongamos que el nodo i es el (k + 1)-´esimo nodo que recibir´a una etiqueta permanente. Para cada nodo j que ahora tiene una etiqueta temporal y est´a conectado al nodo i por un solo arco, sustituimos la etiqueta temporal del nodo j con el: m´ın
etiqueta temporal , del nodo j
etiqueta permanente del nodo i
longitud del + arco (i, j)
,
hacemos permanente la etiqueta temporal m´as peque˜ na. Continuamos este proceso hasta que todos los nodos tengan etiquetas permanentes o bien si s´olo nos interesa la trayectoria m´as corta del nodo 1 al nodo j, detenemos el proceso tan pronto como el nodo j reciba una etiqueta permanente. 3. Para encontrar la trayectoria m´as corta del nodo 1 al nodo j, recorremos la red hacia atr´as desde el nodo j pasando por los nodos que tienen etiquetas que difieren por exactamente la longitud del arco de conexi´on.
1.2.2.
Problema del Flujo M´ aximo
Para el problema del flujo m´aximo consideramos una red dirigida y conexa que tiene exactamente un nodo fuente y un s´olo nodo destino, el resto de los nodos son
´ A LA ADMINISTRACION ´ DE PROYECTOS9 CAP´ITULO 1. INTRODUCCION de trasbordo. Tomando en cuenta la capacidad de los arcos, el objetivo es determinar el patr´on de flujos factibles a trav´es de la red que maximiza el flujo total, desde el nodo origen hasta el nodo destino. El m´etodo Simplex sirve para resolver un problema de flujo m´aximo ya que este problema puede plantearse como uno de programaci´on lineal. Alternativamente, podemos usar otro m´etodo para resolver el problema de flujo m´aximo como se describe a continuaci´on. A partir de la red dada del problema se construye una red residual que muestra las capacidades restantes (llamadas capacidades residuales) para asignar flujos adicionales. Por ejemplo, consideremos la red de la Fig. 1.5. 5
3
1
3 4
2.5 O
3.5
2 4
2
1.5
M
4
Figura 1.5: Un ejemplo de red con capacidades en los arcos. El arco O → 1 tiene una capacidad de 5. Al inicio, en la red residual, antes de asignar cualquier flujo este arco se ver´ıa como: 0 1 5 O Si por ejemplo, hacemos pasar un flujo de 1 a trav´es del arco O → 1, entonces en la red residual se ver´ıa el arco: 1 1 4 O Una vez que le asignemos un flujo al arco, se cambia de un arco dirigido a uno no dirigido. Para los dem´as flujos que queramos hacer pasar por un arco debemos sumar
´ A LA ADMINISTRACION ´ DE PROYECTOS10 CAP´ITULO 1. INTRODUCCION los flujos en la direcci´on del arco original y restar los flujos que vayan en la direcci´on opuesta. Para resolver un problema de flujo m´aximo usamos dos cosas. Una red residual y una (o m´as) trayectorias de aumento. Una red residual se forma a partir de la red original considerando las capacidades de los arcos. La Fig. 1.6 muestra un red residual para la red de la Fig. 1.5. 3
0 1 5
2.5
0
3 4
0
0
O 4
M 2 0 2
0 0
1.5 0
4
3.5
Figura 1.6: Un ejemplo de red residual. Una trayectoria de aumento es una trayectoria del nodo fuente al nodo destino en la red residual, tal que todos los arcos en esa trayectoria tienen capacidad residual estrictamente positiva. En una trayectoria de aumento podemos identificar su capacidad residual como el m´ınimo de las capacidades residuales de los arcos que forman la trayectoria. La capacidad residual de una trayectoria de aumento es la cantidad de flujo que es factible agregar en todos los arcos de la trayectoria. Para resolver un problema de flujo m´aximo podemos emplear el algoritmo de la trayectoria de aumento: 1. Escogemos una trayectoria de aumento en la red residual, del nodo origen al nodo destino. Si no existe tal trayectoria entonces los flujos asignados constituyen un patr´on de flujo ´optimo. 2. Para la trayectoria del paso 1, identificamos su capacidad residual que es el m´ınimo de las capacidades residuales de los arcos que forman la trayectoria. 3. Se disminuye en la cantidad encontrada en el paso 2 la capacidad de cada arco de la trayectoria de aumento. En caso de que el arco tenga direcci´on opuesta
´ A LA ADMINISTRACION ´ DE PROYECTOS11 CAP´ITULO 1. INTRODUCCION se le aumenta la cantidad correspondiente en lugar de disminuirse. Regresamos al paso 1. Ejemplo 3. Hallar el flujo m´aximo para la red de la Fig. 1.5. Soluci´on. Lo primero que necesitamos es construir una red residual que se muestra en la Fig. 1.6. Realicemos el algoritmo del flujo m´aximo. Al inicio, como no hemos asignado ning´ un flujo, la red residual est´a como en la Fig. 1.6. Las iteraciones del algoritmo se muestra en la Fig. fig:iteraciones. Las trayectorias de aumento en cada iteraci´on se muestran con flechas continuas(como →) y las flechas punteadas son arcos que no forman parte de la trayectoria. Existen varias formas de resolver el problema dependiendo de las trayectorias de aumento que se elijan, pero al final el flujo m´aximo es el mismo. Despu´es de realizar las iteraciones necesitamos establecer la capacidad de flujo para cada arco en una red. Esto se muestra en la Fig. 1.8. Por lo tanto, el flujo m´aximo es de 7.5. Ejercicio 2. Los cargamentos de c´ıtricos de Oxcutzcab a M´erida se transportan como sigue: Los c´ıtricos se env´ıan primero a Ticul o a Teabo, luego se dirigen por Tekit o Muna y, finalmente, se env´ıan a M´erida. El n´ umero m´aximo de cargamentos que se pueden enviar al d´ıa entre las poblaciones se muestra en el Cuadro 1.2. 1. Determinar el n´ umero m´aximo de cargamentos de c´ıtricos que pueden enviarse de Oxcutzcab a M´erida en un d´ıa. 2. Cada cargamento que llega a M´erida se vende a $ 40.00. Suponiendo que se venden todos lo cargamentos, ¿Cu´anto dinero recibir´ıa, como m´aximo, al d´ıa? 3. ¿Cu´antos cargamentos de c´ıtricos se pueden transportar, como m´aximo, de Ticul a Muna en un d´ıa? Para hallar el flujo m´aximo del origen al destino en una red usando dos m´etodos: programaci´on lineal o el m´etodo de Ford-Fulkerson. Para plantear un problema de
´ A LA ADMINISTRACION ´ DE PROYECTOS12 CAP´ITULO 1. INTRODUCCION
0
3 1 2 Iteraci´on 1:
M 2
0
0
3
3.5
4
1.5 0
3 1
0
0.5
3
O
M
4
2 0 2
2
0
1.5
4
1.5 0 3
3 0
1
0.5
4
O
M
3
1 1 2
5 1 0
0.5
2 1.5 0
0
3
1.5
4
3 0
1
4 M
1 2.5 2
→6
2
O 1.5
→5
2
5 1 0
→3
0 0
5 1
Iteraci´on 4:
3
O
0 2
Iteraci´on 3:
3 1
0
2.5
4
Iteraci´on 2:
3
→ 7.5
3.5 2 0 1.5
4
0
Figura 1.7: Iteraciones para resolver un problema de flujo m´aximo.
´ A LA ADMINISTRACION ´ DE PROYECTOS13 CAP´ITULO 1. INTRODUCCION 3
1
3 4
5 2 O
M
1 4 2
1.5
3.5 4
Figura 1.8: Red final para un problema de flujo m´aximo. Poblaci´on Oxcutzcab–Ticul Oxcutzcab–Teabo Ticul–Muna Ticul–Tekit Teabo–Muna Teabo–Tekit Muna–M´erida Tekit–M´erida
No. de Cargamentos 50 40 30 25 20 15 40 35
Cuadro 1.2: Datos para el ejercicio 2. flujo m´aximo en t´erminos de un problema de programaci´on lineal debemos considerar lo siguiente: Sea x0 = flujo por el arco ( o los arcos) que va (van) del destino al origen. Maximizamos x0 , sujeto a dos conjuntos de restricciones: 1. El flujo de cada arco debe ser no negativo y no puede exceder la capacidad del arco. 2. Flujo hacia el nodo i = flujo saliente del nodo i (conservaci´on de flujo). Para el m´etodo de Ford-Fulkerson consideramos: I=
conjunto de los arcos en los que se podr´ıa incrementar el flujo
R=
conjunto de los arcos en los que se podr´ıa reducir el flujo,
y realizamos los siguientes pasos: 1. Encontramos un flujo factible. Una forma de lograrlo es establecer como cero el flujo de cada arco.
´ A LA ADMINISTRACION ´ DE PROYECTOS14 CAP´ITULO 1. INTRODUCCION 2. Usando el procedimiento que se describe a continuaci´on, tratamos de encontrar una cadena de arcos y nodos etiquetados que se pueda usar para marcar el destino. Etiquetamos el destino. Luego etiquetamos los dem´as arcos y puntos extremos, seg´ un: a) Si el punto extremo x est´a etiquetado, entonces el punto extremo y no est´a etiquetado y el arco (x, y) es un miembro de I. Luego etiquetamos el punto extremo y y el arco (x, y). Decimos que el arco (x, y) es un arco directo. b) Si el punto extremo y no est´a etiquetado, entonces se etiqueta el punto extremo x y el arco (x, y) es un miembro de R. Luego etiquetamos el punto extremo y y el arco (x, y). Decimos que el arco (x, y) es un arco inverso. Si no se puede etiquetar el nodo destino, el flujo factible actual es un flujo m´aximo, de lo contrario ir al paso 3. 3. Si la cadena usada para etiquetar el destino consiste por completo de arcos directos, se podr´ıa incrementar el flujo por cada uno de los arcos directos de la cadena principal y, por lo tanto, se incrementa el flujo del origen al destino. Si la cadena usada para marcar el destino consta de de arcos directos e inversos, incrementamos el flujo en cada arco directo de la cadena y disminuimos el flujo en cada arco inverso de la cadena. De nuevo se incrementar´a el flujo del origen al destino.
1.2.3.
´ Problema del Arbol de Expansi´ on M´ınima
Este problema comparte algunas caracter´ısticas del problema de la ruta m´as corta. En ambos casos consideramos una red no dirigida y conexa, en la que la informaci´on dada incluye algunas medidas de longitud positiva asociada a cada ligadura. Tambi´en, en ambos casos se selecciona un conjunto de ligaduras tal que la longitud total sea m´ınima y cumpla cierta condici´on. En el caso de la ruta m´as corta la condici´on es que ese conjunto de ligaduras proporcionen una trayectoria del nodo origen al nodo destino. Para el caso del problema del ´arbol de m´ınima expansi´on la
´ A LA ADMINISTRACION ´ DE PROYECTOS15 CAP´ITULO 1. INTRODUCCION condici´on que debe cumplir es que las ligaduras seleccionadas deben proporcionar una trayectoria entre cada par de nodos de la red. Entonces, el problema del ´arbol de expansi´on m´ınima consiste en encontrar un ´arbol de expansi´on cuya longitud total de sus ligaduras sea m´ınima. Observaci´ on 6. Para una red con n nodos se requieren exactamente n − 1 ligaduras para proporcionar una trayectoria entre cada par de nodos. Para resolver el problema del ´arbol de m´ınima expansi´on tenemos el siguiente algoritmo: 1. Se toma de manera arbitraria a cualquier nodo y se pone una ligadura que conecte a este nodo con el m´as cercano. 2. De entre los nodos que no forman parte del ´arbol, se agrega una ligadura entre aquel que sea el m´as cercano a uno de los nodos que ya forman parte del ´arbol. Este paso se repite hasta que se hayan conectado todos los nodos. 3. En caso de empates se pueden romper de manera arbitraria. En ocasiones esto indica que existen varias soluciones al problema. 18
2
9
4 4
4 9
11 1
9
3
6
5
13
6
Figura 1.9: Red para el Ejemplo 4.
Ejemplo 4. Hallar el ´arbol de expansi´on m´ınima para la red de la Fig. 1.9. Soluci´on. Como la red tiene seis nodos se requieren cinco ligaduras para formar el ´arbol. Para aplicar el algoritmo, primero debemos elegir un nodo cualquiera, por ejemplo el nodo 1. En la Fig. 1.10 se muestran las iteraciones del algoritmo. En conclusi´on, el ´arbol de expansi´on m´ınima tiene un longitud de 32.
´ A LA ADMINISTRACION ´ DE PROYECTOS16 CAP´ITULO 1. INTRODUCCION 18
2
9
4
4
1
3 5 Iteraci´on 1 18
2
9
1
6
3 5 Iteraci´on 3 18 9
18 9
6
1
9
4
4 9 6
6
13
3 5 Iteraci´on 4 2
6
4
4
4
9
11
6
4
11 13
13
4
4
3
6
3 5 Iteraci´on 2 2
4
1
1
9
9
2 9
6
4 11
9
9
11 13
4
4
4 4
9 6
9
4
4 11
9
18
2
9 13
5 Iteraci´on 5
6
1
9
3
6
5
6
´ Arbol
Figura 1.10: Iteraciones para resolver el Ejemplo 4. Ejercicio 3. Se pretende dar mantenimiento a algunas de las carreteras que conectan las poblaciones entre M´erida y Temoz´on, seg´ un la Fig. 1. El n´ umero en cada arco es el costo (en miles de pesos) del mantenimiento. Despu´es de realizar los mantenimientos se debe cumplir que: Entre cualquier par de poblaciones, debe existir una trayectoria que conecte dichas poblaciones por medio de caminos a los cuales se les haya dado mantenimiento. Como el presupuesto es limitado, el objetivo es minimizar los costos de mantenimiento. 1. Hallar un ´arbol de expansi´on m´ınima. 2. ¿Cu´ales son las carreteras que se deben elegir para que reciban mantenimiento? 3. ¿Cu´anto costar´ıa (en pesos) dicho mantenimiento?
´ A LA ADMINISTRACION ´ DE PROYECTOS17 CAP´ITULO 1. INTRODUCCION
1.2.4.
Problema del Flujo de Costo M´ınimo
La importancia de este problema en el an´alisis de redes radica en dos aspectos. El primero es que abarca una clase muy amplia de aplicaciones y el segundo es la eficiencia con la pueden resolverse este tipo de problemas ya que se puede formular como un problema de programaci´on lineal. Para resolver este problema podemos usar el m´etodo simplex o bien una variante m´as sencilla llamada m´etodo simplex para redes. El problema de flujo de costo m´ınimo contempla elementos tanto del problema de la ruta m´as corta como del problema de flujo m´aximo. Tomaremos en cuenta un flujo a trav´es de la red con arcos de capacidades limitadas (como en el problema de flujo m´aximo) y consideramos un costo o distancia asociada a cada arco (como en los problemas de la ruta m´as corta). La diferencia de este problema respecto a los anteriores es que se pueden considerar varios nodos origen y varios destino. El problema consiste en una red conexa dirigida en la que los n nodos incluyen al menos un nodo origen y al menos un nodo destino. Las variables de decisi´on son la de forma: xij = flujo a trav´es del arco i → j. La informaci´on que se tiene del planteamiento del problema es: cij =
costo por unidad de flujo a trav´es del arco i → j
uij =
capacidad del arco i → j
bi =
flujo neto generado en el nodo i
El valor de bi depende de la naturaleza del nodo, es decir, bi es positivo cuando es un nodo fuente, bi es negativo cuando es un nodo destino y bi es cero cuando es un nodo de trasbordo. El objetivo, en este caso, es minimizar el costo total de mandar los recursos disponibles a trav´es de la red para satisfacer la demanda dada. La funci´on objetivo, considerando las sumas s´olo sobre los arcos existentes, queda como: Z=
n X n X i=1 j=1
cij xij ,
´ A LA ADMINISTRACION ´ DE PROYECTOS18 CAP´ITULO 1. INTRODUCCION sujeto a:
n X i=1
xij −
n X
xji = bi
para cada nodo i,
i=1
donde la primera suma (de izquierda a derecha) representa el flujo total que sale del nodo i y la segunda, el flujo total que entra al nodo i. Entonces, estas restricciones establecen que el flujo neto generado en cada nodo i debe ser igual a bi . Tambi´en consideramos las restricciones para cada arco i → j que exista en la red: 0 ≤ xij ≤ uij Observaci´ on 7. En algunas aplicaciones, es necesario tener que ajustar al modelo para cumplir con las restricciones de no negatividad. Entonces, cada xij es sustituida por una x0ij = xij − Lij donde Lij es un valor positivo. Observaci´ on 8. Para mantener los problemas balanceados, en ocasiones es necesario a˜ nadir nodos ficticios ya sean de tipo origen o de tipo destino. En cualquier caso, los costos involucrados en los arcos que van hacia (o llegan a) los nodos ficticios se establecen a cero. Observaci´ on 9. Sin necesidad de establecer restricciones enteras de manera expl´ıcita sobre las variables, en los problemas de flujo de costo m´ınimo donde todas las bi y las uij tienen un valor entero, encontraremos soluciones b´asicas factibles (incluyendo la ´optima) donde todas las variables b´asicas tienen tambi´en valores enteros. Para resolver un problema del flujo de costo m´ınimo se recomienda usar el m´etodo simplex para redes ya que nos evita el uso de una tabla simplex dado que toma en cuenta la estructura especial de la red del problema. En esencia, se siguen los mismos pasos que en el m´etodo simplex: encontrar la variable b´asica entrante, determinar la variable b´asica que sale, obtener la nueva soluci´on b´asica factible y detenerse si es la ´optima. Ejercicio 4 (Petr´oleo). Pemex tiene sistemas de producci´on que se pueden agrupar por regiones. La regi´on marina suroeste genera 500,000 barriles por d´ıa y la regi´on sur produce 400,000 barriles por d´ıa. El crudo que se produce en las regiones antes mencionadas se lleva a la refiner´ıa de Tula o a la de Minatitl´ an (suponga que cada
´ A LA ADMINISTRACION ´ DE PROYECTOS19 CAP´ITULO 1. INTRODUCCION refiner´ıa tiene capacidad ilimitada). Refinar 100,000 barriles cuesta $ 7,000.00 en Tula y $ 9,000.00 en Minatitl´an. El petr´oleo refinado se lleva a Chiapas o a Campeche. En Chiapas, se requieren 400,000 barriles por d´ıa y en Campeche 300,000 barriles por d´ıa. Los costos de enviar 100,000 barriles de petr´oleo (crudo o refinado) entre los lugares se muestra en el Cuadro 1.3. De: Regi´on Marina Suroeste Regi´on Sur Tula Minatitl´an
Tula 300 420 – –
A: ($) Minatitl´an Chiapas Campeche 110 – – 100 – – – 450 550 – 470 530
Cuadro 1.3: Datos para el ejercicio 4.
1. Realizar el diagrama de red asociado al problema. Especificar las cij , bj y las capacidades de los arcos. 2. Plantear el problema como uno de programaci´on lineal. Puede resolverlo con ayuda de un programa inform´atico.
1.3.
Introducci´ on a la Ruta Cr´ıtica
La administraci´on de proyectos es una actividad desafiante. Es necesario tener el control sobre cada una de las actividades del proyecto. En la planeaci´on del proyecto deben considerarse muchos detalles en relaci´on a c´omo coordinar las actividades, hacer una programaci´on realista y supervisar en su momento el avance del proyecto. Existen dos m´etodos desarrollados para la administraci´on de proyectos: 1. PERT. T´ecnica de evaluaci´on y revisi´on de programas (en ingl´es, Program Evaluation and Review Technique). 2. CPM. M´etodo de la ruta cr´ıtica (en ingl´es, Critical Path Method). En 1957 se desarroll´o el CPM como un modelo de redes para la administraci´on de proyectos. CPM es un m´etodo determin´ıstico que usa un tiempo fijo estimado para la duraci´on de cada actividad del proyecto. Aunque este m´etodo es simple y f´acil de
´ A LA ADMINISTRACION ´ DE PROYECTOS20 CAP´ITULO 1. INTRODUCCION usar no considera las variaciones de las duraciones de las actividades lo cual puede representar un cambio significativo en el tiempo de terminaci´on del proyecto. PERT es una t´ecnica que contempla la variabilidad de la duraci´on de cada actividad. PERT fue desarrollado a fines de los a˜ nos cincuenta por el proyecto Polaris de la marina estadounidense. Ambas t´ecnicas se apoyan en el uso de redes para ayudar a la planeaci´on de las actividades. Tambi´en, existen programas de computadora dise˜ nados para la aplicaci´on de estas t´ecnicas. Los pasos para planear un proyecto de acuerdo a PERT/CPM son: 1. Identificar las actividades y los eventos que se˜ nalan el inicio o la terminaci´on de las mismas. 2. Determinar la secuencia adecuada para las actividades. 3. Construir la red del proyecto. 4. Estimar el tiempo requerido para realizar cada actividad. 5. Determinar la ruta cr´ıtica. 6. Actualizar la red del proyecto seg´ un el progreso que se tenga. Al utilizar PERT/CPM podemos: 1. Estimar el tiempo de terminaci´on del proyecto. 2. Calcular la probabilidad de terminar el proyecto antes de una fecha espec´ıfica. 3. Identificar las actividades cr´ıticas, es decir, actividades en las cuales se deben evitar retrasos para que la terminaci´on del proyecto no se posponga. 4. Identificar las actividades que cuentan cierta holgura para realizarse sin afectar la terminaci´on a tiempo del proyecto. 5. Obtener las fechas de inicio y de terminaci´on para cada actividad. Las limitantes que presentan PERT/CPM son:
´ A LA ADMINISTRACION ´ DE PROYECTOS21 CAP´ITULO 1. INTRODUCCION 1. La estimaci´on de la duraci´on de las actividades es subjetiva. En ocasiones, las estimaciones no reflejan la realidad. 2. A pesar de que la duraci´on de cada actividad estuviera bien estimada, el modelo supone una distribuci´on beta en estas estimaciones. Otra distribuci´on puede ser la que en realidad presentan los datos. 3. Y a´ un que el suposici´on de la distribuci´on beta fuera v´alida, el m´etodo asume que la distribuci´on de probabilidad del tiempo de terminaci´on del proyecto es la misma que la de la ruta cr´ıtica. Esto no siempre es as´ı pues otras rutas se pueden volver la ruta cr´ıtica en la medida en que sus actividades se retrasen. Observaci´ on 10. Para lidiar con la u ´ltima limitante antes mencionada se emplean simulaciones Monte Carlo para obtener estimaciones m´as realistas para el tiempo de terminaci´on del proyecto. Las reglas para construir un diagrama de proyecto del tipo actividad en el arco (AOA, por sus siglas en ingl´es) son: 1. El nodo 1 representa el inicio del proyecto. Un arco debe de salir desde el nodo 1 para representar cada actividad que no tiene predecesores. 2. Debemos incluir en la red un nodo (llamado nodo de terminaci´on) que representa la conclusi´on del proyecto. 3. Numeramos los nodos de la red de modo que el nodo que representa la terminaci´on de una actividad siempre tenga un n´ umero m´as grande que el nodo que representa el comienzo de una actividad. 4. Una actividad no debe estar representada por m´as de un arco en la red. 5. Dos nodos pueden estar conectados por a lo sumo un arco. Para evitar Observaci´ on 11. Varios esquemas de numeraci´on pueden existir tales que cumplan con la regla 3. Observaci´ on 12. Para evitar violar las relgas 4 y 5, a veces es necesario usar una actividad ficticia con duraci´on cero.
´ A LA ADMINISTRACION ´ DE PROYECTOS22 CAP´ITULO 1. INTRODUCCION Ejercicio 5 (Widgetco [4]). Widgetco est´a a punto de introducir al mercado un producto nuevo, el producto 3. Una unidad del producto 3 se produce al ensamblar una unidad del producto 1 y una unidad del producto 2. Antes que comience la producci´on del producto 1 ´o 2, se debe comprar las materias primas y capacitar a los trabajadores. Antes de poder ensamblar los productos 1 y 2 en el producto 3, es necesario inspeccionar el producto 2 terminado. El Cuadro 1.4, muestra la lista de las actividades y sus predecesores con la duraci´on de cada actividad. Dibujar la red del proyecto. Cuadro 1.4: Datos para el Ejercicio 5. Actividad Predecesores Duraci´on (d´ıas) A = capacitar a los trabajadores – 6 B = comprar materias primas – 9 C = producir el producto 1 A, B 8 D = producir el producto 2 A, B 7 E = probar el producto 2 D 10 F = ensambar los productos 1 y 2 C,E 12
1.4.
M´ etodos para Determinar la Ruta Cr´ıtica
Suponiendo que conocemos la duraci´on de cada actividad, se puede usar el m´etodo de la ruta cr´ıtica (CPM, por sus siglas en ingl´es) para hallar la duraci´on del proyecto. El tiempo de evento inicial para el nodo i, denotado por ET (i), es la fecha m´as pr´oxima en que puede ocurrir el evento que corresponde al nodo i. Para calcular ET (i) realizamos los siguientes pasos: 1. Encontramos cada evento anterior al nodo i que est´e conectado mediante un arco al nodo i. Estos eventos son los predecesores inmediatos de i. 2. Para el ET de cada predecesor inmediato del nodo i, agregamos la duraci´on de la actividad que conecta al predecesor inmediato con el nodo i. 3. ET (i) es igual al m´aximo de las sumas calculadas en el paso 2. El tiempo de evento tard´ıo para el nodo i, denotado por LT (i), es la u ´ ltima fecha en que puede ocurrir el evento que corresponde al nodo i sin retrasar la terminaci´on del proyecto. Para calcular LT (i) realizamos los siguientes pasos:
´ A LA ADMINISTRACION ´ DE PROYECTOS23 CAP´ITULO 1. INTRODUCCION 1. Encontramos cada nodo que ocurre despu´es del nodo i y est´a conectado mediante un arco al nodo i. Estos eventos son los sucesores inmediatos de i. 2. A partir del LT de cada sucesor inmediato del nodo i, restamos la duraci´on de la actividad que conecta al sucesor inmediato con el nodo i. 3. LT (i) es igual al m´ınimo de las diferencias calculadas en el paso 2. Ejercicio 6. Hallar la ruta cr´ıtica para el proyecto del Ejercicio 5. Ejercicio 7. ¿Cu´al es la probabilidad de que el proyecto del Ejercicio 5 se termine en 35 d´ıas?. Considerar las estimaciones del Cuadro 1.5.
Cuadro 1.5: Estimaciones (en Actividad a A 5 B 3 C 2 D 1 E 8 F 9
d´ıas) b 13 10 13 13 12 15
para el Ejercicio 7. m 9 6 8 7 10 12
Ejercicio 8. La red de un proyecto se muestra en la Fig. 1.11. Para cada actividad se dan las estimaciones optimista, pesimista y promedio, seg´ un el Cuadro 1.6. Determinar: 1. La ruta cr´ıtica para la red. Usar duraciones con tiempos medios. 2. La holgura de cada actividad. 3. La probabilidad de que el proyecto se complete en cuarenta d´ıas. 4. El planteamiento de un problema de programaci´on lineal que se pueda usar para hallar la ruta cr´ıtica. Ejercicio 9. Horizon Cable est´a a punto de expandir sus ofertas de TV por cable. Antes de poder dar este servicio, las actividades del Cuadro 1.7 deben completarse.
´ A LA ADMINISTRACION ´ DE PROYECTOS24 CAP´ITULO 1. INTRODUCCION 2
4
7
1
9
3
5
8
6 Figura 1.11: Red del proyecto para el Ejercicio 8.
Cuadro 1.6: Estimaciones (en d´ıas) Actividad a b (1, 2) 4 8 (1, 3) 2 8 (2, 4) 1 7 (3, 4) 6 12 (3, 5) 5 15 (3, 6) 7 18 (4, 7) 5 12 (5, 7) 1 3 (6, 8) 2 6 (7, 9) 10 20 (8, 9) 6 11
para el Ejercicio 8. m 6 4 3 9 10 12 9 2 3 15 9
1. Realiza la red del proyecto. 2. Halla la holgura para cada actividad. 3. Determina la ruta cr´ıtica. 4. Plantea un problema de programaci´on lineal que pueda usarse para hallar la ruta cr´ıtica de este proyecto.
1.5.
Gr´ aficas de Gantt
Una vez terminada planeaci´on del proyecto podemos hacer una gr´afica de Gantt. Henry Gantt desarroll´o una herramienta para visualizar el desarrollo de un proyecto
´ A LA ADMINISTRACION ´ DE PROYECTOS25 CAP´ITULO 1. INTRODUCCION Cuadro 1.7: Datos para el Ejercicio 9. Actividad Predecesores A = elecci´on de las estaciones – B = obtenci´on permiso del ayuntamiento A C = pedido de los equipos para la expansi´on A D = identificaci´on de errores posibles C E = descripci´on de sistemas D F = evaluaci´on de controles internos B,E G = dise˜ no del m´etodo de auditor´ıa F
Duraci´on (d´ıas) 3 6 14 8 4 8 9
en forma de una gr´afica especializada. Inicialmente las gr´aficas de Gantt se usaron para supervisar la construcci´on de barcos. Hoy las usamos colocando barras horizontales como las que se muestran en la Fig. 1.12. Actividad 1 2 3 4
Duraci´on 2 meses 2 meses 2 meses 3 meses
Ene
Feb
Mar
Abr
May
Jun
Jul
Ago
Sep
Figura 1.12: Ejemplo de una gr´afica de Gantt.
En el eje horizontal de la gr´afica de Gantt tenemos una escala de tiempo que se puede expresar en fechas absolutas o en fechas relativas al inicio del proyecto. Dependiendo del proyecto, podemos tener que la unidad de tiempo sea una semana o un mes, que son las m´as comunes. Las barras horizontales indican el inicio y la terminaci´on de cada una de las actividades en el proyecto. Para proyectos m´as complejos, las actividades pueden dividirse en subactividades cada una de las cuales puede estar asociada a una gr´afica de Gantt para permitir la legibilidad global del proyecto. La informaci´on que podemos obtener de una gr´afica de Gantt es com´ unmente: 1. Un marcador vertical que puede indicar el momento presente en el tiempo. 2. El progreso de cada actividad se puede mostrar sombreando la barra conforme al progreso que se tenga. De esta forma, podemos dar un vistazo general del estado que guarda cada actividad.
´ A LA ADMINISTRACION ´ DE PROYECTOS26 CAP´ITULO 1. INTRODUCCION 3. Las dependencias que se indican usando l´ıneas o c´odigos de colores. 4. La asignaci´on de recursos que puede ser especificada para cada actividad. 5. Los puntos en el tiempo donde empiezan y terminan las actividades. La ventaja de las gr´aficas de Gantt es que nos permite visualizar el estado de cada actividad de manera muy general. Com´ unmente se utiliza un software para la generaci´on de las gr´aficas de Gantt por lo que resulta relativamente sencillo elaborarlas. Sin embargo, tambi´en se pueden usar hojas de c´alculo electr´onicas o simple texto para construirlas. Para el an´alisis de las dependencias y la ruta cr´ıtica los modelos de redes como PERT-CPM son m´as robustos para manejar las dependencias y el tiempo de terminaci´on del proyecto. No obstante, las gr´aficas de Gantt se pueden emplear como una herramienta para reportar los resultados obtenidos. Ejercicio 10. Trazar la gr´afica de Gantt para las actividades del Ejercicio 5.
Ejercicios de Repaso Los ejercicios se basan en [1], [3], [4], [5], [6]. Ejercicio 11. Antes de ingresar un producto nuevo al mercado, se deben completar las actividades del Cuadro 1.8. Los tiempos est´an en semanas. 1. Dibujar el diagrama del proyecto. 2. Determinar las trayectorias y las actividades cr´ıticas. 3. Determinar la duraci´on del proyecto y la holgura de cada actividad. 4. ¿Cu´al es el tiempo total requerido (en semanas) para que el producto llegue a las tiendas, si no ocurren retrasos? 5. A m´as tardar, ¿En qu´e semana debe iniciarse el desarrollo de una campa˜ na publicitaria para que no ocurran retrasos? 6. A m´as tardar, ¿En qu´e semana debe terminar el desarrollo de una campa˜ na publicitaria para que no ocurran retrasos?
´ A LA ADMINISTRACION ´ DE PROYECTOS27 CAP´ITULO 1. INTRODUCCION 7. Me interesa que el desarrollo una campa˜ na publicitaria comience lo antes posible, ¿A partir de qu´e semana se podr´ıa comenzar a realizar el desarrollo una campa˜ na publicitaria? 8. Me interesa que el desarrollo una campa˜ na publicitaria termine lo antes posible, ¿A partir de qu´e semana podr´ıa ya haberse terminado el desarrollo una campa˜ na publicitaria? 9. ¿Cu´ales son las actividades en las que se deben evitar retrasos para cumplir con el tiempo establecido en 1? 10. ¿Cu´anto retraso puede tolerarse en el desarrollo de una campa˜ na publicitaria para cumplir con el tiempo establecido en 1? 11. ¿Cu´al es la probabilidad de que el producto llegue a las tiendas en no m´as de 18 semanas despu´es de la fecha de inicio? 12. ¿Cu´al es la probabilidad de que el producto llegue a las tiendas en no m´as de 22 semanas despu´es de la fecha de inicio? 13. La duraci´on de cada actividad se puede reducir hasta por dos semanas al costo siguiente por semana: A, $ 80.00; B, $ 60.00; C, $ 30.00; D, $ 60.00; E, $ 40.00; F , $ 30.00; G, $ 20.00. ¿Cu´anto es lo menos que costar´ıa tener el producto en las tiendas en 18 semanas despu´es de la fecha de inicio? Actividad Predecesores A. Dise˜ nar el producto – B. Estudiar el Mercado – C. Pedir la materia prima A D. Recibir la materia prima C E. Construir el prototipo A,D F. Desarrollar una campa˜ na B publicitaria G. Preparar plan para E la producci´on H. Entregar el producto en G,F las tiendas
6 5 3 2 3
o 2 4 2 1 1
p m 10 6 6 5 4 3 3 2 5 3
7
5
8
7
4
2
6
4
2
0
4
2
Duraci´ on
Cuadro 1.8: Datos para el ejercicio 11.
´ A LA ADMINISTRACION ´ DE PROYECTOS28 CAP´ITULO 1. INTRODUCCION Ejercicio 12 (Una zapater´ıa.). Durante los tres meses siguientes, una zapater´ıa debe satisfacer a tiempo la demanda de: mil pares en el primer mes, mil quinientos en el segundo y mil ochocientos en el tercero. Toma una hora de trabajo producir un par de zapatos. Durante cada uno de los tres meses siguientes, se dispone de cierto n´ umero de horas de trabajo: mil horas de trabajo en el primer mes, mil doscientas en el segundo y otras mil doscientas en el tercero. Cada mes, la zapater´ıa puede a˜ nadir hasta cuatrocientas horas de tiempo extra. En cuanto a los pagos, los trabajadores cobran s´olo las horas que trabajan. En tiempo regular, un trabajador recibe cuatro pesos por hora. En tiempo extra, la paga es de seis pesos por hora. Al final de cada mes se incurre en un gasto de un peso con cincuenta centavos por par de zapatos. 1. Realizar el diagrama de red asociado al problema. Especificar las cij , bj y las capacidades de los arcos. 2. Plantear el problema como uno de programaci´on lineal. Puede resolverlo con ayuda de un programa inform´atico. Ejercicio 13 (Una Facultad.). En la Facultad Log´ıstica hay tres profesoras que ense˜ nan cada una cuatro materias por a˜ no. Cada a˜ no, se abren cuatro grupos de comercio electr´onico, transporte y planeaci´on estrat´egica. Durante cada semestre, se debe abrir por lo menos un grupo de cada materia. La preferencia de horario cada profesora y su preferencia por ense˜ nar las materias se muestran en el Cuadro 1.9. Preferencias Para el semestre sep-ene Para el semestre feb-jul
Dalmira Delta Diana 3 5 4 4 3 4
De impartir comercio electr´onico De impartir transporte De impartir planeaci´on estrat´egica
6 5 4
4 6 5
4 4 6
Cuadro 1.9: Datos para el ejercicio 13. La satisfacci´on total para cada profesora por ense˜ nar determinada materia es la suma de la preferencia semestral y la preferencia de la materia. Por ejemplo, la profesora Dalmira obtiene una satisfacci´on de 3 + 6 = 9 por ense˜ nar comercio electr´onico en el semestre que inicia en septiembre.
´ A LA ADMINISTRACION ´ DE PROYECTOS29 CAP´ITULO 1. INTRODUCCION 1. Realizar el diagrama de red asociado al problema. Especificar las cij , bj y las capacidades de los arcos. 2. Plantear el problema como uno de programaci´on lineal. Puede resolverlo con ayuda de un programa inform´atico. Ejercicio 14 (Una galletera.). Durante los dos meses siguientes, una galletera debe satisfacer a tiempo las demandas para tres tipos de galletas como se muestra en el Cuadro 1.10, en n´ umero de galletas. Mes 1 2
Chispas 50 60
Crema 70 90
Saladas 80 120
Cuadro 1.10: Datos para el ejercicio 14. Hay dos m´aquinas para producir galletas. La m´aquina uno s´ olo puede producir las galletas con chispas y las de crema. La m´aquina dos s´olo puede producir las de crema y las saladas. Cada m´aquina puede usar hasta cuarenta horas por mes. El cuadro 1.11, muestra los tiempos (en horas) y costos asociados a la producci´on y el costo de mantener una unidad de cada producto en el inventario durante un mes. Producto Chispas Crema Saladas
Tiempo de producci´on 30 20 15
Costo de producci´on ($) M´aquina 1 M´aquina 2 40 – 45 60 – 55
Costo de retenci´on ($) 15 10 5
Cuadro 1.11: Datos para el ejercicio 14.
1. Realizar el diagrama de red asociado al problema. Especificar las cij , bj y las capacidades de los arcos. 2. Plantear el problema como uno de programaci´on lineal. Puede resolverlo con ayuda de un programa inform´atico. Ejercicio 15 (Distribuci´on de pulpo). Cada mes, se capturan veinte toneladas de pulpo en Celest´ un. De las cuales, cinco son almacenadas en Progreso y el resto se
´ A LA ADMINISTRACION ´ DE PROYECTOS30 CAP´ITULO 1. INTRODUCCION env´ıa a M´erida. Los costos de transportaci´on y las capacidades de env´ıos entre poblaciones se muestran en el Cuadro 1.12. Traslados Celest´ un–Sisal Celest´ un–Hunucm´a Sisal–Hunucm´a Sisal–Progreso Sisal–M´erida Hunucm´a–Progreso Hunucm´a–M´erida Progreso–M´erida M´erida–Hunucm´a
Costo por tonelada ($) 4 4 2 2 6 1 3 2 1
Capacidad m´axima (en ton) 15 8 ilimitada 4 10 15 5 ilimitada 4
Cuadro 1.12: Datos para el ejercicio 15.
1. Realizar el diagrama de red asociado al problema. Especificar las cij , bj y las capacidades de los arcos. 2. Plantear el problema como uno de programaci´on lineal. Puede resolverlo con ayuda de un programa inform´atico.
Figura 1.13: Soluci´on del Ejercicio 12 usando una hoja electr´onica de c´alculo.
´ A LA ADMINISTRACION ´ DE PROYECTOS31 CAP´ITULO 1. INTRODUCCION
Figura 1.14: Soluci´on del Ejercicio 13 usando una hoja electr´onica de c´alculo.
Figura 1.15: Soluci´on del Ejercicio 14 usando una hoja electr´onica de c´alculo.
´ A LA ADMINISTRACION ´ DE PROYECTOS32 CAP´ITULO 1. INTRODUCCION
Figura 1.16: Soluci´on del Ejercicio 15 usando una hoja electr´onica de c´alculo.
Cap´ıtulo 2 Toma de Decisiones Objetivo Al finalizar la unidad, el alumno o la alumna aplicar´a los conceptos de las cadenas de Markov en la soluci´on de problemas para tomar decisiones ´optimas en condiciones de incertidumbre, de riesgo y de conflicto.
2.1.
Cadenas de Markov
En nuestro curso, usaremos las cadenas finitas de Markov para resolver problemas que involucran la toma de decisiones. Definici´ on 1 (Proceso Markoviano). Est´a formado por un conjunto de objetos y estados tales que: 1. En cualquier momento dado, cada objeto deber´a encontrarse en uno de los estados dados. 2. La probabilidad de que un objeto cambie de un estado a otro (que puede ser el mismo estado) durante un periodo, depende s´olo de estos dos estados. Una cadena finita de Markov es un proceso markoviano donde el n´ umero de estados es finito. Si tenemos N estados (con N entero positivo) y denotamos con pij la probabilidad de cambiar del estado i al j en un periodo, podemos definir una matriz P de N × N cuyos elementos sean las pij . A esta matriz, se le llama matriz estoc´astica o de transici´on asociada al proceso. Necesariamente los elementos de cada rengl´on de P suman uno [7]. 33
CAP´ITULO 2. TOMA DE DECISIONES
34
Gr´aficamente, podemos representar una cadena finita de Markov usando un diagrama de transici´on de estado. Definici´ on 2 (Diagrama de Transici´on de Estado). Es una red dirigida donde los nodos son los estados y los arcos representan posibles transiciones. Ejemplo 5. Los datos del censo dividen a las familias en poblaciones econ´omicamente estables y econ´omicamente inestables. Durante un periodo de diez a˜ nos, la probabilidad de que una familia estable permanezca estable es 0.92, en tanto que la probabilidad de que una familia estable se vuelva inestable es de 0.08. La probabilidad de que una familia inestable se vuelva estable es de 0.03 y la probabilidad de que una familia inestable permanezca inestable es de 0.97. 1. Identificar los elementos de este proceso markoviano. 2. Hallar la matriz estoc´astica asociada. 3. Construir un diagrama de estado de transici´on para este caso. Soluci´on. Este proceso se puede plantear en t´erminos de una cadena finita de Markov: 1. En este proceso los objetos son las familias. Tenemos dos estados, denotemos como 1 la estabilidad econ´omica y con 2 la inestabilidad. 2. La matriz de transici´on queda: 0.92 0.08 . 0.03 0.97 3. En la Fig. 2.1, el n´ umero en cada arco es la probabilidad de la transici´on. 0.92
0.97
0.08 1
2
0.03 Figura 2.1: Diagrama para el proceso del Ejemplo 5. Las potencias de matrices estoc´asticas tambi´en son de inter´es para nuestro curso. (n)
Si denotamos la n-´esima potencia de una matriz estoc´astica P con P (n) = (pij ), (n)
donde sus elementos (pij ) representan la probabilidad de que un objeto cambie de estado despu´es de n periodos.
CAP´ITULO 2. TOMA DE DECISIONES
35
Ejemplo 6. Usando la cadena de Markov definida en el Ejemplo 5, hallar la probabilidad de que una familia permanezca estable econ´omicamente despu´es de dos periodos. Despu´es de 10 a˜ nos Estable
0.92 (a) Estable
0.92
Despu´es de 20 a˜ nos Estable
0.08 Inestable
Estable
0.03 (b) Inestable
0.03
0.92
Estable
Estable
0.97 Inestable
0.03
Estable
Figura 2.2: Diagrama para el proceso del Ejemplo 6.
Soluci´on. Si P = dadas por:
0.92 0.08 , las probabilidades despu´es de dos periodos est´an 0.03 0.97 0.8488 0.1512 . P = 0.0567 0.9433 2
Hay dos formas para que una familia permanezca estable despu´es de 20 a˜ nos. Esto se muestra en la Fig. 2.2 (a), permanece estable en ambos periodos o es vuelve inestable durante los primeros diez a˜ nos y regresa a estable despu´es de 20 a˜ nos. El otro caso, ver Fig. 2.2 (b), cuando es inestable al principio y se vuelve estable durante el primer y segundo periodo, o cuando es inestable por los primeros diez a˜ nos y despu´es se vuelve estable en el segundo periodo. La Fig. 2.2 (a) sirve para calcular el caso cuando una familia estable se mantiene estable despu´es de dos periodos. La probabilidad de que una familia estable siga estable durante un periodo es 0.92, la probabilidad de que permanezca estable por
CAP´ITULO 2. TOMA DE DECISIONES
36
dos periodos es: (0.92)(0.92). La probabilidad de que una familia estable se vuelva inestable durante un periodo es 0.08 y la probabilidad de que una familia inestable se vuelva estable es 0.03, entonces la probabilidad de que ambos eventos sucedan uno despu´es del otro es (0.08)(0.03). De esta forma vemos que para que una familia estable permanezca estable durante dos periodos se alcanza una probabilidad de: (0.92)(0.92) + (0.08)(0.03) = 0.8488, que es el elemento (1, 1) de la matriz P 2 . De la Fig. 2.2 (b), sirve para calcular el caso cuando una familia inestable se vuelve estable despu´es de dos periodos. La probabilidad de que una familia inestable se vuelva estable durante un periodo es 0.03, la probabilidad de que permanezca estable por dos periodos es: (0.03)(0.92). La probabilidad de que una familia inestable siga inestable durante un periodo es 0.97 y la probabilidad de que una familia inestable se vuelva estable es 0.03, entonces la probabilidad de que ambos eventos sucedan uno despu´es del otro es (0.97)(0.03). De esta forma vemos que para que una familia estable permanezca estable durante dos periodos se alcanza una probabilidad de: (0.03)(0.92) + (0.97)(0.03) = 0.0567, que es el elemento (2, 1) de la matriz P 2 . Los otros casos se manejan de manera similar. El elemento (2, 1) de P 2 es la probabilidad de que una familia inestable se vuelva estable despu´es de dos periodos y el elemento (2, 2) de P 2 es la probabilidad de que una familia inestable se mantenga inestable despu´es de dos periodos. Ejercicio 16. Indicar en cada caso el valor de k para que la matriz sea estoc´astica: 1 0 0 0 0.4 0 0.6 0 k 0.12 (b) . (a) 0.2 0 k 0.7 0.15 0.85 0 0 0 1 Ejercicio 17. A partir de la definici´on de matrices, verificar que el producto de dos matrices estoc´asticas del mismo orden es tambi´en estoc´astico. Ejercicio 18. Formular el siguiente proceso como una cadena de Markov:
CAP´ITULO 2. TOMA DE DECISIONES
37
El programa de entrenamiento para los supervisores de producci´on de cierta compa˜ n´ıa contiene dos fases. La fase 1, que incluye tres semanas de trabajo en el aula, va seguida por la fase 2, que consiste en un programa de aprendizaje de tres semanas bajo la direcci´on de los supervisores ya trabajando. De la experiencia pasada, la compa˜ n´ıa espera que 60 % de aquellos que inician el entrenamiento en el aula logren pasar a la fase de aprendizaje, con el restante 40 % que abandona completamente el programa de entrenamiento. De aquellos que pasan a la fase de aprendizaje, 70 % se grad´ uan como supervisores, 10 % deber´a repetir la segunda fase y 20 % queda completamente fuera del programa. 1. Identificar los elementos de este proceso markoviano. 2. Hallar la matriz estoc´astica asociada. 3. Construir un diagrama de estado de transici´on para este caso.
2.2.
Teor´ıa de Juegos
La toma de decisiones bajo condiciones de conflicto, tambi´en es llamada teor´ıa de juegos. Un juego es una situaci´on competitiva entre N personas o grupos, denominados jugadores. Un juego se realiza bajo un conjunto de reglas previamente establecidas con consecuencias conocidas. Las reglas definen las actividades elementales o movimientos del juego. Pueden permitirse diferentes movimientos para los distintos jugadores, pero cada uno de ellos conoce los movimientos de que disponen los otros [7]. Definici´ on 3 (Juego de Suma Cero). Si un jugador gana lo que el otro pierde, al juego se le llama juego de suma cero. Cuando en el juego s´olo participan dos jugadores y adem´as es de suma cero, se dice que es un juego matricial. Esto se debe a que podemos caracterizar el juego usando una matriz (llamada matriz de pagos) como la que se muestra en el Cuadro 2.1, donde gij es la cantidad que el jugador uno le gana al jugador dos cuando el jugador uno realiza su estrategia i y el otro jugador usa su estrategia j. Las Ai son las estrategias puras del jugador uno y Bj , las del jugador dos.
CAP´ITULO 2. TOMA DE DECISIONES
Jugador 1
A1 A2 .. . Am
38
B1 g11 g21
Jugador2 B2 . . . g12 . . . g22 . . . .. .
Bn g1n g2n
gm1
gm2
gmn
...
Cuadro 2.1: Matriz de pagos, G = (gij ), para un juego de dos jugadores de suma cero.
Definici´ on 4 (Estrategia Pura). Es un plan previamente determinado que establece la secuencia de movimientos que un jugador realizar´a durante un juego completo. Cuando los jugadores usan una mezcla de estrategias puras de acuerdo con probabilidades predeterminadas se dice que se usan estrategias mixtas. Ejemplo 7 (Juego de 1-2-3). Dos jugadores muestran simult´aneamente 1, 2 ´o 3 dedos uno al otro. Si la suma de los dedos es par, el jugador dos paga al otro esa cantidad de pesos. Si la suma es impar, el jugador uno tendr´ a que pagar esa cantidad en pesos al jugador dos. Construir la matriz del juego, respecto al jugador uno. (Respuesta: ver el Cuadro 2.2).
Jugador 1
Jugador2 1 2 3 1 2 −3 4 2 −3 4 −5 3 4 −5 6
Cuadro 2.2: Matriz de pagos para el Ejemplo 7.
´ Definici´ on 5 (Soluci´on Optima). Para juegos de suma cero entre dos jugadores, se dice que una soluci´on es ´optima cuando cualquier cambio en las estrategias elegidas por los jugadores no mejora el pago a cualquiera de los jugadores. Definici´ on 6 (Valor del Juego). Es el pago que recibe el jugador uno cuando ambos jugadores juegan de manera ´optima. Si el valor del juego nos da cero, decimos que se trata de un juego justo.
CAP´ITULO 2. TOMA DE DECISIONES
39
Observaci´ on 13. Cualquier juego de suma cero entre dos jugadores tiene un valor del juego. Para resolver un juego de suma cero entre dos jugadores podemos usar los criterios maximin (para el jugador uno) y minimax (para el jugador dos). Esto nos permite asegurar lo mejor de lo peor para cada jugador. Es decir, para el jugador uno debemos obtener el valor m´aximo, m1 , de las ganancias m´ınimas de cada rengl´on de la matriz de pagos. Para el jugador dos debemos tomar el valor m´ınimo, m2 , de las p´erdidas m´aximas de cada columna de la matriz de pagos. Cuando m1 = m2 se dice que el juego es estable y que ambos jugadores usan la soluci´on del punto de equilibrio. En otro caso, se dice que el juego es inestable y no existe punto de equilibrio. Para este tipo de juegos las estrategias puras ya no son ´optimas. Entonces, es necesario usar estrategias mixtas. En resumen: Juegos de suma cero Estable, resolver usando estrategias puras para dos jugadores Inestable, resolver usando estrategias mixtas Observaci´ on 14. Podemos usar el criterio de la dominancia para eliminar alternativas dominadas de modo que se simplifique nuestra matriz de pagos. Para el caso de las estrategias mixtas, definimos: xi = probabilidad de que el jugador uno use la estrategia i (i = 1, 2, . . . , m) yj = probabilidad de que el jugador dos use la estrategia j (j = 1, 2, . . . , n), donde m y n son el n´ umero de estrategias disponibles para el jugador uno y dos respectivamente. De esta manera, el jugador uno establece valores para las xi para definir su plan en el juego. De igual forma, el plan del jugador dos queda determinado al conocer los valores de las yj . Notemos que las probabilidades son no negativas y adem´as cumplen:
m X
= xi = 1 y
i=1
n X
= yj = 1.
j=1
Para el jugador uno el pago esperado es: m X n X i=1 j=1
aij xi yj ,
CAP´ITULO 2. TOMA DE DECISIONES
40
donde las aij son las entradas de la matriz de pagos del juego. Como no se tiene un punto de equilibrio en este tipo de juegos, el criterio maximin (minimax) se puede aplicar para el jugador uno de modo que el valor del juego cumple: a ≤ valor del juego ≤ b, donde a es el valor m´aximo de los pagos esperados m´ınimos y b es el valor m´ınimo de las p´erdidas esperadas m´aximas. Para encontrar la estrategia mixta ´optima se tienen dos m´etodos. Uno gr´afico, que s´olo se puede usar cuando uno de los jugadores tiene exactamente dos estrategias puras (no dominadas), y otro, que es el m´as empleado, que consiste en plantear el juego como un problema de programaci´on lineal. Soluci´on gr´afica por medio del software TORA, ver la Fig. 2.3.
Figura 2.3: Soluci´on gr´afica del Ejercicio .
Ejercicio 19. En un juego de apuestas, el jugador uno tiene una moneda de $ 10 y un vale de $ 20, mientras que el jugador dos tiene una moneda de $ 20 y un vale de $ 30. Simult´aneamente los dos jugadores muestran su moneda o su vale, seg´ un elijan. Si ambos muestran monedas o ambos muestran vales, el jugador uno gana, de otro modo gana el jugador dos. Los pagos se determinan como sigue: si el
CAP´ITULO 2. TOMA DE DECISIONES
41
jugador uno muestra su moneda, los jugadores intercambian la diferencia (en pesos) de las cantidades mostradas por ambos jugadores; si el jugador uno muestra su vale, los jugadores intercambian la suma (en pesos) de las cantidades mostradas por los jugadores. El jugador uno ha notado que puede ganar $ 10 ´o $ 50, o perder $ 20 ´o $ 40 y razona que el juego es justo. ¿Lo es?
Delantero:
D D 0.6 I 1
Portero E I 0.7 1 0.8 0.7
Cuadro 2.3: Datos para el Ejercicio 20.
Ejercicio 20. Consideremos que se va a cobrar un penalti en un partido de f´ utbol. El Cuadro 2.3 lo describe como un juego de suma cero y contiene las probabilidades de anotar un gol. El jugador de los renglones (delantero) tiene dos estrategias: I (disparar a la izquierda) y D (disparar a la derecha). El jugador de las columnas es el portero y tiene tres estrategias: I (se tira a la izquierda), E (espera y luego se tira) y D (se tira a la derecha). El jugador de los renglones est´a interesado en maximizar (y el jugador de las columnas en minimizar) la probabilidad de anotar un gol. ¿Cu´al es la decisi´on ´optima para el delantero? y ¿cu´al es la decisi´on ´optima para el portero?.
2.3.
Toma de Decisiones bajo Condiciones de Incertidumbre
Estrategias:
Mucha Lluvia 1 0 2 0 3 1
Estados de la Naturaleza Lluvia Moderada Lluvia Escasa 0 0 1 0 1 1
Sin Lluvias 5 3 1
Cuadro 2.4: Datos para el Ejercicio 21.
Ejercicio 21. Suponer que se quiere implementar un sistema de riego en el campo. Existen tres estrategias de riego. El Cuadro 2.4 muestra las ganancias (en miles de pesos) al utilizarlas dependiendo de las lluvias.
CAP´ITULO 2. TOMA DE DECISIONES
42
1. ¿Cu´al es la decisi´on ´optima si se usa el criterio de Laplace? 2. ¿Cu´al es la decisi´on ´optima si se usa el criterio de maximin? 3. Construir una tabla de p´erdida de oportunidad. ¿Cu´al es la decisi´on ´optima si se usa el criterio de Savage? 4. ¿Cu´al es la decisi´on ´optima si se usa el criterio de Hurwicz, con α = 0.8? 5. Considerando las probabilidades, ¿Qu´e estrategia se debe seguir? 6. ¿Cu´anto es lo m´aximo que estar´ıa dispuesto a pagar por un estudio m´as detallado sobre las condiciones del clima? Ejercicio 22. Un d´ıa antes de las elecciones, dos candidatos a gobernador consideran las mismas tres ciudades como importantes y merecedoras de una u ´ltima visita. Ya que ninguna visita es u ´til a menos que se haya realizado suficiente trabajo de avance por parte del grupo del candidato, cada candidato deber´a hacer planes antes de saber la elecci´on realizada por su oponente. Los grupos comisionados por ambos lados muestran id´enticas proyecciones. En el Cuadro 2.5, se muestran las ganancias estimadas en miles de votos para cada combinaci´on de visitas del candidato I en este u ´ltimo d´ıa. ¿Qu´e ciudad deber´a elegir cada candidato par la visita?
Candidato I:
Candidato II Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 1 12 −9 14 Ciudad 2 −8 7 12 Ciudad 3 11 −10 10
Cuadro 2.5: Datos para el Ejercicio 22.
2.4.
´ Arboles de Decisi´ on
Los ´arboles de decisi´on son u ´ tiles para determinar decisiones ´optimas en procesos complicados. La t´ecnica consiste en iniciar con los nodos terminales y moverse secuencialmente hacia atr´as a trav´es del ´arbol, calculando las ganancias esperadas
CAP´ITULO 2. TOMA DE DECISIONES
43
en los nodos intermedios. Cada ganancia se escribe encima del nodo correspondiente. Una decisi´on recomendada es aquella que lleva a una ganancia m´axima esperada. Aquellas decisiones que no resultan recomendables tienen las ramas correspondientes marcadas [7]. Ejercicio 23. Una ciudad est´a considerando reemplazar la flota de autos de gasolina propiedad de la municipalidad por autos el´ectricos. El fabricante de estos autos el´ectricos afirma que la ciudad experimentar´a ahorros significativos durante la vida de la flota si efect´ ua el cambio, pero la ciudad tiene dudas. Si el fabricante tiene la raz´on, la ciudad ahorrar´a un mill´on de pesos. Si la nueva tecnolog´ıa falla, como algunos cr´ıticos sugieren, el cambio costar´a a la ciudad $ 450 000. Una tercera posibilidad es que ninguna de las situaciones anteriores ocurra y que la ciudad quede igual con el cambio. De acuerdo con un reporte de consultores, las probabilidades respectivas de estos tres eventos son: 0.25, 0.45 y 0.30. La ciudad podr´ıa utilizar un programa piloto, que de realizarse indicar´ıa el costo potencial o el ahorro por la conversi´on a autos el´ectricos. El programa incluye rentar tres autos el´ectricos durante tres meses y utilizarlos bajo condiciones normales. El costo de este programa piloto para la ciudad ser´ıa de $ 50 000. El consejero de la ciudad considera que los resultados del programa piloto ser´ıan significativos pero no concluyentes. Para apoyar su opini´on muestra el Cuadro 2.6, la cual presenta un resumen de probabilidades basado en la experiencia de otras ciudades. ¿Que decisiones debe tomar la ciudad si quiere maximizar los ahorros esperados?
Si la conversi´on:
Ahorra dinero Da igual Da p´erdida
Un programa piloto indicara Ahorro Sin cambio P´erdida 0.6 0.3 0.1 0.4 0.4 0.2 0.1 0.5 0.4
Cuadro 2.6: Datos para el Ejercicio 23.
Ejercicio 24. La presidenta de una compa˜ n´ıa de una rama industrial altamente competitiva considera que un empleado de la compa˜ n´ıa est´a proporcionando informaci´on confidencial a la competencia. Est´a 90 % segura que este informante es el tesorero de
CAP´ITULO 2. TOMA DE DECISIONES
44
la compa˜ n´ıa, cuyos contactos han sido extremadamente valiosos para obtener financiamiento para la compa˜ n´ıa. Si lo despide y es el informante, la compa˜ n´ıa gana $ 100 000. Si lo despide y no es el informante, la compa˜ n´ıa pierde su experiencia y a´ un tienen un informante en el equipo, con una p´erdida para la compa˜ n´ıa de $ 500 000. Si ella no despide al tesorero, la compa˜ n´ıa pierde $ 30 000, sea o no el informante, ya que en ambos casos el informante contin´ ua en la compa˜ n´ıa. Antes de decidir la suerte del tesorero, la presidenta podr´ıa ordenar pruebas con el detector de mentiras. Para evitar posibles demandas, estas pruebas tendr´ıan que administrarse a todos los empleados de la compa˜ n´ıa con un costo total de $ 30 000. Otro problema es que las pruebas con detector de mentiras no son definitivas. Si una persona est´a mintiendo, la prueba lo revelar´a 90 % de las veces; pero si una persona no est´a mintiendo, la prueba lo indicar´a s´olo 70 % de las veces. ¿Qu´e acciones deber´a tomar la presidenta de la compa˜ n´ıa?
Cap´ıtulo 3 Teor´ıa de Colas o L´ıneas de Espera Objetivo Al finalizar la unidad, el alumno o la alumna describir´a una situaci´on de l´ıneas de espera al proporcionar el modelo matem´atico correspondiente y aplicar´a los modelos elementales y sus resultados b´asicos en la soluci´on de situaciones de colas para la toma de decisiones.
3.1.
Introducci´ on a los Modelos de Colas
Los clientes llegan a un banco, esperan en una fila para obtener un servicio de uno de los cajeros y despu´es salen del banco. Esto es un ejemplo de un sistema o modelo de colas. Si el banco tuviera muchos cajeros los clientes no tendr´ıan que esperar mucho para ser atendidos pero el costo para el banco ser´ıa elevado. Por el contrario, si el banco reduce sus costos demasiado y contrata a pocos cajeros, los clientes podr´ıan tener que esperar demasiado. El objetivo de estudiar la teor´ıa de colas es determinar la manera de operar un sistema de colas de la manera m´as efectiva. Para esto se utilizan modelos matem´aticos que nos permiten hallar un balance adecuado entre el costo del servicio y la cantidad de espera.
3.1.1.
Caracter´ısticas B´ asicas
Veamos algunas definiciones b´asicas relacionadas a las caracter´ısticas de los modelos de colas [5]. Definici´ on 7 (Sistema de Colas). Sistema en el que los productos (o clientes) llegan
45
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
46
a una estaci´on, esperan en una fila (o cola), obtienen alg´ un tipo de servicio y luego salen del sistema. La estructura b´asica de la mayor´ıa de los sistemas de colas se resume en la Fig 3.1. Sistema de Colas Fuente de Entrada
Clientes
Cola
Mecanismo de Servicio
Clientesatendidos
Figura 3.1: Diagrama para la estructura b´asica de un modelo de colas.
Definici´ on 8 (Fuente de Entrada o Poblaci´on de Clientes). Conjunto de todos los clientes posibles de un sistema de colas. De acuerdo a su tama˜ no (n´ umero de clientes potenciales distintos), la fuente de entrada puede ser: Fuente de Entrada
Finita (limitada) Infinita (ilimitada)
Observaci´ on 15. En la pr´actica, cuando el tama˜ no de la poblaci´on es un n´ umero relativamente grande se considera como una poblaci´on infinita. En los modelos que vamos a estudiar, si no se menciona el tipo de poblaci´on de clientes, se supone impl´ıcitamente una poblaci´on infinita. Esto se debe a que los c´alculos son m´as sencillos para poblaciones infinitas. Definici´ on 9 (Proceso de Llegada). Forma en que los clientes de la poblaci´on llegan a solicitar un servicio. Al tiempo que existe entre dos llegadas consecutivas de clientes a un sistema de colas se le llama: Tiempo entre llegadas. Esta es la caracter´ıstica m´as importante del proceso de llegada de un sistema de colas. Adem´as, se puede especificar alguna distribuci´on de probabilidad con la cual los clientes llegan al sistema a trav´es del tiempo. En general, se supondr´a que los clientes se generan por medio de un proceso de Poisson. Un proceso de Poisson es un proceso aleatorio en el que el tiempo de entre llegadas consecutivas sigue una distribuci´on exponencial.
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA Nombre FCFS (first come, first served) LCFS (last come, first served) SIRO (service in random order) Prioridad
47
Descripci´on Son atendidos en el orden en que van llegando a la cola. El cliente que ha llegado m´as recientemente es el primero en ser atendido. Se escoge a un cliente al azar para ser atendido. A cada cliente se le asigna una prioridad y de acuerdo a ´esta son atendidos.
Cuadro 3.1: Disciplinas de cola m´as comunes.
Lo anterior implica que, el n´ umero de clientes que llegan hasta un tiempo espec´ıfico tiene una distribuci´on de Poisson. Recordemos que una distribuci´on de Poisson describe la probabilidad de que se presente un n´ umero dado de llegadas en un intervalo dado de tiempo, cuando el tiempo entre llegadas sigue una distribuci´on exponencial. Definici´ on 10 (Proceso de Colas). La forma en que los clientes esperan a que se les d´e un servicio. La cola es donde los clientes esperan antes de ser servidos y de acuerdo a su capacidad (n´ umero de clientes que pueden esperar para ser atendidos) puede ser: Finita (limitada) Cola Infinita (ilimitada) Observaci´ on 16. En los modelos que vamos a estudiar, si no se menciona la capacidad de la cola, se supone impl´ıcitamente de capacidad infinita. Si el sistema cuenta con una sola cola se dice que es un sistema de colas de una l´ınea. Tambi´en, existen los sistemas de colas de l´ıneas m´ ultiples, cuando los clientes que llegan pueden elegir una de varias colas en la cual esperan para ser atendidos. Definici´ on 11 (Disciplina de Cola). La forma en que los clientes son elegidos para proporcionarles un servicio. Algunas de las disciplinas de cola m´as comunes se resumen en el Cuadro 3.1 [4]. Observaci´ on 17. En los modelos que vamos a estudiar, la disciplina de cola primero en entrar primero en salir (FCFS, del Cuadro 3.1) es la suposici´on est´andar.
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
48
Definici´ on 12 (Proceso de Servicio o de Salida). Forma y rapidez con que son atendidos los clientes. Para atender a los clientes se dispone de una o m´as estaciones de servicio. Cuando los clientes que llegan pasan por s´olo una estaci´on de trabajo se dice que el sistema de colas es de canal sencillo. Cuando los clientes deben pasar por varias estaciones de servicio lo pueden hacer en serie o en paralelo. Las estaciones est´an en serie cuando el cliente recibe el servicio de una secuencia de ellas. Las estaciones est´an en paralelo cuando todas las estaciones ofrecen el mismo tipo de servicio y el cliente s´olo debe pasar por una de ellas. Algunos sistemas pueden tener algunas de sus estaciones en serie y otras en paralelo. En cada estaci´on del sistema de colas podemos tener uno o m´as servidores, los cuales pueden ser: Servidores
Id´enticos No id´enticos
Si todos los servidores realizan el mismo tipo de servicio con la misma rapidez se consideran id´enticos. Supongamos que un cliente es atendido en una estaci´on. El tiempo que transcurre desde el inicio del servicio hasta su terminaci´on, se conoce como tiempo de servicio ´ o duraci´on del servicio. Este puede ser: Tiempo de Servicio o Duraci´on del servicio
Determin´ıstico Probabil´ıstico
El caso determin´ıstico es cuando el servicio a cada cliente dura lo mismo. En el otro caso, cada cliente puede requerir una cantidad distinta e incierta de tiempo para se atendido. Los tiempos de servicio probabil´ısticos se describen mediante una distribuci´on de probabilidad. Por lo general, se usa la distribuci´on exponencial. Tambi´en, existen otras distribuciones que se pueden emplear como la de Erlang [4].
3.1.2.
Clasificaci´ on de los Modelos de Colas
Para representar los sistemas de colas o l´ıneas de espera se dise˜ no una notaci´on de seis elementos [8]: 1/2/3/4/5/6
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
49
que tienen que ver con: 1. El tipo de proceso de llegada. Se suponen tiempos entre llegadas independientes e id´enticamente distribuidos con distribuci´on: Abreviatura M D Ek G
Distribuci´on (Markoviana) exponencial. (Determin´ıstica) degenerada. Erlnag con par´ametro de forma k General
2. La naturaleza de los tiempos de servicio. Se suponen tiempos de servicio independientes e id´enticamente distribuidos con distribuci´on: Abreviatura M D Ek G
Distribuci´on (Markoviana) exponencial. (Determin´ıstica) degenerada. Erlnag con par´ametro de forma k General
3. La cantidad de servidores en paralelo. 4. La disciplina de la cola, con las siguientes abreviaturas: Abreviatura F CF S LCF S SIRO GD
Distribuci´on Primero en llegar, primero en salir. ´ Ultimo en llegar, primero en salir. Servicio en orden aleatorio. Disciplina general.
5. El n´ umero m´aximo admisible de clientes en el sistema (incluyendo a los que est´an esperando y los que est´an siendo atendidos). Para esta caracter´ıstica se puede usar un n´ umero entero o el s´ımbolo ∞. 6. El tama˜ no de la poblaci´on de clientes. Para esta caracter´ıstica se puede usar un n´ umero entero o el s´ımbolo ∞. Por ejemplo, al usar esta notaci´on podemos escribir M/M/1/F CF S/6/∞ que representa un sistema de colas con tiempos de llegada y de servicio exponenciales, con un servidor, con una disciplina de cola de el primero en entrar, primero en salir, una capacidad para seis clientes y una poblaci´on ilimitada de clientes.
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
50
Observaci´ on 18. Cuando los u ´ltimos tres elementos son F CF S/∞/∞ se suelen omitir. Por lo que M/M/2/F CF S/∞/∞ se escribe como M/M/2. Ejemplo 8. Identifica a los clientes, a los servidores y dem´as caracter´ısticas evidentes del sistema de l´ıneas de espera para: 1. Un establecimiento autom´atico de lavado de coches, en una sola fila. 2. El departamento de facturaci´on de un gran almac´en. Soluci´on. Para cada caso tenemos: 1. Los clientes son los coches que entran al establecimiento a fin de ser lavados. Un servidor es el aparato que realiza la limpieza y la fila u ´ nica indica la existencia de uno o m´as servidores en serie. Por lo general, los servicios de lavado funcionan de modo que el primero en entrar es el primero en ser atendido; as´ı que la disciplina de la cola es FIFO. La capacidad del sistema es el n´ umero de autom´oviles que pueden maniobrarse con seguridad dentro del lugar de lavado. Si se permite que hayan coches en la calle esperando turno para entrar, entonces la capacidad del sistema es infinita. 2. Los clientes son los cargos que hacen quienes realizan compras en el almac´en despu´es de que estos cargos se reciben en el departamento de facturaci´on, pero antes de que se terminen de procesar. Los servidores son las personas del departamento de facturaci´on que se encargan de realizar el proceso. El proceso de facturaci´on sigue com´ unmente una disciplina de cola tipo LIFO, ya que el u ´ ltimo cargo recibido por el departamento de facturaci´on se coloca encima de las hojas pendientes de procesar y es entonces el primer cargo que el servidor procesa cuando se desocupa. En general, no hay l´ımite para el n´ umero de cargos que puedan turnarse al departamento de facturaci´on; entonces la capacidad del sistema es infinita.
Ejercicio 25. Identificar a los clientes, a los servidores y a las caracter´ısticas evidentes de los sistemas de l´ıneas de espera siguientes:
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
51
1. Una cafeter´ıa de una sola barra. 2. Una peluquer´ıa con dos peluqueros, cuatro sillas de espera y una orden local de seguridad que limita a siete el n´ umero m´aximo de clientes en el local. 3. Una estaci´on gasolinera de autoservicio de tres bombas. 4. Aeroplanos que solicitan permiso para aterrizar en un peque˜ no aeropuerto. 5. Autom´ oviles en un estacionamiento de cuota. 6. Un juez municipal que atiende casos civiles en la corte. Ejemplo 9. Cada tres minutos llega un nuevo televisor, que es tomado por un ingeniero de control de calidad siguiendo un orden del tipo primero en entrar, primero en atenderse. Hay solamente un ingeniero a cargo del proceso y le toma exactamente 4 minutos el inspeccionar cada nuevo televisor. Si no hay televisores al inicio de un turno, determinar el n´ umero promedio de televisores en espera de ser inspeccionados durante la primera media hora del turno. Soluci´on. Este es un sistema D/D/1 donde los televisores son los clientes y el ingeniero es el u ´ nico servidor. El tiempo entre llegadas es exactamente tres minutos y el tiempo de servicio es exactamente de cuatro minutos. Necesitamos simular el sistema para obtener el historial de la primera media hora de operaci´on. Contamos cu´antos clientes esperan en la cola en cada uno de los 30 minutos. Los resultados son: 9 veces la cola estuvo vac´ıa, 12 veces la cola ten´ıa a un cliente y 9 veces hab´ıan dos clientes en la cola. Por lo anterior, la longitud promedio de la cola es: 0(9) + 1(12) + 2(9) = 1 televisor. 30 Ejemplo 10. A un dep´osito central llegan autobuses para su limpieza en grupos de cinco cada hora, a la hora en punto. Se le da servicio a los autobuses aleatoriamente de uno en uno. Toma once minutos el dar servicio completo a un autob´ us y ´estos abandonan el dep´osito en cuanto est´an limpios. Determinar:
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
52
1. El n´ umero promedio de autobuses en el dep´osito. 2. El n´ umero promedio de autobuses en espera de limpieza. 3. El tiempo promedio que un autob´ us permanece en el sistema. Soluci´on. Se trata de un sistema determin´ıstico, con los autobuses como clientes y el equipo de limpieza como u ´ nico servidor. Las llegadas se presentan una vez por hora, pero en grupos; el tiempo de servicio es de once minutos. Un autob´ us est´a en servicio mientras lo est´an limpiando. Ya que el sistema se renueva cada hora las estad´ısticas que lo caracterizan la primera hora, tambi´en son v´alidas a largo plazo. 1. Hay cinco clientes en la instalaci´on del momento cero al once, cuatro clientes del once al veintid´os, tres clientes del veintid´os al treinta y tres, dos clientes de treinta y tres a cuarenta y cuatro, y un cliente de cuarenta y cuatro a cincuenta y cinco. Cada intervalo es de once minutos. En los u ´ ltimos cinco minutos no hay clientes en la instalaci´on. Entonces, el promedio de clientes en la instalaci´on es: 5(11) + 4(11) + 3(11) + 2(11) + 1(11) + 0(5) = 2.75 autobuses. 60 2. El n´ umero promedio de clientes en la linea de espera, es decir, aquellos autobuses en espera, pero que a´ un no est´an en servicio, es: 4(11) + 3(11) + 2(11) + 1(11) + 0(16) = 1.83 autobuses. 60 3. Un autob´ us permanece en el sistema durante once minutos, ya que se le proporciona el servicio en cuanto llega. El segundo autob´ us espera once minutos antes de recibir servicio, as´ı que permanece en el sistema durante 22 minutos. Por lo tanto el tiempo promedio que un autob´ us permanece en el sistema es: 11 + 22 + 33 + 44 + 55) = 33 min. 5 Ejercicio 26. Si los clientes llegan cada 4 minutos para un servicio que dura 8 minutos y el primer cliente llega cuando las instalaciones de servicio abren, ¿a cu´antos clientes se les niega la entrada a un sistema de l´ıneas de espera D/D/1/3 durante la primera hora?
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
53
Ejercicio 27. Los trabajos llegan a un centro, cada 15 minutos, de tres en tres. El centro dispone de un empleado que tarda exactamente 6 minutos en concluir cada trabajo. Los trabajos que el empleado no est´a procesando, se almacenan en el centro y luego se toman aleatoriamente. Suponer que los trabajos empiezan a llegar cuando el empleado se presenta a trabajar y que no hay trabajos pendientes del turno anterior. ¿Cu´al es el n´ umero promedio de trabajos en el centro durante las primeras 2 horas de ese turno?. ¿De qu´e longitud ser´a la cola despu´es de un turno de ocho horas? Ejercicio 28. Para cierta prueba, se han citado en una cl´ınica cada cinco minutos a los pacientes, empezando a las 9 : 00 a.m. La prueba dura exactamente ocho minutos y normalmente la realiza un solo m´edico contratado para ese fin. Siempre que llegan a juntarse tres o m´as pacientes en la sala de espera, un segundo m´edico de la cl´ınica tambi´en realiza la prueba y contin´ ua haci´endola hasta que la sala est´a vac´ıa cuando ´el concluye una prueba. En ese momento, el segundo m´edico reanuda sus actividades anteriores hasta que se necesite de nuevo su intervenci´on. ¿En qu´e momento empieza el segundo m´edico a realizar pruebas y cu´ando se detiene por primera vez?. ¿Cu´al es el promedio de pacientes en la sala de espera de las 9 : 00 a.m. a las 10 : 00 a.m.?. ¿Cu´al es el n´ umero promedio de pacientes en la cl´ınica, de las 9 : 00 a.m. a las 10 : 00 a.m.?
3.1.3.
Medidas de Rendimiento
Decimos que un sistema de colas se encuentra en su fase transitoria cuando apenas inicia su operaci´on y se encuentra afectado por el estado inicial y el tiempo que ha transcurrido desde el inicio de su operaci´on. Despu´es de cierto tiempo, el sistema se vuelve independiente del estado inicial y del tiempo que haya transcurrido y se puede decir (salvo circunstancias no usuales) que ha alcanzado su estado estable. Podemos usar medidas de rendimiento para responder las siguientes preguntas [5]: 1. En relaci´on con el tiempo, desde el punto de vista del cliente: a) ¿Cuanto tiempo, en promedio, debe esperar en la cola un cliente reci´en llegado antes de ser atendido? El tiempo promedio de espera, denotado por Wq .
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
54
b) ¿Cuanto tiempo, en promedio, pasa un cliente en el sistema incluyendo el tiempo de espera y el de servicio? El tiempo promedio en el sistema, denotado por W . 2. En relaci´on al n´ umero de clientes: a) ¿Cu´antos clientes, en promedio, est´an esperando en la cola para ser atendidos? La longitud media de la cola, denotada por Lq . b) ¿Cu´antos clientes, en promedio, hay en el sistema? El n´ umero medio en el sistema, denotado por L. 3. En relaci´on a las probabilidades tanto para clientes como para servidores: a) ¿Cu´al es la probabilidad de que un cliente reci´en llegado tenga que esperar para ser atendido? Probabilidad de bloqueo, denotada por Pw . b) En cualquier momento en particular, ¿Cu´al es la probabilidad de que un servidor est´e ocupado? La utilizaci´on, denotada por U, que tambi´en nos indica la fracci´on de tiempo que un servidor est´a ocupado. c) ¿Cu´al es la probabilidad de que existan n clientes en el sistema? Probabilidad de estado, denotada por Pn . Como n = 0, 1, 2, . . . entonces Pn es una distribuci´on de probabilidad. d ) Si el espacio de espera es limitado, ¿Cu´al es la probabilidad de que la cola est´e llena y el cliente que llegue no sea atendido? La probabilidad de negaci´on de servicio, denotada por Pd .
3.1.4.
Papel de la Funci´ on Exponencial
Recordemos que una variable aleatoria, X, con distribuci´on exponencial con par´ametro α tiene una funci´on de densidad: ( αe−αt fX (t) = 0
si t ≥ 0 si t < 0
Las probabilidades acumuladas son: P (X ≤ t) = 1 − eαt
P (X > t) = eαt
t ≥ 0.
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
55
El valor esperado de X, E(X), y la varianza de X, var(X) son: E(X) =
1 α
y var(X) =
1 . α2
La distribuci´on de probabilidad m´as importante en la teor´ıa de colas es la exponencial. Esto se debe a sus propiedades: Propiedad 1 Su funci´on de densidad es estrictamente decreciente (t > 0). Esto implica que: P (0 ≤ X ≤ ∆t) > P (t ≤ X ≤ t + ∆t). Propiedad 2 Carencia de memoria, es decir, para cualesquiera t y ∆t positivas: P (X > t + ∆t|X > ∆t) = P (X > t). Propiedad 3 El m´ınimo de varias variables aleatorias exponenciales independientes tiene una distribuci´on exponencial. Propiedad 4 El n´ umero de ocurrencias de una variable exponencial en un intervalo de tiempo dado se distribuye con una distribuci´on de Poisson. Se puede demostrar [9], que la distribuci´on exponencial es la u ´ nica variable aleatoria continua con la propiedad de carencia de memoria.
3.2.
Proceso de Colas Basado en el Proceso de Nacimiento y Muerte
Para los modelos elementales de colas, generalmente se considera que la forma en que los clientes llegan al sistema y luego salen del mismo sigue un proceso de nacimiento y muerte [4]. En t´erminos de la teor´ıa de colas, el nacimiento se refiere a la llegada de un cliente al sistema y la muerte, a su salida del sistema de colas. Definici´ on 13. Un proceso de nacimiento y muerte es un proceso estoc´astico de tiempo continuo tal que el estado del sistema, en cualquier momento, es un entero no negativo.
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
56
El estado del sistema en el tiempo t (t ≥ 0), denotado por N(t), es el n´ umero de clientes en el sistema de colas en el tiempo t. El proceso de nacimiento y muerte sirve para describir en t´erminos probabil´ısticos c´omo cambia N(t) al aumentar t. El funcionamiento de un proceso de nacimiento y muerte supone que los nacimientos y muertes individuales son aleatorios y sus tasas medias de ocurrencia dependen del estado actual del sistema. Esto es precisamente lo que se establece en el siguiente teorema: Teorema 1 (Leyes del movimiento para los procesos de nacimiento y muerte). Si el estado del sistema es j en el tiempo t, (N(t) = j), entonces: Ley 1 El tiempo que falta para el pr´oximo nacimiento es una variable aleatoria tiene distribuci´on exponencial con par´ametro λn , para el estado N(t) = n, para n = 0, 1, 2, . . . . Ley 2 El tiempo que falta para la pr´oxima muerte es una variable aleatoria que tiene distribuci´on exponencial con par´ametro µn , para el estado N(t) = n, para n = 0, 1, 2, . . . . Ley 3 Los nacimientos y las muertes son mutuamente independientes; es decir, las dos variables aleatorias son mutuamente independientes. Observaci´ on 19. El sistema cambia de estado con un s´olo nacimiento o con s´olo una muerte a la vez. De modo que si N(t) = n, puede cambiar a N(t + ∆t) = n + 1 ´o a N(t + ∆t) = n − 1, dependiendo de cual de las dos variables aleatorias (la de la ley uno y la de la ley dos) es m´as peque˜ na. Observaci´ on 20. µ0 = 0 para evitar estados negativos. El funcionamiento del sistema se puede resumir en la Fig. 3.2. λ0 0
1 µ1
λn−1
λ1 2 µ2
λn n + 1 ...
n
... n− 1 µn
µn+1
Figura 3.2: Diagrama para el proceso de nacimiento y muerte con tasas medias λn y µn .
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
57
Ahora, veamos unos resultados importantes en la teor´ıa de colas para hallar la soluci´on de las ecuaciones de balance en un proceso de nacimiento y muerte. Definici´ on 14. Para cualquier estado n del sistema, sean: En (t) = veces que el proceso entra al estado n del tiempo 0 hasta el tiempo t Ln (t) = veces que el proceso sale del estado n del tiempo 0 hasta el tiempo t La tasa media para cada evento se define como el n´ umero esperado de eventos por unidad de tiempo, es decir: En (t) = tasa media a la que el proceso entra al estado n t→∞ t Ln (t) = tasa media a la que el proceso sale del estado n l´ım t→∞ t l´ım
Teorema 2 (Ecuaci´on de Balance para el estado n). Para cualquier estado n (n = 0, 1, 2, . . . ) del sistema: La tasa media de entrada es igual a la tasa media de salida. Las ecuaciones de balance para los primeros n estados son: Estado 0 1 2 .. .
Ecuaci´on de Balance µ 1 P1 = λ0 P0 λ0 P0 + µ2 P2 = (λ1 + µ1 )P1 λ1 P1 + µ3 P3 = (λ2 + µ2 )P2 .. .
n−1 n
λn−2 Pn−2 + µn Pn = (λn−1 + µn−1 )Pn−1 λn−1 Pn−1 + µn+1 Pn+1 = (λn + µn )Pn
Despu´es de plantear las ecuaciones de balance para todos los estados en t´erminos de las probabilidades desconocidas Pn , se puede resolver el sistema de ecuaciones para encontrarlas a˜ nadiendo la restricci´on de que todas las probabilidades deben sumar uno. De este procedimiento, se obtienen: λ0 P µ1 0 λ1 P µ2 1 λ2 P µ3 2
Estado 0: Estado 1: Estado 2: .. .
P1 = P2 = P2 = .. .
Estado n − 1: Estado n:
Pn = λµn−1 Pn−1 + n λn Pn+1 = µn+1 Pn +
+ +
1 (µ1 P1 µ2 1 (µ2 P2 µ3
− λ0 P0 ) = − λ1 P1 ) =
1 (µn−1 Pn−1 µn 1 (µn Pn − µn+1
λ1 P µ2 1 λ2 P µ3 2
− λn−2 Pn−2 ) = λµn−1 Pn−1 n λn λn−1 Pn−1 ) = µn+1 Pn
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA Si definimos: Cn =
(
1
58
si n = 0 si n = 1, 2, . . .
λn−1 λn−2 ...λ0 µn µn−1 ...µ1
los resultados anteriores se resumen a: Pn = Cn P0 . Adem´as, se debe cumplir que:
P∞
n=0
∞ X
Pn = 1, entonces: !
Cn P0 = 1,
n=0
despejando: 1 P0 = P ∞
n=0 Cn
.
Las medidas de rendimiento del sistema se pueden calcular conociendo las probabilidades Pn : L=
∞ X n=0
nPn
Lq =
∞ X
Pn
n=0
L W = ¯ λ
Lq Wq = ¯ , λ
¯ es la tasa de llegadas promedio a la larga, y se calcula como: donde λ ¯= λ
∞ X
λn Pn .
n=0
Observaci´ on 21. Los resultados anteriores son v´alidos cuando el sistema puede alcanzar la condici´on de estado estable. Ejemplo 11. Un proceso markoviano lineal de nacimiento que se inicia con un elemento, experimenta una tasa de nacimientos promedio por hora de λ = 2. ¿Cu´al es la probabilidad de tener una poblaci´on mayor de tres despu´es de una hora?. ¿Cu´al es el tama˜ no esperado de la poblaci´on en ese momento? Soluci´on. Con λ = 2 y t = 1, tenemos p0 (1) = 0 y: p1 (1) = (1 − e−2 )0 e−2 = 0.135 p2 (1) = (1 − e−2 )1 e−2 = 0.117 p3 (1) = (1 − e−2 )2 e−2 = 0.101
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
59
La probabilidad de tener m´as de tres elementos en la poblaci´on despu´es de una hora es: 1 − (0 + 0.135 + 0.117 + 0.101) = 0.647, el tama˜ no esperado de la poblaci´on es E[N(t)] = N(0)eλt y en ese momento est´a dado por: E[N(1)] = 1e(2)1 = 7.389 elementos.
Ejemplo 12. Un proceso posponiendo de nacimiento que se inicia con un elemento, experimenta una tasa de nacimientos promedio por hora de λ = 2. ¿Cu´al es la probabilidad de tener una poblaci´on mayor de tres despu´es de una hora?. ¿Cu´al es el tama˜ no esperado de la poblaci´on en ese momento? Soluci´on. Con N(0) = 1, λ = 2 y t = 1, tenemos p0 (1) = 0 y: p1 (1) =
20 −2 e 0!
= 0.135
p2 (1) =
21 −2 e 1!
= 0.271
p3 (1) =
22 −2 e 2!
= 0.271
La probabilidad de tener m´as de tres elementos en la poblaci´on despu´es de una hora es: 1 − (0 + 0.135 + 0.271 + 0.271) = 0.323, el tama˜ no esperado de la poblaci´on es N(0) + λt, entonces: E[N(1)] = 1 + 2(1) = 3 elementos.
Ejemplo 13. Un bi´ologo observa el crecimiento de cepas de bacterias en un cultivo y encuentra que, tanto las probabilidades de nacimiento como de muerte de una cepa, son proporcionales al n´ umero de cepas en el cultivo y al tiempo transcurrido. En promedio, cada cepa produce una nueva cepa cada siete horas y muere despu´es de 30 horas. ¿Cu´antas cepas puede esperar en un cultivo despu´es de una semana si la poblaci´on inicia con un cultivo? Soluci´on. Tomemos un d´ıa como unidad de tiempo y N(0) = 1. La tasa de nacimientos es: 1 λ = (24) = 3.4285 7
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
60
nacimientos diarios por elemento, y la tasa de mortalidad es: µ=
1 (24) = 0.8 30
muertes diarias por elemento. El tama˜ no esperado de la poblaci´on es: E[N(7)] = 1e(3.4285−0.8)7 = 97953164 elementos.
Ejercicio 29. Una compa˜ n´ıa de autos considera que, en el rango de 40 000 a 300 000 autom´oviles, las ventas de un nuevo modelo siguen un proceso markoviano lineal de nacimiento. Si, en promedio, cada 50 nuevos autom´oviles que est´an en las calles generan diariamente un nuevo comprador, ¿Cu´antos autos u ´ltimo modelo pueden esperar vender 60 d´ıas despu´es de vender el auto n´ umero 40 000? Ejercicio 30. Una tienda de departamentos publica en un diario un anuncio solicitando vendedores. Con base en experiencias previas, la tienda espera que las solicitudes se presenten de acuerdo a una distribuci´on de Poisson con una tasa promedio de dos diarias, mientras se publique el anuncio. ¿Cu´antos d´ıas deber´a publicarse el anuncio si la tienda desea tener 98 % de seguridad de recibir al menos seis solicitudes? Ejercicio 31. Cada lunes por la ma˜ nana, 15 minutos antes de la hora en que un banco local abre, los clientes se forman en la entrada. El patr´on de llegadas aparentemente sigue una distribuci´on de Poisson, con λ = 40 clientes por hora. Determinar la probabilidad de que haya menos de cinco personas en la hora de abrir, considerando que nadie abandona la fila una vez formado.
3.3.
Modelos con Distribuci´ on de Poisson
3.3.1.
Modelo M/M/s
Las caracter´ısticas de un sistema M/M/s son: 1. Una poblaci´on de clientes infinita. 2. Un proceso de llegada en el que los clientes se presentan de acuerdo a un proceso de Poisson con una tasa promedio de λ clientes por unidad de tiempo.
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
61
3. Un proceso de colas que cosiste en una sola fila de espera de capacidad infinita, cuya disciplina es el primero en entrar, primero en salir. 4. Un proceso de servicio que consiste en s servidores id´enticos, cada uno atiende a los clientes de acuerdo con una distribuci´on exponencial, con una cantidad promedio µ de clientes por unidad de tiempo. Observaci´ on 22. Para que un sistema M/M/s alcance una condici´on de estado estable, la tasa total promedio de servicio (sµ), debe ser mayor que la tasa promedio de llegadas (λ). El efecto de tener s servidores en el sistema es un aumento proporcional en la tasa de servicio de nµ si n ≤ s o de sµ si n > s. Por lo cual, las medidas de rendimiento para M/M/s son: 1. Probabilidad de que no haya clientes en el sistema (ρ = λ/µ): P0 = P s−1
ρn n=0 n!
2. N´ umero promedio en la fila:
Lq =
1
+
ρs s!
s . · s−ρ
1 ρs+1 · · P0 . (s − 1)! (s − ρ)2
3. Tiempo promedio de espera en la cola: Wq =
Lq . λ
4. Tiempo promedio de espera en el sistema: W = Wq +
1 . µ
5. N´ umero promedio en el sistema: L = λ · W. 6. Probabilidad de que un cliente que llega tenga que esperar Pw =
1 s s ·ρ · · P0 . s! s−ρ
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
62
7. Probabilidad de que haya n clientes en el sistema (n ≤ s): Pn =
ρn · P0 . n!
8. Probabilidad de que haya n clientes en el sistema (n > s): Pn =
ρn · P0 . s!sn−s
9. Utilizaci´on:
U = 1 − P0 +
s−1 P1 s
+
s−2 P2 s
+···+
1 Ps−1 s
.
Ejercicio 32. El departamento para caballeros de un gran almac´en tiene un sastre para ajustes a la medida. Parece que el n´ umero de clientes que solicitan ajustes sigue una distribuci´on de Poisson, con taza media de llegadas de 24 por hora. Los ajustes se realizan con un orden del tipo FCFS, y los clientes siempre desean esperar, ya que las modificaciones son gratis. Aparentemente, el tiempo que toma realizar el ajuste para un cliente se distribuye exponencialmente, con media de dos minutos. 1. ¿Cu´al es el n´ umero promedio de clientes en la sala de ajustes? 2. ¿Cu´anto tiempo de permanencia en la sala de ajustes deber´ıa planear un cliente? 3. ¿Qu´e porcentaje del tiempo permanece ocioso el sastre? 4. ¿Cu´al es la probabilidad de que un cliente espere los servicios del sastre m´as de diez minutos? 5. ¿Cu´al es la espera promedio que por los servicios del sastre efect´ uan todos los clientes? 6. ¿Cu´al es la espera promedio que por los servicios del sastre realizan s´olo aquellos clientes que deben esperar? Ejercicio 33. Una tienda de manjares delicados es operada por una persona, el propietario. Aparentemente el patr´on de llegadas de clientes durante los s´abados se comporta siguiendo una distribuci´on de Poisson, con una tasa promedio de llegadas
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
63
de diez personas por hora. A los clientes se les atiende siguiendo un orden de tipo FIFO y debido al prestigio de la tienda, una vez que llegan est´an dispuestos a esperar por el servicio. Se estima que el tiempo que toma atender a un cliente, se distribuye exponencialmente, con un tiempo promedio de servicio de cuatro minutos. Determinar: 1. La probabilidad de que haya una l´ınea de espera. 2. La longitud promedio de la l´ınea de espera. 3. El tiempo esperado de permanencia en la l´ınea de espera por cliente. 4. La probabilidad de que un cliente permanezca menos de doce minutos en la tienda. Ejercicio 34. Un vendedor atiende el mostrador en una tienda de helados. Los clientes llegan de acuerdo a un proceso posponiendo, con una tasa media de llegadas de 30 por hora. Se les atiende siguiendo un orden de tipo FCFS, y debido a la calidad del helado, aceptan esperar si es necesario. Aparentemente, el tiempo de servicio por clientes se distribuye exponencialmente, con una media de 1.5 minutos. Determinar: 1. El n´ umero promedio de clientes en espera de servicio. 2. La cantidad de tiempo de espera por el servicio que un cliente deber´ıa estimar. 3. La probabilidad de que un cliente tenga que esperar m´as de quince minutos en la l´ınea de espera. 4. La probabilidad de que el dependiente est´e ocioso.
3.3.2.
Modelo M/M/s/K
Algunas ocasiones, los sistemas de colas tienen una cola finita, es decir, no se permite que el n´ umero de clientes en el sistema exceda un n´ umero especificado (denotado por K), por lo que la capacidad de cola es K − s. Cuando un cliente llega y la cola est´a llena se le niega la entrada al sistema y el cliente nunca entra al sistema. Lo anterior, significa que la tasa media de entrada al sistema se hace cero cuando la cola est´a llena. Entonces para el modelo M/M/s/K, es necesario modificar las
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
64
f´ormulas para calcular las medidas de rendimiento del sistema, tomando en cuenta que en lugar de λn tenemos: ( λ Para n = 0, 1, 2, . . . , K − 1 λn = 0 Para n > K En este caso, se suele a˜ nadir una medida de rendimiento adicional conocida como la probabilidad de negaci´on de servicio, denotada por Pd , que nos indica cu´al es la probabilidad de que un cliente que llegue sea rechazado y se le niegue el servicio porque el ´area de espera est´a llena. Veamos que para M/M/1/K las medidas de rendimiento son: 1. Probabilidad de que no haya clientes en el sistema (ρ = λ/µ): ( 1−ρ Para ρ 6= 1 1−ρk+1 P0 = 1 Para ρ = 1 K+1 2. N´ umero promedio en la fila: Lq = L − (1 − P0 ). 3. Tiempo promedio de espera en la cola: Wq =
Lq λ
donde λ = λ(1 − PK ).
4. Tiempo promedio de espera en el sistema: W = 5. N´ umero promedio en el sistema: ( ρ − 1−ρ L= K 2
L . λ
(K+1)ρk+1 1−ρk+1
Para ρ 6= 1 Para ρ = 1
6. Probabilidad de que haya n clientes en el sistema (n ≤ s): ( (1−ρ)ρn Para ρ 6= 1 k+1 Pn = 1−ρ 1 Para ρ = 1 K+1 En el modelo M/M/s/K, con 1 < s ≤ K, las medidas de rendimiento son:
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
65
1. Probabilidad de que no haya clientes en el sistema (ρ = λ/µ): P0 = P s
1 (λ/µ)n
n=0
n!
+
λ/µs s!
2. N´ umero promedio en la fila: Lq = donde ρ =
λ . sµ
P λ n−s · K n=s+1 sµ
ρ (λ/µ)s K−s K−s P 1 − ρ − (K − s)ρ (1 − ρ) , 0 s! (1 − ρ)2
3. Tiempo promedio de espera en la cola: Wq =
Lq , λ
donde λ = λ(1 − PK ). 4. Tiempo promedio de espera en el sistema: W =
L . λ
5. N´ umero promedio en el sistema: L=
s−1 X
nPn + Lq + s 1 −
n=0
6. Probabilidad de que haya n clientes (λ/µ)n n! n P0 Pn = (λ/µ) P s!sn−s 0 0
s−1 X n=0
Pn
!
.
en el sistema (n ≤ s): Para n = 1, 2, . . . , s Para n = s + 1, . . . , K Para n > K.
Ejemplo 14. (Basado en [7]) Una peque˜ na gasolinera tiene s´olo una bomba para despachar gasolina. Los autos llegan a comparar gasolina siguiendo un proceso posponiendo con una tasa promedio de diez por hora. Aparentemente, el tiempo necesario para dar servicio a un auto se distribuye exponencialmente, con una media de dos minutos. En la gasolinera caben m´aximo cuatro autos y no se permite que los autos se estacionen en la v´ıa p´ ublica. Determinar: 1. El n´ umero promedio de autos que se encuentran al mismo tiempo en la gasolinera.
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
66
2. El tiempo promedio que un cliente debe esperar para obtener servicio, una vez que entra a la estaci´on. 3. La tasa promedio de p´erdida de ingresos por aquellos clientes que no compran en la gasolinera cuando est´a llena, si la venta promedio es de $ 150.00. Soluci´on. Se trata de un sistema M/M/1/4, con µ = 30 clientes por hora, en todos los estados. La tasa promedio de llegadas a la gasolinera es λ = 10 clientes por hora. Entonces, al interior de la gasolinera la tasas promedio de llegadas son en n´ umero de cliente por hora: ( 10 (n = 0, 1, 2, 3) λn 0 (n = 4, 5, . . . ) Como ρ = λ/µ = 1/3 < 1 el sistema puede alcanzar la condici´on estable. 1. En este inciso nos piden: L=
1 5(1/3)5 − = 0.4793 autos. 2 1 − (1/3)5
2. Primero determinamos: (1/3)4 (2/3) p4 = = 0.008264, 1 − (1/3)5 entonces los autos entran a la gasolinera a una tasa de ¯ = 10(1 − 0.008264) = 9.917 clientes por hora. λ Luego, W =
0.4793 = 0.04833, 9.917
con lo que: Wq = 0.04833 −
1 = 0.015 h = 54 seg. 30
3. No se permite la entrada de autos con una tasa de: ¯ = 10 − 9 − 917 = 0.083 clientes por hora. λ−λ As´ı, la tasa media de ganancias perdidas es: (15)(0.083) = $1.25 por hora
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
3.3.3.
67
Variaci´ on de Fuente de Entrada al Modelo M/M/s
Consideremos las mismas condiciones que para el modelo M/M/s pero cuando el tama˜ no de la poblaci´on potencial es finito. Denotamos como N al tama˜ no de la poblaci´on. Bajo estas condiciones, cuando en el sistema tenemos n (con n = 1, 2, . . . , N) clientes quiere decir que existen N − n clientes potenciales restantes en la fuente de entrada. Observaci´ on 23. Los problemas de este modelo siempre alcanzan la condici´on de estado estable. Esto se debe a que λn = 0 para n = N. Tenemos que para s = 1 las medidas de rendimiento son: 1. Probabilidad de que no haya clientes en el sistema (ρ = λ/µ): 1
P0 = P N
N! n=0 (N −n)!
n λ µ
2. N´ umero promedio en la fila:
Lq = N −
λ+µ (1 − P0 ). λ
3. Tiempo promedio de espera en la cola: Wq =
Lq λ
donde λ = λ(N − L).
4. Tiempo promedio de espera en el sistema: W =
L . λ
5. N´ umero promedio en el sistema: L=N−
µ (1 − P0 ) λ
6. Probabilidad de que haya n clientes en el sistema : n λ N! P0 , si n = 1, 2, . . . , N. Pn = (N − n)! µ Veamos que para s > 1, las medidas de rendimiento son:
CAP´ITULO 3. TEOR´IA DE COLAS O L´INEAS DE ESPERA
68
1. Probabilidad de que no haya clientes en el sistema (ρ = λ/µ): h P0 = P s−1 n=0
N! (N −n)!n!
n λ µ
+
2. N´ umero promedio en la fila: Lq =
N X
1 PN
N! n=s (N −n)!s!sn−s
n i λ µ
(n − S)Pn .
n=s
3. Tiempo promedio de espera en la cola: Wq =
Lq λ
donde λ = λ(1 − PK ).
4. Tiempo promedio de espera en el sistema: W =
L . λ
5. N´ umero promedio en el sistema: L=
s−1 X n=0
nPn + Lq + s 1 −
s−1 X n=0
Pn
!
.
6. Probabilidad de que haya n clientes en el sistema (n ≤ s): n N! λ Para 0 ≤ n < s (N −n)!n! µ P0n N! λ Pn = P0 Para s ≤ n ≤ N (N −n)!s!sn−s µ 0 Para n > N.
Cap´ıtulo 4 Secuenciaci´ on Objetivo Al finalizar la unidad, el alumno o la alumna describir´a en qu´e consiste el problema de secuenciaci´on y utilizar´a los modelos de optimizaci´on existentes para encontrar el orden ´optimo de ejecuci´on de un n´ umero determinado de trabajos.
4.1.
Definiciones, notaci´ on y conceptos de secuenciaci´ on.
La secuenciaci´on tiene como objetivo encontrar el orden ´optimo de elaboraci´on de los diferentes procesos requeridos por n trabajos distintos en m m´aquinas. Cada trabajo sirve para elaborar un producto y consta de una serie de procesos. Cada proceso se realiza en una m´aquina determinada. Cuando una m´aquina termina un proceso, puede requerir de ciertos ajustes antes de comenzar a realizar un nuevo proceso. Esto se considera en el llamado tiempo de ajuste de m´aquina. Cuando se trata de problemas de secuenciaci´on simples se pueden emplear algunos m´etodos de optimizaci´on para resolverlos eficientemente. Este es el caso de una, dos o tres m´aquinas. En ocasiones, si aumenta la complejidad del problema de secuenciaci´on se pueden usar m´etodos heur´ısticos (m´as de tres m´aquinas). Sin embargo, cuando el problema es complejo recurrimos a la simulaci´on del sistema y a la intuici´on del personal con experiencia espec´ıfica al problema que queremos resolver. De acuerdo al patr´on de llegada de los trabajos, los problemas de secuenciaci´on
69
´ CAP´ITULO 4. SECUENCIACION
70
se clasifican en: Problema de secuenciaci´on
Est´atico. Din´amico.
Si la producci´on de los n trabajos en m m´aquinas puede ordenarse y realizarse en un s´olo periodo de tiempo se dice que es un problema de secuenciaci´on est´atico. Es din´amico cuando el orden de producci´on y su implantaci´on se realizan a trav´es de varios periodos de tiempo. De acuerdo al n´ umero de m´aquinas, los problemas de secuenciaci´on se clasifican en: Problema de secuenciaci´on
En una m´aquina. En dos o m´as m´aquinas.
De acuerdo al flujo de producci´on, los problemas de secuenciaci´on se clasifican en:
Serie. Aleatorio. Problema de secuenciaci´on Generales.
Se dice que son en serie si se sigue una ruta preestablecida de los procesos, si no existiera dicha ruta se dice que son aleatorios. Si combina flujos en serie y aleatorios se dice que es un problema con flujo de producci´on general. Como hemos visto, los problemas de secuenciaci´on se pueden clasificar de varias maneras. Es por esto, que se propone utilizar una notaci´on de cuatro par´ametros (A/B/C/D), donde: A : Es la llegada de los trabajos. Si es est´atico A es el n´ umero de trabajos. Si es din´amico, A representa la caracter´ıstica de las llegadas (constantes, variables determin´ısticas o variables estoc´asticas). B : Es el n´ umero de M´aquinas. C : Es el tipo de flujo y se representa con una letra: F (Serie), R (aleatorio) y G (general). D : Criterio de optimizaci´on. Esto se describe m´as adelante cuando vemos las medidas de desempe˜ no. Por ejemplo, un problema de secuenciar tres trabajos en serie en dos m´aquinas tal que se minimice el tiempo de flujo m´aximo, se escribe: (3/2/F/Fmax ).
´ CAP´ITULO 4. SECUENCIACION
71
Adem´as de las definiciones b´asicas y la notaci´on anterior es necesario tener en cuenta los siguientes supuestos de los problemas de secuenciaci´on: 1. Cada m´aquina elabora un s´olo proceso a la vez. 2. Se tienen n trabajos independientes, cada uno con una serie de procesos que requieren una relaci´on de precedencia. 3. La descripci´on de cada proceso se conoce con anticipaci´on. 4. Los tiempos de ajuste de m´aquina son independientes de la secuencia de los procesos y se incluyen en los tiempos de proceso. 5. Una vez iniciado un proceso, ´este s´olo se interrumpe hasta su conclusi´on. Cuando se tienen n trabajos y una m´aquina el problema de secuenciaci´on consiste en elegir una secuencia de las n! posibles. Usaremos la notaci´on [k] = q para indicar que el trabajo k se encuentra en el q−´esimo lugar para ser procesado. Por ejemplo, si el cuarto trabajo se har´a primero, escribimos [4] = 1. Mientras que [1] = 4 significa que el trabajo 1 estar´a en el cuarto lugar de la secuencia. Tambi´en, se tiene una notaci´on para cada uno de los elementos del problema de secuenciaci´on. Algunos de ellos se conocen de antemano (representados con min´ usculas) y otros hasta despu´es de la ejecuci´on de los procesos (representados en may´ usculas). Para el caso de n trabajos que constan de un proceso en una m´aquina, usamos: tj : Es el tiempo requerido por el trabajo j. Se incluye el ajuste que se proporciona a la m´aquina previo inicio del proceso. rj : Es el tiempo en el que el trabajo j est´a listo para procesarse. dj : Es el tiempo prometido de entrega, es decir, el tiempo en el que el trabajo deber´ıa entregarse. Cj : Es el tiempo de terminaci´on del trabajo j. Fj : Es el tiempo de flujo del trabajo j. Lj : Es el tiempo de retraso del trabajo j. Tj : Es la impuntualidad del trabajo j.
´ CAP´ITULO 4. SECUENCIACION
4.2.
72
Medidas de Desempe˜ no
En cada uno de los problemas de secuenciaci´on es necesario definir un objetivo que se desee optimizar. De modo que podemos optimizar un problema de acuerdo a una medida de desempe˜ no. Algunas de ellas son: Tiempo total de procesamiento de los trabajos. Retraso promedio de los trabajos Medidas Tiempo promedio de procesamiento de los trabajos de Varianza del tiempo de procesamiento Desempe˜ no Utilizaci´on promedio de las m´aquinas. La impuntialidad de los trabajos.
Definici´ on 15. Para problemas de n trabajos, que constan de un proceso, en una m´aquina las medidas de desempe˜ no se definen como: Flujo del trabajo j: Fj = Cj − rj ,
j = 1, 2, . . . , n.
Retraso del trabajo j: Lj = Cj − dj ,
j = 1, 2, . . . , n.
Impuntualidad del trabajo j: Tj = m´ax{0, Lj }, Flujo promedio: F =
1 n
Impuntualidad promedio: T =
1 n
j = 1, 2, . . . , n.
Pn
j=1 Fj
Pn
j=1 Tj
Flujo m´aximo: Fm´ax = m´ax1≤j≤n {Fj } Impuntualidad m´axima: Tm´ax = m´ax1≤j≤n {Tj } N´ umero de trabajos imputables: Nt = δ(x) =
Pn
j=1
δ(Tj ),
donde:
1 si x > 0. 0 en otro caso.
Observaci´ on 24. Valores negativos de Lj indican eficiencia, pero cuando son positivos muestran ineficiencia. A continuaci´on se describen los algoritmos de secuenciaci´on cl´asicos. Para una revisi´on m´as detallada de los algoritmos de secuenciaci´on consultar los cap´ıtulos 3, 4 y 5 de [10].
´ CAP´ITULO 4. SECUENCIACION
4.3.
73
Secuenciaci´ on en una M´ aquina
Consideremos los problemas (n/1/F/F ), es decir, queremos secuenciar n trabajos (n > 1) en una m´aquina, con flujo aleatorio para conocer el tiempo de flujo promedio. Denotamos como t1 , t2 , . . . , tn los tiempos conocidos de procesamiento de cada uno de los n trabajos y t[k] el tiempo de proceso del trabajo que est´a en la posici´on k. Podemos elegir diversas pol´ıticas de secuenciaci´on, para hallar la secuencia en la que los procesos ser´an realizados. Algunas pol´ıticas suponen que una vez que un trabajo comienza a ser procesado, no se interrumpe hasta que se termina y por eso se les considera del tipo ”no apropiativas´´. Por el contrario, una pol´ıtica es apropiativa cuando se permite que un trabajo que est´a siendo procesado se interrumpa y se reanude tiempo despu´es. El Cuadro 4.1 muestra los datos que se asumen conocidos para un problema de secuenciaci´on en una m´aquina. Cuadro 4.1: Datos de cinco trabajos que ser´an secuanciados en una m´aquina. Trabajos Llegada Duraci´on Prioridad p1 0 4 3 p2 0 3 2 p3 1 1 1 p4 2 6 2 p5 3 2 3
En el Ejemplo 15, se utiliza la pol´ıtica de ”el primero en llegar es el primero en ser atendido´´ conocida como FIFO ´o FCFS por sus siglas en ingl´es (First In, First Out ´o First Come, First Served; respectivamente). Para determinar el orden en que los trabajos ser´an procesados es necesario considerar el momento en el que el trabajo est´a listo para ser procesado. Esto se establece en la columna ”Llegada´´ del Cuadro 4.1. Si hay empates en el tiempo de llegada, ´estos se resuelven de manera arbitraria. En el Ejemplo 16, se utiliza la pol´ıtica de ”turno rotatorio´´ conocida como RR por sus siglas en ingl´es (Round Robin). En esta pol´ıtica, cada trabajo espera su turno para ser atendido. No se permite que un proceso reciba dos turnos consecutivos, a menos que sea el u ´ nico proceso existente. Se define la duraci´on del turno (o quantum) y se denota como q. El valor de q se mantiene constante durante todo el ejercicio.
´ CAP´ITULO 4. SECUENCIACION
74
En el Ejemplo 17, se utiliza la pol´ıtica de ”prioridad´´. Para determinar el orden en que los trabajos ser´an procesados es necesario considerar la prioridad del trabajo. Un n´ umero menor indica es prioritario sobre un n´ umero mayor. Esto se establece en la columna ”Prioridad´´ del Cuadro 4.1. Si hay empates en la prioridad, ´estos se resuelven de manera arbitraria. En el Ejemplo 18, se utiliza la pol´ıtica de ”Tiempo de Procesamiento m´as Corto´´ conocida como SJF por sus siglas en ingl´es (Sortest Job First, trabajo m´as corto primero). Para determinar el orden en que los trabajos ser´an procesados es necesario considerar cu´al es el trabajo con la menor duraci´on. Si hay empates en la duraci´on, ´estos se resuelven de manera arbitraria. Existe tambi´en la versi´on apropiativa del SJF, conocida como ”menor tiempo restante´´. Se abrevia LRT por sus siglas en ingl´es (Least Remaining Time) y se escoge al trabajo que le falte menos para ser terminado. Ejemplo 15. Secuenciar en una m´aquina los trabajos del Cuadro 4.1, utilizando la pol´ıtica FIFO. Soluci´on. En el tiempo cero existen dos trabajos P 1 y P 2. Como llegaron al mismo tiempo entonces podemos iniciar la secuencia con el P 1 o con el P 2. La gr´afica se muestra en la Fig. 4.1, donde notamos que en la parte (a) se inicia la secuencia con P 1 y en la b, con P 2. Despu´es los trabajos son procesados conforme fueron llegando hasta concluir con el u ´ ltimo en 16 unidades de tiempo. Ejemplo 16. Secuenciar en una m´aquina los trabajos del Cuadro 4.1, utilizando la pol´ıtica: 1. Turno rotatorio con turnos de dos unidades de tiempo. 2. Turno rotatorio con turnos de una unidad de tiempo. Soluci´on. En el tiempo cero existen dos procesos, cualquiera de ellos podr´ıa tomar un turno. La gr´afica para un turno de dos unidades se muestra en la Fig. 4.2 en la parte (a). El primer trabajo ser procesado es P 1. Para cuando termina su turno, en el tiempo dos, existen tres trabajos: P 1, P 2, P 3 y P 4. A cualquiera de ellos les puede
´ CAP´ITULO 4. SECUENCIACION
75
Figura 4.1: Alternativas de soluci´on para el Ejemplo 15.
tocar el turno excepto a P 1 que acaba de terminar su turno. Este empate se rompe al azar y en la Fig. 4.2 en la parte (a) vemos que el siguiente proceso con el turno es P 2. Cuando termina su turno, es el tiempo cuatro. En ese momento los cinco trabajos existen. Cualquiera de ellos puede tomar turno excepto P 2 que acaba de terminar su turno. En la Fig. 4.2 en la parte (a), vemos que el siguiente trabajo en ser procesado es el P 3 quien tiene derecho a un turno de dos unidades de tiempo. Como se requiere una unidad de tiempo para terminar el trabajo P 3, estamos listos para asignar el siguiente turno en el tiempo cinco. De los trabajos existentes que pueden obtener el turno se escoge (arbitrariamente) al trabajo P 4 y despu´es de que termina su turno de dos unidades se escoge (tambi´en arbitrariamente) al trabajo P 5. De esta forma podemos continuar asignando el turno a cada uno de los trabajos restantes hasta que en el tiempo doce todos los trabajos se han concluido excepto el trabajo P 4. A partir de ese momento el turno se le asigna siempre al P 4 y se concluye al llegar a las 16 unidades de tiempo. Si el turno tuviera una duraci´on de una unidad de tiempo, la gr´afica est´a en la
´ CAP´ITULO 4. SECUENCIACION
76
Fig. 4.2 en la parte (b). En el tiempo cero podemos escoger al trabajo P 1 ´o al P 2. De la figura, obsevamos que se escoge al P 1 para iniciar la secuencia. Como el turno es de una unidad de tiempo, se debe elegir un nuevo trabajo para ser procesado en cada unidad de tiempo. Esto nos conduce a ir turnando a los procesos en una forma similar a lo que observamos en la Fig. 4.2 en la parte (b). Existen varias maneras de romper los empates, lo cual quiere decir que este ejercicio no tiene una soluci´on u ´ nica tanto para un turno de una unidad de tiempo como para cuando el turno es de dos unidades de tiempo.
Figura 4.2: Alternativas de soluci´on para el Ejemplo 16.
Ejemplo 17. Secuenciar en una m´aquina los trabajos del Cuadro 4.1, utilizando la pol´ıtica: 1. Prioridad, versi´on no apropiativa. 2. Prioridad, versi´on apropiativa.
´ CAP´ITULO 4. SECUENCIACION
77
Soluci´on. La gr´afica se muestra en la Fig. 4.3. Cuando la pol´ıtica es no apropiativa (parte a), de los dos trabajos que existen en el tiempo cero el de mayor prioridad es el trabajo P 2. Cuando este trabajo se concluye, llegamos al tiempo tres. En ese momento, los trabajos que existen son: P 1, P 3 y P 4. Entre ellos el de mayor prioridad es P 3. Al terminar el trabajo P 3, ya est´an listos los trabajos: P 1, P 4 y P 5, de entre los cuales se escoge al P 4 por tener mayor prioridad. Al terminarse este tabajo en el tiempo diez, los dos trabajos que quedan tienen la misma prioridad as´ı que los podemos secuenciar de manera arbitraria. En la Fig. 4.4 parte a, vemos que se dej´o al final el trabajo P 5. Ahora, cuando la pol´ıtica es apropiativa se deben revisar las propiedades cada vez que llega un nuevo trabajo o cada vez que se termina un trabajo. En la Fig. 4.4 parte b, vemos que se inicia con el trabajo P 2. Sin embargo antes de terminar este trabajo llega el P 3 que tiene mayor prioridad que el trabajo que se estaba procesando (P 2) por lo que se interrumpe y se procesa el trabajo P 3. A la siguiente unidad de tiempo, termina el trabajo P 3 y tambi´en llega el trabajo P 4. De modo que hay que decidir cu´al de los trabajos existentes (P 1, P 2 y P 4) se debe procesar. En este caso los trabajos P 2 y P 4 tienen la misma prioridad, por lo que de manera arbitraria escogemos a uno de ellos. Se escoge al P 2. Cuando ´este termina, de nuevo existen tres trabajos pero se escoge al P 4 por tener mayor prioridad. Finalmente, al tiempo diez, cuando el P 4 es terminado, los dos trabajos restantes se pueden secuenciar indistintamente. Por ejemplo, como se muestra en la Fig. 4.4 parte b. Ejemplo 18. Secuenciar en una m´aquina los trabajos del Cuadro 4.1, utilizando la pol´ıtica: 1. Tiempo de procesamiento m´as corto. 2. Menor tiempo restante. Soluci´on. La gr´afica se muestra en la Fig. 4.4. En la parte (a), en el tiempo cero, de los dos trabajos existentes se escoge a P 2 por ser el menor en duraci´on. A pesar de que en el tiempo dos existe el trabajo P 3 que tiene una duraci´on menor, la m´aquina sigue procesando a P 2 hasta su culminaci´on en el tiempo tres. Esto se debe a que
´ CAP´ITULO 4. SECUENCIACION
78
Figura 4.3: Alternativas de soluci´on para el Ejemplo 17.
la pol´ıtica SJF es no apropiativa. En el tiempo tres se procesa al trabajo P 3 por se el que tiene menor duraci´on entre los procesos existentes. En el tiempo cuatro, se han concluido los trabajos P 2 y P 3; entonces sigue el trabajo P 4. Como vemos en la Fig. 4.4, la parte (a), la secuencia es termina con P 1 y P 4 en ese orden. La pol´ıtica de secuenciaci´on LRT se muestra en la Fig. 4.4, parte (b). En el tiempo cero, se elige al P 2 por que le faltan tres unidades de tiempo para terminar que comparado con lo que le falta al otro proceso existente (P 1) resulta ser menor. Sin embargo, en el tiempo uno llega el trabajo P 3 al que le falta una unidad de tiempo para terminarse. Esto ocasiona que la m´aquina deje de procesar al P 2 puesto que le faltan dos unidades de tiempo y tome al trabajo P 3 para realizarlo. De esta forma, al terminar el trabajo P 3 nos encontramos en el tiempo dos. En ese momento, los trabajos existentes son: P 1, P 2 y P 4 que acaba de llegar. Al que le falta menos es al trabajo P 2 que es atendido por la m´aquina una unidad de tiempo hasta que llega un nuevo trabajo. Es el trabajo P 5 que llega en el tiempo tres. En ese momento, existen cuatro trabajos y es necesario investigar a cu´al de ellos le falta menos para
´ CAP´ITULO 4. SECUENCIACION
79
terminar. Como resultado se selecciona al P 2 para ser procesado. Al terminarse este trabajo en el tiempo cuatro, los dem´as trabajos son seleccionados como se muestra en la Fig. 4.4, parte (b). Es decir, ordenados como: P 5, P 1 y P 4.
Figura 4.4: Alternativas de soluci´on para el Ejemplo 18.
De todas las opciones antes presentadas, el siguiente teorema nos indica cual es la mejor para (n/1/F/F ). Teorema 3 (Tiempo de Procesamiento m´as Corto.). Para (n/1/F/F ), el tiempo promedio de flujo F se minimiza con la secuencia: t[1] ≤ t[2] ≤ · · · ≤ t[n] . A esta secuencia se le denomina el tiempo de procesamiento m´ as corto. Del teorema del tiempo de procesamiento m´as corto se deriva el siguiente algoritmo de ordenamiento por inserci´on: 1. Tomar al m´ınimo de los tj y colocarlo en la posici´on 1.
´ CAP´ITULO 4. SECUENCIACION
80
2. De los restantes, tomar al m´ınimo tj y colocarlo en la posici´on 2. 3. As´ı sucesivamente hasta encontrar T[n] . Una variante de este problema es considerar que los trabajos tienen asociada una importancia o prioridad wj . En ese caso, el tiempo de procesamiento m´as corto est´a dado por: t[1] t[2] t[n] ≤ ≤ ··· ≤ . w[1] w[2] w[n] Los ejercicios 35 y 36, basados en [2], nos ayudan a familiarizarnos con la secuenciaci´on en una m´aquina. Ejercicio 35. Con base en los algoritmos de secuenciaci´on vistos, realiza un an´alisis sobre el conjunto de procesos: 1. Del Cuadro 4.2. 2. Del Cuadro 4.3.
Cuadro 4.2: Datos para el Ejercicio 35 parte 1. Proceso Llegada Tiempo de proceso A 0 3 B 1 5 C 3 2 D 9 5 E 12 5
Cuadro 4.3: Datos para el Ejercicio 35 parte 2. Proceso Llegada Tiempo de proceso A 0 1 B 1 9 C 2 1 D 3 9
Ejercicio 36. En un mismo tiempo llegan a un centro de c´alculo cinco trabajos. Tienen tiempos estimados de ejecuci´on 15, 9, 3, 6 y 12 minutos respectivamente. Sus prioridades (definidas desde el exterior) son 6, 3, 7, 9 y 4 respectivamente, donde un
´ CAP´ITULO 4. SECUENCIACION
81
valor menor se corresponde con una prioridad mayor. Determinar el tiempo de flujo para cada trabajo y el flujo promedio para cada uno de los algoritmos indicados. El retardo por cambio de trabajo se considera despresiable. Suponer tambi´en que s´olo un trabajo se ejecuta en cada instante y que todos los trabajos se deben realizar en el mismo centro de c´alculo que contiene s´olo una m´aquina.
4.4.
Secuenciaci´ on en dos M´ aquinas
Ahora con dos m´aquinas, consideremos el problema (n/2/F/Fm´ax ). Cada trabajo requiere de dos procesos secuenciales independientes distintos, realiz´andose el primero en una m´aquina y el siguiente, en la otra. La secuencia de los procesos no se puede alterar. Necesitamos hallar la secuencia de trabajos que minimice el tiempo de flujo m´aximo. El tiempo del proceso j (j = 1, 2), del trabajo i (i = 1, 2, . . . , n), se denota por tij . Para resolver este problema aplicamos el algoritmo de Johnson, reportado en la literatura cl´asica de Investigaci´on de Operaciones [11]: 1. Hacemos k = 1 y p = n. 2. Encontramos el m´ınimo tij . Si ´este tiene j = 1 entonces [i] = k. Es decir, se asigna el lugar k al trabajo i. En otro caso (cuando el m´ınimo se encuentra con j = 2), entonces [i] = p. Es decir, se asigna el lugar p al trabajo i. 3. Se elimina el trabajo i del an´alisis, puesto que ya se le asigno su posici´on en el paso anterior. 4. Con los tij restantes, se repite el procedimiento del paso 2 haciendo k = k + 1 si j = 1, o haciendo p = p − 1 si j = 2. Los empates se resuelven de manera arbitraria. El algoritmo termina en n iteraciones.
4.5.
Extensiones a tres o m´ as M´ aquinas
´ Para tres m´aquinas, el problema que analizaremos es (n/3/F/Fm´ax ). Este se resuelve con el algoritmo de Bifurcaci´on y Acotamiento propuesto por Ignall, Scharge [12] y Lomnichi [13], en 1965.
´ CAP´ITULO 4. SECUENCIACION
82
Se construye un ´arbol de bifurcaciones donde cada nodo representa una soluci´on parcial al problema. Del nodo ra´ız (inicial), se ramifican n nodos, que corresponden a las n posibilidades de asignar uno de los trabajos a la primera posici´on de la secuencia. De cada uno de estos nodos se pueden ramificar n − 1 nodos que corresponden a la segunda posici´on de la secuencia y as´ı sucesivamente. Para no tener que construir el ´arbol completamente se calcula un indicador llamado cota inferior que nos ayudar´a a encontrar la secuencia ´optima sin tener que construir todo el ´arbol. Con la cota inferior, que se calcula para cada uno de los nodos terminales del ´arbol, s´olo se ramifica el nodo que tenga la m´ınima cota inferior. La soluci´on ´optima se obtiene cuando el nodo con la m´ınima cota inferior est´a conectado al nodo ra´ız por medio de una secuencia de n˜ nodos. Para cualquier nodo P su secuencia Jr es un subconjunto de los n trabajos que est´an conectados desde el nodo ra´ız hasta el nodo P , con (1 ≤ r ≤ n). Denotamos con T1 (Jr ), T2 (Jr ) y T3 (Jr ), los tiempos en los que se completan los trabajos de la secuencia Jr en las m´aquinas 1, 2 y 3, respectivamente. Una cota inferior del tiempo total de procesamiento de la secuencia Jr , del nodo P , denotada por CI(P ), se calcula como: X T (J ) + ti1 + m´ın{ti2 + ti3 } 1 r i∈Jr i∈Jr X T (J ) + ti2 + m´ın{ti3 } 2 r CI(P ) = CI(Jr ) = m´ax i∈Jr i∈Jr X T (J ) + ti2 3 r i∈Jr
donde Jr es el conjunto de los n − r trabajos que a´ un no han sido ordenados, es decir
que no se encuentran en Jr . El algoritmo se puede acelerar si consideramos el principio de la dominancia. Si existen dos secuencias distintas Jr e Ir , que contienen los mismos r trabajos, entonces podemos eliminar la secuencia Ir cuando: T2 (Jr ) ≤ T2 (Ir ) y T3 (Jr ) ≤ T3 (Ir ).
´ CAP´ITULO 4. SECUENCIACION
83
Ejercicios Ejercicio 37. Considerar el Cuadro 4.4, para resolver 9/2/G/Fm´ax . Trabajo 1 2 3 4 5 6 7 8 9
M´aquina 1 10 6 9 4 5 5 7 4 6
M´aquina 2 3 9 3 5 9 1 2 9 2
Cuadro 4.4: Tiempo de procesamiento para los trabajos del Ejercicio 37.
Ejercicio 38. Considerar el Cuadro 4.5, para resolver 5/3/G/Fm´ax . Trabajo M´aquina 1 M´aquina 2 M´aquina 3 1 10 3 3 2 6 4 7 3 9 3 10 4 4 2 9 5 5 1 2 Cuadro 4.5: Tiempo de procesamiento para los trabajos del Ejercicio 38.
Ejercicio 39. Considerar el Cuadro 4.6 (Tomado de [10], p. 74), para resolver 9/2/G/Fm´ax . Sugerencia: Utilizar la variante del algoritmo de Johnson, propuesta por Jackson [14].
´ CAP´ITULO 4. SECUENCIACION
Trabajo 1 2 3 4 5 6 7 8 9
Primera M´aquina M1 8 M1 7 M1 9 M1 4 M2 6 M2 5 M1 9 M2 1 M2 5
84
Segunda M´aquina M2 2 M2 5 M2 8 M2 7 M1 4 M1 3
Cuadro 4.6: Orden y tiempo de procesamiento para los trabajos del Ejercicio 39.
Cuadro 4.7: Orden de los procesos para el Ejercicio 39. Grupo C A D Maq1 4 3 2 1 7 6 5 Grupo D B C Maq2 6 5 8 9 4 3 2 1
Bibliograf´ıa [1] Hillier Lieberman. Introducci´on a la Investigaci´on de Operaciones. McGrawHill, M´exico, 8 edition, 2004. [2] Williams Stallings. Sistemas Operativos. Principios de dise˜ no e interioridades. Prentice Hall, 4 edition, 2001. [3] Taha Hamdy. Investigaci´on de Operaciones. Pearson Educaci´on, M´exico, 7a. edition, 2004. [4] Wayne L. Winston. Investigaci´on de Operaciones Aplicaciones y Algoritmos. Thomson, 4 edition, 2005. [5] Kamlesh Mathur and Daniel Solow. Investigaci´on de Operaciones, El arte de la toma de decisiones. Pearson Prentice Hall, 1996. [6] G.D. Eppen. Investigaci´on de Operaciones en Ciencia Administrativa. Prentice Hall, 5 edition, 2000. [7] R. Bronson. Investigaci´on de Operaciones. Schaum. McGrawHill, M´exico, 1993. [8] D. Kendall. Some problems in the theory of queues. Journal of the Royal Statistical Society, 13:151–185, 1951. [9] W. Feller. An Introduction to Probability Theory and Its Applications, volume 1. Wiley, New York, 2nd edition, 1957. [10] S. French. Sequencing and Scheduling. Ellis Harwood, 1982. [11] S.M. Johnson. Optimal twoand three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1):61–68, 1954. [12] E. Ignall and L. Schrage. Application of the branch and bound technique to some flow-shop scheduling problems. Operations Research, 13(3):400–412, 1965. [13] Z.A. Lomnicki. A branch-and-bound algorithm for the exact solution of the three-machine scheduling problem. Operational Research Quarterly, 16(1):89– 100, 1965. [14] J.R. Jackson. An extension of. johnson’s result on job lot scheduling. Naval Research Logistics Quarterly, 3:201–203, 1956.
85