miércoles, 6 de julio de 2011

Introducción a la Teoría de Colas

INTRODUCCION A LA TEORÍA DE COLAS
Autor Leonel Caal

En la teoría de colas se estudiaran los procesos de llegada, tiempo en cola que pasa el cliente, tiempo de servicio así como número de clientes que se encuentran. El proceso de entrada se conoce por lo general como proceso de llegada, la llegada de los clientes.  Los modelos en los que las llegadas se toman de una población pequeña se llama modelos de origen finito. Ha servidores en paralelo como por ejemplo los cajeros de un banco que están organizados generalmente en paralelo, el otro es servidores en serie en los cuales se debe de pasar por varios de ellos antes de completar el servicio un ejemplo de esto son la líneas de ensamble.
La disciplina de cola es el método que se usa para determinar el orden en que se sirve a los clientes. La disciplina más común es la disciplina PLPS (primero en llegar primero en ser servido), ULPS (ultimo en llegar primero en ser servido)  este se puede ejemplificar cuando alguien es el ultimo en subirse a un elevador lleno y el primero que se baja, o sea el primero en ser servido. Disciplina SEOA (servicio en orden aleatorio), DG disciplina general en la cola.

Existe un sistema de notación para el sistema de colas establecido por KENDALL-LEE, la cual representa seis características.
1/2/3/4/5/6
1: Naturaleza del proceso de llegada
2: Naturaleza de tiempos de servicio
3: Número de servidores en Paralelo
4: Disciplina de la cola
5: Número máximo de clientes en el sistema, incluyendo los que esperan y los que están   
    en ventanilla.         
6: Tamaño de la población de la cual se toman los clientes.

Donde:
1 puede ser M: exponencial,  D: tiempos de llegada son idénticamente deterministicas.  Ek: los tiempos entre llegadas son con distribución de Erlang con parámetro de forma k.  GI: los tiempos de llegadas son idénticamente deterministicos y están gobernados por alguna distribución gneral.
2: M, D, Ek, G: los tiempos de servicio son idénticamente deterministicas y siguen alguna distribución general.
4: PLPS, ULPS, SEOA, DG.





EJEMPLO  1

M/M/8/PLPS/10/¥  puede representar una clínica con 8 doctores (/8/)con tiempos exponenciales de llegada y servicio (M/M/), la disciplina en la cola es el primero que llega es el primero en ser servido (/PLPS/), y una capacidad de 10 pacientes (/10/) con una población infinita (/¥).

SISTEMA DE COLAS M/M/1/DG/¥/¥

En este sistema la tasa de llegada y servicio son exponenciales con 1 servidor, disciplina general en la cola con infinitos clientes en el sistema, que se obtienen de una población infinita.
l = número promedio de llegas que entran por unidad de tiempo
m = número de clientes que se atienden por unidad de tiempo
Lq = número promedio de clientes que esperan en la cola
Ls = número promedio de clientes en el sistema
Wq = tiempo promedio que pasa un cliente en la cola

Ws = tiempo promedio que pasa un cliente en el sistema
r = factor de utilización

En estas definiciones, todos los promedios son para estado estable donde  r=l/m<1, si r>1 es fácil ver porqué no puede existir distribución de estado estable. Supongamos l=6 clientes por hora y que m=4 clientes por hora. Aun si el despachador estuviera trabajando todo el tiempo, sólo podría atender a 4 clientes por hora. Así, el número promedio de clientes en el sistema crecería al menos en 6-4=2 clientes por hora. Esto significa que después de mucho tiempo, el número de clientes que hay “explotaría” y no podría existir distribución de estado estable.  Entonces para cualquier sistema de colas en el que exista una distribución de estado estable, se cumplen las siguientes ecuaciones
L=
lW;             Lq=lWq;                     Ls=lWs

EJEMPLO 2

A un cajero sólo llega un promedio de 10 vehículos por hora. Suponga que el tiempo promedio de servicio para cada clientes es de 4 minutos, y que los tiempos entre llegadas y los de servicio son exponenciales. Conteste las siguientes preguntas.
a)    ¿ Cuál es la probabilidad de que el cajero se encuentre vacío?
b)    ¿Cuál es el número promedio de automóviles que esperan en la cola su turno?, se considera que un vehículo que está ocupando el cajero , no está en la cola esperando.
c)    ¿ Cuál es el tiempo promedio que un cliente pasa en el estacionamiento del banco, incluyendo el tiempo en el servicio?
d)    En promedio, ¿Cuántos clientes por hora serán atendidos por el cajero automático?

