Teoria Filas Transparencia1

Prévia do material em texto

Fernando Nogueira Teoria de Filas 1
Teoria de FilasTeoria de Filas
Agner Krarup Erlang
(*1878, Lonborg, Dinamarca; �1929, Copenhagen, Dinamarca).
Fernando Nogueira Teoria de Filas 2
Introdução
O estudo de Teoria de Filas trata com o fenômeno de aguardar em fila usando medidas
representativas da performance do sistema, tais como comprimento médio da fila,
tempo médio de espera na fila, utilização média do sistema, entre outros.
USA (2001)⇒ estimativa de 37.000.000.000 horas gastas em filas pela população/ano.
Pesquisa realizada nos E.U.A. em 1988, com 6000 pessoas. Fonte: Fitzsimmons e Fitzsimmons (2000).
Fernando Nogueira Teoria de Filas 3
Exemplo de como calcular com incertezas
Dois trens vão ocupar um mesmo terminal de carga. Os horários de chegada, de saída e
de permanência dos trens no terminal são tratados como variáveis aleatórias.
7 .6 8 .4 9 .2 1 0 1 0 .8 1 1 .6 1 2 .4 1 3 .2 1 4 1 4 .8 1 5 .6 1 6 .4 1 7 .2
1 2
G a n tt
h o ra
t
e
r
m
i
n
a
l
( )( ) ( ) ( ) ττ−τ=∗ ∫
∞
∞−
dtgftgf
( )( ) ( ) ( )∑ −=∗
n
nmgnfmgf
A soma de 2 variáveis aleatórias,
f e g, é realizada pela
convolução de f e g:
Contínuo
Discreto
Fernando Nogueira Teoria de Filas 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do horario do trem 1 chegar no terminal: Tc1=8.4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do periodo de terminal: Pt=4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do horario do trem 1 sair do terminal: Ts1 = Tc1 + Pt => Ts1 = conv(Tc1,Pt)=12.4
Fernando Nogueira Teoria de Filas 5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do horario do trem 2 chegar no terminal: Tc2=12.4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do periodo de terminal: Pt=4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do horario do trem 2 sair do terminal: Ts2 = Tc2 + Pt => Ts2 = conv(Tc2,Pt)=16.4
Fernando Nogueira Teoria de Filas 6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do horario do trem 1 sair do terminal: E(Ts1)=12.4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do horario do trem 2 chegar do terminal: E(Tc2)=12.4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.05
0.1
0.15
0.2
distribuição de probabilidade do horario de haver 2 trens (FILA) no terminal: P(fila)=0.37333 E(h.fila)=11.9482
Fernando Nogueira Teoria de Filas 7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do horario do trem 1 sair do terminal: E(Ts1)=12.4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do horario do trem 2 chegar do terminal: E(Tc2)==12.4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do periodo de fila no terminal: E(Tempo.fila)=0.55533
Fernando Nogueira Teoria de Filas 8
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do horario do trem 2 sair do terminal (SEM FILA): Ts2 = Tc2 + Pt => Ts2 = conv(Tc2,Pt)=16.4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do periodo de fila no terminal: E(Tempo.fila)=0.55533
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0
0.2
0.4
0.6
0.8
1
distribuição de probabilidade do horario do trem 2 sair do terminal + FILA: TsF2 = Ts2 + f => TsF2 = conv(Ts2,f)=16.9553
Fernando Nogueira Teoria de Filas 9
Estrutura Básica de um Modelo de Fila
Fonte de Entrada⇒ onde gera-se os clientes.
1)Tamanho da População: finita ou infinita.
2)Distribuição de Probabilidade que os clientes são gerados sobre o tempo (Poisson).
3)Distribuição de Probabilidade do tempo entre chegadas (Exponencial).
obs: 2)⇔ 3) se 2) Poisson e 3) Exponencial
 
Fonte 
 de 
Entrada 
 
