• Author / Uploaded
• LeNny Gonz Leon

• Categories
• Distribución de Poisson
• Distribución de probabilidad
• Simulación
• Servidor (Informática)
• Teoría estadística

Citation preview

5 FENOMENOS DE ESPERA 5.1

Introducción

Las líneas de espera son fenómenos muy comunes y que se observan en diversas actividades: la gente que va a un banco a cambiar un cheque, los clientes que van a pagar la mercancía que han comprado, las órdenes que llegan para ser procesadas a través de deferentes procesos, los conductores que llegan a una estación de servicio para tanguear sus autos, etc.. Para que exista una cola sólo se requiere que las llegadas y/o los servicios ocurran a intervalos irregulares. El proceso básico que se asume al formular un modelo de colas es el siguiente: Las unidades que requieren servicio llegan al sistema. Estas unidades entran al sistema y se unen a la "cola". En ciertos puntos en el tiempo, un elemento de la cola es seleccionado para recibir servicio, mediante alguna regla conocida como "la disciplina de la cola". Luego el “mecanismo de servicio" del sistema realiza a la unidad escogida el servicio requerido. La figura 5.1 representa esquemáticamente un proceso de espera.

Fuente 1 Fuente 2 Fuente

Centro de espera

Centro de servicio

Figura 5.1 Un sistema de colas. El gráfico representa un sistema que consta de: • • • • 5.2

Un centro de servicio con tres estaciones Una cola que alimenta las tres estaciones Dos fuentes suministradoras de clientes El flujo entre la fuente y la facilidad de servicio marca el proceso de llegadas. Características de los sistemas de colas

5.2.1 Componentes de los sistemas de colas Un sistema de espera tiene cuatro características: el proceso de llegadas, el mecanismo de servicio, la disciplina de la cola y el número de colas. Los clientes ò el proceso de llegadas El proceso de la demanda de servicios o de llegada de los clientes es, en general, un proceso estocástico y se describe en términos de la distribución de probabilidad del intervalo entre llegadas. Los factores que se necesitan para especificar el proceso de llegadas son: • • •

La fuente de llegadas El tipo de llegadas Los tiempos entre llegadas.

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

2

Algunos tipos de llegadas pueden ser: a)

b) c) d) e) f) g) h)

Llegadas poissonianas, según las cuales el número de clientes que llegan a requerir servicio es un proceso de Poisson, o equivalentemente, el tiempo entre llegadas de clientes sucesivos es exponencial. Llegadas regulares, a intervalos constantes. Llegadas en grupo. Llegadas regulares con impuntualidad. Llegadas en tiempos discretos. Llegadas no estacionarias. Se presenta cuando la tasa de llegada no es constante, sino que depende del instante de tiempo considerado Llegadas que siguen una distribución general. Otros aspectos relacionados con las llegadas son: • Los clientes se desaniman según el tamaño de la cola. • La fuente generadora de clientes puede ser infinita, y las llegadas suelen ser independientes del tamaño de la fuente. • La fuente puede ser finita y las llegadas dependen del número actual de individuos en la fuente. • Pueden llegar diferentes clases de clientes.

Las entidades que llegan al sistema de colas (llamadas unidades, órdenes, trabajos o clientes) poseen ciertas características que afectan al sistema de algún modo. Estas características pueden ser: • • •

•

•

Distribución de las llegadas o del tiempo entre llegadas. Es generalmente un proceso estocástico que gobierna el número de llegadas al sistema. Prioridad. Es alguna medida relativa del valor o importancia que tiene una unidad para el sistema, comparada con las otras unidades. Generalmente indica que tan rápido se va a mover una unidad a lo largo del sistema. Impaciencia. Este factor indica cuanto tiempo puede permanecer una unidad en el sistema sin ser atendida. La impaciencia puede describirse mediante las siguientes condiciones (i) Cuando una unidad rehúsa entrar a la cola porque es muy larga, (ii) cuando una unidad deja la cola después de esperar cierto período de tiempo y (iii) cuando una unidad deja una cola para pasar a otra. Otra característica que pueden tener las unidades es el tiempo que se van a gastar en la facilidad de servicio o tiempo de procesamiento (por ejemplo, órdenes de producción). Sin embargo, en la mayoría de los sistemas de colas este tiempo depende directamente de la facilidad de servicio. Llegadas en lotes, cuando una llegada al sistema puede consistir de varias unidades.

Es frecuente encontrar situaciones reales en que las llegadas no son estacionarias, pero se puede admitir que la tasa de llegada sea constante durante el intervalo de tiempo que sirve de base para estudiar el proceso de colas. Desde el punto de vista analítico, mas no de la simulación, es necesario suponer que la tasa de llegadas sea estacionaria. El mecanismo de servicio Las principales características del mecanismo de servicio son: a) b) c)

Número de estaciones de servicio y configuración de las mismas (serie o paralelo). Número de clientes que pueden ser atendidos en un instante cualquiera. La duración del servicio. La duración de un servicio es, en general, una variable aleatoria y se especifica de acuerdo con una distribución de probabilidad. Los tipos de servicio más comunes son: • Distribución exponencial. • Distribución erlang • Distribución gama • Servicio constante

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

•

3

Tiempo de servicio correlacionado con otros aspectos del sistema. Por ejemplo: servicio acelerado de acuerdo al número de personas que haya esperando.

La facilidad que sirve para atender las unidades puede tener varias características de interés. •

•

•

•

El proceso de servicio, esto es, la distribución de la duración de los servicios. Generalmente es un proceso estocástico cuya variación es inherente a la facilidad. Comúnmente se asignan los valores a los tiempos de servicio a medida que las unidades llegan a la facilidad, aunque puede suceder que estos tiempos se asignen cuando las unidades entran al sistema (órdenes de producción). Configuración del sistema. Cuando existen varias estaciones para prestar servicio, éstas pueden estar en paralelo (cuando todas prestan el mismo servicio, y una unidad pasa solamente por una estación) o en serie (cuando una unidad debe pasar por todas las estaciones) o puede haber una combinación serie paralelo. Disciplina del servicio. Esta característica indica si se puede o no interrumpir un servicio una vez este ha comenzado. Esta disciplina esta íntimamente ligada con la prioridad o importancia de las unidades, o con la necesidad del servicio de las unidades. Las unidades de mayor prioridad pueden exigir que la facilidad detenga su proceso actual para atenderlas. El sistema puede atender también en lotes a varias unidades simultáneamente.

La disciplina de la cola La disciplina de espera es el conjunto de reglas que especifican el orden de atención a las unidades. Los casos más comunes pueden ser: a)

b) c) d)

Disciplina FIFO o PEPS (Primeros el entrar, primero en salir). La primera unidad que llega, será la primera en ser atendida. Es el caso más general de selección de la unidad que pasa al servicio. Disciplina LIFO o UEPS (Últimos en entrar, primeros en salir). Los últimos clientes en llegar, serán los primeros en ser atendidos. Selección aleatoria de la unidad a ser atendida. Selección de acuerdo con la importancia del cliente, es decir, de acuerdo con la prioridad del cliente.

La línea de espera puede tener las siguientes características: • •

•

