Tema teoria de colas

MODELOS Y SIMULACIÓN SISTEMAS DE COLAS

1 JAQUELINE MARTINEZ CALDERON

TEMA 6

TEORÍA DE COLAS

6.1. INTRODUCCIÓN

Las "colas" son un aspecto de la vida moderna que nos encontramos continuamente en nuestras actividades diarias.

En el contador de un supermercado, accediendo al Metro, en los Bancos, etc., el fenómeno de las colas surge

cuando unos recursos compartidos necesitan ser accedidos para dar servicio a un elevado número de trabajos o

clientes.

El estudio de las colas es importante porque proporciona tanto una base teórica del tipo de servicio que podemos

esperar de un determinado recurso, como la forma en la cual dicho recurso puede ser diseñado para proporcionar un

determinado grado de servicio a sus clientes.

Debido a lo comentado anteriormente, se plantea como algo muy útil el desarrollo de una herramienta que sea

capaz de dar una respuesta sobre las características que tiene un determinado modelo de colas.

6.2. DEFINICIONES INICIALES

La teoría de colas es el estudio matemático del comportamiento de líneas de espera. Esta se presenta, cuando los

“clientes” llegan a un “lugar” demandando un servicio a un “servidor”, el cual tiene una cierta capacidad de

atención. Si el servidor no está disponible inmediatamente y el cliente decide esperar, entonces se forma la línea de

espera.

Una cola es una línea de espera y la teoría de colas es una colección de modelos matemáticos que describen

sistemas de línea de espera particulares o sistemas de colas. Los modelos sirven para encontrar un buen compromiso

entre costes del sistema y los tiempos promedio de la línea de espera para un sistema dado.

Los sistemas de colas son modelos de sistemas que proporcionan servicio. Como modelo, pueden representar

cualquier sistema en donde los trabajos o clientes llegan buscando un servicio de algún tipo y salen después de que

dicho servicio haya sido atendido. Podemos modelar los sistemas de este tipo tanto como colas sencillas o como un

sistema de colas interconectadas formando una red de colas. En la siguiente figura podemos ver un ejemplo de

modelo de colas sencillo. Este modelo puede usarse para representar una situación típica en la cual los clientes

llegan, esperan si los servidores están ocupados, son servidos por un servidor disponible y se marchan cuando se

obtiene el servicio requerido.

El problema es determinar qué capacidad o tasa de servicio proporciona el balance correcto. Esto o es sencillo, ya

que un cliente no llega a un horario fijo, es decir, no se sabe con exactitud en que momento llegarán los clientes.

También el tiempo de servicio no tiene un horario fijo.

Los problemas de “colas” se presentan permanentemente en la vida diaria: un estudio en EEUU concluyó que, por

término medio, un ciudadano medio pasa cinco años de su vida esperando en distintas colas, y de ellos casi seis

meses parado en los semáforos.

En la teoría de la formación de colas, generalmente se llama sistema a un grupo de unidades físicas, integradas de

tal modo que pueden operar al unísono con una serie de operaciones organizadas. La teoría de la formación de colas

busca una solución al problema de la espera prediciendo primero el comportamiento del sistema. Pero una solución

al problema de la espera consiste en no solo en minimizar el tiempo que los clientes pasan en el sistema, sino

también en minimizar los costos totales de aquellos que solicitan el servicio y de quienes lo prestan.



La teoría de colas incluye el estudio matemático de las colas o líneas de espera y provee un gran número de

modelos matemáticos para describirlas.

Se debe lograr un balance económico entre el costo del servicio y el costo asociado a la espera por ese servicio

La teoría de colas en sí no resuelve este problema, sólo proporciona información para la toma de decisiones

6.2.1. Objetivos de la Teoría de Colas

Los objetivos de la teoría de colas consisten en:

Identificar el nivel óptimo de capacidad del sistema que minimiza el coste global del mismo.

Evaluar el impacto que las posibles alternativas de modificación de la capacidad del sistema tendrían en el coste

total del mismo.

Establecer un balance equilibrado (“óptimo”) entre las consideraciones cuantitativas de costes y las cualitativas

de servicio.

Hay que prestar atención al tiempo de permanencia en el sistema o en la cola: la “paciencia” de los clientes

depende del tipo de servicio específico considerado y eso puede hacer que un cliente “abandone” el sistema.