Fila 
Mecanismo 
de 
Atendimento 
Clientes Clientes 
Atendidos 
Sistema de Fila 
Disciplina 
da Fila 
Fernando Nogueira Teoria de Filas 10
Fila⇒ onde os clientes aguardam antes de serem atendidos.
1)Número máximo de clientes que a fila pode conter (buffer): finito ou infinito.
Disciplina da Fila⇒ ordem que os clientes em fila são selecionados para atendimento.
First In First Out (FIFO) = First Come First Served (FCFS), Last In First Out (LIFO),
Randômica, Prioridade, entre outras.
Mecanismos de Atendimento (Serviço)⇒ onde o cliente é atendido.
1)Número de instalações de atendimento em série (não necessariamente).
2)Numero de canais de atendimento (servidores) em paralelo para cada inst. de atend.
3)Distribuição de Probabilidade para cada servidor (Exponencial).
 
instalação de 
atendimento 1
Clientes 
Clientes 
Atendidos 
Sistema de Fila 
444 8444 76 Fila
CCCCCC
C
C
C
C
14
13
12
11
S
S
S
S
44 844 76 Fila
CCCC
instalação de 
atendimento 2
C
C
C
23
22
21
s
s
s
Clientes 
Atendidos
 
Fernando Nogueira Teoria de Filas 11
t
f
(
t
)
:
d
e
n
s
i
d
a
d
e
 
d
e
 
p
r
o
b
a
b
i
l
i
d
a
d
e
pdf - Exponencial
λ
0 E(t)=1/ λ 0
0.2
0.4
0.6
0.8
1
t
f
(
t
)
:
p
r
o
b
a
b
i
l
i
d
a
d
e
 
a
c
u
m
u
l
a
d
a
PDF - Exponencial
Distribuição Exponencial
As variáveis aleatórias Tempo Entre Chegadas e Tempo de Atendimento são
modeladas geralmente pela Distribuição Exponencial. Seja t um v.a. com
Distribuição Exponencial com parâmetro λ, então:
( )
λ
=
1
tE ( ) 21tvar λ=
{ }
{ }
( )0t
edteTtP
e1dteTtP
T
T
t
T
T
0
t
≥
=λ=>
−=λ=≤
λ−
∞
λ−
λ−λ−
∫
∫
( )



<
≥λ
=
λ−
0tpara0
0tparae
tf
t
Fernando Nogueira Teoria de Filas 12
Perda de Memória
{ } { }
{ } { }{ }
{ }
{ }
( )
( ) { }TtPee
e
ttP
tTtP
ttP
tttTtP
tttTtP
TtPtttTtP
T
t
tT
>===
∆>
∆+>
=
∆>
∆>∩∆+>
=∆>∆+>
>=∆>∆+>
λ−
∆λ−
∆+λ−
Se agora são 8:20hs e a última chegada ocorreu 8:00hs, a probabilidade que a próxima chegada
irá ocorrer após 8:30hs é função apenas do intervalo entre 8:20hs e 8:30hs (T), ou seja, é
independente do intervalo entre 8:00hs (quando ocorreu a última chegada) e 8:20hs (∆t). Exemplo:
Uma máquina quebra a cada 40 minutos em média com distribuição exponencial. Assim, a taxa
média de quebra é:
A função densidade é:
Se agora são 8:20hs, a probabilidade que a próxima quebra seja até 8:30hs é:
Porém, se agora são 7:00hs, a probabilidade que a próxima quebra seja até 8:30hs é:
hora/quebra5.1
40
60
==λ( ) 0t,e5.1tf t5.1 >= −
22.0e1
60
10
tP 60
105.1
≈−=





 ≤






−
89.0e1
60
90
tP 60
905.1
≈−=





 ≤






−
{ } { }APBAP =∩⇒
B A =
B contém A
A
 
