Teoria das Filas - Parte 1

Prévia do material em texto

1
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Por que aparecem as filas?
Não é eficiente, nem racional, que cada um
disponha de todos os recursos individualmente.
Por exemplo:
que cada pessoa disponha do uso exclusivo de
uma rua para se movimentar;
que cada pessoa tenha um supermercado para o
seu abastecimento exclusivo;
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Recursos limitados devem ser
compartilhados.
Ao compartilhar recursos, pode acontecer
que no momento em que se queira fazer uso
de um recurso, este esteja ocupado;
necessidade de esperar
aparecem as filas
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Um fluxo é o movimento de alguma
entidade através de um ou mais canais de
capacidade finita para ir de um ponto a
outro.
Capacidade finita significa que o canal só
pode satisfazer a demanda a uma taxa finita.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Exemplos:
� fluxo de automóveis (entidades)
através de uma rede de caminhos
(canais)
� transmissão de mensagens telefônicas
(entidades) através da rede (canal)
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Os fluxos podem ser classificados em:
� Determinísticos: sistemas no qual o
comportamento da demanda pelo serviço é
previsível;
� Aleatório: não é possível predizer como
vai se comportar a demanda pelo serviço.
2
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Para descrever um sistema de filas
um processo de entrada e um de saída
devem ser especificados. Alguns
exemplos podem ser vistos na tabela
seguinte:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Sistema Entrada Saída
Banco Correntistas Atendentes
Pizzaria 
on-line
Requisição de
pizza
Atendente envia
motoqueiro com a pizza
Pedágio Automóveis Atendente cobra e libera o
veículo
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
A entrada é geralmente denominada de
processo de chegada. Chegadas são
denominadas de clientes. Em todos os
sistemas será assumido que não mais do que
uma chegada pode ocorrer em um único
instante.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Será assumido que o processo não é
afetado pelo número de clientes no sistema. Se
o processo de chegada não é afetado pelo
número de consumidores presentes ele é
descrito pela especificação de uma distribuição
de probabilidade para os tempos inter
chegadas sucessivas.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Para descrever o processo de saída
(processo de atendimento) de um sistema de
filas é normalmente especificado uma
distribuição de probabilidade – distribuição
do tempo de serviço – que fornece o tempo de
atendimento dos clientes.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Em muitas situações será assumido que o
tempo de atendimento é independente do
número de clientes presentes. Geralmente dois
regimes de atendimento são considerados: em
série e em paralelo.
3
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Regimes de atendimento
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
O serviço é paralelo se todos os atendentes
fornecem o mesmo tipo de atendimento e o
cliente só precisa passar por um atendente. Ele
é em série se o cliente precisa passar por vários
atendentes antes de ter seu serviço completado.
Uma linha de montagem é um exemplo de tal
tipo de serviço.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
A disciplina da fila descreve o método
usado para determinar a ordem em que os
consumidores serão atendidos. O método mais
comum é o FIFO (First In First Out) em que os
clientes são atendidos pela ordem de chegada.
Outro métodos é o LIFO (Last In FirstOut).
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Em alguns casos a ordem em que os
clientes chegam não faz diferença é o método
SIRO (Service In Randon Order). Um último
método de atendimento é o atendimento por
prioridade que classifica cada cliente de
acordo com a maior ou menor necessidade de
atendimento.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Outro fator que deve ser considerado é o
processo que um cliente utiliza para decidir
em qual fila ele vai entrar. Por exemplo em
alguns bancos o cliente deve entrar numa fila
única. Quando existem várias ele vai optar
pela mais curta.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Na maioria das aplicações de filas
deve-se tentar refletir a realidade e
mantê-la computacionalmente tratável,
assim a escolha mais comum é a
distribuição Exponencial.
4
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção



