Cap.2/1 Capítulo 2 Conceitos Fundamentais de Simulação Frederico R. B. Cruz Simulação de...

Cap.2/1

Capítulo 2Conceitos Fundamentais de Simulação

Frederico R. B. Cruz

Simulação de Sistemas

Departamento de Estatística - UFMG

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/2

Conceitos Fundamentais:Um Sistema Simplificado

• objetivo geral:– estimar a produção esperada;– tempo na fila, tamanho da fila, proporção de tempo no qual a

máquina está ocupada;

• bom senso– seja consistente (partes de tempo);

– seja razoável (interpretação, arredondamentos).

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/3

Especificações do Modelo

• inicialmente (tempo 0), sistema vazio e desocupado;

• unidade de tempo: minutos;

• tempos de chegada: 0,00, 6,84, 9,24, 11,94, 14,53;– tempo entre chegadas: 6,84, 2,40, 2,70, 2,59, 0,73;

• tempos de serviço: 4,58, 2,96, 5,86, 3,21, 3,11;

• parar após transcorridos 15 minutos de simulação.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/4

Objetivos do Estudo:Medidas de Desempenho

• número total de partes produzidas P;• tempo médio de espera das partes na fila:

• tempo máximo de espera das partes na fila:

D

N

ii

N

1

N = número de partes produzidas;Di = tempo de espera da i-ésima unidade;conhecidos: D1 = 0 (por quê?)

N > 1 (por quê?)

max, ,i N

iD1

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/5

Objetivos do Estudo:Medidas de Desempenho (cont.)

• número médio de partes na fila:

• número máximo de partes na fila:

• tempo médio e máximo de ciclo das partes (tempo no sistema)

Q(t) = número de partes na filano tempo t

max ( )0 15t

Q t

F P FiiP

i Pi

11

, max, ,

Fi = tempo ciclo i-ésima unidade

Q t dt( )0

15

15

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/6

Objetivos do Estudo:Medidas de Desempenho (cont.)

• utilização da máquina (proporção de tempo de ocupação):

• muitas outras possíveis (sobrecarga de informação?).

B t dt( )0

15

15

B tt

t( )

1

0

if the machine is busy at time

if the machine is idle at time

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/7

Opções de Análise

• palpite– tempo médio entre chegadas = 3,05 min

– tempo médio de serviço = 3,94 min

– tamanho da fila tende a explodir (talvez não em apenas 15 min);– se o tempo médio entre chegadas fosse maior que o tempo médio

de serviço e estes tivessem variância nula, nunca haveria filas;– a realidade: entre estes dois extremos;

– palpite tem suas limitações!

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/8

Opções de Análise (cont.)

• teoria de filas– requer hipóteses adicionais a respeito do modelo;– modelo popular e simples, a fila M/M/1

• tempo entre chegadas ~ exponencial

• tempo de serviço ~ exponencial e independente das chegadas

• E(serviço) < E(chegadas)• regime permanente (tempo muito longo, eterno); • resultados analíticos exatos, p.e., tempo médio de espera na fila:

– problemas: validade, estimativa das médias, janela de tempo; – freqüentemente, útil, como primeira aproximação.

S

A S

2

S

A

EE

((Service Time)Interarrival Time)

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/9

Simulação Mecânica

• operações (chegadas, tempos de serviço) individuais ocorrerão exatamente como na realidade;

• movimentos e mudanças ocorrem no tempo correto, na ordem correta;

• interação entre as diferentes partes;

• intalação de “observadores” para obtenção de medidas de desempenho;

• abordagem “força bruta”;

• nada de misterioso ou refinado– mas muitos detalhes e anotações;– software para simulação pode fazê-lo para você.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/10

Partes de Um Modelo de Simulação

• entidades– “agentes” que se movem, mudam de estado, afetam e são

afetados por outras entidades;

– objetos dinâmicos—são criados, se movem, vão embora (talvez); – usualmente, representam coisas “reais”:

• nosso modelo, entidades são partes;

