Teoría de Colas

Teoría de colas
La teoría de colas es el estudio matemático de las colas o líneas

de espera dentro de un sistema. Esta teoría estudia factores como
el tiempo de espera medio en las colas o la capacidad de trabajo
del sistema sin que llegue a colapsar. Dentro de las matemáticas,
la teoría de colas se engloba en la investigación de operaciones y
es un complemento muy importante a la teoría de sistemas y la
teoría de control. Se trata así de una teoría que encuentra
aplicación en una amplia variedad de situaciones como negocios,
comercio, industria, ingenierías, transporte y logística o
telecomunicaciones. Diagrama que muestra dos colas y
múltiples nodos servidores. La
En el caso concreto de la ingeniería, la teoría de colas permite teoría de colas estudia los tiempos
modelar sistemas en los que varios agentes que demandan cierto de espera y capacidad del sistema.
servicio o prestación, confluyen en un mismo servidor y, por lo
tanto, pueden registrarse esperas desde que un agente llega al
sistema y el servidor atiende sus demandas. En este sentido, la teoría es muy útil para modelar
procesos tales como la llegada de datos a una cola en ciencias de la computación, la congestión de red
de computadoras o de telecomunicación, o la implementación de una cadena productiva en la
ingeniería industrial.
En el contexto de la informática y de las tecnologías de la información y la comunicación las

situaciones de espera dentro de una red son más frecuentes. Así, por ejemplo, los procesos enviados a
un servidor para su ejecución forman colas de espera mientras no son atendidos; la información
solicitada, a través de Internet, a un servidor Web puede recibirse con demora debido a la congestión
en la red; también se puede recibir la señal de línea de la que depende nuestro teléfono móvil ocupada
si la central está colapsada en ese momento, etc.
Índice
Historia
Modelo de formación de colas
Objetivos
Elementos existentes en la teoría de colas
Notación Kendall
Estructuras típicas
Medidas de desempeño de estado estable
Modelos
M/M/1
M/M/s
Las limitaciones del acercamiento matemático
Aplicación a la telefonía
Modelos de colas con distribuciones no exponenciales
Véase también
Referencias
Bibliografía
Enlaces externos
Historia
El matemático danés Agner Krarup Erlang, trabajador de la Copenhagen Telephone Exchange,
publicó el primer artículo sobre la teoría de colas en 1909.1 Específicamente se preocupó del estudio
del problema de dimensionamiento de líneas y centrales de conmutación telefónica para el servicio de
llamadas.
Modelo de formación de colas

Se forman debido a un desequilibrio temporal entre la demanda del servicio y la capacidad del sistema
para suministrarlo.
En las formaciones de colas se habla de clientes, tales como máquinas dañadas a la espera de ser
rehabilitadas. Los clientes pueden esperar en cola debido a que los medios existentes sean
inadecuados para satisfacer la demanda del servicio; en este caso, la cola tiende a ser explosiva, es
decir, a ser cada vez más larga a medida que transcurre el tiempo. Los clientes puede que esperen
temporalmente, aunque las instalaciones de servicio sean adecuadas, porque los clientes llegados
anteriormente están siendo atendidos.
Objetivos
Los objetivos de la teoría de colas consisten en:
Identificar el nivel óptimo de capacidad del sistema que minimiza su coste.

Evaluar el impacto que las posibles alternativas de modificación de la capacidad del sistema
tendrían en su coste total.
Establecer un balance equilibrado (“óptimo”) entre las consideraciones cuantitativas de costes y
las cualitativas de servicio.
Prestar atención al tiempo de permanencia en el sistema o en la cola de espera.
Elementos existentes en la teoría de colas

Proceso básico de colas: Los clientes que requieren un
servicio se generan en una fase de entrada. Estos clientes
entran al sistema y se unen a una cola. En determinado
momento se selecciona un miembro de la cola, para
proporcionarle el servicio, mediante alguna regla conocida Figura 1.
como disciplina de servicio. Luego, se lleva a cabo el servicio
requerido por el cliente en un mecanismo de servicio,
después de lo cual el cliente sale del sistema de colas.
Fuente de entrada o población potencial: Una característica de la fuente de entrada es su
tamaño. El tamaño es el número total de clientes que pueden requerir servicio en determinado
momento. Puede suponerse que el tamaño es infinito o finito.
Cliente: Es todo individuo de la población potencial que solicita servicio como por ejemplo una
lista de trabajo esperando para imprimirse.
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.
Disciplina de la cola: La disciplina de la cola se refiere al orden en el que se seleccionan sus
miembros para recibir el servicio. Por ejemplo, puede ser:
FIFO (first in first out) primero en entrar, primero en salir, según la cual se atiende primero al
cliente que antes haya llegado.
LIFO (last in first out) también conocida como pila que consiste en atender primero al cliente
que ha llegado el último.
RSS (random selection of service) que selecciona los clientes de manera aleatoria, de
acuerdo a algún procedimiento de prioridad o a algún otro orden.
Processor Sharing – sirve a los clientes igualmente. La capacidad de la red se comparte entre
los clientes y todos experimentan con eficacia el mismo retraso.
Mecanismo de servicio: El mecanismo de servicio consiste en una o más instalaciones de