Solución:
Identificamos el modelo M/M/1/DG/¥/¥, ya que no especifica la cantidad de clientes en el sistema ni la población asumimos infinito, y se coloca una disciplina general.

Identificamos l = 10 vehículos/hora  y m=4 minutos/hora, lo primero que hay que fijarse es que no estan en las misma unidades entonces m la colocamos en vehículos por hora si atiende 1 vehiculo en 4 minutos entonces atenderá 15 en una hora por lo tanto m=15 vehiculos/hora.  RECORDARSE SIEMPRE EN LAS MISMA UNIDADES.

a) La probabilidad de que el cajero se encuentre vació es Po = 1- r   ;  
r= l/m=10/15=2/3=0.667, entonces Po=1-0.667 = 0.33, por lo tanto el cajero estará vació el 33% del tiempo.
b) Lq=r2/(1-r)=.6672/(1-.667)= 1.33 clientes
c) Ahora buscamos  W que es el tiempo total de todo el sistema.
L=r/(1/r)=0.667/(1-0.667)=2 clientes.
W=L/l = 2/10 = 1/5 hora = 12 minutos.
e)    Si el cajero estuviera ocupado siempre, podría atender 15 clientes por hora. Pero sabemos que solo se esta ocupado 0.67 del tiempo. Así que durante cada hora llegaran 0.67(15)=10 clientes.  El valor de 0.67 se obtiene de 1-Po, que es el tiempo que esta ocupado.

EJEMPLO 3.
Supongamos que todos los propietarios de automóviles llenan sus tanques de gasolina cuando están exactamente a la mitad, En la actualidad, llega un promedio de 7.5 clientes por hora a una gasolinera que tiene una sola bomba. Se necesita un promedio


de 4 minutos para atender un automóvil. Suponga que tanto los tiempos entre llegadas como los tiempos de servicio son exponenciales.
a)    Para el caso actual, calcule L y W
b)    Suponga que se presenta escasez de gasolina y que hay compras de pánico. Para modelar este fenómeno, suponga que todos los propietarios de automóvil compran gasolina cuando sus tanques les falta exactamente ¾ partes. Como cada conductor pone menos gasolina al tanque durante cada visita a la gasolinera, suponga que el tiempo promedio de servicio se ha reducido a 3.33 minutos ¿Cómo afecto la compra de pánico a L y a W?

Solución:
a)    Al identificar el sistema observamos que es M/M/1/DG/¥/¥ con l=7.5 vehículos /hora y m=15 vehículos por hora. Primero encontramos r=7.5/15=0.50, nótese que aquí se hace conversión porque m tiene diferentes unidades. Teniendo r logramos obtener L=r/(1/r) = 0.50/(1-0.5)=1, luego obtenemos W=L/l=1/7.5=0.13 horas. Con estos resultados podemos observar que todo está bajo control y son improbables las largas colas.

b)    Con la segunda opción tenemos el mismo sistema M/M/1/DG/¥/¥ con l=2(7.5)=15 vehículos por hora, se preguntar porque por 2 y es dado que el cliente llenará con doble de frecuencia su tanque porque ahora no estar a la mitad sino que ¾, y visitara la gasolinera cada vez que se haya gastado ¼ de tanque. Y m es igual a 60/3.33 = 18 vehiculos por hora donde r=15/18=5/6.

Con los datos utilizamos las ecuaciones:  L=(5/6)/(1-5/6)=5 automóviles y
W=5/15=1/3 horas = 20minutos.
Ya comparando se ve que las compras de pánico han originado colas mas largas y tiempos más largos  en el sistema.


EJEMPLO 4