6.2.2. Elementos existentes en un modelo de colas

1. Fuente de entrada o población potencial: Es un conjunto de individuos (no necesariamente seres vivos)

que pueden llegar a solicitar el servicio en cuestión. Podemos considerarla finita o infinita. Aunque el caso

de infinitud no es realista, sí permite (por extraño que parezca) resolver de forma más sencilla muchas

situaciones en las que, en realidad, la población es finita pero muy grande. Dicha suposición de infinitud no

resulta restrictiva cuando, aún siendo finita la población potencial, su número de elementos es tan grande

que el número de individuos que ya están solicitando el citado servicio prácticamente no afecta a la

frecuencia con la que la población potencial genera nuevas peticiones de servicio.

2. Cliente: Es todo individuo de la población potencial que solicita servicio. Suponiendo que los tiempos de

llegada de clientes consecutivos son 0<t1<t2<..., será importante conocer el patrón de probabilidad según el

cual la fuente de entrada genera clientes. Lo más habitual es tomar como referencia los tiempos entre las

Generalmente el administrador se encuentra en un dilema

Asumir los costos derivados de tener largas colas Asumir los costos derivados de prestar un buen servicio



llegadas de dos clientes consecutivos: consecutivos: clientes consecutivos: T{k} = tk - tk-1, fijando su

distribución de probabilidad. Normalmente, cuando la población potencial es infinita se supone que la

distribución de probabilidad de los Tk (que será la llamada distribución de los tiempos entre llegadas) no

depende del número de clientes que estén en espera de completar su servicio, mientras que en el caso de que

la fuente de entrada sea finita, la distribución de los Tk variará según el número de clientes en proceso de

ser atendidos.

3. Capacidad de la cola: Es el máximo número de clientes que pueden estar haciendo cola (antes de

comenzar a ser servidos). De nuevo, puede suponerse finita o infinita. Lo más sencillo, a efectos de

simplicidad en los cálculos, es suponerla infinita. Aunque es obvio que en la mayor parte de los casos reales

la capacidad de la cola es finita, no es una gran restricción el suponerla infinita si es extremadamente

improbable que no puedan entrar clientes a la cola por haberse llegado a ese número límite en la misma.

4. Disciplina de la cola: Es el modo en el que los clientes son seleccionados para ser servidos. Las disciplinas

más habituales son:

La disciplina FIFO (first in first out), también llamada FCFS (first come first served): según la cual se

atiende primero al cliente que antes haya llegado.

La disciplina LIFO (last in first out), también conocida como LCFS (last come first served) o pila: que

consiste en atender primero al cliente que ha llegado el último.

La RSS (random selection of service), o SIRO (service in random order), que selecciona a los clientes de

forma aleatoria.

5. Mecanismo de servicio: Es el procedimiento por el cual se da servicio a los clientes que lo solicitan. Para

determinar totalmente el mecanismo de servicio debemos conocer el número de servidores de dicho

mecanismo (si dicho número fuese aleatorio, la distribución de probabilidad del mismo) y la distribución de

probabilidad del tiempo que le lleva a cada servidor dar un servicio. En caso de que los servidores tengan

distinta destreza para dar el servicio, se debe especificar la distribución del tiempo de servicio para cada

uno.

6. La cola, propiamente dicha, es el conjunto de clientes que hacen espera, es decir los clientes que ya han

solicitado el servicio pero que aún no han pasado al mecanismo de servicio.

Canal

Canales de servicio en serie

Canales de servicio en paralelo



El sistema de la cola: es el conjunto formado por la cola y el mecanismo de servicio, junto con la disciplina de la

cola, que es lo que nos indica el criterio de qué cliente de la cola elegir para pasar al mecanismo de servicio. Estos

elementos pueden verse más claramente en la siguiente figura:

Un modelo de sistema de colas debe especificar la distribución de probabilidad de los tiempos de servicio para cada

servidor.

La distribución más usada para los tiempos de servicio es la exponencial, aunque es común encontrar la distribución

degenerada o determinística (tiempos de servicio constantes) o la distribución Erlang (Gamma).

6.3. NOTACIÓN DE KENDALL

Por convención los modelos que se trabajan en teoría de colas se etiquetan

Fuente de Entrada

Llegada de un Cliente

Cola

Disciplina de la Cola

Sistema de la Cola

Mecanismo de Servicio

