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
Curso: Engenharia de Produção
ser
Um fluxo é o movimento de alguma
compartilhados.
Ao compartilhar recursos, pode acontecer
que no momento em que se queira fazer uso
de um recurso, este esteja ocupado;
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ó
necessidade de esperar
pode satisfazer a demanda a uma taxa finita.
aparecem as filas
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Curso: Engenharia de Produção
Exemplos:
fluxo
de
Os fluxos podem ser classificados em:
automóveis
(entidades)
Determinísticos:
sistemas
no
qual
o
através de uma rede de caminhos
comportamento da demanda pelo serviço é
(canais)
previsível;
transmissão de mensagens telefônicas
(entidades) através da rede (canal)
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Aleatório: não é possível predizer como
vai se comportar a demanda pelo serviço.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
1
Curso: Engenharia de Produção
Curso: Engenharia de Produção
Sistema
Para descrever um sistema de filas
Entrada
Saída
Banco
Correntistas
um processo de entrada e um de saída
Pizzaria
Requisição
devem
on-line
pizza
motoqueiro com a pizza
Pedágio
Automóveis
Atendente cobra e libera o
ser
especificados.
Alguns
exemplos podem ser vistos na tabela
Atendentes
de Atendente
envia
veículo
seguinte:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Curso: Engenharia de Produção
Será assumido que o processo não é
A entrada é geralmente denominada de
processo
de
denominadas
chegada.
de
Chegadas
clientes.
Em
todos
são
os
sistemas será assumido que não mais do que
uma chegada pode ocorrer em um único
instante.
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
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Curso: Engenharia de Produção
Para descrever o processo de saída
Em muitas situações será assumido que o
(processo de atendimento) de um sistema de
tempo de atendimento é independente do
filas
uma
número de clientes presentes. Geralmente dois
distribuição de probabilidade – distribuição
regimes de atendimento são considerados: em
do tempo de serviço – que fornece o tempo de
série e em paralelo.
é
normalmente
especificado
atendimento dos clientes.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
2
Curso: Engenharia de Produção
Curso: Engenharia de Produção
Regimes de atendimento
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
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
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 First Out).
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
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Curso: Engenharia de Produção
Outro fator que deve ser considerado é o
Na maioria das aplicações de filas
processo que um cliente utiliza para decidir
deve-se tentar refletir a realidade e
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
mantê-la computacionalmente tratável,
assim a escolha mais comum é a
distribuição Exponencial.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
3
Curso: Engenharia de Produção
Uma
variável
aleatória
T
tem
Curso: Engenharia de Produção
uma
Considere que a duração, em minutos,
distribuição exponencial de parâmetro λ se sua
fdp for do tipo:
seja uma VAC exponencial com duração média
µ = 10. Se alguém chegou justo na sua
de
λ. e
f( t ) = 
0
-λ t
se
t≥0
frente na cabine telefônica, determine a
se
t<0
probabilidade de que você tenha que esperar
mais do que 10 minutos.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Curso: Engenharia de Produção
∞
2,0
10
1,5
P ( X ≥ 10 ) = ∫ 0 ,1 e − 0 ,1tdt =
[
]
1,0
= lim − e − 0 ,1t − ( e −1) =
t→∞
0,5
= e −1 = 0 ,3679 = 36 ,79 %
0,0
1
11
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
21
31
41
51
61
71
81
91
101
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Curso: Engenharia de Produção
1,00
A função F(t) = P(T ≤ t) é dada por:
0,90
0,80
0,70
0
se t < 0


F( t ) = 
- λt se t ≥ 0

1 - e
0,60
0,50
0,40
0,30
0,20
0,10
Obs.: Tente determinar!
0,00
0
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
1
2
3
4
5
6
7
8
9
10
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
4
Curso: Engenharia de Produção
Curso: Engenharia de Produção
σ2 = V(T) = E(T2) – E(T)2
∞
− λt dt =
E( T ) = ∫−+∞
∞ t.f ( t )dt = ∫0 t.λ e
∞
= [ − t e −λt ]0 + ∫0∞ e −λt dt
∞ 2
2
− λt dt =
E( T 2 ) = ∫−+∞
∞ t .f ( t )dt = ∫0 t .λ e
=
∞
= [ − t 2 e −λt ]0 + ∫0∞ 2 te −λt dt =
− λt  ∞

1
− λt e
− t e −
 =
λ 0 λ

