Teoria de Filas: Conceitos e Aplicações

Prévia do material em texto

SIMULAÇÃO DE SISTEMAS
Teoria de
Filas
 
TÓPICOS
 
Noções Básicas
Definições e História
Expandindo Conceitos
Aplicações
MOTIVAÇÃO
NOÇÕES BÁSICAS
E S T R U T U R A E C A R A C T E R Í S T I C A S D E F I L A S
Estrutura
 
 
OTIMIZAÇÃO
Melhor utilização dos serviços
Menor tempo de espera
Maior rapidez no atendimento
OBJETIVOS
Características
P A D R Ã O D E
C H E G A D A
Processos estocásticos,
podem ser
estacionários ou não.
Pode ser individual ou
em grupo.
P A D R Ã O D E
S E R V I Ç O
Processos estocásticos,
podem ser
estacionários ou não.
Pode ser individual ou
em grupo.
Características
A T I T U D E D O
C L I E N T E
Podem ser
"decepcionados",
"impacientes",
"desistentes", etc.
T I P O D E
C L I E N T E
Podem ser
classificados por
prioridade,
complexidade do
serviço, etc.
 
encurtador.com.br/eswPS
http://encurtador.com.br/eswPS
Características
D I S C I P L I N A
D A S F I L A S
Forma como os
clientes na fila são
escolhidos (FIFO, LIFO,
RSS, PR, etc).
C A P A C I D A D E
Pode ser infinita, ou
finita, em que existe
uma limitação para o
tamanho da fila.
Características
C A N A I S D E
S E R V I Ç O
Podem ser simples ou
multicanais, podendo
ser uma fila única, ou
múltiplas filas.
E S T Á G I O D E
S E R V I Ç O
Pode ser simples ou
multi-estágio, pode
ocorrer processo de
reciclagem
OUTROS
TIPOS
A P R O X I M A Ç Õ E S
Problemas com altas taxas de
ocupação (engarrafamento) podem
ser aproximados por filas
R E D E D E F I L A S
Múltiplas filas podem ser organizadas
em estrutura de redes
F I L A S P O N D E R A D A S
Algoritmo de fila que utiliza
pesos em diversos parâmetros
DEFINIÇÃO
O Q U E É U M A F I L A ?
Qualquer sistema em que uma
'entrada' tem uma 'demanda'
por um recurso finito pode ser
regido por um sistema de filas.
L E O N A R D K L E I N R O C K
AGNER KRARUP ERLANG 
Publicou o primeiro artigo sobre teoria de filas.
HISTÓRIA
MARCOS INICIAIS
1 9 1 7
Erlang modelou e
resolveu o problema
de gerenciamento de
ligações (fila M/D/1)
1 9 4 0
Teoria de filas se torna
uma área de pesquisa
amplamente estudada
1 9 5 3
David Kendall
introduz sua notação
para filas
1 9 6 2
Leonard Kleinrock
aplica teoria de filas
ao problema de
troca de mensagens
A - B
Distribuições de
probabilidade de
tempo de chegada
e de atendimento.
S - K
Número de servidores
em paralelo e
capacidade do
sistema.
M
Tipo de disciplina da
fila.
NOTAÇÃO DE KENDALL
 
A/B/S/K/M ou somente A/B/S
A - B
M (exponencial)
D (determinístico)
G (não especificada)
S - K
1, 2, ..., ∞
M
FIFO/LIFO (First/Last in first out)
RSS (Aleatória)
PR (Preferencial)
NOTAÇÃO DE KENDALL
V A L O R E S Q U E P O D E M S E R A S S U M I D O S
EXPANDINDO
CONCEITOS
T Ó P I C O S M A I S C O M P L E X O S E O U T R A S
A B O R D A G E N S P A R A F I L A S .
Variáveis fundamentais
TS 
Tempo médio de permanência no
sistema
TF
Tempo médio de permanência na fila
NS
Número médio de clientes no sistema
NF
Número médio de clientes na fila
Variáveis fundamentais
S
Quantidade de atendentes
NA
Número médio de clientes em atendimento
 
μ
Ritmo médio de atendimento
O inverso é o intervalo médio de
atendimento TA
λ
Ritmo médio de chegada
O inverso é o intervalo médio entre as
chegadas IC
 
FORMULAÇÕES
I N T E N S I D A D E D E T R Á F E G O
i = ⌈λ/μ⌉ 
R E L A Ç Õ E S
NS = NF + NA TS = TF + TA
L I T T L E
NF = λTF NS = λTS (sistema estacionário)
MODELAGEM
P R O C E S S O D E M O R T E E N A S C I M E N T O
Exemplos
 
https://www.supositorio.com/rcalc/rcalclite.htm
http://simjs.com/queuing/
http://queueing-systems.ens-lyon.fr/
APLICAÇÕES
E X E M P L O S P R Á T I C O S
ELEVADORES
 
Chegada de clientes
em grupo
 
 
 
 
HOSPITAL
Disciplina de fila preferêncial,
classificação dos clientes por
nível de risco
 
 
Aviões
Sistema multi-estágio, voos com escalas
encurtador.com.br/efMOR
 
NAVIOS
 
Alocação de navios em
portos
INCÊNDIOS
FLORESTAIS
Estudou teoria de filas para otimizar a
satisfação dos clientes em uma fila de banco.
Aplicou o mesmo algoritmo para controlar
incêndios florestais, tratando os recursos
disponíveis como o "serviço" e cada foco de
incêndio como um "cliente", com ordem de
prioridade por gravidade e risco, sendo que
quanto mais o fogo tem que "esperar pelo
atendimento", mais "irritado" o cliente fica, ou
seja, mais grave se torna o incêndio.
D A V I D M A R T E L L
Outros exemplos
B A L A D A S
Manter a fila
propositalmente grande
P I L H A S
Disciplina de fila LIFO
A R Q U I V O S
Fila com pesos
CRÉDITOS E
REFERÊNCIAS
 
COSTA, Luciano Cajado. Teoria das filas. 2009.
http://www.netlab.tkk.fi/opetus/s383143/kalvot/english.shtml
https://bit.ly/33ZuMPN
https://en.wikipedia.org/wiki/Queueing_theory
ARENALES, Marcos et al. Pesquisa operacional: para cursos de engenharia. 
BRESSAN, Graça. Modelagem e simulação de sistemas computacionais. 
FILHO, Clovis Perin. Introdução à simulação de sistemas
 
B E A T R I Z A R I A
K A I N A N R A M O S
V I T O R H I D E K I
M A R I N A R O C H A