∆t Τ t 
t >∆t+T 
t >∆t 
t >∆t+T ∩ t >∆t 
Fernando Nogueira Teoria de Filas13
Processos de Nascimento e Morte: relação entre Poisson e Exponencial
Processo de Nascimento Puro ⇒ somente chegadas são permitidas. Ex: emissão de
certidão de nascimento.
Processo de Morte Puro ⇒ somente saídas são permitidas. Ex: retirada aleatória de
itens de um estoque.
Tempo entre Chegadas e Tempo entre Saídas possuem distribuição exponencial com
parâmetros λn e µn, respectivamente⇒ Cadeia de Markov em Tempo Contínuo.
Processo de Nascimento Puro
Seja p0(T) a probabilidade de nenhuma chegada durante um período T. Dado que o
Tempo entre Chegadas t é exponencial e que a taxa de chegada é λ clientes por unidade
de tempo, então:
Expandindo p0(T) em Taylor, para um intervalo de tempo h > 0 , porém pequeno, fica:
Considerando que em um intervalo pequeno, no máximo um evento pode ocorrer, então
para h→ 0:
( ) { } { } ( ) TT0 ee11TtP1TtPTp λ−λ− =−−=≤−=≥=
( ) ( ) ( )22h0 hOh1...!2
hh1ehp +λ−=−λ+λ−== λ−
( ) ( ) h)h1(1hp1hp 01 λ=λ−−≈−=
Fernando Nogueira Teoria de Filas 14
Este resultado mostra que a probabilidade de uma chegada durante h é diretamente
proporcional à h com taxa de chegada λ (constante de proporcionalidade).
A distribuição do número de chegadas pn(T) durante um período T, pode ser deduzida
por:
Na primeira equação, n chegadas serão percebidas durante T + h se há n chegadas
durante T e nenhuma chegada durante h, ou n-1 chegadas durante T e uma chegada
durante h. Todas as outras combinações são impossíveis para a distribuição exponencial
(no máximo um evento pode ocorrer para um intervalo de tempo pequeno). Uma vez
que chegadas são eventos independentes, o produto das probabilidades pode ser
aplicado no lado direito das 2 equações acima. Na segunda equação, zero chegadas
durante T + h podem ocorrer somente se nenhuma chegada ocorrer durante T e h. As
derivadas das 2 equações dadas acima são:
( ) ( ) ( ) ( ) ( ) ( )( ) ( )( )
( ) ( ) ( ) ( )( ) 0n,h1.Tphp.TphTp
0n,h.Tph1.Tphp.Tphp.TphTp
0000
1nn11n0nn
=λ−=≈+
>λ+λ−=+≈+
−−
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )



=λ−=−+=′
>λ+λ−=−+=′
→
−→
0n,Tp
h
TphTplimTp
0n,TpTp
h
TphTplimTp
0
00
0h0
1nn
nn
0hn
Fernando Nogueira Teoria de Filas 15
A solução do sistema de equações diferenciais resulta em:
que é a distribuição de Poisson com média chegadas durante T. A variância
é . O resultado mostra que se o Tempo entre Chegadas é Exponencial com
média 1/λ então o número de chegadas durante T é Poisson com média λT.
( ) ( ) ,...2,1,0n,
!n
eTTp
Tn
n =
λ
=
λ−
{ } TTnE λ={ } TTnvar λ=
0 1 2 3 4 5 6 7 8 9 10
0
0.05
0.1
0.15
0.2
0.25
n - numero de chegadas no periodo T = 1
P
r
o
b
a
b
i
l
i
d
a
d
e
Funçao de Probabilidade:Poisson - Lambda = 3
0 1 2 3 4 5 6 7 8 9 10
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
n - numero de chegadas no periodo T = 1
P
r
o
b
a
b
i
l
i
d
a
d
e
 
A
c
u
m
u
l
a
d
a
Funçao Distribuiçao de Probabilidade:Poisson - Lambda = 3
Fernando Nogueira Teoria de Filas 16
Exemplo:
Um terminal de carga recebe caminhões a uma taxa de 1 caminhão a cada 12
minutos. O Tempo entre Chegadas é exponencialmente distribuído.
a)O número médio de caminhões por dia é:
b)O número médio de caminhões por ano é:
c)A probabilidade de nenhum caminhão chegar em um dia é:
d)A probabilidade de chegar 50 caminhões em 3 horas dado que 40 caminhões
chegaram durante as 2 primeiras horas do período de 3 horas é:
Processo de Morte Puro
O sistema possui N clientes e nenhuma chegada é permitida. Atendimentos
ocorrem em uma taxa µ clientes por unidade de tempo. A probabilidade pn(T)
de n clientes permanecerem após T unidades de tempo é:
dia/hoesminca12024*
12
60
==λ
ano/hoesminca43800365*120T ==λ
( ) ( ) 0
!0
e1*1201p
1*1200
0 ≈=
−
( )
( )
( )
( ) ( )
( )( )( )
( ) 018.0!10
e1*51p
!4050
e23*
12
60
23p
1*510
10
1*
12
604050
4050 ≈==
−