=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
2 ∞
2 1
2
∫0 tλe − λt dt = . = 2
λ
λ λ
λ
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
A variância será então:
2
σ2 = V( T ) = E( T 2 ) − E( T ) =
E o desvio será:
Assim se T tem uma distribuição exponencial,
então: f(t) = λ e- λt
F( t ) = P(T ≤ t ) = 1 − e - λt
P ( T > t ) = e - λt
2
2
1
1
1
= 2 −  = 2 − 2 = 2
λ
λ
λ
λ
λ
2
Curso: Engenharia de Produção
σ =
P ( t1 ≤ T ≤ t 2) = F( t 2) − F( t1) = e - λ t1 − e- λ t 2
1
µ = E (T ) =
λ
1
2
=
V
(
T
)
=
E (T 2 ) − E ( T ) 2 = 2
σ
λ
1
σ=
λ
1
λ
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Curso: Engenharia de Produção
Seja T uma VAC com distribuição
exponencial de parâmetro λ. Determinar o
P(X ≥ µ ) = 1 − F(µ ) = 1 − [1 − e − tλ ] =
= e−1 = 0,3679 = 36,79%
a probabilidade de T assumir valores
superiores ao seu valor esperado.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
5
Curso: Engenharia de Produção
Curso: Engenharia de Produção
Um dos motivos da utilização da
Exponencial na teoria das filas é a sua
Seja T uma VAC com distribuição
propriedade de falta de memória:
exponencial de parâmetro λ. Determinar
P(T > t + h/ T ≥ t) = P(T > h)
o valor mediano de T.
Para quaisquer valores não negativos de
t e h.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Curso: Engenharia de Produção
Pode ser mostrado que nenhuma
Isto significa que se sabemos que
outra VAC tem esse mesmo tipo de
um tempo t transcorreu desde a
propriedade.
Essa
propriedade
é
denominada de falta de memória da
última chegada então a probabilidade
de transcorra um tempo h até a
próxima chegada não depende de t.
variável.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Assim se quisermos saber o tempo
Curso: Engenharia de Produção
Se
o
tempo
entre
chegadas
é
para a próxima chegada não importa há
exponencial então a distribuição do
quanto tempo tenha ocorrido a última
número
chegada.
intervalo de tempo t é dado pelo seguinte
Essa
propriedade
pode
simplificar a análise dos sistemas de filas.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
de
chegadas
em
qualquer
teorema:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
6
Curso: Engenharia de Produção
Curso: Engenharia de Produção
são
Uma VAD X tem uma distribuição de
exponenciais com parâmetro λ se e só se o
Poisson com parâmetro λ se, para x = 0, 1, 2, ...,
número de chegadas que ocorre num
a probabilidade de P(X = x) é dada por:
Tempos
intervalo
interchegadas
de
tempo
t
segue
uma
f(x) = P(X = x) = (e-λλλx)/x!
distribuição de Poisson com parâmetro λt.
para x = 0, 1, 2, …
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Curso: Engenharia de Produção
Se X tem uma distribuição de
Poisson com parâmetro λ então, tem-se
Se definirmos x como o número de
chegadas
que
ocorrem
durante
qualquer intervalo de tempo t, então o
que: σ = λ
teorema diz que:
E(X) = V(X) = λ
P(Xt = x) = [e-λt(λt)x]/x!
Assim:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
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
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;
um intervalo de tempo t, assim λ pode ser
2. Para valores de t pequenos, a probabilidade
pensado como o número médio de chegadas
de uma chegada é proporcional ao tamanho
por unidade de tempo ou taxa de chegadas.
do intervalo.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
7
Curso: Engenharia de Produção
Se
as
condições
1
e
2
forem
verdadeiras então:
com parâmetro λt onde os tempos
são
Em resumo: se a taxa de chegadas é
estacionária e chegadas passadas não afetam as
Xt segue uma distribuição de Poisson
interchegadas
Curso: Engenharia de Produção
exponenciais
de
parâmetro λ.
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
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de Produção
Sabe-se que a variável aleatória X é bimodal para
Curso: Engenharia de Produção
Se
o
tempo
interchegadas
não
é
x = 1 e x = 2 e que tem uma distribuição de Poisson.
exponencial, então ele pode ser modelado pela
Sabendo que X é diferente de zero, a probabilidade de
distribuição de Erlang. Uma distribuição de
X assumir um valor menor do que 3 é dada por:
Erlang é uma VAC cuja fdp depende de dois
(a) 4/e2
(b) 4/(e2 – 1)
parâmetros: r = taxa e k = forma (que deve ser
(d) 1 – 4/e2
(e) 4/(1 – e2).
(c) 2/e
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
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
Curso: Engenharia de Produção
A distribuição de Erlang é
um
caso
particular
da
distribuição Gama.
Agner Krarup Erlang (1878 –
f(t) = [r(rt)k-1e-rt]/(k – 1)! para t ≥ 0
1929),
Obs. A distribuição de Erlang será
representada por E(r, k).
que
engenheiro
utilizou
Probabilidade
a
para
dinamarquês
teoria
modelar
da
e
resolver problemas de telefonia.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
8
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.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
9