Teoria das Filas

Prévia do material em texto

27/07/2016
1
TEORIA DAS FILAS E SIMULAÇÃO
Formação das filas
As filas podem ocorrer:
 em interseções
 pontos de estrangulamentos de rodovias
 pontos de ocorrências de incidentes
 praças de pedágio
 entrada/saída de estacionamentos
 sistemas de transporte coletivo
 bancos, linhas de produção etc.
TEORIA DAS FILAS E SIMULAÇÃO
Formação das filas
Estruturas do sistema de filas
População Fila
Atendimento
Disciplina nas filas
 FIFO ou PEPS ("First In First Out" ou "Primeiro a Entrar Primeiro a Sair)
 LIFO ou UEPS ("Last In First Out" ou "Último a Entrar Primeiro a Sair)
 SIRO ("Service In Random Order")
 PRI ("Priority Service")
TEORIA DAS FILAS E SIMULAÇÃO
Formação das filas
Padrão de chegadas
Poisson
Distribuição discreta
p(x) = (e
-
·x)/x!
Padrão de saídas da fila
Exponencial
Distribuição contínua
f(t) = ·e-t
TEORIA DAS FILAS E SIMULAÇÃO
Formação das filas
Notação dos modelos de fila (Kendall)
A/B/c/k/m/Z
Disciplina da fila
Tamanho da população que usa o sistema
Número máximo de usuários
Número de canais de atendimento
Distribuição dos tempos de serviço
Distribuição dos intervalos de chegada
M: distribuição aleatória
D: distribuição determinística
Em: distribuição Erlang (exponencial ou gama)
Hm: distribuição hiper-exponencial no estágio m
G: distribuição genérica
Exemplo de notação:
M/D/1 - Chegada aleatória, saída determinística e 1 canal de atendimento
27/07/2016
2
MEDIDAS DE DESEMPENHO DE FILAS
: taxa de chegada
: taxa de atendimento
1/: intervalo entre chegadas sucessivas
1/: tempo médio de atendimento
Nf: número médio de usuários na fila
Ns: número médio de usuários no sistema
tf: tempo médio de espera na fila
ts: tempo médio de espera no sistema
c: número de canais de atendimento
: taxa de utilização dos atendentes (=/(c·))
r: intensidade de tráfego (/)
TEORIA DAS FILAS E SIMULAÇÃO
Formação das filas
Tempo de duração da fila (ts)
Tempo 
máximo de 
espera na 
fila (tf)
F
il
a
 
m
á
x
im
a
 
(
N
f
)
Mom fluxo (Mf)
N
ú
m
e
r
o
 
d
e
 
v
e
íc
u
lo
s
 
a
c
u
m
u
la
d
o
s
 (
N
s
)
Tempo (t)
Q
u
a
n
t
i
d
a
d
e
 
d
e
 
v
e
í
c
u
l
o
s
 
(
N
)
Nsi
Na

1

t
Nsi
λ 
t
Na
μ 

2
Taxa de chegada
Taxa de serviço
Intensidade de tráfego


 
Espera média Ns
Mf
Em 
Fila média ts
Mf
Nm 
TEORIA DAS FILAS E SIMULAÇÃO
Formação das filas
Tempo de duração da fila (ts)
Tempo 
máximo de 
espera na 
fila (tf)
F
il
a
 
m
á
x
im
a
 
(
N
f
)
N
ú
m
e
r
o
 
d
e
 
v
e
íc
u
lo
s
 
a
c
u
m
u
la
d
o
s
 (
N
s
)
Tempo (t)
Q
u
a
n
t
i
d
a
d
e
 
d
e
 
v
e
í
c
u
l
o
s
 
(
N
)
Nsi Na


1
t
Nsi
λ 
t
Na
μ 
Taxa de chegada
Taxa de serviço
Intensidade de tráfego


 

2
Mom fluxo (Mf)
Espera média Ns
Mf
Em 
Fila média ts
Mf
Nm 
TEORIA DAS FILAS E SIMULAÇÃO
Medidas de Desempenho
t
Ns
λ 
t
Na
μ 
Taxa de chegada
Taxa de serviço
Número de usuários do sistema
tλNs 
Número de usuários atendidos
tμNa 
Intensidade de tráfego


   < 1  sistema não saturado
 ≥ 1  sistema supersaturado
27/07/2016
3
Exemplo 1
Uma rodovia com duas faixas de tráfego por sentido apresenta, durante o pico
da manhã, uma taxa de fluxo de 2.700 veic/h no sentido de maior movimento.
Num dado momento, um acidente bloqueia completamente as duas faixas por
12 minutos, quando uma das faixas é liberada. Após 30 minutos a pista é
completamente liberada ao tráfego. Considerando a capacidade da via de
2.100 veic/h/faixa, determine as medidas de desempenho:
 comprimento máximo da fila
 tempo máximo na fila
 duração da fila
 número de veículos acumulados
 espera média
 comprimento médio da fila
Solução
Q
d
e
v
e
í
c
(
N
)
Tempo (t)
t
Ns
λ 
60
2.700

veic/min54
Período de t = 0 a 12
= 45
60
2.100
μ1 
veic/min35
veic/min70μ2 
12
540
30
1.350
6307
2
0
 v
e
ic
16 min
Ns = 45 · 12
Ns = 540 veic
 = 0
Na = 0
Período de t = 12 a 30
= 45
N = 540 + (30 - 12) · 45
N = 1.350 veic
 = 35
Na = (30 - 12) · 35
Na = 630
Nf = 1.350 - 630
Nf = 720
tf = 30 - 630 / 45
tf = 16 min
Espera média
Em = Mf / Nf
ts
Solução
Q
d
e
v
e
í
c
(
N
)
Tempo (t)
t
Ns
λ 
60
2.700

veic/min54
Duração da fila
ts = 30 + td
60
2.100
μ1 
veic/min35
veic/min70μ2 
12
540
30
1.350
630
58,8
7
2
0
 v
e
ic
16 min
2.646
 
   308,58
2
630646.2
2
6301230
2
58,82.646
Mf







td
td = 720 / (70 - 45)
td = 28,8 min
28,8
ts = 30 + 28,8
ts = 58,8 min
Numero de veículos acumulados
Nf = 45 · 58,8
Nf = 2.646 veic
Mf =24.948 veic·min
Em = 24.948 / 2.646 = 9,4 min
Solução
Q
d
e
v
e
í
c
(
N
)
Tempo (t)
Fila média
Lm = 24.948 / 58,8
Lm = 424,3 veic
12
540
30
1.350
630
58,8
7
2
0
 v
e
ic
16 min
2.646
t
Ns
λ 
60
2.700

veic/min54
60
2.100
μ1 
veic/min35
veic/min70μ2 
28,8
27/07/2016
4
TEORIA DAS FILAS E SIMULAÇÃO
Solução analítica
Servidor único - FIFO - M/M/1


-1
Ns 




1
Nf
2


 
  nnp   1)(
Número médio de usuários no sistema - Ns
Número médio de usuários na fila - Nf
Taxa de utilização do sistema - 
Probabilidade de existirem n usuários na fila - p(n)
TEORIA DAS FILAS E SIMULAÇÃO
Solução analítica
Servidor único - FIFO - M/M/1
Tempo médio de espera no sistema - ts
ts Ns
tf Nf
 

1
ts



tf
Tempo médio de espera na fila - tf
Relações em regime constante
Probabilidade do sistema ficar ocioso
p(0) = 1 - 
Probabilidade de existirem n usuários no sistema
p(n) = n · (1 - )
TEORIA DAS FILAS E SIMULAÇÃO
Solução analítica
Servidor único - FIFO - M/M/1
Probabilidade de esperar por mais de t na fila
p(>t) =  · e-( - )·t
Sistema estável:
 <  ou  < 1
Fila de tamanho infinito:
  
TEORIA DAS FILAS E SIMULAÇÃO
Solução analítica
Servidor único - FIFO - M/D/1
 




12
2
Nf
2
 



12
tf
 

 


12
21
ts tf
Número médio de usuários na fila - Nf
Tempo médio de espera na fila - tf
Tempo médio de espera no sistema - ts
27/07/2016
5
TEORIA DAS FILAS E SIMULAÇÃO
Solução analítica
Multiservidor - FIFO - M/M/c





c


r
 
1
1
0 !!
)0(











 
c
n
cn
rcc
rc
n
r
p
Taxa de utilização do sistema - 
Relação entre a taxa de chegada e a de atendimento
Probabilidade do sistema ficar ocioso
Probabilidade de existirem n usuários na fila - p(n)
Para 1 ≤ n ≤ c
Para n ≥ c
)0(
!
)( p
n
r
np
n

)0(
!
)( p
cc
r
np
cn
n




TEORIA DAS FILAS E SIMULAÇÃO
Solução analítica
Multiservidor - FIFO - M/M/c
Número médio de usuários na fila - Nf
 
)0(
!
2
1
p
rcc
rc
Nf
c





Número médio de usuários no sitema - Ns
 
)0(
!
2
1
p
rcc
cr
rNs
c










Tempo médio de espera nosistema - ts
   
)0(
!1
1
2
p
cc
r
ts
c



 


Tempo médio de espera na fila - tf
   
)0(
!1
2
p
cc
r
tf
c






Exemplo 2
Num determinado porto chegam 6 navios por dia, e o atendimento dura em
média 3 horas. Considerando-se que a chegada dos navios atende a
distribuição de Poisson, determinar:
a) a probabilidade de um navio chegar ao porto e não ter que esperar para
atracar
b) a quantidade média de navios na fila do porto
c) a quantidade de navios no sistema portuário
d) a quantidade média de navios utilizando o porto
e) o tempo médio que os navios permanecem na fila
f) a taxa de chegada para que o tempo médio dos navios na fila seja de 3
horas
g) a probabilidade do porto estar em uso
Solução
a) probabilidade do porto estar desocupado
p(0) = 1 - 
 = 6 navios/dia
 = 1 navio / cada 3 horas = 8 navios/dia
 =  /  = 6 / 8 = 0,75




