Simulação de eventos discretos

Simulação de evento discreto.

A simulação de eventos discretos (SED) modela a operação de um sistema como uma sequência de eventos discretos no tempo. Cada evento ocorre em um determinado instante de tempo e marca uma mudança de estado no sistema. Entre eventos consecutivos, considera-se que o sistema não sofre mudança alguma, assim, a simulação pode saltar diretamente do instante de ocorrência de um evento para o próximo.

Esta forma de execução se contrasta com a simulação contínua, na qual a simulação acompanha continuamente a dinâmica no sistema ao longo do tempo, sem saltos discretos de um evento ao outro. Assim, na simulação contínua o tempo é quebrado em pequenos intervalos e o estado do sistema é avaliado de acordo com o que ocorre dentro de cada intervalo. Em contraponto, a simulação de eventos discretos não precisa simular cada fatia de tempo e, ao saltar de um evento ao outro, ela é usualmente executada com mais rapidez que sua correspondente simulação contínua.

Um técnica conhecida para execução de simulações de eventos discretos é o "Método das três fases" . Nesta abordagem, a primeira fase sempre avança o relógio para o próximo evento a ocorrer, respeitando a ordem cronológica de eventos (chamados de eventos do tipo A). A segunda fase é a execução de todos os eventos que incondicionalmente ocorrem no instante atual (chamados de eventos do tipo B). A terceira fase é a execução de todos os eventos que condicionalmente ocorrem no tempo atual (chamados eventos do tipo C). O método das três fases é um refinamento da abordagem baseada em eventos, na qual os eventos simultâneos são ordenados de modo a tornar mais eficiente o uso dos recursos computacionais. O método das três fases é utilizado por diversos pacotes comerciais de simulação, mas do ponto de vista do usuário, tais especificidades técnicas do método de execução são geralmente ocultas.

Exemplo

Um exercício comum para se entender como são construídos modelos de simulação de eventos discretos é a modelagem de um sistema de fila de atendimento, tal como a fila formada por clientes que chegam em um agência bancária e esperam por atendimento no caixa. Neste caso, as entidades do sistema são os clientes que buscam atendimento e os eventos são: a chegada de um novo cliente, o início do atendimento no caixa e o fim do atendimento (equivalente a saída do cliente do sistema).  Os estados do sistema, que são passíveis de alteração pelos eventos anteriores, são: o número de clientes na fila de atendimento (um número inteiro entre 0 e n) e o estado do caixa (livre ou ocupado). As variáveis aleatórias que devem ser identificadas para modelar a componente estocástica do sistema são: o tempo entre chegadas sucessivas de clientes e o tempo de serviço no caixa de atendimento.

Componentes de uma simulação de eventos discretos

Além da lógica do que acontece quando ocorrem eventos no sistema, a simulação de eventos discretos ainda inclui:

Estado

Cada estado do sistema é representado por um conjunto de variáveis que capturam as suas propriedades mais significativas. O comportamento dos estados ao longo do tempo, S(t) pode ser matematicamente representado por uma função degrau cujos valores mudam em resposta à execução dos eventos discretos do próprio sistema.

Relógio

A simulação deve manter controle do tempo atual de simulação, independentemente da unidade de medida de tempo utilizada pelo sistema sendo modelado. Na simulação de eventos discretos, em contraponto à denominada simulação em tempo real, o relógio "salta" entre os instantes de ocorrência dos eventos, ou seja, de outra forma, o relógio avança para o instante de início do próximo evento enquanto a simulação é executada.

Lista de eventos

Usualmente, a simulação mantém ao menos uma lista de eventos pendentes, que representa os eventos que ainda devem ser executados. Um evento é descrito pelo seu instante de ocorrência no tempo e um tipo, indicando o código que será usado para simular o evento. É comum que o código do evento seja parametrizado e, neste caso, a descrição do evento também conterá parâmetros para o seu código de execução.

Quando os eventos são instantâneos, as atividades que se estendem ao longo do tempo são modeladas como sequências de eventos. Alguns ambientes de simulação permitem que o instante de execução de um evento possa ser especificado por um intervalo identificado pelo instante de início e fim do evento.