– pode haver entidades “imaginárias” para modelagem de “travessuras”:

• demônios/anjos que surgem e danificam partes/deixam inoperantes;

• usualmente, apresentam múltiplas realizações;

– pode haver diferentes entidades concorrentes.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/11

Partes de Um Modelo de Simulação (cont.)

• atributos– características de todas as entidades: descrevem, diferenciam;

– todas as entidades possuem atributos básicos, mas diferentes valores para diferentes atributos, p.e.:

• tempo de chegada;

• prazo para entrega;

• prioridade;

• cor;

– valores são característicos de uma entidade específica;

– semelhantes às variáveis locais;

– no Arena, algumas são automáticas, outras, você define.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/12

Partes de Um Modelo de Simulação (cont.)

• variáveis (globais)– reflete a característica de um sistema, independente das entidades;

– cujo nome e valor só existe um para o modelo inteiro;

– não acopladas às entidades;

– podem ser acessadas e modificadas pelas entidades;• tempo de viagem entre estações;

• número de partes no sistema;

• cronômetro da simulação;

– escritas nas “paredes” do sistema, não nas partes;

– algumas, próprias no Arena, mas outras podem ser definidas por você.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/13

Partes de Um Modelo de Simulação (cont.)

• recursos– sobre o que as entidades competem:

• pessoal,

• equipamentos,

• espaço físico;

– as entidades tomam um recurso, utilizam-no e liberam-no;

– pense em um recurso como sendo atribuído a uma entidade, em lugar de uma entidade pertencendo a um recurso;

– “um” recurso pode ter diversas unidades de capacidade:• assentos em uma mesa de restaurante;

– número de unidades de um recurso podem mudar ao longo da simulação.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/14

Partes de Um Modelo de Simulação (cont.)

• filas– locais de espera das entidades, quando não podem se mover

(possivelmente porque o recurso que pretendem tomar não está disponível);

– têm nomes, freqüentemente ligados ao recurso respectivo;

– podem ter capacidade finita para modelar limitação de espaço—tem que ser modelado o que fazer quando uma entidade surgir para entrar em uma fila que já estiver cheia;

– usualmente, monitora-se o seu tamanho e tempo de espera.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/15

Partes de Um Modelo de Simulação (cont.)

• acumuladores de estatísticas– variáveis que “monitoram” o que está ocorrendo;

– dependentes das medidas de desempenho de interesse;

– “passivos” no modelo—não participam, apenas monitoram;

– muito, são automáticos no Arena, mas alguns precisam ser inicializados e manipulados por você durante a simulação;

– ao final da simulação, são utilizados para calcular as medidas de desempenho finais.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/16

Partes de Um Modelo de Simulação (cont.)

• acumuladores de estatísticas para o sistema simplificado:– número de partes produzidas até então;

– total de tempos gastos na fila até então;

– número de partes que passaram pela fila;

– maior tempo na fila já visto;

– total de tempos no sistema;

– maior tempo no sistema já visto;

– área sob a curva de tamanho da fila Q(t) até então;

– maior Q(t) até então;

– área sob a curva de ocupação do servidor B(t) até então;

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/17

Eventos

• “algo” que acontece em um instante de tempo (simulado) e pode mudar:– atributos,

– variáveis,

– acumuladores de estatísticas;

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/18

Eventos para o Sistema Simplificado

• chegada de uma nova parte no sistema:– atualizar os acumuladores de estatísticas,

• área sob Q(t),

• máximo Q(t),

• área sob B(t);

– marcar a parte com o tempo corrente

– se a máquina está desocupada:• iniciar processamento (programar partida), tornar a máquina ocupada,

inicializar o tempo na fila (0);

– senão (máquina ocupada):• colocar parte no final da fila, incrementar tamanho da fila;

– programar próximo evento de chegada.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/19

Eventos para o Sistema Simplificado (cont.)

• partida (quando o serviço é completado):– incrementar o acumulador do unidades produzidas;