Longitud. Es decir, el número máximo de unidades que pueden esperar en frente de una estación. Número de colas. Cuando hay varias estaciones en paralelo puede existir una cola única que alimente todas las estaciones o puede existir una cola para cada estación. Además, en este último caso, cada unidad que llega puede escoger la cola en la cual esperará - la más corta, la más rápida, etc. Cuando las estaciones que prestan el servicio están ordenadas en serie, debe existir una cola para cada estación. La disciplina de la cola, la cual indica el método de ordenar las unidades en la cola y escoger la próxima que va a ser atendida. Existen varias posibilidades para escoger la disciplina de la cola De acuerdo al orden de llegada, o la que tenga la menor fecha de entrega, la que vaya a permanecer el tiempo mínimo en el servicio o hacer la selección en forma aleatoria.

El número de colas Cuando las estaciones de servicio están organizadas en serie, en general existe una cola en frente de cada estación. Cuando las estaciones de servicio están organizadas en paralelo, puede existir una cola para cada estación o puede existir una sola cola que alimente todas las estaciones. Además, el tamaño de cada una de las colas puede ser diferente.. Desde el punto de vista analítico, se supone que sólo existe una cola para todas las estaciones.

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

4

5.2.2 Objetivos El objetivo que se persigue al estudiar un sistema de colas puede ser muy variado. Generalmente se pretende definir cual debe ser la mejor configuración de tal forma que se minimice el costo de operación del sistema, o cual puede ser el costo de operación para una configuración dada. Entre las diferentes medidas que se pueden obtener para analizar el comportamiento de un sistema de colas están las siguientes: a) Tiempo medio que una unidad permanece en el sistema y la distribución de frecuencia del tiempo de permanencia en el sistema. b) Utilización de las estaciones de servicio. c) Número medio de unidades en el sistema y distribución del número de unidades del sistema. d) Tiempo medio que permanece una unidad en cada una de las colas y su distribución. e) Número medio de unidades en cada una de las colas y su distribución. f) Tiempo de inactividad de las estaciones de servicio, o porcentaje de utilización Los fenómenos de espera pueden estudiarse analíticamente o mediante la simulación. Sin embargo, sólo existen soluciones analíticas para unos casos particulares, generalmente cuando las llegadas y los servicios son exponenciales, y el sistema no es muy complejo. La simulación, por el contrario puede usarse para resolver cualquier problema de colas, por complejo que sea, no importa cual sea la distribución del tiempo entre llegadas y del tiempo de servicio. 5.2.3 Variables que deben considerarse al formular un modelo de colas En todo modelo hay tres tipos de variables que deben considerarse: Variables exógenas, de estado y endógenas. Con relación a los modelos de colas, cada una de estas categorías puede incluir las siguientes variables a) Variables exógenas o de entrada al sistema: Entre estas variables se encuentran las siguientes: • • • • • • • • b.

Variables de estado: • • • • • • •

c.

Tiempo entre llegadas al sistema. Tiempo de servicio en las diferentes estaciones. Prioridad de los clientes Número de estaciones de servicio Tasa de llegada de clientes al sistema Tasa de servicio de las diferentes estaciones o servidores Costos de prestación del servicio por unidad de tiempo Costo de espera o de inactividad por cliente

Tiempo que una orden cualquiera permanece en una cola. Tiempo que una estación esta inactiva, esperando la llegada de un cliente. Número de unidades en el sistema en cualquier instante. Número de unidades en la cada cola. Número de estaciones inactivas en cualquier instante. Número de órdenes recibiendo servicio en un instante cualquiera. Tiempo de permanencia de un cliente en el sistema

Variables endógenas: • • • • • •

Número medio unidades en el sistema. Número medio de unidades en cada una de las colas. Número medio de unidades recibiendo servicio. Número medio de estaciones inactivas. Tiempo medio que una unidad permanece en el sistema. Tiempo medio que una unidad permanece en cada una de las colas.

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

5

5.2.4 Clasificación de los modelos de colas Existe una clasificación estándar para identificar los modelos de colas, según sus características o propiedades. Esta clasificación se aplica a modelos de servicio único prestado por una o varias estaciones. Los modelos se identifican mediante la siguiente convención, en letras: Clasificación de Kendall: A/B/C: (D/E/F) donde las letras o campos se usan según la siguiente convención: A = En esta campo se coloca la distribución del tiempo entre llegadas B = En este campo se especifica la distribución del tiempo de servicio C = Se usa para identificar el número de estaciones de servicio, en paralelo D = En este campo se especifica la prioridad del sistema. Por defecto se supone que es FIFO. E =Indica la capacidad de sistema (Por defecto ise supone que es limitada) F = Tamaño de la fuente (Por defecto se asume que es ilimitada) Para especificar la distribución del tiempo entre llegadas y del tiempo se servicio se usa la siguiente convención: • • • •

M = Distribución exponencial G = Distribución general Ek = Distribución de Erlang D = Distribución constante

A veces la clasificación es simplemente A/B/C, y si es del caso se especifica con palabras alguna otra propiedad del sistema. Ejemplo: Ejemplo: Ejemplo: Ejemplo:

M/M/5: (FIFO/∞/∞) M/M/1: (FIFO/10/∞) M/M/s: (FIFO/M/M) M/G/1

A continuación se analizan diferentes modelos que son útiles para simular los fenómenos de espera. Sin embargo, previamente es necesario definir algunos parámetros y variables usados en los diferentes modelos, y las relaciones que son válidas para todos los modelos de canales en paralelo. 5.2.5 Parámetros, variables y relaciones básicas Parámetros Los principales parámetros usados en los modelos de colas son los siguientes • • • • •

S = Número de servidores o estaciones de servicio, en paralelo λ = Tasa media de llegada de clientes al sistema µ = Tasa media de servicio por estación m = Tamaño de la fuente (número máximo de clientes que pueden llegar al sistema) N = Capacidad del sistema (número máximo de clientes que pueden haber en el sistema en cualquier instante)

Variables de estado Las principales variables de estados usadas son: • • •

X(t) = n = Número de clientes que hay en el sistema en cualquier instante v = Número de clientes que hay en la cola en cualquier instante. Se supone que existe una cola que alimenta todas las estaciones de servicio a = Número de clientes que están recibiendo servicio en cualquier instante. También es equivalente al número de servidores ocupados

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

• •

6

r = Número de servidores inactivos Pn(t) = Probabilidad de que haya n personas en el sistema en el tiempo t

Medidas de congestión Se denominan medidas de congestión aquellas medias o indicadores que reflejan el comportamiento general del sistema a largo plazo, o en régimen permanente. Se refieren, por lo general, a las variables endógenas o de salida del sistema •

Pn = Probabilidad, a largo plazo, de que haya n personas en el sistema

•

L = Número esperado de clientes en el sistema

•

Lq = Número esperado de clientes en la cola

•

W = Tiempo esperado de permanencia de un cliente en el sistema

•

Wq = Tiempo medio de espera de un cliente antes de ser atendido (tiempo de permanencia en la cola)

•

Wq/Wq>0 = Tiempo medio de espera de un cliente en la cola, cuando tiene que esperar.

•

a = Número medio de clientes que reciben servicio

•

= Número medio de servidores ocupados

