Prof. Lorí Viali, Dr.
[email protected]
http://www.pucrs.br/famat/viali/
Dentre a grande variedade de
sistemas que podem ser modelados e
para os quais a simulação pode ser
aplicada com proveito, uma classe
mostra-se particularmente de interesse.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
É a classe dos sistemas construídos
pelo homem (artificiais), que interagem
com o ambiente (abertos), que se
alteram com o tempo (dinâmicos), onde
existem mudanças que não podem ser
previstas (estocásticos) e onde as
alterações ocorrem em pontos isolados
do tempo (discretos).
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Caracterizado o sistema, duas das
principais decisões que precisam ser
tomadas
é
como
se
darão
as
modelagens das estruturas estática e
dinâmica do sistema.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
1
Estrutura Estática
as
A modelagem da estrutura estática
componentes principais do sistema,
consiste em identificar os componentes
definindo sua estrutura lógica e decidir
principais, através da definição das
como será feito o manuseio do tempo:
entidades e suas inter-relações, eventos
se através do enfoque do processo, da
(atividades ou processos), atributos, filas
atividade ou do evento.
(e suas disciplinas), etc.
É
necessário
identificar
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Quase todas as linguagens de
simulação utilizam alguma forma
gráfica (diagramas) para representar o
sistema a ser modelado, tanto para
auxiliar no processo de construção do
modelo quanto na sua implementação.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
O manuseio do tempo
Uma das vantagens da simulação é
A essência da simulação é que as
que a velocidade na qual o experimento
mudanças de estado do sistema são
ocorre pode ser controlada. Pode-se
modeladas através do tempo. Assim, é
simular semanas e meses ou mesmo anos
importante considerar como o fluxo do
em
poucos
minutos
de
tempo
computacional.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
tempo pode ser gerenciado.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
2
Na vida real, o tempo flui numa taxa
uniforme. Num computador digital não é
possível
ter
continuamente.
variáveis
Existe
mudando
um
tamanho
O incremento constante é o caminho
mais simples de controlar o fluxo do
tempo. Esta abordagem é conhecida
mínimo de incremento de qualquer
como "tempo fatiado" (time slicing)
variável num computador digital.
[CARRIE, 1992 e PIDD, 1997].
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Ela
consiste
em
atualizar
e
examinar o modelo em intervalos
regulares. Para uma fatia de tempo dt,
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Um problema óbvio com esta
abordagem é que a decisão sobre o
tamanho do incremento deve ser tomada
o modelo é atualizado para o tempo
antes da simulação ser desenvolvida.
t + dt, para mudanças ocorridas no
Isto poderá acarretar descompassos.
intervalo (t, t + dt).
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Pode-se ter fatias muito largas, que
A diferença entre manusear o tempo
podem impossibilitar certas atividades, ou
em incrementos fixos ou variáveis é
fatias muito pequenas, que vão gerar
ilustrada pelo exemplo abaixo, devido a
ineficiência que é refletida em tempos
PIDD, 1997. O incremento variável
computacionais longos e por checagens
consiste em atualizar o modelo somente
freqüentes e nem sempre necessárias.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
na ocorrência dos eventos.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
3
Exemplo
Uma fábrica é constituída pelas
Tempo na máquina A =
máquinas A e B. O tempo para
processar um lote de peças, depende
do tipo de máquina e do tamanho do
(Tamanho do lote/50 + 1) dias,
Tempo na máquina B =
(Tamanho do lote/100 + 3) dias.
lote, da seguinte forma:
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
A fábrica somente inicia o
processamento de um lote, que deve
ser processado nas duas máquinas,
quando todo o lote foi processado
numa máquina.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Isto é, nenhum lote pode iniciar
seu processamento em uma máquina
até que todo o lote anterior tenha sido
processado nesta máquina. Os lotes
chegam à fábrica de acordo com as
datas da tabela.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Lote número
Tamanho
Dia da chegada
1
2
200
400
1
8
3
4
100
200
14
18
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Os tempos de processamento de cada
lote em cada máquina são:
Lote número
Máquina A
Máquina B
1
2
3
4
5
9
3
5
5
7
4
5
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
4
Dia
Trabalhos esperando pela
Trabalhos em progresso para
Máquina A
Máquina B
Máquina A
Máquina B
1
-
-
1
-
Simulando o funcionamento da fábrica
2
-
-
1
-
3
-
-
1
-
através de incrementos constantes de um
4
-
-
1
-
5
-
-
1
-
dia, os quatro lotes serão processados em
6
-
-
-
1
7
-
-
-
1
32 dias. A tabela 1 mostra a simulação a
8
-
-
2
1
9
-
-
2
1
incrementos constantes dos lotes.
10
-
-
2
1
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
16
3
-
2
-
17
-
-
3
2
18
4
-
3
2
19
4
-
3
2
20
-
3
4
2
21
-
3
4
2
22
-
3
4
2
23
-
3
4
2
24
-
-
4
3
25
-
4
-
3
26
-
4
-
3
27
-
4
-
3
28
-
-
-
4
29
-
-
-
4
30
-
-
-
4
31
-
-
-
4
32
-
-
-
4
No
sétimo
dia
também
não
ocorrem alterações e no oitavo, temos
a chegada do lote 2 e a máquina A
inicia o seu processamento e assim por
diante.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
11
-
-
2
-
12
-
-
2
-
13
-
-
2
-
14
3
-
2
-
15
3
-
2
-
Conforme a tabela 1, no primeiro dia
o lote 1 chega e é imediatamente
processado na máquina A. Nos dias 2, 3, 4
e 5 não há alterações, pois a máquina A,
ainda está processando o lote 1 somente
no sexto dia a máquina B inicia o
processamento do primeiro lote.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Vê-se que esta abordagem além de
tediosa é uma forma ineficiente de
simular o sistema suposto acima, uma vez
que o modelo estará sendo examinado a
cada fatia do tempo (1 dia) e em 32/36 =
88,9% dos dias nenhuma alteração
acontecerá.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
5
Em virtude destes períodos de
tempo estáticos é que normalmente é
preferível
utilizar
simulação
a
incrementos variáveis.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Cada um destes eventos pode
ocorrer no máximo quatro vezes durante
a simulação, uma para cada tarefa. De
fato, como a tabela 4 mostra, alguns
coincidem e o modelo necessita somente
ser atualizado em 16 ocasiões.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Para elaborar a simulação a
incrementos variáveis, considera-se os
seguintes eventos:
Chegada da tarefa;
Máquina A inicia o trabalho;
Máquina A termina o trabalho;
Máquina B começa o trabalho;
Máquina B termina o trabalho.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Enquanto a tabela 1, mostra as
inevitáveis
32
atualizações
da
abordagem tempo em incrementos
constantes. O método de incrementos
variáveis, neste caso, concentra-se no
progresso de cada lote, quando eles
passam através da fábrica.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Tabela 2 - Simulação a incrementos variáveis
Máquina A
Tarefa
número
Data de
chegada
1
Máquina B
Inicio
Fim
Inicio
Fim
1
5
6
10
2
8
8
16
17
23
3
14
17
19
24
27
4
18
20
24
28
32
Desta
incremento
forma
a
variável
técnica
possui
do
duas
vantagens sobre a abordagem tempo
fatiado.
Fonte: Pidd, 1988
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
6
A primeira, é que o tamanho do
incremento
de
tempo
A segunda, é deixar claro a
ajusta-se
ocorrência de eventos significativos
automaticamente para períodos de alta
na simulação. A desvantagem é a
ou baixa atividade, evitando desta
necessidade
de
forma checagens dispendiosas e/ou
informação
para
desnecessárias dos estados do modelo.
simulação.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
manter
controlar
mais
a
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
A simulação
a
incrementos
variáveis pode ser realizada através de
várias formas, no entanto, todas
possuem um denominador comum que é
produzir programas com estrutura
hierárquica de três níveis (FISHMAN, 1973)
que são os seguintes:
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
Nível 1 - Programa de controle ou
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
No
primeiro
nível,
está
o
executivo;
Nível 2 - Operações;
Nível 3 - Rotinas detalhadas.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
programa de controle ou executivo.
Ele é o responsável por:
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
7
Referências:
(a) programar eventos futuros,
(b) executar eventos em uma seqüência
de simulação própria e
(c) atualizar a variável relógio (clock)
que controla o tempo.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
HILLIER, F. S., LIEBERMAN, G. J.
Introduction to Operations Research. New
York (NY): McGraw Hill, 2002. Seventh
Edition. 805 p.
NANCE, Richard E., TECH, Virginia. The Time
and State Relationships in Simulation
Modeling. Communications of the ACM.
USA, v. 24, n. 4, p. 173-79, Apr. 1981.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
CARRIE, Allan. Simulation of Manufacturing Systems.
Great Britain: John Wiley & Sons, 1992, 417 p.
CHEN, Shin-Ken. The Design, Evaluation and Test of
Flexible Manufacturing System: A hybrid
Approach of Optimization and Phisical emulation.
USA: Case Western Reserve University, May 1987.
Ph.D. Thesis.
FISHMAN, G. S. Concepts and Methods in Discrete
Event Digital Simulation. New York: Willey, 1973.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
PIDD, M. Computer Simulation in Management
Science. New York: John Wiley & Sons,
1997, 5nd ed., 307 p.
SOBOL, I. O método de Monte Carlo. Editora
Mir. Moscou. 1983, 64 p.
TOCHER, K. D. The Art of Simulation. London:
Universities Press, 1963. 184 p.
Prof. Lorí Viali, Dr. – Faculdade de Matemática - Departamento de Estatística - PUCRS
8