Servicio

Canal

Canales de servicio en serie

Canales de servicio en paralelo

___/___/___

Distribución de tiempo entre

llegadas

Distribución de tiempos de

servicio

Número de servidores



Con el objeto de verificar si una situación determinada del sistema de líneas de espera se ajusta o no a un modelo

conocido, se requiere de un método para clasificar las líneas de espera. Esa clasificación debe de responder

preguntas como las siguientes:

1. ¿ El sistema de líneas de espera tiene un solo punto de servicio o existen varios puntos de servicio en

secuencia?

2. ¿Existe solo una instalación de servicio o son múltiples las instalaciones de servicio que pueden atender a

una unidad?

3. ¿ Las unidades que requieren el servicio llegan siguiendo algún patrón o llegan en forma aleatoria?

4. ¿El tiempo que requieren para el servicio se da en algún patrón de o asume duraciones aleatorias de tiempo?

Por lo general, las tasas de llegada y de servicio no se conocen con certidumbre sino que son de naturaleza

estocástica o probabilística. Es decir los tiempos de llegada y de servicio deben describirse a través de

distribuciones de probabilidad y las distribuciones de probabilidad que se elijan deben describir la forma en que e

comportan los tiempos de llegada o de servicio.

En teoría de líneas de espera o de colas se utilizan tres distribuciones de probabilidad bastante comunes, están se

mencionan a continuación:

Markov

Determinística

General

La distribución de Markov, en honor al matemático A.A. Markov quien identifico los eventos "sin memoria", se

utiliza para describir ocurrencias aleatorias, es decir, aquellas de las que puede decirse que carecen de memoria

acerca de los eventos pasados.

Una distribución determinística es aquella en que los sucesos ocurren en forma constante y sin cambio.

La distribución general sería cualquier otra distribución de probabilidad. Es posible describir el patrón de llegadas

por medio de una distribución de probabilidad y el patrón de servicio a través de otra.

Para permitir un adecuado uso de los diversos sistemas de líneas de espera, kendall, matemático británico elaboro

una notación abreviada para describir en forma sucinta los parámetros de un sistema de este tipo. En la notación

Kendall un sistema de líneas de espera se designa como:

A / B / C

En donde

A = se sustituye por la letra que denote la distribución de llegada.

B = se sustituye por la letra que denote la distribución de servicio.

C = se sustituye por el entero positivo que denote el numero de canales de servicio.

La notación kendall también utiliza M = Markoviano, D = determinística, G = General, por ejemplo un sistema de

líneas de espera con llegadas aleatorias, servicio determinístico y tres canales de servicio se identificará en notación

Kendall como:



M / D / 3

En todos los casos se supone que solo existe una sola línea de entrada.

Es evidente que existen otros atributos aparte de los que se analizaron antes y que deben de tomarse en

consideración como por ejemplo:

El tamaño de la población de los que provienen los elementos que ingresan al sistema de líneas de espera.

La forma en que las unidades llegan para ingresar al sistema de líneas de espera; por ejemplo, una por una o

en forma de grupos.

Si las unidades rechazan o no debido a la longitud de la línea de espera y no ingresan al sistema.

Si las unidades se arrepienten y abandonan el sistema después de haber aguardado un tiempo en la fila.

Si existe o no espacio suficiente para que todas las unidades que llegan aguarden en la fila.

Los modelos de Líneas de espera que se analizarán son los siguientes:

a) MODELO M / M / 1

Este sistema trata de una distribución de llegada Markoviano, tiempo de servicio Markoviano, y un servidor.

Llegadas aleatorias (M / M / 1)

En las situaciones cotidianas es fácil encontrar ejemplos de llegadas aleatorias, puesto que las llegadas serán

aleatorias en cualquier caso en la que una de ellas no afecte a las otras. Un ejemplo clásico de llegadas aleatorias

son las llamadas que arriban a un conmutador telefónico o un servicio de emergencia.

Se ha determinada que las ocurrencias aleatorias de un tipo especial pueden describirse a través de una distribución

discreta de probabilidad bien conocida, la distribución de Poisson. Este tipo especial de llegadas aleatorias supone

características acerca de la corriente de entrada. En primer lugar, se supone que las llegadas son por completo

independientes entre sí y con respecto al estado del sistema.

En segundo lugar la probabilidad de llegada durante un periodo específico no depende de cuando ocurre el periodo,