1
Nf
2
75,01
75,0 2


navios25,2
c) quantidade média de navios no sistema portuário


-1
Ns 
0,75-1
75,0

navios3
c) quantidade média de navios utilizando o porto
N = Ns - Nf = 3 - 2,25 = 0,75 navios
e) tampo médio em que os navios permanecem na fila



tf
68
75,0


h9dias0,375 
f) taxa de chegada para que os navios permaneçam na fila por 3 horas



tf




tf
 


tf     2
tf
2


tf
21  






tf
p(0) = 1 - 0,75 = 0,25 ou 25%
b) quantidade média de navios na fila
27/07/2016
6











tf
1
2
tf = 3 horas = 0,125 dias








8
125,0
1
82
 dianavios /4
g) probabilidade do porto estar em uso
p(≠0) = 1 - p(0)
p(0) = 1 - 
p(≠0) = 1 - (1 - ) = 
p(≠0) = 0,75 ou 75%
Exemplo 3
Uma distribuidora de combustíveis possui uma única plataforma de embarque
para caminhões. Sabendo-se que os ritmos de chegadas seguem um discreto,
que a taxa de chegada é de 4 caminhões/hora, que a taxa de atendimento é de
5 caminhões/hora e que o custo horário de funcionamento é de R$ 5,00/hora
e do motorista de R$ 25,00/hora, determinar o custo horário do sistema e a
probabilidade do funcionário que abastece ficar ocioso.
Solução:
Número médio de usuários no sistema:


