La teoría de las colas es el estudio matemático de las filas de espera o colas . [1] Se construye un modelo de colas de modo que se puedan predecir las longitudes de las colas y el tiempo de espera. [1] La teoría de las colas generalmente se considera una rama de la investigación de operaciones porque los resultados se utilizan a menudo al tomar decisiones comerciales sobre los recursos necesarios para proporcionar un servicio.
La teoría de las colas tiene su origen en la investigación de Agner Krarup Erlang cuando creó modelos para describir el sistema de la empresa Copenhagen Telephone Exchange, una empresa danesa. [1] Desde entonces, las ideas han tenido aplicaciones que incluyen telecomunicaciones , ingeniería de tráfico , informática [2] y, particularmente en ingeniería industrial , en el diseño de fábricas, tiendas, oficinas y hospitales, así como en la gestión de proyectos. [3] [4]
Ortografía
La ortografía "cola" sobre "cola" se encuentra típicamente en el campo de la investigación académica. De hecho, una de las revistas emblemáticas del campo es Queueing Systems .
Nodos de cola únicos
Se puede pensar en una cola o un nodo de cola como casi una caja negra . Los trabajos o "clientes" llegan a la cola, posiblemente esperan algún tiempo, tardan algún tiempo en procesarse y luego salen de la cola.
Sin embargo, el nodo de cola no es una caja negra pura, ya que se necesita cierta información sobre el interior del nodo de cola. La cola tiene uno o más "servidores", cada uno de los cuales puede emparejarse con un trabajo que llega hasta que sale, después de lo cual ese servidor estará libre para emparejarse con otro trabajo que llegue.
Una analogía que se utiliza a menudo es la del cajero de un supermercado. Hay otros modelos, pero este es uno que se encuentra comúnmente en la literatura. Los clientes llegan, son procesados por el cajero y se van. Cada cajero procesa un cliente a la vez y, por lo tanto, este es un nodo de cola con un solo servidor. Una configuración en la que un cliente se irá inmediatamente si el cajero está ocupado cuando llega el cliente se denomina cola sin búfer (o sin "área de espera" o términos similares). Una configuración con una zona de espera para hasta n clientes se denomina cola con un búfer de tamaño n .
Proceso de nacimiento-muerte
El comportamiento de una sola cola (también llamado "nodo de cola") se puede describir mediante un proceso de nacimiento-muerte , que describe las llegadas y salidas de la cola, junto con la cantidad de trabajos (también llamados "clientes" o "solicitudes ", o cualquier otra cosa, dependiendo del campo) actualmente en el sistema. Una llegada aumenta el número de trabajos en 1 y una salida (un trabajo que completa su servicio) reduce k en 1.
Equilibrar ecuaciones
Las ecuaciones de estado estacionario para el proceso de nacimiento y muerte, conocidas como ecuaciones de equilibrio , son las siguientes. Aquídenota la probabilidad de estado estable de estar en el estado n .
Las dos primeras ecuaciones implican
y
Por inducción matemática,
La condición lleva a:
que, junto con la ecuación para , describe completamente las probabilidades de estado estacionario requeridas.
Notación de Kendall
Los nodos de cola única generalmente se describen usando la notación de Kendall en la forma A / S / c donde A describe la distribución de duraciones entre cada llegada a la cola, S la distribución de los tiempos de servicio para trabajos yc el número de servidores en el nodo. [5] [6] Para un ejemplo de la notación, la cola M / M / 1 es un modelo simple en el que un solo servidor atiende trabajos que llegan de acuerdo con un proceso de Poisson (donde las duraciones entre llegadas se distribuyen exponencialmente ) y tienen exponencialmente tiempos de servicio distribuidos (la M denota un proceso de Markov ). En una cola M / G / 1 , la G significa "general" e indica una distribución de probabilidad arbitraria para los tiempos de servicio.
Ejemplo de análisis de una cola M / M / 1
Considere una cola con un servidor y las siguientes características:
- λ : la tasa de llegada (el tiempo esperado entre la llegada de cada cliente, por ejemplo, 30 segundos);
- μ : el recíproco del tiempo medio de servicio (el número esperado de finalizaciones consecutivas del servicio por la misma unidad de tiempo, por ejemplo, por 30 segundos);
- n : el parámetro que caracteriza el número de clientes en el sistema;
- P n : la probabilidad de que haya n clientes en el sistema en estado estacionario.
Además, sea E n el número de veces que el sistema entra en el estado n y L n el número de veces que el sistema sale del estado n . Entonces para todo n , | E n - L n | ∈ {0, 1}. Es decir, el número de veces que el sistema sale de un estado difiere como máximo en 1 del número de veces que entra en ese estado, ya que volverá a ese estado en algún momento en el futuro ( E n = L n ) o no. (| E norte - L norte | = 1).
Cuando el sistema llega a un estado estable, la tasa de llegada debe ser igual a la tasa de salida.
Por lo tanto, las ecuaciones de equilibrio
implicar
El hecho de que conduce a la fórmula de distribución geométrica
dónde
Cola simple de dos ecuaciones
Se atribuye a Erlang un sistema de colas básico común , y es una modificación de la Ley de Little . Dada una tasa de llegada λ , una tasa de abandono σ y una tasa de salida μ , la longitud de la cola L se define como:
Suponiendo una distribución exponencial de las tarifas, el tiempo de espera W se puede definir como la proporción de llegadas atendidas. Esto es igual a la tasa de supervivencia exponencial de aquellos que no abandonan durante el período de espera, lo que da:
La segunda ecuación se reescribe comúnmente como:
El modelo de una caja de dos etapas es común en epidemiología. [7]
Resumen del desarrollo de la teoría.
En 1909, Agner Krarup Erlang , un ingeniero danés que trabajaba para la Central Telefónica de Copenhague, publicó el primer artículo sobre lo que ahora se llamaría teoría de las colas. [8] [9] [10] Modeló el número de llamadas telefónicas que llegan a una central mediante un proceso de Poisson y resolvió la cola M / D / 1 en 1917 y el modelo de cola M / D / k en 1920. [11] En Notación de Kendall:
- M significa Markov o sin memoria y significa que las llegadas ocurren de acuerdo con un proceso de Poisson;
- D significa determinista y significa trabajos que llegan a la cola y requieren una cantidad fija de servicio;
- k describe el número de servidores en el nodo de cola ( k = 1, 2, ...).
Si hay más trabajos en el nodo que servidores, los trabajos se pondrán en cola y esperarán el servicio.
La cola M / G / 1 fue resuelta por Felix Pollaczek en 1930, [12] una solución luego reformulada en términos probabilísticos por Aleksandr Khinchin y ahora conocida como la fórmula Pollaczek-Khinchine . [11] [13]
Después de la década de 1940, la teoría de las colas se convirtió en un área de investigación de interés para los matemáticos. [13] En 1953, David George Kendall resolvió la cola GI / M / k [14] e introdujo la notación moderna para las colas, ahora conocida como notación de Kendall . En 1957 Pollaczek estudió el GI / G / 1 utilizando una ecuación integral . [15] John Kingman dio una fórmula para el tiempo medio de espera en una cola G / G / 1 : la fórmula de Kingman . [dieciséis]
Leonard Kleinrock trabajó en la aplicación de la teoría de las colas a la conmutación de mensajes a principios de la década de 1960 y la conmutación de paquetes a principios de la década de 1970. Su contribución inicial a este campo fue su tesis doctoral en el Instituto Tecnológico de Massachusetts en 1962, publicada en forma de libro en 1964. Su trabajo teórico publicado a principios de la década de 1970 apoyó el uso de la conmutación de paquetes en ARPANET , un precursor de Internet.
El método geométrico matricial y los métodos analíticos matriciales han permitido considerar colas con distribuciones de tiempo de servicio y entre llegadas distribuidas por tipo de fase . [17]
Los sistemas con órbitas acopladas son una parte importante de la teoría de las colas en la aplicación a las redes inalámbricas y al procesamiento de señales. [18]
Problemas como las métricas de rendimiento para la cola M / G / k siguen siendo un problema abierto. [11] [13]
Disciplinas de servicio
Se pueden utilizar varias políticas de programación en los nodos de cola:
- Primero en entrar primero en salir
- También llamado primero en llegar, primero en ser atendido (FCFS), [19] este principio establece que los clientes son atendidos uno a la vez y que el cliente que ha estado esperando más tiempo es atendido primero. [20]
- Último en entrar primero en salir
- Este principio también atiende a los clientes de uno en uno, pero el cliente con el menor tiempo de espera será el primero en ser atendido. [20] También conocido como pila .
- Compartir procesador
- La capacidad de servicio se comparte equitativamente entre los clientes. [20]
- Prioridad
- Se atiende primero a los clientes con alta prioridad. [20] Las colas de prioridad pueden ser de dos tipos, no preventivas (donde un trabajo en servicio no se puede interrumpir) y preventivas (donde un trabajo en servicio puede ser interrumpido por un trabajo de mayor prioridad). No se pierde trabajo en ninguno de los modelos. [21]
- El trabajo más corto primero
- El siguiente trabajo que se servirá es el que tenga el tamaño más pequeño [22]
- Primero el trabajo más corto preventivo
- El siguiente trabajo que se publicará es el que tenga el tamaño original más pequeño [23]
- El tiempo de procesamiento restante más corto
- El siguiente trabajo a realizar es el que tiene el requisito de procesamiento restante más pequeño. [24]
- Instalación de servicio
- Servidor único: los clientes se alinean y solo hay un servidor
- Varios servidores paralelos: cola única: los clientes se alinean y hay varios servidores
- Varios servidores: varias colas: hay muchos contadores y los clientes pueden decidir dónde hacer la cola.
- Servidor no confiable
Las fallas del servidor ocurren de acuerdo con un proceso estocástico (generalmente Poisson) y son seguidas por los períodos de configuración durante los cuales el servidor no está disponible. El cliente interrumpido permanece en el área de servicio hasta que se arregle el servidor. [25]
- Comportamiento de espera del cliente
- Rechazo: clientes que deciden no unirse a la cola si es demasiado larga
- Jockeying: los clientes cambian entre las colas si creen que se les atenderá más rápido al hacerlo.
- Renegación: los clientes abandonan la cola si han esperado demasiado para recibir el servicio.
Los clientes que llegan no atendidos (ya sea porque la cola no tiene búfer o debido a que el cliente se niega o se niega) también se conocen como abandonos y la tasa promedio de abandonos es un parámetro importante que describe una cola.
Redes de cola
Las redes de colas son sistemas en los que varias colas están conectadas por lo que se conoce como enrutamiento del cliente. Cuando un cliente recibe servicio en un nodo, puede unirse a otro nodo y hacer cola para recibir servicio o abandonar la red.
Para redes de m nodos, el estado del sistema se puede describir mediante un vector m –dimensional ( x 1 , x 2 , ..., x m ) donde x i representa el número de clientes en cada nodo.
La red de colas más simple y no trivial se llama colas en tándem . [26] Los primeros resultados significativos en esta área fueron las redes Jackson , [27] [28] para las cuales existe una distribución estacionaria en forma de producto eficiente y el análisis del valor medio [29] que permite medir métricas promedio como el rendimiento y los tiempos de permanencia. calculado. [30] Si el número total de clientes en la red permanece constante, la red se denomina red cerrada y también se ha demostrado que tiene una distribución estacionaria en forma de producto en el teorema de Gordon-Newell . [31] Este resultado se extendió a la red BCMP [32] donde se muestra que una red con tiempos de servicio, regímenes y enrutamiento de clientes muy generales también exhibe una distribución estacionaria en forma de producto. La constante de normalización se puede calcular con el algoritmo de Buzen , propuesto en 1973. [33]
También se han investigado redes de clientes , redes Kelly donde los clientes de diferentes clases experimentan diferentes niveles de prioridad en diferentes nodos de servicio. [34] Otro tipo de red son las redes G propuestas por primera vez por Erol Gelenbe en 1993: [35] estas redes no asumen distribuciones de tiempo exponenciales como la clásica Red Jackson.
Algoritmos de enrutamiento
En redes de tiempo discreto donde existe una restricción sobre qué nodos de servicio pueden estar activos en cualquier momento, el algoritmo de programación de peso máximo elige una política de servicio para brindar un rendimiento óptimo en el caso de que cada trabajo visite solo una persona [19] nodo de servicio . En el caso más general en el que los trabajos pueden visitar más de un nodo, el enrutamiento de contrapresión proporciona un rendimiento óptimo. Un programador de red debe elegir un algoritmo de cola , que afecta las características de la red más grande [ cita requerida ] . Consulte también Programación estocástica para obtener más información sobre la programación de sistemas de colas.
Límites medios de campo
Los modelos de campo medio consideran el comportamiento limitante de la medida empírica (proporción de colas en diferentes estados) cuando el número de colas ( m arriba) llega al infinito. El impacto de otras colas en cualquier cola de la red se aproxima mediante una ecuación diferencial. El modelo determinista converge a la misma distribución estacionaria que el modelo original. [36]
Aproximaciones de tráfico pesado / difusión
En un sistema con altas tasas de ocupación (utilización cercana a 1) se puede utilizar una aproximación de tráfico pesado para aproximar el proceso de longitud de la cola mediante un movimiento browniano reflejado , [37] proceso de Ornstein-Uhlenbeck o un proceso de difusión más general . [38] El número de dimensiones del proceso browniano es igual al número de nodos de cola, con la difusión restringida al orthant no negativo .
Límites de fluidos
Los modelos fluidos son análogos deterministas continuos de las redes de colas que se obtienen tomando el límite cuando el proceso se escala en el tiempo y el espacio, permitiendo objetos heterogéneos. Esta trayectoria escalada converge a una ecuación determinista que permite comprobar la estabilidad del sistema. Se sabe que una red de colas puede ser estable, pero tener un límite de fluidos inestable. [39]
Ver también
- Modelo Ehrenfest
- Unidad de Erlang
- Simulación de red
- Gestión de la producción de proyectos
- Área de cola
- Retraso en la cola
- Sistema de gestión de colas
- Regla empírica de las colas
- Detección temprana aleatoria
- Teoría de la renovación
- Rendimiento
- Programación (informática)
- Embotellamiento
- Modelo de generación de tráfico
- Red de flujo
Referencias
- ↑ a b c Sundarapandian, V. (2009). "7. Teoría de las colas". Probabilidad, estadística y teoría de colas . Aprendizaje PHI. ISBN 978-8120338449.
- ^ Lawrence W. Dowdy, Virgilio AF Almeida, Daniel A. Menasce. "Performance by Design: Computer Capacity Planning by Example" . Archivado desde el original el 6 de mayo de 2016 . Consultado el 8 de julio de 2009 .
- ^ Schlechter, Kira (March 2, 2009). "Hershey Medical Center to open redesigned emergency room". The Patriot-News. Archived from the original on June 29, 2016. Retrieved March 12, 2009.
- ^ Mayhew, Les; Smith, David (December 2006). Using queuing theory to analyse completion times in accident and emergency departments in the light of the Government 4-hour target. Cass Business School. ISBN 978-1-905752-06-5. Retrieved 2008-05-20.[permanent dead link]
- ^ Tijms, H.C, Algorithmic Analysis of Queues", Chapter 9 in A First Course in Stochastic Models, Wiley, Chichester, 2003
- ^ Kendall, D. G. (1953). "Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain". The Annals of Mathematical Statistics. 24 (3): 338–354. doi:10.1214/aoms/1177728975. JSTOR 2236285.
- ^ Hernández-Suarez, Carlos (2010). "An application of queuing theory to SIS and SEIS epidemic models". Math. Biosci. 7 (4): 809–823. doi:10.3934/mbe.2010.7.809. PMID 21077709.
- ^ "Agner Krarup Erlang (1878-1929) | plus.maths.org". Pass.maths.org.uk. 1997-04-30. Archived from the original on 2008-10-07. Retrieved 2013-04-22.
- ^ Asmussen, S. R.; Boxma, O. J. (2009). "Editorial introduction". Queueing Systems. 63 (1–4): 1–2. doi:10.1007/s11134-009-9151-8. S2CID 45664707.
- ^ Erlang, Agner Krarup (1909). "The theory of probabilities and telephone conversations" (PDF). Nyt Tidsskrift for Matematik B. 20: 33–39. Archived from the original (PDF) on 2011-10-01.
- ^ a b c Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems. 63 (1–4): 3–4. doi:10.1007/s11134-009-9147-4. S2CID 38588726.
- ^ Pollaczek, F., Ueber eine Aufgabe der Wahrscheinlichkeitstheorie, Math. Z. 1930
- ^ a b c Whittle, P. (2002). "Applied Probability in Great Britain". Operations Research. 50 (1): 227–239. doi:10.1287/opre.50.1.227.17792. JSTOR 3088474.
- ^ Kendall, D.G.:Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain, Ann. Math. Stat. 1953
- ^ Pollaczek, F., Problèmes Stochastiques posés par le phénomène de formation d'une queue
- ^ Kingman, J. F. C.; Atiyah (October 1961). "The single server queue in heavy traffic". Mathematical Proceedings of the Cambridge Philosophical Society. 57 (4): 902. Bibcode:1961PCPS...57..902K. doi:10.1017/S0305004100036094. JSTOR 2984229.
- ^ Ramaswami, V. (1988). "A stable recursion for the steady state vector in markov chains of m/g/1 type". Communications in Statistics. Stochastic Models. 4: 183–188. doi:10.1080/15326348808807077.
- ^ Morozov, E. (2017). "Stability analysis of a multiclass retrial system withcoupled orbit queues". Proceedings of 14th European Workshop. 17: 73–90. doi:10.1007/978-3-319-66583-2-6 (inactive 31 May 2021).CS1 maint: DOI inactive as of May 2021 (link)
- ^ a b Manuel, Laguna (2011). Business Process Modeling, Simulation and Design. Pearson Education India. p. 178. ISBN 9788131761359. Retrieved 6 October 2017.
- ^ a b c d Penttinen A., Chapter 8 – Queueing Systems, Lecture Notes: S-38.145 - Introduction to Teletraffic Theory.
- ^ Harchol-Balter, M. (2012). "Scheduling: Non-Preemptive, Size-Based Policies". Performance Modeling and Design of Computer Systems. pp. 499–507. doi:10.1017/CBO9781139226424.039. ISBN 9781139226424.
- ^ Andrew S. Tanenbaum; Herbert Bos (2015). Modern Operating Systems. Pearson. ISBN 978-0-13-359162-0.
- ^ Harchol-Balter, M. (2012). "Scheduling: Preemptive, Size-Based Policies". Performance Modeling and Design of Computer Systems. pp. 508–517. doi:10.1017/CBO9781139226424.040. ISBN 9781139226424.
- ^ Harchol-Balter, M. (2012). "Scheduling: SRPT and Fairness". Performance Modeling and Design of Computer Systems. pp. 518–530. doi:10.1017/CBO9781139226424.041. ISBN 9781139226424.
- ^ Dimitriou, I. (2019). "A Multiclass Retrial System With Coupled Orbits And Service Interruptions: Verification of Stability Conditions". Proceedings of FRUCT 24. 7: 75–82.
- ^ "Archived copy" (PDF). Archived (PDF) from the original on 2017-03-29. Retrieved 2018-08-02.CS1 maint: archived copy as title (link)
- ^ Jackson, J. R. (1957). "Networks of Waiting Lines". Operations Research. 5 (4): 518–521. doi:10.1287/opre.5.4.518. JSTOR 167249.
- ^ Jackson, James R. (Oct 1963). "Jobshop-like Queueing Systems". Management Science. 10 (1): 131–142. doi:10.1287/mnsc.1040.0268. JSTOR 2627213.
- ^ Reiser, M.; Lavenberg, S. S. (1980). "Mean-Value Analysis of Closed Multichain Queuing Networks". Journal of the ACM. 27 (2): 313. doi:10.1145/322186.322195. S2CID 8694947.
- ^ Van Dijk, N. M. (1993). "On the arrival theorem for communication networks". Computer Networks and ISDN Systems. 25 (10): 1135–2013. doi:10.1016/0169-7552(93)90073-D. Archived from the original on 2019-09-24. Retrieved 2019-09-24.
- ^ Gordon, W. J.; Newell, G. F. (1967). "Closed Queuing Systems with Exponential Servers". Operations Research. 15 (2): 254. doi:10.1287/opre.15.2.254. JSTOR 168557.
- ^ Baskett, F.; Chandy, K. Mani; Muntz, R.R.; Palacios, F.G. (1975). "Open, closed and mixed networks of queues with different classes of customers". Journal of the ACM. 22 (2): 248–260. doi:10.1145/321879.321887. S2CID 15204199.
- ^ Buzen, J. P. (1973). "Computational algorithms for closed queueing networks with exponential servers" (PDF). Communications of the ACM. 16 (9): 527–531. doi:10.1145/362342.362345. S2CID 10702. Archived (PDF) from the original on 2016-05-13. Retrieved 2015-09-01.
- ^ Kelly, F. P. (1975). "Networks of Queues with Customers of Different Types". Journal of Applied Probability. 12 (3): 542–554. doi:10.2307/3212869. JSTOR 3212869.
- ^ Gelenbe, Erol (Sep 1993). "G-Networks with Triggered Customer Movement". Journal of Applied Probability. 30 (3): 742–748. doi:10.2307/3214781. JSTOR 3214781.
- ^ Bobbio, A.; Gribaudo, M.; Telek, M. S. (2008). "Analysis of Large Scale Interacting Systems by Mean Field Method". 2008 Fifth International Conference on Quantitative Evaluation of Systems. p. 215. doi:10.1109/QEST.2008.47. ISBN 978-0-7695-3360-5. S2CID 2714909.
- ^ Chen, H.; Whitt, W. (1993). "Diffusion approximations for open queueing networks with service interruptions". Queueing Systems. 13 (4): 335. doi:10.1007/BF01149260. S2CID 1180930.
- ^ Yamada, K. (1995). "Diffusion Approximation for Open State-Dependent Queueing Networks in the Heavy Traffic Situation". The Annals of Applied Probability. 5 (4): 958–982. doi:10.1214/aoap/1177004602. JSTOR 2245101.
- ^ Bramson, M. (1999). "A stable queueing network with unstable fluid model". The Annals of Applied Probability. 9 (3): 818–853. doi:10.1214/aoap/1029962815. JSTOR 2667284.
Otras lecturas
- Gross, Donald; Carl M. Harris (1998). Fundamentals of Queueing Theory. Wiley. ISBN 978-0-471-32812-4. Online
- Zukerman, Moshe (2013). Introduction to Queueing Theory and Stochastic Teletraffic Models (PDF). arXiv:1307.2968.
- Deitel, Harvey M. (1984) [1982]. An introduction to operating systems (revisited first ed.). Addison-Wesley. p. 673. ISBN 978-0-201-14502-1. chap.15, pp. 380–412
- Newell, Gordron F. (1 June 1971). Applications of Queueing Theory. Chapman and Hall.
- Leonard Kleinrock, Information Flow in Large Communication Nets, (MIT, Cambridge, May 31, 1961) Proposal for a Ph.D. Thesis
- Leonard Kleinrock. Information Flow in Large Communication Nets(RLE Quarterly Progress Report, July 1961)
- Leonard Kleinrock. Communication Nets: Stochastic Message Flow and Delay(McGraw-Hill, New York, 1964)
- Kleinrock, Leonard (2 January 1975). Queueing Systems: Volume I – Theory. New York: Wiley Interscience. pp. 417. ISBN 978-0471491101.
- Kleinrock, Leonard (22 April 1976). Queueing Systems: Volume II – Computer Applications. New York: Wiley Interscience. pp. 576. ISBN 978-0471491118.
- Lazowska, Edward D.; John Zahorjan; G. Scott Graham; Kenneth C. Sevcik (1984). Quantitative System Performance: Computer System Analysis Using Queueing Network Models. Prentice-Hall, Inc. ISBN 978-0-13-746975-8.
- Jon Kleinberg; Éva Tardos (30 June 2013). Algorithm Design. Pearson. ISBN 978-1-292-02394-6.
enlaces externos
- Queueing theory calculator
- Teknomo's Queueing theory tutorial and calculators
- Office Fire Emergency Evacuation Simulation on YouTube
- Virtamo's Queueing Theory Course
- Myron Hlynka's Queueing Theory Page
- Queueing Theory Basics
- A free online tool to solve some classical queueing systems
- JMT: an open source graphical environment for queueing theory
- LINE: a general-purpose engine to solve queueing models
- What You Hate Most About Waiting in Line: (It’s not the length of the wait.), by Seth Stevenson, Slate, 2012 – popular introduction