Simulador de Teoria das Filas (M/M/1)

taxas de chegada/serviço e estabilidade da fila

Exemplo resolvido — Simulador de Teoria das Filas (M/M/1)

Utilização ρ	0,750
Previsão de M/M/1 para L	3,000
Taxa de chegada resultante	3,0084
Tempo médio no sistema (W)	1,012
Previsão da lei de Little	3,045
L contado (média no tempo)	3,044
Divergência entre as duas	0,0006
Erro padrão do L contado	0,121

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

o precipício de rho 🖖

L = ρ/(1−ρ) não cresce de forma suave. Tem uma assíntota vertical em ρ = 1. Quando a utilização sobe de 90% para 99%, o tamanho médio da fila salta de 9 pessoas para 99. Exatamente na capacidade máxima, o valor é ilimitado. Este é o 'precipício de rho'. Uma fila com 80% de utilização parece quase idêntica a uma com 85%. No entanto, ao empurrá-la para 95%, os tempos de espera disparam, porque W = 1/(μ−λ) tem a mesma singularidade: é o denominador que encolhe em direção a zero e não o numerador que cresce. É por isso que sistemas reais, como call centers e urgências hospitalares, são deliberadamente superdimensionados bem abaixo da capacidade de 100%. Essa margem de manobra 'desperdiçada' perto do topo é o que nos mantém longe do precipício.

a aleatoriedade é o que forma a fila 🖖

Em M/M/1, os dois M significam "Markoviano": as chegadas ocorrem de forma aleatória (Poisson) e os tempos de serviço variam ao acaso (exponencial), passando por um único servidor. A ideia central é surpreendente. Uma fila pode formar-se mesmo quando, em média, o servidor é mais rápido do que a chegada dos clientes. Se todos chegassem com precisão mecânica e cada tarefa demorasse o mesmo tempo, um servidor com capacidade ociosa nunca formaria uma fila. A espera provém da variabilidade e não da sobrecarga. Ao definir λ bem abaixo de μ, uma fila continuará a aparecer e a desaparecer. Se definirmos ambos os padrões como regulares, o gráfico acima nunca sai do 0 e do 1. Com intervalos e tarefas idênticos, o servidor termina sempre antes da próxima chegada, em qualquer utilização abaixo de 1.

a Lei de Little exige quase nada 🖖

O L e o W aqui apresentados não são independentes. Satisfazem a relação L = λW e, de forma análoga, Lq = λWq. Esta identidade assume quase nada. John Little provou-a em 1961 e as suas únicas exigências são: uma taxa de chegada de longo prazo que exista e seja finita, assim como um tempo médio no sistema de longo prazo. Não exige chegadas de Poisson, serviço exponencial, independência, um único servidor, nem sequer um estado estacionário distributivo. Podemos observar o valor disto na tabela acima. Ao introduzirmos um padrão regular ou em rajadas em qualquer um dos fluxos, ρ/(1−ρ) resulta quatro vezes superior numa configuração e quinze vezes inferior noutra. Por sua vez, λW e o L contado de forma independente mantêm-se com uma diferença máxima de 0,011 de um cliente em cada uma das 405 configurações testadas. A mesma relação governa uma enfermaria de hospital, o trabalho em curso de uma fábrica e o inventário de uma loja: o conteúdo médio é igual à taxa de chegada multiplicada pelo tempo médio passado no interior.

duas médias e apenas uma delas pertence a um cliente 🖖

