Teoria das Filas - Parte 5

Prévia do material em texto

1
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
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
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
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
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
2
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
É um sistema do tipo M/M/s 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:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
A taxa de entrada (chegadas) no sistema
será:
λj = λ para j = 1, 2, ..., c – 1.
= 0 se j ≥ c.
A taxa de saída do sistema será:
µj = jµ para j = 1, 2, ..., s - 1.
= sµ para j = s, s + 1, …, c.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Este modelo corresponde ao sistema
M/M/s já estudado anteriormente, só que
agora existe perda, pois o (k+1)-ésimo
cliente não poderá entrar no sistema pois ele
se encontra lotado.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Neste caso, será considerado que s > 1 (o
caso s = 1 já foi estudado) e que s < c, pois se
s ≥ c, o tempo de espera para os clientes que
entram no sistema é zero. A taxa de saída do
sistema dependerá do estado do sistema. A
população é suposta infinita e a disciplina da
fila é FIFO.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
A taxa média de entrada no sistema é:
onde pc é a probabilidade de o sistema estar
cheio.
As probabilidades pj de existirem “j”
clientes no sistema são obtidas por:
)p1(λpλpλλ c
1c
0j j
1c
0j j
m −=∑=∑=
−
=
−
=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Como ρ = λ/sµ então:











>
=





=





=
−
c j se 0 
c ..., s, j se p
µ
λ
s!s
1
 
1-s ..., 1, 0, j se p
µ
λ
!j
1
 
 p 0
j
0
j
j sj
3
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Desta forma:











>
=
=
=
ρ
ρ
c j se 0 
c ..., s, j se 
!s
 
1-s ..., 1, 0, j se 
!j
 
 ps
p
)s(
p 0
js
0
j
j
)p
!s
ρs1(λ)p1(λλ 0
cs
cm −=−=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Quando ρ ≠ 1, tem-se:








ρ−
−
+=
=








ρ−
−
+=
+=+=
ρρ
∑
ρ
ρρ∑
ρ
∑ ρ∑ ρ∑ ρ∑ ρ
+−
−
=
+−
−
=
=
−
==
−
=
−
1
1
!s!j
 
1
1
!s!j
 
!s!j!s!j
1scs1s
0j
j
1sc
s
s1s
0j
j
c
sj
j
s1s
0j
jc
sj
j
1s
0j
j
1
0
)s()s(
s)s(
s)s(s s)s(p
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Quando ρ = 1, temos:
)1sc(
!s!j
 
1
!s!j!s!j
)
ss
ssss(p
s1s
0j
j
c
sj
s1s
0j
jc
sj
j
1s
0j
j
1
0
s
+−+=
+=+
ρ
=
∑
∑∑∑
ρ
∑
−
=
=
−
==
−
=
−
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Resumindo, tem-se:











=ρ
≠ρ
=








+−+∑
















ρ−
ρ−ρ
+∑
ρ
−
=
+−
−
=
−
−
1 se 
1 se 
)1sc(
!s
s
!j
s
1
1
!s
)s(
!j
)s(
p
s1s
0j
j
1scs1s
0j
j
1
1
0
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Do tamanho médio da fila do sistema
M/M/s tem-se:
∑
+=
−=
c
1sj
jq
pL )sj(
Então, para este caso:








ρ−
−
ρ
=
ρ
==
=−=−=
ρρ∑ρρ∑ ρρ
∑ ρρ∑ ρ
+−
+
−
=
+
−
=
−+
+=
−−+
+=
1
1
d
d
!sd
d
!s
j
!s
 
)sj(
!s!s
)sj(
1sc
1s
s
0
sc
0j
j1s
s
0
sc
1j
1j1s
s
0
c
1sj
1sj1s
s
0
c
1sj
0
js
q
spspsp
sppsL
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Então, para este caso, isto é, ρ ≠ 1:
}1{
!s
 
1
!s
 
sssk1
!s
 
1)1sc(
!s
 
)]sc)(1(1[
)1(
sp0
)1(
)]sc)(1(1[sp
)1(
sp
)1(
)1(spL
sc
2
1ss
2
sc
1s
s
0
2
1scsc1scscsc
1s
s
0
2
1scsc
1s
s
0q
ρ−ρ−+
ρ−
ρ
ρ−
ρ−ρ−+ρ
ρ−
ρρρρρρ
ρ−
ρρρ−ρ
−
+
−
+
+−−+−−−
+
+−−
+
−=








−
=








−++−−
=
=








−++−−
=
4
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Quando ρ = 1, tem-se:
2
)1sc)(sc(
!s
j
!s
 
)sj(
!s!s
)sj(
spsp
sppsL
s
0
sc
1j
s
0
c
1sj
s
0
c
1sj
0
s
q
+−−
==
=−=−=
∑
∑∑
−
=
+=+=
Então, juntando os dois resultados, temos:








=ρ+−−
≠ρ−
=
ρ−ρ−+
ρ−
ρ
−
+
1 se 
2
)1sc)(sc(
!s
1 se }1{
!s 
sp
)]sc)(1(1[
)1(
sp
L
s
0
sc
2
1ss
q
0
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
O número médio de clientes no sistema
quando ρ ≠ 1 é, a exemplo do sistema M/M/s:
ps)]sc)(1(1[
)1(
sp0
ps)]sc)(1(1[
)1(
sp0
sp
)]sc)(1(1[
)1(
sp0mLq
0
1c1s
sc
2
1ss
0
cs
sc
2
1ss
cs
0
sc
2
1ss
!s
s}1{
!s
 
!s
1s}1{
!s
 
!s
1
}1{
!s
 L
ρρ−ρ−+
ρ−
ρ
ρρ−ρ−+
ρ−
ρ
ρ
ρ−ρ−+
ρ−
ρ
µ
λ+
++
−
+
−
+
−
+
−ρ+−=








−ρ+−=
µ








−λ
+−==
Prof. Lorí Viali, Dr. – PUCRS– FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
ρ+−=
ρ+−=
ρ++−=
ρ+−−=
ρρ−ρ−+
ρ−
ρ
ρρ−+−ρ−+
ρ−
ρ
ρ−ρ−ρ−+
ρ−
ρ
ρ−ρρ−ρ−+
ρ−
ρ
−
+
−
+
−
+
−−
+
s}1{
!s
 
s}1{
!s
 
s}s1{
!s
 
s}s1{
!s
 L
)]sc)(1(1[
)1(
sp
))]1(ssc)(1(1[
)1(
sp
)1()]sc)(1(1[
)1(
sp
)1()]sc)(1(1[
)1(
sp
sc
2
1s
0
s
sc
2
1s
0
s
2sc
2
1s
0
s
2scsc
2
1s
0
s
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Quando ρ = 1, tem-se:
s
!s2
s)1sc)(sc(
 
!s
s
!s2
)1sc)(sc(
 
!s
1s
!s2
)1sc)(sc(
 L
sp0
sp0sp0
sp0sp0mLq
s
1ss
ss
+
−+−−
=
−+
+−−
=










−+
+−−
==
+
µ
λ+
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Então, juntando os dois resultados, temos:
 
1 se s
!s2
s)1sc)(sc(
1 se s}1{
!s
 L
sp0
)]sc)(1(1[
)1(
sp0
s
sc
2
1ss








=ρ+
−+−−
≠ρρ+−
=
ρρ−ρ−+
ρ−
ρ
−
+
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Tempo médio de espera na fila, quando ρ ≠ 1.
)]}sc)(1(1[1{
)!s(
 
!s
-1
)]}sc)(1(1[1{
!s
 
!s
-1
)]}sc)(1(1[1{
!s 
sc
0
cs2
s
0
1s
cs
0
sc
2
s
0
1s
cs
0
sc1s
s
0
m
q
q
ps)1(
sp
sp
)1(
sp
sp
spL
W
−ρ−+−
−µ
=








µ
−ρ−+−
=








λ
−ρ−+−
==
ρ
ρρ−
ρ
ρ
ρ
ρ−
ρ
ρ
ρρ
λ
−
−
−
−
−+
5
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Tempo médio de espera na fila, quando ρ = 1.
)!s(2
)1sc)(sc(
 
!s
-1s
!s2
)1sc)(sc(
 
!s
-1
!s2
)1sc)(sc(
 
ps
sp
sp
sp
sp
spL
W
0
s
0
1s
s
0
s
0
s
0
s
0
m
q
q
−µ
+−−
=








µ
+−−
=







λ
+−−
==
−
λ
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Resumindo os dois resultados, tem-se:









=ρ
−µ
+−−
≠ρ−ρ−+−
−µ
=
−
−
−
ρ
ρρ−
ρ
1 se 
)!s(2
)1sc)(sc(
1 se )]}sc)(1(1[1{
)!s(
ps
sp
ps)1(
sp
W
0
s
0
1s
sc
0
cs2
s
0
1s
q
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
O tempo de espera no sistema é dado por:
λ
=
µ
+=
m
q
L1
W W
Assim quando ρ ≠ 1, tem-se:
µ
+−ρ−+−
−µ
=
µ
+= ρ
ρρ−
ρ
−
−
1
)]}sc)(1(1[1{
)!s(
1
W sc
0
cs2
s
0
1s
q ps)1(
sp
W
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Assim quando ρ = 1, tem-se:
µ
+
−µ
+−−
=
µ
+=
−
1
)!s(2
)1sc)(sc(1
W
ps
sp
W
0
s
0
1s
q
Resumindo, tem-se:









=ρ
µ
+
−µ
+−−
≠ρ
µ
+−ρ−+−
−µ
=
−
−
−
ρ
ρρ−
ρ
1 se 
1
)!s(2
)1sc)(sc(
1 se 
1
)]}sc)(1(1[1{
)!s(
W
ps
sp
ps)1(
sp
0
s
0
1s
sc
0
cs2
s
0
1s
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
A probabilidade de o tempo de espera
na fila ser zero P(T = 0) é a probabilidade de
o sistema ter s - 1 clientes. Assim:
∑
ρ
∑
−
=
−
=
===
1s
0j
0
j1s
0j
j p
)s(
p
!j
)0T(P
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Considere um salão de beleza com três
cabeleireiros trabalhando. Uma média de 15
clientes por hora chegam ao estabelecimento
para serem atendidos. Cada cabeleireiro leva
em média 15 minutos para atender um cliente.
A capacidade do salão é de 12 clientes por hora.
6
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Os clientes que não encontram lugar
abandonam o salão e vão procurar atendimento
em outro local. Determine:
(i) O número médio de clientes que entram no
salão.
(ii) O tamanho médio da fila.
(iii) O tempo médio de espera na fila.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Temos um sistema M/M/3/12 com
λ = 15 clientes por hora e µ = 4 clientes por
hora. Assim ρ = 15/3.4 = 1,25. Tem-se
ainda que s = 3 e c = 3.4 = 12.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
(i) O número médio de clientes que entram
no salão será:
Então λm = 15(1 – 0,215376) = 11,77.
Portanto 3,23 clientes, por hora, são
perdidos.
)p
!s
ρs1(λ)p1(λλ 0
cs
cm −=−=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
(ii) O tamanho médio da fila é dado por:
Então Lq = 5,96 clientes.
1 quando }1{
!s
0 )]sc)(1(1[
)1(
sp
L
sc
2
1ss
q ≠ρ−= ρ−ρ−+ρ−
ρ
−
+
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
(iii) O tempo médio de espera na fila é dado por:
Então Wq = 0,51 horas = 30,40 minutos.
1 se )]}sc)(1(1[1{
)!s(
s
0 sc
0
cs2
1s
q
ps)1(
sp
W ≠ρ−ρ−+−
−µ
= ρ
ρρ−
ρ
−
−
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
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.