Universidad de Chile Facultad de Ciencias F´ısicas y Matem´aticas Departamento de Ingenier´ıa Industrial

IN44A: Investigaci´on Operativa Profesores: R. Caldentey, R. Epstein, P. Rey Prof. Aux.: J. Gacit´ ua, L. Vald´es, D. Wilson

Control 3 Lunes 23 de Junio 2008

Pregunta 1 Pasajeros llegan a un paradero de taxis seg´ un un proceso de Poisson de tasa λ pasajeros por hora. Los taxis llegan al paradero tambi´en seg´ un un proceso de Poisson de tasa µ taxis por hora. Los taxis forman una fila a la espera de un pasajero. Cuando llega un pasajero, toma el primer taxi de la fila y se va a su destino. Si no hay taxis en la fila, el pasajero se va y busca otro medio de transporte. Calcule, para el largo plazo, lo siguiente: 1. N´ umero promedio de taxis esperando en fila (0,5 puntos). Estamos frente a una cola M/M/1. Los pasajeros act´ uan como servidor y los taxistas como clientes. Sea {X(t), t ≥ 0} la cadena de Markov representa el n´ umero de taxistas esperando pasajeros. X(t) ∈ N0 . El generador infinitesimal de la cadena es  −µ    −(λ + µ) Q = (qij ) =  µ    λ

i=j=0 i = j, i ≥ 1 j = i + 1, j = i − 1, i ≥ 1

Para hacer c´ alculos en el largo plazo, debemos obtener las probabilidades estacionarias. Se plantean las ecuaciones de equilibrio, µπ0 (µ + λ)πi ∞ X πi

= λπ1 = µπi−1 + λπi+1 ∀i = 1, 2.. =

1

i=0

Sea ρ =

µ λ

(Se asume ρ < 1). Con las ecuaciones anteriores se llega a

En esta pregunta se pide L =

P∞

i=0

iπi =

1−ρ

π0

=

πi

= ρi π0

µ λ−µ

2. Tiempo promedio que debe esperar un taxi para encontrar pasajero (0,5 puntos). Se busca el tiempo promedio que un taxi esta en el sistema, W. Ocupando Little y la parte anterior se obtiene W

=

L µ

=

1 λ−µ

3. Fracci´ on de los pasajeros que no encuentra taxi (0,5 puntos). favorables Se hace un an´ alisis de casos por unidad de tiempo. La totalidad de los pasajeros llega al casos totales paradero a tasa λ. En el largo plazo, pasajeros llegan a un sistema vac´ıo con tasa π0 λ, por lo tanto la fracci´ on pedida es π0 λ = π0 λ

Considere que cada pasajero que se retira supone un costo C al sistema “taxis”. Tambi´en, suponga que cada taxi en la fila significa un costo de T por hora de espera al sistema “taxis”. Adicionalmente, cada pasajero que toma un taxi representa un beneficio esperado de B al sistema “taxis”. 4. Si el sistema “taxis”puede regular la tasa de llegada µ, plantee las ecuaciones que permitan encontrar el µ ´ optimo para los taxistas (0,6 puntos). Se define la funci´ on de utilidad Π = B(1 − π0 )λ − Cπ0 λ − T · L El µ ´ optimo se obtiene al resolver δΠ =0 δµ

Pregunta 2 Un centro m´edico atiende pacientes graves y pacientes leves. Los pacientes graves llegan al centro seg´ un un proceso de Poisson de tasa α pacientes por hora. Los pacientes leves llegan tambi´en seg´ un un proceso de Poisson de tasa β pacientes por hora. La sala de espera para pacientes graves es muy grande (para efectos pr´acticos infinta), pero la sala de espera para pacientes leves acepta hasta 2 pacientes como m´aximo. Si llega un paciente leve al centro y la sala de espera est´ a llena, el paciente se retira y se atiende en otro servicio. El centro s´ olo puede atender a un enfermo a la vez. El tiempo de atenci´on de un enfermo distribuye exponencialmente con tasa µ pacientes por hora, independiente si el paciente est´a grave o leve. El centro atiende a los pacientes leves s´ olo cuando no hay pacientes graves en el centro, es decir, los pacientes graves tienen la prioridad. Incluso, si cuando est´an atendiendo a un paciente leve llegara un paciente grave, la atenci´ on al paciente leve es suspendida y este paciente leve es enviado a su sala de espera (si la sala de espera est´ a llena el paciente leve se va del centro) y se atiende inmediatamente al paciente grave. 1. Exprese en funci´ on de los par´ ametros del problema, el tiempo promedio que debe esperar un paciente grave para empezar a ser atendido. (0,5 puntos) Sea {X(t), t ≥ 0} cadena de Markov en tiempo continuo que representa el n´ umero de pacientes graves y leves dentro del hospital. El conjunto de estados es E = {N0 × {0, 1, 2}} ∪ (0, 3). El primer ´ındice indica el n’mero de pacientes graves en el hospital; el segundo, los pacientes leves. El diagrama de estados es el siguiente:

Las ecuaciones que permiten encontrar las probabilidades estacionarias son las siguientes:

(α + β)π0,0

= µ(π1,0 + π0,1 )

(µ + α + β)π0,1

= βπ0,0 + µ(π1,1 + pi0,2 )

(µ + α + β)π0,2

= βπ0,1 + µ(π1,2 + pi0,3 )

(µ + α)π0,3

= βπ0,2

(µ + α + β)πi,0

= απi−1,0 + µπi+1,0 ∀i ≥ 1

(µ + α + β)πi,1

