Distribución Estacionaria de una Cadena de Markov en Tiempo Continuo

En la Teoría de Probabilidades, una Cadena de Markov en Tiempo Continuo (CTMCContinuous Time Markov Chain) corresponde a un modelo matemático donde una variable aleatoria toma valores en un espacio finito y donde el tiempo en que la variable se encuentra en un determinado estado adopta valores reales no negativos que siguen una Distribución Exponencial. Dicha característica denominada Propiedad de No Memoria determina que el comportamiento a futuro del proceso estocástico depende sólo del estado actual y no del comportamiento histórico de dicha variable.

En este contexto a continuación presentamos un ejemplo del cálculo de una Distribución Estacionaria o de Largo Plazo para una Cadena de Markov en Tiempo Continuo. Nuestro objeto de análisis en términos intuitivos es similar al caso de la Distribución Limite de una Cadena de Markov en Tiempo Discreto, es decir, estimar en el largo plazo (e independiente de la distribución inicial) cuál es la probabilidad que el proceso estocástico se encuentre en uno de los N estados posibles.

Distribución Estacionaria Cadena de Markov en Tiempo Continuo

Aves arriban a uno de los 4 alimentadores (comederos) ubicados en el patio de una casa de acuerdo a un Proceso de Poisson con tasa promedio de un ave por minuto. Si todos los alimentadores (4 en total) están ocupados, el ave se va sin esperar que un alimentador se desocupe y en caso contrario el ave come de un alimentador por un tiempo determinado que sigue una Distribución Exponencial con media de un minuto. Se desea modelar la cantidad de alimentadores o comederos ocupados X(t) a través de una Cadena de Markov en Tiempo Continuo.

Sea X(t) la variable aleatoria que representa el número de alimentadores ocupados. En este contexto X(t) representa el número de entidades presentes en los alimentadores en el instante t, cuyo tamaño aumenta con la llegada (nacimiento) de entidades (aves) o disminuye con la salida (muerte) de entidades (aves).

Al existir 4 alimentadores, la cantidad de éstos que se pueden encontrar ocupados en un instante del tiempo son 0, 1, 2, 3 o 4, (X(t)\in\begin{Bmatrix}0,1,2,3,4\end{Bmatrix}t\geq 0) según se representa en el diagrama de transición a continuación:

proceso nacimiento y muerte ctmc

Los valores en las flechas que unen los estados 0 con el 1, 1 con el 2, 2 con el 3 y 3 con el 4, corresponden a la tasa de llegada λ (tasas de nacimiento) que en este caso corresponde a \lambda_{i}=1[\frac{ave}{minuto}] para todo i.

Por otro lado las tasas de servicio (salida o muerte) µ corresponderán a \mu_{i}=i\mu, de modo que de esta forma se obtienen las tasas indicadas en la parte inferior del diagrama en aquella transiciones que consisten en disminuir el número de alimentadores ocupados. Notar que en este caso \mu=1[\frac{ave}{minuto}] .

La cadena propuesta es claramente irreducible (es decir, todos los estados se comunican entre sí y existe por tanto una única clase de estados), de modo que podemos estimar una distribución estacionaria o de largo plazo. En este sentido la ecuación correspondiente es:

ecuaciones largo plazo ctmc

Donde por cierto \sum\pi _{i}=1. La Matriz General G, que tiene como característica que la sumatoria de los valores en sus respectivas filas corresponde a cero, a su vez queda definida por:

matriz g ctmc

De este modo se obtiene el siguiente sistema de ecuaciones:

sistema ecuaciones largo plazo ctmc

La solución del sistema corresponde a:

soluciones ecuaciones ctmc

Que representa para cada estado la proporción del tiempo (en el largo plazo) que cada uno de ellos se encontrará ocupado, por ejemplo, se espera que en el 36,92% del tiempo no se encuentren alimentadores (comederos) ocupados.

Los resultados anteriores han sido corroborados haciendo uso de una planilla de Simulación de Sistemas de Espera disponible en el Libro Investigación de Operaciones de H. Taha. Notar que se ha establecido un límite de 4 entidades (en este caso aves) para el sistema:

simulación ctmc