<
≥λ
=
λ
0 t se 
t se e.
)t(f
t
0
0-
Uma variável aleatória T tem uma
distribuição exponencial de parâmetro λ se sua
fdp for do tipo:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Considere que a duração, em minutos,
seja uma VAC exponencial com duração média
de µ = 10. Se alguém chegou justo na sua
frente na cabine telefônica, determine a
probabilidade de que você tenha que esperar
mais do que 10 minutos.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
[ ]
%,,e
)e(elim
dte,)X(P
t,
t
t,
793636790
1010
1
110
10
10
===
=−−=
=∫=≥
−
−−
∞→
∞
−
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
0,0
0,5
1,0
1,5
2,0
1 11 21 31 41 51 61 71 81 91 101
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
A função F(t) = P(T ≤ t) é dada por:
 
 0 t se e-1
0 < t se 0
)t(F
t-



≥
=
λ
Obs.: Tente determinar!
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
0,00
0,10
0,20
0,30
0,40
0,50
0,60
0,70
0,80
0,90
1,00
0 1 2 3 4 5 6 7 8 9 10
5
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
λ
=





λ
−−
=∫+−=
=∫ λ=∫=
λ−
λ−
∞
∞ λ−λ− ∞
∞ λ−+∞
∞−
1e
et
dte]et[
dte.tdt)t(f.t)T(E 
t
t
0
0
tt
0
0
t
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
σ2 = V(T) = E(T2) – E(T)2
λ
=
λλ
=∫ λλ
=
=∫+−=
=∫ λ=∫=
∞ λ−
∞ λ−λ− ∞
∞ λ−+∞
∞−
20
t
0
tt2
0
0
t222
21
.
2
dtet
2
dtte2]et[
dte.tdt)t(f.t)T(E 
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
A variância será então:
λ
=
λ
−
λ
=





λ
−
λ
=
=−==σ
222
2
2
222
11212
)T(E)T(E)T(V 
E o desvio será:
λ
=σ
1Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Assim se T tem uma distribuição exponencial, 
então:
λ
1
σ
λ
1)T(E)T(E)T(Vσ
λ
1)T(Eµ
ee)t(F)t(F)tTt(P
e)tT(P
e1)tT(P)t(F
eλ f(t)
2
222
λ-λ-
1221
tλ-
tλ-
tλ-
t2t1
=
=−==
==
−=−=≤≤
=>
−=≤=
=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Seja T uma VAC com distribuição
exponencial de parâmetro λ. Determinar o
a probabilidade de T assumir valores
superiores ao seu valor esperado.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
%79,36 3679,0 e 
]e1[1)µ(F1)µX(P
1
λt
===
=−−=−=≥
−
−
6
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Um dos motivos da utilização da
Exponencial na teoria das filas é a sua
propriedade de falta de memória:
P(T > t + h/ T ≥ t) = P(T > h)
Para quaisquer valores não negativos de
t e h.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Pode ser mostrado que nenhuma
outra VAC tem esse mesmo tipo de
propriedade. Essa propriedade é
denominada de falta de memória da
variável.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Isto significa que se sabemos que
um tempo t transcorreu desde a
última chegada então a probabilidade
de transcorra um tempo h até a
próxima chegada não depende de t.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Assim se quisermos saber o tempo
para a próxima chegada não importa há
quanto tempo tenha ocorrido a última
chegada. Essa propriedade pode
simplificar a análise dos sistemas de filas.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Se o tempo entre chegadas é
exponencial então a distribuição do
número de chegadas em qualquer
intervalo de tempo t é dado pelo seguinte
teorema:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Tempos interchegadas são
exponenciais com parâmetro λλλλ se e só se o
número de chegadas que ocorre num
intervalo de tempo t segue uma
distribuição de Poisson com parâmetro λλλλt.
7
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Uma VAD X tem uma distribuição de
Poisson com parâmetro λλλλ se, para x = 0, 1, 2, ...,
a probabilidade de P(X = x) é dada por:
f(x) = P(X = x) = (e-λλλλλλλλx)/x!
para x = 0, 1, 2, …
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Se X tem uma distribuição de Poisson
com parâmetro λλλλ então, tem-se que:
E(X) = V(X) = λλλλ
Assim: λ=σ
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Se definirmos x como o número de
chegadas que ocorrem durante
qualquer intervalo de tempo t, então o
teorema diz que:
P(Xt = x) = [e
-λt(λt)x]/x!
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Como Xt tem uma distribuição de Poisson
com parâmetro λλλλt então:
E(Xt) = V(Xt) = λλλλt
Uma média de λλλλt chegadas ocorre durante
um intervalo de tempo t, assim λλλλ pode ser
pensado como o número médio de chegadas
por unidade de tempo ou taxa de chegadas.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Para que a taxa de chegadas seja
considerada exponencial algumas hipóteses
devem ser satisfeitas:
1. Chegadas sobre intervalos de tempo não
sobrepostos são independentes;
2. Para valores de t pequenos, a probabilidade
de uma chegada é proporcional ao tamanho
do intervalo.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Se as condições 1 e 2 forem
verdadeiras então:
Xt segue uma distribuição de Poisson
com parâmetro λλλλt onde os tempos
interchegadas são exponenciais de
parâmetro λλλλ.
8
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Em resumo: se a taxa de chegadas é
estacionária e chegadas passadas não afetam as
futuras, então os tempos interchegadas seguem
uma distribuição exponencial com parâmetro λλλλ
e o número de chegadas em qualquer intervalo
de tempo t é Poisson com parâmetro λλλλt.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Se o tempo interchegadas não é
exponencial, então ele pode ser modelado pela
distribuição de Erlang. Uma distribuição de
Erlang é uma VAC cuja fdp depende de dois
parâmetros: r = taxa e k = forma (que deve ser
um inteiro positivo). Dados os parâmetros r e k
a fdp da Erlang é dada por:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Uma VAD T tem uma distribuição de
Erlang de parâmetros r e k
f(t) = [r(rt)k-1e-rt]/(k – 1)! para t ≥ 0
Obs. A distribuição de Erlang será
representada por E(r, k).
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
A distribuição de Erlang é
um caso particular da
distribuição Gama.
Agner Krarup Erlang (1878 –
1929), engenheiro dinamarquês que
utilizou a teoria da Probabilidade
para modelar e resolver problemas
de telefonia.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Utilizando integração por partes podemos
mostrar que se T tem uma distribuição de
Erlang com parâmetros r e k, então:
E(T) = k/r
V(T) = k/r2
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
DANTAS, Carlos Alberto Barbosa. Probabilidade: Um
Curso Introdutório. 2 ed. São Paulo: EDUSP, 2000.
GRIMMETT, G. R., SITRZAKER, D. R. Probability
and Random Processes. Oxford (London): Oxford
University Press, 1991.
WISTON, Wayne L. Operations Research:
Applications and Algorithms. 3 ed. Belmont (CA):
Duxbury Press, 1994.