•

r = Número de servidores inactivos

•

P(Wq>0) = Probabilidad de que un cliente tenga que esperar

Relaciones básicas La variable de estado más importante es el número de clientes que hay en el sistema (n), ya que a partir de ésta se pueden derivar todas las demás, como se muestra a continuación. Número de clientes en la cola (V)

0 si n < s V = n − s si n ≥ s Número de clientes que están recibiendo servicio (a)

n si n < s a=  s si n ≥ s Número de estaciones o servidores inactivos (r)

s − n si n < s r=  0 si n ≥ s Además, dado que el número de clientes que hay en el sistema debe estar o recibiendo servicio o esperando ser atendidos, se debe cumplir que n=v+a Usando las relaciones anteriores y la definición de valor esperado, se tienen las siguientes expresiones: ∞

L = ∑ n Pn n =0 ∞

L q = ∑ (n − s) P n n =s

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

7

s −1

r = ∑ (s − n ) Pn n =0 s −1

∞

s −1

n −1

n =0

n =s

n =0

n =0

a = ∑ n Pn + s ∑ Pn = ∑ n Pn + s(1 −

∑ Pn )

P(Wq>0) = P(n≥s) = Probabilidad de esperar = Igualmente se debe cumplir que

n =v + a

∞

s −1

n= s

n =0

∑ P n =1 − ∑ P n

Otras relaciones (Fórmulas de Litlle) Las siguientes expresiones, cuya demostración en forma heurística se hará posteriormente, son válidas para todos los modelos de colas, si se calcula adecuadamente la tasa efectiva λef como la tasa media de entrada de clientes al sistema.

L = λ ef W L = λ ef W q q a=

λ ef µ

A continuación se analizan diferentes modelos que son útiles para analizar analíticamente los fenómenos de espera. 5.2.6 Función de costos. Costos a considerar Como ya se mencionó, el objetivo que se persigue al estudiar un sistema de colas puede ser muy variado. Generalmente se pretende definir cual debe ser la mejor configuración de tal forma que se minimice el costo de operación del sistema, o cual puede ser el costo de operación para una configuración dada. Por lo tanto, al realizar el análisis de los fenómenos de espera, es necesario considerar los diferentes costos involucrados en estos sistema, los cuales se resumen en:: a)

Costos de prestación del servicio

Este costo se puede referir al costo ocasionado por cada servidor por unidad de tiempo (Co), o al costo marginal de incrementar la tasa de servicio por unidad de tiempo Cu. En el primer caso para encontrar el costo total, el costo unitario se multiplica por el número de servidores (s), mientras que en el segundo caso se multiplica por la tasa de servicio (µ) Co = Costo por servidor/tiempo Cu = Costo de incrementar la tasa de servicio b)

Costo de espera o de inactividad por cliente

Este costo se refiere a lo que le cuesta a un cliente esperar mientras se lo atiende. En algunos casos este costo lo sufre directamente el sistema (tiempo de inactividad de las máquinas, tiempo ocioso de los empleados esperando las herramientas de trabajo), y en otros casos el sistema no asume directamente este costo, sino que lo sufre directamente el cliente, pero a la larga, su efecto se notará sobre el sistema, ya que si el sistema no reduce estos costos de inactividad de los clientes, éstos preferirán ir a otros sitios, y por lo tanto la demanda del sistema decaerá. Este costo lo denotaremos por Ci, y en general se puede aplicar o al número medio de unidades que esperan ser atendidas o al número medio de unidades en el sistema, dependiendo de los

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

8

elementos tendidos en cuenta la realizar su estimación. Ci = Costo de inactividad por cliente por unidad de tiempo c)

Costo total por unidad de tiempo.

Corresponde a la suma de los costos de operación y de inactividad. Se podría formular como: CT(s) = sCo + Ci L CT(µ) = uCu +Ci L 5.3

Sistema de colas con varias estaciones de servicio en paralelo

La figura 5.2 ilustra esquemáticamente un sistema de colas cuando existen varias estaciones idénticas que prestan el mismo servicio. Las unidades llegan al sistema, por lo general en forma aleatoria, entran si hay espacio disponible, esperan en una cola, si es del caso, antes de recibir el servicio, luego pasan al servicio y finalmente abandonan el sistema. Por lo general el tiempo de llegada y el tiempo de servicio son aleatorios. Si cuando el cliente llega hay una estación vacía o inactiva, pasa inmediatamente al servicio y es atendida, en caso contrario la unidad que llega se coloca en la cola y espera mientras llega su turno para ser atendida. Cuando una estación o servidor finaliza un servicio, y hay varias unidades esperando ser atendidas, la elección de la próxima unidad que va a recibir servicio puede realizarse de varias maneras, de acuerdo al orden de llegada, es decir, los primeros que llegan pueden ser los primeros en salir, o también puede usarse alguna otra disciplina, como la prioridad o la selección aleatoria.

1 2 s

Llegada

Línea de espera Centro de servicio Figura 5.2 Un sistema de estaciones en paralelo

5.3.1 Modelo M/M/s (abierto) o M/M/s (FIFO/∞ ∞/∞ ∞) Las principales suposiciones de este modelo son las siguientes: • • • • • •

Las llegadas siguen un proceso de Poisson con tasa λ, es decir, el tiempo entre llegadas de dos clientes sucesivos es exponencial una media de 1/λ Existen s servidores idénticos, con una tasa de servicio µ, y los tiempos de servicio son exponenciales Existe una cola que alimenta los s servidores La fuente de donde provienen los clientes es infinita El sistema tiene una capacidad ilimitada para atender los clientes La disciplina de la cola es FIFO, es decir, se atiende los clientes de acuerdo al orden de llegada.

5.3.1.1.

Formulación del modelo

Si analizamos las suposiciones del modelo, vemos que se ajusta a un “Proceso de nacimiento y muerte” ya que las llegadas al sistema (nacimientos) son exponenciales con tasa λ, y el tiempo entre salidas (muertes) también es exponencial, con las siguientes tasas:

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

9

λn = λ , n ≥ 0 µn = n µ , n < s = sµ, n ≥ s Para el cálculo de la tasa de salida (tasa de muerte) debe tenerse en cuenta que el próximo tiempo de salida está dado por el menor de los tiempos de servicio de los servidores que están ocupados atendiendo clientes. Como cada tiempo de servicio es exponencial con tasa µ, entonces el tiempo ente salidas del sistema es también exponencial con una tasa igual al número de servidores ocupados multiplicado por la tasa de servicio de cada servidor (µ). Si el número de clientes que hay en el sistema n es inferior al número de servidores s, entonces el número de servidores ocupados será n y el sistema atenderá todos los clientes con una tasa total nµ, pero si el número de clientes del sistema es mayor o igual al número de servidores, entonces el sistema atenderá s clientes con una tasa total sµ. Cálculo de las probabilidades límites Como se trata de un proceso de nacimiento y muerte, se pueden usar las ecuaciones respectivas dadas por

λ λ ... λ µ P

P=µ µ n

0

1

n −1

1

2

n

0

la cual se descompone de la siguiente manera: a) Para n < s