El número de alimentadores ocupados en el largo plazo son:

alimentadores ocupados largo plazo

Se concluye que en el largo plazo se encuentren ocupados 0,9845 comederos. Cabe destacar que según el resultado de la simulación anterior L_{s}=0,98462 y por cierto la diferencia respecto a nuestro resultado obedece exclusivamente a la cantidad de decimales utilizados para la estimación.

Comparación de un Servicio General y Específico para la Atención de Clientes (Teoría de Colas)

En los sistemas de atención de público se suelen encontrar distintos esquemas o configuraciones en las que se organiza la espera de los clientes antes de ser atendidos. Se pueden observar casos donde los clientes se ordenan en una fila para ser atendidos por un servidor, otros donde los clientes se ordenan en una fila común y luego son atendidos por un servidor en la medida que este disponible (esquema frecuente en las cajas rápidas en los supermercados). En este contexto el siguiente artículo evaluaremos un sistema de atención general y uno específico, comparando desde un punto de vista cuantitativo el desempeño de cada caso a través de la simulación del comportamiento de la Línea de Espera.

Un banco pequeño en un centro comercial tiene dos cajeros. Uno maneja al público general y uno maneja a los clientes regulares. Cada tipo de clientes llega con una media de 20 por hora (para una proporción de la llegada total de 40 clientes por hora). El tiempo de servicio para ambos cajeros promedia 2 minutos (sigue una distribución exponencial, es decir, se verifica el cumplimiento de la Propiedad de Falta de Memoria o Amnesia de la Distribución Exponencial). El gerente del banco está considerando cambiar el orden de atención para permitir que cada cajero pueda manejar ambos tipos de clientes. Debido a que los cajeros tendrían que manejar ambos tipos de trabajos, sus eficiencias disminuirían a un tiempo de servicio de 2,2 minutos por cliente. ¿Se debe cambiar al nuevo esquema de atención?.

Servicio General y Específico para la Atención de Clientes

El servicio específico implica que cada cajero atiende de forma exclusiva un tipo de clientes sin existir colaboración entre los mismos. Una representación esquemática de dicho escenario se muestra a continuación:

servicio-especifico-teoria-

En el artículo Simulación de una Línea de Espera M/M/1 (Teoría de Colas) en Excel se detalla el procedimiento para obtener los indicadores de desempeño de una línea de espera con un servidor, donde el tiempo entre llegadas de los clientes se distribuye exponencial, al igual que los tiempos de servicios. En el ejemplo la atención para cada tipo de clientes muestra los siguientes resultados:

servicio-general-mm1

El número esperado de clientes en el sistema Ls es de 2 clientes (en este caso la fila y atención para cada tipo de cliente constituye un sistema), el número esperado de clientes en la fila Lq es de 1,333, el tiempo promedio que un cliente esta en el sistema Ws es 0,1 horas, es decir, 6 minutos. Finalmente el tiempo que un cliente esta en la fila Wq es de 0,06667 horas (4 minutos).

En el caso de un servicio general, en donde existe colaboración entre los servidores, la capacidad de cada uno de ellos baja a µ=60/2,2[clientes/hora].

servidor-general-teoria-de-

Los indicadores de desempeño son: Ls=3,17307 (considerando los 2 tipos de clientes, es decir, en promedio se espera tener menos clientes en el sistema que el caso del servicio específico donde en total se esperan, en promedio, 4 clientes en el sistema); el tiempo promedio que un cliente esta en el sistema Ws es 0,07933 horas (aprox 4,76 minutos); el número esperado de clientes en la fila Lq es de 1,7064 y el tiempo que en promedio un cliente esta en la fila Wq es de 0,04266 horas (2,56 minutos).

mm1-servicio-general

Se concluye que si bien en nuestro ejemplo la capacidad de cada uno de los servidores baja al atender los 2 tipos de clientes, esto se ve compensado por el efecto de colaboración que se genera entre los mismos, lo que permite bajar el tiempo que en promedio un cliente esta en el sistema y en la fila. Estos aspectos claramente son valorados desde la perspectiva de los clientes y deberían ser tomados en cuenta al momento de decidir si se cambia el esquema original de atención de clientes.