– calcular e acumular o tempo no sistema (agora - tempo de chegada);

– atualizar as estatísticas acumuladas;

– se a fila é não-vazia:• tome a primeira parta da fila, calcule e acumule o tempo na fila, inicie

serviço (programar evento de partida);

– senão (fila está vazia):• faça a máquina desocupada (note que neste caso não haverá

programação de evento de partida).

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/20

Eventos para o Sistema Simplificado (cont.)

• Final– atualize as estatísticas acumuladas (até o final da simulação);

– calcular as medidas de desempenho finais, utilizando as estatísticas acumuladas.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/21

Especificações para o Sistema Simplificado

• relógio da simulação (interno ao Arena)

• calendário de eventos (lista de eventos):– [número da entidade, tempo do evento, tipo de evento];

– mantidos na ordem segundo a qual ocorrerão;

– próximo evento sempre no topo;

– inicialmente, programar a primeira chegada;

– final, corresponde à última partida;

• variáveis de estado (descrevem o status atual):– status do servidor, B(t) = 1, se ocupado, 0, se livre;

– número de usuários na fila, Q(t);

– tempos de chegada de cada usuário (lista de tamanho aleatório).

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/22

Simulação Manual

• acompanhar manualmente as variáveis de estados e os acumuladores;

• utilizar os tempos de chegada e de serviço;

• acompanhar o calendário de eventos;

• adiantar o relógio de um evento ao próximo;

• por simplicidade, omitir cálculos dos tempos no sistema e valores máximos;

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/23

Simulação Manual:inicialização

System Clock B(t) Q(t) Arrival times ofcusts in queue

Event calendar

No. of completedtimes in queue

Total of times in queue Area under B(t) Area under Q(t)

B(t) graph

Q(t) graph

Interarrival times 6.84 2.40 2.70 2.59 0.73

Service times 4.91 3.09 6.45 3.40 3.25

t01

t0123

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/24

Simulação Manual:inicialize em t = 0.00

System Clock

0.00

B(t)

0

Q(t)

0

Arrival times ofcusts in queue<empty>

Event calendar[1, 0.00,Arr][-, 15.00, End]

No. of completedtimes in queue0

Total of times in queue

0.00

Area under B(t)

0.00

Area under Q(t)

0.00

B(t) graph

Q(t) graph

Interarrival times 6.84 2.40 2.70 2.59 0.73

Service times 4.58 2.96 5.86 3.21 3.11

t0

1

t0123

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/25

Simulação Manual:chegada da parte 1 em t = 0.00

System Clock

0.00

B(t)

1

Q(t)

0

Arrival times ofcusts in queue<empty>

Event calendar[1, 4.58,Dep][2, 6.84,Arr][-, 15.00, End]

No. of completedtimes in queue1

Total of times in queue

0.00

Area under B(t)

0.00

Area under Q(t)

0.00

B(t) graph

Q(t) graph

Interarrival times 6.84 2.40 2.70 2.59 0.73

Service times 4.58 2.96 5.86 3.21 3.11

1

t0123

t0

1

1

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/26

Simulação Manual:partida da parte 1 em t = 4.58

System Clock

4.58

B(t)

0

Q(t)

0

Arrival times ofcusts in queue<empty>

Event calendar[2, 6.84,Arr][-, 15.00, End]

No. of completedtimes in queue1

Total of times in queue

0.00

Area under B(t)

4.58

Area under Q(t)

0.00

B(t) graph

Q(t) graph

Interarrival times 6.84 2.40 2.70 2.59 0.73

Service times 4.58 2.96 5.86 3.21 3.11

t0

1

t0123

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/27

Simulação Manual:chegada da parte 2 em t = 6.84

System Clock

6.84

B(t)

1

Q(t)

0

Arrival times ofcusts in queue<empty>

Event calendar[3, 9.24,Arr][2, 9.80,Dep][-, 15.00, End]

No. of completedtimes in queue2

Total of times in queue

0.00

Area under B(t)

