Unıversıdad Tecnologıca Nacıonal

FRRo

Informe N° 2 - Teoría

Teoría de Colas

Alumnos:
Nombre y Apellıdo Legajo Comısıón
Milena Lebedinsky 43982 305
Cristian Paglialunga 43968 301

Docentes:
Ing. Cristian Medín, Ing. Jorge A. Campanaro, Ing. Ger-
mán Baró

19 de enero de 2021
Índice general

1. Resumen 3

2. Introducción 4
2.1. Sistemas de líneas de espera y teoría de colas . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Historia del desarrollo y aplicación de la teoría de colas . . . . . . . . . . . . . . . . . 4
2.3. Elementos que conforman el sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4. Características que describen al sistema . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4.1. Llegada de un cliente de la población al sistema . . . . . . . . . . . . . . . . . 8
2.4.2. Patrones del servicio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4.3. Comportamiento de la cola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4.4. Capacidad del sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4.5. Arreglos de servidores y filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4.6. Niveles o pasos del servicio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5. Descripción de un sistema y notación de tipos de sistemas . . . . . . . . . . . . . . . 11
2.6. Resultados: la respuesta del sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3. Conceptos empleados para la deducción y el análisis de un sistema de colas 14

3.1. Procesos estocásticos, procesos de conteo, procesos de Poisson y de Markov . . . . 14
3.1.1. Teorema de Palm-Khintchine . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2. Procesos de Nacimiento - Muerte y procesos de colas . . . . . . . . . . . . . . . . . . 16

4. Sistemas generales G/G/1 y G/G/c 19

4.1. Notación de las variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2. Resultados generales G/G/1, G/G/c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3. Intensidad del tráfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.4. Distribución de probabilidad resultante para la cantidad de clientes . . . . . . . . . . . 21
4.5. Fórmulas de Little . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5. Sistemas M/M/1 y M/M/c 24

5.1. Distribuciones exponenciales y de Poisson y propiedad de Markov . . . . . . . . . . . 24
5.2. Proceso M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.2.1. Alcanzando el estado estable: Distribución de los tiempos de espera con la
evolución del sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.3. Proceso M/M/c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.3.1. Resultados resolviendo a partir de las probabilidades y del diagrama . . . . . 30

1
 5.3.2. Fórmula de Erlang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

6. Redes de colas 33
6.1. Estructura topológica de redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6.1.1. Teorema de Burke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6.1.2. Sistema tándem o serie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.2. Redes de Jackson o Markovianas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.2.1. Redes de Jackson Abiertas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.2.2. Redes de Jackson cerradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

7. Conclusiones 40
7.1. Ejemplo 1. Cola simple abierta M/M/? . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.2. Ejemplo 2. Red de Jackson abierta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

8. Anexo: Autoevaluación 43

9. Bibliografía 46
9.1. Fuentes bibliográficas del contenido del trabajo práctico: . . . . . . . . . . . . . . . . . 46
9.2. Fuente de las imágenes: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

2
1. Resumen

El objetivo de este trabajo es exponer los conceptos fundamentales en teoría de colas, así como
otros que pueden resultar de interés por su interpretación, por particularidades de sus aplicaciones,
o porque simplemente presentan ideas que ayudan a pensar a la hora del análisis y modelado de un
sistema de colas.
En la introducción se definen los sistemas de colas, se analiza cada una de sus componentes y
las diferentes variaciones que pueden presentar, y se presenta una notación usual, útil para denotar
las características más importantes que definen sistema - conocida como notación de Kendall.
Luego se ve una breve definición de algunos conceptos matemáticos y de estadística, útiles para
representar el proceso a fin de calcular las respuestas y predecir su comportamiento.
Luego se presentan los resultados de la teoría encontrados para los sistemas más simples que
abarcan la mayoría de los casos a estudiar: sistemas generales y sistemas con propiedades de
Markov. Se analiza por qué se se emplea cada modelo para casos particulares de la práctica, en que
puntos son válidos, así como sus debilidades y las simplifcaciones supuestas. Además, se hace una
revisión de algunas demostraciones de las fórmulas más importantes.
Antes de terminar se ven brevemente algunas generalidades de redes de colas, teoremas de
interés y los cálculos para las topoligías particulares: en serie y de Jackson abierta y cerrada.
Finalmente como conclusión se plantean y se analizan algunos ejercicios, uno propuesto a partir
de la observación de un caso hipotético, y otro extraído de la bibliografía. Se puede ver que:

• Los conceptos vistos encuentran utilidad rápidamente al analizar con detenimiento algunas apli-
caciones de la teoría de colas.

• Existen otras herramientas que han quedado por fuera de este trabajo harían que los modelos
propuestos sean más precisos y reflejen mejor la realidad

• Una aproximación no demasiado rigurosa de casos generales y frecuentes se puede lograr con
bastante simplicidad en el cálculo. Qué tan aceptable es esta aproximación se podría determinar a
través de una simulación y al compararla con lo que se observa en la realidad.

3
2. Introducción

2.1. Sistemas de líneas de espera y teoría de colas

