Server (Computing)">
Frank FG TCC SJRP
Frank FG TCC SJRP
Frank FG TCC SJRP
Banca avaliadora:
Prof. Dr. Kelton Augusto Pontara da Costa
1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5 Exequibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 Organização do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 REVISÃO BIBLIOGRÁFICA . . . . . . . . . . . . . . . . . . . . . . . 16
2.1 Redes de fila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1 Elementos de uma fila . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2 Tipos de filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.3 Processo de chegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.4 Processo de atendimento . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.5 Disciplina da fila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Simulação de sistemas . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Modelos de simulação . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.2 Aplicações da simulação . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Simulação de sistemas de eventos discretos . . . . . . . . . . . . . 22
2.3.1 Componentes de um sistema . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.2 Programação de eventos . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Python e SimPy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5 Trabalhos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 DESENVOLVIMENTO DO PROJETO . . . . . . . . . . . . . . . . . . 26
3.1 Cenário da simulação . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Componentes do modelo de simulação . . . . . . . . . . . . . . . . 26
3.3 Visualização do sistema . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Construção do simulador . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.1 Inicialização dos parâmetros da simulação . . . . . . . . . . . . . . . . 28
3.4.2 Criação do ambiente de simulação . . . . . . . . . . . . . . . . . . . . 28
3.4.3 Visualização dos dados . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 TESTES E RESULTADOS . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1 1o Caso de teste: 2 guichês de venda e 2 scanners . . . . . . . . . 34
4.2 2o Caso de teste: 4 guichês de venda e 4 scanners . . . . . . . . . 35
SUMÁRIO 12
5 CONCLUSÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.1 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
13
1 INTRODUÇÃO
1.1 Objetivos
O objetivo deste trabalho é realizar a implementação de um simulador de eventos
discretos que utilize a biblioteca de simulação da linguagem Python, SimPy, e que possibilite
a análise de sistemas reais que possam ser modelados como filas de espera. A ferramenta a
ser desenvolvida deve ser capaz de simular um sistema de filas para entrada em um evento
qualquer, considerando a chegada massiva de clientes em um determinado intervalo de
tempo.
Capítulo 1. INTRODUÇÃO 14
1.2 Motivação
Nos dias atuais, é cada vez mais necessário o uso de modelos que simulem eventos
do mundo real, para otimizar processos já estabelecidos ou até mesmo para auxiliar o
desenvolvimento de um novo projeto. Com a simulação de eventos é possível, por exemplo,
organizar o atendimento de um estabelecimento e planejar novas rotas de transporte.
Portanto, dada a importância da simulação de eventos, aliada às facilidades da linguagem
Python, surgiu a oportunidade para implementação do simulador.
1.3 Justificativa
A tomada de decisões sem um planejamento prévio é bastante arriscada e pode
trazer resultados negativos. A simulação de eventos discretos possibilita a criação de
estratégias para otimização de sistemas do mundo real de forma segura, por meio de testes.
Portanto, essas simulações são indispensáveis para quem precisa avaliar as consequências
de mudanças em um sistema e decidir quais métodos implementar e quais descartar.
1.4 Metodologia
A metodologia para realização deste trabalho consiste nas seguintes etapas: pesquisa
sobre o tema, incluindo simulação de sistemas, simulação de eventos discretos, filas, Python
e Simpy; implementação e especificação do funcionamento do simulador desenvolvido; e a
realização de testes e análise dos resultados obtidos. O material utilizado na pesquisa foi
retirado principalmente de livros, artigos científicos, documentação online e sites, todos
meios gratuitos e acessíveis.
1.5 Exequibilidade
Para a realização deste trabalho será utilizada a linguagem de programação Python
e os recursos de hardware do próprio autor. Além disso, todo o material utilizado pode ser
obtido gratuitamente, assim o trabalho pode ser realizado dentro do prazo estipulado sem
preocupação com recursos adicionais.
e SimPy.
2 REVISÃO BIBLIOGRÁFICA
pode ser atendido por um servidor no mesmo instante; caso contrário, dizemos que pode
ocorrer atendimento em lote [Arenales e Armentano 2006].
Usualmente nos modelos de atendimento usa-se o parâmetro µ e, assim como nos
modelos de chegadas, existem duas nomenclaturas comumente utilizadas associadas a este
parâmetro: número de atendimentos na unidade de tempo e tempo decorrido entre dois
atendimentos consecutivos [Moreira 2017].
Cada uma dessas grandezas apresenta uma distribuição de probabilidade, como é
ilustrado na tabela 2.
Como pode ser observado na figura 4, o modelo de simulação pode ser utilizado
como uma ferramenta para se obter respostas a sentenças do tipo: “O que ocorre se...”,
possibilitando que sejam obtidos insights que auxiliem nas tomadas de decisões antes que
mudanças no sistema sejam implementadas [Chwif e Medina 2014].
Os modelos de simulação podem ser divididos em duas categorias: modelos contínuos
e modelos discretos.
• Modelos contínuos: são utilizados para modelar sistemas cujo estado varia continua-
mente no tempo. Geralmente, modelos desse tipo são compostos por uma série de
equações diferenciais, que são resolvidas numericamente para ver como o modelo se
comporta. [Bratley, Fox e Schrage 2012]
• Modelos discretos: são utilizados para modelar sistemas que mudam o seu estado
em momentos discretos no tempo, a partir da ocorrência de eventos. Em modelos
discretos pode ser observado a disputa por recursos limitados e filas onde os elementos
do sistema esperam pela liberação do recurso solicitado.
Neste trabalho, os modelos aos quais estaremos tratando são voltados a simulação
discreta de sistemas.
• Bancos: a simulação pode ser utilizada para verificar qual é a melhor política de
abertura e fechamento de caixas, número de caixas automáticos necessários, estudar
problemas de layout, determinar o tempo máximo de espera em fila etc;
• Hospitais: neste caso a simulação pode ser utilizada para estudar o comportamento
de UTIs, dimensionamento de ambulâncias, simulações para testar políticas de
transplantes de órgãos etc;
• Cadeias logísticas: nesse segmento a simulação pode ser utilizada para determinar
qual deve ser a melhor politica de estocagem, transporte e distribuição, desde a
origem das matérias-primas, passando pela fabricação até o consumidor final;
analisar um sistema da vida real a partir de uma sequência de eventos discretos no tempo,
podendo servir como base para a modelagem de outros sistemas. O projeto considera
a estimativa de propriedades importantes do sistema a ser modelado e a verificação de
características relevantes sobre seu comportamento, para que tenha seu desempenho
otimizado.
26
3 DESENVOLVIMENTO DO PROJETO
Eventos:
• Chegada de clientes;
É possível observar por meio do fluxograma da figura acima que, após a chegada do
cliente, sua passagem pelo guichê de venda ou ida direta ao scanner e consequente entrada
Capítulo 3. DESENVOLVIMENTO DO PROJETO 28
no evento é condicionada pela posse do ingresso, visto que se o cliente não apresentar esse
atributo, deverá obrigatoriamente comprá-lo.
Ao longo da simulação, com a chegada massiva de clientes, ambos os recursos,
guichês de venda e scanners, formarão filas e assim poderemos observar o desempenho do
sistema, por meio dos tempos de espera.
• Número de scanners.
Além desses valores, o tempo de simulação, ou seja, por quanto tempo a simulação
irá ocorrer deve ser fornecido. Os parâmetros podem ser inicializados via código ou obtidos
por meio de input do usuário. Para uma maior rapidez e praticidade no desenvolvimento,
nesse trabalho todos as variáveis foram inicializadas via código.
de simulação, e iniciar a simulação com a chamada de uma função que controla a chegada
dos ônibus.
A seguir é mostrado o trecho de código responsável por essa etapa:
env = simpy . Environment ( ) #Def . do ambiente
#C o n f i g . dos g u i c h e s de venda
s e l l e r _ l i n e s = [ simpy . Resource ( env , c a p a c i t y =1)
f o r _ i n range (SELLER_LINES ) ]
#C o n f i g . dos s c a n n e r s
s c a n n e r _ l i n e s = [ simpy . Resource ( env , c a p a c i t y =1)
f o r _ i n range (SCANNER_LINES ) ]
w h i l e True :
next_bus = random . e x p o v a r i a t e ( 1 / BUS_ARRIVAL_MEAN)
on_board = i n t ( random . g a u s s (BUS_OCCUPANCY_MEAN,
BUS_OCCUPANCY_STD) )
next_bus = ARRIVALS . pop ( )
on_board = ON_BOARD. pop ( )
# Espera p e l o o n i b u s
bus_log . next_bus ( next_bus )
y i e l d env . timeout ( next_bus )
bus_log . b u s_ a rr iv e d ( on_board )
PURCHASE_GROUP_SIZE_MEAN, PURCHASE_GROUP_SIZE_STD) ) ,
remaining )
p e o p l e _ p r o c e s s e d = p e o p l e _ i d s [− g r o u p _ s i z e : ]
p e o p l e _ i d s = p e o p l e _ i d s [: − g r o u p _ s i z e ]
# Determina a l e a t o r i a m e n t e s e o grupo de p e s s o a s e s t a
indo para os g u i c h e s de venda ou d i r e t a m e n t e para os
scanners
i f random . random ( ) > PURCHASE_RATIO_MEAN:
env . p r o c e s s ( scanning_customer ( env , p e o p l e _ p r o c e s s e d ,
s c a n n e r _ l i n e s , TIME_TO_WALK_TO_SELLERS_MEAN +
TIME_TO_WALK_TO_SCANNERS_MEAN,
TIME_TO_WALK_TO_SELLERS_STD +
TIME_TO_WALK_TO_SCANNERS_STD) )
else :
env . p r o c e s s ( purchasing_customer (
env , p e o p l e _ p r o c e s s e d , s e l l e r _ l i n e s ,
scanner_lines ))
Vale ressaltar que como essa é a função de evento de nível superior, vemos que
todo seu trabalho está ocorrendo em um loop while infinito. No final do loop, é disparado
um de dois eventos de forma aleatória: o grupo vai diretamente aos scanners (chamada
da função scanning_customer()) ou é necessário comprar os ingressos primeiro (chamada
da função purchasing_customer()). Em ambos os casos, a menor fila será escolhida no
momento da seleção.
A função purchasing_customer() simula três eventos principais: ir para a fila,
esperar na fila e, em seguida, passar o controle para o evento scanning_customer() (a
mesma função que é chamada por bus_arrival() para aqueles que vão direto para os
scanners).
d e f purchasing_customer ( env , p e o p l e _ p r o c e s s e d , s e l l e r _ l i n e s ,
scanner_lines ) :
walk_begin = env . now
y i e l d env . timeout ( random . g a u s s (TIME_TO_WALK_TO_SELLERS_MEAN,
TIME_TO_WALK_TO_SELLERS_STD) )
walk_end = env . now
Capítulo 3. DESENVOLVIMENTO DO PROJETO 31
# Compra i n g r e s s o
s a l e _ b e g i n = env . now
y i e l d env . timeout ( random . g a u s s (SELLER_MEAN, SELLER_STD) )
sale_end = env . now
register_group_moving_from_bus_to_seller (
p e o p l e _ p r o c e s s e d , walk_begin , walk_end , s e l l e r _ l i n e [ 1 ] ,
queue_begin , queue_end , s a l e _ b e g i n , sale_end )
# Espera na f i l a
f o r _ in people_processed :
s c a n n e r s . add_to_line ( s c a n n e r _ l i n e [ 1 ] )
y i e l d req
f o r _ in people_processed :
s c a n n e r s . remove_from_line ( s c a n n e r _ l i n e [ 1 ] )
queue_end = env . now
# E s c a n e i a o i n g r e s s o de cada p e s s o a
f o r person in people_processed :
scan_begin = env . now
4 TESTES E RESULTADOS
1o CT 2o CT 3o CT 4o CT
Taxa de chegada de ônibus (distrib. exp) 1/3 1/3 1/3 1/3
Ocupação do ônibus (distrib. normal) 100±30 100±30 100±30 100±30
Tempo para caminhar até o guichê de venda 1±0.25 1±0.25 1±0.25 1±0.25
(distrib. normal)
Tempo para caminhar até o scanner (distrib. 0.5±0.1 0.5±0.1 0.5±0.1 0.5±0.1
normal)
Clientes sem ingresso (%) 40 40 40 60
Número de guichês de venda 2 4 6 5
Número de scanners 2 4 6 5
Figura 8 – 1o Caso de teste: Média de espera na fila dos guichês de venda ao longo do
tempo.
Figura 9 – 1o Caso de teste: Média de espera na fila dos scanners ao longo do tempo.
Figura 10 – 2o Caso de teste: Média de espera na fila dos guichês de venda ao longo do
tempo.
Figura 11 – 2o Caso de teste: Média de espera na fila dos scanners ao longo do tempo.
Na figura 10 podemos ver que assim como no primeiro caso de teste, o crescimento
do tempo de espera nos guichês de venda no segundo caso de teste também é de certa
forma linear, atingindo o seu ápice de pouco mais de 15 unidades de tempo também ao
final da simulação. O tempo médio calculado foi de 8.1 unidades de tempo.
Já a figura 11 retrata que o maior pico de espera nos scanners foi quando o relógio
da simulação estava por volta de 21 chegando a 0.6 unidades de tempo, além disso foi
obtido uma espera média de 0.1 unidades de tempo.
Figura 12 – 3o Caso de teste: Média de espera na fila dos guichês de venda ao longo do
tempo.
Capítulo 4. TESTES E RESULTADOS 36
Figura 13 – 3o Caso de teste: Média de espera na fila dos scanners ao longo do tempo.
Com 6 guichês e 6 scanners pode ser notada uma redução considerável nos tempos
de espera comparados aos resultados das seções 4.1 e 4.2.
Nesse caso, o tempo de espera nos guichês de venda ultrapassa ligeiramente 6
unidades de tempo em poucos momentos durante a simulação, como pode ser visto na
figura 12. Isso se reflete no tempo de espera médio obtido, que foi de 3.7 unidades de
tempo, sendo a menor média entre todos os casos de teste.
Os scanners tiveram tempos de espera bem baixos, tendo como pico 0.1 unidades
de tempo em um único dado momento da simulação, fora isso a espera se manteve abaixo
de 0.075 unidades de tempo durante quase toda a simulação. Assim, tem-se um tempo
médio de espera bem próximo de 0.
Figura 15 – 4o Caso de teste: Média de espera na fila dos scanners ao longo do tempo.
Capítulo 4. TESTES E RESULTADOS 37
Tabela 4 – Médias dos tempos de espera nas filas em cada caso de teste.
1o CT 2o CT 3o CT 4o CT
Tempo de espera médio - Guichês de venda 10.9 8.1 3.7 9.4
Tempo de espera médio - Scanners 0.6 0.1 ≈0 ≈0
Ao observar os três primeiros casos de teste, é possível notar que com o aumento do
número de guichês de venda e scanners o tempo de espera médio em ambas as filas decresce
consideravelmente. Por outro lado, no quarto caso de teste, que apresenta uma maior
porcentagem média de clientes sem ingresso (20% maior que o restante), mesmo possuindo
5 guichês e 5 scanners o tempo médio de espera nos guichês de venda é o segundo maior.
Portanto, com a análise dos resultados obtidos, é possível concluir que para efeito
de reduzir as filas de espera nesse cenário, pode ser mais interessante investir nas vendas
online de ingressos do que aumentar a quantidade de guichês de venda e scanners.
38
5 CONCLUSÕES
5.1 Conclusão
Ao final deste trabalho, podemos concluir que um simulador como este pode
ser utilizado como base para a análise de diversos processos da vida real que podem ser
modelados como uma fila de espera. Também pode ser utilizado para facilitar o aprendizado
da linguagem empregada e da simulação de eventos discretos.
Os estudos realizados durante a revisão bibliográfica foram de suma importância
para adquirir conhecimento sobre simulação e embasar o projeto teoricamente. O contato
com a linguagem Python e o ambiente de simulação SimPy também foi fundamental para o
desenvolvimento do simulador. A gama de ferramentas matemáticas e analíticas disponíveis
para Python é muito alta e o SimPy completa esses recursos para incluir simulações de
eventos discretos, com um código limpo e fácil de entender.
Foi muito proveitoso o desafio de criar uma ferramenta com o objetivo de auxiliar
os usuários na vida real. As dificuldades encontradas, considerando o aprendizado da
aplicação do framework SimPy em Python e a compreensão do tema puderam ser superadas
e o trabalho pôde ser concluído.
Referências
BANKS, J. (Ed.). Discrete-event system simulation. 4th ed. ed. Upper Saddle River,
NJ: Pearson Prentice Hall, 2005. (Prentice-Hall international series in industrial and
systems engineering). ISBN 9780131446793.
BRATLEY, P.; FOX, B.; SCHRAGE, L. A Guide to Simulation. Springer New York,
2012. ISBN 9781468401677. Disponível em: <https://books.google.com.br/books?id=bh_
lBwAAQBAJ>.
PRADO, D. Teoria das Filas e da Simulação. Nova Lima: Falconi Editora, 2017.
OCLC: 1229919887. ISBN 9788555560200.