Simulação via Eventos Discretos

Discrete Time Event Simulation

Fila M/M/1

Os elementos chave em uma simulação por eventos discretos são variáveis e eventos. Para executar a simulação, é necessário manter o controle de certas variáveis. No geral, existem três tipos de variáveis que devemos manipular:

Considere um serviço de atendimento, onde os clientes chegam para serem atendidos. Se houver fila, eles esperam sua vez até que o servidor (o atendente) esteja disponível. O sistema funciona sob uma política FIFO (First In, First Out), ou seja, o primeiro cliente a chegar é o primeiro a ser atendido. Apenas um cliente pode ser atendido por vez, e os outros aguardam.

É o sistema de filas mais simples, onde existe um único servidor, já que apenas um cliente pode ser atendido por vez. Em modelos de fila M/M/1 em que há apenas um servidor, consideramos que os clientes chegam de acordo com um processo de Poisson e os tempos de serviço têm uma distribuição exponencial. Na simulação desse modelo, utilizamos a seguinte função para a geração dos tempos:

T=1λln(U)

onde U é um número aleatório gerado uniformemente no intervalo (0,1).

Lei de Little

Um dos fundamentos da teoria de filas é a Lei de Little, dada pela fórmula: E[N]=λE[W] Essa fórmula se aplica a qualquer sistema em equilíbrio, onde os clientes chegam, passam certo tempo, são atendidos e partem.


Medidas de Desempenho

O modelo é considerado estável somente se λ<μ. Se, em média, as chegadas ocorrem mais rapidamente que as conclusões dos serviços, a fila se tornará indefinidamente longa.

A seguir foram calculadas medidas de desempenho com base em cada simulação realizada, cada gráfico conta com uma legenda onde estão classificadas as simulações e seus respectivos parâmetros de execução:

Em algumas medidas, existem campos que podem ser utilzados para validar o desempenho do sistema.

1. Utilização/Ocupação (ρ)

Sabendo que, a cada 1/λ unidades de tempo um novo cliente chega, e a cada 1/μ unidades de tempo um atendimento é finalizado, temos que:

Tempo médio entre as chegadas=1λ Tempo médio de atendimento=1μ

A utilização ou ocupação do sistema mede a proporção média do tempo em que o servidor fica ocupado em relação ao tempo total de operação, é necessário que ρ<1 para que a fila seja estável, caso contrário ela crescerá indefinidamente. A utilização é dada pela fórmula: ρ=λμ

10k20k30k40k50k60k70k80k90k100k0.850.90.951
Parâmetros1: (P1:0.25, P2:0.2475) = 99%2: (P1:0.5, P2:0.45) = 90%3: (P1:0.2, P2:0.17) = 85%4: (P1:0.6, P2:0.57) = 95%Utilização (Ocupação)TempoOcupação

Valide a utilização:

ρ =


2. Número máximo de elementos na fila

Este gráfico mostra o número máximo de elementos na fila durante a simulação. O número de elementos pode variar dependendo da taxa de chegada de novos elementos e da capacidade do sistema de processá-los.

10k20k30k40k50k60k70k80k90k100k0100200300
Parâmetros1: (P1:0.25, P2:0.2475) = 99%2: (P1:0.5, P2:0.45) = 90%3: (P1:0.2, P2:0.17) = 85%4: (P1:0.6, P2:0.57) = 95%Máximo de FilaTempoFila Máxima

3. Média de elementos no sistema (E[N]) & Tempo médio de espera (E[W])

A média de elementos no sistema reflete quantos itens, em média, estão presentes no sistema a qualquer instante de tempo. Já o tempo médio de espera representa o tempo que um elemento permanece no sistema.

10k20k30k40k50k60k70k80k90k100k020406080
Parâmetros1: (P1:0.25, P2:0.2475) = 99%2: (P1:0.5, P2:0.45) = 90%3: (P1:0.2, P2:0.17) = 85%4: (P1:0.6, P2:0.57) = 95%E[N] e E[W]TempoE[N] & E[W]

