Discrete Time Event Simulation
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 = \frac{-1}{\lambda} \cdot ln(U)$$
onde U é um número aleatório gerado uniformemente no intervalo (0,1).
Um dos fundamentos da teoria de filas é a Lei de Little, dada pela fórmula: \[ E[N] = \lambda \cdot 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.
O modelo é considerado estável somente se \(\lambda < \mu\). 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:
Sabendo que, a cada \(1/\lambda\) unidades de tempo um novo cliente chega, e a cada \(1/\mu\) unidades de tempo um atendimento é finalizado, temos que:
$$\text{Tempo médio entre as chegadas} = \frac{1}{\lambda} $$ $$\text{Tempo médio de atendimento} = \frac{1}{\mu} $$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 \( \rho < 1 \) para que a fila seja estável, caso contrário ela crescerá indefinidamente. A utilização é dada pela fórmula: $$\rho = \frac{\lambda}{\mu}$$
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.
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.
Em um modelo estável, isto é, \(\rho < 1\), a probabilidade de haver exatamente \(n\) clientes no sistema é denotada por \(P_n\). Essa probabilidade segue uma distribuição geométrica e pode ser expressa como:
$$ P_n = (1 - \rho) \cdot \rho^n$$Para uma distribuição discreta, o valor esperado é dado pela soma ponderada das probabilidades de cada estado:
$$E[N] = \sum\limits_{n=0}^\infty n \cdot P_n$$Substituímos \( P_n = (1 - \rho) \cdot \rho^n \) na equação:
$$E[N] = \sum\limits_{n=0}^\infty n \cdot (1 - \rho) \cdot \rho^n $$ $$E[N] = (1 - \rho) \cdot \sum\limits_{n=0}^\infty n \cdot \rho^n $$Agora, precisamos calcular a soma \( \sum_{n=0}^{\infty} n \cdot \rho^n \):
$$\sum\limits_{n=0}^\infty n \cdot \rho^n = \frac{\rho}{(1-\rho)^2} $$Substituindo o resultado encontrado:
$$E[N] = \cancel{(1 - \rho)} \cdot \frac{\rho}{\cancel{(1-\rho)^2}} $$Portanto,
$$E[N] = \frac{\rho}{1-\rho} $$
Assim, podemos aplicar a Lei de Little para encontrar \(E[W]\):
$$ E[N] = \lambda \cdot E[W]$$Substituindo \(E[N]\) pela fórmula encontrada:
$$\frac{\rho}{1-\rho} = \lambda \cdot E[W]$$Substituindo \(\rho = \frac{\lambda}{\mu}\):
$$\frac{\frac{\lambda}{\mu}}{1-\frac{\lambda}{\mu}} = \lambda \cdot E[W]$$ $$\frac{\lambda}{\mu - \lambda} = \lambda \cdot E[W]$$Dividimos ambos os lados por \(\lambda\):
$$\frac{\cancel{\lambda}}{\cancel{\lambda}\cdot(\mu - \lambda)} = \frac{\cancel{\lambda} \cdot E[W]}{\cancel{\lambda}}$$Portanto, o tempo médio de espera no sistema é definido por:
$$E[W] = \frac{1}{\mu - \lambda}$$
Calcule \(E[N]\) e \(E[W]\) através das fórmulas:
$$E[N] = \frac{\rho}{1-\rho}$$
$$E[W] = \frac{1}{\mu - \lambda}$$
A taxa de chegada, ou \(\lambda\), 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 \(\mu\) ) refere-se à média de clientes que um servidor (ou sistema de atendimento) consegue processar ou atender em uma unidade de tempo.
$$\lambda = \frac{1}{\text{Tempo médio entre as chegadas}}$$
$$\mu = \frac{1}{\text{Tempo médio de atendimento}}$$
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] = \lambda \cdot E[W]$$
$$\text{Erro de Little} = \left| E[N] - \lambda \cdot E[W] \right|$$
Temos que:
Substituindo \( E[N] \) e \( E[W] \):
\[ \text{Erro de Little} = \left| \frac{\rho}{1 - \rho} - \lambda \cdot \frac{1}{\mu(1 - \rho)} \right| \] \[ \text{Erro de Little} = \left| \frac{\rho}{1 - \rho} - \frac{\lambda}{\mu(1 - \rho)} \right| \]Como \(\rho = \frac{\lambda}{\mu}\), substituímos \( \lambda = \rho \cdot \mu \) para simplificar:
\[ \text{Erro de Little} = \left| \frac{\rho}{1 - \rho} - \frac{\rho \cdot \cancel{\mu}}{\cancel{\mu}(1 - \rho)} \right| \] \[ \text{Erro de Little} = \left| \frac{\rho}{1 - \rho} - \frac{\rho}{1-\rho}\right|\]Portanto,
\[ \text{Erro de Little} =0\]
ROSS, S. M., Simulation. 4ª ed. San Diego: Academic Press, 2006.
ALLEN, Arnold O. Probability, statistics, and queueing theory: with computer science applications. 2. ed. San Diego: Academic Press, 1990.