-1
Ns 
 

1
ts
 = 4 / 5 = 0,8
0,8-1
8,0
Ns 
caminhões4
Tempo de permanência no sistema
45
1


hora1
Exemplo 3
Uma distribuidora de combustíveis possui uma única plataforma de embarque
para caminhões. Sabendo-se que os ritmos de chegadas seguem um discreto,
que a taxa de chegada é de 4 caminhões/hora, que a taxa de atendimento é de
5 caminhões/hora e que o custo horário de funcionamento é de R$ 5,00/hora
e do motorista de R$ 25,00/hora, determinar o custo horário do sistema e a
probabilidade do funcionário que abastece ficar ocioso.
Custo horário do sistema:
Sistema: R$ 5,00
Motorista: 4 · 1 · 25,00 = R$ 100,00
Total: R$ 105,00
Probabilidade do sistema estar ocioso:
p(0) = 1 - 
p(0) = 1 - 0,8
p(0) = 0,2 ou 20%
Exemplo 4
Um aeroporto possui uma única pista de pouso e decolagem, e opera com 15
aviões que chegam por hora e gastam, em média 3 minutos para aterrissar e
desocupar a pista. Assumindo que as chegadas são um processo de Poisson e
que o tempo de aterrisagem é distribuído de forma exponencial, determinar a
intensidade de tráfego, o número médio de aviões aguardando a autorização
para pouso e o tempo de espera destes. Determinar o desempenho do
aeroporto se o mesmo tiver a ampliação de uma nova pista que possa operar
conjuntamente.
Solução:
Com uma pista de pouso e decolagem em operação:
 = 15 aviões/h
 = 60 / 3 = 20 aviões/h
Taxa de ocupação do sistema:
 =  /  = 15 / 20 = 0,75
Número de aviões aguardando para pousar:




1
Nf
2
75,01
75,0 2


aviões25,2
27/07/2016
7
Tempo médio de espera:



tf
1520
75,0


min9h0,15 
Desempenho com duas pistas de pouso e decolagem:
c = 2
Taxa de ocupação do sistema:





c 202
15


375,0
Probabilidade do sistema estar ocioso:


r
75,0
4545,0
 
1
1
0 !!
)0(











 
c
n
cn
rcc
rc
n
r
p
 
1
210
75,02!2
75,02
!1
75,0
!0
75,0










Número médio de aviões aguardando para pousar:
 
)0(
!
2
1
p
rcc
rc
Nf
c





 
4545,0
75,02!2
75,02
2
3




aviões1227,0
Tempo médio de espera para o pouso:
   
)0(
!1
2
p
cc
r
tf
c






   
4545,0
15202!12
2075,0
2
2




min0,49h0,0082 