sino más bien, depende solo de la longitud del intervalo. Se dicen que estas ocurrencias carecen de "memoria".

Si conocemos el número promedio de ocurrencias por periodo, podemos calcular las probabilidades acerca del

número de eventos que ocurrirán en un periodo determinado, utilizando las probabilidades conocidas de la

distribución de Poisson.

En particular, existe un promedio de l llegadas en un periodo, T, la probabilidad de n llegadas en el mismo periodo

esta dado por:

P[n llegadas en le tiempo T] =

Por ejemplo si existe un promedio de 6 llegadas aleatorias por hora, la probabilidad de que haya solo 3 llegadas

durante una hora esta dada por:

P[6 llegadas en le tiempo en una hora] = = 0.0892



Tiempo de servicio aleatorio (M / M / 1)

Al igual que las llegadas aleatorias, la ocurrencia de tiempos de servicios aleatorios, carentes de memoria, es suceso

bastante común en las situaciones cotidianas de líneas de espera. Y al igual que las llegadas aleatorias los tiempos

de servicio carentes de memoria se describen a través de una distribución de probabilidad.

La diferencia entre las llegadas aleatorias y los tiempos de servicio aleatorios es que estos se describen a través de

una distribución continua en tanto que las llegadas se describen a través de una distribución de Poisson, que es

discreta. Si la duración de los tiempos de servicio es aleatoria, la distribución exponencial negativa describe ese

tipo de servicio. Si la m es la tasa promedio de servicio entonces la distribución esta dada por:

F(t) = m e-m t

Es posible emplear esta formula para calcular la probabilidad de que el servicio sea mas prolongado que alguna

duración especificada de tiempo T. En la siguiente figura se representa es modelo.

Características de operación

Para calcular las características de operación de una cola M / M / 1, primero debemos de observar que sí l = tasa

promedio de llegadas y m = tasa promedio de servicio, entonces l debe de ser menor que m . Si esto no ocurriera el

promedio de llegadas sería superior al número promedio que se atienden y el número de unidades que están

esperando se volvería infinitamente grande. Si hacemos que r = l / m puede denominarse a r como factor de

utilización. Este valor es la fracción promedio de que el sistema este ocupado, también sería el número promedio de

unidades que están siendo atendidas en cualquier momento. En términos de probabilidad tendríamos que:

Pw = probabilidad de que el sistema esté ocupado.

Entonces la probabilidad de que el sistema no esté trabajando, o esté vacío, P0, puede obtenerse por medio de:

A partir de esto podemos obtener la probabilidad de que haya n unidades en el sistema, Pn, mediante:

en donde n es cualquier entero no negativo. Este importante resultado nos permite calcular las características de

operación de las líneas de espera.

La primera característica de operación que calculamos es el numero promedio de unidades que se encuentran en el

sistema, ya sea esperando o siendo atendidas. Denominaremos a este número promedio de unidades promedio, L.

Entonces tenemos que:

Con estos valores obtenidos podemos calcular el número promedio de unidades que esperan ser atendidas, Lq.

Dado que L es el número de unidades que están esperando o están siendo atendidas, y r es el número promedio de

unidades que están siendo atendidas en algún momento dado entonces:



L = Lq + r

A partir de esto es fácil observar que

Lq = L - r

O también podríamos decir que

Ahora examinaremos el tiempo de espera. Utilizaremos W para representar el tiempo promedio o esperado que una

unidad se encuentra en el sistema. Para encontrar W, observaremos que se L el número esperado de unidades de en

le sistema y l es el número promedio de unidades que llegan para ser atendidas por periodo, entonces el tiempo

promedio de cualquier unidad que llega debe estar en le sistema está dado por:

W = tiempo promedio de una unidad en el sistema

De manera similar, el tiempo esperado o promedio que una unidad tiene que esperar antes de ser atendida, Wq, esta

dado por:

En la siguiente figura se representa este modelo.

b) MODELO M / M / S

Este modelo supone llegadas y tiempos de servicio aleatorios para canales de servicio múltiples, teniendo las

mismas consideraciones que le modelo de canal único de servicio (M / M / 1), excepto que ahora existe una sola fila

de entrada que alimenta los canales múltiples de servicio con iguales tasas de servicio.

El cálculo de las características de la línea de espera para el modelo M / M / S es lago mas complicado que los