¿Quieres tener el archivo Excel con la planilla de Simulación de una Línea de Espera utilizada en este ejemplo?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Simulación de una Línea de Espera M/M/1 (Teoría de Colas) en Excel

Un sistema de espera M/M/1 es aquel que considera un servidor, con tiempos exponenciales de servicio y entre llegadas de clientes. La implicancia que los tiempos de servicio se distribuyan exponencial es que existe una preponderancia de tiempos de servicio menores al promedio combinados con algunos pocos tiempos extensos. Un ejemplo de ello es lo que sucede en las cajas de los bancos donde la mayoría de las transacciones requieren poco tiempo de proceso por parte del cajero, no obstante algunas transacciones más complejas consumen bastante tiempo. Por otra parte afirmar que los tiempos entre llegadas se distribuyen exponencial implica una preponderancia de tiempos entre llegadas menores que el promedio en combinación con algunos tiempos más extensos. Lo anterior tiene relación con la aleatoriedad del proceso de llegada de clientes que permite establecer la Propiedad de Falta de Memoria o Amnesia de la Distribución Exponencial y con los conceptos presentados en el artículo Qué son las Líneas de Espera (Teoría de Colas), donde queda en evidencia que la formación de las colas o filas esta asociada a la variabilidad del sistema.

En este contexto consideremos la siguiente notación, donde valores usuales para A y B son M (distribución exponencial) y G (distribución general).

notacion-de-kendall

El siguiente ejemplo disponible en el artículo Qué es la Ley de Little y su aplicación en el análisis de Líneas de Espera, nos permitirá ilustrar la simulación en Excel del comportamiento de un sistema de espera M/M/1.

Simulación de una Línea de Espera M/M/1

Ejemplo: Un pequeño banco está considerando abrir un servicio para que los clientes paguen desde su automóvil. Se estima que los clientes llegarán a una tasa promedio de 15 por hora (λ=15). El cajero que trabajará en la ventanilla puede atender a los clientes a un ritmo promedio de uno cada tres minutos (es decir, la capacidad promedio del servidor es de µ=20). Suponga que el patrón de llegadas es Poisson y el patrón de servicios es Exponencial.

Al hacer uso de la Planilla de Fórmulas de Sistema de Espera, se alcanzan los resultados que se resumen en la imagen a continuación.

salida-planilla-linea-de-es

Con esto la utilización promedio del servidor es de un 75%, el número esperado de clientes en el sistema Ls es 3, el número esperado de clientes en la fila Lq son 2,5, el tiempo promedio que un cliente permanece en el sistema Ws (espera más atención) son 0,2 horas (0 12 minutos) y el tiempo promedio que un cliente permanece en la fila Wq (esperando su atención) es de 0,15 horas (o 9 minutos).

Otra alternativa es simular el comportamiento de la línea de espera con configuración M/M/1 haciendo uso de Excel. Para ello ingresamos en la planilla Queueing_Simulator el número de servidores (1), la distribución para el tiempo entre llegadas (exponencial con media de 4 minutos, esto es, si llegan en promedio 15 clientes por hora, entonces en promedio llega un cliente cada 1/15 de hora o equivalentemente cada 4 minutos) y una distribución para el tiempo de servicio también exponencial con media de 3 minutos. Finalmente ingresamos el número de llegadas que se desea simular (arbitrariamente se ha seleccionado 100.000 llegadas para evaluar un comportamiento del sistema en el largo plazo) y luego Run Simulation.

simulacion-mm1-excel

Se puede apreciar que los resultados obtenidos en la columna F son (aproximadamente) similares a los obtenidos utilizando los resultados que establece la Ley de Little. Por ejemplo, el número esperado de clientes en el sistema L es 3,0157; el número esperado de clientes en la fila Lq es 2,2665; el tiempo esperado que un cliente permanece en el sistema W son 12,0612 minutos y así sucesivamente.

Importante: Los resultados mostrados anteriormente corresponden a aquellos obtenidos con una simulación tipo. Si una vez alcanzados los resultados presionamos nuevamente Run Simulation obtendremos cambios en los resultados los cuales de todos modos deberían aproximar los resultados de la Ley de Little bajo el supuesto de considerar un número significativo de llegadas a simular.

