Chetverikov S. Yu., Popov M.A.
Rússia, Instituto de Economia e Empreendedorismo (Moscou)
A teoria dos sistemas de filas é uma disciplina matemática aplicada que investiga características numéricas fenômenos que ocorrem na economia. Estes incluem a operação de uma central telefônica, centros de atendimento ao consumidor, caixas registradoras em um supermercado, etc.
Modelos matemáticos de tais objetos são sistemas de filas (QS) descritos a seguir: solicitações (aplicações de serviço) entram no sistema, cada uma das quais é atendida por algum tempo e depois sai do sistema. No entanto, devido a restrições de recursos (número de caixas registradoras em serviço, velocidade de atendimento etc.), o sistema é capaz de atender apenas um determinado número de solicitações ao mesmo tempo. Os modelos matemáticos neste caso são projetados para resolver o problema de calcular os indicadores numéricos da qualidade de funcionamento do QS.
Ao construir modelos QS, dois sistemas são fundamentalmente distinguidos: determinísticos e estocásticos, que realmente determinam o tipo de modelo matemático.
Considere o sistema determinístico mais simples que consiste em P dispositivos idênticos, nos quais os requisitos chegam em intervalos de tempo determinísticos (constantes), e o tempo para atender cada requisito também é constante. É óbvio que se as demandas chegam em intervalos
e o tempo de serviço para cada requisito é
então a condição necessária e suficiente para o funcionamento normal do sistema é o cumprimento da desigualdade
Caso contrário, com o tempo, os requisitos se acumularão no sistema.
Opções X e q têm um significado físico simples:
X- o número médio de solicitações que chegam por unidade de tempo ou a intensidade do fluxo de entrada;
q é o número médio de requisitos que cada dispositivo é capaz de atender por unidade de tempo, ou a intensidade dos requisitos de atendimento por um dispositivo;
/ 7ts - o número médio de requisitos que podem atender P aparelhos, ou o requisito de intensidade de manutenção de todo o sistema.
Assim, a condição (1) significa que a intensidade do fluxo de entrada não deve exceder a intensidade dos requisitos de manutenção de todo o sistema. Considere a quantidade
A chamada inicialização do sistema.
Então a desigualdade (1) pode ser reescrita como:
Nesse caso, a carga pode ser interpretada como a fração média do tempo durante o qual os dispositivos estão ocupados atendendo aos requisitos, e o valor de 1 - p - como a fração média do tempo durante o qual os dispositivos estão ociosos.
Por fim, mais uma nota sobre o funcionamento de um sistema com características determinísticas:
se no momento inicial o sistema estiver livre e a condição (2) for satisfeita, então cada demanda que entrar no sistema se tornará imediatamente o dispositivo de serviço;
no caso p
finalmente, se p > 1, então por unidade de tempo a fila aumenta em média em Sr-1).
Em sistemas de filas reais, elementos de aleatoriedade desempenham um papel significativo:
em primeiro lugar, os tempos entre as chegadas dos sinistros não são determinísticos;
em segundo lugar, os tempos de atendimento dos pedidos não são determinísticos.
Além disso, elementos de aleatoriedade podem aparecer devido a outros motivos, por exemplo, falhas de elementos de sistemas de filas.
Acontece que os elementos de aleatoriedade afetam significativamente a qualidade do funcionamento dos sistemas de serviço. Então, se a carga p = 1, então, ao contrário dos sistemas determinísticos, nos sistemas estocásticos a fila tende ao infinito ao longo do tempo em média. Filas em sistemas estocásticos são formadas mesmo no caso p
Considere uma descrição formalizada de QS. Os principais parâmetros do QS são:
fluxo de entrada de requisitos;
estrutura do sistema;
características temporais dos requisitos de serviço;
disciplina de serviço.
Vamos dar uma olhada nessas opções.
Fluxo de entradaé caracterizado por momentos aleatórios de recebimento de requisitos em um sistema simples, e para sistemas complexos - pelos tipos de requisitos que chegam a esses momentos.
Ao especificar um fluxo aleatório, geralmente assume-se que o fluxo de entrada é recorrente e, na maioria das vezes, Poisson.
Façamos algumas observações sobre a correção da descrição dos fluxos de demandas que entram em sistemas reais por Poisson e recorrentes. Obviamente, a propriedade da ausência de efeitos colaterais em sistemas reais é extremamente rara, uma vez que um fluxo com tal propriedade pode receber um número arbitrariamente grande de requisitos com uma probabilidade diferente de zero (embora extremamente pequena) em qualquer período de tempo arbitrariamente pequeno. No entanto, a prática mostra que a descrição do fluxo de entrada por Poisson é legítima na maioria dos casos com um grau de precisão suficiente. Uma confirmação matemática adicional deste fato é o teorema de Khinchin, que diz que a união de um grande número de fluxos "raros" sob restrições muito fracas dá um fluxo de Poisson.
A segunda propriedade do fluxo de Poisson - estacionaridade - também não suscita críticas. De fato, a intensidade do fluxo de entrada, como regra, depende da hora do dia, do ano e assim por diante. Se as propriedades de ausência de efeito posterior e normalidade forem preservadas, um fluxo de Poisson não estacionário é obtido. Em alguns casos, é possível desenvolver modelos matemáticos para calcular sistemas econômicos com tal fluxo de entrada, mas as fórmulas resultantes são muito complicadas e difíceis de aplicação prática. Por esta razão, os cálculos são limitados a um determinado intervalo de tempo em que a intensidade do fluxo de entrada muda pouco.
Se apenas a propriedade de ordinaridade for abandonada, obtém-se um fluxo de Poisson não comum, no qual os momentos de chegada dos requisitos formam um fluxo de Poisson ordinário, mas em cada um desses momentos chega um número aleatório de requisitos. A maioria dos resultados válidos para sistemas com fluxo de Poisson é praticamente inalterado para sistemas com fluxo de Poisson não comum.
Para definir a estrutura QSé necessário listar todos os elementos disponíveis no sistema, e indicar quais os tipos de requisitos ou mesmo em quais fases do serviço cada elemento pode atender. Nesse caso, um único elemento pode atender solicitações de vários tipos e, inversamente, solicitações do mesmo tipo podem ser atendidas em vários elementos. A seguir, assumiremos que o QS possui um ou mais elementos idênticos, e cada requisito pode ser atendido em qualquer um deles. Sistemas desse tipo são chamados única linha(um elemento) ou multilinha(vários itens).
Os sistemas de serviço podem ter elementos para que as solicitações aguardem o início do serviço. Se existem infinitamente muitos desses elementos, então eles falam de sistemas com espera, se seu número é finito - sobre sistemas com um número finito de lugares de espera, se eles estão ausentes (o requisito que fez com que todos os elementos ocupados no momento de entrada no sistema é perdido; um exemplo são os sistemas telefônicos comuns) - sobre sistemas com perdas.
Cronometragem os requisitos de serviço também são um objeto complexo para uma descrição formalizada. Geralmente assume-se que os tempos de atendimento de todos os clientes são independentes uns dos outros e são variáveis aleatórias igualmente distribuídas. Caso o QS receba solicitações de vários tipos, a distribuição do tempo de atendimento pode depender do tipo de solicitação.
Disciplina de serviço consiste na regra de enfileiramento dos requisitos e na ordem em que são selecionados da fila para atendimento, na distribuição dos elementos entre os requisitos e em sistemas multifásicos - entre as fases de atendimento. Assumiremos que a disciplina mais simples é implementada no sistema - atendendo ao requisito na ordem de chegada (FIFO). Em sistemas multilinha, uma fila comum é formada para todos os elementos, e a primeira reclamação na fila vai para qualquer elemento liberado.
No entanto, o QS também usa disciplinas de serviço mais complexas. Os exemplos mais simples de tais disciplinas são a ordem de serviço de inversão (reversa) (LIFO), na qual o requisito que entrou no sistema por último é atendido.
A disciplina de separação uniforme dos elementos do sistema, na qual cada um dos P requisitos no sistema são atendidos na mesma taxa 1/p.Às vezes, no momento em que um requisito entra no sistema, o tempo de seu atendimento (o trabalho a ser feito) é conhecido. Então é possível usar disciplinas que dependem dos tempos residuais de atendimento das requisições. Em particular, a disciplina de atender ao primeiro requisito com o tempo mínimo de atendimento restante permite obter o comprimento mínimo da fila a qualquer momento. O uso de disciplinas de serviço complexas muitas vezes permite, sem custos adicionais, melhorar significativamente a qualidade do funcionamento do QS.
Uma classe especial de QSs são sistemas prioritários que recebem fluxos de solicitações de várias prioridades, e solicitações de prioridades mais altas têm precedência sobre solicitações de prioridades mais baixas, ou seja, servido mais cedo. As prioridades podem ser relativas, quando solicitações de prioridade mais alta não interrompem serviços de solicitações de prioridade mais baixa nos elementos, e absolutas, quando ocorre tal interrupção.
No caso de prioridades absolutas, várias modificações também são possíveis: clientes mal atendidos com atendimento interrompido saem dos sistemas (sistemas com dropout), continuam sendo atendidos após todos os clientes de maior prioridade saírem do sistema (sistemas com pós-atendimento) e são atendidos novamente.
As disciplinas de serviço também devem incluir fatores como o estágio preparatório antes do início do atendimento do próximo requisito ou após a chegada de um requisito em um sistema livre, o estágio de mudança de um elemento para requisitos de serviço de um tipo diferente, atendimento de requisitos por elementos não confiáveis de o sistema, etc Por fim, a quantidade de tempo que uma solicitação gasta no sistema ou o tempo que leva para aguardar o início do serviço pode ser limitada.
Vamos agora descrever as características do QS que são de interesse do usuário. Às vezes, na prática, eles são chamados de características probabilístico-temporais. O mais importante deles são comprimento da fila(ou seja, o número de solicitações aguardando para serem atendidas) e tempo de espera para que a solicitação comece a ser veiculada. Como tanto o comprimento da fila quanto o tempo de espera para o início do serviço são variáveis aleatórias, então, naturalmente, eles são descritos por suas próprias distribuições. Além disso, as distribuições do comprimento da fila e do tempo de espera dependem do tempo atual.
Em sistemas com perdas ou número finito de vagas de espera, as características mais importantes também incluem a probabilidade de perder o pedido.Às vezes, juntamente com o comprimento da fila, eles consideram o número total de solicitações no sistema, e junto com o tempo de espera de início do serviço - tempo de residência do requisito no sistema.
Em sistemas com perdas ou número finito de vagas de espera, bem como em sistemas com espera e carregamento p
A maioria dos trabalhos sobre a teoria das filas são dedicados a encontrar características estacionárias, embora características não estacionárias tenham sido estudadas em detalhes suficientes.
Literatura
Considerado na aula anterior, um processo aleatório de Markov com estados discretos e tempo contínuo ocorre em sistemas de filas (QS).
Sistemas de filas - são sistemas em que as solicitações de atendimento são recebidas em horários aleatórios, enquanto as solicitações recebidas são atendidas pelos canais de atendimento disponíveis no sistema.
Exemplos de sistemas de filas são:
Nós |
Requisitos |
|
Hospital |
ordenanças |
Pacientes |
Produção |
||
O aeroporto |
Saídas de pista Pontos de registro |
Passageiros |
Considere o esquema de operação do QS (Fig. 1). O sistema consiste em um gerador de requisições, um despachante e um nó de serviço, um nó de contabilidade de falhas (terminador, destruidor de requisições). Nó de serviço em caso Geral pode ter vários canais de atendimento.
Além desses elementos básicos no QS, algumas fontes também distinguem os seguintes componentes:
terminador - destruidor de transações;
armazém - armazenamento de recursos e produtos acabados;
conta contábil - para realizar operações do tipo "lançamento";
gerente - gerente de recursos;
A primeira divisão (pela presença de filas):
NO CMO com falhas uma solicitação que chega no momento em que todos os canais estão ocupados é rejeitada, sai do QS e não é mais atendida.
NO CMO com uma fila um aplicativo que chega em um momento em que todos os canais estão ocupados não sai, mas enfileira e aguarda uma oportunidade para ser atendido.
QS com filas subdividido em tipos diferentes dependendo de como a fila está organizada - limitado ou não limitado. As restrições podem estar relacionadas tanto ao comprimento da fila quanto ao tempo de espera, "disciplina de serviço".
Assim, por exemplo, os seguintes QS são considerados:
Os tipos de restrição de fila podem ser combinados.
Outra classificação divide o CMO de acordo com a origem das aplicações. O próprio sistema ou algum ambiente externo que exista independentemente do sistema pode gerar aplicações (requisitos).
Naturalmente, o fluxo de solicitações geradas pelo próprio sistema dependerá do sistema e de seu estado.
Além disso, os SMOs são divididos em abrir CMO e fechado SMO.
Em um QS aberto, as características do fluxo de aplicações não dependem do estado do próprio QS (quantos canais estão ocupados). Em um QS fechado, eles dependem. Por exemplo, se um trabalhador atende a um grupo de máquinas que requerem ajustes de tempos em tempos, a intensidade do fluxo de "requisitos" das máquinas depende de quantas delas já estão em boas condições e aguardando ajustes.
Um exemplo de sistema fechado: a emissão de um salário por um caixa de uma empresa.
Pelo número de canais, os QS são divididos em:
As principais características de um sistema de filas de qualquer tipo são:
Para descrever o fluxo de entrada, você precisa definir uma lei probabilística que determina a sequência de momentos de recebimento dos requerimentos de serviço, e indicar o número de tais reclamações em cada recibo regular. Nesse caso, via de regra, operam com o conceito de “distribuição probabilística dos momentos de recebimento de requerimentos”. Aqui você pode agir como requisitos individuais e de grupo (o número de tais reivindicações em cada recebimento sucessivo). Neste último caso, geralmente nós estamos falando sobre um sistema de filas com serviço de grupo paralelo.
Eu– tempo de chegada entre os requisitos – variáveis aleatórias independentes identicamente distribuídas;
E(A)é o tempo médio de chegada (MO);
λ=1/E(A)- a intensidade de recebimento dos requisitos;
Características do fluxo de entrada:
Virar - um conjunto de requisitos esperando para serem atendidos.
A fila tem um nome.
Disciplina de fila determina o princípio segundo o qual as solicitações que chegam à entrada do sistema de atendimento são conectadas da fila ao procedimento de atendimento. As disciplinas de fila mais usadas são definidas pelas seguintes regras:
primeiro a entrar primeiro a sair (FIFO)
o tipo mais comum de fila.
Qual estrutura de dados é adequada para descrever tal fila? A matriz é ruim (limitada). Você pode usar uma estrutura LIST.
A lista tem um começo e um fim. A lista consiste em entradas. Uma entrada é uma célula de lista. O aplicativo chega ao final da lista e é selecionado para serviço desde o início da lista. A entrada consiste em uma descrição do aplicativo e um link (um índice de quem está por trás dele). Além disso, se a fila tiver um limite de tempo, o limite de tempo também deverá ser especificado.
Você, como programador, deve ser capaz de fazer listas de dois lados, de um lado.
Listar ações:
Uma estrutura conhecida como STACK. Pode ser descrito por uma estrutura de matriz ou lista;
Cada aplicação é caracterizada, entre outras coisas, por um nível de prioridade e, ao chegar, é colocada não no final da fila, mas no final de seu grupo de prioridade. O despachante classifica por prioridade.
Mecanismo de serviço é determinado pelas características do próprio procedimento de atendimento e pela estrutura do sistema de atendimento. Os procedimentos de serviço incluem:
Para uma descrição analítica das características do procedimento de atendimento, utiliza-se o conceito de “distribuição probabilística do tempo de atendimento dos requisitos”.
Si- tempo de serviço euª exigência;
E(S)– tempo médio de atendimento;
μ=1/E(S)- a velocidade dos requisitos de serviço.
Deve-se observar que o tempo para atender um aplicativo depende da natureza do próprio aplicativo ou dos requisitos do cliente e do estado e recursos do sistema de atendimento. Em alguns casos, também é necessário levar em consideração probabilidade de falha do canal de serviço após um certo intervalo de tempo limitado. Esta característica pode ser modelada como um fluxo de falhas entrando no QS e tendo prioridade sobre todas as outras requisições.
Fator de utilização de QS
Nμ – taxa de serviço no sistema quando todos os dispositivos de serviço estão ocupados.
ρ=λ/( Nµ) é chamado Fator de utilização de QS , mostra quantos recursos do sistema estão sendo usados.
A estrutura do sistema de serviços é determinada pelo número e arranjo mútuo canais de atendimento (mecanismos, instrumentos, etc.). Em primeiro lugar, deve-se ressaltar que um sistema de atendimento pode ter não um canal de atendimento, mas vários; um sistema deste tipo é capaz de atender a vários requisitos simultaneamente. Nesse caso, todos os canais de atendimento oferecem os mesmos serviços e, portanto, pode-se argumentar que há serviço paralelo .
Exemplo. Caixas registradoras na loja.
O sistema de serviço pode consistir em vários tipos diferentes de canais de serviço pelos quais cada requisito atendido deve passar, ou seja, no sistema de serviço os procedimentos de atendimento aos requisitos são implementados sequencialmente . O mecanismo de serviço define as características do fluxo de solicitações de saída (servido).
Exemplo. Comissão Médica.
Serviço Combinado - manutenção de depósitos na caixa de poupança: primeiro o controlador, depois o caixa. Em regra, 2 controladores por caixa.
Então, a funcionalidade de qualquer sistema de filas é determinada pelos seguintes fatores principais :
Como os principais critérios para a eficácia do funcionamento dos sistemas de filas Dependendo da natureza do problema a ser resolvido, pode haver:
É óbvio que R obl + P otk = 1.
Atraso – um dos critérios de atendimento do QS, o tempo gasto pelo pedido na antecipação do atendimento.
Di– atraso na fila de requisições eu;
W i \u003d D i + S i– tempo gasto no sistema do requisito eu.
(com probabilidade 1) é o atraso médio estabelecido de um pedido na fila;
(com probabilidade 1) é o tempo médio em estado estacionário que o requisito passa no QS (espera).
Q(t)- o número de solicitações na fila por vez t;
EU(t)– número de clientes no sistema por vez t(Q(t) mais o número de requisitos que estão em serviço no momento t.
Então expoentes (se houver)
(com probabilidade 1) é o número médio de tempo estável de solicitações na fila;
(com probabilidade 1) é o número médio de requisições no sistema com média de tempo em estado estacionário.
Observe que ρ<1 – обязательное условие существования d, w, Q e eu no sistema de filas.
Se lembrarmos que ρ= λ/( Nμ), fica claro que se a intensidade de recebimento de solicitações for maior que Nμ, então ρ>1, e é natural que o sistema não consiga lidar com tal fluxo de aplicações e, portanto, não se pode falar em d, w, Q e EU.
Os resultados mais gerais e necessários para sistemas de filas incluem as equações de conservação
Deve-se notar que os critérios acima para avaliar o desempenho do sistema podem ser calculados analiticamente para sistemas de filas M/M/N(N>1), ou seja, sistemas com fluxos Markov de clientes e serviços. Por M/G/ l para qualquer distribuição G e para alguns outros sistemas. Em geral, a distribuição do tempo entre as chegadas, a distribuição do tempo de atendimento, ou ambas, devem ser exponenciais (ou uma espécie de distribuição Erlang exponencial de k-ésima ordem) para que uma solução analítica seja possível.
Além disso, você também pode falar sobre características como:
Outro exemplo interessante (e ilustrativo) de uma solução analítica – cálculo do atraso de fila médio em estado estacionário para um sistema de filas M/G/ 1 de acordo com a fórmula:
.
Na Rússia, esta fórmula é conhecida como a fórmula de Pollacek. – Khinchin, no exterior esta fórmula está associada ao nome de Ross.
Assim, se E(S) Tem maior valor, então a sobrecarga (em este caso medido como d) será maior; que é de se esperar. A fórmula também revela um fato menos óbvio: o congestionamento também aumenta quando a variabilidade na distribuição do tempo de atendimento aumenta, mesmo que o tempo médio de atendimento permaneça o mesmo. Intuitivamente, isso pode ser explicado da seguinte forma: a variância da variável aleatória tempo de atendimento pode levar grande importância(porque deve ser positivo), ou seja, o único dispositivo de serviço estará ocupado muito tempo, o que aumentará a fila.
O tema da teoria das filasé estabelecer a relação entre os fatores que determinam a funcionalidade do sistema de filas e a eficiência de seu funcionamento. Na maioria dos casos, todos os parâmetros que descrevem os sistemas de filas são variáveis ou funções aleatórias, portanto, esses sistemas são chamados de sistemas estocásticos.
A natureza aleatória do fluxo de pedidos (requisitos), bem como, no caso geral, a duração do serviço leva a que ocorra um processo aleatório no sistema de filas. Pela natureza do processo aleatório que ocorrem em um sistema de filas (QS) são distinguidos Sistemas Markov e não Markov . Nos sistemas Markov, o fluxo de entrada de solicitações e o fluxo de saída de solicitações atendidas (reivindicações) são Poisson. Os fluxos de Poisson facilitam a descrição e a construção de um modelo matemático de um sistema de filas. Esses modelos têm bastante soluções simples, então a maioria das aplicações conhecidas da teoria das filas usa um esquema markoviano. No caso de processos não markovianos, os problemas de estudo de sistemas de filas se tornam muito mais complicados e exigem o uso de modelagem estatística, métodos numéricos usando um computador.
Na prática da atividade humana, um grande lugar é ocupado por processos de enfileiramento que ocorrem em sistemas projetados para uso reutilizável na solução de problemas do mesmo tipo. Tais sistemas são chamados de sistemas de filas (QS). Exemplos de tais sistemas são sistemas de telefone, sistemas de computador, automotivo, aviação, sistemas de manutenção, lojas, bilheterias e similares.
Cada sistema é composto por um certo número de unidades de serviço (instrumentos, dispositivos, dispositivos "pontos, estações), que são chamados de canais de serviço. De acordo com o número de canais, o QS é dividido em canal único e multicanal. O diagrama de um sistema de filas de canal único é mostrado na Fig. 6.2.
As aplicações normalmente não entram no sistema de forma regular, mas sim de forma aleatória, formando um fluxo aleatório de aplicações (requisitos). O atendimento de cada requisito em si pode levar um certo tempo ou, mais frequentemente, um tempo indefinido. A natureza aleatória leva ao fato de que o QS é carregado de forma desigual: em alguns períodos de tempo acumula muito um grande número de aplicativos (eles entram na fila ou deixam o QS sem atendimento), enquanto em outros períodos o QS opera com subcarga ou está ocioso.
Arroz. 6.2.
O objetivo do estudo dos sistemas de filas é analisar a qualidade de seu funcionamento e identificar oportunidades para sua melhoria. Ao mesmo tempo, o conceito de "qualidade de funcionamento" em cada caso individual terá sua própria significado específico e expressa em diferentes termos quantitativos. Por exemplo, indicadores quantitativos como tamanho da fila para atendimento, tempo médio de atendimento, espera por atendimento ou encontrar um requisito no sistema de atendimento, tempo ocioso dos dispositivos de atendimento; confiança de que todas as solicitações recebidas pelo sistema serão atendidas.
Assim, a qualidade do funcionamento do sistema de filas é entendida não como a qualidade da execução de um determinado trabalho, cuja solicitação foi recebida, mas o grau de satisfação da necessidade de atendimento.
O tema da teoria das filas é a construção de modelos matemáticos que relacionam as condições de operação dadas do QS (o número de canais, seu desempenho, a natureza do fluxo de aplicativos, etc.) com os indicadores de desempenho do QS, que descrevem sua capacidade de lidar com o fluxo de aplicativos.
A primeira característica que permite classificar as tarefas de enfileiramento é o comportamento das demandas recebidas pelo sistema de atendimento no momento em que todas as máquinas estão ocupadas.
Em alguns casos, uma reclamação que entra no sistema em um momento em que todas as máquinas estão ocupadas não pode esperar que elas sejam liberadas e deixa o sistema sem atendimento, ou seja, a reivindicação é perdida para o sistema de veiculação fornecido. Tais sistemas de serviço são chamados de sistemas com perdas, e os problemas formulados com base neles são chamados de problemas de serviço para sistemas com perdas.
Se, por outro lado, uma demanda, tendo entrado no sistema, entra na fila e aguarda a liberação do dispositivo, esses sistemas são chamados de sistemas com espera e as tarefas correspondentes são chamadas de tarefas de serviço em sistemas com espera. O QS com espera é dividido em diferentes tipos dependendo de como a fila está organizada: com um comprimento de fila limitado ou ilimitado, com um tempo de espera limitado, etc.
Os QSs também diferem no número de requisitos que podem estar simultaneamente no sistema de atendimento. Distribuir:
Dependendo das formas organização interna serviços do sistema são:
Um passo importante no estudo de QS é a escolha dos critérios que caracterizam o processo em estudo. A escolha depende do tipo de problemas em estudo, do objetivo perseguido pela solução.
Na prática, na maioria das vezes, existem sistemas em que o fluxo de requisitos é próximo ao mais simples, e o tempo de atendimento obedece a uma lei de distribuição exponencial. Esses sistemas são mais desenvolvidos na teoria das filas.
Nas condições de uma empresa, são típicas as tarefas com espera, com um número finito de dispositivos de serviço, com um fluxo limitado de requisitos e com serviço desordenado.
Nas últimas décadas, em vários campos economia nacional havia a necessidade de resolver problemas probabilísticos relacionados à operação de sistemas de filas. Exemplos de tais sistemas são as centrais telefônicas, oficinas, pontos de venda, bilheterias e assim por diante. o trabalho de qualquer sistema de filas consiste em atender o fluxo de entrada de necessidades (chamadas de assinantes, fluxo de clientes para a loja, necessidades de trabalho na oficina, etc.).
A disciplina matemática que estuda modelos de sistemas de filas reais é chamada de teoria das filas. A tarefa da teoria das filas é estabelecer a dependência dos indicadores de desempenho resultantes do sistema de filas (a probabilidade de o requisito ser atendido; a expectativa matemática do número de requisitos atendidos, etc.) dispositivos no sistema, os parâmetros do fluxo de entrada de requisitos, etc.) .) é possível estabelecer tais dependências na forma de fórmula apenas para sistemas de filas simples. O estudo de sistemas reais é realizado por imitação, ou modelagem de seu trabalho em um computador usando o método de testes estatísticos.
O sistema de filas é considerado dado se o seguinte for definido:
1) o fluxo de entrada de requisitos, ou, em outras palavras, a lei de distribuição que caracteriza os momentos no tempo em que os requisitos entram no sistema. A causa raiz dos requisitos é chamada de origem. No que segue, concordamos em assumir que a fonte possui um número ilimitado de requisitos e que os requisitos são homogêneos, ou seja, diferem apenas nos momentos de sua aparição no sistema;
2) um sistema de serviço que consiste em uma unidade e um nó de serviço. Este último é um ou mais dispositivos de serviço, que serão referidos como dispositivos. Cada requisito deve ir para um dos instrumentos para ser atendido. Pode acontecer que os requisitos tenham que esperar até que os dispositivos estejam livres. Nesse caso, os requisitos estão na loja, formando uma ou mais filas. Vamos supor que a transição do requisito do armazenamento para o nó de serviço ocorra instantaneamente;
3) o tempo de atendimento do requisito por cada dispositivo, que é uma variável aleatória e se caracteriza por uma determinada lei de distribuição;
4) disciplina de espera, ou seja, um conjunto de regras que regem o número de requisitos que estão ao mesmo tempo no sistema. Um sistema no qual uma demanda recebida é rejeitada quando todos os dispositivos estão ocupados é chamado de sistema sem espera. Se uma solicitação que manteve todos os dispositivos ocupados entrar em uma fila e esperar até
até que um dos dispositivos fique livre, esse sistema é chamado de sistema de espera puro. Um sistema em que um cliente que manteve todos os servidores ocupados entra na fila somente se o número de clientes no sistema não exceder um determinado nível (caso contrário, o cliente é perdido) é chamado de sistema de filas misto;
5) disciplina de serviço, ou seja, um conjunto de regras segundo as quais o requisito é selecionado da fila para atendimento. As seguintes regras são mais frequentemente usadas na prática:
- são aceites os pedidos de serviço por ordem de prioridade;
- Os pedidos de atendimento são aceitos de acordo com o tempo mínimo para recebimento de recusa;
- os pedidos de serviço são aceitos por ordem aleatória de acordo com as probabilidades dadas;
6) disciplina de fila, ou seja, um conjunto de regras segundo as quais o requisito dá preferência a uma ou outra fila (se houver mais de uma) e está localizado na fila selecionada. Por exemplo, uma reclamação recebida pode ser colocada na fila mais curta; nesta fila, ela pode ser localizada por último (essa fila é chamada ordenada), ou pode ir para o serviço fora de turno. Outras opções também são possíveis.
5 Exemplo de modelagem QS
Considere o seguinte sistema:
1 Solicitações chegam em horários aleatórios, enquanto
o intervalo de tempo Q entre quaisquer duas demandas sucessivas tem uma lei exponencial com o parâmetro eu, ou seja, a função de distribuição tem a forma
>0. (11)
O sistema de filas consiste em s servidores idênticos e numerados.
3 Tempo T sobre bsl - uma variável aleatória com uma lei de distribuição uniforme no segmento.
4 Sistema sem espera, ou seja, o requisito que deixou todos os dispositivos ocupados deixa o sistema.
5 A disciplina de serviço é a seguinte: se no momento do recebimento do k-ésimo requisito o primeiro servidor estiver livre, então ele começa a atender o requisito; se este servidor estiver ocupado e o segundo estiver livre, a solicitação será atendida pelo segundo servidor e assim por diante.
Precisa avaliar expectativas matemáticas o número de solicitações atendidas pelo sistema no tempo T e rejeitadas.
Para o momento inicial de cálculo escolhemos o momento de chegada do primeiro requisito Т1=0. Vamos introduzir a seguinte notação: Tk é o momento de recebimento do k-ésimo requisito; ti - hora de término do serviço i-ésimas exigências dispositivo, i=1, 2, 3, ...,s.
Suponha que no tempo T 1 todos os dispositivos estejam livres.
A primeira demanda chega ao servidor 1. O tempo de atendimento deste servidor tem distribuição uniforme no segmento . Portanto, o valor específico de t obl deste tempo é encontrado pela fórmula
(12)
onde r é o valor de uma variável aleatória R uniformemente distribuída no segmento . O dispositivo 1 estará ocupado durante o tempo to bsl. Portanto, o ponto de tempo t 1 do fim do atendimento do requisito pelo dispositivo 1 deve ser considerado igual a: t 1 = T1+ t sobre obsl.
Em seguida, adicione um ao contador de solicitações atendidas e passe para a próxima solicitação.
Suponha que k requisitos já tenham sido considerados. Vamos definir o momento Т k+1 de recebimento do (k+1)-ésimo requisito. Para fazer isso, encontramos o valor t do intervalo de tempo entre os sucessivos requisitos. Como esse intervalo tem uma lei exponencial, então
12
x \u003d - Em r (13)
| Ll
onde r é o próximo valor da variável aleatória R . Então o momento de chegada do (k + 1)º requisito: T k +1 = Tk + T.
O primeiro dispositivo está livre neste momento? Para responder a esta pergunta, é necessário verificar a condição ti<
Tk
+
i
- Если это условие выполнено, то к моменту Т
k
+1 первый прибор освободился и может
обслуживать требование.
В этом случае
t
1 заменяем на (Т
k
+1
+
t
обсл), добавляем единицу в счетчик об
служенных
требований и переходим к следующему требованию. Если
t
1>T k +1, então o primeiro dispositivo no tempo T k +1 está ocupado. Nesse caso, verificamos se o segundo dispositivo está livre. Se a condição i 2<
Tk
+
i
выполнено, заменяем t2 на (Т
k
+1+
t
о
бсл),
добавляем единицу в счетчик обслуженных требований и переходим к
следующему требованию. Если
t
2>Т k +1, então verificamos a condição 1×<Тк+1 и т. д.
Eсли
при всех
i
от 1 до
s
имеет
ti
>T k +1, então no momento T k +1 todos os dispositivos estão ocupados. Nesse caso, adicionamos um ao contador de falhas e passamos para o próximo requisito. Cada vez, após calcular T k + 1, devemos também verificar a condição para o término da implementação: Tk + i<
T
. Если это условие выполнено, то одна
реализация
процесса функционирования системы воспроизведена и испыта
ние заканчивается. В счетчике обслуженных
требований и в счетчике отказов находятся
числа n обсл и n отк.
Após repetir esse teste n vezes (usando r diferente) e calcular a média dos resultados dos experimentos, determinamos as estimativas das expectativas matemáticas do número de clientes atendidos e do número de clientes que foram rejeitados:
(14)
(Ji
nj = 1
onde (n obl) j e (n obl) j são os valores de n obl e n obl no j-ésimo experimento.
13
Lista de fontes usadas
1 Emelyanov A.A. Modelagem de simulação de processos econômicos [Texto]: Proc. subsídio para universidades / A.A. Emelyanov, E. A. Vlasova, R. V. Pensamento. - M. : Finanças e estatísticas, 2002. - 368s.
2 Buslenko, N.P. Modelagem de sistemas complexos [Texto] / N.P. Buslenko.- M.: Nauka, 1978. - 399p.
3 soviéticos B.Ya. Sistemas de modelagem [Texto]: Proc. para universidades / B.Ya. Sove tov, S.A. Yakovlev. -M. : Altíssima. escola, 1985. - 271 p.
4 soviéticos B.Ya. Sistemas de modelação [Texto]: Workshop laboratorial: Proc. subsídio para universidades na especialidade: "Sistema automatizado de processamento de informações e controle". / B.Ya. Sovetov, S.A. Yakovlev. -M. : Altíssima. escola, 1989. - 80 p.
5 Maximei I.V. Modelagem de simulação em computador [Texto] / Maksimey, I.V. -M: RÁDIO E COMUNICAÇÃO, 1988. - 231s.
6 Wentzel E.S. Teoria da probabilidade [Texto]: livro didático. para universidades / E.S. Meta de ventilação - M. : Superior. escola, 2001. - 575 p.
7 Gmurman, V. E. Teoria das probabilidades e estatística matemática [Texto]: livro didático. subsídio / V.E. Gmurman.- M.: Mais alto. escola, 2001. - 479 p.
Anexo A
(obrigatoriedade)
Tópicos aproximados de assentamento e obras gráficas
1 Há um médico trabalhando no pronto-socorro. A duração do tratamento do paciente
e os intervalos de tempo entre as admissões dos pacientes são variáveis aleatórias distribuídas de acordo com a lei de Poisson. De acordo com a gravidade das lesões, os pacientes são divididos em três categorias, a admissão de um paciente de qualquer categoria é um evento aleatório com distribuição equiprovável. O médico lida primeiro com pacientes com lesões mais graves (na ordem em que são recebidas), depois, se não houver, com pacientes de gravidade moderada e só depois com pacientes com lesões menores. Simule o processo e estime os tempos médios de espera na fila de pacientes de cada categoria.
2 Existem duas zonas de reparação na frota de automóveis urbanos. O primeiro serve reparos de curtos e duração média, o segundo - médio e longo. Como avarias, os veículos são entregues à frota; o intervalo de tempo entre entregas é uma variável aleatória de Poisson. A duração do reparo é uma variável aleatória com distribuição normal. Modele o sistema descrito. Estime os tempos médios de espera na fila de transporte, exigindo reparos de curto, médio e longo prazo, respectivamente.
3 Um minimercado com um controlador - um caixa atende clientes cujo fluxo de entrada obedece à lei de Poisson com parâmetro de 20 clientes/hora. Realize uma simulação do processo descrito e determine a probabilidade de parada do controlador - caixa comprimento médio filas, o número médio de clientes no minimercado, o tempo médio de espera para atendimento, o tempo médio gasto pelos clientes no minimercado e avaliar o seu trabalho.
4 ATS recebe pedidos de chamadas de longa distância. O fluxo de solicitações é Poisson. Em média, são recebidas 13 candidaturas por hora. Encontre o número médio de pedidos recebidos por dia, o tempo médio entre o aparecimento de pedidos. Na central telefônica, o mau funcionamento aparece se mais de 50 solicitações forem recebidas em meia hora. Encontre a probabilidade de falha da estação.
5 A estação de serviço recebe os mais simples
o fluxo de aplicações com intensidade de 1 carro por 2 horas, não podendo ficar mais de 3 carros na fila do pátio. Tempo médio de reparo - 2 horas. Avaliar o trabalho do CMO e desenvolver recomendações para melhorar o serviço.
6 Um tecelão atende a um grupo de teares, realizando intervenções de curto prazo conforme necessário, cuja duração é uma variável aleatória. Simule a situação descrita. Qual é a probabilidade de paralisação de duas máquinas ao mesmo tempo. Qual é o tempo médio de inatividade por máquina.
7 Em uma central telefônica de longa distância, duas operadoras de telefonia atendem uma fila comum de pedidos. O próximo pedido é atendido pela telefonista que foi a primeira a ser liberada. Se ambos estiverem ocupados quando o pedido for recebido, a chamada será cancelada. Simule o processo assumindo que os fluxos de entrada são Poisson.
8 Há dois médicos trabalhando no pronto-socorro. Duração do tratamento dói
e os intervalos de tempo entre as admissões dos pacientes são variáveis aleatórias distribuídas de acordo com a lei de Poisson. De acordo com a gravidade das lesões, os pacientes são divididos em três categorias, a admissão de um paciente de qualquer categoria é um evento aleatório com distribuição equiprovável. O médico lida primeiro com pacientes com lesões mais graves (na ordem em que são recebidas), depois, se não houver, com pacientes de gravidade moderada e só depois com pacientes com lesões menores. Simule o processo e estime os tempos médios de espera na fila de pacientes de cada categoria.
9 Em uma central telefônica intermunicipal, duas operadoras de telefonia atendem
criar uma fila comum de pedidos. O próximo pedido é servido por essa telefonista,
que foi lançado primeiro. Se ambos estiverem ocupados no momento do recebimento do pedido, uma fila será formada. Simule o processo assumindo que os fluxos de entrada são Poisson.
10 Em um sistema de transmissão de dados, os pacotes de dados são trocados entre os nós A e B através de um canal de comunicação duplex. Os pacotes chegam aos pontos do sistema de assinantes com intervalos de tempo entre eles de 10 ± 3 ms. A transmissão de pacotes leva 10 ms. Os pontos possuem registradores de buffer que podem armazenar dois pacotes, incluindo o que está sendo transmitido. Se um pacote chega no momento em que os registradores estão ocupados, os pontos do sistema são fornecidos com acesso a uma linha de comunicação satélite half duplex, que transmite pacotes de dados em 10 ± 5 ms. Quando a linha de satélite está ocupada, o pacote é rejeitado. Simule a troca de informações no sistema de transmissão de dados por 1 min. Determine a frequência das chamadas para a linha de satélite e sua carga. Se forem possíveis falhas, determine o volume de registros de buffer necessários para que o sistema funcione sem falhas.
11 Deixe o sistema padrão ser usado em uma central telefônica com uma entrada: se o assinante estiver ocupado, a fila não é formada e é necessário ligar novamente. Simule a situação: três assinantes tentam entrar em contato com o mesmo dono do número e, se forem bem-sucedidos, conversam com ele por algum tempo (aleatório em duração). Qual é a probabilidade de que alguém tentando falar pelo telefone não consiga fazê-lo em um determinado tempo T.
12 Uma empresa comercial planeja atender pedidos de compra de mercadorias por telefone, para o qual é necessário instalar uma central telefônica miniautomática adequada com vários telefones. Se o pedido chegar quando todas as linhas estiverem ocupadas, o cliente receberá uma recusa. Se no momento da recepção do pedido pelo menos uma linha estiver livre, é feita uma mudança para esta linha e um pedido é feito. A intensidade do fluxo de entrada de pedidos é de 30 pedidos por hora. A duração da aplicação é em média 5 minutos. Determine o número ótimo de canais de atendimento para garantir a operação estacionária do QS.
13 Em uma loja de autoatendimento existem 6 controladores - caixas. O fluxo de entrada de compradores obedece à lei de Poisson com uma intensidade de 120 pessoas por hora. Um caixa pode atender 40 pessoas por hora. Determine a probabilidade de caixa ocioso, o número médio de clientes na fila, o tempo médio de espera, o número médio de caixas ocupados. Faça uma avaliação do trabalho do QS.
14 Um fluxo de Poisson de 200 clientes por hora entra em uma loja de autoatendimento. Durante o dia são atendidos por 3 controladores de caixa com intensidade de 90 clientes por hora. A intensidade do fluxo de entrada de compradores durante o horário de pico aumenta para um valor de 400 compradores por hora e, durante as horas de recessão, atinge 100 compradores por hora. Determinar a probabilidade de formação de fila na loja e o comprimento médio da fila durante o dia, bem como o número necessário de controladores de caixa nos horários de pico e recesso, fornecendo o mesmo comprimento da fila e a probabilidade de sua formação como no modo nominal.
15 O número médio de clientes que chegam ao nó de liquidação em uma loja de autoatendimento é de 100 pessoas por hora. O caixa pode atender 60 pessoas por hora. Simule o processo e determine quantos caixas são necessários para que a probabilidade de fila não ultrapasse 0,6.
16 Simule uma fila em uma loja com um vendedor com leis equiprováveis de distribuição de variáveis aleatórias: a chegada de clientes e a duração do serviço (com algum conjunto fixo de parâmetros). Obtenha características estáveis: os valores médios de espera na fila pelo comprador e o tempo ocioso do vendedor na antecipação da chegada dos compradores. Avalie sua credibilidade.
17 Simule uma fila em uma loja com um vendedor com leis de Poisson de distribuição de variáveis aleatórias: a chegada de clientes e a duração do serviço (com algum conjunto fixo de parâmetros). Obtenha características estáveis: os valores médios de espera na fila pelo comprador e o tempo ocioso do vendedor na antecipação da chegada dos compradores. Avalie sua credibilidade.
18 Crie um modelo de posto de gasolina. Encontre indicadores da qualidade das solicitações de serviço. Determine o número de racks para que a fila não cresça.
19 Número médio de clientes que chegam ao terminal de pagamento em uma loja de autoatendimento, 60 pessoas por hora. O caixa pode atender 35 pessoas por hora. Simule o processo e determine quantos caixas são necessários para que a probabilidade de fila não ultrapasse 0,6.
20 Construir um Modelo Rota do onibus com n paradas. Determinar os indicadores de desempenho para o uso do QS.
Por CMO com falhas:
Por CMO com espera ilimitada tanto a taxa de transferência absoluta quanto a relativa perdem seu significado, pois cada solicitação recebida será atendida mais cedo ou mais tarde. Para tal QS, indicadores importantes são:
Por CMO tipo misto ambos os grupos de indicadores são usados: tanto relativos quanto largura de banda absoluta, e características de expectativa.
Dependendo da finalidade da operação de enfileiramento, qualquer um dos indicadores acima (ou um conjunto de indicadores) pode ser selecionado como critério de desempenho.
modelo analítico QS é um conjunto de equações ou fórmulas que permitem determinar as probabilidades dos estados do sistema no processo de sua operação e calcular indicadores de desempenho de acordo com características conhecidas fluxo de entrada e canais de atendimento.
Não existe um modelo analítico geral para um QS arbitrário. Modelos analíticos foram desenvolvidos para um número limitado de casos especiais de QS. Modelos analíticos que representam com maior ou menor precisão sistemas reais são, via de regra, complexos e difíceis de ver.
A modelagem analítica do QS é muito facilitada se os processos que ocorrem no QS forem Markovianos (os fluxos de solicitações são simples, os tempos de atendimento são distribuídos exponencialmente). Neste caso, todos os processos em QS podem ser descritos por equações diferenciais, e no caso limite, para estados estacionários- linear equações algébricas e, depois de resolvê-los, determine os indicadores de desempenho selecionados.
Vamos considerar exemplos de alguns QS.
Exemplo 2.5. Três inspetores de trânsito verificam as cartas de porte dos caminhoneiros. Se pelo menos um inspetor estiver livre, o caminhão que passa é parado. Se todos os fiscais estiverem ocupados, o caminhão passa sem parar. O fluxo de caminhões é o mais simples, o tempo de verificação é aleatório com distribuição exponencial.
Tal situação pode ser simulada por um QS de três canais com falhas (sem fila). O sistema é aberto, com aplicações homogêneas, monofásico, com canais absolutamente confiáveis.
Descrição dos estados:
Todos os inspetores são gratuitos;
Um inspetor está ocupado;
Dois inspetores estão ocupados;
Três inspetores estão ocupados.
O gráfico dos estados do sistema é mostrado na fig. 2.11.
No gráfico: - a intensidade do fluxo de caminhões; - a intensidade das verificações de documentos por um inspetor de tráfego.
A simulação é realizada para determinar a parte dos carros que não será testada.
Solução
A parte desejada da probabilidade é a probabilidade de emprego de todos os três inspetores. Como o gráfico de estado representa esquema típico"morte e reprodução", então encontraremos usando dependências (2.2).
O rendimento deste posto de inspetores de trânsito pode ser caracterizado rendimento relativo:
Exemplo 2.6. Para receber e processar os relatórios do grupo de reconhecimento, um grupo de três oficiais foi designado para o departamento de reconhecimento da associação. A taxa esperada de relatórios é de 15 relatórios por hora. O tempo médio de processamento de um relatório por um oficial é . Cada oficial pode receber relatórios de qualquer grupo de reconhecimento. O oficial liberado processa o último dos relatórios recebidos. Os relatórios recebidos devem ser processados com uma probabilidade de pelo menos 95%.
Determine se o grupo designado de três oficiais é suficiente para completar a tarefa designada.
Solução
Um grupo de oficiais funciona como um CMO com falhas, composto por três canais.
O fluxo de relatórios com intensidade 
pode ser considerado o mais simples, pois é o total de vários grupos de reconhecimento. Intensidade de manutenção 
. A lei de distribuição é desconhecida, mas isso não é essencial, pois é demonstrado que para sistemas com falhas ela pode ser arbitrária.
A descrição dos estados e o gráfico de estado do QS serão semelhantes aos dados no Exemplo 2.5.
Como o gráfico de estado é um esquema de "morte e reprodução", existem expressões prontas para as probabilidades de estado limite para ele:
A relação é chamada a intensidade reduzida do fluxo de aplicações. significado físico o seguinte: o valor é o número médio de solicitações que chegam ao QS para o tempo médio de atendimento de uma solicitação.
No exemplo 
.
No Falha na CMO ocorre quando todos os três canais estão ocupados, ou seja, . Então:
Porque probabilidade de falha no processamento de relatórios é superior a 34% (), então é necessário aumentar o pessoal do grupo. Vamos dobrar a composição do grupo, ou seja, o QS agora terá seis canais, e calcular:
Assim, apenas um grupo de seis oficiais poderá processar os relatórios recebidos com uma probabilidade de 95%.
Exemplo 2.7. Existem 15 instalações de travessia do mesmo tipo no trecho de forçamento do rio. O fluxo de equipamentos que chegam à travessia é em média 1 unidade/min, o tempo médio de travessia de uma unidade de equipamento é de 10 minutos (levando em consideração o retorno da instalação de travessia).
Avalie as principais características da travessia, incluindo a probabilidade de uma travessia imediata imediatamente após a chegada de um equipamento.
Solução
Largura de banda absoluta, ou seja, tudo o que chega à travessia é quase imediatamente atravessado.
Número médio de instalações de travessia em operação:
Cruzando as taxas de utilização e tempo de inatividade:
Um programa também foi desenvolvido para resolver o exemplo. Os intervalos de tempo para a chegada dos equipamentos na travessia, o tempo da travessia são tomados para serem distribuídos de acordo com uma lei exponencial.
As taxas de utilização do ferry após 50 viagens são praticamente as mesmas: 
.