Los mecánicos que trabajan en una planta de troquelado deben sacar herramientas de un almacén. Llega un promedio de diez mecánicos por hora buscando partes. En la actualidad el almacén está a cargo de un empleado a quien se les pagan 6 dólares/h y gasta un promedio de 5 min. Para entregar las herramientas de cada solicitud. Como a los mecánicos se les paga 10 dólares/h, cada hora que un mecánico pasa en el almacén de herramientas le cuesta 10 dólares a la empresa. Esta ha de decidir si vale la pena contratar, a 4 dólares/h, un ayudante del almacenista. Si se contrata al ayudante, el almacenista sólo tardará un promedio de 4 min para atender las solicitudes de herramientas. Suponga que son exponenciales tanto los tiempos de servicio como el tiempo entre llegadas. ¿Se debe de contratar al ayudante?

Solución.
Con 1 empleado.
l=10mecanico/hora      m=5min/mecanico lo coloco en las misma unidades
m=12mecanicos/hora
El costo total por hora será el sueldo del empleado que atiende ($6), mas el Tiempo que pasa el mecánico en el almacén por lo que se le paga ($10), colocando esto en formula tenemos.
Costo Total = 6 +10L
L=lW       W=1/(m-l) =1/(12-10)=0.5 horas


Costo Total = $6/hora + ($10/mec-hora)(10mec/hora)(0.5horas)=$56/hora
En el enunciado se menciona que se le pagan $10/hora al mecánico, y dice también que cada hora que pasa en el almacén de herramientas le cuesta $10 a la empresa, pero al leerse detenidamente se da cuenta que están hablando de los mismo $10/hora.

Análisis para 1 empleado con 1 ayudante que gana $4/hora
$4 del ayudante por hora
$6 del empleado por hora
l=10mec/hora    m=4min/mec = 15mec/hora
W=1/(15-10)=0.2 horas
CT=$4+$6+$10lW
CT=$4+$6+$10(10)(0.2) = $30/hora.

Conclusión:
La mejor opción es contratar al ayudante porque el costo será menor y se estaría ahorrando $50-$20=$30 por concepto de demoras, y con este ahorro alcanza para pagarle al ayudante y hasta sobra.

EJEMPLO 5.
En una aerolinea se debe revisar cada pasajero, así como su equipaje, para ve si trae armas. Suponga que al aeropuerto Internacional La Aurora llega un promedio de 10 pasajeros/minuto. Los tiempos entre llegas son exponenciales. Para revisar a los pasajeros, el aeropuerto debe tener una estación que consiste en un detector de metales y una máquina de rayos X para el equipaje . Cuando está trabajando la estación se necesitan dos empleados. Una estación puede revisar un promedio de 12 pasajeros/min. Con la hipótesis que el aeropuerto sólo tiene una estación de verificación, responda las siguientes preguntas.
a)¿ Cuál es la probabilidad de que un pasajero tenga que esperar para ser revisado?
c)    En promedio, ¿Cuántos pasajeros esperan en la cola para entrar a la estación?
d)    En promedio, ¿Cuánto tiempo pasará el pasajero en la estación de verificación.

Solución:
Primero identificamos el modelo M/M/1/DG/¥/¥ donde existe un servidor, en el problema puede confundirse pensando que son dos servidores porque hay dos empleados trabajando, pero NO es así ya que un servidor aquí se considera una estación independientemente que se realice en ella y cuantos la atiendan.

a) l=10 pasajeros/minuto   m=12 pasajeros/minuto
r=l/m=10/12=0.833    Po=1-0.833=0.17 (probabilidad de que este vacio) entonces estar ocupado 1-0.17= 0.833 =83.33% del tiempo esto es igual a r.

b) Lq=lWq=l2/(m(m-l)) = 102/(12(12-10))=4.17 personas en la cola.
c)    Ws=1/(m-l)=1/(12-10)=0.5 minutos.


MODELO M/M/1/DG/m/¥

Este sistema es parecido al anterior con la variante que tiene una capacidad total de “m” clientes, y cuando existen estos “m” clientes, todas las llegadas se regresan y el sistema las pierde para siempre. Este número máximo de clientes es una constante y varia según el libro que se utiliza c,m, etc.    En este modelo de