¿Quieres tener el archivo Excel con la Simulación de una Línea de Espera M/M/1 utilizada en este ejemplo?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Cómo calcular la Utilización de un servidor, Tiempo de Espera y Tiempo de Flujo de una Línea de Espera

El siguiente artículo aborda de forma práctica cómo calcular algunos indicadores de desempeño básico de un sistema de espera con un único servidor. Entre ellos, la tasa promedio de flujo (λ), la capacidad promedio del servidor (μ), la utilización promedio del servidor (ρ=λ/μ), el tiempo promedio que un cliente esta en la fila esperando ser atendido (Wq) y el tiempo promedio que un cliente esta en el sistema (Ws), esto incluyendo tanto los tiempos de espera como los tiempos de atención.

Considere un proceso de línea de espera que tiene un servidor y una única fila (caja de atención) como el que se describe a continuación. Se opera bajo una regla de prioridad FIFO, es decir, se atienden los clientes por orden de llegada. Los registros tomados para la primera hora de trabajo de un día en particular son los siguientes:

linea-de-espera-1-servidor
tabla-llegada-de-clientes-l

Por ejemplo el Cliente 3 llega exactamente 9 minutos después de iniciada las actividades y una vez que comienza su atención (por el servidor) el tiempo requerido para completar ésta es de 7 minutos. Es decir, el tiempo de flujo de este cliente es de 11 minutos, donde 7 minutos corresponde a la atención en sí y los 4 minutos restantes son los minutos que debe esperar que se desocupe el servidor (que esta atendiendo al Cliente 2). Con este ejemplo queda en evidencia que contar con la información de las primeras 3 columnas se puede completar la información de las columnas restantes.

Ahora desarrollaremos algunos cálculos básicos que permite tener una noción del desempeño de esta línea de espera.

Calcular la tasa de flujo promedio (λ) y la capacidad promedio del servidor (μ): Pasaron 12 clientes por el servicio en 60 minutos, luego la tasa de flujo promedio es λ=0,2[clientes/minuto]=12[clientes/hora]. El tiempo de servicio promedio es 4[min] (corresponde al promedio de los valores de la columna Ws), luego la capacidad promedio es μ=1[clientes]/4[min]=0,25[clientes/min]=15[clientes/hora].

La utilización promedio del servidor (ρ): Esto permite estimar que porcentaje del tiempo en promedio el servidor esta ocupado (atendiendo clientes). En nuestro ejemplo ρ=λ/μ=12[clientes/hora]/15[clientes/hora]=80%. Notar que de este ejemplo sencillo se obtiene una importante conclusión que se puede extrapolar a otros sistemas de espera más complejos:

Si existe variabilidad en las llegadas y/o atenciones, entonces hay colas (aunque de largo finito). A pesar de que λ<μ, es decir, de que ρ<1. Si λ>μ el sistema es inestable (colas infinitas). Es decir, las colas se deben a la variabilidad y no al hecho de que λ>μ (ρ>1).

El tiempo promedio que un cliente pasa en el sector de caja (espera + atención) (Ws): El tiempo promedio que un cliente pasa en el sector de caja corresponde al promedio de los valores de la columna “Tiempo Sistema”: Ws=8[min].

Evalúe si el proceso de llegada es estacionario: Un proceso de llegada es estacionario si el número esperado de clientes que llegan al sistema sólo depende de la longitud del intervalo de tiempo y no del tiempo de inicio del intervalo. Lo anterior por simple inspección no se cumple para el ejemplo. En este sentido se puede apreciar que en la primera media hora de observación han llegado 8 clientes (de un total de 12 clientes en la hora completa). Por tanto el sistema tiene un requerimiento mayor en el primer período de observación.

clientes-acumulados

El gráfico anterior corrobora esta conclusión. Se muestra la cantidad de clientes (acumulados) que han llegado al sistema al cabo de un determinado tiempo. La línea roja mostraría teóricamente el comportamiento de un proceso estacionario, donde un cliente llega exactamente cada 5[min]. La línea azul muestra el comportamiento real del proceso en estudio.