O conjunto de eventos aguardando por execução são usualmente organizados como uma fila com prioridade, ordenada cronologicamente. Isto é, independentemente da ordem com que os eventos são adicionados ao conjunto de eventos, eles são removidos em ordem estritamente cronológica. Diversos algorítimos genéricos de busca e ordenação de filas com prioridade se provaram eficazes para a simulação de eventos discretos, tais como o splay tree, skip lists, calendar queues, e ladder queues.

Tipicamente, os eventos são agendados para execução de modo dinâmico, ao longo da própria da simulação. Por exemplo, no exemplo do banco proposto anteriormente, o evento "chegada do cliente" no instante t poderia, caso a fila de clientes esteja vazia e o caixa livre neste instante,  incluir a criação dos eventos subsequentes "saída do cliente" no instante t+s, onde s é um tempo gerado a partir da distribuição do tempo de serviço no caixa.

Geradores de números aleatórios

Uma simulação usualmente necessita gerar variáveis aleatórias de vários tipos para a sua execução e que dependem dos fenômenos em estudo no sistema real. O processo de geração é feito por um ou mais geradores de números Pseudo-aleatórios.

Um dos problemas com as distribuições probabilísticas utilizadas para geração de números aleatórios, é que muitas vezes desconhece-se como são tais distribuições no regime estacionário. Nestes casos, os eventos iniciais não terão comportamento representativo das distribuições reais (em regime estacionário). Tal tipo de situação pode ser contornada aplicando-se alguma técnica de bootstrapping no modelo de simulação, de modo que dedica-se atenção especial para que o conjunto inicial de eventos ocorra entre intervalos de tempo os mais realistas quanto possível. Como tais eventos devem programar os eventos subsequentes, a distribuição do intervalo de ocorrência entre os eventos aproxima-se do seu comportamento no estado estacionário (ou regime permanente). No processo de extração de estatísticas dos parâmetros de saída do modelo de simulação, deve-se ignorar os eventos que ocorrem antes de que o estado estacionário seja atingido ou mesmo, deve-se executar a simulação por um tempo longo o suficiente de modo que as condições iniciais do sistema seja dissipadas pelo estado do sistema ao atingir o regime permanente (Esse uso do termo bootstrapping pode ser contrastado com a sua utilização tanto na estatística,  quanto na computação.)

Estatísticas

Uma simulação normalmente estima as principais estatísticas de interesse do comportamento do sistema. No caso do banco, por exemplo, uma estatística de interesse seria o tempo médio de espera por atendimento dos clientes. Em um modelo de simulação, as métricas (como a do tempo médio de espera por atendimento) são geralmente obtidas por meio de médias de replicações do modelo. Cada replicação representa uma diferente execução completa do modelo. Para se avaliar a qualidade do valor obtido, são construídos Intervalos de confiança para as estatísticas estimadas.

Condições de finalização de execução

Teoricamente, uma simulação de eventos discretos poderia ser executada para sempre. Assim, o projetista do modelo de simulação deve decidir quando a simulação deve terminar. Tipicamente, as condições de finalização são "no instante t" ou "após o processamento de um número n de eventos" ou, mais geralmente, "quando a medida estatística X atingir o valor de x".

Lógica de um simulador de eventos discretos

Um simulador de eventos discretos possui um loop principal típico:

Início

• Inicializar Condição de Término para FALSO
• Inicializar as variáveis de estado do sistema
• Inicializar o Relógio (usualmente o tempo inicial de simulação é igual a zero)
• Agendar um evento inicial (por exemplo, colocar algum evento inicial na Lista de Eventos)

Laço de execução

Enquanto (a condição de término é FALSA) execute o seguinte::

• Definir o relógio para o instante do próximo evento
• Executar o próximo evento e removê-lo da lista de eventos
• Atualizar as estatísticas

Fim

• Gerar relatórios de estatísticas

Usos comuns

Diagnóstico de problemas em processos

A simulação é uma abordagem particularmente útil para diagnosticar problemas em sistemas complexos. O livro A Meta (Teoria das Restrições) ilustra a importância de se entender os gargalos em um sistema. Somente aquelas melhorias que atuam sobre os gargalos são realmente capazes de melhorar o desempenho do sistema. Em muitas organizações, os gargalos se ocultam no excesso de estoques, no excesso de produção, na variabilidade dos processos, na variabilidade do seqüenciamento de tarefas. Ao representar com precisão o sistema real dentro de um modelo de simulação, é possível obter uma visão panorâmica de todo o sistema em estudo.