Defina ambos os padrões para ritmo regular e compare duas linhas da tabela. A fila que um cliente encontra ao chegar é 0,000. O observador que regista a mesma fila ao longo do tempo obtém 0,751. Cada cliente depara-se com um sistema vazio. O servidor está ocupado três quartos do tempo. Ambas as perspetivas estão corretas. L pondera o tamanho da fila pelo tempo, enquanto a perspetiva da chegada o pondera por cliente. Não há nada que obrigue duas ponderações diferentes a concordar. A lei de Little emparelha uma média de tempo com uma média de cliente e nunca afirma que são idênticas. Com as chegadas de Poisson, elas coincidem, razão pela qual é fácil não reparar nesta distinção. Uma chegada tem a mesma probabilidade em qualquer instante, pelo que a visão do cliente é uma amostra representativa do relógio. Essa é a propriedade PASTA, que pertence às chegadas em vez de pertencer à fila. Ao mudar as chegadas para agrupadas, a mesma execução devolve 27,011 em contraste com a média temporal de 21,482. Isto acontece porque uma rajada corresponde, em simultâneo, ao momento em que chega a maioria dos clientes e ao momento em que a linha é mais comprida.

Problemas resolvidos na íntegra

Uma fila com 3 chegadas por hora e um aumento de 20% 5 passos
Os clientes chegam a uma taxa de 3 por hora e o servidor processa 4 por hora. O servidor está ocioso um quarto do tempo, o que parece confortável. Calcule a fila que isto produz e, em seguida, o efeito de um aumento de 20% nas chegadas.
1. A cadeia equilibra-se. A taxa de entrada em cada estado iguala a taxa de saída, o que resulta em Pₙ = (1 − ρ)ρⁿ. Trata-se de uma distribuição geométrica sobre o comprimento da fila, em que ρ é a fração de tempo em que o servidor está ocupado. Aqui, ρ = 0,75.
  
  $P_{n} = (1 - ρ) ρ^{n}, ρ = \frac{λ}{μ} = \frac{3}{4} = 0.750$
2. A média dessa distribuição é ρ/(1 − ρ). Repare no que está no denominador: não é a capacidade ociosa em clientes por hora, mas sim a fração ociosa. São, em média, três pessoas no sistema, para um servidor que está inativo um quarto do dia.
  
  $L = n \geq 0 \sum n P_{n} = \frac{ρ}{1 - ρ} = \frac{0.750}{0.250} = 3.000$
3. Se subtrairmos a pessoa que está a ser servida (presente com probabilidade ρ), restam 2,25 à espera.
  
  $L_{q} = L - ρ = 3.000 - 0.750 = 2.250$
4. A lei de Little transforma uma população num tempo e não necessita de qualquer pressuposto sobre a distribuição. O número médio de elementos no sistema corresponde à taxa de chegada multiplicada pelo tempo médio lá despendido. É uma hora no sistema, da qual 45 minutos são passados na fila, para uma tarefa que demora 15 minutos a ser concluída.
  
  $W = \frac{L}{λ} = \frac{3.000}{3} = 1.000, W_{q} = \frac{L _{q}}{λ} = 0.750$
5. Agora, vamos aumentar λ para 3,6. A utilização passa de 0,75 para 0,90 (mais 20% de trabalho) e ρ/(1 − ρ) passa de 3 para 9.
  
  $λ = 3.6 : ρ = 0.90, L = 9; λ = 3.96 : ρ = 0.99, L = 99$
Resposta

A ferramenta imprime L = 3,000, L_q = 2,250, W = 1,000, W_q = 0,750 a 75% de utilização. A lição reside no denominador de ρ/(1 − ρ). O que determina a fila não é a quantidade de capacidade ociosa que temos, mas sim o que nos resta como fração. É essa fração que gastamos quando adicionamos carga. Mais vinte por cento de chegadas triplica a fila. Outros 10% adicionais (ρ = 0,99) transformam esse valor em 99. É por esta razão que os hospitais, as autoestradas e os controladores de disco colapsam em vez de se degradarem suavemente perante uma utilização elevada. É também por isso que dizer "estamos apenas a 90% da capacidade" não é o motivo de tranquilidade que parece.

$L = \frac{ρ}{1 - ρ} blows up at ρ = 1 : + 20% λ ⟹ \times 3 queue$
As mesmas taxas com a aleatoriedade removida 5 passos
Mantenha λ = 3 por hora e μ = 4 por hora e remova qualquer vestígio de aleatoriedade. Chegadas com exatamente vinte minutos de intervalo, e cada tarefa a demorar exatamente quinze minutos. A utilização continua a ser 0,750. Calcule a fila produzida e a que distância ρ/(1 − ρ) fica desse valor.