capacidad finita, llega un promedio de lPm, de esas llegadas encuentran al sistema lleno a toda capacidad y se van. Por lo tanto, en realidad entrará al sistema un promedio de `l=l(1-Pm) llegadas por unidad de tiempo. En este modelo existirá estado estable aún si l>m Esto se debe que aun cuando l>m,la capacidad finita de “m” en el sistema evita que “explote” el número de gentes en la cola.

EJEMPLO 6
En una peluquería hay un peluquero y un total de 10 asientos. Los tiempos de llegada tienen distribución exponencial, y llega un promedio de 20 clientes posibles por hora. Los que llegan cuando la peluquería esta llena no entran. El peluquero tarda un promedio e 12 minutos en atender a cada cliente. Los tiempos de corte de pelo tienen distribución exponencial.
a)    En promedio ¿Cuántos cortes de pelo hará el peluquero?
b)    En promedio ¿Cuánto tiempo pasará un cliente en la peluquería, cuando entra?

Solución
Identificación del modelo M/M/1/DG/10/¥
a)    Una fracción de P10 de las llegas encuentra que la peluquería esta llena. Por lo tanto, entrará a ella un promedio de l(1-P10) por hora. Todos los clientes que desean que se les corte el cabello, y por lo tanto, el peluquero hará un promedio de l(1-P10) cortes por hora. 
m=10 , l=20 clientes por hora y m=5 clientes/hora . Entonces r=20/5=4
                                                 donde n=1,2,....m
Sustituyendo datos P10=0.75
Asi, los cortes de pelo son en promedio 20(1-0.75)=5 cortes/hora.

b) Para calcular W=L/(l(1-Pm))

W=9.67/(20(1-0.75))=1.93 horas.

EJEMPLO 7
Una instalación de servicio consiste de una persona que puede atender un promedio de 2 clientes/h . Los tiempos de servicio son exponenciales.  Llega un promedio de 3 clientes por hora, y se supone que los tiempos entre llegadas son exponenciales. La capacidad del sistema es de 3 clientes.
a)    En promedio, ¿Cuántos clientes potenciales entran al sistema cada hora?
b)    ¿Cuál es la probabilidad de quien atiende esté ocupado?

Solución
l=3clientes/hora.   m=2clientes/hora     capacidad máxima del sistema=m=3
a)    r=3/2=1.5


`l=l(1-Pm)= l(1-P3)=3(1-0.4154)=1.75 clientes por hora.

b)    la probabilidad que este ocupado es Pocupado=1-Po

     por lo tanto que este ocupado es 1-0.123=0.876
estará ocupado el 87.6% del tiempo.

PROBLEMA 1. Propuesto
Una estación de llenado de cilindros de gas trabaja a una tasa promeido de 15 cilindros por hora. Los cilindros llegan a recibir servicio a una tasa promedio de 10 por hora. De acuerdo a las normas de seguridad de la empresa no se permite más de 4 cilindros en espera cuando uno esta siendo llenado para la información anterior calcule.
a)    El número de cilindros que se encuentran simultáneamente en la estación.
b)    El tiempo total de permanencia en el sistema
c)    La tasa promedio de perdida de clientes por aquellos cilindros que no pueden ingresar al sistema.
a) 1.53 cilindros   b) 0.16 horas   c)0.48 cilindros/hora.


MODELO M/M/k/DG/¥/¥

Se suponen tiempos de llegadas exponenciales, con rapidez l, que los tiempos de servicio son exponenciales con rapidez m, y que hay una sola cola de clientes esperando ser atendido por una de las k ventanillas.

EJEMPLO 8.
 Un banco tiene dos cajeros. Llegan al banco con un promedio de 80 clientes por hora y esperan en una sola cola para que los atiendan. El tiempo promedio que se necesita para atender a un cliente es 1.2 minutos. Suponga que los tiempos entre llegadas y los de servicio son exponenciales. Calcular.
a)    Número esperado de clientes en el banco.
b)    Tiempo esperado que pasa un cliente en el banco
c)    La fracción del tiempo que determinado cajero está desocupado.