4.58

Area under Q(t)

0.00

B(t) graph

Q(t) graph

Interarrival times 6.84 2.40 2.70 2.59 0.73

Service times 4.58 2.96 5.86 3.21 3.11

2

t01

t0123

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/28

Simulação Manual:chegada da parte 3 em t = 9.24

System Clock

9.24

B(t)

1

Q(t)

1

Arrival times ofcusts in queue9.24

Event calendar[2, 9.80,Dep][4, 11.94, Arr][-, 15.00, End]

No. of completedtimes in queue2

Total of times in queue

0.00

Area under B(t)

6.98

Area under Q(t)

0.00

B(t) graph

Q(t) graph

Interarrival times 6.84 2.40 2.70 2.59 0.73

Service times 4.58 2.96 5.86 3.21 3.11

23

t01

t0123

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/29

Simulação Manual: partida da parte 2 em t = 9.80

System Clock

9.80

B(t)

1

Q(t)

0

Arrival times ofcusts in queue<empty>

Event calendar[4, 11.94, Arr][-, 15.00, End][3, 15.66, Dep]

No. of completedtimes in queue3

Total of times in queue

0.56

Area under B(t)

7.54

Area under Q(t)

0.56

B(t) graph

Q(t) graph

Interarrival times 6.84 2.40 2.70 2.59 0.73

Service times 4.58 2.96 5.86 3.21 3.11

3

t01

t0123

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/30

Simulação Manual: chegada da parte 4 em t = 11.94

System Clock

11.94

B(t)

1

Q(t)

1

Arrival times ofcusts in queue11.94

Event calendar[5, 14.53, Arr][-, 15.00, End][3, 15.66, Dep]

No. of completedtimes in queue3

Total of times in queue

0.56

Area under B(t)

9.68

Area under Q(t)

0.56

B(t) graph

Q(t) graph

Interarrival times 6.84 2.40 2.70 2.59 0.73

Service times 4.58 2.96 5.86 3.21 3.11

34

t01

t0123

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/31

Simulação Manual: chegada da parte 5 em t = 14.53

System Clock

14.53

B(t)

1

Q(t)

2

Arrival times ofcusts in queue14.53, 11.94