λ/ µ ) 2 ( λ λ P 2= P = P0 µ 2µ 0 2 λ/ µ ) n ( λ λ λ ... P = Pn= P 0 , (válida para n = 0) µ 2 µ nµ 0 n! λ P1= P 0, µ

b) Para n ≥ s

λ λ λ λ λ ... ... P µ 2 µ sµ sµ sµ 0 ( λ/ µ ) s λ/ sµ n − s = ( λ/ µ ) s n − s , donde φ = λ = φ ( ) P0 P0 s! s! sµ

Pn=

∞

Como los Pn forman una distribución de probabilidad se debe cumplir que

∑P n=0

1  ∑ P n = 1 = ∑  n=0 n = 0 n!  ∞

s −1

λ µ

n

s

∞ 1  λ   n −s  P 0 + ∑   φ P0 n = s s!  µ  

 s −1 1  λ  n 1  λ  s ∞  n − s    +   ∑ φ P 0=  ∑ s!  µ  n = s  n = 0 n !  µ  

−1

n

=1

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

 s −1 1  λ  n 1  λ  s 1     +   P 0=  ∑ n ! µ s ! µ 1 − φ  n = 0     

10

−1

λ 0) = P(n ≥ s ) = ∑ n= s

0

n− s

s

0

s!

s!

P (λ / µ ) ∑ϕ = s!(1 − ϕ )

s

∞

n−s

0

n= s

Probabilidad de no esperar s −1

P (λ / µ )

n =0

n!

P(W q = 0) = P (n < s ) = ∑

n

0

P (λ / µ ) =1−

s

0

s!(1 − ϕ )

Tiempo medio de espera en la cola E(Wq)

E (W q ) = =

∞

∫w

Wq f ( wq )dwq =

0

µ P0 (λ

/ µ)

(s − 1)!

s

µ P0 (λ

/ µ)

(s − 1)!

s

− sµ (1−ϕ )

∞

∫w wq e

wq

dwq

0

1 1 P0 (λ / µ ) = su (1 − ϕ ) su (1 − ϕ ) s!sµ (1 − ϕ ) 2

s

El tiempo medio de espera en la cola por lo general se denota por Wq Función de densidad del tiempo de espera en la cola dado que el cliente tiene que esperar f(wq/wq>0) Simplemente se calcula usando la definición de probabilidad condicional, como

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

f ( wq / wq > 0) =

f ( wq , wq > 0) P( wq > 0)

=

µ P0 (λ

15

/ µ) e µ ϕ w (s − 1)! P (λ / µ ) s

− s (1− )

q

s

0

s!(1 − ϕ )

− sµ (1−ϕ )

= sµ (1 − ϕ ) e

wq

Por lo tanto, la distribución condicional del tiempo de espera dado que hay que esperar se distribuye exponencialmente con parámetro (tasa ) sµ(1 - ϕ) Tiempo medio de espera en la cola dado que hay que esperar E(Wq/ Wq>0)

E ( wq / wq > 0) =

1 sµ (1 − ϕ )

Tiempo medio de permanencia en el sistema E(W) Se lo calcula como el tiempo medio de permanencia en la cola más el tiempo medio en el sistema

E (W ) = E (Wq ) +

1

µ

=

P (λ / µ )

s

0

s!sµ (1 − ϕ )

2

+

1

µ

El tiempo medio de permanencia en el sistema por lo general se denota por W 5.3.1.3. Fórmula de Little Las fórmulas de Little proporcionan una forma más sencilla de calcular algunas variables endógenas del sistema (tiempos medios en la cola y en el sistema, número medio de servidores ocupados), definiendo adecuadamente la tasa efectiva de entrada al sistema, de acuerdo con la situación analizada. Cálculo del ttiempo medio de espera y en el sistema W y Wq Sea θ un período de tiempo suficientemente grande. Considere los siguientes aspectos a) b) c) d) e) f) g)

Tasa media de llegada sistema por unidad de tiempo Tasa efectiva de entrada al sistema/tiempo Total de entradas al sistema durante el tiempo θ Tiempo de permanencia en el sistema por unidad Tiempo total gastado en el sistema por todas las unidades Número medio de unidades en el en sistema Tiempo total gastado en el sistema por todas las unidades

=λ =λef= λ = θ λef =W = θ λef W =L = θ L (θLq)

Como e) y g) son iguales se tiene que θ λef W = θ L ⇒ L = λef W ⇒ W = L/λef Para el caso del tiempo medio en la cola, basta con sustituir el tiempo medio en el sistema (W) por el tiempo medio en la cola (Wq), y el número medio de unidades en el sistema (L) por el número medio de unidades en la cola (Lq) para obtener la siguiente expresión:

θ λef Wq = θ Lq ⇒ Lq = λef Wq ⇒ Wq = Lq/λef

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

16

Cálculo de número medio de clientes en el servicio Sea θ un período de tiempo suficientemente grande. Sean a) b) c) d) e) f)

Tasa media de llegada al sistema por unidad de tiempo Tasa efectiva de entrada al sistema por unidad de tiempo Número total de entradas al sistema durante el tiempo θ Número medio de estaciones ocupadas Tasa media global de servicio del sistema Número medio unidades atendidas durante el tiempo θ

= = = = =

λ λef= λ θ λef a aµ

= aµθ

Como el “número medio de unidades atendidas” durante el tiempo θ debe ser igual en el largo plazo al “Número medio de unidades que entran” al sistema, entonces se tiene que ( c ) = ( f ) a µ θ = θ λef ⇒ a = λef / µ= λ / µ En resumen, para le modelo M/M s abierto, se tiene que

L = λ ef W = λ W L = λ ef W q = λ W q q a= 5.3.2

λ ef λ = µ µ

Modelo M/M/1 (abierto) o M/M/1 (FIFO/∞ ∞/∞ ∞)

Las principales suposiciones de este modelo son las siguientes: • • • • • •

Las llegadas siguen un proceso de Poisson con tasa λ, es decir, el tiempo entre llegadas de dos clientes sucesivos es exponencial una media de 1/λ Existe un solo servidor idénticos, con una tasa de servicio µ, y tiempos de servicio exponenciales Existe una cola que alimenta al servidor La fuente de donde provienen los clientes es infinita El sistema tiene una capacidad ilimitada para atender los clientes La disciplina de la cola es FIFO, es decir, se atiende los clientes de acuerdo al orden de llegada.

5.3.2.1.

Formulación del modelo

Este es un caso particular del modelo que acabamos de desarrollar, para s = 1, Por lo tanto, todas las expresiones desarrolladas son aplicables, sin embargo, algunas fórmulas se pueden simplificar. A continuación presentaremos la forma final que toman las principales fórmulas. De nuevo vemos que se trata de un “Proceso de nacimiento y muerte” ya que las llegadas al sistema (nacimientos) son exponenciales con tasa λ, y el tiempo entre salidas (muertes) también es exponencial, con las siguientes tasas: λn = λ, µn = µ

n ≥0 n ≥1

5.3.2.2. Cálculo de las probabilidades límites y medidas de desempeño Como se trata de un proceso de nacimiento y muerte, se pueden usar las ecuaciones respectivas dadas por

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

λ λ ... λ µ P

P=µ µ n

0

1

n −1

1

2

n

17

0