cálculos para el caso de canal único, y dado que primordialmente nos interesa las implicaciones de estas

características mas que las formulas necesarias para calcularlos, nos apoyaremos en le uso de tablas elaboradas a

partir de estas formulas para hacer los cálculos.



Características de operación.

En el modelo M / M / S, si m es la tasa promedio de servicio para cada uno de los S canales de servicio, entonces ya

no se requiere que m > l , pero Sm debe ser mayor que l para evitar una acumulación infinita de líneas de espera. En

el caso de M / M / S, la característica que se utilizará para hacer los demás cálculos es la probabilidad de que el

sistema esté ocupado. En otras palabras, la probabilidad es de que haya S o más unidades en el sistema. En este caso

todos los canales de servicio se estarán utilizando y por ello se dice que el sistema está ocupado. Esto de puede

representar como:

P(Sistema ocupado) =

Y lo podemos calcular por medio de la siguiente ecuación:

P(Sistema ocupado) =

En donde Po estará representado por

Con las ecuaciones anteriores podemos calcular los demás datos que requiera el sistema. En el modelo M / M / S,

al igual que el modelo M / M / 1, se tiene que L = Lq + r, pero aquí utilizaremos el valor P(sistema ocupado) para

calcular Lq:

Lq = P(sistema ocupado) x

Ahora calcularemos el valor L

Lq = P(sistema ocupado) x

En el caso de M / M / S, al igual que en el modelo M / M / 1, W = L / l y Wq = Lq / l , por ello se tiene que

En la siguiente figura se representa este modelo.



MODELO M / G / 1

Descripción

Sistema de líneas de espera con llegadas aleatorias, distribución general de los tiempos de servicio (para el cual se

supone conocida la desviación estándar), un canal de servicio y una línea de espera.

En este modelo las llegadas se distribuyen de acuerdo con la distribución de Poisson, al igual a los casos anteriores,

pero los tiempos de servicio no necesariamente se distribuyen de acuerdo con la distribución exponencial negativa.

Si consideramos el caso en que solo existe un solo canal, estamos considerando el caso M / G / 1, es decir, llegadas

de tipo Markov, tiempo de servicio general y un canal de servicio.

La razón por la que podemos considerar el caso M / G / 1 es que las formulas que se utilizan para calcular sus

características de operación son bastantes simples. Al igual que en el caso M / M / S, no es posible calcular en

forma directa el numero esperado de unidades en el sistema (L). Para esto primero debe de calcularse el numero de

unidades que están esperando a ser atendidas (Lq), y utilizar este resultado para calcular el valor de L. Para calcular

el valor de Lq debemos de conocer le valor de la desviación (s ) estándar de la distribución que distingue los

tiempos de servicio. Si no se conoce la distribución de los tiempos de servicio no es posible determinar las

características de operación.

Ahora si conocemos la desviación estándar y la media de la distribución de los tiempos de servicio, puede obtenerse

formula para el valor de Lq a partir de la siguiente ecuación.

Si utilizamos Lq podemos determinar el valor de L, por medio de la siguiente ecuación:

Al igual que las características de operación de los modelos M / M / 1 y M / S / 1, podemos calcular el tiempo

esperado en el sistema de líneas de espera (W), y el tiempo que se invierte antes de ser atendido (Wq), esto lo

podemos realizar por medio de las siguientes ecuaciones:

c) MODELO M / D / 1



Descripción

Sistema de líneas de espera con llegadas aleatorias, tiempo de servicio constante, una línea de servicio y una línea

de espera.

En este modelo los tiempos de servicio son determinísticos, este es un caso especial de la situación M / G / 1 que se

analizó con anterioridad, en donde la desviación estándar es igual a cero. En este caso se puede conocer el número

de unidades que están esperando a ser atendidas (Lq), a través de la siguiente ecuación:

Todas las demás características de operación pueden determinarse a partir de este valor. Si utilizamos Lq podemos

determinar el valor de L, por medio de la siguiente ecuación:

Al igual que las características de operación de los modelos M / M / 1 y M / S / 1, podemos calcular el tiempo

esperado en el sistema de líneas de espera (W), y el tiempo que se invierte antes de ser atendido (Wq), esto lo

podemos realizar por medio de las siguientes ecuaciones:

Tema teoria de colas

Education

Transcript of Tema teoria de colas