Teoria das Filas - Parte 4

Prévia do material em texto

1
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
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 da Filas – Parte IV
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 da Filas – Parte IV
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 da Filas – Parte IV
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 da Filas – Parte IV
2
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
É um sistema do tipo M/M/1 com no
máximo “c” consumidores no sistema. Quando
a capacidade “c” do sistema for atingida os
clientes são dispensados e perdidos para o
sistema. Os parâmetros são:
λj = λ para j = 1, 2, ..., c – 1.
µj = µ para j = 1, 2, ..., c.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
A probabilidade do sistema estar vazio é
se ρ ≠ 1 e de p0 = 1/(c + 1) se ρ = 1
A probabilidade de existirem “j” clientes no
sistema é:
pj = 1/(c + 1) se ρ = 1 para 0 < j ≤ c.
se ρ ≠ 1 para 0 < j ≤ c.
pj = 0 para j > c
ρ−
ρ−
=
+1c0 1
1p
ρ−
ρρ−
=
+1
1
1
c
j
j
)(
p
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Combinando o fato de que
com as probabilidades
anteriores, tem-se:
∑=
=
c
0j j
pjL
1. quando c/2L
e
1. quando 
))((
]c)c([
L
c
cc
=ρ=
≠ρ
ρ−ρ−
ρ+ρ+−ρ
=
+
+
11
11
1
1
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Lq = L – Ls = L – (1 – p0) = L – 1 + p0, uma vez que:
E(Nc) = P(N = 0).E(Nc/ N = 0) + P(N > 0).E(Nc/N > 0)
= p0.0 + (1 – p0)x1 = 1 – p0.
Nem todo o trafego para o sistema entra no
mesmo porque os consumidores são rejeitados
quando existem mais do que “c” clientes no
sistema, isto é, com probabilidade pc.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
A determinação de W e Wq a partir do
Teorema 1 é mais complicada. Lembrar que em
L = λW e Lq = λWq, λ representa o número
médio de clientes por unidade de tempo que, de
fato, entram no sistema. Nesse modelo de
capacidade finita λpc das chegadas encontram o
sistema cheio e abandonam o sistema.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Dessa forma λλλλc = λλλλ(1 – pc) chegadas por
unidade de tempo entrarão, de fato, no
sistema. Combinando esses resultados com os
valores de L e W do teorema 1, vem:
e
)p(
LL
W
cc −λ
=
λ
=
1 )p(
LL
W
c
q
c
q
q
−λ
=
λ
=
1
3
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Assim a taxa de utilização do servidor,
ρs, que é a probabilidade de que o servidor
esteja ocupado é dada por:
ρρρρs = λcWs = λλλλ((((1111 – pc)Ws
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Para um sistema M/M/1/GD/c/∞ o
estado estacionário existe mesmo se λ ≥ µ.
Isso ocorre porque mesmo se λ ≥ µ, a
capacidade finita do sistema não permite
que o número de clientes no sistema cresça
sem limites.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Uma barbearia de um único barbeiro
possui um total de 10 assentos. Os tempos são
exponencialmente distribuídos e um total de
20 clientes potenciais chegam a cada hora. Os
clientes que encontram o local cheio não
entram. O barbeiro leva uma média de 12
minutos para barbear cada cliente.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
O tempo de serviço é exponencialmente
distribuído.
1. Na média quantas clientes o barbeiro irá
atender?
2. Na média, quanto tempo cada cliente
gastará na barbearia?
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Uma fração p10 de clientes irá encontrar a
barbearia cheia. Assim uma média de λ(1 – p10)
entrarão na barbearia a cada hora. Todos os
clientes que entrarem serão barbeados. Assim
o barbeiro fará uma média de λ(1 – p10) barbas
por hora.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Do problema tem-se que c = 10, λ = 20
clientes por hora e µ = 5 clientes por hora.
Então ρ = 20/5 = 4 e p0 = (1 – 4)/(1 – 411)
Assim uma média de 20(1 - 3/4) = 5
clientes por hora serão atendidos.
75,0
41
43
41
41
4p 11
10
11
10
10 =
−
−
=





−
−
=
4
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Isso significa que uma média de 20 – 5 = 15
possíveis clientes por hora não irão entrar na
Barbearia.
2. Para determinar W vamos determinar
primeiro L
clientes67,9
)41)(41(
]4104.111[4L 11
1110
=
−−
+−
=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Então:
A barbearia está sempre lotada e o
barbeiro deveria pensar em contratar um
ajudante.
horas 93,1
)4/31(20
67,9
W =
−
=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Um porto que recebe navios graneleiros tem
uma única estação de descarga que permite
descarregar até 5 navios por dia. O porto tem
um cais que permite a ancoragem de apenas 2
navios que quando está ocupado, navios
adicionais que pretendam ancorar são desviados
para outro porto, acarretando um custo de R$
20000 por navio desviado.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
A imobilização de navios no porto tem um
custo de $12000 por dia por navio. As chegadas
dos navios podem ser consideradas como de
Poisson com uma média de 3 navios por dia,
sendo os tempos de descarga exponenciais.
Quer-se avaliar a viabilidade de ampliar o cais
para abrigar 3 navios, onde esta ampliaçãoresultaria num custo adicional de $1000 diários.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
A ampliação será econômica se a redução
dos custos (imobilização + desvio) de navio for
maior do que $1000 por dia.
Custo de imobilização (CI):
$12000Wλc = $12000L dia.
Custo de desvio (CD):
CD = $20000(3 – λc) dia em 3 – λc é o
número de navios desviados diariamente.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Temos então:
λ = 3 navios/dia, µ = 5 navios/dia s = 1,
ρ = 3/5. Vamos calcular os custos com c = 2
e c = 3.
Custos com c = 2.
p2 = 0,184 , 1− p2 = 0,816
λc = λ(1 – pc) = 2,448
L = 0,673 navios
Lq = 0,183 navios
5
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Assim os custos com c = 2, são:
CI + CD = $12000.0,673 + $20000.(3 –
2,448) = $8076 + $11040 = $19116 dia.
Custos com c = 3.
p3 = 0,099 , 1− p3 = 0,901
λc = λ(1 – p3) = 2,703
L = 0,904 navios
Lq = 0,363 navios
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
Custos com c = 3.
CI + CD = $12000.0,904 + $20000.(3 –
2,703) = $10848 + $5940 = $16788 dia.
A redução de custos entre as duas
situações é de: $19166,00 - $16788,00 =
$2378,00 dia > $1000 dia. Assim a ampliação
se justifica.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Teoria da Filas – Parte IV
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.