Los fenómenos de espera surgen cuando algunas entidades (clientes) solicitan acceso y atención a determinado(s) lugar(es) (servidor(es)) el cual procesa cada solicitud con una rapidez tal, que los clientes tienen que esperar a ser procesados(atendidos) en un tiempo posterior al de su llegada.
Las
experiencias cotidianas están llenas de fenómenos de espera. Cuando se ingresa
a un restaurante se experimentan fenómenos de espera, cuando se desea hacer un
trámite bancario, frente a un semáforo etc. Las personas, los productos, la
información, etc., pasan mucho tiempo en espera de atención. De ahí la
importancia del estudio de estos fenómenos.
La manera de
abordar el estudio de estos fenómenos es diversa, se pueden abordar desde el
punto de vista de la simulación por computadora o bien se pueden abordar desde
el punto de vista algebraico. Ambos puntos de vista tienen sus ventajas
respectivas.
ü Sin costo de
espera y/o de prestación, estudiar
“cola” es intrascendente.
ü La cola y la espera sólo dependen de la velocidad de arribo de los clientes.
ü Solamente podrán salir
de la cola y dirigirse a los canales de despacho los clientes que ingresaron al sistema.
ü Del sistema salen
tantos clientes como entran, la característica del despacho no influye.
ü Menos de un servidor no
es posible colocar.
ü Para realizar el estudio de las colas de espera es
imprescindible que se cumpla con la condición de ser sistemas estables y permanentes.
SISTEMA ESTABLE
Un sistema es estable cuando no sufre alteraciones a lo largo del día.
En los procesos aleatorios eso se da cuando el valor medio ó promedio de la
variable permanece constante independiente del tiempo. Por ejemplo se puede
decir, el valor medio de 60u/hora. Eso significa que a las 10:00 hs., a las
12:00, a las 18:30, a las 23.40, o en cualquier momento del día, el promedio siempre se mantiene en su
valor 60 u/hora. Pero como precisamente es promedio, la variable a la cual
represente, puede en cualquier momento tomar valores como 53-45-85-17-70-0-32
etc.
El sistema es permanente cuando la variable aleatoria toma una media que se
mantiene día a día o sea lo mismo el martes que el jueves. Veamos, el
acceso de clientes al 112 de Telecom no es estable porque según sea la hora del
día en que haga la medición, algunas veces hay mas llamadas que en otras.
En cambio es permanente, porque no existe razón para que se encuentren diferencias importantes en los llamados que se hagan entre las 8.00 y las 10.00 de los días lunes, martes... o los viernes.
MODELO M / M / 1(Monocola - Monocanal)
El modelo M / M / 1 es el mas fácil de estudiar y
puede aplicarse a personas esperando en una cola para comprar boletos para el
cine, a mecánicos que esperan obtener herramientas de un expendio o a trabajos
de computadora que esperan tiempo de procesador, etc.
Características del modelo.
ü
Una fuente a partir de la cual
fluyen los clientes.
ü Un único canal de despacho que constituye el centro de
servicio.
ü Una línea de
espera en Cola.
ü Llegada
Poisson.
ü Cola infinita,
primero en llegar primero en ser servido (FIFO).
ü Tiempos de
servicio exponenciales.
Matemáticamente,
este modelo es el mas simple de estudiar.
Se considera que el proceso de entrada es poissoniano: esto es, los tiempos entre llegadas tienen una distribución exponencial negativa con parámetro l y el canal de servicio tiene tiempos de servicio que también siguen una distribución exponencial negativa con parámetro m.
Como sucedió
con las cadenas de Markov1, en los
modelos de línea de espera, a menudo lo que interesa son sólo las
características de operación a largo plazo de tales sistemas: esto es, cuando
el sistema se encuentra en equilibrio
estadístico o en estado estable. El intervalo de
tiempo necesario para acercarse lo suficientemente próximo al estado estable
(denominado comportamiento transitorio
del proceso) no se toma en cuenta.
Sin embargo,
debe considerarse que muchos sistemas nunca llegan a un estado estable, para el estudio de éstos se utiliza la
técnica de simulación.
En cualquier
momento del día, el estado del proceso de línea de espera M/M/1 está
descripto por completo mediante el número de clientes en el sistema(los
clientes en la línea de espera más el cliente en el canal de servicio).
Entonces, el
estado del proceso puede asumir valores:
0: La instalación de servicio está
ociosa, no hay clientes en la línea de espera
1: La instalación de servicio esta
ocupada, no hay unidades en la línea de espera
2, 3,..n clientes: La instalación de servicio está ocupada, hay n - 1 unidades en la línea de espera.
En los sistemas de líneas de espera una transición de
estado a otro puede ocurrir en cualquier momento y no sólo en los puntos
regularmente espaciados en el tiempo. Sin embargo, el proceso tenderá a un
estado estable que es independiente de su posición o estado inicial.
Cualquier persona que tenga la
intención de ir a un lugar en donde ella supone que debe esperar, se plantea
intuitivamente la siguiente pregunta: ¿cuál es la probabilidad de esperar para
ser atendido? Así, si supone que hay una probabilidad cercana a 1 de que haya
20 a 25 personas en la fila el sábado en la mañana, escogerá otro día, para el
cual esta probabilidad sea menor a su juicio. En todos los fenómenos de espera,
la determinación de la ley de probabilidad pn
del número de unidades en el sistema constituye un cálculo fundamental, a
partir del cual podrán ponerse en evidencia varias expresiones cuantitativas.
Esto no se cumple en general, sino sólo
en un cierto intervalo de tiempo que interesa determinar de antemano. Dos
causas pueden provocar la variación de pn:
- Una modificación de la tasa media de
arribo de clientes l y/o de la
tasa media de servicio m.
- El fenómeno
transitorio que se produce entre el comienzo del funcionamiento del servicio y
el instante en el cual se ha estabilizado la situación. La duración de este
fenómeno transitorio es función de l y de m.
Por ejemplo, será conveniente tomar como intervalo de medida una duración superior a tres o cuatro veces la duración de la estabilización de la situación.
Denótese a las
probabilidades de estado estable como pn, n = 0, 1. 2,... , donde el
subíndice se refiere al número de unidades en el sistema. Como se ha visto,
para llegadas poissonianas y un tiempo exponencial negativo de servicio, las
probabilidades de que ocurra una llegada o se concluya un servicio en un
intervalo de duración h no depende
de la historia del sistema antes del inicio del intervalo. Por lo tanto, la
probabilidad de una transición de un estado dado a otro estado en el intervalo h no depende de cuánto tiempo haya
ocupado ese estado el sistema.
Toda la información necesaria para describir
el comportamiento futuro del sistema está contenida en esa especificación de
estado. Por esta razón, en las líneas de esperas, tales como M/M/1 algunas veces se las denomina markovianas. Para tales sistemas, si se observa el proceso en estado
estable en dos momentos elegidos de manera aleatoria, separados por un corto
intervalo de tiempo h, entonces debe
cumplirse que las probabilidades de encontrar el proceso en los diferentes
estados permanecen sin cambio, debido a la definición misma de estado estable.
Pero esto requiere que, para cada estado la probabilidad de encontrarse en ese
estado y salir de él durante un tiempo h, equilibre exactamente la probabilidad
de encontrarse en otros estados y entrar a ese estado durante h.
Considerando
en primer lugar una cola infinita donde llegan con una media de l clientes por
unidad de tiempo, y son servidos con una media de m clientes por
unidad de tiempo. La cola puede encontrarse en los estados {1,2,3..n }. El
número de transacciones de nàn+1 es entonces l pn
y el número de transacciones nàn -1 es m pn:
En el
equilibrio, el número de transiciones en uno y otro sentido ha de ser igual,
por término medio, so pena de que la cola se encuentre vacía permanentemente o
crezca sin límite. Por lo tanto, si pn
es la probabilidad estacianoria de que el sistema se
encuentre en el estado n :
Resolviendo la primera para p1 podemos encontrar p2 de la segunda, que podemos
sustituir en la tercera para encontrar p3
y así sucesivamente, obteniendo un resultado general:
pn = (l/ m)n
p0 n>=1
(1) pn = (r)n
p0
n>=1 (fórmula
de recurrencia)
En cualquier
tiempo en particular la probabilidad de que un servidor esté ocupado lo da la
medida de rendimiento asociada que es la utilización,
denotado con U. Esta medida indica también la fracción de tiempo que un
servidor está ocupado.
Por lo que
U
= r
=l/ m
Sea p0
la probabilidad de que un cliente que llega no tenga que esperar para se
atendido. Esto es la probabilidad de que el sistema esté vacío.
(2) Entonces p0
= 1 – U = 1 - r
Reemplazando p0 en (1) queda :
(3) pn= (l¤m)n (1-l¤m) = rn (1 - r ) ,
toda n ³ 0
También es
igual a la probabilidad de que el canal de servicio esté ocupado. Ya que el
proceso de llegada es poissoniano (3), también es la distribución del número de
unidades que encontrará un cliente al llegar al sistema en estado estable.
PROBABILIDAD ACUMULADA
Con lo visto
hasta el momento podemos responder a la pregunta:
¿Cual es la probabilidad de llegar y ser el cuarto de la cola?
El cual es un
valor puntual y muy preciso, pn , que es la
probabilidad de llegar y encontrarse con el sistema en estado cinco, p5
(uno en atención y cuatro en cola).
Cuando el que
llegue se integre, el sistema pasará a estado seis, p6 ,si es que en el mismo momento no termina el servicio del
que están atendiendo.
Para cuando se
trabaje con Probabilidades Acumuladas,
la pregunta sería:
¿Cual es la
probabilidad de llegar y ser a lo sumo el quinto de la cola?
Para este otro
supuesto, el cliente encuentra como agradable:
ü
llegar y ser atendido de inmediato. Sistema en estado cero,
ü
llegar y ser el primero de la cola. Sistema en estado uno,
ü
llegar y encontrar el sistema en estado cinco, en tal caso
sería el cuarto de la cola.
Como todos esos estados le son favorables, por el Teorema de la Probabilidad Total, se deben sumar todas las probabilidades de los eventos:
P(5) = p0 + p1 + p2 + . . .+ p5 = 1 - r 5+ 1 = 1 - r n+ 1
Para esto sirve calcular las probabilidades acumuladas.
En nuestro
caso, el valor más interesante es:
p0 + p1 + p2 + p3 + . . .+ pn
>= 0.95
o sea cual es
ese valor de estado que “derrama la copa” y hace que se alcance o supere, lo
que se considera la Máxima Probabilidad de Estado del Sistema. Supongamos que
nos resulte n
= 81 entonces:
p0 + p1 + p2 + . . . + p80 +
p81 » 0.953
El sistema podrá y como
máximo llegar a tener 80 personas en la cola.
Dada la distribución de estado estable, es posible obtener un cierto número de importantes características de operación del sistema, que tal vez resulten necesarias como datos en la obtención de medidas de efectividad del sistema.
1.
El número promedio de unidades en el sistema (incluyendo aquella que esté en
servicio), denotado como L:
2.
.El número promedio de unidades que
esperan en la línea, denotado Lq será:
3. El tiempo promedio
que el sistema está ocioso y el
tiempo promedio de ocupación de la instalación de servicio.
Una
interpretación alternativa para las probabilidades de estado estable es que
representan la fracción promedio de tiempo que el sistema se encuentra en cada
estado. Por lo tanto po
= 1 - r es la
fracción promedio de tiempo que ninguna unidad se encuentra en el sistema o
tiempo promedio ocioso
y pw(el sistema esté ocupado) = r
es la fracción promedio de tiempo que
hay al menos 1 unidad en el sistema o el tiempo promedio de ocupación de la
instalación.
4.
El tiempo
promedio que pasa el cliente en la cola denotado por Wq,
Sale del cociente entre el numero medio de clientes que hay en esa cola sobre la velocidad de arribo de los mismos al sistema. Esto es casi análogo a la formula de velocidad, que es v= e / t, como aquí lo que queremos calcular es el tiempo, despejamos: t = e / v. Haciendo analogía con el fenómeno de espera sería, el tiempo de espera en la cola
(Wq)= numero de
clientes en la cola (espacio)
velocidad de llegada de los mismos
(v).
5.
EI tiempo
promedio que permanece un cliente en el sistema, denotado por Ws.
Esta es la suma del tiempo esperado en la
cola Wq, y el tiempo esperado de servicio. Entonces.
Ws = Wq +(1/m)
Reemplazando Wq tenemos:
Otra forma de obtener el valor de r (intensidad
de tráfico) es conociendo Ls (número medio
de unidades en el sistema).
ANALISIS DEL FACTOR DE USO PARA UNA COLA M / M / 1
El Factor de
Uso se define como:
l: numero promedio de llegadas de clientes por unidad de tiempo
m: es la velocidad de servicio por unidad de tiempo
r:
definido
por l / m se conoce
como factor de utilización o intensidad de tráfico (r).
S: define la
cantidad de servidores. En este caso será igual a 1, por lo que la ecuación quedaría: Y = (r / k).
k: se define como la cantidad de
clientes que el servidor puede atender en un mismo instante, k puede tomar el
valor 1 (sin efecto bulk service)o mayor que 1(con efecto bulk service).
A la largo del análisis de las fórmulas de
rendimiento antes desarrolladas se consideró que el servidor atendía un cliente
por vez (k=1).
Cuando el
fenómeno de espera es realizado por personas, entran factores importantes en
juego que son el razonamiento y el
poder de decisión.
Una cola puede
crecer tanto como sea posible, pero llegará un punto donde los clientes se
comiencen a retirar sin ser atendidos o que haya personas que no entren al
sistema por el largo extremado de la cola.
Si el
prestador del servicio no le implica costo alguno perder estos clientes no se
realizará un análisis para mejorar esta situación. Sería el caso de la cola
realizada por los jubilados en las cajas de los bancos (de Argentina) para el
cobro de sus mensualidades.
En cambio la
situación es analizada cuando dicha pérdida de clientes afecta económicamente
al prestador de servicio. Tal es caso de un banco que pierde clientes en su
servicio de caja de ahorro o cuenta corriente.
Para mejorar el rendimiento del sistema monocola monocanal contamos con algunas posibilidades según el caso en cuestión.
ü Si el sistema lo permite se realiza la implementación del efecto bulk service.
Entonces
consideramos el Factor de Uso con el que
obtendremos las medidas de rendimiento.
Es el caso del servicio prestado por un ascensor, por un colectivo, etc., donde k tomará el valor de la capacidad que el servidor pueda tener.
ü
En ocasiones se presenta la
situación de no poder controlar el crecimiento de la cola. Con la imposibilidad
de aplicar el efecto bulk service, tal es el caso de los consultorios médicos.
Para el ejemplo mencionado recurrimos a la implementación de turnos. Mediante
este método lograremos afectar la velocidad de arribo de clientes y como
consecuencia también se produce un cambio en la distribución de arribos de
Poisson General (Normal).
ü
En caso de ser factible una manera de optimizar el servicio
es hacer variar la tasa de servicio (m). Esto implica elevar el costo del servidor.
ü
Como restricción para nuestro modelo no se puede aumentar el
número de servidores ya que perderá la esencia de modelo M /M /1 a M / M / S.
FORMULAS PARA
CALCULAR LAS MEDIDAS DE RENDIMIENTO DE UN SISTEMA DE COLAS M / M /1
MEDIDA
DE RENDIMIENTO |
FORMULA
GENERAL |
Probabilidad
de que haya n clientes en el sistema Utilización Probabilidad
de que un cliente que llega tenga que esperar Probabilidad
de que no haya clientes en el sistema Numero
promedio en el sistema Numero
promedio en la fila Tiempo
promedio de espera en la cola Tiempo
promedio de espera en el sistema |
U
=r |
EL PROBLEMA DE COLAS DE LA OHIO TURNPIKE
La Comisión de la Autopista de Ohio (Ohio Turnpíke Commission, OTC) tiene un numero de estaciones para el pesado de camiones a lo largo de la autopista de cuota de Ohio, para verificar que el peso de los vehículos cumple con las regulaciones federales. Una de taIes estaciones se ilustra en la figura. La administración de OTC esta considerando mejorar la calidad del servicio en sus estaciones de pesado y ha seleccionado una de las instalaciones como modelo a estudiar, antes de instrumentar los cambios. La administración desea analizar y entender el desempeño del sistema actual durante las horas pico, cuando llega a la bascula el mayor numero de camiones suponiendo que el sistema puede desempeñarse bien durante este periodo, el servicio en cualquier otro momento será aún mejor.
El gerente de operaciones siente que el sistema actual de la figura cumple con las cuatro condiciones presentadas anteriormente. Su siguiente paso es estimar las tasas promedio de llegada y de servicio en dicha estación. De los datos disponibles, suponga que la gerencia determina que los valores son:
l = numero
promedio de camiones que llegan por hora = 60
m = número
promedio de camiones que pueden ser pesados por hora = 66
El valor de m = 66 es mayor
que el de l = 60, de modo que es posible
hacer el análisis de estado estable de este sistema.
En términos de
los parámetros m y l los investigadores han derivado formulas
para calcular las diferentes medidas de rendimiento para cualquier sistema de
colas M / M / 1. Estas fórmulas a menudo se expresan en términos de la intensidad de tráfico, r (la letra
griega rho ), que es el cociente de l sobre m. Para el
problema de OTC, esta intensidad de tráfico es
r =l / m = 60 / 66 = 0.9091
Mientras más cerca este r de 1, mas
cargado estará el sistema, lo cual tiene como resultado colas mas largas y
tiempos de espera más grandes.
En términos de r , l y m, las medidas
de rendimiento, para el problema de OTC, se calculan de la manera siguiente:
1. Probabilidad
de que no haya clientes en el sistema (P0):
P0 =
1-r = 1 –0.9091 = 0.0909
Este valor indica que aproximadamente 9% del tiempo un camión que llega no tiene que esperar a que se le proporcione el servicio porque la estación de pesado esta vacía. Dicho de otra manera, aproximadamente 91% del tiempo un camión que llega tiene que esperar.
2. Numero
promedio en la fila (Lq ):
Lq =
=
= 9.0909
En otras palabras, en el estado estable, en promedio, la estación de pesado puede esperar tener aproximadamente nueve camiones esperando para obtener el servicio(sin incluir al que se esta pesando).
Cuando ya ha determinado un valor para
Lq , usted puede calcular los valores de Wq , Ws y L.s.
3. Tiempo
promedio de espera en la cola (Wq ):
Wq =
Lq / l = 9.0909 /
60 = 0.1515
Este valor indica que, en promedio, un
camión tiene que esperar 0.1515 horas, aproximadamente 9 minutos, en la fila
antes de que empiece el proceso de pesado.
4. Tiempo
promedio de espera en el sistema (W):
W = Wq + 1 / m = 0.1515+
1/66 = 0.1667
Este valor indica que, en promedio, un
camión invierte 0.1667 horas, 10 minutos, desde que llegas hasta que sale.
5. Numero
promedio en el sistema (Ls ):
Ls =
=
=10
Este valor indica que, en promedio,
existe un total de 10 camiones en la estación de pesado, ya sea en la bascula o
esperando ser atendidos.
6. Probabilidad
de que un cliente que llega tenga que esperar (pw):
pw= 1- P0 = r = 0.9091
Este valor, como se estableció en el paso 1, indica que aproximadamente 91% del tiempo un camión que llega tiene que esperar.
7. Probabilidad
de que haya n clientes en el sistema (Pn):
Pn = rn * P0
Al utilizar esta fórmula, se obtienen
las siguientes probabilidades:
n |
Prob. Estimada de encontrar n clientes en el sist. |
Probabilidad Acumulada |
0 |
0.0909 |
0.0909 |
1 |
0.0826 |
0.1736 |
2 |
0.0751 |
0.2487 |
3 |
0.0683 |
0.3170 |
|
. |
. |
|
. |
. |
29 |
0.0057 |
0.9427 |
30 |
0.0052 |
0.9479 |
31 |
0.0047 |
0.9526 |
32 |
0.0043 |
0.9569 |
33 |
0.0039 |
0.9609 |
|
. |
. |
Gráfica
de la Probabilidad Estimada de encontrar n clientes en el Sistema.
Esta tabla proporciona la distribución de probabilidad para el número de camiones que se encuentran en el sistema. Los números que aparecen en la tabla se pueden utilizar para responder una pregunta como: ¿ cuál es la probabilidad de que no haya mas de 3 camiones en el sistema? En este caso, la respuesta de 0.3169 se obtiene mediante la suma de las primeras cuatro probabilidades de la tabla, para n = 0, 1, 2 y 3.
Observamos que el estado máximo de la cola se alcanza aproximada-mente en n = 31.
8. Utilización(U):
U = r =0.9091
Este valor indica que aproximadamente 91% del tiempo las instalaciones de pesado están en uso (un camión esta siendo pesado). De manera equivalente, aproximadamente 9% del tiempo la estación esta sin funcionar, sin que haya camiones que se estén pesando.
CALA, Daniel Fernando
UTN