la cual se descompone de la siguiente manera:

λ P1= P 0 µ

() ()

λ 2 λλ = P0 P0 µ µµ λ n λλ λ λ n ... P 0= P 0 = φ P 0 , donde φ = , (válida para n = 0) Pn= µ µµ µ µ P 2=

∞

Como los Pn forman una distribución de probabilidad se debe cumplir que

∑P n=0

∞

∑P n=0

P ⇒

0

=1 = n

∞

∑φ P n=0

= 1 − φ =1−

P

n

=ϕ

n

n

0

∞

P ∑φ

= =

0

n=0

n

=

P

0

1−φ

, si φ =

n

=1

λ w0)

P(W q > w0) =

µ P0 (λ

/ µ)

s − sµ (1−ϕ )

(s − 1)!su (1 − ϕ ) e

w0 = ϕ

− µ (1−ϕ )

e

w0

Probabilidad de esperar P(Wq > 0)

P(W q > 0) =

P (λ / µ )

s

0

s!(1 − ϕ )

=ϕ

Probabilidad de no esperar s −1

P (λ / µ )

n=0

n!

P(W q = 0) = P(n < s ) = ∑

n

=1− ϕ

0

Tiempo medio de espera en la cola E(Wq)

E (W q ) = Wq =

Lq

λ

=

λ µ (µ − λ )

Función de densidad del tiempo de espera en la cola dado que el cliente tiene que esperar f(wq/wq>0)

f ( wq / wq > 0) = µ (1 − ϕ ) e

− µ (1−ϕ )

wq

Tiempo medio de espera en la cola dado que hay que esperar E(Wq/ Wq>0)

E ( wq / wq > 0) =

1 1 = µ (1 − ϕ ) ( µ − λ )

Tiempo medio de permanencia en el sistema E(W) Se lo calcula como el tiempo medio de permanencia en la cola más el tiempo medio en el sistema

E (W ) =

L

λ

= E (Wq ) +

1

µ

=

λ µ (µ − λ )

+

1

1 µ (µ − λ ) =

La tabla No 1 al final del documento presenta un resumen de las principales fórmulas para los modelos M/M/s y M/M/1 abiertos Ejemplo 1. Los clientes de un supermercado llegan a las cajas registradoras con una frecuencia promedio de 20 por hora, siguiendo una distribución de Poisson. El tiempo que un cliente gasta en cada caja se distribuye exponencialmente con una media de 10 minutos. Si el criterio del

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

19

supermercado es tal que se permita a un cliente esperar en la cola un promedio de 5 minutos, determine el número de cajas registradoras que se requieren. Solución. De acuerdo con la información disponible tenemos un modelo M/M/s (abierto), con los siguientes parámetros: λ = 20 clientes/hora 1/µ = 10 minutos/cliente ⇒ µ = 0.10clientes/minuto = 6 clientes/hora El objetivo es determinar cuantas cajas registradoras (s) se deben instalar de tal forma que el tiempo promedio de espera en la cola (Wq) sea menor o igual a 5 minutos. El número de cajas registradoras (s) debe ser tal que el sistema tenga un régimen estable, para lo cual se requiere que ϕ = λ / (sµ) sea menor de uno lo cual implica que s > λ / µ. Para nuestro caso se tiene que s>20/6 = 3.33, es decir, s ≥ 4. Por lo cual se deben ensayar valores de s iguales o superiores a 4, hasta encontrar el primer valor para el cual el tiempo medio de espera sea de cinco minutos o menos. Las fórmulas a emplear serían

(λ / µ ) W= P s!sµ (1−φ ) 2

q

 s −1 1  λ  1  λ  1   P =∑   +   − n ! µ s ! µ 1 φ   n = 0    n

s

0

y

s

−1

0

Para s = 4 se tiene:

  

P0 = 1 +

Wq =

( 20 / 6) 1

+

( 20 / 6) 2

2 +

( 20 / 6) 3!

3 +

( 20 / 6) 4!

4

  (1 − 20 / 24)  1

−1 =

1 42.9259

== 0.02131

( 20 / 6) 4 (0.02131) = 0.164 horas = 9.84 min utos 4!( 4)(6)(1 − 20 / 24) 2

Como el tiempo de espera es superior a 5 minutos, se deben ensayar s = 5. La tabla siguiente resume los resultados para s = 4 y s = 5. Número de cajas registradoras P0 Número medio de clientes en la cola Lq Tiempo medio de espera Wq (horas) Tiempo medio de espera Wq (minutos)

S=4 0.02131 3.2886 0.164 9.87

S=5 0.0318 0.6533 0.0327 1.96

Como para s = 5 el tiempo de espera es inferior a cinco minutos, entonces la solución es instalar cinco cajas registradoras. Ejemplo 2. Se va a contratar un mecánico para que repare unas máquinas que se descomponen a una tasa promedio de tres por hora. Las descomposturas se distribuyen en el tiempo de una manera que puede considerarse como Poisson. El tiempo no productivo de una máquina cualquiera se considera que le cuesta a la empresa $25 por hora. La compañía ha limitado la decisión a uno de 2 mecánicos, uno lento pero barato, el otro rápido pero caro. El primero de ellos pide $15 por hora; a cambio dará servicio a las máquinas descompuestas, de manera exponencial, a una tasa media de cuatro por hora. El segundo pide $25 por hora y compondrá las máquinas de manera exponencial a una tasa de seis por hora. Cuál de los mecánicos debe contratarse?. Dé toda la información que considere necesaria. Solución. De acuerdo con la situación planteada tenemos que escoger entre dos sistemas

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

20

alternativos de un servidor cada uno, y la decisión se basará en aquella alternativa que proporcione el mínimo costo esperado por hora. Cada alternativa es un sistema M/M/1 abierto. La función de costos está dada por CT(alternativa) = sCo + Ci L Donde s = 1 representa el número de mecánicos, Co representa el costo por mecánico por hora, y Ci es el costo de inactividad (tiempo no productivo) por máquina por hora, y se aplica al número medio de máquinas inactivas L, ya que una máquina está en estado no productivo tanto cuando está esperando ser reparada como cuando está siendo reparada. Información general: λ = 3 máquinas/hora, Ci = $25/máquina-hora Alternativa A (mecánico lento): µ = 4 máquinas/hora, Co = $15/mecánico-hora L = λ / (µ - λ) = 3/(4 - 3) = 3 máquinas⇒ Costo (A) = 15 + 25 x 3 = $90/hora Alternativa B (mecánico rápido): µ = 6 máquinas/hora, Co = $25/mecánico-hora L = λ / (µ - λ) = 3/(6 - 3) = 1 máquina⇒ Costo (B) = 25 + 25 x 1 = $50/hora Por lo tanto la administración deberá contratar al mecánico rápido, ya que garantiza un menor costo esperado por hora. Ejemplo 3. El administrador de un supermercado puede emplear a María o a Carmen. María quien presta servicio a una tasa exponencial de 20 clientes por hora, puede ser contratada a un costo de $12. por hora. Carmen quien da el servicio a una tasa exponencial de 30 clientes por hora, puede ser contratada a un costo de $ C por hora. La administración estima que, en promedio el tiempo del consumidor vale $4 por hora y que debe tenerse en cuenta en el modelo. Si los consumidores llegan a una tasa Poisson de 10 por hora, entonces: a) Cuál es el costo promedio si se contrata a María? b) Cuál es el costo promedio si se contrata a Carmen? c) Cuál es el valor máximo por hora que puede pagarse a Carmen? Solución. Se deja como problema propuesto. Ejemplo 4. Un problema de optimización. Los trabajos llegan a un taller de acuerdo con una distribución de Poisson a razón de 80 trabajos por semana. Una máquina automática representa el cuello de botella del taller. Se estima que un aumento unitario en la tasa de producción de la máquina costará US$ 250 por semana. Los trabajos demorados normalmente dan como resultado la pérdida de clientes, y se estima un costo de 500 dólares por trabajo por semana. Determine la tasa de producción óptima de la máquina con base en la información dada. Solución. El objetivo del problema es determinar cual debe ser la tasa de servicio del sistema µ tal que se minimice el costo total de de producción más el costo por pérdida de los clientes,dado por CT(µ) = µCo + Ci L Como se trata de un modelo M/M/1 abierto, el número medio de clientes en el sistema L está dado por L = λ/(µ-λ), por lo tanto la función costos queda definida como:

CT (µ = = µ C o +

λC i µ−λ

Como la tasa de servicio es una variable continua, para encontrar el valor de µ que minimice el costo total, se puede derivar la expresión del costo total con respecto a µ, igualar a cero y despejar el valor de µ.

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

21

λC i λC i dCT(µ) = Co − =0 ⇒ µ = λ ± 2 dµ Co (µ − λ) Como para que el sistema tenga un régimen estable se requiere µ > λ, entonces la tasa çoptima de servicio estará dada por:

µ* = λ +

λC i Co

Para verificar que el valor anterior corresponda a un mínimo, se encuentra la segunda derivada, se reemplaza el valor de µ por el valor óptimo y se verifica que la segunda derivada sea positiva.

d 2 CT(µ) dµ

2

=

2λC i (µ − λ)

3

=0 ⇒ µ = λ ±

λC i Co

Reemplazando el valor óptimo de µ se obtiene que

d 2 CT(µ) dµ 2

 λC  = 2λC i / i   Co 

3/ 2

>0

lo cual compraba que el valor hallado de µ efectivamente corresponde a un mínimo. Para nuestro caso tenemos que: λ = 80 trabajos/semana, Co = $250/trabajo-semana, Ci = $500/trabajo-semana

µ* = 80 +

80(500) = 92.6 250

Ejemplo 4. Un problema de optimización numérica (Métodos de búsqueda) .En las instalaciones de un almacén de herramientas, las solicitudes de cambio de herramientas ocurre de acuerdo con una distribución de Poisson, con una media de 17.5 solicitudes por hora. Cada empleado puede manejar un promedio de 10 solicitudes por hora. El costo de contratar un nuevo empleado para las instalaciones es de US $12 por hora. El costo de pérdida de producción por máquina es aproximadamente US $50 por hora. Determine el número óptimo de empleados para las instalaciones. 5.4 Modelos de capacidad finita La principal diferencia con los modelos analizados anteriormente estriba en que el sistema tiene una capacidad finita K, por lo tanto, si un cliente llega y encuentra que en el sistema ya hay K clientes, entonces no puede entrar al sistema. 5.4.1 Modelo M/M/s capacidad finita (K) - Modelo M/M/s (FIFO/K/∞ ∞) La suposición adicional con respecto al modelo M/M/s (abierto) analizado previamente es que la siguiente: • El sistema tiene una capacidad limitada K para atender los clientes • Existen s servidores idénticos, con una tasa de servicio µ, y tiempos de servicio exponenciales. 5.4.1.1. Formulación del modelo Analizadas las suposiciones del modelo, vemos que se ajusta a un “Proceso de nacimiento y

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

22

muerte” con las siguientes tasas. Cálculo de la tasa de nacimiento (tasa de entrada) λn Si cuando un cliente llega al sistema encuentra que aún existe espacio (n < K) entonces el cliente entra al sistema, pero si el sistema se encuentra lleno (n = K) entonces abandona el sistema y desiste de entrar. λn

=λ =0

si n < K si n = k

Cálculo de la tasa de muerte (tasa de salida) µn Si el número de clientes que hay en el sistema n es inferior al número de servidores s, entonces el sistema atenderá todos los clientes con una tasa total nµ, pero si el número de clientes del sistema es mayor o igual al número de servidores, entonces el sistema sólo podrá atender s clientes con una tasa total sµ. µn = n µ sµ

si n < s si s ≤ n ≤ K

Por lo tanto, la diferencia básica con el modelo M/M/s abierto está en que el número máximo de clientes en el sistema es K (se supone que K ≥ s), por lo tanto las probabilidades estarán limitadas a este valor. Cálculo de las probabilidades límites Como se trata de un proceso de nacimiento y muerte, se pueden usar las ecuaciones respectivas dadas por

λ λ ... λ µ P

P=µ µ n

0

1

n −1

1

2

n

0

la cual se descompone de la siguiente manera: a) Para n ≤ s

λ P1= P 0, µ

P 2=

2 λ λ 1 λ = P   P µ 2µ 0 2  µ  0

n λ λ λ 1 λ ... P =   P 0 , (válida para n = 0) Pn= µ 2 µ nµ 0 n!  µ  b) Para s ≤ n ≤ K

λ λ λ λ λ ... ... P µ 2 µ sµ sµ sµ 0 s n− s s 1 λ λ 1  λ  n− s λ =     = φ P0 P 0 , donde φ =   s!  µ   sµ  s!  µ  sµ

Pn=

∞

Como los Pn forman una distribución de probabilidad se debe cumplir que

∑P n=0

n

=1

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

1  ∑ P n = 1 = ∑  n=0 n = 0 n!  s −1

K

λ µ

23

n

s

K 1  λ   n−s  P 0 + ∑   φ P0 n = s s!  µ  

 s −1 1  λ  n 1  λ  s K  n −s  =   +   ∑ φ ∑ P0 s!  µ  n = s  n = 0 n !  µ  

−1

 s −1 1  λ  n 1  λ  s  1 − φ K − s +1      +    P 0=  ∑   µ µ − φ n ! s ! 1  n = 0       =

 s −1 1  λ  n 1  λ  s   ∑   +   ( K − s + 1 )  s!  µ   n = 0 n !  µ  

−1

,ϕ =

λ ≠1 sµ

−1

,ϕ =

λ =1 sµ

Cuando la capacidad es finita, siempre existen las probabilidades límites, aunque el número medio de clientes que lleguen al sistema sea mayor que el número medio de clientes que el sistema está en capacidad de atender, ya que el sistema limita el número de clientes que pueden entrar, y que por lo tanto serán atendidos. 5.4.1.2. Medidas de congestión Número medio de clientes en la cola Lq Está definido como: K

K

Lq = ∑ ( n − s ) P n = ∑ n= s

(λ / µ ) (n − s)

n=s

s

s!

φ P

0

∑ (n − s)φ K

Como se puede observar, el término

(λ / µ ) φ = s

n− s

s!

n − s −1