Validação E[N] e E[W]:

Em um modelo estável, isto é, ρ<1, a probabilidade de haver exatamente n clientes no sistema é denotada por Pn. Essa probabilidade segue uma distribuição geométrica e pode ser expressa como:

Pn=(1ρ)ρn

Para uma distribuição discreta, o valor esperado é dado pela soma ponderada das probabilidades de cada estado:

E[N]=n=0nPn

Substituímos Pn=(1ρ)ρn na equação:

E[N]=n=0n(1ρ)ρn E[N]=(1ρ)n=0nρn

Agora, precisamos calcular a soma n=0nρn:

n=0nρn=ρ(1ρ)2

Substituindo o resultado encontrado:

E[N]=(1ρ)ρ(1ρ)2

Portanto,

E[N]=ρ1ρ

Assim, podemos aplicar a Lei de Little para encontrar E[W]:

E[N]=λE[W]

Substituindo E[N] pela fórmula encontrada:

ρ1ρ=λE[W]

Substituindo ρ=λμ:

λμ1λμ=λE[W] λμλ=λE[W]

Dividimos ambos os lados por λ:

λλ(μλ)=λE[W]λ

Portanto, o tempo médio de espera no sistema é definido por:

E[W]=1μλ

Calcule E[N] e E[W] através das fórmulas:

E[N]=ρ1ρ

E[W]=1μλ


4. Taxa de chegada de elementos no sistema (λ) & Taxa de atendimento (μ)

A taxa de chegada, ou λ, representa o número de novos elementos que chegam ao sistema por unidade de tempo, é representada pelo inverso do tempo médio entre as chegadas. Já a taxa de atendimento (denotada como μ ) refere-se à média de clientes que um servidor (ou sistema de atendimento) consegue processar ou atender em uma unidade de tempo.

λ=1Tempo médio entre as chegadas

μ=1Tempo médio de atendimento

10k20k30k40k50k60k70k80k90k100k23456
Parâmetros1: (P1:0.25, P2:0.2475) = 99%2: (P1:0.5, P2:0.45) = 90%3: (P1:0.2, P2:0.17) = 85%4: (P1:0.6, P2:0.57) = 95%TempoTaxas

5. Erro de Little

O Erro de Little verifica a validade da fórmula de Little, que estabelece uma relação entre o número médio de clientes no sistema, o tempo médio de espera e a taxa de chegada de clientes. Um erro muito alto pode indicar inconsistências na simulação. Para garantir consistência, o erro de Little deve ser próximo de 0.

Lei de Little: E[N]=λE[W]

Erro de Little=|E[N]λE[W]|

10k20k30k40k50k60k70k80k90k100k−1−0.500.51
Parâmetros1: (P1:0.25, P2:0.2475) = 99%2: (P1:0.5, P2:0.45) = 90%3: (P1:0.2, P2:0.17) = 85%4: (P1:0.6, P2:0.57) = 95%Erro de LittleTempoErro

Validação do Erro de Little:

Temos que:

  • ρ=λμ
  • E[N]=ρ1ρ
  • E[W]=1μλ=1μ(1ρ)
Erro de Little=|E[N]λE[W]|

Substituindo E[N] e E[W]:

Erro de Little=|ρ1ρλ1μ(1ρ)| Erro de Little=|ρ1ρλμ(1ρ)|

Como ρ=λμ, substituímos λ=ρμ para simplificar:

Erro de Little=|ρ1ρρμμ(1ρ)| Errode Little=|ρ1ρρ1ρ|

Portanto,

Erro de Little=0


Referências

  1. ROSS, S. M., Simulation. 4ª ed. San Diego: Academic Press, 2006.

  2. ALLEN, Arnold O. Probability, statistics, and queueing theory: with computer science applications. 2. ed. San Diego: Academic Press, 1990.