En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , un sistema de sondeo o modelo de sondeo es un sistema en el que un solo servidor visita un conjunto de colas en algún orden. [1] El modelo tiene aplicaciones en redes informáticas y telecomunicaciones , [2] fabricación [3] [4] y gestión del tráfico por carretera . El término sistema de sondeo se acuñó al menos en 1968 [5] [6] y el primer estudio de un sistema de este tipo en 1957, donde se modeló a un solo reparador que reparaba máquinas en la industria algodonera británica. [7]
Generalmente se supone que el servidor visita las diferentes colas de manera cíclica. [1] Existen resultados exactos para tiempos de espera, longitudes de cola marginales y longitudes de cola conjuntas [8] en épocas de sondeo en ciertos modelos. [9] Se pueden aplicar técnicas de análisis de valor medio para calcular cantidades promedio. [10]
En un límite fluido , donde llega una gran cantidad de trabajos pequeños, se puede considerar que los nodos individuales se comportan de manera similar a las colas fluidas (con un proceso de dos estados). [11]
El servidor elige cuándo avanzar al siguiente nodo según uno de los siguientes criterios: [12]
servicio exhaustivo, donde un nodo continúa recibiendo servicio hasta que el búfer esté vacío.
servicio cerrado, donde el nodo atiende todo el tráfico que estaba presente en el instante en que el servidor llegó y comenzó a prestar servicio, pero las llegadas posteriores durante este tiempo de servicio deben esperar hasta la siguiente visita al servidor.
servicio limitado, donde se puede atender un número máximo fijo de trabajos en cada visita del servidor. [13]
Si un nodo de cola está vacío, el servidor se mueve inmediatamente para atender al siguiente nodo de cola.
El tiempo que tarda en cambiar del nodo de servicio i − 1 al nodo i se denota por la variable aleatoria d i .
Utilización
Defina ρ i = λ i E( S i ) y escriba ρ = ρ 1 + ρ 2 + … + ρ n . Entonces ρ es la fracción de tiempo a largo plazo que el camarero pasa atendiendo a los clientes. [14]
Tiempo de espera
Tiempo de espera previsto
Para el servicio cerrado, el tiempo de espera esperado en el nodo i es [12]
y para un servicio exhaustivo
donde C i es una variable aleatoria que denota el tiempo entre entradas al nodo i y [15]
La varianza de C i es más complicada y un cálculo directo requiere resolver n 2 ecuaciones lineales y n 2 incógnitas, [16] sin embargo es posible realizar el cálculo a partir de n ecuaciones. [17]
Tránsito pesado
El proceso de carga de trabajo se puede aproximar mediante un movimiento browniano reflejado en un sistema altamente cargado y adecuadamente escalado si el cambio de servidores es inmediato [18] y un proceso de Bessel cuando el cambio de servidores lleva tiempo. [19]
Aplicaciones
Se han utilizado sistemas de sondeo para modelar redes Token Ring . [20]
Enlaces externos
Bibliografía sobre modelos de sondeo (artículos publicados entre 1984 y 1993) de Hideaki Takagi
Referencias
^ ab Boxma, DO ; Weststrate, JA (1989). "Tiempos de espera en sistemas de sondeo con enrutamiento de servidores Markovianos". Messung, Modellierung und Bewertung von Rechensystemen und Netzen . Informatik-Fachberichte. vol. 218. pág. 89. doi :10.1007/978-3-642-75079-3_8. ISBN 978-3-540-51713-9.
^ Carsten, R.; Newhall, E.; Posner, M. (1977). "Un análisis simplificado de los tiempos de escaneo en un bucle Newhall asimétrico con servicio exhaustivo". IEEE Transactions on Communications . 25 (9): 951. doi :10.1109/TCOM.1977.1093936.
^ Karmarkar, EE. UU. (1987). "Tamaños de lotes, tiempos de entrega e inventarios en proceso". Management Science . 33 (3): 409–418. doi :10.1287/mnsc.33.3.409. JSTOR 2631860.
^ Zipkin, PH (1986). "Modelos para el diseño y control de sistemas de producción por lotes estocásticos de múltiples artículos". Investigación de operaciones . 34 (1): 91–104. doi :10.1287/opre.34.1.91. JSTOR 170674.
^ Leibowitz, MA (1968). "Colas". Scientific American . 219 (2): 96–103. doi :10.1038/scientificamerican0868-96.
^ Takagi, H. (2000). "Análisis y aplicación de modelos de sondeo". Evaluación del desempeño: orígenes y direcciones . LNCS . Vol. 1769. págs. 423–442. doi :10.1007/3-540-46506-5_18. hdl :2241/530. ISBN.978-3-540-67193-0.
^ Mack, C.; Murphy, T.; Webb, NL (1957). "La eficiencia de N máquinas patrulladas unidireccionalmente por un operario cuando el tiempo de marcha y los tiempos de reparación son constantes". Revista de la Royal Statistical Society. Serie B (Metodológica) . 19 (1): 166–172. doi :10.1111/j.2517-6161.1957.tb00253.x. JSTOR 2984003.
^ Resing, JAC (1993). "Sistemas de sondeo y procesos de ramificación multitipo". Sistemas de colas . 13 (4): 409–426. doi :10.1007/BF01149263.
^ Borst, SC (1995). "Sistemas de sondeo con múltiples servidores acoplados" (PDF) . Queueing Systems . 20 (3–4): 369–393. doi :10.1007/BF01245325.
^ Czerniak, O.; Yechiali, U. (2009). "Sistemas de sondeo fluido" (PDF) . Queueing Systems . 63 (1–4): 401–435. doi :10.1007/s11134-009-9129-6.
^ ab Everitt, D. (1986). "Aproximaciones simples para Token Rings". IEEE Transactions on Communications . 34 (7): 719–721. doi :10.1109/TCOM.1986.1096599.
^ Takagi, H. (1988). "Análisis de colas de modelos de sondeo". ACM Computing Surveys . 20 : 5–28. doi :10.1145/62058.62059.
^ Gautam, Natarajan (2012). Análisis de colas: métodos y aplicaciones . CRC Press. ISBN9781439806586.
^ Eisenberg, M. (1972). "Colas con servicio periódico y tiempo de cambio". Investigación de operaciones . 20 (2): 440–451. doi :10.1287/opre.20.2.440. JSTOR 169005.
^ Sarkar, D.; Zangwill, WI (1989). "Tiempo de espera esperado para sistemas de colas cíclicas no simétricas: resultados exactos y aplicaciones". Management Science . 35 (12): 1463. doi :10.1287/mnsc.35.12.1463. JSTOR 2632232.
^ Coffman, EG ; Puhalskii, AA; Reiman, MI (1995). "Sistemas de sondeo con tiempos de conmutación cero: un principio de promediado de tráfico pesado". Anales de probabilidad aplicada . 5 (3): 681. doi : 10.1214/aoap/1177004701 . JSTOR 2245120.