servicio, cada una de ellas con uno o más canales paralelos de servicio, llamados servidores.
Redes de colas: Sistema donde existen varias colas y los trabajos fluyen de una a otra. Por
ejemplo: las redes de comunicaciones o los sistemas operativos multitarea.
El proceso de servicio: Define cómo son atendidos los clientes.
Notación Kendall
David G. Kendall introdujo una notación de colas A/B/C en 1953. La notación de Kendall para
describir las colas y sus características puede encontrarse en Tijms, H.C,Algorithmic Analysis of
Queues, Capítulo 9 en A First Course in Stochastic Models, Wiley, Chichester, 2003. Ha sido desde
entonces extendida a 1/2/3/(4/5/6) donde los números se reemplazan con:
1. Un código que describe el proceso de llegada. Los códigos usados son:

M para "Markoviano" (la tasa de llegadas sigue una distribución de Poisson), significando una
distribución exponencial para los tiempos entre llegadas.
D para unos tiempos entre llegadas deterministas, es decir, no siguen un proceso probabilista
a la hora de su determinación.
G para una "distribución general" de los tiempos entre llegadas, o del régimen de llegadas.
2. Un código similar que representa el proceso de servicio (tiempo de servicio). Se usan los mismos
símbolos.
3. El número de canales de servicio (o servidores).
4. La capacidad del sistema, o el número máximo de clientes permitidos en el sistema incluyendo
esos en servicio. Cuando el número está al máximo, las llegadas siguientes son rechazadas. Un
caso particular de esta situación es el modelo M/M/n/n o Erlang-B, en el cual no hay cola de
espera, sino n recursos (servidores) y hasta n usuarios como máximo; si llega el usuario n+1, es
rechazado. Este último modelo es el que se aplica en telefonía convencional. Otro caso particular
es el modelo Erlang-C o M/M/n, donde la capacidad del sistema es ilimitada, aunque haya sólo n
recursos; en caso de llegar el recurso número n+1, pasará a una cola de espera, pero no es
rechazado.
5. El orden de prioridad en la que los trabajos en la cola son servidos:
First Come First Served (FCFS) o First In First Out (FIFO)
Last Come First Served (LCFS) o Last In First Out (LIFO)
Service In Random Order (SIRO)
Processor Sharing
6. El tamaño del origen de las llamadas. El tamaño de la población desde donde los clientes vienen.
Esto limita la tasa de llegadas.
Estructuras típicas
El primer sistema que se muestra en la figura, se llama un sistema
de un servidor y una cola. El segundo, una línea con múltiples
servidores. El tercer sistema, aquel en que cada servidor tiene una
línea de separación. El cuarto sistema, es una línea con servidores
en serie. Este modelo puede aplicarse a trabajos ordenador que
esperan tiempo de procesador.
Medidas de desempeño de estado

estable
En teoría de colas se utilizan comúnmente las siguientes medidas Figura 2.
de desempeño, estas se calculan de forma diferente según el
modelo de la línea de espera:
Ls = Cantidad esperada de clientes en un sistema
Lq = Cantidad esperada de clientes en una cola
Ws = Tiempo de espera en el sistema
Wq = Tiempo de espera anticipado en la cola
ρ = Factor de utilización del sistema
Modelos
M/M/1
En este modelo, según la notación de Kendall, la tasa de llegadas y la tasa de servicio siguen una
distribución de Poisson. Y hay un solo servidor. Las medidas de desempeño de estado estable se
calculan de la siguiente forma:
Donde λ es la tasa promedio de arribos al sistema y μ la tasa promedio de servicio.

Cabe resaltar que si λ ≥ μ el sistema es explosivo, además, Wq nunca será mayor que Ws.2
M/M/s
Este modelo supone que existen en el sistema s (entero positivo) servidores, en este caso las medidas
de desempeño se calcularán así3 :
Las limitaciones del acercamiento matemático

La teoría de formación de una cola es a menudo demasiado restrictiva matemáticamente para ser
capaz de modelar todas las situaciones verdaderas a nivel mundial. Por ejemplo; los modelos
matemáticos a menudo asumen el número de clientes, o la capacidad de la cola infinitos, cuando es
evidente que deben estar limitados.
Los medios alternativos del análisis de la teoría de colas consisten
generalmente en simulaciones de ordenador o en el análisis de datos experimentales.
Aplicación a la telefonía
Las redes telefónicas se diseñan para acomodar la intensidad ofrecida del tráfico con solamente una
pequeña pérdida. El funcionamiento de los sistemas depende de si la llamada es rechazada, de si está
perdida, etc. Normalmente los sistemas de desbordamiento hacen uso de rutas alternativas e incluso
estos sistemas tienen una capacidad de carga finita o máxima de tráfico. Sin embargo, el uso de las
colas permite que los sistemas esperen por las peticiones de su cliente hasta que los recursos libres
estén disponibles. Esto significa que si los niveles de la intensidad del tráfico exceden de la capacidad
disponible, las llamadas del cliente se perderían. La disciplina de colas determina la manera de cómo
manejar las llamadas de los clientes. Define la manera en que les servirán, la orden de las cuales se
sirven, y la manera en la que los recursos se dividen entre los clientes.
Modelos de colas con distribuciones no exponenciales