= απi−1,1 + βπi,0 + µπi+1,1 ∀i ≥ 1

(µ + α)πi,2

= απi−1,2 + βπi,1 + µπi+1,2 ∀i ≥ 2

(µ + α)π1,2 X πi,j

= α(π0,2 + π0,3 ) + βπ1,1 + µπ2,2 =

1

({i,j)∈E}

La respuesta a esta pregunta es Wq , de la cola de pacientes graves. Calculamos entonces Lq : X Lq = (i − 1)πi,j {(i,j)∈E:i≥1}

La tasa efectiva de entrada de pacientes graves es α, por lo tanto, Wq =

Lq α

2. Exprese en funci´ on de los par´ ametros del problema, la fracci´on de los pacientes leves que se retiran del centro habiendo sido atendidos satisfactoriamente. (1,0 puntos) En el largo plazo, pacientes leves aparecen con una tasa β por hora en el sistema. Cuando la cadena est´ a en los estados (0,1),(0,2),(0,3) est´an siendo atendidos pacientes leves, por lo tanto la tasa efectiva a la cual salen pacientes leves del hospital es (π0,1 + π0,2 + π0,3 )µ. La fracci´on de pacientes leves que se retiran siendo atendidos satisfactoriamente es entonces (π0,1 + π0,2 + π0,3 )µ β

Responda SOLO UNA de las dos preguntas siguientes

Pregunta 3 A un call-center llegan llamadas telef´ onicas a tasa λ llamadas por minuto. En el centro hay n operadoras, esperando atender las consultas de los clientes. Cada operadora tarda un tiempo exponencial de tasa µ llamadas por minuto en atender a un cliente. Si todas las operadoras est´an ocupadas, las llamadas van haciendo cola en el sistema telef´ onico. 1. En el largo plazo, ¿cu´ antas personas hay en el sistema esperando a ser atendidas? (0,8 puntos) Estamos frente a una cadena M/M/C. Se desarrollar´a el modelo via cadenas de Markov en tiempo cont´ınuo. Sea {X(t), t ≥ 0} cadena de Markov en tiempo continuo que representa el n´ umero de llamadas en el call-center. El conjunto de estados es E = N0 . El generador infinitesimal de la cadena es  −λ i=j=0      −(λ + iµ) i = j, 0 < i ≤ n    −(λ + nµ)) i = j, i > n Q = (qij ) =  iµ j = i − 1, i ≤ n     nµ j = i − 1, i > n    λ j =i+1 Las ecuaciones que permiten resolver las probabilidades estacionarias son:

λπ0

=

µπ1

(λ + iµ)πi

=

λπi−1 + (i + 1)µπi+1 ∀0 < i < n

(λ + nµ)πj X πi

=

λπj−1 + nµπj+1 ∀j ≤ n

=

1

i∈E

El n´ umero promedio de personas esperando a ser atendidas en el largo plazo es X Lq = (i − n)πi i∈E:i≥n

2. Suponga que hay n clientes siendo atendidos y ninguno esperando y acaba de llegar una nueva llamada al call-center. En promedio, en cuanto tiempo m´as este cliente terminar´a su diligencia con el call-center? (0,8 puntos) Sea A el tiempo que debe esperar el cliente en ser atendido. Sea B el tiempo durante el cual es atendido. Tenemos A exp(nµ) y B exp(µ). Buscamos E[A+B]: E[A + B]

= E[A] + E[B] 1 1 + = nµ µ 1+n = nµ

3. Sabemos que existe un costo por hora de operadora que es igual a C · µ. Adem´as, si un cliente tiene que esperar se incurre en un costo de L, independiente del lapso que el cliente ha tenido que esperar.

Si el gerente puede regular la tasa de atenci´on de las operadoras, plantee como podemos encontrar la tasa ´ optima de atenci´ on, aquella que minimiza los costos horarios en el largo plazo. (0,8 puntos) El costo por horaPdel conjunto de secretarias es nCµ. La tasa efectiva a la cual llegan clientes que deben esperar es i>n πi λ. Debemos entonces minimizar, minµ>0 nCµ + L

X

πi λ

i>n

Pregunta 4 Un proceso de producci´ on puede estar en tres estados: 1. Operacional (O): En este estado el proceso genera una producci´on con un valor econ´onimco de $I por hora. 2. Mantenimiento (M): La mantenci´ on dura un tiempo exponencialmente distribuido con una media de 1 hora. El costo de una mantenci´ on es de $m por mantenci´on. ´ n (R): Un equipo en estado Operacional puede fallar antes de una mantenci´on. En este 3. Reparacio caso el equipo debe ser reparado, lo que toma un tiempo exponencialmente distribuido con una media de 5 horas. El costo de una reparaci´ on es de $r por reparaci´on. Despu´es de una Mantenci´ on o una Reparaci´on el equipo vuelve a su estado Operacional. El tiempo de falla de un equipo operacional esta expoenencialmente distribuido con una media de 10 horas. Por otro lado, la pol´ıtica de mantenci´ on de la empresa es tal que el tiempo para la pr´oxima mantenci´ on de un equipo Operacional est´ a exponencialmente distribuido con una media de 5 horas. Estos tiempos de falla y mantenci´ on son independientes. a) Si el sistema se encuentra inicialmente en operaci´on, cu´al es la probabilidad que este en mantenci´ on despues de 10 horas de operaci´ on. b) Qu´e relaci´ on debe existir entre I, m y r para que el proceso de producci´on sea rentable al considerar su operaci´ on de largo plazo?