P ∑ (n − s)φ K

0

n=s

se puede representar como la derivada

n= s

∑φ K

de la siguiente

n−s

n − s −1

con respecto a ϕ. Es decir,

n= s

K d K n − s d  1 − φ K − s + 1  = ∑ (n − s ) φ n − s − 1 = ∑ φ  dφ n = s dφ  1− φ n =s   K − s (1 − φ)(K − s + 1) φ (−1) − (1 − φ K − s + 1)(−1) = (1 − φ) 2 1 + (K − s) φ K − s + 1−(K − s + 1) φ K − s = (1 − φ) 2

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

⇒ Lq=

(

(λ / µ ) s φP 0 1 + (K − s) φ K − s + 1−(K − s + 1) φ K − s 2 s!(1 − φ)

24

)

Probabilidad de entrar al sistema Un nuevo cliente entra al sistema si éste no se encuentra lleno, es decir, si el número de clientes que hay en el sistema en el momento de su llegada es inferior a su capacidad (n < K). Por lo tanto K −1

P(entrar ) = P(n< K ) = ∑ Pn =1− Pk n =0

La probabilidad de no entrar es la probabilidad de que el sistema se encuentre lleno, es decir

(λ / µ ) =

s

P(no entrar ) = P (n = K ) = Pk

s!

ϕ P K −s

0

Tasa efectiva de entrada al sistema = λef La tasa de llegada de clientes al sistema es λ, sin embargo no todos pueden entrar al sistema; sólo entran aquellos clientes que encuentran espacio disponible. Recordemos que λn representa la tasa a la cual se incrementa el número de clientes del sistema (tasa de entrada), y está dada por: λn = λ

si n < K

=0

si n = k

Entonces la tasa media de entrada al sistema o tasa efectiva está dada por: K

K −1

K −1

n =0

n =0

n =0

λ ef = ∑ λ n Pn = ∑ λ Pn + 0 Pn =λ ∑ Pn = λ (1 − Pk ) Una breve explicación de la fórmula anterior es la siguiente: La proporción clientes que entran al sistema es 1 - PK, por lo tanto la tasa efectiva de entrada al sistema es la tasa de llegada λ multiplicada por la proporción de clientes que logran entrar al sistema dada por 1 - PK, es decir la tasa efectiva de entrada es λef =λ (1 – PK) Número medio de clientes en servicio Se puede calcular usando la fórmula de Little, trabajando con la tasa efectiva, como:

λ (1 − P K ) λ a = ef = µ µ Número medio de servidores inactivos

r = s − a = s − λ ef / µ Número medio de clientes en el sistema

L = Lq + a

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

25

Tiempo medio de permanencia en la cola y en el sistema Se puede calcular usando la fórmula de Little, trabajando con la tasa efectiva, como

L = λ ef W ⇒ W =

L

=

λ ef

L λ(1 − P K )

Lq L = λ ef W ⇒ W = q q q λ(1 − P K ) 5.4.2 Modelo M/M/1 capacidad finita (K) - Modelo M/M/1 (FIFO/K/∞ ∞) Este es un caso particular del modelo que acabamos de desarrollar, para s = 1. Por lo tanto, todas las expresiones desarrolladas son aplicables, sin embargo, algunas fórmulas se pueden simplificar. A continuación presentaremos la forma final que toman las principales fórmulas 5.4.2.1. Formulación del modelo Se trata de un “Proceso de nacimiento y muerte” con las siguientes tasas: λn = λ 0 µn = µ

si n K Pn= 0 K

Como los Pn forman una distribución de probabilidad se debe cumplir que

∑ P n =1

n =0

K

∑

n=0

P n =1 = =

K

∑φ

n=0

P 0(K

n

P0=P0

+ 1)

K

∑φ

n=0

si ϕ =

n

=

 1 − φ K +1  P 0  1 − φ   

λ =1 µ

si ϕ =

λ ≠1 µ

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

 1− φ   = P 0  K +1  1− φ  1 = K +1

si ϕ =

λ ≠1 µ

si ϕ =

λ =1 µ

26

Para que existan las probabilidades límites no se requiere que λ/µ sea menor que uno. 5.4.2.2. Medidas de desempeño del sistema a)

Número medio de clientes en la cola Lq

Lq = b)

φ2

)

(

K K −1 P 0 1 + ( K − 1) φ − K φ 2 (1 − φ )

Número medio de clientes en servicio

λ (1 − P K ) λ a = ef = µ µ c)

Número medio de servidores inactivos

r = s − a = 1 − λef / µ d)

Número medio de clientes en el sistema

L = Lq + a e)

Tiempo medio de permanencia en la cola y en el sistema

Se puede calcular usando la fórmula de Little, trabajando con la tasa efectiva, como

L = λ ef W ⇒ W =

L λ ef

=

L λ(1 − P K )

Lq L = λ ef W ⇒ W = q q q λ(1 − P K ) La tabla No 3 al final del documento presenta un resumen de las principales fórmulas para los modelos M/M/s y M/M/1 con capacidad finita (K) Ejemplo. Una pequeña barbería operada por un solo peluquero tiene una capacidad para dos personas. Los consumidores llegan a una tasa Poisson de 3/hora y los tiempos de servicio son variables aleatorias exponenciales con media de 1/4 de hora. Cual es: a) b) c) d)

El número medio de personas en la barbería? La proporción de clientes que entran a la barbería? El tiempo promedio gastado en la barbería por cada cliente que entra? En cuánto se incrementarían sus entradas brutas por día si i) el peluquero trabajara un 50% más rápido, ii) si la capacidad de la barbería fuera de 3?

Ejemplo. El gerente de una emisora local está planeando un programa telefónico especial de cinco días para la recolección de fondos para una causa especial, y desea determinar el tipo de sistema telefónico que debe alquilar para recibir las promesas de donaciones. Para ello ha recibido seis cotizaciones diferentes que proporcionan 15 o 20 líneas telefónica, con diferentes

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

27

opciones de líneas de espera. Además, de campañas anteriores se ha estimado que cada donación es de US 450, y que un 80% de los contribuyentes potenciales que no logran comunicarse, vuelven a llamar posteriormente. Se ha estimado que el proceso de llamadas es Poisson con una tasa de 150 llamadas por hora, y la tasa de servicio por línea telefónica es de 12 llamadas / hora. Cuál sistema se debe alquilar? Sistema 1 2 3 4 5 6

5.5

Número de teléfonos 15 20 15 20 15 20

Llamadas en espera 0 0 5 5 10 10

Costo total (US$/día) 150 220 180 264 225 330

Modelos de fuente finita

Existen algunas situaciones en las cuales el número de elementos que hay en la fuente que suministra los clientes para el sistema de colas es limitada, y por lo tanto, el número de clientes que pueden estar solicitado servicio en cualquier instante también lo es. Además, la tasa a la cual los clientes llegan a solicitar servicio depende de cuantos elementos haya en la fuente. Es decir, si en la fuente hay muchos elementos, entonces la tasa a la cual los clientes llegan al sistema será mayor que si en la fuente sólo quedaran unos pocos elementos. Un caso típico de este sistema es un taller que tiene varias máquinas idénticas que fallan de vez en cuando y requieren servicio de uno o varios mecánicos disponibles para estas eventualidades. Otro caso puede ser el de una sala de computadores que presta servicio a un grupo de estudiantes, y que está a cargo de un monitor encargado de resolver las dudas que los estudiantes tengan, 5.5.1

