Filas Markovianas

Uma fila markoviana possui chegadas de Poisson e tempos de serviço exponenciais, tornando o número de clientes uma cadeia de Markov de tempo contínuo cujo equilíbrio pode ser resolvido explicitamente.

Definition

Uma fila markoviana é um sistema de serviço no qual os clientes chegam de acordo com um processo de Poisson e requerem tempos de serviço exponenciais independentes, de modo que o número no sistema evolui como uma cadeia de Markov de tempo contínuo de nascimento-morte com distribuições explícitas de estado estacionário e tempo de espera.

Scope

Este tópico abrange a notação de Kendall para sistemas de filas, a fila M/M/1 de servidor único e sua distribuição estacionária geométrica, sistemas M/M/c e de perda com múltiplos servidores, as fórmulas de Erlang B e C, estabilidade e intensidade de tráfego, e a derivação do comprimento médio da fila, tempo de espera e quantidades de período de ocupação a partir do processo subjacente de nascimento-morte.

Core questions

• Como a fila M/M/1 surge como um processo de nascimento-morte e qual é a sua distribuição estacionária?
• Que condição sobre a intensidade de tráfego garante que a fila seja estável?
• Como o comprimento médio da fila e o tempo de espera são obtidos, e como a lei de Little é aplicada?
• Como múltiplos servidores e capacidade finita alteram as fórmulas de Erlang?

Key theories

Distribuição estacionária e estabilidade M/M/1

O número em uma fila M/M/1 tem uma distribuição estacionária geométrica com parâmetro igual à intensidade de tráfego, a razão entre a taxa de chegada e a taxa de serviço, e a fila é estável precisamente quando essa razão é menor que um.

Fórmulas de perda e atraso de Erlang

Para sistemas multi-servidor, a fórmula de Erlang B fornece a probabilidade de bloqueio em um sistema de perda e a fórmula de Erlang C fornece a probabilidade de espera em um sistema de atraso, ambas derivadas das equações de balanço de nascimento-morte e centrais para o planejamento de capacidade.

Clinical relevance

As filas markovianas são os modelos fundamentais para dimensionar grupos de troncos telefônicos, equipes de call center, fazendas de servidores e balcões de atendimento, onde as fórmulas de Erlang traduzem a carga oferecida e os níveis de serviço alvo no número de servidores necessários.

History

Erlang derivou as fórmulas de perda e atraso para o tráfego telefônico entre 1909 e 1917, Kendall introduziu a notação sistemática de chegada/serviço/servidor e a análise de cadeia incorporada em 1953, e o tratado de Kleinrock na década de 1970 aplicou a teoria a redes de computadores e comunicação.

Key figures

• Agner Krarup Erlang
• David Kendall
• Leonard Kleinrock

Seminal works

• kleinrock1975

Frequently asked questions

O que significa M/M/1?

Na notação de Kendall, o primeiro M denota chegadas Markovianas (Poisson), o segundo M denota tempos de serviço exponenciais, e o 1 denota um único servidor.

Quando uma fila Markoviana é estável?

Quando a intensidade de tráfego, a taxa de chegada dividida pela taxa total de serviço, é menor que um; caso contrário, a fila cresce indefinidamente e nenhuma distribuição estacionária existe.