Solución.
Identificando modelo M/M/2/*/¥/¥ , un modelo con llegadas y atención exponencial, con 2 servidores y capacidad ilimitada.
k: número de servidores
k =2 cajeros
l=80 clientes / hora
m = 1.2 minutos / cliente  al realizar la conversión  m = 50 clientes/minuto
                         <O> cajero 1
¥ O O O O O                              K = 2 cajeros (servidores)
                  <O> cajero 2

a)    El número esperado de clientes en el sistema es Ls

    para encontrar Ls hay tener primero
esta ecuación puede ser dividida en dos partes


teniendo Po buscar Ls



Ls= 4.44 clientes.  Esta cantidad de clientes se encuentran en el banco en promedio.

b)    El tiempo esperado que pasa el cliente en el banco seria Ws
Un cliente pasa en el banco un promedio de Ws=3.33 minutos.

c)    El tiempo que el cajero esta desocupado se define como la probabilidad de 0.
Po = 0.1111 = 11.11% del tiempo estará desocupado.

EJEMPLO 9

El gerente de un banco debe determinar cuántos cajeros deben trabajar los viernes. Por cada minuto que un cliente espera en la cola, el gerente supone que se incurre en un costo de 5 centavos de dólar. Al banco llegan un promedio de 2 clientes por minuto. En promedio, un cajero se tarda 2 minutos en tramitar la transacción de un cliente. Al banco  le cuesta 9 dólares por hora la contratación de un cajero. Los tiempos entre llegadas y los tiempos de servicio son exponenciales. Para reducir al mínimo la suma de los costos de servicio y los de demora, ¿Cuántos cajeros deben trabajar el banco los viernes?

Solución:
Por cada minuto que el cliente espera en la cola cuesta $0.05/min
Un cajero gana $9 /hora
k=?
l=2 clientes / minuto       m = 2 minutos / cliente

Pongo todo en las mismas unidades
Cliente en la cola $3/hora
Cajero $9/hora
l=120 clientes / hora      m = 0.5 clientes / minuto = 30 clientes / hora

Costo Total = Costo esperado de servicio / min + costo esperado de demora / min

Costo esperado de demora / min =(clientes esperados/min)(costo esperado de demora / cliente)

La anterior es para casos generales.
En especifico en este problema seria
CT=9k + Wq(3)(120)

r=l / km = 120/(30k)= 4/k<1  tiene que ser menor de 1 para que sea estado estable de lo contrario el sistema explotaría, por lo tanto nuestros servidores han de ser mayor que 5  K>=5.   Nótese que si fueran 4 servidores r=120/(4*30)=1 y esto no es menor que 1.  Al usar 5 servidores r=120/(5*30)<1 y si se cumple r=0.8

Para determinar si este es el menor costo se probaran con k=5 servidores.
Wq=2.22/120=0.018488 horas

Ahora ya se  puede determinar el costo total porque solo  faltaba Wq
CT = 9(5)+0.018488(3)(120)=$51.66 / hora.

Al comparar con k=6
CT = 9(6)+0.0047(3)(120) = $55.69/hora.
PROBLEMA 10.

Hay dos peluquerías con un peluquero cada una, y los establecimientos están en la misma calle. Cada peluquería puede tener un máximo de 4 personas, y todo cliente potencial que encuentre que está llena no esperará. El peluquero 1 cobra 11 dólares por corte y se tarda un promedio de 12 minutos para atender a un cliente. El peluquero 2 cobra 5 dólares por corte y se tarda un promedio de 6 minutos para terminar un corte. A cada peluquería llega un promedio de 10 clientes posibles por hora. Naturalmente, un cliente posible se transforma en un cliente real sólo si encuentra que la peluquería no esta llena. Si se supone que los tiempos entre llegadas son exponenciales, así como los tiempos de corte de pelo. ¿Cuál peluquero gana más?

Solución:
Identificar modelo:  M/M/1/*/4/¥/¥

Para el peluquero 1. 
m=12 min/cliente = 5 clientes / hora
l=10 clientes /hora                                        Gana $ 11  por corte
K= 1 peluquero
m= 4 clientes

Ganancia = $11(1-Po) m
(1-Po) = probabilidad que no este ocupado o sea que este realizando un corte.


Ganancia = $11(1-0.032)(5) = $53.24
El peluquero 1 gana $53.24 cada hora.

Para el peluquero 2. 
m= 6 min/cliente = 10 clientes /hora                          m= 4 clientes
l=10 clientes /hora                                                               k= 1 peluquero