Modelo M/M/s Fuente finita (N) ó Modelo M/M/s: (FIFO/N/N)

La suposición básica adicional que se tiene en este modelo con relación a los anteriores es que la fuente de donde provienen los clientes es limitada, es decir, el número máximo de clientes que puede haber en el sistema es finito (N). Como ya se mencionó., un caso típico es un taller que tiene N máquinas idénticas que requieren servicio de vez en cuando, y existen s mecánicos para prestarles el servicio requerido. Las suposiciones básicas del modelo son: • • • • • •

Fuente de donde provienen los clientes es finita, de un tamaño N, lo cual implica que el número de clientes (máquinas) en el sistema está limitado a N. El tiempo entre requerimientos de servicio por cada cliente (máquina) es exponencial con tasa λ. Existen s servidores idénticos (mecánicos) para atender los clientes (máquinas) que llegan al sistema El tiempo de servicio de cada clientes exponencial con media 1/µ. Existe una sola cola que alimenta los s servidores La disciplina de la cola FIFO, según el orden de llegada al sistema.

La figura siguiente ilustra esquemáticamente el sistema

1 3

1

2

2 4 s N-n

Población

Cola

Servicio

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

28

5.5.1.1. Formulación del modelo Si n representa el número de unidades que hay en el sistema, entonces N - n representa el número de unidades que permanecen en la fuente. Si el tiempo que cada unidad tarda en requiere servicio es exponencial con tasa λ, y si en la fuente hay N – n unidades, entonces el tiempo del próximo requerimiento de servicio será el mínimo entre los tiempos de requerimientos de servicio de las N – n unidades, y este tiempo es exponencial con tasa (n – n)λ Tiempo de próxima llegada = mínimo (T1, T2,...,TN-s) → Exp{(N-n)λ} Por lo tanto, este modelo se puede representar como un proceso de nacimiento y muerte” con las siguientes tasas: λn = (N-n)λ

0≤n 0)

Wq W q /W q > 0 W =W s

ρ

µ(1 − ρ) e−µ (1−ρ)w q (µ − λ) e−(µ−λ ) w q

ρ2

s P 0 (λ / µ ) s! (1 − ρ ) µs(1 − ρ ) e− µs (1− ρ ) wq ( µs − λ ) −( µs −λ ) wq

e

λ = λ (1 − ρ ) µ ( µ − λ )

(λ / µ ) s ρ P 0 s! (1 − ρ ) 2 λ

1

1 sµ − λ

µ −λ

1 L 1 = = Wq + µ−λ λ µ

(λ / µ) s ρ P 0 +1/µ s!(1 − ρ) 2 λ

L, L q , a , r = Número medio de: Unidades en el sistema, en la cola, en el servicio (o estaciones ocupadas) y estaciones inactivas, respectivamente. W q , W = Tiempos medios de permanencia en la cola y en el sistema, respectivamente. ND = No Disponible

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

47

Tabla No 2. Teoría de Colas. Modelos exponenciales Fuente finita Medida Pn

P0

Lq r

M/M/s Fuente Finita

C n P0 , C 0=1, ρ=λ / sµ a )Para n < s (M − n + 1)λ Cn = Cn − 1 nµ b)Para s ≤ n ≤ M C n = C n − 1 ρ(M − n + 1)

M  n∑= 0C n 

M/M/1 Fuente Finita

Cn P 0 C0=1 Cn = Cn −1 ρ(M − n + 1) ρ=

λ µ

−1

M

∑ (n − s) Pn

n =s s −1

−1

M  n∑= 0C n  M − (1 − P0)

1+ ρ ρ

P0

∑ (s − n ) Pn

n =0

a

L

( M − L )λ µ Lq + a

1 – P0

s − r=

M −

1 − P0

M

ρ

∑ n Pn

n =0 ND

ND

ND

ND

s −1

1 – P0

f ( w q / w q > 0)

n =0 ND

ND

Wq

Lq

f ( wq ) P(W q > w0) P(n≥s) = P(wq>0)

1−

∑ Pn

( M − L)λ

W q /W q > 0

 1 1 M  − − 1 µ  1 − P0  λ

Wq P(n ≥ s)

W =W s

L ( M − L)λ

Wq 1 − P0 1 M  1  − µ  1 − P0  λ

L, L q , a , r = Número medio de: Unidades en el sistema, en la cola, en el servicio (o estaciones ocupadas) y estaciones inactivas, respectivamente. W q , W = Tiempos medios de permanencia en la cola y en el sistema, respectivamente. ND = No Disponible

B. Calderón. “Procesos Estocásticos. Fenómenos de espera”

48

Tabla No 3. Teoría de Colas. Modelos exponenciales de capacidad finita Medida

M/M/1

(λ/µ) P0 ,

1− ρ

ρ P0 =ρ n

M/M/s n

n

1− ρ

Pn

N +1

n! n −s

(λ/µ)sρ

0≤n≤N ρ =λ/µ

P0

s! 1− ρ

N +1

N −1 2   − ρ P0 1 − ρ   2 N −1  (1− ρ) ( N − 1)(1 − ρ) ρ 

Lq =V

P0 =

r

1− ρ

a

1 – P0

Lq (1 − P N )λ

Wq W q /Wq > 0

  N −s ρ 

µ

N +1

L,L q , a , r =

ρ

λ (1 − P N )

( N + 1) ρ ρ − N +1 1− ρ 1− ρ

P(n≥s) = P(wq>0)

}

N −s s  − ( λ/µ ) ρ P 0 1 −  2  s! (1 − ρ ) ( N − s )(1 − ρ)

µ

L= n

W =W s

{

−1

s−a

N −1

ρ λ(1 − P N ) 1−

,s ≤ n ≤ N

 s −1 (λ/µ) n (λ/µ) s 1−ρ N − s +1  + ∑  n ! s ! ( 1 − ρ ) n = 0  

1− ρ P0

λ sµ

n 0)

Wq

λ

Wq

W q /Wq > 0

W =W s

λ µ

ρ

2

λ

1

1

Wq + µ

Modelos con prioridades: 1) Modelos con prioridades relativas M/M/s

W p = A.

1

2) Modelo con prioridades absolutas M/M/1

1

+ , p = 1,2,..., P

B p −1 B p µ  sµ − λ s −1 ρ j  A =k!  + sµ  s  ∑ j! j = 0 ρ  

W p=

1/ µ

B p B p −1

, p = 1,2,..., P P

L p =W p λ p , λ = ∑ λ i i =1

p

P B0 = 1, λ = ∑ λ i , i =1

L,L q , a , r =

B p =1 −

∑ λi

i =1

su

, p = 1,2,..., P

Número medio de: Unidades en el sistema, en la cola, en el servicio (o estaciones

ocupadas) y estaciones inactivas, respectivamente.

W q , W = Tiempos medios de permanencia

en la cola y en el sistema, respectivamente. N (K) = Capacidad del sistema. ND = No Disponible.