En particular, el supuesto de tiempos entre llegadas exponenciales implica que las llegadas ocurren al
azar (proceso de entrada de Poisson), lo cual es una aproximación razonable en muchas situaciones
pero no cuando las llegadas están programadas o reguladas con todo cuidado. Todavía más, las
distribuciones de tiempos de servicio reales con frecuencia se desvían bastante de la forma
exponencial, en particular cuando los requerimientos de servicio de los clientes son muy parecidos.
Por ello, es importante disponer de otros modelos de colas que usen otras distribuciones de
probabilidad.
Desafortunadamente, el análisis matemático de los modelos de colas con distribuciones
no exponenciales es mucho más difícil. Sin embargo, se han podido obtener algunos resultados útiles
con algunos modelos.4 :
Véase también
Unidad Erlang
Ingeniería industrial
Distribución de Poisson
Throughput
Planificador
Congestión vehicular
Red de flujo
Distribución de Erlang
Distribución Exponencial
Cola (estructura de datos)
Cola de prioridad (estructura de datos)
Congestión de red
Referencias
1. http://pass.maths.org.uk/issue2/erlang/index.html
2. Taha, Investigación de operaciones (2012). «18». Medidas de desempeño de estado estable
(Novena edición). PEARSON EDUCACIÓN. p. 612. ISBN 978-607-32-0796-6.
3. Lieberman, INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES (2010). «17». TEORÍA
DE COLAS (Novena edición). McGRAW-HILL/INTERAMERICANA EDITORES, S.A. DE C.V.
p. 725. ISBN 978-607-15-0308-4.
4. Lieberman, INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES (2010). «17». TEORÍA
DE COLAS (Novena edición). McGRAW-HILL/INTERAMERICANA EDITORES, S.A. DE C.V.
p. 737. ISBN 978-607-15-0308-4.
Bibliografía
Gross, Donald; Carl M. Harris (1998). Fundamentals of Queueing Theory. Wiley. ISBN 0-471-32812-
X. Online (https://books.google.com/books?id=K3lQGeCtAJgC)
Deitel, Harvey M. (1984) [1982]. An introduction to operating systems (https://archive.org/details/in
troductiontoopdeit00deit/page/673) (revisited first edición). Addison-Wesley. p. 673 (https://archiv
e.org/details/introductiontoopdeit00deit/page/673). ISBN 0-201-14502-2. chap.15, pp. 380–412
Lazowska, Edward D.; John Zahorjan; G. Scott Graham; Kenneth C. Sevcik (1984). Quantitative
System Performance: Computer System Analysis Using Queueing Network Models (https://archiv
e.org/details/quantitativesyst00lazo). Prentice-Hall, Inc. ISBN 0-13-746975-6.
Zukerman, Moshe. Introduction to Queueing Theory and Stochastic Teletraffic Models (http://www.
ee.cityu.edu.hk/~zukerman/classnotes.pdf).
Enlaces externos
Artículos de Teoría de Colas (http://www.gestiondeoperaciones.net/category/lineas-de-espera/)
Queueing Theory Basics (https://web.archive.org/web/20130123204351/http://eventhelix.com/Rea
ltimeMantra/CongestionControl/queueing_theory.htm)
Calculadora de Teoría de Colas (http://www.supositorio.com/rcalc/rcalclite_esp.htm)
Obtenido de «https://es.wikipedia.org/w/index.php?title=Teoría_de_colas&oldid=136360428»
Esta página se editó por última vez el 15 jun 2021 a las 21:57.
El texto está disponible bajo la Licencia Creative Commons Atribución Compartir Igual 3.0;
pueden aplicarse cláusulas
adicionales. Al usar este sitio, usted acepta nuestros términos de uso y nuestra política de privacidad.
Wikipedia® es una marca registrada de la Fundación Wikimedia, Inc., una organización sin ánimo de lucro.

Teoría de Colas

Cargado por

Copyright:

Formatos disponibles

Teoría de Colas

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Teoría de Colas

Cargado por

Copyright:

Formatos disponibles

Teoría de colas

La teoría de colas es el estudio matemático de las colas o líneas

En el contexto de la informática y de las tecnologías de la información y la comunicación las

Modelo de formación de colas

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

Elementos existentes en la teoría de colas

Mecanismo de servicio: El mecanismo de servicio consiste en una o más instalaciones de

El proceso de servicio: Define cómo son atendidos los clientes.

1. Un código que describe el proceso de llegada. Los códigos usados son:

Medidas de desempeño de estado

Ls = Cantidad esperada de clientes en un sistema

Lq = Cantidad esperada de clientes en una cola

Ws = Tiempo de espera en el sistema

Wq = Tiempo de espera anticipado en la cola

ρ = Factor de utilización del sistema

Donde λ es la tasa promedio de arribos al sistema y μ la tasa promedio de servicio.

Las limitaciones del acercamiento matemático

Modelos de colas con distribuciones no exponenciales

También podría gustarte