−
=−
−
−
−
−
Fernando Nogueira Teoria de Filas 17
( ) ( )( )
( ) ( )( ) ( )( )
( ) ( )( ) ( )( )
( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( )
( )
( ) ( ) ( )∑
=
µ−−
+
+
−==
−
µ
=





µ=′
<<µ+µ−=′
µ−=′
→





µ+=+
<<µ+µ−=+
µ−=+
N
1n
n0
TnN
n
10
1nnn
NN
100
1nnn
NN
Tp1TpN,...,2,1n,
!nN
eTTp
TpTp
Nn0,TpTpTp
TpTp
0hCom
h.Tp1.TphTp
Nn0,h.Tph1.TphTp
h1.TphTp
A solução deste sistema de equações
diferencias resulta na Distribuição de
Poisson Truncada.
Distribuição de Poisson Truncada
Exemplo:
Uma loja de flores recebe 18 buquês de rosas no começo de cada semana.
Em média, a loja vende 3 buquês de rosas por dia sendo que tal demanda
possui distribuição de Poisson. Sempre que o nível do estoque alcança 5
buquês de rosas, um novo pedido de 18 buquês de rosas é feito para ser
entregue no começo da próxima semana. Todo o estoque no fim da semana
(sobra) é perdido.
( )
( )⇒µ
⇒µ−
h
h1
prob. de realizar 0
atendimentos em h
prob. de realizar 1
atendimento em h
Fernando Nogueira Teoria de Filas 18
a) Uma vez que o atendimento é realizado numa taxa µ = 3, a probabilidade de
fazer um novo pedido (quando o estoque chega em 5 buquês) em qualquer dia
da semana é:
( ) ( ) ( ) ( )
( ) ( )
( )
( )∑
=
−
−
≤
=
−
+=
+++=
5
1n
T3n18
0
5105n
7,...,2,1T,
!n18
eT3Tp
Tp...TpTpTp
Gráficos para T = 3
Fernando Nogueira Teoria de Filas 19
b) O número médio de buquês de rosas que serão perdidos no fim de cada
semana é:
{ } ( ) buquês664.7np7tnE 18
0n
n∑
=
==≥
( )7T7t =⇔≥
Gráficos para T = 7
Fernando Nogueira Teoria de Filas 20
Modelo de Fila de Poisson Generalizado
�Processo de Nascimento e Morte combinados (Tempo entre Chegadas e
Tempo entre Saídas possuem distribuição exponencial)
�Modelo é baseado em situação do processo operando sobre condições de
Estados Estavéis (Estados em Fase de Regime, Estados Estacionários).
�O estado do sistema é o número n de clientes no Sistema de Fila.
�Para n > 0 e h → 0, o estado n pode somente mudar para o estado n – 1
quando um atendimento ocorre na taxa µn ou para o estado n + 1 quando uma
chegada ocorreu na taxa λn. Obs: estado 0 só pode mudar para o estado 1
quando uma chegada ocorre na taxa λ0. µ0 não é definido porque nenhum
atendimento pode ocorrer para n = 0.
�Probabilidades pn são obtidas através do Diagrama de Transição de Taxa:
Fernando Nogueira Teoria de Filas 21
Em condições de Estados Estáveis, para n > 0, a taxa esperada de fluxo
entrando e saindo do estado n precisa ser igual. Uma vez que o estado n pode
mudar somente para o estado n – 1 ou n + 1, tem-se:
1n1n1n1n pp
nestadonoentrando
fluxodeesperadataxa
++−− µ+λ=




 ( ) nnn p
nestadodosaindo
fluxodeesperadataxa
µ+λ=





Igualando as 2 taxas, tem-se a seguinte equação de balanço:
( ) 0n,ppe,...2,1n,ppp 1100nnn1n1n1n1n =µ=λ=µ+λ=µ+λ ++−−
Para n = 0, tem-
se:
0
1
0
1 pp 





µ
λ
=
Para n = 1, tem-
se: ( ) 0
12
01
21112200 ppppp 





µµ
λλ
=⇒µ+λ=µ+λ
Por indução:
,...2,1n,p
...
...p 0
11nn
02n1n
n =





