ÍNDICE
1.
INTRODUÇÃO......................................................................................................................... 3
2.
O QUE É SIMULAÇÃO .......................................................................................................... 3
2.1.
3.
QUANDO A SIMULAÇÃO É UMA FERRAMENTA IMPORTANTE .............................................. 4
PRINCÍPIOS DA SIMULAÇÃO DE SED’S ......................................................................... 5
3.1.
CONCEITOS BÁSICOS DA SIMULAÇÃO.................................................................................... 5
3.2.
CALENDÁRIO DE EVENTOS .................................................................................................... 6
3.3.
O ALGORITMO PARA A SIMULAÇÃO DE SED ....................................................................... 8
3.4.
UM EXEMPLO DE SIMULAÇÃO DE SED................................................................................ 11
3.4.1.
SIMULAÇÃO PARA O ATENDIMENTO DE CINCO CLIENTES ................................................... 14
3.4.2.
ANÁLISE DOS DADOS OBTIDOS DA SIMULAÇÃO .................................................................. 18
4.
LINGUAGENS USADAS NA SIMULAÇÃO DE SED....................................................... 18
5.
FATORES QUE DEVEM SER OBSERVADOS NA SIMULAÇÃO ................................ 20
5.1.
GERAÇÃO DE NÚMEROS ALEATÓRIOS ................................................................................ 20
5.1.1.
5.2.
6.
TRANSFORMAÇÃO INVERSA................................................................................................ 21
ESTIMATIVA DE PARÂMETROS ............................................................................................ 22
CONCLUSÃO......................................................................................................................... 23
ANEXO A. SIMULAÇÃO DE SED USANDO O ARENA ........................................................ 24
A.1 O ARENA ................................................................................................................................... 24
A.2 SIMULAÇÃO DE UMA CÉLULA DE MANUFATURA ................................................................... 24
A.2.1 MODELAGEM DA CÉLULA PARA A SIMULAÇÃO NO ARENA ................................................... 25
A.2.1.1 Modelagem das Peças ......................................................................................................... 25
A.2.1.2 Modelagem das Máquinas................................................................................................... 29
A.2.1.3 Modelagem dos AGVs ........................................................................................................ 30
A.2.1.4 Modelagem dos Percursos dos AGVs ................................................................................. 31
A.2.1.5 Implementação das Restrições ............................................................................................ 31
A.2.1.6 Conclusões .......................................................................................................................... 32
REFERÊNCIAS BIBLIOGRÁFICAS ......................................................................................... 33
Simulação de Sistemas a Eventos Discretos
2
ÍNDICE DE FIGURAS
Figura 1 - Autômato representativo do funcionamento de uma máquina ............... 6
Figura 2 - Diagrama de Blocos do Algoritmo de Simulação de SED...................... 9
Figura 3 - Exemplo para a simulação - Fila em uma agência bancária................ 11
Figura 4 - Gráfico da Transformação Inversa....................................................... 21
Figura 5 - Célula flexível de manufatura............................................................... 25
Figura 6 - Fluxo de Montagem das Peças............................................................ 25
Figura 7 - Definição da Seqüência da Peça 1 (quando esta passa por M2) ........ 26
Figura 8 - Definição dos Tipos de Peça ............................................................... 27
Figura 9 - Atribuição de desenhos às peças ........................................................ 27
Figura 10 - Caixa de diálogo do Bloco Arrive ....................................................... 28
Figura 11 - Determinando os atributos da entidade ............................................. 29
Figura 12 - Caixa de diálogo do bloco Server ...................................................... 29
Figura 13 - Caixa de Diálogo do Bloco Transporter, definição do AGV R1 .......... 30
Figura 14 - Caixa de Diálogo NetworkLink ........................................................... 31
Figura 15 - Diagrama de blocos da chamada de transporte na M1...................... 32
Simulação de Sistemas a Eventos Discretos
1.
3
Introdução
No estudo de sistemas dinâmicos, o primeiro objetivo é a modelagem. Um
modelo é formado por um conjunto de equações que descrevem o
comportamento do sistema, para que dessa forma possa ser encontrada sua
resposta a uma dada entrada. Acontece que, muitas vezes os sistemas com os
quais se trabalham não admitem simplificações, de modo a facilitar a obtenção
analítica dessa resposta, ou os sistemas podem ser tão complexos que não
possuem uma solução analítica para suas equações. O modelo matemático ainda
é válido, o problema é que normalmente não se dispõe de ferramentas para
resolver as equações que o compõe.
Neste conjunto de sistemas se encontram os Sistemas a Eventos Discretos
(SED), cujas soluções analíticas para seus modelos matemáticos são muito
difíceis de encontrar. Para tais sistemas um mecanismo empregado para o seu
estudo é a Simulação, que vem a ser um processo no qual um sistema é
resolvido numericamente, e os dados obtidos por esse processo são empregados
para estimar o comportamento de várias variáveis de interesse do sistema.
2.
O que é Simulação
Simulação á a imitação da operação de um processo ou sistema ao longo do
tempo. Seja feita manualmente ou através de um computador, a simulação
envolve a geração de uma história artificial do sistema, e a observação desta
história permite criar inferências a respeito das características de operação do
sistema real.
A observação do sistema à medida que ele evolui ao longo do tempo é
estudada através do desenvolvimento de um modelo. Este modelo geralmente é
obtido fazendo-se uma série de considerações a respeito do comportamento do
sistema. Estas considerações são expressas através de relações matemáticas,
lógicas e simbólicas entre as entidades, ou outros componentes do sistema. Uma
vez desenvolvido e validado, um modelo pode ser usado para investigar uma
grande variedade de perguntas tipo “ e se ” sobre o sistema real, ou seja,
mudanças no sistema poderiam ser primeiro simuladas com o objetivo de se
prever o impacto destas mudanças no sistema real. A simulação também pode
ser usada para estudar sistemas durante a fase de desenvolvimento do mesmo,
Simulação de Sistemas a Eventos Discretos
4
antes mesmo de terem sido construídos fisicamente. Portanto, a simulação pode
ser usada tanto para prever o efeito de uma alteração em sistemas existentes, ou
como uma ferramenta de desenvolvimento que permite prever a performance de
novos sistemas sob um conjunto variado de circunstâncias.
2.1. Quando a Simulação é uma Ferramenta Importante
A disponibilidade de linguagens de simulação para problemas específicos, o
desenvolvimento da computação aliado ao barateamento de sua utilização, e os
avanços na metodologia de simulação fizeram da simulação a mais utilizada e
aceita ferramenta em pesquisa de operações e análise de sistemas. A simulação
pode ser usada com os seguintes propósitos:
a) Possibilitar o estudo e a experimentação das interações internas de um
sistema complexo, ou de um subsistema dentro de um sistema maior;
b) Alterações das informações, organização e nas condições de um sistema
podem ser simuladas, e o efeito destas alterações podem ser observadas
no comportamento do modelo;
c) O conhecimento adquirido no desenvolvimento de um modelo para a
simulação pode ser de grande importância para sugerir melhorias no
sistema estudado;
d) Através de mudanças nos valores de entradas da simulação e observando
a resposta do sistema, podemos reconhecer as variáveis mais importantes
do sistema e como elas interagem;
e) A simulação pode ser usada como meio pedagógico para reforçar o
aprendizado da metodologia para obtenção das respostas analíticas;
f) A animação permite visualizar a operação do sistema e desta forma
podemos estudar a planta; e
g) Os sistemas modernos são tão complexos que as interações entre seus
subsistemas só podem ser analisadas através de simulações.
Existem inúmeros campos de aplicação da simulação, entre eles podemos
citar:
a) Sistemas de Manufatura;
Simulação de Sistemas a Eventos Discretos
5
b) Logística;
c) Transporte;
d) Sistemas de Distribuição;
e) Sistemas biológicos, etc.
3.
Princípios da Simulação de SED’s
3.1. Conceitos básicos da simulação
Antes de ser dar início ao estudo da simulação de SED, deve-se ter em mente
os seguintes conceitos:
a) Entidade: é o objeto de interesse no sistema. Pode ser uma peça em um
sistema de manufatura, um cliente ou um documento.
b) Atributo: é uma propriedade da entidade que é importante no processo de
simulação. São exemplos de atributo o tipo de peça, o saldo bancário de
um cliente em um banco, tipo de percurso a ser percorrido, etc. Vale a
pena salientar que os atributos não são imutáveis em uma entidade, eles
podem variar à medida que a entidade percorre todos os pontos do
sistema, por exemplo, o valor agregado a uma entidade pode aumentar
depois da peça passar por cada uma das etapas da linha de produção.
c) Processos: são as operações às quais estão submetidas às entidades, por
exemplo, a furação de uma peça, o depósito em uma conta. Algumas
vezes são necessários Recursos para a execução de algum tipo de
trabalho em uma entidade, e tais recursos podem ou não impor atrasos às
entidades durante o seu fluxo pelo sistema.
d) Recurso: elemento que executa o trabalho em uma entidade. Pode ser
uma máquina, um atendente de uma loja, etc.
e) Atrasos: são impostos à entidade pelo sistema. Podem ser atrasos devido
à execução de um processo ou atrasos em virtude da espera da entidade
em uma fila até que determinado(s) recurso(s) esteja(m) livre(s). No caso
de uma fila por exemplo, o cliente deverá aguardar até que vendedor
atenda todas as pessoas que chegaram antes dela.
f) Estado do Sistema: é a coleção das variáveis necessárias para descrever
o sistema em qualquer tempo, ou seja, é o seu retrato. Por exemplo, em
Simulação de Sistemas a Eventos Discretos
6
uma fila a variável de estado é o número de entidades que nela se
encontra (0, 1, ou 2) ou um recurso tipo atendente, o estado será em que
situação se encontra o recurso (ocupado, ocioso, ou não disponível).
g) Evento: é uma ação instantânea que pode alterar o estado do sistema. Por
exemplo, são eventos em um sistema: a chegada do cliente, o início de um
trabalho de uma máquina.
3.2. Calendário de Eventos
Para que se possa pensar na simulação de um SED, o sistema deve ser
modelado por meio de autômatos que irão representar o seu comportamento a
medida que os eventos vão ocorrendo, tais eventos possuem natureza
estocástica.
Os SEDs são sistemas compostos por variáveis randômicas e tais entradas
nos levam a respostas randômicas do sistema. Porém para cada um dos estados
do sistema existe um conjunto de eventos factíveis, Γ(x ) , este conjunto de
eventos é a união dos eventos controláveis e não controláveis para este
determinado estado.
Para exemplificar, seja o autômato que representa uma máquina mostrado a
seguir.
Figura 1 - Autômato representativo do funcionamento de uma máquina
Simulação de Sistemas a Eventos Discretos
7
Seus estados e os eventos são apresentados a seguir:
Estado
Descrição
0
Máquina ociosa
1
Máquina em operação
2
Máquina quebrada
Evento
Descrição
Tipo de Evento
S
Início da operação da máquina
Controlável
E
Fim da operação da máquina
Não-Controlável
B
Máquina quebra
Não-Controlável
R
Máquina recuperada
Controlável
O conjunto de eventos factíveis denotado por Γ(x ) , onde x é o estado do
sistema para o autômato apresentado será:
Estado
Γ(x )
0
{S}
1
{E,B}
2
{R}
Para a simulação de um SED, emprega-se para cada um dos estados uma
lista que será composta por todos seus eventos factíveis, a qual é chamada de
Calendário de eventos, este calendário de eventos é a principal estrutura de
dados de um simulador de SED.
Para dar a natureza estocástica aos SED deve-se atribuir a cada um dos
eventos pertencentes ao calendário um número aleatório, este número representa
o intervalo de tempo que transcorrerá desde o instante de tempo atual até o
instante de tempo onde este evento poderá ocorrer. Depois de atribuídos estes
números aos eventos, o calendário é ordenado na ordem crescente de ocorrência
de eventos.
Por exemplo, suponha-se que a máquina apresentada anteriormente esteja no
estado 1, portanto, os eventos factíveis são B e E, e que o instante de tempo em
que se encontra o sistema seja t = 10 s. A simulação deverá gerar os intervalos
Simulação de Sistemas a Eventos Discretos
8
de tempo para a ocorrência de E e B, que poderia dar como retorno os valores 3 e
4 para os eventos B e E respectivamente. De posse desses dados, o calendário
de eventos para a máquina no estado 1 ficaria da seguinte forma:
Calendário de Eventos
Evento
t’ = t + ∆t
B
10 + 3 = 13
E
10 + 4 = 14
Estando o calendário já ordenado pela ordem crescente de instante de tempo
de ocorrência de eventos pode-se concluir que o próximo evento a ocorrer será a
quebra da máquina aos 13 s. Este evento levará a máquina para o estado 2,
então, dando prosseguimento à simulação deve-se retirar do calendário todos os
eventos não factíveis para este estado, inserir os eventos factíveis, gerar números
aleatórios para os intervalos de tempo para a ocorrência dos eventos e então
repetir todo o processo empregado para a máquina quando ela se encontrava no
estado 1.
3.3. O Algoritmo para a Simulação de SED
O algoritmo para a simulação de SED é apresentado na forma de diagrama de
blocos a seguir:
Simulação de Sistemas a Eventos Discretos
9
Figura 2 - Diagrama de Blocos do Algoritmo de Simulação de SED
Ao se iniciar a simulação do sistema é chamada a rotina de inicialização que
faz com que o sistema assuma um estado inicial x0 e atribui um valor t0
(usualmente 0 (zero)) para o instante inicial da simulação. Na inicialização
também é feita a chamada da rotina que gera os intervalos de tempo aleatórios
para os eventos factíveis para o estado inicial, de posse desses intervalos de
tempo e dos eventos factíveis, o calendário de eventos é montado em ordem
crescente de instantes de ocorrência de eventos.
Montado o calendário de eventos, constata-se que o próximo evento a ocorrer
será o e1, no instante de tempo t1. Assim, o processo de simulação será uma
repetição contínua dos seis passos seguintes:
Passo 1: Remover o par (e1, t1) do calendário de eventos;
Simulação de Sistemas a Eventos Discretos
10
Passo 2: Atualizar o instante de simulação com o instante de ocorrência do
evento e1, ou seja, t = t1;
Passo 3: Atualizar o estado do sistema de acordo com a função de transição
x’ = f (x,e1);
Passo 4: Apagar do calendário de eventos todos os eventos infactíveis para o
novo estado x’;
Passo 5: Adicionar ao calendário de eventos qualquer evento factível para o
novo estado do sistema que ainda não tenha sido agendado. O instante de
ocorrência dos eventos inseridos nesta etapa do processo será a soma do
tempo do sistema atualizado, obtido no etapa 2 deste processo, com o
valor obtido para os intervalos de tempo calculados pelo gerador de
números aleatórios; e
Passo 6: Reordenar o calendário na ordem crescente de instantes de
ocorrência de eventos.
Para dar suporte a este algoritmo deve existir toda uma estrutura que será
responsável por coletar todos os dados e calcular as variáveis de interesse para a
simulação. Todos os componentes são listados a seguir:
a) Estados: uma lista onde todas as variáveis de estado são
armazenadas;
b) Tempo: uma variável onde o tempo de simulação é armazenado;
c) Calendário de Eventos: uma lista onde todos os eventos agendados
são armazenados juntamente com o instante de ocorrência dos
mesmos;
d) Registradores de dados: variáveis e/ou listas onde os dados são
armazenados para cálculos de estimativas;
e) Rotina de Inicialização: inicializa toda a estrutura de dados da
simulação;
f) Rotina de atualização de tempo: identifica o próximo evento a ocorrer
e avança o tempo da simulação para o instante de ocorrência deste
evento;
Simulação de Sistemas a Eventos Discretos
11
g) Rotina de geração de intervalos de tempo aleatórios: transforma os
números gerados aleatoriamente pelo computador em intervalos de
tempo de ocorrência para os eventos do sistema;
h) Rotina de geração de relatório: computa todos os valores relevantes
da simulação baseada em todos os dados coletados durante a
simulação; e
i) Programa principal: responsável pela coordenação de todos as rotinas
e estruturas de dados que compõe a simulação.
3.4. Um exemplo de simulação de SED
Como exemplo para a simulação, seja o simples sistema de fila de uma
agência bancária, onde os clientes são atendidos pelo caixa.
Figura 3 - Exemplo para a simulação - Fila em uma agência bancária
Neste evento podemos verificar uma série de elementos que foram definidos
na Seção 2.1, são eles:
•
Entidade: cliente;
•
Atributo: saldo na conta bancária;
•
Processo: atendimento do cliente;
•
Estado: Comprimento da Fila;
Simulação de Sistemas a Eventos Discretos
12
•
Recurso: caixa do banco; e
•
Eventos: chegada do cliente e saída do cliente.
Perguntas que podem ser respondidas através da simulação deste sistema
podem ser:
1. Quanto tempo em média um cliente permanece no banco?
Para responder esta pergunta deve-se usar a seguinte expressão:
Ŝ =
1 N
∑ Sk (1)
N k =1
onde:
N Æé o número de clientes; e
Sk Ætempo de sistema de cada cliente k, ou seja, o tempo que o cliente k leva
desde o momento que ele chega ao banco até o momento de sua partida.
2. Probabilidade de o caixa estar ocupado?
O caixa estará ocupado toda vez que o comprimento da fila for maior que zero.
Para calcular-se esta probabilidade, denotada por ρ̂ N , deve ser armazenado ao
longo da simulação a quantidade de tempo em que a fila permanece com um
número i de clientes, esta variável será chamada de T(i), onde i = 0, 1, 2, ...
O tempo total da simulação, TN, será dado por:
∞
TN = ∑ T (i ) (2)
i =0
Então o percentual de tempo em que o caixa fica ocupado pode ser calculado
pela seguinte expressão:
∞
ρ̂ N =
∑ T (i )
i =1
TN
(3)
Simulação de Sistemas a Eventos Discretos
13
Ou então, podemos encontrar ρ̂ N através da seguinte expressão:
ρˆ N = 1 −
T (0 )
TN
(4)
Pode ser constatado que a equação (4) é mais fácil de ser implementada,
porque ao contrário da equação (3) é necessário apenas armazenar a quantidade
de tempo em que a fila fica com um número zero de clientes, este valor será
armazenado na variável T(0).
3. Qual o comprimento médio da fila?
Denota-se por QN, o comprimento médio da fila durante o intervalo de tempo
necessário para atender N clientes e:
pN(i) = probabilidade de que o comprimento da fila seja i durante o intervalo de
tempo necessário para atender N clientes, onde i = 0, 1, 2, ...
Por definição,
∞
QN = ∑ ipN (i )
(5)
i =0
De modo a obter o estimar o valor de Q̂N , a partir de QN , será necessário
estimar pˆ N (i ) a partir de pN(i).
pˆ N (i ) =
T (i )
(6)
TN
Então, substituindo a equação (6) em (5) e dividindo por TN obtém-se o valor
médio da fila que é dado por:
1
Qˆ N =
TN
∞
∑ iT (i )
i =0
(7)
Simulação de Sistemas a Eventos Discretos
14
Observa-se então, para que se possa saber o comprimento médio da fila
deverá ser armazenado o tempo em que a fila fica em cada um dos tamanhos
possíveis durante a simulação.
Tendo visto que tipos de perguntas podem ser respondidos ao final da
simulação, a seção seguinte apresenta passo a passo as etapas deste processo.
3.4.1. Simulação para o atendimento de cinco clientes
Um outro ponto importante é a escolha de um Critério de Parada, que vem a
ser a condição a ser testada ao longo da simulação de modo a interrompê-la
quando esta condição for satisfeita.
Podem ser critérios de parada:
a) Tempo de Simulação: pode-se optar por interromper a simulação depois
de transcorrido um certo intervalo de tempo; e
b) Condição Satisfeita: pode-se optar por interromper a simulação quando
for atingido determinado objetivo, como por exemplo, uma determinada
quantidade de clientes atendida ou um número x de peças montadas.
Será utilizado como critério de parada para a simulação o atendimento de
cinco clientes. Portanto, tem-se:
t = 0 Æ Inicialização
A rotina de inicialização fará a variável Tempo = 0 e o Estado = 0 (onde o
estado para o sistema em questão é o comprimento da fila).
Precisa-se então montar o calendário de eventos factíveis para o sistema,
como não há clientes na fila logicamente não poderá haver partida de clientes,
então o único evento factível é a chegada de clientes, então inclui-se no
calendário o evento chegada e ao rodar a rotina de geração de número aleatórios
de intervalos de tempo obtém-se ∆t = 0,4 .
As estruturas de dado do programa na ficarão da seguinte forma:
Simulação de Sistemas a Eventos Discretos
Tempo
Estado
0
0
Tempo de Chegadas
1
2
3
4
5
15
Calendário de
Eventos
chegada
0,4
Tempo de
Sistema
1
2
3
4
5
Tempo de Ocupação da Fila
T(0)
T(1)
T(2)
T(4)
T(5)
0
0
0
0
0
t = 0,4 Æ Primeiro cliente chega
Este é o único evento agendado, então se deve fazer Tempo = 0,4 e o
Estado = 1. Este evento deverá ser removido do calendário e deverá ser feita sua
atualização. Neste novo estado dois eventos são factíveis, a chegada de um novo
cliente ou a saída do cliente que chegou no instante t = 0,4, deverão ser inseridos
estes dois eventos no calendário e feita a chamada da rotina de geração de
intervalos de tempo, que poderá retornar 0,3 para a chegada de um novo cliente e
1,6 para a saída do cliente que chegou no sistema.
Após a atualização para t=0,4 a estrutura de dados ficará da seguinte forma:
Tempo
Estado
0,4
1
Tempo de Chegadas
1
2
3
4
5
0,4
Calendário de
Eventos
chegada 0,7
partida
2,0
Tempo de
Sistema
1
2
3
4
5
Tempo de Ocupação da Fila
T(0)
T(1)
T(2)
T(4)
T(5)
0,4
0
0
0
0
t = 0,7 Æ Segundo cliente chega
As variáveis devem ser atualizadas, fazendo Tempo = 0,7 e Estado = 2. Esta
chegada será removida do calendário e como a partida ainda é um evento factível
ela permanece no sistema com o tempo t = 2 calculado no item anterior, porém,
no estado 2 um outro evento que também pode ocorrer e a chegada de cliente,
Simulação de Sistemas a Eventos Discretos
16
portanto, um novo evento chegada será incluído no calendário, e ao rodando a
rotina de geração de intervalos de tempo ela pode retornar 0,4.
Após a atualização para t=0,7 a estrutura de dados ficará da seguinte forma:
Tempo
Estado
0,7
2
Tempo de Chegadas
1
2
3
4
5
0,4
0,7
Calendário de
Eventos
chegada 1,1
partida
2,0
Tempo de
Sistema
1
2
3
4
5
Tempo de Ocupação da Fila
T(0)
T(1)
T(2)
T(4)
T(5)
0,4
0,3
0
0
0
t = 1,1 Æ Terceiro cliente chega
Mais uma vez o evento com o menor tempo de ocorrência era uma chegada
de cliente, portanto deve-se atualizar a variável Tempo = 1,1 e o Estado = 3.
Deve-se retirar este evento do calendário, a partida do cliente ainda é um evento
factível, então permanece no calendário, deve-se ainda incluir uma nova chegada
de cliente e a rotina de geração de intervalos retorna o valor 1,7.
Após a atualização para t=1,1 a estrutura de dados ficará da seguinte forma:
Tempo
Estado
1,1
3
Tempo de Chegadas
1
2
3
4
5
0,4
0,7
1,1
Calendário de
Eventos
partida
2,0
chegada 2,8
Tempo de
Sistema
1
2
3
4
5
Tempo de Ocupação da Fila
T(0)
T(1)
T(2)
T(4)
T(5)
0,4
0,3
0,4
0
0
t = 2 Æ Primeiro cliente deixa o sistema
Agora o primeiro evento do calendário é a partida de um cliente. Deve-se
então ajustar o Tempo = 2 e Estado = 2. Este evento deverá ser retirado do
sistema, o evento chegada, agendado no item anterior deverá permanecer no
calendário, entretanto, neste estado, a partida de cliente é um evento factível
Simulação de Sistemas a Eventos Discretos
17
então inclui-se no calendário um novo evento partida, e ao chamar a rotina de
geração obtém-se um intervalo de ocorrência 0,5.
Após a atualização para t=2 a estrutura de dados ficará da seguinte forma:
Tempo
Estado
2
2
Tempo de Chegadas
1
2
3
4
5
0,4
0,7
1,1
Calendário de
Eventos
partida
2,5
chegada 2,8
Tempo de
Sistema
1
1,6
2
3
4
5
Tempo de Ocupação da Fila
T(0)
T(1)
T(2)
T(3)
T(4)
0,4
0,3
0,4
0,9
0
t = 2,5 Æ Segundo cliente deixa o sistema
Um novo cliente deixa o sistema, deve-se ajustar o Tempo = 2,5 e o
Estado = 1. O evento partida deverá ser removido do calendário, o evento
chegada deverá ser mantido e um novo evento partida deverá ser incluído. A
rotina de geração de intervalos retorna 1.
Após a atualização para t=2,5 a estrutura de dados ficará da seguinte forma:
Tempo
Estado
2,5
1
Tempo de Chegadas
1
2
3
4
5
0,4
0,7
1,1
Calendário de
Eventos
chegada 2,8
Partida
3,5
Tempo de
Sistema
1
1,6
2
1,8
3
4
5
Tempo de Ocupação da Fila
T(0)
T(1)
T(2)
T(3)
T(4)
0,4
0,3
0,9
0,9
0
Fim da Simulação: Quando o critério de parada é atingido, uma possível
configuração final das estruturas de dados do sistema poderia ser:
Simulação de Sistemas a Eventos Discretos
Tempo
Estado
5,3
1
Tempo de Chegadas
1
2
3
4
5
0,4
0,7
1,1
2,8
4,5
18
Calendário de
Eventos
chegada 5,9
Tempo de
Sistema
1
1,6
2
1,8
3
2,4
4
1,0
5
0,8
Tempo de Ocupação da Fila
T(0)
T(1)
T(2)
T(3)
T(4)
1,1
1,4
1,9
0,9
0
3.4.2. Análise dos dados obtidos da simulação
De posse da estrutura de dados obtida ao fim da simulação do sistema as
perguntas formuladas no início da seção 2.4 poderão ser respondidas.
1. Quanto tempo em média um cliente permanece no banco?
1,6 + 1,8 + 2,4 + 1,0 + 0,8
Sˆ 5 =
= 1,52
5
2. Probabilidade de o caixa estar ocupado?
ρˆ 5 = 1 −
1,1
= 0.79
5,3
3. Qual o comprimento médio da fila?
(0.1,1) + (1.1,4) + (2.1,9) + (3.0,9) + 0 + ...
Qˆ 5 =
= 1,49
5,3
4.
Linguagens usadas na simulação de SED
Os programas de simulação de SED atuais permitem a animação das
entidades, dos recursos, das filas e de diversos outros elementos que compõe o
sistema.
Tal
animação
permite
uma
melhor
visualização
do
fluxo
de
Simulação de Sistemas a Eventos Discretos
19
acontecimentos e uma melhor compreensão do sistema. Tais programas também
são capazes de gerar relatórios sobre os elementos mais comuns do sistema,
como o tempo de utilização dos recursos e estatísticas sobre o tamanho das filas.
São mostrados a seguir exemplos de linguagens de simulação de SED.
a) GASP
Coleção de 30 rotinas de FORTRAN que podem ser usadas para
simplificar o processo de simulação baseado em um esquema de
agendamento de eventos.
b) GPSS (General Purpose Simulation System)
Linguagem baseada em blocos com os quais podemos implementar um
modelo de simulação orientado a processos.
c) SIMAN (SIMulation ANalysis)
Permite ao usuário usar um modelo de simulação orientado a processos,
orientado a eventos, ou a combinação dos dois.
d) SIMSCRIPT
Como o SIMAN permite uma simulação orientada a eventos ou processos.
É particularmente atrativo para a modelagem de sistemas mais complexos
que não precisam ser caracterizados por estruturas de filas.
e) SLAM ( Simulation Language for Alternative Modeling)
Permite ao usuário usar um modelo de simulação orientado a processos ou
eventos. A modelagem do sistema envolve a caracterização do sistema
através de um sistema de redes, consistindo de nós e arestas.
f) EXTEND
É um pacote de simulação orientado a objetos com um grande número de
bibliotecas para diferentes aplicações. Permite a utilização destas
bibliotecas para a construção de novos objetos.
Simulação de Sistemas a Eventos Discretos
20
No site: http://www.topology.org/soft/sim.html são encontrados uma série de
programas para a simulação de SEDs.
5.
Fatores que devem ser observados na simulação
5.1. Geração de Números Aleatórios
Um problema na simulação de SED é a dificuldade encontrada para que
possam ser gerados números aleatórios de modo a representar fielmente a
natureza estocástica dos eventos que compõe o sistema.
Não importa a quantidade de esforços aplicados nesta tarefa, é impossível
copiar a habilidade da mãe natureza para produzir eventos aleatórios. Todas as
técnicas empregadas para se gerar números aleatórios são sistemáticas,
baseadas em algum tipo de algoritmo ou procedimento, portanto, pela sua própria
natureza, estas técnicas não podem produzir números realmente aleatórios.
A qualidade dos números aleatórios gerados será resultado do montante de
esforço computacional que estivermos dispostos a aplicar na simulação. O
método mais empregado na geração de números aleatórios é o da Congruência
Linear, que é baseado na seguinte relação recursiva:
X k +1 = (aX k + c ) mod m , k = 0, 1, 2, ... (8)
onde:
aÆ
é o multiplicador;
cÆ
é o incremento;
m Æ é o módulo; e
X0 Æ é o valor inicial, chamado semente.
A partir de uma distribuição de números uniforme, a qual é denotada por
U[0,1] qualquer distribuição de variáveis pode ser obtida. Pode-se notar que a
equação 8 fornece uma distribuição uniforme, e para que possa ser gerado uma
distribuição uniforme de números {U1, U2, ...} no intervalo [0,1] uma alternativa é
simplesmente fazer Uk = Xk / m.
Simulação de Sistemas a Eventos Discretos
21
Observando a equação 8 nota-se que a expressão para Xk é periódica, por
exemplo, fazendo m = 4, a = 1, c = 5 e X0 = 2, é obtida a seguinte seqüência { 3,
0, 1, 2, 3, 0, 1, ...}, ou seja, o período para este caso será 4. O período da
seqüência é função da variável m, portanto, será interessante escolher valores
elevados de m para se obter a seqüência X.
Existe um grande número de técnicas que geram seqüências com
distribuições diferentes da uniforme a partir da distribuição uniforme, a mais usada
é a Transformação Inversa.
5.1.1. Transformação Inversa
Seja X a seqüência a ser gerada a partir de uma distribuição F(x), vale a pena
salientar que esta distribuição F(x) é função da expressão apresentada no item
anterior. F(x) estará sempre compreendida no intervalo [0,1], e que para cada
valor de F(x) existirá um único valor de X no eixo x, como pode ser visto pela
figura a seguir.
F(x)
1
U
0
x
X=F
-1
(U)
Figura 4 - Gráfico da Transformação Inversa
Exemplo: Obtenção da distribuição exponencial F(x) = e-x.
Como U é igual a F(x) para algum x faz-se:
U = e-X
Vamos obter então a função inversa:
Simulação de Sistemas a Eventos Discretos
22
X = - ln (1-U)
Finalmente, para obter-se os números aleatórios com a distribuição
exponencial são aplicados os valores da seqüência {U1, U2, ...} obtida pela
maneira apresentada no item 4.1.
5.2. Estimativa de Parâmetros
Quando são efetuadas simulações para o estudo de um SED algumas
questões importantes devem ser consideradas:
1. Qual seria uma condição de parada suficientemente boa para encerrar
a simulação e obter a resposta para o estado permanente de um SED?
Não existem técnicas completamente confiáveis para se determinar um bom
ponto para a parada da simulação, pois em um SED pode haver eventos cujo
intervalo de tempo entre suas ocorrências pode ser maior que o tempo usado
para a simulação, o que portanto, invalidaria a simulação.
Uma técnica não muito confiável consiste em simular o sistema durante um
tempo T, e obter o valor de uma variável de interesse para este T, ou seja, X(T),
agora dando prosseguimento à simulação até o tempo 2T, chega-se a X(2T).
Caso | X(2T) – X(T) | < ε para um ε suficientemente pequeno, a simulação é
encerrada. Caso contrário simula-se o sistema até 3T e verificamos se | X(3T) –
X(2T) | < ε, até que a condição seja satisfeita.
2. Como chegar a um valor aceitável de uma determinada variável no
nosso sistema?
Uma técnica para estimar-se com um maior grau de confiabilidade o valor de
uma variável é efetuar um grande número de simulações, e em cada uma destas
simulações fazer o cálculo do valor médio desta variável.
Por exemplo, caso a variável de interesse seja o tempo médio de permanência
de um cliente na fila do banco, a simulação deverá ser realizada n vezes, e em
cada uma delas deverá ser calculado o tempo médio de permanência dos clientes
no banco. Então, seja Ŝi o tempo médio no sistema para a simulação i, portanto
um valor aproximado para o tempo de sistema médio para o sistema em estudo
será:
Simulação de Sistemas a Eventos Discretos
23
1 n
Sˆ = ∑ Sˆ i
n i =1
(9)
Para os casos em que busca-se o comportamento em estado permanente do
sistema alguns refinamentos podem ser feitos na obtenção dos valores médios de
uma determinada variável em cada uma das simulações. A idéia chave é eliminar
o efeito da parte transitória do sistema no cálculo da variável de interesse, já que
o seu valor difere muito do valor da variável em seu estado permanente.
6.
Conclusão
Este trabalho tenta apresentar todos os passos a serem seguidos para se
executar a simulação de um SED, bem como as considerações mais importantes
que deverão ser levadas em conta na estimativa dos valores de interesse ao final
da
simulação,
para
que
os
valores
obtidos
expressem
realmente
o
comportamento das variáveis, validando desta forma o modelo desenvolvido para
o sistema.
Um fator de extrema importância na simulação é o cuidado que deve ser dado
à fase de modelagem do sistema, pois uma modelagem que simplifique
demasiadamente o comportamento do sistema certamente gerará uma simulação
que não representa o comportamento verdadeiro do sistema.
A simulação usando a técnica de eventos discretos é uma área de estudo
recente e em virtude disto muitos pontos ainda estão em aberto, entretanto, como
muitos sistemas que precisam ter seu comportamento estudado ou possuem um
sistema de equações diferenciais muito complexo ou nem mesmo o possuem, a
simulação destes sistemas só é possível através deste método.
Tendo em vista o exposto acima, o desenvolvimento das linguagens de
programação para a simulação de SED bem como a criação de programas com
uma interface mais amigável para o usuário é um vasto campo que tem muito a
ser desenvolvido e sua aplicação é bastante diversificada.
Simulação de Sistemas a Eventos Discretos
24
Anexo A. Simulação de SED usando o Arena
A.1 O Arena
O Arena é um programa de simulação de baseado na linguagem SIMAN,
produzido pela Rockwell Software. Desenvolvido para o ambiente Windows ele
dispõe de uma interface gráfica onde o processo a ser estudado é modelado
através de diagramas de blocos, onde procedimentos, tomadas de decisão,
mudanças de atributos, entre outras ações são aplicadas às entidades de
interesse à medida que elas percorrem as etapas do processo.
Os dois principais grupos de blocos são:
a) Blocos de Processo: são responsáveis pela criação e extinção das
entidades, executam as tarefas necessárias através da alocação de 1 ou mais
recursos para a sua execução, etc.
b) Blocos de Transferência: são responsáveis pelo deslocamento das
entidades pelas diversas etapas do processo, para isto podem ser usados desde
esteiras a Automated Guided Vehicle (AGV).
A.2 Simulação de uma Célula de Manufatura
Seja o sistema que utiliza as máquinas M1, M2, M3 e M4 e os robôs R1 e R2
para a produção das peças P1 e P2. Cada recurso pode comportar uma peça por
vez. As peças entram na célula através dos buffers de entrada I1 e I2 e deixam a
célula através dos buffers de descarga O1 e O2. A disposição dos equipamentos
e a seqüência de montagem das peças são apresentadas a seguir.
Simulação de Sistemas a Eventos Discretos
25
Figura 5 - Célula flexível de manufatura
Figura 6 - Fluxo de Montagem das Peças
A.2.1 Modelagem da Célula para a Simulação no Arena
A.2.1.1 Modelagem das Peças
No Arena os locais onde as entidades permanecem, para aguardar a
disponibilidade de um recurso ou para que possa ser executada uma tarefa são
chamados de Stations. Como o percurso das peças entre as máquinas da célula
já é pré-determinado, primeiro definiu-se dentro do bloco Sequences os locais por
onde cada uma das peças deverá passar pela célula.
Como P1 pode ser manipulada tanto pela M1 quanto pela M2 um artifício
usado para a definição das seqüências das peças foi criar uma entidade chamada
Simulação de Sistemas a Eventos Discretos
26
Peça 3, que fará o percurso I1 Æ M2 Æ M3 Æ O1. Vale ressaltar que, durante a
simulação, todas as vezes que se fizer referência a Peça 3, deve-se associá-la a
Peça 1 que durante o seu processo de manufatura passou pela M2 e não pela
M1.
Na figura a seguir tem-se a definição da seqüência para a Peça 3, no campo
Steps tem-se as Stations por onde a entidade passará ao longo da célula.
Figura 7 - Definição da Seqüência da Peça 1 (quando esta passa por M2)
Optou-se por empregar seqüências ao invés de transporte de peças porque
uma vez definida a seqüência de uma peça, toda vez que ela tiver que deixar uma
Station não será preciso indicar a próxima Station a ser visitada, pois o bloco
Transport que fará este trabalho procurará dentro das propriedades da entidade
o tipo de percurso e saberá desta forma dar o correto destino a ela. Essa atitude
também facilita a alteração do processo produtivo, pois caso seja necessário
alterar o caminho de uma peça não será preciso modificar todas as chamadas da
função Transport.
Como o principal atrativo do Arena é permitir a visualização da simulação do
processo, no bloco Sets são definidos os Tipos de Peças que serão usadas para
que possa ser atribuído a cada uma delas um desenho de modo a permitir sua
visualização por todo o trajeto na célula. A atribuição de figuras a cada uma das
peças é feita através do bloco Entities.
Simulação de Sistemas a Eventos Discretos
27
Figura 8 - Definição dos Tipos de Peça
Figura 9 - Atribuição de desenhos às peças
Para que possa ser simulado o processo, o próximo passo a seguir é utilizar o
bloco Arrive, que é responsável pela criação das entidades, neste bloco podem
ser definidos os intervalos entre as chegadas de novas peças, o destino inicial
das peças, que para o caso da célula será uma esteira, que no Arena é
representada pelo bloco Conveyor.
Simulação de Sistemas a Eventos Discretos
28
Figura 10 - Caixa de diálogo do Bloco Arrive
Dentro de Assign são determinados os parâmetros da nova entidade que
acabou de ser criada, como o Tipo da Peça e sua Seqüência, como é
apresentado a seguir.
Simulação de Sistemas a Eventos Discretos
29
Figura 11 - Determinando os atributos da entidade
A.2.1.2 Modelagem das Máquinas
Para a modelagem das máquinas será usado o bloco Server, nele pode-se
configurar o recurso que será empregado na entidade quando de sua chegada na
Station onde se encontra a máquina, bem como o desenho representativo dos
estados da máquina (ociosa, trabalhando, quebrada, etc), o tempo de duração de
determinada tarefa, bem como o destino a ser dado à entidade depois de sua
passagem pelo Server.
Figura 12 - Caixa de diálogo do bloco Server
Simulação de Sistemas a Eventos Discretos
30
A.2.1.3 Modelagem dos AGVs
Agora deverão ser definidos os veículos que farão o transporte das peças
entre as Stations da célula. Para isto será usado o bloco Transporter, onde será
definido o tipo de caminho a ser percorrido pelo AGV, para a célula de manufatura
em questão optou-se por usar o sistema Guided Path, no qual cada um dos
transportes só poderá percorrer caminhos previamente determinados para ele,
evitando assim que haja o choque entre AGVs.
Figura 13 - Caixa de Diálogo do Bloco Transporter, definição do AGV R1
Da mesma forma que são atribuídos desenhos às entidades e às máquinas,
também são atribuídos desenhos aos AGVs.
Simulação de Sistemas a Eventos Discretos
31
A.2.1.4 Modelagem dos Percursos dos AGVs
Nesta etapa deve-se levantar todos os possíveis percursos a serem realizados
pelo AGV, para a criação de cada um destes percursos, é usado o bloco NLink,
onde é necessário associar a cada Station uma Intersection, esta Intersection é o
ponto onde ocorre a transferência da entidade entre a Station e o AGV, o
NetworkLink é sempre definido por duas Intersections.
Figura 14 - Caixa de Diálogo NetworkLink
A.2.1.5 Implementação das Restrições
Como cada máquina só pode comportar uma peça por vez, a rotina que
solicita o transporte da peça deverá conter uma verificação do estado da Station
de destino.
Por isso, antes de solicitar o AGV a rotina testa as seguintes variáveis na
estação de destino:
a) Verifica se não existe alguma peça indo para aquele destino;
b) Verifica se o recurso, no caso da célula em questão, a máquina, não está
ocupada; e
Simulação de Sistemas a Eventos Discretos
32
c) Verifica se não existe alguma peça no buffer de saída da Station de
destino.
Caso todas estas condições sejam satisfeitas significa que a Station de
destino está vazia, e a peça poderá ser transferida, caso contrário, a rotina de
transporte manterá a peça em um buffer, em um bloco chamado Wait,
aguardando por um sinal enviado pelo bloco chamado Signal, que indicará que a
peça que estava ocupando o destino já foi despachada e que a máquina está
livre.
A célula em questão apresenta um complicador, como as máquinas M1 e M2
enviam suas peças para a M3, no instante em que M3 der o sinal de liberação M1
e M2 podem solicitar ao mesmo tempo o transporte, o que acarretaria no envio de
duas peças para M3, o que não é aceitável. Para contornar este problema logo
após a liberação da peça no bloco Wait em M1 e M2 um novo teste é feito para
ver se M3 reúne condições para receber a peça. O diagrama de blocos da rotina
de envio de peça é mostrado a seguir.
Figura 15 - Diagrama de blocos da chamada de transporte na M1
A.2.1.6 Conclusões
Após algumas simulações com o Arena pode-se constatar que o programa
não atende um requisito básico para a simulação de SED, a geração de números
aleatórios.
Os números aleatórios gerados pelo programa são sempre os mesmos, ou
seja, as variáveis da fórmula: X k +1 = (aX k + c ) mod m , k = 0, 1, 2, ...,
apresentada na seção 4.1, são sempre as mesmas, o que faz com que em todas
as simulações os mesmos resultados sejam obtidos. Tal comportamento
Simulação de Sistemas a Eventos Discretos
33
impossibilita o estudo estatístico do sistema, impedindo desta forma o cálculo do
valor estimado das variáveis de interesse da célula através da observação do
comportamento do sistema ao final de n simulações, haja vista que em todas elas
chegaremos aos mesmos resultados.
Referências Bibliográficas
1. Cassandras, Christos G., e Lafortune, Stéphane. Introduction to Discrete Event
Systems. Kluwer Academic Publisher.
2. Mendes,
Rafael
Santos.
Simulação
http://www.dca.fee.unicamp.br/~rafael/
de
Sistemas
Dinâmicos.