Event calendar[-, 15.00, End][6, 15,26, Arr][3, 15.66, Dep

No. of completedtimes in queue3

Total of times in queue

0.56

Area under B(t)

12.27

Area under Q(t)

3.15

B(t) graph

Q(t) graph

Interarrival times 6.84 2.40 2.70 2.59 0.73

Service times 4.58 2.96 5.86 3.21 3.11

35 4

t0

1

t0123

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/32

Simulação Manual: final em t = 15.00

System Clock

15.00

B(t)

1

Q(t)

2

Arrival times ofcusts in queue14.53, 11.94

Event calendar[6, 15,26, Arr][3, 15.66, Dep]

No. of completedtimes in queue3

Total of times in queue

0.56

Area under B(t)

12.74

Area under Q(t)

4.09

B(t) graph

Q(t) graph

Interarrival times 6.84 2.40 2.70 2.59 0.73

Service times 4.58 2.96 5.86 3.21 3.11

35 4

t0

1

t0123

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/33

Simulação Manual:Finalizações

• tempo médio na fila:

• tamanho médio da fila:

• utilização do servidor:

Total of times in queueNo. of times in queue completed

min./part 0 56

3019

..

Area under ( ) curveFinal clock value

partQ t

4 0915

0 27.

.

Area under ( ) curveFinal clock value

(dimensionless)B t

1274

150 85

..

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/34

Registro Completo da Simulação Manual

Just-Finished Event Variables Attributes Statistical Accumulators Event CalendarEntityNo.

Timet

EventType Q(t) B(t)

Arrival Times:(In Queue) In Service P N D D* F F* Q Q* B [Entity No., Time, Type]

– 0.00 Init 0 0 ( ) ___ 0 0 0.00 0.00 0.00 0.00 0.00 0 0.00[1,[–,

0.00,15.00,

Arr]End]

1 0.00 Arr 0 1 ( ) 0.00 0 1 0.00 0.00 0.00 0.00 0.00 0 0.00[1,[2,[–,

4.58,6.84,

15.00,

Dep]Arr]End]

1 4.58 Dep 0 0 ( ) ___ 1 1 0.00 0.00 4.58 4.58 0.00 0 4.58[2,[–,

6.84,15.00,

Arr]End]

2 6.84 Arr 0 1 ( ) 6.84 1 2 0.00 0.00 4.58 4.58 0.00 0 4.58[3,[2,[–,

9.24,9.80,

15.00,

Arr]Dep]End]

3 9.24 Arr 1 1 (9.24) 6.84 1 2 0.00 0.00 4.58 4.58 0.00 1 6.98[2,[4,[–,

9.80,11.94,15.00,

Dep]Arr]End]

2 9.80 Dep 0 1 ( ) 9.24 2 3 0.56 0.56 7.54 4.58 0.56 1 7.54[4,[–,[3,

11.94,15.00,15.66,

Arr]End]Dep]

4 11.94 Arr 1 1 (11.94) 9.24 2 3 0.56 0.56 7.54 4.58 0.56 1 9.68[5,[–,[3,

14.53,15.00,15.66,

Arr]End]Dep]

5 14.53 Arr 2 1 (14.53, 11.94) 9.24 2 3 0.56 0.56 7.54 4.58 3.15 2 12.27[–,[6,[3,

15.00,15.26,15.66,

End]Arr]Dep]

– 15.00 End 2 1 (14.53, 11.94) 9.24 2 3 0.56 0.56 7.54 4.58 4.09 2 12.74[6,[3,

15.26,15.66,

Arr]Dep]

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/35

Implementação Computacional da Simulação Orientada a Eventos

• claramente adequada;

• frequentemente utiliza bibliotecas para:– gerenciamento de listas;

– geração de números aleatórios;

– coleta de dados;

– gerência de lista de eventos e relógio;

– conclusões e saídas;

• programa principal agrega bibliotecas e executa os eventos em ordem.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/36

Variabilidade na Simulação

• simulação anterior é apenas uma replicação — amostra de tamanho unitário (pouco valor)

• cinco replicações:

• intervalos de confiança das esperanças– p.e., intervalo de 95% de confiança do

E(tempo médio na fila):101 2776

159

5101 197. .

., . .± ± or

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/37

Comparação de Alternativas

• Normalmente, simulação é utilizada para mais de uma simples configuração;

• freqüentemente, deseja-se comparar alternativas, selecionar ou procurar pela melhor (segundo algum critério);

• sistema simplificado: o quê aconteceria se a taxa de chegada dobrasse?– reduzir o tempo entre chegadas à metade;

– simular novamente o modelo;

– realizar cinco replicações.

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/38

Resultados:situação inicial versus dobro taxa chegada

• observar a variabilidade;

• risco em tomar decisões por apenas uma (primeira) replicação;

• difícil concluir que há realmente diferenças;

• é necessária análise estatística dos resultados.

0 1 2 3 4

Original Model

Double-Time Model1

1

Total Production

0 1 2 3 4

Original Model

Double-Time Model

Average Time in Queue5

1

1

3 54 8 9

Original Model

Double-Time Model

Average Flowtime11

1

1

76 10

0 1 2 3 4

Original Model

Double-Time Model1

Average Number in Queue

1

0.4 0.6 0.8 1.0

Original Model

Double-Time Model1

1

Machine Utilization

Simulaçãoo de SistemasConceitos Fundamentais de Simulação

Cap.2/39

Revisão do Estudo de Simulação

• entenda o sistema;

• tenha objetivos claros;

• formule um modelo de representação;

• traduza o modelo para um software de simulação;

• verifique o “programa”;

• valide o modelo;

• planeje os experimentos;

• faça simulações;

• analise, compreenda, documente os resultados.