µµµ
λλλ
=
−
−−
p0 é determinado através de:
1p
0n
n =∑
∞
=
Fernando Nogueira Teoria de Filas 22
Exemplo 1:
Uma mercearia possui a seguinte regra para definir o número de caixas
operando na loja dependendo do número de clientes:
No de clientes 
na loja
No de caixas 
operando
1 a 3 1
4 a 6 2
+ de 6 3
A Taxa de Chegada, com distribuição Poisson, é 10
clientes/h e o Tempo de Atendimento, comdistribuição Exponencial, é 12 minutos/cliente.
Determine a distribuição de probabilidade pn de n
clientes no Sistema de Fila em condições de
Estados Estáveis.





==
==
==
=µ
==λ=λ
,...8,7n,h/clientes155*3
6,5,4n,h/clientes105*2
3,2,1n,h/clientes512
60
,...1,0n,h/clientes10
n
n
00
3
4
00
3
3
00
2
2
001
p8p
10
10
5
10p
p8p
5
10p
p4p
5
10p
p2p
5
10p
=











=
=





=
=





=
=





=
,...8,7n,p
3
28
p
15
10
10
10
5
10p
p8p
10
10
5
10p
p8p
10
10
5
10p
0
6n
0
6n33
n
00
33
6
00
23
5
=





=


















=
=











=
=











=
−
−
Fernando Nogueira Teoria de Filas 23
p0 é determinado por:
1...
3
2
3
21831p1...
3
28
3
28
3
28888842pp
2
0
32
00 =
















+





+





++⇒=








+





+





+





+++++++
Usando a soma da série geométrica , tem-se:1x,
x1
1
x
0i
i <
−
=∑
∞
=
55
1p1
3
21
1831p 00 =⇒=
























−
+
De posse de p0, pode-se calcular então qualquer probabilidade pn. Por
exemplo, a probabilidade que somente um caixa esteja operando é dada por:
( ) 255.0
55
1842ppp 321 ≈++=++
e o número esperado de caixas ociosos é:
( ) ( ) ( ) caixa1...pp0ppp1ppp2p3 876543210 =+++++++++
Fernando Nogueira Teoria de Filas 24
Terminologia
Fernando Nogueira Teoria de Filas 25
Em condições de Estados Estáveis (não transiente)
Relações entre L, W, Lq e Wq
Fórmula de Little
obs: se
⇒λ= WL
qq WL λ=
λ−≠λ seutilizacten
µ
+=
1WW q
µ
λ
+=⇒
µ
λ
+λ=λ⇒λ





µ
+=λ qqq LLWW
1WW
µ
λ
=−= qLLs
número médio de 
servidores ocupados
s
s
=ρ
Fernando Nogueira Teoria de Filas 26
Exemplo 2:
A taxa de chegada de carros é 6 carros/h com distribuição de Poisson em um
estacionamento que possui 5 vagas. O intervalo de tempo que os carros ficam
estacionados é distribuído exponencialmente com média de 30 min. Os carros
que não encontram uma vaga disponível, podem esperar em uma área
provisória até que algum carro estacionado deixe o estacionamento. Esta área
pode suportar até 3 carros. Demais carros que não conseguem estacionar nem
aguardar na área provisória vão embora.
a) a probabilidade, pn, de ter n carros no sistema:
( )
( )



==
==
=µ
==λ
=
8,7,6n,h/carros1030
605
5,...,2,1n,h/carrosn230
60n
7,...,1,0n,h/carros6
5s
n
n






=
=
=
−
8,7,6n,p
5!5
3
5,...,2,1n,p
!n
3
p
05n
n
0
n
n
1
5!5
3
5!5
3
5!5
3
!5
3
!4
3
!3
3
!2
3
!1
3pp1p...pp 3
8
2
765432
00810 =





++++++++⇒=+++
n 0 1 2 3 4 5 6 7 8
pn .04812 .14436 .21654 .21654 .16240 .09744 .05847 .03508 .02105
Fernando Nogueira Teoria de Filas 27
b) A taxa efetiva de chegada (λeff):
Se 8 carros já estão no estacionamento, então um outro carro não poderá
entrar, assim a proporção de carros que não entrarão é p8.
c) O número médio de carros no estacionamento e na área provisória é:
d) O tempo médio que um carro aguarda na área provisória (Wq) é:
e) O número médio de vagas ocupadas (servidores ocupados) é:
f) O fator de utilização do estacionamento:
 
