Teoria das Filas - Parte 3

Prévia do material em texto

Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
A notação utilizada na teoria das filas é
variada mas, em geral, as seguintes são comuns:
λ = número médio de clientes que entram 
no sistema por unidade de tempo;
µ = número médio de clientes atendidos
(que saem do sistema) por unidade de tempo;
L = número médio de clientes no sistema;
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Lq = número médio de clientes na fila;
Ls = número médio de clientes sendo atendidos;
W = tempo médio que o cliente fica no sistema;
Wq = tempo médio que o cliente fica na fila;
Ws = tempo médio que um cliente leva para ser 
atendido.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
W(t) = a probabilidade de que um cliente fique
mais do que um tempo t no sistema;
Wq(t) = a probabilidade de que um cliente
fique mais do que um tempo t na fila.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Para um sistema de filas está em estado 
estacionário, tem-se: L = λW Lq =λWq Ls = λWs
L é expresso em número de clientes, λ é
expresso em termos de clientes por hora e W é
expresso em horas. Assim λW tem a mesma 
unidade (clientes) de L. 
As três equações acima são válidas para 
qualquer sistema de filas.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
É um sistema com tempos interchegadas 
exponencialmente distribuídos de parâmetro
λ e tempo de serviço exponencialmente 
distribuídos com parâmetro µ e com “s”
servidores atuando em paralelo e uma única 
fila de clientes. Se j ≤ s clientes estiverem no 
sistema então todos estarão sendo atendidos.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Se j > s clientes estiverem no sistema então 
j – s clientes estarão esperando na fila. 
Qualquer cliente que chegar e encontrar um 
servidor ocioso será atendido imediatamente e 
aqueles que não encontrarem servidores livres 
entrarão na fila esperando para serem 
atendidos.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Bancos e correios na qual todos os clientes 
esperam numa fila única são muitas vezes 
representados por esse tipo de modelo.
Para descrever esse tipo de modelo da 
mesma forma como os demais será suposto 
que:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
λj = λ para j = 0, 1, 2, 3, …
Se j servidores estiverem ocupados então a 
finalização do serviço ocorre a uma taxa de 
µ + µ + … + µ = jµ
Sempre que j clientes estiverem presentes o 
min(j, s) servidores estarão ocupados. Assim:
µj = min(j, s)µ.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Resumindo então esse modelo pode ser 
representado como um processo de 
nascimento e morte com os seguintes 
parâmetros:
λj = λ para j = 0, 1, 2, 3, …
µj = jµ para j = 0, 1, 2, …, s
µj = sµ para j = s, s + 1, s + 2, …
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Define-se ρ = λ/(sµ) para ρ < 1, então:
e
∑ ρ−
ρ
+
ρ
=
−
=
1s
0i
si0
)1(!s
)s(
!i
)s(
1
p
s ..., 2, 1, j para 
!j
0
j
j
p)s(
p ==
ρ
... 2,s 1,s s, j para 
!s
0Ps
j
 
sj!s
0P
j)s(
j
s
s
p ++=ρ=
−
ρ
=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Se ρ ≥ 1, então não existe um estado 
estacionário. Em outras palavras se a taxa de 
chegadas é igual ou maior a taxa de serviço 
λ ≥ sµ então o sistema não dará mais conta.
Pode ser mostrado que, a probabilidade 
do estado estacionário, quando todos os 
servidores estão ocupados é dado por:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
que é a probabilidade de que um 
consumidor tenha que entrar na fila. Essa 
probabilidade é bastante utilizada em 
telefonia e é conhecida como fórmula C de 
Erlang. 
)1(!s
p)s(
)sj(P 0
s
ρ−
ρ
=≥
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
O tempo de espera médio na fila é dado 
por: 
Então: 
ρ−
ρ≥
=
1
)sj(P
Lq
λ−µ
≥
=
λ
=
s
)sj(PL
W
q
q
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Para determinar L (e então W) utiliza-se 
o fato de que L = Lq + Ls. Uma vez que Ws = 
1/µ, utilizando o Teorema um, segue que:
Ls = λ/µ e então: L = Lq + λ/µ.
Também:
W = L/λ =
µ
+
λ−µ
≥
=
µ
+=
µ
+
λ
1
s
)sj(P1
W
1L
q
q
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
W(t) = a probabilidade de que um cliente
fique mais do que um tempo t no 
sistema;
Wq(t) = a probabilidade de que um cliente
fique mais do que um tempo t na fila.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III








ρ−−
−
≥+=
=








ρ−−ρ−
−
+=
ρ−−µ−
µ−
ρ−−µ−
µ− ρ
)s1s(
]1[)sj(P1 
)s1s)(1(!s
]1[
1)t(W
e
e
ep)s(
e
)s1s(t
t
)s1s(t
0
s
t
ee
p)s(
W )1(ts)1(ts0
s
q )sj(P)1(!s)t(
ρ−µ−ρ−µ− ≥=
ρ−
=
ρ
Quando s -1 = sρ ]t)sj(P1[)t(W e t µ≥+= µ−
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Considere um banco com dois caixas. 
Uma média de 80 clientes por hora chegam 
ao banco e esperam na fila para serem 
atendidos. Cada caixa leva na média 1,2 
minutos para atender um cliente. 
Determine:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
1. O número esperado de clientes no banco?
2. O tempo médio gasto por cliente no banco?
3. A fração de tempo que um caixa está livre?
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Temos um sistema M/M/2 com λ = 80 
clientes por hora e µ = 50 clientes por hora. 
Assim ρ = 80/2.50 = 0,80 < 1 e portanto existe 
um estado estacionário. Para λ ≥ 100 nenhum 
estado estacionário irá existir. 
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
A probabilidade de o sistema estar vazio 
é dado por:
Então: 
7111,0
9
4,6
)80,01(!2
)9/1()8,0.2(
)1(!s
p)s(
)sj(P
2
0
s
==
−
=
ρ−
ρ
=≥
9
1
4,0
6,1
6,11
1
)8,01(!2
)8,0.2(
8,0.21
1
)1(!s
)s(
!i
)s(
1
p
221s
0i
si0
=
++
=
−
++
=
∑ ρ−
ρ
+
ρ
=
−
=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de EstatísticaCurso: Engenharia de Produção
Teoria das filas – Parte III
1. 
2. Tem-se L = Lq + λ/µ = 2,84 + 80/50 = 4,44 
clientes. Então: W = 4,44/80 = 0,0556 horas = 
= 3,33 minutos.
3. Para determinar o tempo que um atendente 
está livre é preciso considerar que isso irá
ocorrer sempre que j = 0 e na metade do
clientes 84,2
8,01
8,0.7111,0
1
)sj(P
Lq =
−
=
ρ−
ρ≥
=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
tempo (por simetria) em que j = 1. Então a 
probabilidade de eque o servidor esteja livre é
dada por p0 + 0,5p1. Como p0 = 1/9, basta 
determinar p1. Tem-se p1 = (sρ)jp0/j! e, então
p1 = (2.0,8)(1/9)/1 = 8/45 = 0,1777.
Assim a probabilidade de que um atendente 
esteja livre é: (1/9) + 0,8/9 = 1,8/9 = 0,20 = 20% 
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
O gerente de um banco quer determinar 
quantos caixas devem trabalhar nas sextas 
feiras. Para cada minuto que um cliente gasta 
na fila o gerente estima um custo de $ 0,25. 
Uma média de dois clientes por minuto chegam 
ao banco. 
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Na média um caixa atende um cliente a 
cada 2 minutos. O banco tem um custo de 
$ 9,00 a hora para contratar um caixa. Para 
minimizar a soma dos custos quantos 
caixas o banco deve manter trabalhando 
nas sextas?
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Temos um sistema M/M/s com λ = 2 
clientes por minuto e µ = 0,5 clientes por 
minuto. Assim ρ = (λ/sµ) < 1 requer que 
(4/s) < 1 para que o sistema esteja em equilíbrio. 
Assim s ≥ 5. Isto é, deve existir pelo menos 5 
caixas para que a fila não vá para o infinito.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Vamos calcular agora os custos para
s = 5, 6, …
Custos = (Serviço + Espera) por minuto.
Custo de serviço = 9/60 = $ 0,15, já que 
cada caixa ganha $ 9,00 a hora.
Custo de espera = (Número esperado de 
clientes/minuto).(custo de espera/cliente)
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Mas: custo de espera/cliente = 0,05Wq.
Como chegam 2 clientes, em média por 
minuto: 
Custo de espera = 2.0,05Wq = 0,10Wq.
Para s = 5, ρ = 2/0,5.5 = 0,80 e P(j ≥ 5) = 0,55.
Ainda Wq = Lq/λ = P(j ≥ s)/(sµ – λ) =
= 0,55/(5.0,5 – 2) = 1,1 minutos.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Assim para s = 5
Custo de espera/minuto = 0,10.1,1 = $ 0,11 e
Custo total = 0,15.5 + 0,11 = $ 0,86.
Como s = 6 tem um custo de serviço de 
6.0,15 = $ 0,90 por minuto, 6 caixas não tem um 
custo menor do que 5 caixas. Assim 5 caixas é o 
número ótimo.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
Colocando de outro forma: adicionar 
um caixa pode poupar no máximo 11 
centavos por minuto em custos de espera, 
mas como um caixa custa 15 centavos por 
minuto, não é vantajoso contratar mais do 
que cinco caixas.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria das filas – Parte III
GRIMMETT, G. R., SITRZAKER, D. R. 
Probability and Random Processes. Oxford 
(London): Oxford University Press, 1991.
KLEINROCK, Leonard. Queueing Systems: v. 1: 
Theory. New York: John Wiley, 1975.
WISTON, Wayne L. Operations Research: 
Applications and Algorithms. 3 ed. Belmont
(CA): Duxbury Press, 1994.