Ganancia = $5(1-Po) m

r=10/10 = 1

Si utilizamos la formula

, por lo tanto hay que apoyarse en el siguiente concepto.

Cuando l=m las probabilidades del estado estable del sistema M/M/1/*/m/¥ son
  donde n=0,1,2,.... m
y todas la Pn deben ser iguales
Ganancia = $5(1-0.2)(10)=$40

El peluquero 2 ganara $40 por hora.

Conclusión:
            Por lo tanto el peluquero 1 ganara $13.24 mas por hora que el peluquero 2. (peluquero 1 = $53.24 ,  peluquero 2 = $40)





SISTEMA DE COLAS M/M/k/DG/m/¥


PROBLEMA 11


Una compañía de tractores que arenda sus vehículos para la agricultura y envía sus unidades al taller de mantenimiento de rutina cada 5,000 kilómetros, las instalaciones de mantenimiento están abiertas las 24 horas del día y son atendidos por tres cuadrillas de 3 hombres cada una. El tiempo que toma en dar el servicio a un tractor se distribuye exponencialmente con una media de 5 horas, los tractores llegan a las instalaciones siguiendo un proceso poisoniano con una tasa media de 12 por día sin embargo los conductores tienen instrucciones de no entrar a la instalación si ya hay 5 tractores en cuyo caso llegaran con el despachador para recibir nuevas instrucciones determine a) El tiempo esperado que un tractor permanece específicamente en el proceso de mantenimiento solo cuando esta en servicio. b) El costo total diario para la compañía si el costo improductivo es de Q5 por tractor por hora, y cada mecánico gana Q3.00 por hora .  c) La perdida diaria para la compañía si el costo de enviar a un tractor a las instalaciones y que regrese sin un servicio es de Q50.

Solución. 
Identificación del modelo  M/M/3/*/5/¥
k=3
m=5 horas /tractor                  l=12 tractores /hora              m = 5 tractores

Todo en las misma unidades
k=3      m=4.8 tractores/hora              l=12 tractores /hora              m = 5 tractores

a)    Ws –Wq
b)    (Q5/hora)(24horas)Ls  + (Q3/hora)(24horas)(9mecanicos)
c)    50(l-`l)

Como ya se determinó como se obtiene cada respuesta que me piden solo falta encontrar los datos como Ws, Wq, l, Ls.
    0 < n < k
    k £ n £ m

Pn=0    n > m


Ws=Ls/`l                               Wq=Lq/`l


Como vemos según las formulas hay que encontrar varios valores antes de las respuestas que buscamos.

Buscando las probabilidades
Con 0 < n < k   (0 < n < 3)

Con  k £ n £ m        3 £ n £ 5

como la suma de todas la probabilidades ha de ser 1 tenemos
Po + 2.5Po + 3.125Po + 2.6Po + 2.17Po + 1.81Po = 1
13.205Po=1
Po=0.076

Por lo tanto al tener Po se puede obtener el resto de probabilidades.
Po=0.076
P1=2.5Po=2.5(0.076)=0.19
P2=3.125Po=2.5(0.076)=0.2375
P3=2.6Po=2.6(0.076)=0.1976
P4=2.17Po=2.17(0.076)=0.1649
P5=1.81Po=1.81(0.076)=0.1376
Y la suma de todo esto da 1

Cálculo de Lq


Lq= 0.44 tractores

Cálculo de Ls


Ls = 2.59 tractores


`l=12(1-0.1376)=10.35 tractores al día.

Ws=2.59/10.35  = 0.25 días = 6 horas

Wq=0.44/10.35 = 0.0425 días = 1.02 horas

Ahora ya se tienen las respuestas a las preguntas.

a)    Ws –Wq = 0.25 día – 0.042 día = 0.2075 día = 4.98 horas
Tiempo en servicio exclusivamente = 4.98 horas.

b)    CT=(Q5/h)(24h/día)(2.59tractores) + (Q3/h)(24h/dia)(9mecanicos)
CT=310.8 + 648 = Q 526.8/día
            CT=Q526.8 al día.

c)    50(12-10.35)=82.5

No hay comentarios:

Publicar un comentario en la entrada