Fonte Sistema λ 
λeff 
λ lost � λ=λeff + λlost 
h/carro8737.51263.06eh/carro1263.002105.0x6p losteff8lost =−=λ−λ=λ==λ=λ
carros1286.3p8...p1p0L 810 =+++=
hora03265.
2
153265.1WWq =−=µ
−=hora53265.
8737.5
1286.3LW
eff
==
λ
=
vagas9386.2
2
8737.5LLs effq ==µ
λ
=−=
58737.
2*5
8737.5
s
ou58737.
5
9368.2
s
s eff
==
µ
λ
=ρ===ρ
Fernando Nogueira Teoria de Filas 28
Notação (a/b/c):(d/e/f)
a: distribuição do tempo entre chegada (M, D, Ek, G, GI);
b: distribuição do tempo de atendimento (M, D, Ek, G, GI);
c: número de servidores (canais de atendimento);
d: disciplina da fila (FIFO, FCFS, LIFO, Randômica, Prioridade, Qualquer, ...)
e: número máximo de clientes no sistema (finito ou infinito);
f: tamanho da fonte de entrada (finito ou infinito).
onde:
M: Markoviano (Exponencial (tempo)↔ Poisson (taxa));
D: Determinístico (tempo constante);
Ek: Distribuição de Erlang ou Gama↔ soma de distrib. exponenciais independentes
G: distribuição geral (não se sabe nada sobre os tempos de chegada/serviço);
GI: distribuição geral em que os tempos de chegada/serviço são i.i.d..
Exemplos: (M/M/1):(Fifo/∞/∞), (M/D/10):(Rand/20/∞)
Fernando Nogueira Teoria de Filas 29
Modelo (M/M/s):(qq/∞∞∞∞/∞∞∞∞)
λeff = λ ⇒ fila (buffer) infinita 0n,n ≥λ=λ
( )( ) ( )
( )
( ) ( )
( )
( )








≥µλ=
µ
λ
=
µ




 µ
λ
<≤µλ=
µ
λ
=
µµµµ
λ
=
−−
=
∏
sn,p
s!s
p
s!s
p
si
sn0,p
!n
p
!n
p
n...32
p
0sn
n
0nsn
n
0s
1i
n
0
n
0n
n
0
n
n



≥µ
<µ
=µ
sn,s
sn,n
n
( ) ( ) ( )
( ) ( )
( ) 1s,s1
1
!s!n
s!s!n
p
1
s1s
0n
n
1
sn
sns1s
0n
n
0
<
µ
λ












µλ−
µλ
+
µλ
=
=














µ
λµλ
+
µλ
=
−
−
=
−
∞
=
−
−
=
∑
∑∑
( ) ( ) ( ) ( )
( ) ( ) ( )
( )2
0
s
0
s
0k
k
0
s
0k
k
0
s
0k 0k
0
k
s
sk
sn
nq
1!s
p
1
1
d
dp
!sd
dp
!s
d
dp
!s
p
!s
kkppsnL
ρ−
ρµλ
=





ρ−ρ
ρµλ=




 ρ
ρ
ρµλ
=
ρ
ρρµλ=ρµλ==−=
∑
∑∑ ∑∑
∞
=
∞
=
∞
=
∞
=
+
∞
= µ
λ
+= qLL λ
=
q
q
L
W λ
=
LW
obs: (M/M/s) é um caso especifico do Modelo de Fila de Poisson Generalizado.
Modelo de Fila de Poisson Generalizado → independente da disciplina de fila.
{ } ( )( )
( )