Abrir este problema na ferramenta
1. O cliente k chega em k/λ e, estando o servidor livre, sai em k/λ + 1/μ. O cliente seguinte chega em (k + 1)/λ. O servidor termina a tempo sempre que 1/μ ≤ 1/λ, o que corresponde a ρ ≤ 1 reescrito.
  
  $ρ = \frac{λ}{μ} = \frac{3}{4} = 0.750, \frac{1}{λ} = 0.3333 > \frac{1}{μ} = 0.250$
2. Assim, enquanto a fila for estável, ninguém espera. Temos W_q = 0 e W é apenas o tempo de serviço, ou seja, 1/μ = 0,250 horas. São quinze minutos no edifício, com todos os minutos a serem dedicados ao serviço.
  
  $\frac{k}{λ} + \frac{1}{μ} \leq \frac{k + 1}{λ} ⟺ \frac{1}{μ} \leq \frac{1}{λ} ⟺ ρ \leq 1 ⟹ W_{q} = 0$
3. A lei de Little transforma isso numa população e não necessita de nenhuma distribuição para o fazer. Temos L = λW = 3 × 0,250 = 0,750 e L_q = 0. São três quartos de um cliente, o que representa exclusivamente a fração de tempo em que o servidor está ocupado.
  
  $W = \frac{1}{μ} = 0.250, L = λW = 3 \times 0.250 = 0.750, L_{q} = λ W_{q} = 0$
4. Agora temos ρ/(1 − ρ) = 0,750/0,250 = 3,000, o que é quatro vezes a realidade. O fator não é uma coincidência destes números. O modelo M/M/1 devolve ρ/(1 − ρ), enquanto a precisão mecânica resulta em ρ. Como tal, o exagero é de 1/(1 − ρ) em qualquer utilização.
  
  $ρ 0.50 0.75 0.90 0.95 0.99 ρ / (1 - ρ) 1.000 3.000 9.000 19.000 99.000 ρ 0.500 0.750 0.900 0.950 0.990 1/ (1 - ρ) 241020100$
5. Para ρ = 0,99, esse fator é de 100. O modelo M/M/1 coloca 99 pessoas no sistema. Já um tráfego perfeitamente regular coloca 0,99.
  
  $\frac{ρ / ( 1 - ρ )}{ρ} = \frac{1}{1 - ρ}; ρ = 0.99 : 99.000 ⟷ 0.990$
Resposta

A ferramenta imprime W = 0,250 e a lei de Little converte esse valor em L = 0,750, contra uma previsão de 3,000 no modelo M/M/1 (um erro de +299,6%). A fila nunca esteve lá. O precipício de ρ do primeiro bloco de análise baseia-se inteiramente na variabilidade. Sem essa variabilidade, também não há precipício em ρ = 0,99. O que isto nos ensina fora desta página é a vantagem das marcações. Adicionar capacidade e remover variabilidade são ações que encurtam uma fila. A expressão 1/(1 − ρ) indica-nos que a segunda opção é mais compensadora exatamente onde a primeira é mais difícil de adquirir. Com uma utilização de 75%, um horário perfeitamente regular permite uma redução quádrupla e, a 99%, uma redução de cem vezes. Nenhuma clínica real alcança essa precisão mecânica, sendo que as mesmas taxas com chegadas agrupadas resultam antes em 21,482.

$L_{D / D /1} = ρ = 0.750 ⟷ L_{M / M /1} = \frac{ρ}{1 - ρ} = 3.000, \frac{L _{M / M /1}}{L _{D / D /1}} = \frac{1}{1 - ρ} = 4$

Referências (1)

Insight block 3 — how little L = λW assumes: J. D. C. Little, "A Proof for the Queuing Formula: L = λW." Operations Research 9(3), 383–387, 1961.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.