Una cola o línea de espera se trata de un conjunto de clientes que se encuentran a la espera de
un determinado servicio. Este comportamiento se debe a que el servicio puede tener determinado
tiempo de demora, y de no ser inmediatamente provisto al cliente, el cliente esperará a ser servido,
formando la línea de espera, hasta ser atendido y/o dejar el sistema.
La teoría de colas es una colección de modelos matemáticos que describen sistemas de línea
de espera. Dichos modelos sirven para encontrar un balance entre el costo del servicio y el costo
asociado a la espera por ese servicio. Esta teoría brinda información sobre el comportamiento de
este tipo de sistemas (de líneas de espera pero cabe destacar que no se encarga por sí misma
de la optimización de dicho sistema. Esta sería una tarea posterior, para mejorarlo en función de la
satisfacción de los clientes o usuarios, y del desempeño de quienes ofrecen el servicio. El ajuste de
los parámetros para un determinado rendimiento se considera fuera del rango de estudio de la teoría
de colas y se corresponde más bien con el campo de investigación operativa, campo que engloba a
la teoría de colas. Estas áreas son fundamentales a su vez para el análisis de todo tipo de sistemas
dinámicos y para la toma de decisiones.
Puede observarse que la definición de un sistema de colas es amplia y puede utilizarse para el
análisis de diversos sistemas. Quizás el ejemplo más familiar consiste en pensar al cliente como una
persona que acude a un negocio deseando adquirir un bien, servicio o información. Puede resultar
que todos los empleados estén atendiendo a otros clientes, por lo que deba esperar en cola, caso
común en el día a día, hasta ser atendido, satisfacer la transacción correspondiente y retirarse. Pero
los sistemas de líneas de espera son mucho más generales aún: el cliente puede tratarse de una
instrucción esperado a ser ejecutada en la memoria de una computadora, un avión esperando a
recibir el visto bueno para despegar en un aeropuerto, o un tiempo de espera programado antes de
realizar cierta acción en un sistema de maquinaria industrial.
En resumen, la teoría de colas se desarrolló para estudiar la relación entre parámetros abstractos,
simplificando la relación que existe entre ellos. Sus aplicaiones permiten predecir el comportamiento
de un sistema que deberá proveer de un servicio a una cantidad de clientes o demandas aleatorias
y son el fundamento analítico del modelado de muchos sistemas.

2.2. Historia del desarrollo y aplicación de la teoría de colas

Uno de los problemas que dió pie al desarrollo de la teoría de colas fue la congestion de tráfico
para la comunicación telefónica. En 1909, el matemático, estadístico, ingeniero e investigador Ag-

4
 Figura 2.1: A.K. Earlang, matemático, estadístico, ingeniero e investigador danés nacido en 1878

ner Krarup Erlang publicó su trabajo ’Teoría de probabilidades en las conversaciones telefónicas’,
y en publicaciones posteriores seguiría describiendo las distintas variables del sistema con mayor
presisción: los tiempos entre llamadas entrantes, el tiempo de espera, la duración de cada llamda y
la cantidad de canales disponibles seguirían determinadas distribuciones de probabilidad y satisfa-
ciendo relaciones matemáticas entre sí.
El concepto de un sistema alcanzando su estado estacionario fue también descubierto por Erlang,
así como el estudio de su optimización. Hoy en día, el Erlang es una unidad adimensional utilizada en
telefonía como una medida estadística del volumen de tráfico nombrada trás él, así como un lenguaje
de progamación utilizado en sistemas con altos requerimientos de respuesta y concurrencia en línea.
A Erlang se lo considera el padre de la ingeniería de tráfico de telecomunicaciones y la teoría de colas.
En 1927 E. C. Molina publicó un paper titulado ’Application of the Theory of Probability to Telepho-
ne Trunking Problems’, lo que traducido al español podría entenderse como ’Aplicación de la teoría
de la probabilidad a problemas troncales en la telefonía’.
Un año más tarde, en 1928, Thornton Fry publicó un libro titulado ’Probabilidad y sus usos en
ingenería’, expandiendo el trabajo de Earlang.
En la década de 1930, Felix Pollaczek fue pionero en trabajar con distribuciones de Poisson como
variables de entrada, salidas arbitrarias, tanto con un único como múltiples canales. A su vez, más
trabajos se realizaban en paralelo al rededor del mundo por los investigadores rusos Kolmogorov y
Kintchine, el francés Crommelin y el sueco Palm.
Se continuo avanzando de forma lenta y constante en las primeras décadas, hasta que en 1950
se disparó el estudio y campos de aplicación de esta área, con infinidad de trabajos publicados desde

5
Figura 2.2: Operadoras telefónicas. Una aplicación de la teoría de colas que motivó ampliamente su
desarrollo.

entonces, y en curso, hasta el día de hoy, en entornos de trabajo tan diversos como servicios públicos,
negocios e ingeniería industrial.
Esta teoría se ha extendido y desarrollado mucho más allá del punto de vista práctico inmediato.
Sin embargo, no puede quedar sin mencionar que a la hora de aplicarla, tan importante como el
desarrollo teórico es el criterio de asignación de modelos al comportamineto de la realidad. No todos
los sistemas se comportan de la misma forma y también existe un gran campo de trabajo en cuanto
al desarrollo de modelos para cada uno de ellos.

2.3. Elementos que conforman el sistema

El objetivo de estos sistemas es el de proveer uno o varios servicios. Los elementos básicos que
componen a un sistema de colas son:

Fuente o población de usuarios (contexto del sistema): Potenciales usuarios a requerir al-
guno de los servicios provistos por el sistema. Se suele considerar infinita por simplicidad,
aunque es sabido que existe un máximo de potenciales clientes a ingresar en casi todas las
situaciones prácticas. Sin embargo, la probabilidad de que se presenten todos los clientes de
entre el conjunto de potenciales usuarios es baja, por lo que el error que pueda acarrear esta
suposición es bajo o no tiene efecto.

Servidor: Son las entidades encargadas de satisfacer la necesidad de los usuarios. Esta tarea
demanda un determinado tiempo (tiempo de servicio). En general se considera que cuando

6
 un cliente está siendo atendido (recibiendo el servicio) el servidor se encuentra ocupado hasta
completarlo

Cola o línea de espera: Está compuesta por los usuarios que no pueden ser atendidos al
ingresar al sistema, debido al tiempo que demoran los servidores en prestar el servicio. Cuando
todos los servidores se hallan ocupados, un cliente que ingresa al sistema se coloca en cola.
Por lo tanto, debe esperar conformando la línea de espera.

Figura 2.3: Esquema de un sistema de colas: elementos básicos que lo conforman

2.4. Características que describen al sistema

En la mayoría de los casos, seis parámetros que definen al sistema proveen la información nece-
saria y suficiente para un buen análisis de su comportamiento y estudiar posibles variaciones. Para
realizar el modelo matemático del sistema se los suele trabajar como variables aleatorias. Estos son:

El patrón de llegada y el comportamiento de los clientes

El patrón de servicio

El comportamiento de las colas

La capacidad del sistema

Cantidad de servidores y filas

Niveles o pasos del servicio

7
Figura 2.4: Características que varían entre distintos sistemas. Los valores de las mismas determinan
el comportamiento (la respuesta) del sistema

2.4.1. Llegada de un cliente de la población al sistema

La llegada de un cliente al sistema es un evento aleatorio, y al estudiar la llegada de clientes

a través del tiempo, se está hablando de un proceso estocástico. Por ello se suele trabajarse con
los tiempos entre llegadas de clientes en términos de las distribuciones de probabilidad que siguen
dichos tiempos. Además, suele definirse si es posible o no, y en que medida ocurre, que se presente
más de un cliente en simultáneo.
Además, existen distintos comportamientos por parte de los clientes, dependiendo del sistema
particular en estudio:

Puede que un cliente rechace hacer una cola demasiado larga, tomando la desición de no
ingresar al sistema.

Por otro lado, puede que el cliente se frustre, decidiendo abandonar la cola luego de trascurrido
determinado tiempo en espera.

En sistemas con múltiples colas, un cliente puede decidir cambiar entre ellas según determi-
nados criterios.

Los patrones de comportamientos pueden ser estacionarios, es decir aquellos fijos desde el
momento inicial del sistema e independientes del tiempo, o no estacionarios, esto es, variables con
una dependencia en el tiempo.

2.4.2. Patrones del servicio

Al igual que el tiempo entre llegadas de clientes, se trabaja el tiempo de servicio para cada clien-
tes a partir de una distribución de probabilidad. Además, existe la posibilidad de servir a más de un
cliente en simultáneo: algunos procesos con esta característica son, por ejemplo, multiples progra-

8
mas corriendo en un procesador que puede procesar en paralelo, o múltiples personas subiendo a
un mismo juego en un parque de diversiones.
Al igual que el comportamiento de los clientes en las colas, el servicio puede ser o no dependiente
del estado del sistema. Por ejemplo, al haber una cola más larga, el servicio puede acelerarse, o por
el contrario, entorpecerse.
Además, también pueden ser o no esacionarios (es decir, dependientes del tiempo transcurrido
desde un tiempo inicial del sistema).
Se suele considerar el tiempo de servicio y el tiempo de llegadas entre clientes como procesos
independientes, excepto raras excepciones. A partir de estas dos variables, ambas aleatorias, se
tendrá no una certeza, sino otra distribución de probabilidad como resultado, que describa el posible
largo de la cola.

2.4.3. Comportamiento de la cola

Imaginemos primero el caso más común: llegar a un negocio a comprar algo y hacer fila en orden
de llegada. El vendedor atenderá primero a los primeros en la cola. Este es el conocido algoritmo
FCFS, de sus siglas en inglés first come first served o FIFO, first in first out: el primero en llegar es
atendido primero.
Sin embargo, está lejos de ser el único algoritmo de selección posible. El LCFS, last come first
served, es el caso opuesto, donde se atiende primero al último cliente en llegar al sistema. Un caso
de ejemplo podría ser el ir guardando algún artículo no perecedero para su uso en fila. El último en
colocarse estará disponible más cerca para su uso, y en este caso, estaremos seleccionando según
LCFS.
Otra forma de seleccionar clientes de la cola es a partir de un proceso aleatorio, o RSS, random
selection for service. Puede que se seleccione un cliente de la cola completamente al azar, con una
distribución uniforme, o pueden establecerse órdenes de prioridad. Este patrón se podría observar
en una sala de urgencias en un hospital.
Además, al asignar orden de atención por prioridades, pueden ocurrir dos cosas: se puede colocar
primero en la fila al cliente de prioridad más alta, o se puede interrumpir el servicio y atender direc-
tamente a un cliente que acaba de llegar, si éste tiene prioridad mayor al que está siendo atendido,
o a partir de cierta escala de valores.

2.4.4. Capacidad del sistema

Puede ser el caso de que exista un máximo de clientes permitidos en el sistema, teniendo o no
en cuenta a los clientes que están siendo atendidos. Si este es el caso, se rechazarán a los clientes
que lleguen a la línea de espera, y no se permitirá su entrada a la misma.

9
2.4.5. Arreglos de servidores y filas

Existen múltiples maneras de distribuir las colas y los canales de servicio, o servidores, que atien-
den a los clientes en paralelo. Puede permitirse una única cola y múltiples servidores, como suele
ser el caso de la mayoría de peluquerías, o puede permitirse una cola por cada servidor, como suele
ocurrir en algunos supermercados. También podrían lograrse arreglos de ambas situaciones.

Figura 2.5: Sistema de una sola cola y servidor

Figura 2.6: Sistema de una cola para múltiples servidores

Figura 2.7: Sistema con múltiples servidores y colas para cada uno de ellos

2.4.6. Niveles o pasos del servicio

Existen múltiples ejemplos de servicios que se prestan en diferentes etapas. Por ejemplo, al rea-
lizar un trámite, puede encontrarse con una primera línea de espera para presentar documentación,
y una segunda etapa donde se presenta una validación de la documentación entregada.
Siendo el mencionado el caso más simple, existe también un ejemplo en el caso de las teleco-
municaciones: cuando un mensaje debe recorrer una cantidad de nodos en algún orden arbitrario.
En este caso, las distintas etapas y el orden en que se llevan a cabo pueden ser asignados aleato-
riamente.
Por otro lado, existe la posibilidad de retroalimentación del sistema, donde por variadas circuns-
tancias, puede retrocederse o combinarse la cantidad de veces que un mismo cliente se presenta
en las distintas etapas.

10
Figura 2.8: Sistema de colas con múltiples pasos. El servicio consta de 2 pasos intermedios (servicio
1 y servicio 2).

2.5. Descripción de un sistema y notación de tipos de sistemas

Existe una suerte de estándar a la hora de describir el comportamiento de los parámetros men-
cionados en un sistema de colas. Se la conoce como notación de Kendall ya que la misma fue desa-
rrollada por David George Kendall, estadístico y matemático inglés. Para caracterizar el sistema, se
emplean símblos y barras de la siguiente manera:
A/B/c/Y/Z
donde A indica la distribución de los intervalo de tiempos de llegada, B indica la distribución de
tiempos del servicio, c es el numero de canales de servicio, o servidores en paralelo, Y es la restricción
de capacidad del sistema y Z la disciplina del sistema. En otras bibliografías se puede encontrar:
A/B/X/Y/Z
Pero esta vez X es la cantidad de servidores (X = c).
Algunos de los posibles valores para cada una de estas variables se muestran en la tabla 2.9, a
continuación.

11
Figura 2.9: Valores posibles para cada uno de los parámetros, A, B, c, Y, Z, que describen el com-
portamiento de un sistema de colas

De esta manera, podría hacerse mención de un tal sistema M/D/2/∞/FCFS, aportando con esta
notación la siguiente información: los tiempos entre llegadas siguen una distribución exponencial,
tiempos de servicio deterministas, se cuentan con dos servidores en paralelo, no existe límite de
capacidad para el sistema, y se sirve a los clientes en orden de llegada.
En muchas ocasiones se puede encontrar una notación con sólo tres símbolos, ya que se puede
omitir la capacidad del sistema cuando no se imponen restricciones, Y = ∞, y la disciplina de asig-
nación es Z = FCFS. En este caso, se estaría hablando del mismo sistema del ejemplo mencionado
si se lo llama simplemente M/D/2
Se puede notar que esta notación no brinda información acerca de todas las situaciones diferetes
que han sido mencionadas en el análisis del comportamiento de distintos actores del sistema. Para el
estudio detallado del comportamiento de sistemas más complejos, como colas con retroalimentación,
llegadas simultáneas de clientes, dependencias con el tiempo o con el estado de las distribuciones
de tiempo, etc., se suele adoptar una notación que debe ser mencionada en el propio texto que
introduce el sistema en estudio.

12
2.6. Resultados: la respuesta del sistema
Tras describir el comportamiento de un sistema, se desea obtener por resultado la respuesta
del mismo. Los parámetros de respuesta del sistema son diversos y, dependiendo de la aplicación,
algunos resultan de mayor interés que otros. Algunos resultados de interés general son:

Tiempos del cliente

Patrón de acumulación de clientes

Tiempo de ocio de los servidores

En cuanto al tiempo del cliente, puede interesar su tiempo de espera en la cola así como su
tiempo total en el sistema. Por ejemplo: En un parque de diversiones interesa el tiempo de espera de
los clientes en cola, ya que es lo que se desea minimizar para mejorar la performance. En un taller
mecánico de reparación de maquinaria, la misma se encuentra inhabilitada hasta que termina el
proceso completo, considerando tiempo de espera y servicio, por lo que interesa minimizar el tiempo
total de permanencia en el sistema.
También existen dos casos a estudiar en cuanto a cantidad de clientes: la cantidad en espera
y la cantidad total en el sistema. Conocer el número de personas en cola puede ser útil para tomar
desiciones dinámicamente, como por ejemplo habilitar otra caja en un supermercado. Por otro lado,
si interesa por ejemplo, poner un máximo de personas permitidas en el interior de un local, deberán
tenerse en cuenta tanto aquellas que están siendo atendidas como aquellas que están en la cola.
El estudio del tiempo de ocio de un servidor puede tomarse para un servidor en particular del
sistema o para la sumatoria de tiempos ociosos de todos los servidores. Se halla con frecuencia en
el campo de la informática, donde el tiempo de servicio es mínimo, por lo que un estancamiento de
unos pocos segundos puede conllevar un alto coste.
Para la posterior optimización del sistema, a cada una de estas respuestas se le debe asignar un
costo asociado, con el fin de hallar un equilibrio entre todos los parámetros.
Una herramienta útil para hallar las respuestas del sistema suelen ser las simulaciones. Las mis-
mas permiten comparar el comportamiento de distintos diseños del sistema.

13
3. Conceptos empleados para la de-
ducción y el análisis de un siste-
ma de colas

Para modelar el comportamiento de un sistema de colas, y deducir la relación entre las variables
de interés que se mencionaron anteriormente, se emplean algunos conceptos matemáticos, que se
explican a continuación.

3.1. Procesos estocásticos, procesos de conteo, procesos de

Poisson y de Markov
Un proceso estocástico es una abstracción matemática que trabaja sobre una familia de va-
riables aleatorias {X(t), t ∈ T }, donde T es un parámetro (usualmente, el tiempo), el cual puede
ser discreto (medido en unidades enteras de días, horas, etc) o contínuo. A su vez, los valores que
pueden tomar las variables pueden ser también contínuos o discretos.
A un proceso estocástico tiene la propiedad de Markov si el estado de las variables en el futuro
depende únicamente del valor de las variables en la actualidad, y no del tiempo o de la historia. Es
decir, no posee memoria.
A los procesos de Markov de variables discretas, a tiempo contínuo o discreto, se los suele llamar
cadenas de Markov.
Un proceso de conteo es un proceso estocástico {N (t), t ≥ 0} que representa, en cada instante
de tiempo, el número total de ocurrencias de un determinado evento hasta dicho instante de tiempo.
Por lo tanto, dicho proceso debe tomar valores enteros positivos y debe ser creciente, es decir

N (t) ∈ N = {0, 1, 2, ...}

t1 ≤ t2 ⇒ N (t1 ) ≤ N (t2 )

14
Figura 3.1: Gráfica de un ejemplo de un proceso de conteo en el que han ocurrido cuatro llegadas u
ocurrencias

A un proceso de conteo con una distribución de Poisson, y con tiempos entre pares de sucesos de
distribución exponencial, también se los denomina proceso de Poisson. Cuando ocurre un suceso
o incremento, el mismo verifica las propiedades de:

Incrementos estacionarios: La ocurrencia de un evento en un intervalo de tiempo depende de

la longitud del intervalo y no de cuándo inicia el intervalo con respecto al tiempo de vida del
sistema.

Incrementos independientes: La ocurrencia de eventos en intervalos de tiempo disjuntos son

independientes entre sí.

Figura 3.2: Ejemplo de un proceso de conteo en el que se denomina Si al tiempo transcurrido hasta
la i-ésima ocurrencia y Xi al tiempo transcurrido entre la i-ésima ocurrencia y la ocurrencia i − 1

15
3.1.1. Teorema de Palm-Khintchine

Si se tienen múltiples procesos de conteo agregados de incrementos independientes, es decir,

se considera el proceso de que cuenta si se produjo una llegada en alguno de ellos, se complejiza
el cálculo de la probabilidad de que se produzca una llegada, ya que dependerá de la suma de las
distribuciones de los distintos procesos.
El teorema de Palm-Khintchine establece que, al considerar mayor cantidad de procesos de
conteo agregados, más se asemeja el comportamiento de la agregación a un proceso de Poisson

Figura 3.3: Representación de la agregación de múltiples procesos independientes, resultante en un

proceso de Poisson

Se puede establecer una analogía con el teorema central del límite, que establece que la suma
de suficientes variables independientes se aproxima a una distribución normal.
Como se verá más adelante, se suele modelar una gran cantidad de procesos de colas como
procesos M/M/c. El motivo intrínseco de observar ese comportamiento en los procesos de llegadas
en la realidad podría estar relacionado con este resultado.

3.2. Procesos de Nacimiento - Muerte y procesos de colas

Una cadena de Markov de tiempo continuo es un proceso aleatorio en un espacio de estados
contable, donde se cumple la propiedad de Markov.
Los procesos de nacimiento - muerte son un tipo de cadena de Markov de tiempo contínuo en el
que se dice que un sistema puede estar en un número de estados {1,2,...} en los que la transición
a un estado mayor n + 1 se da con una tasa λn y el retroceso de vuelta al estado n con una tasa
µ(n+1) . Se los suele representar con un diagrama de tasas como el que se muestra en la figura 3.4
a continuación.

16
 Figura 3.4: Diagrama de tasas de un proceso de nacimiento - muerte

La propiedad de Markov del proceso establece que las probabilidades de cambiar a un estado
sólo depende del estado actual y no de los anteriores. Por ende si en un instante de tiempo s el
sistema se encuentra en un estado i, la probabilidad de estar en un futuro s + t en un estado j sólo
dependerá del estado i en el que se encuentre el proceso en el instante s, y no de la historia antes
de s.

Figura 3.5: Diagrama de la evolución de los estados del proceso de nacimientos-muerte en el tiempo

Si además se cumple que las tasas λn y µn no dependen del estado n, se dice que es una cadena
de Markov homogénea
Puede describirse a un sistema de colas como un proceso de nacimiento-muerte en el que la
cantidad de clientes en el sistema es el estado. El mismo resulta de agregar los procesos de conteo
de llegadas y de partidas.
Si se denota con pn a la fracción de tiempo que el sistema se encuentra en el estado n, o lo que
es lo mismo, la probabilidad de que a un determinado tiempo el sistema se euentre en ese estado,
se tiene la siguiente ecuación para la misma, a partir de las tasas:

17
 λn−1 pn−1
pn = (3.1)
µn

la cual puede resulverse iterativamente reemplazando pn−1 . Pero, como la sumatoria de las pro-
babilidades de todos los estados posibles del sistema debe sumar 1, se debe cumplir que:

1
p0 = P∞ Qn λi−1
(3.2)
1+ n=1 i=1 µi

Una condición necesaria y suficiente para que exista el estado estable es la convergencia de la
P∞ Qn
serie 1 + n=1 i=1 λi−1
µi .

18
4. Sistemas generales G/G/1 y G/G/c

Se vió que un sistema se puede describir de manera concisa si se utiliza la notación de Kendall.
Tal y como se mencionó, obviaremos la capacidad del sistema considerándola infinita y el comporta-
miento de las colas, asumiendo que es de forma FCFS. En resumen, analizaremos diversos sistemas
que varían en los parámetros A/B/X:
Tiempos entre llegadas / Tiempos de servicio / cantidad de servidores

4.1. Notación de las variables

Las variables que caracterizan al sistema usualmente son un dato, y se suelen denotar:

λ al promedio de la tasa de entrada de clientes al sistema, o velocidad de arribo en clien-

tes/unidad de tiempo.

τ al tiempo entre dos arribos de clientes consecutivos. Al tiempo promedio entre llegadas se
lo denota E[τ ]

µ a la tasa promedio de servicios prestados por servidor

s al tiempo de servicio para un usuario. E[s] es el tiempo promedio de servicio, y E[s] = 1/µ.

r, o a veces u, es una buena medida para la congestión del sistema, que se suele denominar
intensidad del tráfico y se mide en unidades ’Erlang’

ρ es la intensidad del tráfico por servidor

Cuando se puede hablar de un estado estable del sistema, a las variables que describen la
respuesta del sistema, que se obtienen por resultado de las variables anteriores, se representan con
letras mayúsculas latinas:

N : cantidad total de usuarios presentes en el sistema en un instante de tiempo. Nq son la

cantidad de clientes en la cola y Ns la cantidad de clientes recibiendo servicios.

L: cantidad promedio de usuarios presentes en el sistema, y Lq a la cantidad de usuarios

en cola. A aquellos clientes que se encuentran siendo atendidos, se los denota Ls , siendo
L = Lq + Ls

T : el tiempo total que un cliente permanece en el sistema, siendo Tq el tiempo en cola y s el

tiempo recibiendo el servicio.

W : el tiempo promedio que un usuario se encuentra dentro del sistema, Wq al tiempo promedio

19
 que un usuario se encuentra en la línea de espera y E[s] el promedio de tiempo en servicio. El
uso de la letra W para los casos anteriores viene del inglés ’wait’.

4.2. Resultados generales G/G/1, G/G/c

La notación G se refiere a distribuciones generales o arbitrarios para los tiempos entre llegadas
y de servicio. De esta manera, los resultados obtenidos de este análisis resultan de utilidad para la
mayoría de los sistemas. Consideraremos los casos en los que se tiene un (1) único servidor o una
cantidad constante c de servidores, un buen caso general ya que se presenta con mayor frecuencia.

4.3. Intensidad del tráfico

La intensidad del tráfico r se define como el cociente r = λ/µ [Erlang]. A veces se la denota
también con la letra u.
Si se considera que los clientes aparecen con una frecuencia de λ clientes por unidad de tiempo
y se los atiende cada µ clientes por unidad de tiempo, en c servidores en paralelo, la intensidad del
tráfico por servidor puede calcularse como:

λ
ρ=
c·µ

De esta manera, si ρ > 1, quiere decir que la cantidad de clientes que ingresan al sistema es
mayor a la cantidad de clientes que son servidos, λ > c · ρ. En este caso, se formará una cola
que aumentará su tamaño indefinidamente. No habrá un estado estacionario, sino que se tendrá un
incremento infinito de la espera.
Si ρ = 1, la cola quedará determinada por la aleatoriedad de las variables. Por lo tanto, tampoco
se tendrá un estado estable conocido a medida que transcurra el tiempo, a no ser que los tiempos
sean constantes (deterministas) y perfectamente sincronizados, caso que no se suele hallar en la
vida real.
Si ρ < 1, será posible alcanzar un estado estable a partir del cual el tiempo de espera y la cantidad
de clientes permanecerán, justamente, estables.
En este último caso, se puede tomar también a ρ como pb : la probabilidad de que un servidor
arbitrario se encuentre ocupado, donde se utiliza el subíndice b del inglés ’busy’. Cuando la utilización
de los servidores se da de manera uniforme, a ρ también se la denomina factor de utilización de
servicio. Para el caso c = 1 se tiene que 1 − pb = 1 − ρ es la probabilidad de que el sistema esté
vacío y coincide con la intensidad del tráfico u.
De esta manera, se puede conocer, a partir de λ y µ, la cantidad mínima de servidores c entero
que permita al sistema alcanzar un estado estable.

20
4.4. Distribución de probabilidad resultante para la cantidad de
clientes
Si denotamos con L al promedio de clientes en el sistema, podemos decir que esta cantidad sigue
una distribución de probabilidad. Si llamamos N a la cantidad de usuarios en el sistema, o N(t) a
la cantidad de usuarios en el instante t, entonces L es la media de N y se tiene:

∞
X
L = E[N ] = n · pn
n=0

donde se esta realizando una sumatoria para todos los posibles valores de N, siendo pn = P (N =
n).
De la misma manera, se podría definir esta ecuación para la cantidad de clientes en cola Lq :

∞
X ∞
X
Lq = E[Nq ] = nq · pnq = (n − c)pn
nq =0 n=c+1

considerando que se quiere descontar de una determinada cantidad de clientes n, cada uno de
los clientes que se hallan en alguno de los c servidores, y además, al menos un cliente se halla en
cola.

4.5. Fórmulas de Little

Una de las relaciones más importantes es la desarrollada en 1960 por John Little y . La misma
relaciona las variables de tasa de entrada de clientes al sistema λ y la cantidad media de clientes L,
las cuales son relativamente sencillas de obtener, con la variable W , o tiempo medio que permanecen
los usuarios en el sistema, que suele ser de gran interés y no tan sencilla de calcular por otros medios.
El teorema de Little establece que a mayor tasa de clientes, y tiempo promedio de permanencia
en el sistema, mayor la cantidad promedio de clientes presentes en el mismo. Es decir:

L = Wλ (4.1)

Y de la misma manera, para la cantidad de clientes en cola:

L q = Wq λ

Conociendo que W = Wq + 1/µ, basta con encontrar uno de los cuatro valores para hallar los
demás.
Parte de su importancia radica, además, en que se puede aplicar a casi cualquier sistema.
Jhon Little prueba esta igualdad en su artículo de 1960 ’A Proof for the Queueing Formula’. Sin
embargo, como él mismo lo dice en el mismo artículo, ya se solía emplear la fórmula llegando a
ella como resultado a través de heurísticas u aproximaciones menos rigurosas que la desarrollada

21
entonces.
Una demosrtación menos rigurosa se puede elobrar de la siguiente manera:
Si se llama al proceso de llegadas α(t) y β(t) al proceso de salidas, entonces la cantidad media
de personas en el sistema estará dada por el proceso. Un usuario i espera un tiempo Ti .

N (t) = α(t) − β(t)

Figura 4.1: Un sistema de colas muy general, que resulta de agregar dos procesos de conteo: llega-
das al sistema y salidas

Se puede obtener el resultado de la ecuación 4.1 si se calcula este valor como el promedio en el
tiempo de la cantidad de clientes en el sistema

Z t
1
L = lím N (τ )dτ
t→∞ t 0

y si se aplica la aproximación

Z t α(t)
1 1X
lím N (τ )dτ ≈ lím Ti
t→∞ t 0 t→∞ t
i=1

multiplicando y dividiendo por α(t) se tiene:

Pα(t)
α(t) i=1 Ti
L ≈ lím
t→∞ t α(t)

Y cada uno de los términos es:

α(t)
λ = lím
t→∞ t

Pα(t)
i=1 Ti
W = lím
t→∞ α(t)

22
 De manera que se llega efectivamente a

L = λW

Un detalle importante a la hora de aplicar el teorema de Little es que se trabaja con la tasa λ de
clientes que efectivamente entran al sistema, y no la tasa de la población que desea hacecrlo. Por lo
tanto, en los sistemas donde haya usuarios rechazados habrá que tener en cuenta esta distinción
en la notación de Kendall, ya que de lo contrario se asumen iguales.

23
5. Sistemas M/M/1 y M/M/c

Según se vió previamente, se denota con la letra M a las características del sistema que se rigen
por distribuciones de probabilidad exponenciales. Se utiliza la letra M para denotar que se está ante
un proceso de Markov (o sin memoria).

5.1. Distribuciones exponenciales y de Poisson y propiedad de

Markov
Sea una variable aleatoria x que represente la cantidad de veces que se produce un evento, es
decir, tomando valores discretos, regida por una distribución de probabilidad de Poisson. La proba-
bilidad de que x tome un determinado valor k es:

λk e−λ
P (x) =
k!

Siendo λ el valor promedio que toma x. Si se analiza el gráfico de esta distribución, que se muestra
a continuación, se puede notar que la probabilidad crece, con un máximo en k = λ, y luego disminuye
algo mas rápido.

Figura 5.1: Gráfica de la probabilidad en función de los posibles valores para x, variable aleatoria de
Poisson

Mientras que si t que representa el tiempo transcurrido entre dos eventos x de Poisson consecu-
tivos, t estará regida por una distribución de probabilidad exponencial, siendo ésta:

24
 P (t) = λe−λt

Y su gráfico:

Figura 5.2: Gráfica de la probabilidad en función de los posibles valores para t, variable aleatoria
exponencial

Entonces, es equivalente decir que los tiempos entre arribos de clientes o tiempos de servicio
se rigen por una distribución exponencial, que decir que la tasa de clientes o la tasa de servicios
siguen una distribución de Poisson.
Una variable aleatoria que se rige por una distribución de probabilidad Poissoniana cuenta con
las siguientes propiedades:

en un intervalo de tiempo infinitesimal puede o no ocurrir un único suceso x

la ocurrencia o no del suceso es independiente de su ocurrencia entre distintos intervalos

si se toma un intervalo de tiempo mayor, la probabilidad de que ocurra x aumenta linealmente

con la longitud del intervalo de tiempo, y permanece independiente de la ocurrencia de eventos
en otros sub-intervalos

Este es uno de los casos más aplicados ya que se está tratando a los sucesos como indepen-
dientes entre sí.
Por otro lado, es sencillo aplicar este modelo a un caso real: basta obtener los valores promedio
para expresar las distribuciones, a diferencia de otras distribuciones que requieren datos como la
varianza, o que por el contrario, omiten el hecho de que se cuenta con un valor medio conocido.

25
5.2. Proceso M/M/1
En un sistema de colas M/M/1 las tasas de nacimiento y muerte son λ y µ respectivamente,
constantes para todos los niveles del sistema (ver figura 5.4)

Figura 5.3: Diagrama de tasas de un sistema de colas del tipo M/M/1

A un proceso en el que se acummulan llegadas, las cuales se rigen por una distribución de Poisson
también se lo denomina proceso de Poisson
Se debe recordar distribuciones de los tiempos entre llegadas τ y de servicio s son respectiva-
mente:

P (τ ) = λe−λτ

P (s) = µe−µs

Si se plantean las ecuaciones a partir del diagrama, como se vió en el caso anterior, se tiene un
modelo para la simulación del sistema con ecuaciones:

µ
p0 = p1
λ
λ+µ µ
pn+1 = pn − pn−1
µ λ

Resolviendo las ecuaciones, se tiene como resultado la probabilidad pn de que el sistema se

encuentre con una cantidad de clientes n:

pn = (1 − ρ)ρn

Cuando el sistema alcanza el estado estable, se tienen en promedio L clientes en el sistema:

26
 ∞ ∞ ∞
X X X ρ
L= npn = n(1 − ρ)ρn = ρ(1 − ρ) nρn−1 =
n=0 n=1 n=1
ρ−1

Figura 5.4: Diagrama de tasas de un sistema de colas del tipo M/M/1

Y según la fórmula de Little’s:

L ρ 1 µ 1
W = = = = =
λ λ(1 − ρ) µ(1 − λ/µ) 1−λ µ−λ

Mientras que para Lq , análogamente al caso de L, pero omitiendo a la persona que se encuentra
en el servidor:

∞ ∞ ∞
X X X ρ 1
Lq = (n − 1)pn = npn − pn = − (1 − p0 ) =
n=1 n=1 n=1
(ρ − 1) 1−ρ

Lq ρ
Wq = =
λ µ−λ

5.2.1. Alcanzando el estado estable: Distribución de los tiempos de espera

con la evolución del sistema

Esta evolución, a diferencia de los parámetros calculados hasta ahora, depende fuertemente
del comportamiento de la cola, por lo que cabe detacar que, como se omite esta información en la
notación, se está asumiendo un algoritmo F CF S. Un comportamiento diferente, tendrá por resultado
una evolución distinta a la que se verá a continuación.
En esta sección analizaremos la variable aleatoria Tq que representa el tiempo de espera en cola

27
y Wq (t) es la distribución de probabilidad acumulada.
Una característica a destacar en cuanto a la variable aleatoria tiempo de espera, es que la misma
tiene un comportamiento contínuo para todos los valores distintos de cero, pero posee a su vez una
propiedad de variable aleatoria discreta en t = 0 ya que la su probabilidad es P (Wq (t = 0) 6= 0), ya
que en el inicio el sistema está vacío, los servidores libres, y el tiempo de espera es efectivamente
cero, y aunque esta condición puede o no volver a repetirse a lo largo de la vida del sistema, al menos
el primer cliente en ingresar tiene la certeza de no formar cola.
Si la probabilidad de que el sistema se encuentre en estado n al tiempo t es qn

Wq (0) = q0 = {Probabilidad de hallar el sistema vacío}

A la probabilidad de encontrar al sistema en ese estado a cualquier tiempo la llamamos pn .

Anteriormente se ha mencionado que pn se corresponde con la fracción de tiempo total que el
sistema se encuentra en estado n sobre el total de tiempo. Resulta que para la distribución de Poisson
para las llegadas pn = qn , y por lo tanto:

Wq (0) = q0 = p0 = 1 − ρ

Queda encontrar la probabilidad acumulada para cualquier valor de t. Esto es, la probabilidad de
que un cliente espere una cantidad de tiempo igual o menor a t, Wq (t).
Como el sistema no posee memoria, este cálculo es equivalente a la probabilidad de que las n
personas que se encuentren en el sistema al momento de ingresar sean atendidas en un tiempo
menor o igual a t.

Wq (t) = {P r(Tq ≤ t)}

∞
X
= Wq (0) + P r{se atienden n personas en tiempo menor o igual a t|se encontraron n personas}pn
n=1

Para saber la probabilidad de atender n personas en un tiempo menor o igual a t se debe cono-
cer la distribución que sigue la ocurrencia de n sucesos de Poisson en el tiempo. Por ser eventos
independientes en el tiempo, el resultado es la convolución de n distribuciones exponenciales. Esto
es, la distribución de Erlang.

28
 Figura 5.5: Función de distribución de probabilidad de Erlang para distintos parámetros de k

La ecuación a resolver queda:

t ∞
(µxρ)n−1
Z X
Wq = (1 − ρ) + ρ µ(1 − ρ)e−µx dx
0 n=1
(n − 1)!

donde la sumatoria para todos los posibles valores de n se hace para marginar sobre esta variable
y encontrar la probabilidad de esperar desde 0 hasta t, independientemente del estado del sistema.
El resultado de la distribución Wq (t) es:

Wq (t) = 1 − e−(µ−λ)t

El gráfico se muestra a continuación:

Figura 5.6: Probabilidades de ser atendido en tiempos menores o iguales a t (tendiendo a 1 cuando
t tiende a infinito)

29
5.3. Proceso M/M/c
Al generalizar la cantidad de servidores en el sistema, no se modifica la tasa de arribo. Para cada
estado n del sistema ingresan λ clientes por unidad de tiempo en promedio.
Sin embargo, el tiempo de servicios prestados depende de cuantos clientes se encuentran actual-
mente siendo atendidos en alguno de los servidores. Si cada uno de ellos presta un servicio que dura
en promedio s = 1/µ, y se encuentran n ≤ c servidores ocupados, la tasa de ’muerte’ del proceso
nacimiento-muerte será nµ. Generalizando, si se encuentran n personas en el sistema, la tasa será:

nµ n≤c


cµ

n>c

El diagrama de tasas se muestra en la figura 5.7

Figura 5.7: Diagrama de tasas para el proceso de nacimiento-muerte de un sistema M/M/c. A partir
de n = c, la tasa de muerte es constante, cµ

5.3.1. Resultados resolviendo a partir de las probabilidades y del diagrama

Si se sigue un procedimiento similar para hallar las probabilidades de encontrar al sistema con n
personas (o, lo que es lo mismo, en el estado n), pn , y luego se obtiene el promedio de n se obtiene
la cantidad promedio de personas en un sistema M/M/c. Realizando la demostración, y notando
r = λ/µ y ρ = λ/cµ, luego calculando los parámetros siguientes con la fórmula de Little, se llega a
los resultados:

rc ρ
L=r+( p0 )
c!(1 − ρ)2

rc ρ
Lq = ( )p0
c!(1 − ρ)2

para las medias de cantidad de personas en el sistema y en cola respectivamente. Se puede

destacar que al no ser una fórmula lineal, no es sencillo extrapolar un resultado ante una variación

30
de los valores. Esto también se puede deducir al analizar los distintos gráficos de Lq ante variaciones
de c, los cuales se muestran a continuación:

Figura 5.8:

Este tipo de sistemas es tan general que esta fórmula se requiere con frecuencia. Para ello,
existen tablas de valores con aproximaciones de Lq para variaciones de c y ρ (saturación).

Figura 5.9: Tabla de valores aproximados para Lq

Por otro lado, los resultados para el tiempo medio de espera en sistemas M/M/c es:

1 rc
W = +( )p0
µ c!(cµ)(1 − ρ)2

Lq
Wq =
λ

31
5.3.2. Fórmula de Erlang

La fórmula de Erlang da la probabilidad de que un cliente tenga que esperar en cola. Es decir, la
probabilidad de que todos los servidores se encuentren ocupados al momento de arribar al sistema.
Una forma de calcularlo es calcular primero la probabilidad de ser atendido a tiempos menores o
iguales que t, como ya se hizo antes pero para procesos M/M/1. El resultado para Wq es diferente
para procesos M/M/c. En este caso se tiene

c−1 c−1 n
X X r r c p0
Wq (0) = P r{Tq = 0} = P r{n 6 c − 1} = pn = p0 =1−
n=0 n=0
n! c!(1 − ρ)

Y, si esta es la probabilidad de encontrar los servidores vacíos, la probabilidad de no encontrar

ninguno vacío será:

rc
c!(1−ρ)
E(r, c) = 1 − Wq (0) = rc
Pc−1 rn (5.1)
c!(1−ρ) + n=1 n!

Expresión que se puede simplificar a:

rc /c!
E(r, c) = Pc−1 rn
rc /c! + (1 − ρ) n=1 n!

En distintas bibliografías se encuentran distintas notaciones para el parámetro r. Como ya se

mencionó, se lo puede encontrar bajo el nombre de u. Sin embargo, es fácil recordar que se trata
del cociente de las dos cantidades fundamentales del sistema, que son las tasas de llegada y de
servicio. A la fórmula de Erlang también se la puede encontrar como E(c, u).
Si se observa cautelosamente las ecuaciones vistas para los resultados de sistemas M/M/c, se
puede ver que pueden expresarse en términos de las mismas variables que la fórmula de Erlang:

E(r, c)
W =
cµ(1 − ρ)

rE(r, c)
L=
c(1 − ρ)

Como el parámetro E(r, c) resulta de interés por su interpretación intuitiva, y como las fórmulas
mostradas no son difíciles de recordar, se suelen calcular los resultados de sistemas M/M/c a partir
de su relación con el parámetro.
Además, en el caso de que la cantidad de los servidores sea c = 1, se tiene

E(r, c) = ρ = r (5.2)

manteniendo la simplicidad de cálculo en sistemas M/M/1 mediante este método.

32
6. Redes de colas

Conocidos ya algunos procedimientos para el desarrollo del modelo de un sistema de colas,

veamos otra rama de estudio en la teoría de colas ampliamente aplicable y que permite llevar los
sistemas simples de los casos vistos a sistemas más complejos y generales.
Como ya se mencionó, los sistemas de colas pueden variar en diversas características. Hemos
visto el desarrollo para distintas distribuciones de tiempos de llegada, tiempo de servicio y cantidad
de servidores. Sin embargo hemos considerado siempre, (aunque sea de manera implícita) que:

La fuente de clientes y la capacidad del sistema eran infinitas

El primer cliente que llegaba era el primer cliente atendido (disciplina FCFS)

Los sistemas eran simples y abiertos, lo que se detallará mejor a continuación

Con sistema simple y abierto se hace referencia a las características que cumplen los niveles
o pasos del servicio y a la cantidad de servidores y colas. Los sistemas que hemos visto eran
simples porque contaban con un único paso de servicio, donde podía haber uno o múltiples servido-
res en paralelo y abiertos porque los clientes entraban al sistema, eran servidos y salían. Veamos
ahora el caso de sistemas donde el cliente tiene que realizar una determinada cantidad de pasos
(cada paso es un servicio requerido) para satisfacer su objetivo para con el sistema.
Llamamos nodo a un paso o nivel de servicio, con uno o múltiples servidores realizando deter-
minada tarea.
Una red de colas es un conjunto de n nodos donde cada uno es un sistema de colas con uno o
varios servidores.
La red será un sistema compuesto por un conjunto de nodos interrelacionados funcionando asin-
crónica (entradas y salidas de clientes sin sincronizar) y simultáneamente.
En el caso más general:

Los clientes pueden entrar desde el exterior a cualquier nodo.

Los clientes pueden abandonar la red desde cualquier nodo.

Cada cliente puede hacer un recorrido diferente por la red.

Los clientes pueden volver a nodos que ya han visitados, evitar otros nodos e incluso perma-
necer en la red indefinidamente.

El estudio de las redes de colas tiene aplicaciones prácticas con frecuencia en el campo de las
TIC, por ejemplo el recorrido de un mensaje a través de Internet que debe atravesar por diversos
servidores para llegar a destino, o la ejecución de una línea de código que requiere esperar de que
cada parte de la máquina realice las operaciones necesarias para llevar a cabo la instrucción.

33
6.1. Estructura topológica de redes
Una red de colas podría representarse a través de un grafo orientado en el que los nodos se
relacionan según se producen transiciones de clientes que salen servidos de un nivel del sistema y
entran a otro, con una determinada probabilidad.
Una red de colas es abierta si los clientes pueden entrar y salir del sistema. Una red abierta
puede ser:
• Acíclica: Un cliente nunca puede volver a la misma cola.
• Cíclica: Cuando hay bucles en la red.
En una red abierta, un nodo i puede tener una tasa de entrada λi de clientes desde el exterior del
sistema, y una tasa de salida µi .
En las redes cerradas no entran nuevos clientes y los existentes nunca salen, es decir, el número
de clientes es constante a lo largo del tiempo.
La estructura topológica de la red es importante porque describe las transiciones admisibles
entre nodos (que, nuevamente, no deben confundirse con las transiciones entre los estados del
sistema). A las transiciones entre nodos también se les puede asignar una determinada probabilidad.

6.1.1. Teorema de Burke

El teorema de Burke, postulado y demostrado por Paul J. Burke en 1956, quién trabajaba en los
laboratorios Bell en aquel entonces, establece que:

Dada una cola M/M/1 o M/M/c en estado estable, cuyas llegadas de clientes es un un proceso de
Poisson de parámetro λ:
1. El proceso de salidas de clientes es también un proceso de Poisson parámetro λ
2. La cantidad de clientes en el sistema en el tiempo T es independiente de la historia del proceso
de salidas en t<T

Previo a su demostración, este teorema habría sido anticipado por O’Brien en 1954 y Morse en
1955. La demostración realizada por Burke consistía en mostrar que los intervalos de tiempo entre
salidas consecutivas estaban distribuidos exponencial e independientemente con un parámetro igual
al rate de llegadas.
Posteriormente, se publica una demostración que generaliza otros casos: el criterio de Kolomogo-
rov, que establece que cualquier proceso de nacimiento-muerte es una cadena de Markov reversible,
y el teorema de Burke es un caso particular.

34
Figura 6.1: Idea gráfica para la demostración del teorema de Burke, a través del criterio de Klomo-
gorov.

Esta demostración puede parecer antiintuitiva en el sentido de que el proceso de salidas depende
directamente de las llegadas, y es independiente del proceso de servicios.

6.1.2. Sistema tándem o serie

Un primer caso sencillo a considerar es el de las llamadas redes tándem, en serie o secuenciales,
donde existe un único camino para los clientes del nodo k al nodo k+1, entrando en el nodo cero y
saliendo en el último.
El estado de un sistema secuencial de N nodos es un vector de N componentes (x1 , x2 , ..., xN )
las cuales indican la cantidad de clientes en cada uno de los nodos 1, 2, ..., N respectivamente
En la figura se muestra una red en serie de 2 nodos.

Figura 6.2: Red tándem de 2 nodos

El estado de este sistema podría representarse como un vector (n, m), indicando que hay n clien-
tes en el nodo 1 y m en el nodo 2.
Veamos ahora una característica importante de este tipo de sistemas: la cantidad de clientes
en un nodo y en otro son independientes. Las ecuaciones de flujo involucran:
•La tasa de entrada λi y salida µi a un nodo i, las cuales deben ser idénticas por el teorema de
Burke
•La probabilidad de que el sistema se encuentre en determinado estado (n, m), la cual es la

35
probabildiad conjunta de tener n clientes en un nodo y m en el otro rn,m . Las ecuaciones de flujo se
plantean en la tabla a continuación:

Figura 6.3: Ecuaciones de flujo para un sistema secuencial de 2 nodos, donde ri,j es la probabilidad
P
de que el sistema se encuentre en estado (i,j). Además, se sabe que m,n r(m,n) = 1.

Por otro lado, llamamos a la probabilidad de que haya n clientes en el nodo i rn,0 , y a la probabi-
lidad de que haya m clientes en el nodo j r0,m . Se tiene que:

λ n λ
rn,0 = ( ) (1 − )
µ1 µ1

λ m λ
r0,m = ( ) (1 − )
µ2 µ2

Finalmente, se tiene una demostración para la independencia de los eventos si se reemplaza

rn,m por rn,0 r0,m en cada una de las ecuaciones de flujo del sistema estacionario, es decir, que las
probabilidades conjuntas son, en todos los casos, iguales a multiplicar las probabilidades marginales.
rn,m = rn,0 r0,m Debe tenerse en cuenta que se conoce de antemano que la solución estacionaria
será única.
Sin embargo, según lo visto, el tiempo de espera en un servidor y en el otro, NO son nece-
sariamente independientes, pero sí lo son los tiempos totales, teniendo en cuenta el tiempo de
servicio.
Una vez mostrada la independencia entre las probabilidades de los distintos estados, se pueden
calcular los resultados para los principales parámetros como se hizo en el caso de sistemas simples,
ya que:

X X X
L= (n + m)rn,m = nrn,0 + r0,m m
n,m n m

Finalmente, por la fórmula de Little, los resultados son:

λ λ
L= +
µ1 − λ µ2 − λ

L 1 1
W = = +
λ µ1 − λ µ2 − λ

36
 1 1
Wq = W − ( + )
µ1 µ2

6.2. Redes de Jackson o Markovianas

Las redes de Jackson se tratan de un caso más general que el de redes secuenciales.
Una red se denomina Red de Jackson si, dada una red de n nodos, la misma cumple:

Los clientes llegan desde el exterior al nodo i-ésimo según un proceso de Poisson de tasa λi

Cada uno de los ci servidores del nodo i-ésimo tiene tiempo de servicio exponencial de pará-
metro µi

La probabilidad de que un cliente que termina servicio en el nodo i-ésimo se dirija al nodo
j-ésimo, rij , es independiente del estado del nodo j-ésimo

Un cliente que termina el servicio en el nodo i-ésimo puede abandonar la red con probabilidad
ri0
P
Para cada nodo j=0 nri j = 1, i = 1, ..., n

Las redes secuenciales son un tipo de Redes de Jackson.

6.2.1. Redes de Jackson Abiertas

Son redes con k nodos que contemplan la posibilidad de entrada de clientes desde el exterior.
De las propiedades que se vieron para redes de Jackson generales, las redes abiertas verifican
tres propiedades:

a La llegada de clientes al nodo i desde fuera del sistema sigue un proceso de Poisson de pa-
rámetro o tasa λi . También pueden llegar clientes al nodo i desde otros nodos de dentro de la
red.

b Cada nodo i consiste en ci servidores, cada uno con tiempo de servicio exponencial de pará-
metro µi

c El cliente una vez servido en el nodo i pasa (instantáneamente) a nodo j, j = 1, 2, ..., k con
probabilidad rij o abandona la red con probabilidad ri0

37
Figura 6.4: Representación de una Red de colas de Jackson abierta. Se tiene, en este caso particular,
λ2 = λ3 = 0 y r20 = 0

Dado que el flujo total de entrada a un nodo i (i 1, 2, ... , k) = debe ser igual al flujo total de salida
del nodo, se obtienen las siguientes ecuaciones de equilibrio:

k
X
Λi = λi + Λj rij
j=1

donde Λi son las llegadas totales al nodo i; el primer término λi se debe a las llegadas de fuera
del sistema y el segundo Λj rij a las llegadas desde otro nodo j.
Las k ecuaciones anteriores forman un sistema lineal con solución única, que se resuelve para
hallar las tasas de llegada a cada nodo Λi
Se pueden plantear las variables del sistema como vectores donde cada una de sus componentes
es su valor en dicho nodo

      
Λ1 λ1 r11 r12 ... r1k Λ1
      
Λ2  λ2   r21 r22 ... r2k  Λ2 
      
 = +
 ..   ..   ..   .. 
 
 .  .  .  . 
      
Λk λk rk1 rk2 ... rkk Λk

y despejando entonces matricialmente:

~ = (I − ~r)−1~λ
Λ (6.1)

Finalmente, a partir de este resultado puede calcularse, de forma análoga a un sistema simple,
la condicion de no saturación para un nodo i como:

Λi
ρi = <1
µ i ci

38
6.2.2. Redes de Jackson cerradas

En una red cerrada no entran ni salen calientes, el número de clientes es constante en el tiempo.
Se cumple que:

1. Cada nodo i es una cola M /M /ci

2. Al finalizar el proceso en el nodo i, un cliente pasa al nodo j con probabilidad ri j

3. Los tiempos de servicio siguen distribuciones exponenciales de tasa µi

En una red cerrada al no haber entradas ni salidas de clientes, resulta indispensable conocer el
número de clientes dentro de la red N, que permanece constante en el tiempo. Por este motivo,
el número medio de clientes en la red es constante:

L = N (cte.)

y las cantidades del tiempo medio de espera en la red y en cada nodo carecen de sentido. En
estos casos, el parámetro de importancia es la probabilidad pi de hallar una determinada cantidad
de clientes ni , en cada nodo i.
Se consideran k nodos por los cuales los clientes viajan indefinidamente, y como la tasa de en-
trada a un nodo es igual a la de salida, se tienen las ecuaciones de equilibrio:

k
X
Λi = Λj rij
j=1

que, si se ve, se corresponden con las ecuaciones de redes de Jackson abiertas, con la diferencia
de que λi = 0, i = 1, ..., k.

Figura 6.5: Representación de una Red de colas de Jackson cerrada, con sus ecuaciones de equili-
brio para unas determinadas relaciones entre nodos rij .

39
7. Conclusiones

Se han visto múltiples conceptos de la teoría de colas muy frecuentemente usados en sus aplica-
ciones. Mediante las herramientas vistas pueden modelarse sistemas muy generales y que cubren
muchos casos prácticos, como los ejemplos que se presentan en este capítulo.
Sin embargo existe basto desarrollo de otros modelos de colas, que involucran otras distribu-
ciones en los tiempos, limitaciones en la capacidad del sistema o la fuente de clientes, distintas
topologías de redes, etc. que han quedado por fuera del alcance de este trabajo, pero a tener en
cuenta al momento de considerar modelar un sistema.
Los ejemplos que se ven a continuación se narran como el razonamiento que se debe seguir
desde la observación de la situación que se querría modelar hasta la obtención de resultados.

7.1. Ejemplo 1. Cola simple abierta M/M/?

Veamos un caso muy general de la vida cotidiana que podríamos modelar con los conceptos que
se vieron de teoría de colas.
Se tiene un negocio familiar con un único empleado, Juan el padre de familia, atendiendo en
caja. Podemos decir que se trata un sistema de colas que presta el servicio de ventas, con un único
servidor c=1.
Se trata de una farmacia que planea mudarse a un barrio con alta tasa de demanda. Uno de los
hermanos decidió ir al nuevo lugar y llevar una cuenta de cuantos clientes se presentan en la farmacia
más cercana. Luego dividió la cantidad obtenida por la cantidad de horas que duró el experimento.
De esta manera, se obtuvo la tasa de llegada de clientes que se espera y es de λ = 7 clientes por
hora.
Otro de los hermanos decidió contar una cierta cantidad de veces cuanto tiempo tarda su padre
en atender a cada uno de los clientes. Obtiene el valor promedio de las mediciones y con ello un
valor medio del tiempo de servicio s, E[s] = 15 minutos = 1/4 hora. La tasa de servicios prestados
será entonces µ = 4
A pesar de que en realidad se presentaban menos clientes en el horario de la siesta, la familia
decide suponer que los clientes se presentarán en cualquier horario con igual probabilidad. De esta
manera, contando con la media de los datos, proponen que su farmacia es un sistema de colas M/M/1
para modelar el comportamiento de los tiempos de espera y acumulación de clientes.
Al obtener el parámetro ρ = 7/4, la familia obtiene la información necesaria para afirmar que los
clientes se acumularán a medida que transcurre el tiempo, ya que el sistema nunca alcanzará el
estado estable: ρ > 1.
La siguiente idea es analizar que sucedería si la hermana mayor, Julia, ocupara otro puesto aten-

40
diendo clientes en la caja. Es decir, se quiere modelar los resultados para un sistema M/M/2 con los
mismos parámetros.
Se obtiene en primer lugar que ρ = 7/2 ∗ 4 = 7/8, de manera que sí es posible alcanzar el estado
estacionario.
El siguiente paso es calcular las fórmulas vistas para sistemas M/M/c. Para ello pueden aplicarse
las ecuaciones vistas directamente o bien puede hallarse primero el valor de la fórmula de Erlang y
luego calcular los resultados a través de las fórmulas que involucran su resultado,

E(r, c)
W =
cµ(1 − ρ)

rE(r, c)
L=
c(1 − ρ)

7.2. Ejemplo 2. Red de Jackson abierta

Veamos ahora un caso de aplicación a las telecomunicaciones de la teoría de colas. El mismo se
trata de un ejercicio extraído del material de Teoría de Colas presentado por el Portal de Estadística
Aplicada:
”’Los servidores de dos terminales del aeropuerto de Madrid, según una disciplina FIFO, según
un proceso de Poisson reciben respectivamente 20 y 30 procesos de usuarios por minuto. El ser-
vidor de la primera terminal tiene capacidad para atender una media de cien procesos por minuto,
mientras que cualquiera de los dos procesadores del servidor de la segunda terminal puede atender
a veinticinco procesos, con tiempo de procesado exponenciales.”’
Se trata de dos terminales de un servidor que poseen una determinada capacidad de procesar
tareas que arriban. Podemos ir suponiendo que cada terminal representará un nodo en el que se
prestara el servicio ’procesar una tarea’ y la tarea es el cliente del sistema (requiere ser procesada).
Hasta ahora, sabemos que podemos tratar la cola de la misma forma que en el ejercicio 1: se atienden
los procesos en el orden en orden de llegada (FIFO). La tasa de llegada de tareas es de λ1 = 20
y λ2 = 30 a cada uno de los nodos. Por otro lado, nos dan la velocidad de procesamiento de cada
terminal. La tasa de cada uno de los procesadores es de µ1 = 100 procesos por minuto y µ2 = 25
procesos por minuto, si la primera terminal es el nodo 1 y la segunda el nodo 2. Como la segunda
terminal posee dos procesadores c2 = 2. El ejercicio continúa:
”’Cuando un proceso está a punto de finalizar en el servidor de la segunda terminal crea un nuevo
proceso hijo en el servidor de la primera terminal el 25 % de los casos, en otro caso termina totalmente
su ejecución. Por otra parte, los procesos que se encuentran a punto de finalizar en el servidor de
la primera terminal crean un nuevo proceso en su servidor el 20 % de los casos, en caso contrario
cuando terminan su ejecución envían otro proceso al servidor de la segunda terminal un 10 % de las
veces.”’
El nuevo proceso creado por la segunda terminal, delegado al procesamiento en la terminal 1
podría interpretarse como una probabilidad de un proceso saliente del nodo 2 hacia el nodo 1, con

41
r21 = 0,25 y r20 = 0,75. De la misma manera para los procesos creados en la primera terminal
entrantes a la terminal 2, y a sí misma: r11 = 0,2, r12 = 0,1.
Si se resuelve en la forma matricial que se vió en el capítulo de Redes de Jackson, se tiene por
resultado los parámetros del sistema:
      
Λ1 20 0,2 0,1 Λ
 = +   1
Λ2 30 0,25 0 Λ2

~ = (I~ − ~r)−1~λ
Λ

  
Λ135,5
 = 
Λ2 33,6

Con ello se puede calcular, en primer lugar, si el sistema se satura tras un determinado tiem-
po de recibir tareas. Esto es crucial a determinar en cualquier sistema informático que se quiera
implementar.
   
Λ1
ρ1
  =  µ1 c1 
Λ2
ρ2 µ2 c2

Sabiendo el resultado anterior para Λi , los valores de µi y c1 = 1 y c2 = 2:

   
ρ1 0, 35484
 = 
ρ2 0, 67096

De esta forma se sabe que el sistema no se satura y puede operar sin provocar, teoricamente,
errores de timeout.
Si los servidores se saturaran, también se sabe que una corrección es disminuir el valor de ρi
añadiendo procesadores a alguna de las terminales para aumentar la capacidad de procesamiento
en paralelo y de esa forma c1 o c2 serían mayores.

42
8. Anexo: Autoevaluación

1. ¿Qué parámetros describen a un sistema de colas?

Los más importantes son:

• el tiempo entre llegada de clientes, o tasa de clientes que entran al sistema (denotado como λ)
• tiempo de servicio o tasa de clientes que abandonan el sistema (denotado como µ)
• cantidad de servidores. (denotado como ̧)

Otras variables a considerar podrían ser:

• el algoritmo con el que se atiende a los clientes

• la capacidad máxima del sistema.
• cantidad de potenciales clientes (asumida por lo general infinita)

Además, se pueden considerar diversos comportamientos mas detallados, como la posibilidad

de que un cliente abandone la cola, o un sistema con múltiples pasos que se interconectan como en
el caso de las redes de colas.

2. ¿Qué parámetros se desean conocer?

Suele ser de interés conocer:

• el tiempo en promedio que un cliente pasa en la cola W

• el tiempo total en promedio que un cliente se encuentra en el sistema
• la cantidad media de clientes dentro del sistema
• la cantidad media de clientes en cola

También se puede buscar hallar otros resulados:

• la probabilidad de que el sistema este vacío

• la probabilidad de que un cliente sea atendido en menos de determinada catidad de tiempo
• la probabilidad de que los servidores se hallen sin clientes, es decir, el porcentaje de tiempo que
se encuentran vacíos

43
 Por lo general se modelan las colas como procesos de nacimiento-muerte o de conteo y se ha-
llan estos valores a partir de las probabilidades de encontrar n clientes en el sistema, planteando
ecuaciones de flujo.
3. ¿Cómo se puede determinar si existe un estado estable para un sistema de colas simple?

Un parámetro que permite conocer si el sistema llega a estado estable es la intensidad del tráfico
por servidor, o factor de utilización ρ = λ/cµ. Para que el sistema pueda alcanzar el estado estable,
se requiere ρ < 1.
Esta ecuación permite también variar la cantidad de servidores para hallar aquella que permita al
sistema alcanzar el estado estable.
4. ¿Qué sucede en caso de que el sistema no cumpla las condiciones para alcanzar el es-
tado estable?

Cuando el sistema se encuentra en estado estable, quiere decir que permanece con una deter-
minada cantidad de clientes en promedio, y se encuentra con cantidades diferentes al valor medio
con una determinada varianza.
Cuando esto no se cumple (para ρ ≥ 1) sucede que la cantidad media de clientes en el el sistema
diverge, al igual que el tiempo de espera, a medida que transcurre el tiempo en el sistema. Es decir,
estas cantidades aumentan indeterminadamente hasta el infinito.

5. ¿Cómo se relacionan el promedio de personas en el sistema con el tiempo de espera

medio?

El promedio de clientes en el sistema L y el tiempo de espera medio W se relacionan mediante

las fórmulas de Little

L = Wλ

6. ¿Qué distribuciones se podrían utilizar para describir los distintos parámetros y por qué?

Para describir los tiempos de servicio y los tiempos entre llegadas de clientes se suele utilizar
la distribución exponencial, lo que es lo mismo que considerar las llegadas y la tasa de servicios
prestados como variables aleatorias de Poisson.
Se suelen utilizar estas distribuciones ya que basta con conocer la media para expresar el modelo
matemático del sistema, la cual se puede obtener de la observación del sistema en funcionamiento
o de los datos de los servidores.
Además, estas distribuciones asumen que eventos diferentes (en tiempos diferentes) son inde-
pendientes entre sí

44
 7. ¿Qué representa la fórmula de Erlang?

La fórmula de Erlang permite conocer la probabilidad de que un cliente tenga que esperar. Es
decir, la probabilidad de que el sistema no se encuentre vacío ante la llegada de un cliente.

8. ¿Cómo se puede obtener el promedio de personas en el sistema asumiendo procesos

de Markov?

Como la fórmula de Erlang se relaciona con el tiempo de espera en los servidores, puede obte-
nerse este valor a partir de dicha fórmula, y luego despejar el número medio de personas a partir de
la fórmula de Little.
Para calcular estos valores se requiere conocer la tasa de entrada de clientes al sistema, la tasa
de servicio, y cantidad de servidores

9. ¿Qué es una red de colas? ¿Qué propiedad cumplen las redes con tasas de entradas de
Markov?

Una red de colas es un conjunto de nodos interrelacionados, de los cuales cada uno es un sistema
de colas simple.
Cada nodo posee una tasa de entrada y de salida. Según el teorema de Burke, una tasa de
entradas Poissoniana implica una tasa de salida con igual distribución y parámetro.
Luego se demosraría que esto es válido para cualquier proceso de Markov ya que la indepen-
dencia entre intervalos de tiempo hace que el proceso inverso sea simétrico en el tiempo

10. ¿Qué es una red de colas abierta? ¿Y una cerrada?

Una red de colas abierta permite la entrada de clientes externos al sistema en algún nodo, mintras
que las redes cerradas poseen una cantidad de clientes constante, desde el inicio hasta el fin, y
ningún cliente llega del exterior o abandona la red.
En este último caso, el parámetro que interesa encontrar es la probabilidad de encontrar una
cierta cantidad de clientes en cada nodo, en un determinado momento.

45
9. Bibliografía

9.1. Fuentes bibliográficas del contenido del trabajo práctico:

Fundamentals of Queueing Theory - Gross, Donald; Carl M. Harris (4ta edición)

Introduction to Queueing Theory and Stochastic Teletraffic Models - Moshe Zukerman (2000–2020)

Una introducción amable a la teoría de colas - Departamento de Ingeniería Telemática - Uni-

versidad Carlos III de Madrid

Teoría de colas aplicada al estudio del sistema de servicio de una farmacia - M.Sc. Ing. Eduardo
López Hung, M.Sc. Lic. Lai Gen Joa Triay (Revista Cubana de Informática Médica 2018:10(1)3-
15)

www.estadistica.net/INVESTIGACION/TEORIA-COLAS.pdf

Aplicando Teorıa
́ de Colas en Dirección de Operaciones - José Pedro García Sabater (Curso
2015 / 2016)

Material de la asignatura investigación operativa en Universidad Politécnica de Madrid (http://www.dma.eui.upm.

2010/transparencias/introducci○ %C3 %B3n_redes_colas.pdf)

Trabajo de fin de grado en estadística: Modelos de Teorías de Colas - Gabriel Esteban Veláz-
quez, Universidad de Sevilla

https://es.wikipedia.org/wiki/Agner_Krarup_Erlang

https://es.wikipedia.org/wiki/Unidad_Erlang

https://en.wikipedia.org/wiki/Burke %27s_theorem

https://www.fiwiki.org/images/6/6b/4._Redes_de_colas.pdf

9.2. Fuente de las imágenes:

Resultados de la búsqueda en Google Imágenes

https://www.moreno.marzolla.name/software/queueing/

Cuadros del libro Gross Fundamentals of Queueing Theory - Gross, Donald; Carl M. Harris (4ta
ed.)

https://www.randomservices.org/random/index.html

46
 https://twitter.com/doescience

De maku-ule - Trabajo propio, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?cu-

rid=3658880

CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=74038

El resto de las imágenes han sido hechas mediante el software Inkscape.

47