µλ−−
−
ρ−
µλ+
=>ω
µλ−−µ−
µ−
1s
e1
1!s
p1
eTp
1sTs
0T { } { }( ) ( )T1sqq e0p1Tp ρ−µ−=ω−=>ω { } ∑
−
=
==ω
1s
0n
nq p0p
01sse =µλ−− ( ) T1se1 1sT µ=µλ−−−⇒ µλ−−µ−
s–1 e não s porque é a probabilidade de um cliente
chegar e não ficar em fila. Se um cliente chegar, quando
já houver s clientes, este ficará na fila.
n=0 e não n=1 porque se nunca
houver fila p{wq=0} = 1 e sem p0 a
somatória não resulta em 1.
Fernando Nogueira Teoria de Filas 30
Exemplo:
Um hospital possui apenas um médico de plantão.Um estudo foi realizado para analisar
a viabilidade de contratar mais um médico plantonista, sendo o intervalo entre chegadas
estimado de 30 min. e o tempo de atendimento estimado de 20 min, ambos distribuídos
exponencialmente.
λ = 2, µ = 3.
De posse dos resultados acima, o hospital entendeu que o tempo aguardado esperado na
fila para um único médico (Wq= 2/3 horas = 40 min.) é grande, fato que justifica a
contratação de mais médico plantonista.
Fernando Nogueira Teoria de Filas 31
Modelo (M/M/s):(qq/N/∞∞∞∞), s ≤≤≤≤ N
Difere do modelo (M/M/s):(qq/∞/∞) no número máximo de clientes no sistema
que é finito e igual a N. O comprimento máximo da fila é Lq = N-s e λeff ≠ λ.



≥
<≤λ
=λ
Nn0
Nn0,
n



≤≤µ
<≤µ
=µ
Nns,s
sn0,n
n
( )
( )
( )




≤≤µλ
<≤µλ
=
−
Nns,p
s!s
sn1,p
!np
0sn
n
0
n
n
( ) ( ) ( ) 1s
0n
N
1sn
snsn
0
s!s!n
p
−
= +=
−














µ
λµλ
+
µλ
= ∑ ∑
( ) ( )( )
( )( )
( )
( )
( )






















µ
λ
−





µ
λ
−−





µ
λ
−
µλ−
µλµλ
=
−−
s
1
s
sN
s
1
s1!s
spL
sNsN
2
s
0
q1
s
Para ≠
µ
λ
( ) ( )( )
0
s
q p!s2
1sNsNL +−−µλ=
( )λ−=λ−λ=λλ=λ NlosteffNlost p1ep
µ
λ
+= effqLL
eff
q
q
L
W
λ
=
eff
LW
λ
=
µ
λ
=ρ
s
eff
1
s
Para =
µ
λ
Mesmo quando (λ/sµ) ≥ 1 o sistema
pode alcançar a condição de estados
estáveis porque λn= 0 para n ≥ N.
Fernando Nogueira Teoria de Filas 32
Exemplo:
Uma companhia de entrega possui 4 caminhões. São observados em média 16 pedidos
de entregas por hora com distribuição Poisson e o intervalo de tempo gasto por entrega
é em média 12 minutos com distribuição Exponencial. Do ponto de vista de Teoria de
Filas, os caminhões são os servidores e os pedidos de entregas são os clientes. A
companhia está estudando a possibilidade de implementar (ou não) a seguinte política:
advertir a pessoa que solicita um pedido de entrega de um potencial atraso excessivo
toda vez que houver 6 pedidos de entrega na fila. Comparar os resultados do modelo
sem e com a implantação da política citada.
λ= 16, µ = 5
Cenário 1: (M/M/4):(qq/∞/∞)⇒ Sem política: Fila (Buffer) infiníta
Cenário 2: (M/M/4):(qq/10/∞)⇒ Com política: Fila (Buffer) finíta, N = 4 + 6 = 10
Fernando Nogueira Teoria de Filas 33
Modelo (M/M/R):(qq/K/K), R ≤≤≤≤ K
Aplicação típica: existem R pessoas para dar manutenção em K máquinas. λ é a taxa em
que as máquinas quebram e µ é a taxa em que as máquinas são reparadas.
Se todas as máquinas estão quebradas não há mais máquinas para quebrarem ⇒
Tamanho da População Finita: λn = (K – n)λ, 0 ≤ n ≤ K.
( )



≥
<≤λ−
=λ
Kn0
Kn0,nK
n



≤≤µ
<<µ
=µ
KnR,R
Rn0,n
n
( )
( ) ( )






≤≤





µ
λ
−
≤≤





µ
λ
−
=
−
KnR,p
R!R!nK
!K
Rn0,p
!n!nK
!K
p
0
n
Rn
0
n
n
( ) ( ) ( )
1
R
0n
K
1Rn
n
Rn
n
0 .R!R!nK
!K
.
!n!nK
!Kp
−
= +=
− 













