2.2 QS multicanal con espera
Sistema con longitud de cola limitada. Consideremos un canal QS con espera, que recibe un flujo de solicitudes con intensidad; intensidad del servicio (para un canal); número de lugares en la cola.
Los estados del sistema están numerados según la cantidad de solicitudes asociadas con el sistema:
sin cola:
Todos los canales son gratuitos;
Un canal está ocupado, el resto están libres;
-los canales están ocupados, el resto no;
Todos los canales están ocupados, no hay canales libres;
hay una cola:
Todos los n canales están ocupados; una aplicación está en la cola;
Todos los n canales y r solicitudes en la cola están ocupados;
Todos los n canales y r solicitudes en la cola están ocupados.
GSP se muestra en la Fig. 17. Cada flecha está marcada con las intensidades correspondientes de los flujos de eventos. Según las flechas de izquierda a derecha, el sistema siempre se transfiere por el mismo flujo de solicitudes con una intensidad de
Arroz. 17. QS multicanal con espera
El gráfico es típico de los procesos de reproducción y muerte, para los cuales previamente se obtuvo la solución. Escribamos expresiones para las probabilidades límite de estados usando la notación: (aquí usamos la expresión para la suma progresión geométrica con denominador).
Por tanto, se han encontrado todas las probabilidades estatales.
Determinemos las características de la eficiencia del sistema.
Probabilidad de fracaso. Una solicitud entrante se rechaza si todos los n canales y todos los m lugares de la cola están ocupados:
(18)
El rendimiento relativo complementa la probabilidad de falla a uno:
Rendimiento absoluto de QS:
(19)
Número medio de canales ocupados. Para QS con rechazos coincidió con el número promedio de solicitudes en el sistema. Para un QS con cola, el número medio de canales ocupados no coincide con el número medio de aplicaciones en el sistema: este último valor se diferencia del primero por el número medio de aplicaciones en la cola.
Denotaremos el número medio de canales ocupados por . Cada canal ocupado atiende un promedio de reclamos A por unidad de tiempo, y el QS en su conjunto atiende un promedio de reclamos A por unidad de tiempo. Dividiendo uno por otro obtenemos:
El número promedio de solicitudes en la cola se puede calcular directamente como la expectativa matemática de un proceso discreto. variable aleatoria:
(20)
Aquí nuevamente (la expresión entre paréntesis) ocurre la derivada de la suma de la progresión geométrica (ver arriba (11), (12) - (14)), usando la relación para ello, obtenemos:
Número promedio de aplicaciones en el sistema:
Tiempo medio de espera de una solicitud en la cola. Consideremos una serie de situaciones que difieren en el estado en el que una solicitud recién llegada encontrará el sistema y cuánto tiempo tendrá que esperar para recibir servicio.
Si una solicitud no encuentra todos los canales ocupados, no tendrá que esperar en absoluto (los miembros correspondientes en expectativa matemática son iguales a cero). Si una solicitud llega en un momento en el que todos los n canales están ocupados y no hay cola, tendrá que esperar en promedio un tiempo igual a (porque el "flujo de liberación" de los canales tiene una intensidad de ). Si una solicitud encuentra todos los canales ocupados y una solicitud delante de ella en la cola, tendrá que esperar en promedio una cantidad de tiempo (para cada solicitud delante), etc. Si una solicitud se encuentra en una cola de - solicitudes, tendrá que esperar en promedio el tiempo Si una solicitud recién llegada encuentra solicitudes m que ya están en la cola, no esperará en absoluto (pero no será atendida). El tiempo medio de espera lo encontramos multiplicando cada uno de estos valores por las probabilidades correspondientes:
(21)
Al igual que en el caso de un QS de un solo canal con espera, observamos que esta expresión difiere de la expresión para la longitud promedio de la cola (20) sólo en el factor , es decir
.
El tiempo medio de permanencia de una solicitud en el sistema, así como para un QS de un solo canal, difiere del tiempo medio de espera por el tiempo medio de servicio multiplicado por el rendimiento relativo:
.
Sistemas con longitud de cola ilimitada. Consideramos un canal QS con espera, cuando no pueden haber más de m solicitudes en la cola al mismo tiempo.
Como antes, al analizar sistemas sin restricciones, es necesario considerar las relaciones obtenidas para .
Obtenemos las probabilidades de estados a partir de las fórmulas pasando al límite (en ). Tenga en cuenta que la suma de la progresión geométrica correspondiente converge y diverge en >1. Asumiendo que<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Probabilidad de fallo, rendimiento relativo y absoluto. Dado que tarde o temprano cada solicitud será atendida, las características del rendimiento de QS serán:
El número medio de solicitudes en cola se obtiene de (20):
,
y el tiempo medio de espera es de (21):
.
El número medio de canales ocupados, como antes, se determina mediante el rendimiento absoluto:
.
El número promedio de aplicaciones asociadas al QS se define como el número promedio de aplicaciones en la cola más el número promedio de aplicaciones en servicio (número promedio de canales ocupados):
Ejemplo 2. Una gasolinera con dos surtidores (n = 2) atiende un flujo de coches con una intensidad de =0,8 (coches por minuto). Tiempo medio de servicio por máquina:
No hay otra gasolinera en la zona, por lo que la cola de coches delante de la gasolinera puede crecer casi ilimitadamente. Encuentra las características del QS.
Porque el<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
etc.
El número medio de canales ocupados lo encontraremos dividiendo la capacidad absoluta del QS A = = 0,8 por la intensidad del servicio = 0,5:
La probabilidad de que no haya cola en una gasolinera será:
Número medio de coches en cola:
Número medio de coches en gasolineras:
Tiempo medio de espera en cola:
Tiempo medio que pasa un coche en una gasolinera:
QS con tiempo de espera limitado. Anteriormente, consideramos sistemas con espera limitada solo por la longitud de la cola (el número de m solicitudes simultáneamente en la cola). En tal QS, una aplicación que ha crecido en una cola no la abandona hasta que espera servicio. En la práctica, existen otros tipos de QS en los que una solicitud, después de esperar un tiempo, puede abandonar la cola (las llamadas solicitudes “impacientes”).
Consideremos un QS de este tipo, suponiendo que la restricción del tiempo de espera es una variable aleatoria.
Supongamos que hay un QS de espera de n canales en el que el número de lugares en la cola es ilimitado, pero el tiempo que una solicitud permanece en la cola es una variable aleatoria con un valor medio, por lo tanto, cada solicitud en la cola es sujeto a una especie de “flujo de cuidados” de Poisson con intensidad:
Si este flujo es Poisson, entonces el proceso que ocurre en el QS será Markoviano. Encontremos las probabilidades estatales para ello. La numeración de los estados del sistema está asociada con la cantidad de aplicaciones en el sistema, tanto en servicio como en cola:
sin cola:
Todos los canales son gratuitos;
Un canal está ocupado;
Dos canales están ocupados;
Todos los n canales están ocupados;
hay una cola:
Todos los n canales están ocupados, hay una solicitud en la cola;
Todos los n canales están ocupados, las r solicitudes están en cola, etc.
La gráfica de estados y transiciones del sistema se muestra en la Fig. 23.
Arroz. 23. QS con tiempo de espera limitado
Marquemos este gráfico como antes; Todas las flechas que van de izquierda a derecha indicarán la intensidad del flujo de aplicaciones. Para los estados sin cola, las flechas que salen de ellos de derecha a izquierda indicarán, como antes, la intensidad total del flujo que da servicio a todos los canales ocupados. En cuanto a los estados con cola, las flechas que salen de ellos de derecha a izquierda tendrán la intensidad total del flujo de servicio de todos los n canales más la intensidad correspondiente del flujo de salidas de la cola. Si hay r-aplicaciones en la cola, entonces la intensidad total del flujo de salidas será igual a .
Como se puede observar en el gráfico, existe un patrón de reproducción y muerte; usando expresiones generales para las probabilidades límite de estados en este esquema (usando notaciones abreviadas, escribimos:
(24)
Observemos algunas características de un QS con espera limitada en comparación con el QS considerado anteriormente con solicitudes de "pacientes".
Si la longitud de la cola no está limitada y las solicitudes son "pacientes" (no salen de la cola), entonces el régimen límite estacionario existe sólo en el caso (en la correspondiente progresión geométrica infinita diverge, que físicamente corresponde al crecimiento ilimitado de la cola en ).
Por el contrario, en un QS con solicitudes “impacientes” que abandonan la cola tarde o temprano, siempre se alcanza el modo de servicio establecido, independientemente de la reducida intensidad del flujo de solicitudes. Esto se desprende del hecho de que la serie for en el denominador de la fórmula (24) converge para cualquier valor positivo de y .
Para un QS con solicitudes "impaciente", el concepto de "probabilidad de falla" no tiene sentido: cada solicitud se pone en fila, pero no puede esperar el servicio y sale con anticipación.
Rendimiento relativo, el número promedio de solicitudes en la cola. La capacidad relativa q de dicho QS se puede calcular de la siguiente manera. Obviamente, todas las solicitudes serán atendidas, excepto aquellas que salgan de la cola antes de lo previsto. Calculemos el número promedio de solicitudes que abandonan la cola antes de tiempo. Para ello, calculamos el número medio de solicitudes en la cola:
Cada una de estas aplicaciones está sujeta a un “flujo de salidas” con una intensidad de . Esto significa que del número promedio de -solicitudes en la cola, en promedio, -las solicitudes saldrán sin esperar servicio, -las solicitudes por unidad de tiempo y en total por unidad de tiempo, en promedio, las -solicitudes serán atendidas. La capacidad relativa del QS será:
Aún obtenemos el número promedio de canales ocupados dividiendo el ancho de banda absoluto A por:
(26)
Número medio de solicitudes en cola. La relación (26) le permite calcular el número promedio de aplicaciones en la cola sin sumar la serie infinita (25). De (26) obtenemos:
y el número promedio de canales ocupados incluidos en esta fórmula se puede encontrar como la expectativa matemática de una variable aleatoria Z, tomando valores 0, 1, 2,..., n con probabilidades,:
En conclusión, observamos que si en las fórmulas (24) vamos al límite en (o, lo que es lo mismo, en ), entonces en 
Una cola de longitud k permanece en ella con probabilidad Pk y no se une a la cola con probabilidad gk=1 - Pk." Así es exactamente como la gente suele comportarse en las colas. En los sistemas de colas, que son modelos matemáticos de procesos de producción, las posibles La longitud de la cola está limitada por un tamaño constante (capacidad del búnker, por ejemplo). Obviamente, este es un caso especial de la configuración general.
En esta sección veremos algunos de los QS más simples y derivaremos expresiones para sus características (indicadores de desempeño). Al mismo tiempo, demostraremos las principales técnicas metodológicas características de la teoría elemental de las colas "Markov". No perseguiremos el número de muestras QS de las cuales se derivarán las expresiones finales de las características; Este libro no es un libro de referencia sobre la teoría de las colas (esta función se cumple mucho mejor con manuales especiales). Nuestro objetivo es presentar al lector algunos “pequeños trucos” que faciliten el camino a través de la teoría de las colas, que en varios libros existentes (incluso pretendiendo ser populares) puede parecer un conjunto de ejemplos incoherentes.
En esta sección, consideraremos todos los flujos de eventos que transfieren el QS de un estado a otro como los más simples (sin estipularlo específicamente cada vez). Entre ellos estará el llamado “flujo de servicios”. Se refiere al flujo de solicitudes atendidas por un canal continuamente ocupado.
En este flujo, el intervalo entre eventos, como siempre en el flujo más simple, tiene una distribución exponencial (en muchos manuales dicen en cambio: “el tiempo de servicio es exponencial”; nosotros mismos usaremos este término en el futuro). En este apartado sobra decir la distribución exponencial del tiempo de servicio, como siempre para el sistema “más simple”.
Introduciremos las características de rendimiento del QS bajo consideración a medida que avancemos.
1. QS de canal n con fallas (problema de Erlang).
Aquí consideraremos uno de los primeros problemas “clásicos” de la teoría de colas; Este problema surgió de las necesidades prácticas de la telefonía y fue resuelto a principios de este siglo por el matemático danés Erlang. El problema se formula de la siguiente manera: existen canales (líneas de comunicación) que reciben un flujo de solicitudes con intensidad K. El flujo de servicios tiene una intensidad (el valor inverso del tiempo promedio de atención). Encuentre las probabilidades finales de los estados QS, así como las características de su efectividad:
A - rendimiento absoluto, es decir, el número medio de solicitudes atendidas por unidad de tiempo;
Rendimiento relativo, es decir, la proporción promedio de aplicaciones entrantes atendidas por el sistema;
Rotk es la probabilidad de rechazo, es decir, que la solicitud dejará el QS sin atender;
k es el número medio de canales ocupados.
Solución. Numeraremos los estados del sistema S (SMO) según el número de solicitudes ubicadas en el sistema (en este caso coincide con el número de canales ocupados):
No existe ni una sola solicitud en la OCM,
Hay una solicitud en el QS (un canal está ocupado, el resto está libre),
En el sistema QS las solicitudes de canales están ocupadas, el resto están libres),
Hay solicitudes en el QS (todos los canales están ocupados).
El gráfico de estado del QS corresponde al patrón de muerte y reproducción (Fig. 20.1). Marquemos este gráfico: coloque la intensidad de los flujos de eventos al lado de las flechas. El flujo de aplicaciones con intensidad X se transfiere desde el sistema (tan pronto como llega una aplicación, el sistema salta).
El mismo flujo de solicitudes transfiere el sistema desde cualquier estado izquierdo al vecino derecho (ver las flechas superiores en la Fig. 20.1).
Pongamos las intensidades en las flechas inferiores. Deje que el sistema esté en el estado (un canal está funcionando). Realiza mantenimiento por unidad de tiempo. Indicamos la intensidad de la flecha. Ahora imaginemos que el sistema está en el estado (dos canales están funcionando). Para que funcione, el primer canal o el segundo deben finalizar el servicio; la intensidad total de sus flujos de servicios es igual a la flecha correspondiente. El flujo total de servicios proporcionados por tres canales tiene una intensidad igual a los canales; colocamos estas intensidades en las flechas inferiores de la Fig. 20.1.
Y ahora, conociendo todas las intensidades, usaremos las fórmulas ya preparadas (19.7), (19.8) para las probabilidades finales en el esquema de muerte y reproducción. Usando la fórmula (19.8) obtenemos:
Los términos de la expansión serán los coeficientes en las expresiones para
Tenga en cuenta que en las fórmulas (20.1), (20.2) las intensidades de los huevos no se incluyen individualmente, sino solo en forma de proporción.
y llamaremos al valor “intensidad reducida del flujo de aplicaciones”. Su significado es el número promedio de solicitudes recibidas durante el tiempo promedio de atención de una solicitud. Usando esta notación, reescribimos las fórmulas (20.1), (20.2) en la forma:
Las fórmulas (20.4), (20.5) para las probabilidades finales de estados se denominan fórmulas de Erlang, en honor al fundador de la teoría de colas. La mayoría de las otras fórmulas de esta teoría (hoy en día hay más que hongos en el bosque) no llevan ningún nombre especial.
Así, se han encontrado las probabilidades finales. Utilizándolos, calcularemos las características de rendimiento del QS. Primero, encontremos la probabilidad de que una solicitud entrante sea rechazada (no sea atendida). Para hacer esto, todos los canales deben estar ocupados, lo que significa
A partir de aquí encontramos el rendimiento relativo: la probabilidad de que se atienda la solicitud:
Obtenemos el rendimiento absoluto multiplicando la intensidad del flujo de aplicaciones X por
Sólo queda encontrar el número promedio de canales ocupados k. Este valor se podría encontrar “directamente”, como la expectativa matemática de una variable aleatoria discreta con posibles valores y probabilidades de estos valores.
Sustituyendo aquí las expresiones (20.5) y realizando las transformaciones correspondientes, eventualmente obtendríamos la fórmula correcta para k. Pero la derivaremos de manera mucho más simple (¡aquí está, uno de los “pequeños trucos”!) De hecho, lo sabemos. el rendimiento absoluto A. Esto no es más que la intensidad del flujo de aplicaciones atendidas por el sistema. Cada canal ocupado atiende un promedio de solicitudes por unidad de tiempo. Esto significa que el número medio de canales ocupados es
¿Y qué proporción de canales estarán inactivos?
Aquí ya se ve algún indicio de optimización. De hecho, el mantenimiento de cada canal por unidad de tiempo cuesta una determinada cantidad. Al mismo tiempo, cada aplicación reparada genera algunos ingresos. Multiplicando este ingreso por el número promedio de solicitudes A atendidas por unidad de tiempo, obtenemos el ingreso promedio del QS por unidad de tiempo. Naturalmente, a medida que aumenta el número de canales, estos ingresos aumentan, pero también aumentan los costos asociados con el mantenimiento de los canales. ¿Qué compensará: un aumento de ingresos o gastos? Depende de los términos de la operación, la "tarifa por el servicio de la aplicación" y el costo de mantenimiento del canal. Conociendo estos valores, podrá encontrar el número óptimo de canales, el más rentable. No resolveremos tal problema, dejando que el mismo "lector curioso y no perezoso" presente un ejemplo y lo resuelva. Por lo general, inventar problemas desarrolla más que resolver los ya planteados por alguien.
Los sistemas ML son parte de una clase más amplia de sistemas dinámicos que a veces se denominan sistemas de flujo. Sistema de hilo Es un sistema en el que determinados objetos se mueven a través de uno o más canales de capacidad limitada con el fin de desplazarse de un punto a otro. Al analizar los sistemas de flujo, se dividen en dos clases principales:
sistemas regulares, es decir sistemas en los que los flujos se comportan de manera predecible (se conoce la magnitud del flujo y el momento de su aparición en el canal). En el caso de que exista un solo canal, el cálculo del sistema es trivial. Es obvio que entre la intensidad del flujo λ y rapidez del servicio Con hay una proporción λ < C;
Sistemas irregulares, es decir, sistemas en los que los hilos se comportan de forma impredecible.
Más interesante es el caso de un flujo regular que se distribuye a través de una red de canales. Es obvio que la condición λ < C guardado para cada canal. Esto crea un problema combinatorio complejo.
Hay siete caminos:
A→B→D→E→F
A→C→B→ E→F
A→C→B→D→E→F
A→C→B→ D→F
Es necesario transportar carga desde A V F. Se conoce la capacidad de cada canal. ¿Cuál es la capacidad de la red y qué camino debe tomar el flujo? Este problema se puede resolver utilizando el teorema del flujo máximo, que consideramos anteriormente (Fig. 6).
La segunda clase incluye flujos probables aleatorios, en los que el momento de recepción de un requisito no está determinado y el número de requisitos es impredecible. La teoría de las colas se ocupa de resolver este tipo de problemas.
En general, el sistema de colas se puede representar en la Figura 7.
Arroz. 7.
El tema de la teoría de colas. es establecer la relación entre la naturaleza del flujo de solicitudes, el número de canales, la productividad, el correcto funcionamiento y la eficiencia.
Como características de presentación Se pueden utilizar las siguientes cantidades y funciones:
el número medio de aplicaciones que el QS puede atender por unidad de tiempo;
el número medio de solicitudes rechazadas y abandonadas por la OCM;
la probabilidad de que la solicitud recibida sea atendida de inmediato;
tiempo medio de espera en la cola;
número medio de solicitudes en cola;
ingreso promedio de SMO por unidad de tiempo y otros indicadores económicos de SMO.
El análisis de QS se simplifica si ocurre un proceso de Markov en el sistema, entonces el sistema puede describirse mediante ecuaciones diferenciales ordinarias y las probabilidades límite, mediante ecuaciones algebraicas lineales.
Un proceso de Markov requiere que todos los flujos sean Poisson (sin efectos secundarios), pero el aparato de los procesos de Markov también se utiliza cuando el proceso es diferente de Markov. En este caso, las características del QS se pueden estimar de forma aproximada: cuanto más complejo sea el QS, más precisa será la aproximación.
Clasificación de sistemas de colas.
QS puede ser de dos tipos:
QS con fallas;
QS con espera (es decir, con cola).
El servicio en sistemas con cola puede ser de diferente naturaleza:
el servicio se puede optimizar;
servicio aleatorio;
servicio con prioridad, pudiendo ser la prioridad con o sin interrupción.
Los sistemas de colas se dividen en:
sistemas con espera ilimitada, en este caso, la tarea recibida por el QS pasa a la cola y espera servicio. Tarde o temprano será atendida;
sistemas con expectativas limitadas, mientras que se imponen restricciones a la aplicación en la cola, por ejemplo, un tiempo limitado de permanencia en la cola, la longitud de la cola, el tiempo total de permanencia en el QS. Dependiendo del tipo de QS, se pueden utilizar diferentes indicadores para evaluar la eficacia.
Para QS con fallas, se utilizan los siguientes indicadores de desempeño:
rendimiento absoluto A– el número medio de aplicaciones que pueden ser atendidas por unidad de tiempo;
rendimiento relativo q– número medio relativo de solicitudes. En este caso, el rendimiento relativo se puede encontrar usando la fórmula
Donde λ es la intensidad de solicitudes recibidas por el QS.
Para SMO con expectativa rendimiento absoluto A Y rendimiento relativo q pierden su significado, pero otras características cobran importancia:
unidad de tiempo de espera en cola;
número medio de solicitudes en cola;
Tiempo promedio de permanencia en el sistema.
Para un QS con cola limitada, ambos grupos de características son interesantes.
Considere norte - Sistema de cola de canales con espera.
La intensidad del flujo de servicio es μ. La duración del servicio es una variable aleatoria sujeta a la ley de distribución exponencial. El flujo de servicios es el flujo de eventos de Poisson más simple.
El tamaño de la cola permite que haya gente en ella. m aplicaciones.
Para encontrar las probabilidades marginales, puede utilizar las siguientes expresiones.
(0‑1)
Dónde.
Probabilidad de negarse a atender una solicitud(Se producirá una falla si todos los canales están ocupados y hay m solicitudes):
(0‑2)
Ancho de banda relativo.
(0‑3)
Rendimiento absoluto.
(0‑4)
Número medio de canales ocupados.
Para un QS con cola, el número promedio de canales ocupados no coincide (a diferencia del QS con fallas) con el número promedio de solicitudes en el sistema. La diferencia es igual al número de solicitudes esperando en la cola.
Denotaremos el número medio de canales ocupados. Cada canal ocupado atiende en promedio μ reclamaciones por unidad de tiempo, y el QS en su conjunto atiende A reclamaciones por unidad de tiempo. Dividiendo A por μ obtenemos
(0‑5)
El número promedio de solicitudes en la cola.
Para encontrar el número promedio de solicitudes esperando en la cola si χ≠1, puedes usar la expresión:
(0‑6)
(0‑7)
donde = .
El número promedio de aplicaciones en el sistema.
(0‑8)
Tiempo medio de espera para una solicitud en cola.
El tiempo de espera promedio para una aplicación en la cola se puede encontrar a partir de la expresión (χ≠1).
(0‑9)
Tiempo promedio que una aplicación permanece en el sistema.
Al igual que en el caso de un QS monocanal, tenemos:
(0‑10)
El contenido de la obra..
Preparación de instrumentos experimentales. .
Realizado de acuerdo con las reglas generales.
Cálculo utilizando un modelo analítico. .
1. Prepare la siguiente tabla en Microsoft Excel.
|
Opciones |
Analítico |
Imitación |
|||||||||||||||
|
norte |
metro |
ta |
ts |
ρ |
χ |
P0 |
P1 |
p2 |
rotk |
W. |
nozh |
q |
A |
rotk |
W. |
q |
A |
2. En las columnas de los parámetros QS de la tabla, escriba sus datos iniciales, que se determinan según la regla:
norte =1,2,3
metro=1,3,5
Para cada combinación ( Nuevo Méjico) es necesario encontrar valores teóricos y experimentales de indicadores QS para los siguientes pares de valores:
= <порядковый номер в списке группы>
3. Ingrese las fórmulas apropiadas en las columnas con los indicadores del modelo analítico.
Experimentar con un modelo de simulación..
1. Configure el modo de inicio con tiempo de servicio distribuido exponencialmente estableciendo el valor del parámetro correspondiente en 1.
2. Para cada combinación de n, my ejecute el modelo.
Ingrese los resultados de las ejecuciones en la tabla.
3. Ingrese fórmulas para calcular el valor promedio del indicador Ptk, q y A en las columnas correspondientes de la tabla.
Análisis de resultados .
1. Analizar los resultados obtenidos por métodos teóricos y experimentales, comparando los resultados entre sí.
2. Para una de las combinaciones (n,m), trace en un diagrama la dependencia de Ptk de los datos obtenidos teórica y experimentalmente.
Optimización de los parámetros QS. .
Resuelva el problema de optimizar el tamaño del número de lugares en una cola metro para dos dispositivos con tiempo de servicio medio = desde el punto de vista de obtener el máximo beneficio. Como condiciones del problema, tome:
- ingresos por el servicio de una aplicación equivalente a 80 USD/hora,
- el costo de mantenimiento de un dispositivo es 1$/hora,
- el costo de mantener un lugar en la cola es de 0,2 USD/hora.
1. Para los cálculos, es recomendable crear una tabla:
La primera columna se completa con la cantidad de dispositivos. norte =1.
La segunda columna se rellena con los valores de los números de la serie natural (1,2,3...).
Todas las celdas de la tercera y cuarta columnas están llenas de valores.
Las fórmulas para las columnas de la tabla de la sección 0 se transfieren a las celdas de las columnas del cinco al catorce.
En las columnas con los datos iniciales de las secciones Ingresos, Gastos, Ganancias, ingrese los valores (ver arriba).
En las columnas con valores calculados de las secciones Ingresos, Gastos, Ganancias, escriba las fórmulas de cálculo:
- número de aplicaciones por unidad de tiempo
N r = A
- ingreso total por unidad de tiempo
Yo S = Yo r *N r
- consumo total por unidad de tiempo
E S =E s *n + E q *m
- beneficio por unidad de tiempo
P = I S - E S
Dónde
ir - ingresos de una aplicación,
es - consumo por dispositivo,
ecuación - costo por lugar en la fila
2. Complete las filas de la tabla para n=2 y n=3.
Encuentre m opte por n =1,2,3.
3. Dibuje gráficas de la dependencia C(m) para n=1,2,3 en un diagrama.
Reporte de trabajo:
El informe de trabajo debe incluir:
- datos iniciales,
- resultados de cálculos y experimentos con el modelo de software,
Gráficos para P abiertos,
- tabla con datos para encontrar el mejor m y el valor de m opt,
- gráficos de beneficio por unidad de tiempo dependiendo de m para n=1,2,3.
Preguntas de control :
1) Dé una breve descripción del modelo QS multicanal con una cola limitada.
2) ¿Qué indicadores caracterizan el funcionamiento de un QS multicanal con cola limitada?
3) ¿Cómo se calculan las probabilidades marginales de un QS multicanal con una cola limitada?
4) ¿Cómo encontrar la probabilidad de que no se pueda dar servicio a una aplicación?
5) ¿Cómo encontrar el ancho de banda relativo?
6) ¿Cuál es el rendimiento absoluto?
7) ¿Cómo se calcula el número promedio de aplicaciones en el sistema?
8) Dé ejemplos de un QS multicanal con una cola limitada.
Tareas.
1) La gasolinera dispone de 3 surtidores y una plataforma para que 3 coches esperen a repostar. En promedio, llega a la estación un automóvil cada 4 minutos. El tiempo medio de servicio de una máquina es de 2,8 minutos. Determinar las características operativas de una gasolinera.
2) La estación de inspección técnica de vehículos, que cuenta con 3 puestos de inspección, recibe en promedio 1 vehículo cada 0,4 horas. El aparcamiento en el patio tiene capacidad para 3 coches. El tiempo medio de funcionamiento de un puesto es de 0,5 horas. Determinar las características de la estación de servicio.
3) La mercancía se entrega a la tienda mediante vehículos. Durante el día llegan una media de 6 coches. Los cuartos de servicio para preparar mercancías para la venta permiten procesar y almacenar mercancías transportadas en dos vehículos. En la tienda trabajan tres empacadores de productos por turnos, cada uno de los cuales puede procesar la mercancía de una máquina en promedio en 5 horas. La jornada laboral de los empacadores es de 12 horas. Determine las características operativas de la tienda, así como cuál debe ser la capacidad de los cuartos de servicio para que la probabilidad de procesamiento completo de la mercancía sea superior a 0,96.
4) La tienda tiene tres cajas registradoras. El tiempo medio de atención para un cliente es de 3 minutos. La intensidad del flujo de clientes es de 7 personas por minuto. El número de clientes que hacen cola en la caja no puede exceder de 5 personas. Un comprador que llega a una tienda en la que hay 5 personas en cada fila en la caja registradora no espera, sino que sale de la tienda. Determinar las características de la tienda.
5) El almacén mayorista entrega mercancías a los clientes. La carga del vehículo la realizan tres equipos de cargadores, cada uno de los cuales está formado por 4 personas. El almacén tiene capacidad para 5 vehículos simultáneamente y si llega un vehículo nuevo en este momento no se le da servicio. La intensidad del flujo entrante es de 5 coches por hora. La velocidad de carga es de 2 vehículos por hora. Dar una valoración del funcionamiento del almacén y una opción para su reorganización.
6) La aduana tiene tres terminales. La intensidad del flujo de vehículos que transportan mercancías y están sujetos a control aduanero es de 30 unidades. por día. El tiempo promedio de trámite aduanero en la terminal para un vehículo es de 3 horas. Si hay 5 autos en fila para pasar por el control aduanero, los autos que llegan van a otra oficina de aduanas. Encuentre indicadores de desempeño aduanero.
7) Los vehículos con materiales de construcción llegan de media a la obra en 40 minutos. El tiempo medio de descarga de un vehículo es de 1,8 horas. En la descarga participan dos equipos de cargadores. No podrán estar en fila más de 5 vehículos para la descarga en la obra. Determinar los indicadores de desempeño del sitio de construcción.
8) En promedio, llegan 12 autos por hora a un lavadero con tres estaciones de trabajo. Si ya hay 6 coches en la cola, los coches recién llegados no se unen a la cola, sino que abandonan el lavado. El tiempo promedio de lavado de autos es de 20 minutos, el costo promedio de los servicios de lavado de autos es de 150 rublos. Determinar los indicadores de desempeño del lavado de autos y la pérdida promedio de ingresos durante la jornada laboral (de 9 a 19 horas).
9) La intensidad del flujo de vehículos que transportan mercancías y están sujetos a control aduanero es de 50 unidades. por día. El tiempo medio de tramitación aduanera en la terminal para un vehículo es de 2,8 horas. La cola máxima para el control aduanero no debe ser superior a 8 coches. Determine cuántas terminales deben abrirse en la aduana para que la probabilidad de que el vehículo esté inactivo sea mínima.
Sistema con longitud de cola limitada. Consideremos un canal QS con espera, que recibe un flujo de solicitudes con intensidad; intensidad del servicio (para un canal); número de lugares en la cola.
Los estados del sistema están numerados según la cantidad de solicitudes asociadas con el sistema:
sin cola:
Todos los canales son gratuitos;
Un canal está ocupado, el resto están libres;
Los canales están ocupados, el resto no;
Todos los canales están ocupados, no hay canales libres;
hay una cola:
Los n canales están ocupados; una aplicación está en la cola;
Los n canales están ocupados, r aplicaciones están en cola;
Los n canales están ocupados, metro solicitudes en cola.
GSP se muestra en la Fig. 5.9. Cada flecha está marcada con las intensidades correspondientes de los flujos de eventos. Según las flechas de izquierda a derecha, el sistema siempre se transfiere por el mismo flujo de solicitudes con una intensidad de
Exponencial multicanal SMO Se diferencia del monocanal en lo siguiente. Hay más de un canal en él. Una solicitud entrante pasa a cola si todos los canales están ocupados. En caso contrario, la solicitud ocupa un canal libre. 
(5.56)
Escribamos expresiones para las probabilidades límite de estados usando la notación: (ver 5.45)
Probabilidad de fracaso. Una solicitud recibida se rechaza si todos están ocupados. norte canales y todo metro lugares en fila:
(5.57)
El rendimiento relativo complementa la probabilidad de falla a uno:
Rendimiento absoluto de QS:
(5.58)
Número medio de canales ocupados. Para SMO con las denegaciones, coincidió con el número medio de solicitudes en el sistema. Para SMO con una cola, el número medio de canales ocupados no coincide con el número medio de aplicaciones en el sistema: este último valor se diferencia del primero en el número medio de aplicaciones en la cola.
Denotaremos el número medio de canales ocupados por . Cada canal ocupado atiende en promedio solicitudes por unidad de tiempo, y SMO el servicio general es promedio A Aplicaciones por unidad de tiempo. Dividiendo uno por otro obtenemos:
El número promedio de solicitudes en una cola se puede calcular directamente como la expectativa matemática de una variable aleatoria discreta:
(5.59)
Aquí nuevamente (la expresión entre paréntesis) se produce la derivada de la suma de la progresión geométrica (ver arriba (5.50), (5.51)-(5.53)), usando la relación para ello, obtenemos:
Número promedio de aplicaciones en el sistema:
Tiempo medio de espera para una solicitud en cola. Consideremos una serie de situaciones que difieren en el estado en el que una solicitud recién llegada encontrará el sistema y cuánto tiempo tendrá que esperar para recibir servicio.
Si una solicitud no encuentra todos los canales ocupados, no tendrá que esperar en absoluto (los términos correspondientes en la expectativa matemática son iguales a cero). Si la aplicación llega en un momento en el que todos están ocupados PAG canales, pero no hay cola, tendrá que esperar en promedio un tiempo igual a (porque el “flujo de lanzamientos” de canales tiene una intensidad de ). Si una aplicación encuentra todos los canales ocupados y una aplicación delante de ella en la cola, tendrá que esperar en promedio una cantidad de tiempo (para cada aplicación delante), etc. Si una aplicación se encuentra en una cola de aplicaciones , tendrá que esperar en promedio un período de tiempo . Si una aplicación recién llegada se encuentra en la cola metro solicitudes, entonces no esperará en absoluto (pero no será atendido).
tiempo promedio de espera encontramos multiplicando cada uno de estos valores por las probabilidades correspondientes:
(5.60)
Al igual que en el caso de un QS de un solo canal con espera, observamos que esta expresión difiere de la expresión para la longitud promedio de la cola (5,59) solo en el factor , es decir
Tiempo promedio que una aplicación permanece en el sistema, lo mismo que para un solo canal SMO, difiere del tiempo de espera promedio por el tiempo de servicio promedio multiplicado por el rendimiento relativo:
Sistemas con longitud de cola ilimitada.
Se consideró un canal QS con espera, cuando no más de metro aplicaciones.
Como antes, al analizar sistemas sin restricciones, es necesario considerar las relaciones obtenidas para .
Obtenemos las probabilidades de estados a partir de las fórmulas (5.56) pasando al límite (en ). Tenga en cuenta que la suma de la progresión geométrica correspondiente converge y diverge en > 1. Suponiendo que< 1 и устремив в формулах (5.56) величину metro hasta el infinito, obtenemos expresiones para las probabilidades límite de estados:
(5.61)
Probabilidad de fallo, rendimiento relativo y absoluto. Dado que tarde o temprano cada solicitud será atendida, las características del rendimiento de QS serán:
Obtenemos el número medio de solicitudes en cola a partir de (5,59):
y el tiempo medio de espera es de (5.60):
El número medio de canales ocupados, como antes, se determina mediante el rendimiento absoluto:
El número promedio de aplicaciones asociadas al QS se define como el número promedio de aplicaciones en la cola más el número promedio de aplicaciones en servicio (número promedio de canales ocupados):
La creciente complejidad de las estructuras y modos de los sistemas reales complica el uso de métodos clásicos de la teoría de colas debido a la creciente dimensión de los problemas a resolver, lo que es especialmente típico de los sistemas con estructura de red. Una de las posibles formas de superar la dimensionalidad es utilizar modelos en forma de redes de colas (Queuing).
SEMO es una colección de un número finito de nodos de servicio en los que circulan solicitudes, moviéndose de acuerdo con la matriz de enrutamiento de un nodo a otro. El nodo siempre está abierto. SMO. Al mismo tiempo, separe SMO SMO− la estructura del sistema y los requisitos que circulan a través de él. SEMO, − componentes de los flujos de materiales (mensajes (paquetes) en una red de comunicación, tareas en sistemas multiprocesadores, contenedores de flujos de carga, etc.).
A su momento, SEMO Se utiliza para determinar las características del sistema más importantes de los sistemas de información: productividad; tiempo de entrega del paquete; probabilidad de pérdida y bloqueo de mensajes en nodos; áreas de valores de carga permitidos en los que se garantiza la calidad de servicio requerida, etc.
En teoria SEMO El concepto de estado de la red es fundamental. La característica más importante de las redes. mes− probabilidades de sus estados. Para determinar las probabilidades de estados. SEMO Investigar el proceso aleatorio que ocurre en la red. Como modelos fluyendo SEMO Los procesos de Markov y semi-Markov también se utilizan con mayor frecuencia.
3.3. El sistema de colas como modelo.
1.5. Redes de cola
Un proceso de Markov con tiempo continuo describe el funcionamiento de exponenciales. SEMO.
La red se llama exponencial si los flujos entrantes de requisitos en cada SMO Poisson, y los tiempos de cada etapa del servicio implementado en cualquier SMO las redes tienen exponencial distribución. Esto nos permite suponer que las etapas del servicio son independientes entre sí y no dependen ni de los parámetros del flujo entrante, ni del estado de la red, ni de las rutas de las solicitudes.
Teoría de la exponencial SEMO más desarrollado, y es ampliamente utilizado tanto para el estudio de redes PD como para el estudio de multiprocesador. sistemas informáticos (CS). Se han desarrollado fórmulas prácticas para calcular las características temporales-probabilísticas (PTC) de dichas redes y sistemas.
Los intentos de analizar en profundidad modelos de sistemas de red que no son de Markov encuentran dificultades significativas, que se deben, en particular, a la falta de independencia de la duración de la estancia de los requisitos en varios nodos de modelos de sistemas de red con disciplinas no estándar. Así, por ejemplo, con una suposición bastante realista de que la longitud de la solicitud permanece constante durante su transmisión a través de los nodos de la red, es necesario rastrear la ruta de cada solicitud, lo que hace imposible calcular analíticamente las características de una red con el número de nodos M>2.
Un análisis de los trabajos dedicados al estudio o cálculo de modelos que no son de Markov muestra que las soluciones, por regla general, se obtienen algorítmicamente mediante cálculos numéricos complejos utilizando transformaciones de Laplace-Stieltjes, se implementan en software, requieren mucha mano de obra o tienen importantes errores en la evaluación de los indicadores de desempeño de los sistemas de información (SI) en el área de carga media y pesada. Por lo tanto, para modelar semo, saliendo de la clase de los multiplicativos, utilizan métodos aproximados.
Análisis comparativo de métodos de modelado aproximado. SEMO y los ejemplos dados muestran que es necesario utilizar métodos aproximados para calcular SeMO con gran precaución, que al calcular SeMO específico, en el proceso de resolver diversos problemas aplicados, parece necesario realizar investigaciones para evaluar la precisión y sensibilidad. del método utilizado, así como realizar un experimento de simulación del SeMO original para un conjunto suficientemente grande de valores de parámetros variados.
Los métodos analíticos para calcular las características IS se basan, por regla general, en el análisis de CeMO exponencial. Con este aparato matemático es posible obtener modelos analíticos para resolver una amplia gama de problemas en el estudio de sistemas. SeMO es, ante todo, un conjunto de sistemas de colas interconectados. Por tanto, es necesario recordar las principales características de estos sistemas.
Red de colas representa una colección de números finitos norte Nodos de servicio, en los que circulan las solicitudes, moviéndose de acuerdo con la matriz de enrutamiento de un nodo a otro. Un nodo es siempre un QS abierto (y el QS puede ser de cualquier clase). Al mismo tiempo, separe SMO mostrar partes funcionalmente independientes de un sistema real, conexiones entre SMO- la estructura del sistema y los requisitos que circulan a través de él. semo,- componentes de los flujos de materiales (mensajes (paquetes) en una red de comunicación, tareas en sistemas multiprocesador, contenedores de flujos de carga, etc.).
Para representación visual SEMO Se utiliza un gráfico cuyos vértices (nodos) corresponden a individuos. SMO y los arcos muestran conexiones entre nodos.
La transición de aplicaciones entre nodos se produce instantáneamente de acuerdo con las probabilidades de transición. 
, p ij- la probabilidad de que la solicitud después del servicio en el nodo i irá al nodo j. Naturalmente, si los nodos no están conectados directamente entre sí, entonces p ij= 0. Si de i- transición del nodo a un solo nodo j, Eso p ij= 1.
SEMO clasificados según varios criterios (Fig. 4).
La red se llama lineal, si las intensidades de los flujos de aplicación en los nodos están relacionadas entre sí mediante una relación lineal
yo j= un yo yo i,
donde un yo- coeficiente de proporcionalidad, o relativo a la fuente
yo j= un j yo 0 ,.
Coeficiente a j llamado coeficiente de transmisión, caracteriza la proporción de solicitudes recibidas en j-º nodo desde el origen de las aplicaciones, o - el número promedio de veces que una aplicación pasa por este nodo durante el tiempo que la aplicación está en la red.
Si las intensidades de los flujos de aplicación en los nodos de la red están relacionadas por una relación no lineal (por ejemplo, 
), entonces la red se llama no lineal..
Una red siempre es lineal si en ella no se pierden ni se multiplican aplicaciones.
Abierto Una red es una red abierta en la que las solicitudes provienen del entorno externo y salen de la red hacia el entorno externo después de ser atendidas. En otras palabras, la característica del circuito abierto SEMO(RSeMO) es la presencia de una o más fuentes externas independientes que generan aplicaciones que ingresan a la red, independientemente de cuántas aplicaciones ya estén en la red. En cualquier momento en RSeMO puede haber un número arbitrario de aplicaciones (de 0 a ¥).
Arroz. 4. Clasificación de redes de colas.
EN SeMO cerrado (ZSeMO) circula un número fijo de solicitudes y no existe una fuente externa independiente. Basado en consideraciones físicas, en ZSeM Se selecciona sobre el arco exterior, en el que está marcado. pseudo-cero un punto relativo al cual se pueden medir las características de sincronización.
Conjunto una red es una red en la que constantemente circulan un cierto número de aplicaciones y hay aplicaciones provenientes de fuentes externas independientes.
EN homogéneo aplicaciones de la misma clase circulan en la red. Y, a la inversa, en heterogéneo la red puede contener aplicaciones de varias clases. Las aplicaciones pertenecen a clases diferentes si difieren en al menos uno de los siguientes atributos:
La ley de distribución de la duración del servicio en nodos;
Prioridades;
Rutas (caminos de movimiento de solicitudes en la red).
EN exponencial Las redes de duración del servicio en todos los nodos se distribuyen según una ley exponencial y los flujos que ingresan a la red de bucle abierto son simples (Poisson). En todos los demás casos la red es no exponencial.
Si el servicio prioritario se proporciona en al menos un nodo, entonces esto es: prioridad neto. La prioridad es un signo que determina el orden del servicio. Si el servicio de solicitudes en los nodos se realiza en el orden de recepción, entonces dicha red ninguna prioridad.
Por lo tanto, llamaremos exponencial SEMO, cumpliendo los requisitos:
Flujos de entrada SEMO veneno;
En todo NORTE SMO el tiempo de atención de las solicitudes tiene una función de distribución de probabilidad exponencial y las solicitudes se atienden en el orden de llegada;
Transferencia de solicitud desde la salida. iº SMO en la entrada j- es un evento aleatorio independiente con una probabilidad p ij ; p i0- la probabilidad de que la solicitud abandone CeMO.
Si las aplicaciones ingresan a la red y la abandonan, entonces la red se llama abierta. Si las aplicaciones no entran ni salen de la red, la red se llama cerrada. El número de aplicaciones en una red cerrada es constante.