Um modelo de simulação operacional de um sistema permite ao gestor compreender processos decisivos para o seu desempenho. Uma simulação pode ser criada para incluir qualquer número de indicadores de desempenho , tais como a ocupação dos trabalhadores em cada tarefa, a taxa de entrega de produtos, a taxa de produtos rejeitados, o ciclo financeiro etc.

Aplicações no projeto e gestão de Hospitais

Em hospitais, a simulação de eventos discretos é geralmente aplicada tanto no projeto de alas hospitalares, quanto na gestão de recursos (mão-de-obra e suprimentos). No dimensionamento de alas, a simulação por ser ferramenta de apoio ao Projeto de Arquitetura, auxiliando no dimensionamento de áreas de espera, número de leitos etc. Na gestão, a simulação auxilia no dimensionamento de turnos de trabalho, equipes necessárias, estoques de suprimentos etc.

Bancada de testes de desempenho de novas políticas operacionais

Em muitas situações, metodologias comprovadas (Lean, Six Sigma, TQM etc.) não conseguem melhorar o desempenho total de um sistema de produção. Um modelo de simulação permite que o usuário compreenda e teste os impactos da aplicação de uma certa metodologia de em uma bancada de testes, identificando o impacto no desempenho do sistema antes de que a metodologia seja aplicada no sistema real.

Avaliação de decisões de investimento de capital

Veja também: métodos de Monte Carlo em finanças; finanças Corporativas #de Capital, decisões de investimento e #Quantificar a incerteza.

A simulação é também utilizada para modelar o potencial de retorno de investimentos de capital. Por meio de modelos de investimentos,gestores podem tomar decisões cientificamente embasadas e avaliar cenários alternativos de investimentos.

Simuladores de redes de computadores

A simulação de eventos discretos é utilizada para simular novos protocolos de rede de computadores em diferentes cenários de tráfego antes da implantação.

Veja também

Técnicas de modelagem de sistemas:

• Máquina de estados finitos e um caso especial, a cadeia de Markov
• Processo estocástico
• Teoria das Filas
• Especificação de sistemas de eventos discretos

Técnicas computacionais:

• Experimentos computacionais
• Modelagem computacional
• Método de Monte Carlo
• Método da redução de variância
• Gerador de números pseudoaleatórios

Software:

• Lista de softwares de simulação (em inglês)
• Lista de software de simulação de eventos discretos ( em inglês)
• SimPy: Simulation in Python

Disciplinas:

• Pesquisa Operacional
• Engenharia de Produção
• Engenharia Industrial
• Logística
• Simulação de redes

Publicações:

• Publicações em simulação (em inglês)

Leitura complementar

• Chwif, Leonardo; Medina, Afonso C. Modelagem e Simulação de Eventos Discretos: Teoria e Aplicações. 4ª edição. São Paulo: Elsevier Brasil, 2014. 320 p. ISBN 978-8535279320.
• Myron H. MacDougall (1987). Simulating Computer Systems: Techniques and Tools. MIT Press. 
• William Delaney; Erminia Vaccari (1988). Dynamic Models and Discrete Event Simulation. Dekker INC. 
• Roger W. McHaney (1991). Computer Simulation: A Practical Perspective. Academic Press. 
• Michael Pidd (1998). Computer simulation in management science – fourth edition. Wiley. 
• A, Alan Pritsker, Jean J. O'Reilly (1999). Simulation with Visual SLAM and AweSim. Wiley.  CS1 maint: Multiple names: authors list (link)
• Averill M. Law; W. David Kelton (2000). Simulation modeling and analysis – third edition. McGraw–Hill. 
• Bernard P. Zeigler; Herbert Praehofer; Tag Gon Kim (2000). Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems – second edition. Academic Press. 
• Jerry Banks; John Carson; Barry Nelson; David Nicol (2005). Discrete-event system simulation – fourth edition. Pearson. 
• James J. Nutaro (2010). Building software for simulation: theory and algorithms, with applications in C++. Wiley.