µ
λ
−
+





µ
λ
−
= ∑ ∑
∑
=
=
K
0n
nnpL ( ){ } ( )LKnKEeff −λ=−λ=λ
eff
q
q
L
W
λ
=
eff
LW
λ
=
µ
λ
=ρ
s
eff
µ
λ
−=
eff
q LL
Fernando Nogueira Teoria de Filas 34
Exemplo:
Uma companhia possui 22 máquinas. Cada máquina quebra, em média, a cada 2 horas,
sendo gastos 12 minutos, em média, para realizar o reparo. O tempo entre quebras e o
tempo de reparo são distribuídos Exponencialmente. Analisar a produtividade da
companhia em função do número de pessoas encarregadas de dar manutenção.
λ= 0.5, µ = 5
22
L22
sdisponiveimáquinas
quebradasmáquinassdisponiveimáquinas
máquinas
adeprodutivid
−
=
−
=





Fernando Nogueira Teoria de Filas 35
Modelo (M/G/1):(qq/∞∞∞∞/∞∞∞∞)
Distribuição do tempo de atendimento é qualquer com média 1/µ e variância
σ2.
Para
1<
µ
λ
=ρ
ρ−=1p0 ( )ρ−
ρ+σλ
=
12
L
222
q λ
=
q
q
L
Wµ
+=
1WW q pn é intratável 
analiticamente
Exemplo:
Um lava-jato recebe, em média, 4 carros por hora com distribuição Poisson e o tempo
de atendimento é 10 minutos por carro com distribuição exponencial se a lavagem é
realizada por um funcionário. Se a lavagem for realizada por uma máquina o tempo de
atendimento é também 10 minutos, porém constante (determinístico ⇒ σ2 = 0).
Comparar as medidas de performance do sistema operando com o funcionário e com a
máquina. λ = 4, µ = 6.
ρ+= qLL
Fernando Nogueira Teoria de Filas 36
nível de serviço
c
u
s
t
o
s
Modelo de Custos para Filas
EOC
EWC
ETC
Nível de
serviço
ótimo 
Modelos de Custos
( ) ( ) ( )
( )
esperadotempodeunidadeporaguardardecustoEWC
esperadosistemadooperaçãodecustoEOC
esperadototalcustoETC
serviçodenívelsoux
:onde
xEWCxEOCxETC
=
=
=
µ=
+=
Geralmente utiliza-se:
( )
( ) LCxEWC
xCxEOC
2
1
=
=
clienteportempodeunidadeporaguardarporcustoC
tempodeunidadeporxdeunidadeporcustoC
:onde
2
1
=
=
Fernando Nogueira Teoria de Filas 37
Exemplo:
Uma gráfica necessita comprar uma copiadora. Existem 4 modelos de copiadoras no
mercado com suas características dada na tabela abaixo. Os Jobs chegam com
distribuição Poisson com média de 4 jobs/dia. O tamanho de cada job é em média de
10000 folhas. Contratos com os clientes da gráfica estipula uma penalidade de $80,00
por job/dia de atraso. Qual copiadora a gráfica deve comprar?
Os valores de C1i são os custos de operação dados na tabela acima. Para fins práticos,
cada copiadora pode ser tratada como um modelo (M/M/1):(qq/∞/∞). A taxa de
chegada é λ = 4 jobs/dia e a taxa de atendimento µi (jobs/dia) é:
Modelo custo de 
operação ($/h) velocidade(cópias/min)
1 15 30
2 20 36
3 24 50
4 27 66 sii1i
ii2i1i
iii
L80C24ETC
LC24CETC
EWCEOCETC
ielomod4,3,2,1i
+=
×+×=
+=
⇒=
Modelo i λλλλi µµµµi Lsi EOCi($) EWCi($) ETCi($)
1 4 30*60*24/10000 = 4.320 12.50 360,00 1000,00 1360,00
2 4 36*60*24/10000 = 5.184 3.39 480,00 271,20 751,20
3 4 50*60*24/10000 = 7.200 1.25 576,00 100,00 676,00
4 4 66*60*24/10000 =9.504 0.73 648,00 58,40 706,40