Prévia do material em texto
Profº Túlio de Almeida
Pesquisa Operacional II
5. TEORIA DAS FILAS
5.1. DEFINIÇÃO E CLASSIFICAÇÃO DE UM
SISTEMA DE FILAS
5.1.1. Tipos de Sistemas de Filas
Fila Única e um Único Servidor
É o sistema de fila mais simples, possui as seguintes
características:
O sistema possui um único estágio (serviço ou
atendimento).
Composto por apenas 3 elementos: 1 fonte de
usuários, 1 fila e apenas 1 servidor.
Como exemplo, pode-se citar a fila de uma lotérica de
bairro para pagamento de contas.
Fila Única e Múltiplos Servidores em Paralelo
É um sistema que nada mais é que um aprimoramento
do primeiro sistema, e tem as seguintes
características:
O sistema possui um único estágio (serviço ou
atendimento).
Composto por apenas 3 elementos: 1 fonte de
usuários, 1 fila e 2 ou mais servidores.
Como exemplo pode-se citar a fila para atendimento
em caixas eletrônicos.
Múltiplas Filas e Múltiplos Servidores em Paralelo
É um sistema aprimorado a partir de anterior. Só que
há duas ou mais filas e estas podem ser classificadas
de acordo com o usuário e/ou serviço oferecido.
O sistema possui um único estágio (serviço ou
atendimento).
Profº Túlio de Almeida
Pesquisa Operacional II
Composto por apenas 3 elementos: 1 fonte de
usuários, 2 ou mais filas e 2 ou mais
servidores.
Como exemplo, pode-se citar as filas de
supermercados que possui os caixas comuns, o caixa
rápido e o caixa preferencial.
Fila Única e Múltiplos Servidores em Série
É um sistema com uma única fila mas em que
ocorrem vários atendimentos e deve-se respeitar uma
ordem destes atendimentos:
O sistema possui vários estágios (serviços ou
atendimentos).
Composto por apenas 3 elementos: 1 fonte de
usuários, 1 fila e 2 ou mais servidores em
série.
Um exemplo a ser considerado é o drive thru. Os
veículos na fila fazem três processos: fila para a
realização do pedido, depois pagamento e por fim a
retirada do pedido (lanche, café etc).
5.1.2. Processo de Chegada
O processo de chegada de usuários é descrito pelo
intervalo de tempo entre chegadas sucessivas de
usuários. Em geral, admite-se que não mais de um
usuário pode chegar no mesmo instante, caso
contrário, pode-se dizer que houve uma chegada em
lotes, como por exemplo, a chegada de um casal em
um restaurante.
Admite-se também que:
o processo de chegada não se altera ao longo
do tempo;
o processo de chegada não se altera devido
ao número de indivíduos presentes no
sistema.
Devido aos tipos de sistemas de filas, os indivíduos
podem ser considerados iguais estatisticamente ou
agrupados por classes (filas) que possuam uma
estatística comum a elas.
5.1.3. Processo de Serviço
O processo de serviço é descrito pelo tempo de
serviço (atendimento) por usuário. Cada servidor não
precisa ser necessariamente um indivíduo, mas pode
ser um grupo de indivíduos ou máquinas.
Assim como no processo de chegada, admite-se que
o processo de serviço não se altera ao longo do tempo
e não sofre influência do número de indivíduos
presentes no sistema.
Profº Túlio de Almeida
Pesquisa Operacional II
5.1.4. Notação de Kendall-Lee
A fim de explicar e caracterizar uma fila, Kendall
(1953) e Lee (1968), sugeriram a seguinte notação:
A | B | m : C | K | N
onde:
A – refere-se a característica do processo de chegada.
Desta forma pode assumir:
M – exponencial – markoviano sem memória
Ep – distribuição de Erlang com parâmetro de
forma p
GD – distribuição genérica
B – refere-se a característica do processo de serviço.
Assim como a chegada, pode assumir:
M – exponencial –markoviano sem memória
Ep – distribuição de Erlang com parâmetro de
forma p
GD – distribuição genérica
m – número de servidores em paralelo
C – esta característica representa a disciplina da fila,
que pode ser:
FCFS – first come, first served
LCFS – last come, first served
SIRO – service in random order
GD – genérico
Observação: Se a disciplina for genérica, omite-se
este parâmetro da notação de Kendall-Lee.
Caso tenha ainda prioridades, usa-se:
PRP – preemptive priority
NPRP – nonpreemptive priority
K – número de usuários na fila
N – tamanho da população (fonte da fila)
Observação: Caso os valores de K e N assumam o
valor ∞ (ilimitado), deve-se omiti-los da notação de
Kendall-Lee.
Exemplo:
Em uma agência de serviço de energia elétrica, há um
setor que lida com a reclamação dos clientes. A
chegada de clientes acontece de maneira exponencial
assim como o atendimento das reclamações que é
feito por 2 servidores. A disciplina ocorre de maneira
genérica e não há limitação para o número de
usuários nem para a população. Escreva o modelo da
fila na notação de Kendall-Lee.
M | M | 2 | GD | ∞ | ∞
simplificando
M | M | 2
Agora fazendo o contrário, é possível caracterizar uma
fila por meio da notação de Kendall-Lee. Por exemplo:
M | G | 3 | FCFS | 10 | 100
M – chegada markoviana
G – atendimento genérico
m – 3 postos de atendimento
FCFS – disciplina da fila (primeiro a chegar, primeiro a
ser servido)
K – fila limitada a 10 usuários
N – população de 100 usuários
5.2. MEDIDAS DE DESEMPENHO DE UM
SISTEMA DE FILAS
5.2.1. Parâmetros de uma Fila
Taxa de Chegada
Dado o intervalo de tempo entre chegadas de clientes
dado por E(X), pode-se afirmar que a taxa de chegada
de usuários.
)X(E
1
Taxa de Atendimento
Em contrapartida, há um intervalo de tempo entre os
atendimentos por parte dos servidores que é dado por
E(S). Desta forma, a taxa de atendimento será:
)S(E
1
Profº Túlio de Almeida
Pesquisa Operacional II
Se houver m servidores atendendo em paralelo, a taxa
de atendimento ser mμ.
Fator de Utilização
Trata-se da razão entre a taxa de chegada de
usuários e a taxa total disponível de serviço no
sistema.
m
)S(E.
m
5.2.2. Análise em Equilíbrio
No equilíbrio, considera-se que a taxa de chegada de
usuários λ e a taxa de atendimento μ não se alteram
ao longo do tempo.
Sob certas condições, é razoável esperar que, após
algum tempo de operação suficientemente grande, a
fila entre em equilíbrio, e por isso pode-se considerar:
)t(L)t(L)t(L qs
L (t) – número total de usuários no sistema (serviço e
fila) no instante t
Ls (t) – número de usuários em serviço no instante t
Lq (t) – número de usuários em fila no instante t
Após i usuários em um sistema em equilíbrio:
W (i) – tempo de permanência no sistema
Wq (i) – tempo de espera na fila
5.2.3. Fórmula de Little
O Teorema de Little, é dado pela seguinte fórmula:
)W(E)L(E
Pela fórmula de Little, obtém-se equações que
relacionam os parâmetros λ, μ, E(L), E(Lq), E(Ls), E(W)
e E(Wq).
)W(E)L(E qq
)L(E)L(E)L(E)L(E qqs
)W(E
1
)W(E)S(E)W(E qq
5.3. DISTRIBUIÇÃO DE PROBABILIDADE DE
POISSON E EXPONENCIAL
5.3.1. Processos de Poisson
Qual a probabilidade de n clientes chegarem em T
unidades de tempo?
A distribuição de Poisson é empregada em
experimentos, nos quais não se está interessado no
número de sucessos obtidosem n tentativas, como
ocorre no caso da distribuição Binomial, mas sim no
número de sucessos ocorridos durante um intervalo
contínuo, que pode ser um intervalo de tempo,
espaço, etc. Como por exemplo:
O número de suicídios ocorridos em uma
cidade durante um ano;
O número de acidentes automobilísticos
ocorridos numa rodovia em um mês;
Número de chegadas a um caixa automático
de um banco durante um período de 15 minutos
A probabilidade de um carro chegar a um
posto de gasolina em quaisquer dois períodos de
tempo de mesmo tamanho.
A chegada ou não chegada de um carro em
qualquer período de tempo independentemente da
chegada ou não chegada de outro carro em qualquer
outro período.
Defeitos por unidade (m2, m, etc.) por peça
fabricada
Erros tipográficos por página, em um material
impresso
Carros que passam por um cruzamento por
minuto, durante certa hora do dia.
Usuários de computador ligados à Internet
Note que nos exemplos acima, não há como
determinar‐se a probabilidade de ocorrência de um
sucesso, mas sim a frequência média de sua
ocorrência, como, por exemplo, dois suicídios por ano,
a qual será que denominada λ.
Propriedades do experimento de Poisson
a. A probabilidade de uma ocorrência é a mesma
para quaisquer dois intervalos
Profº Túlio de Almeida
Pesquisa Operacional II
b. A ocorrência ou não ocorrência em qualquer
intervalo é independente da ocorrência ou não‐
ocorrência em qualquer intervalo.
5.3.2. Distribuição de Poisson
É, então, uma distribuição de probabilidade discreta
que se aplica a ocorrência de eventos ao longo de
intervalos especificados. A variável aleatória é o
número de ocorrência do evento no intervalo. Os
intervalos podem ser de tempo, distância, área,
volume ou alguma unidade similar.
Uma variável aleatória X admite distribuição de
Poisson se:
X = {0, 1, 2, ...} (não tem limites);
!k
.e
)kX(P
k
, k = 0, 1, 2, ...; é a
probabilidade de k ocorrências em um intervalo
= =E(X)
;
= = Var(X) 2
.
Uma distribuição de Poisson difere de uma
distribuição binomial nestes aspectos fundamentais:
1. A distribuição binomial é afetada pelo tamanho da
amostra n e pela probabilidade p, enquanto que a
distribuição de Poisson é afetada apenas pela média
λ;
2. Na distribuição binomial, os valores possíveis da
variável aleatória X são 0; 1; 2; ... , n, mas a
distribuição de Poisson têm os valores de X de 0; 1; 2;
... , sem qualquer limite superior.
Observação: O parâmetro λ é usualmente referido
como taxa de ocorrência.
5.3.3. Distribuição Exponencial
Esta é uma distribuição que se caracteriza por ter uma
função de taxa de falha constante. A distribuição
exponencial é a única com esta propriedade. Ela é
considerada uma das mais simples em termos
matemáticos. Esta distribuição tem sido usada
extensivamente como um modelo para o tempo de
vida de certos produtos e materiais. Ela descreve
adequadamente o tempo de vida de óleos isolantes e
dielétricos, entre outros.
A fdp é dada por:
xe)x(f
Graficamente pode ser vista da seguinte forma:
x
0
xdxe)x(F
Fazendo mudança de variáveis:
xu
du
dx
dx
du
Substituindo, tem-se que:
]e[ee)x(Fdue)x(F 0xx0u
x
0
u
Desta forma, obtém-se a seguinte fda:
xe1)x(F
Observação: Se o número de ocorrências por unidade
de tempo é uma distribuição de Poisson (Discreta), a
distribuição dos intervalos de tempo entre as
ocorrências é Exponencial (Contínua).
5.4. PROCESSOS DE NASCIMENTO E MORTE
5.4.1. Modelo de Nascimento Puro
Defina-se
p0(t) – probabilidade de nenhuma chegada durante um
período de tempo t.
Dado que o intervalo de tempo entre chegadas segue
uma distribuição exponencial e que a taxa de chegada
é λ clientes por unidade de tempo, então
p0(t) = P{Intervalo de tempo entre chegadas ≥ t}
p0(t) = 1- P{Intervalo de tempo entre chegadas ≤ t}
Com isso tem-se que:
)e1(1)t(p t0
t
0 e)t(p
Profº Túlio de Almeida
Pesquisa Operacional II
5.4.2. Modelo de Morte Puro
O modelo começa com N clientes no tempo 0 e
nenhuma nova chegada é permitida. As partidas
ocorrem a taxas de μ clientes por unidade de tempo.
Considerando um intervalo entre chegadas
infinitesimal h, e fazendo uso de equações diferenciais
é possível obter:
)!nN(
e)t(
)t(p
tnN
n
N
1n
nn )t(p1)t(p
Observação: As equações diferenciais apontam para
uma distribuição de Poisson truncada.
5.5. MODELOS DE FILA PARA UM SERVIDOR
5.5.1. Modelo de Fila M|M|1:GD|∞|∞
Para modelos de fila M|M|1 faz-se uso do seguinte
fator de utilização.
A fila pode ser representada por um modelo de
nascimento e morte como segue:
.1,2,3,4,.. n
.0,1,2,3,..n
n
n
Exemplo:
Em um drive-in de um restaurante de fast-food,
chegam em média 10 carros por hora. Se o tempo
médio de atendimento de cada cliente é de 4 minutos
e os intervalos de tempo entre chegadas e de
atendimento são exponenciais.
a. Qual a probabilidade de o sistema estar vazio?
acarros/hor 10
acarros/hor 15
4
60
)S(E
1
667,0
15
10
)1(pP nn
333,01P0
b. Qual o número médio de carros no drive-in e o
número médio de carros em fila no drive-in?
667,01
667,0
1
)L(E
= 2 carros
O número médio de carros no serviço é E(Ls) = 0,667
≈ ρ
Pela equação,
)L(E)L(E)L(E qs
obtém que
333,1)L(E q
c. Qual o tempo médio de permanência no drive-in e o
tempo de espera na fila do drive-in?
)667,01(10
667,0
1
)W(E
= 0,20 hora ou 12
minutos.
)667,01(15
667,0
1
)W(E q
≈ 0,13 hora ou 8
minutos
Pela equação,
)W(E)W(E)W(E qs
obtém que
07,0)W(E s
hora ou 4 minutos
O que faz sentido com o modelo inicial!
d. Qual a probabilidade de haver dois ou mais carros
(em fila e em serviço) no drive-in?
n
nP
22 )667,0()2L(P
= 0,44
5.5.2. Modelo de Fila M|M|1:GD|K|∞
Trata-se de um modelo de fila onde o número de
usuários é limitado. Como exemplo, pode-se citar um
serviço que possui uma limitação de espaço físico
para a fila.
Pela fórmula de Little tem-se que:
)P1(
)L(E)L(E
)W(E
k
Onde PK
1k
k
k
1
)1(
P
Profº Túlio de Almeida
Pesquisa Operacional II
Exemplo:
No exemplo do drive-in, do restaurante de fast food,
considere que não haja espaço físico para mais de 5
carros (em fila e serviço), caso contrário, a fila invade
a rua do restaurante, e os clientes, ao chegarem
desistem da fila.
a. Qual a taxa de perda de clientes e a taxa média de
utilização da fila?
05,0
67,01
)67,01(67,0
P
15
5
5
A taxa de perda é de
5,0)05,0.(10P5
usuários por hora
A utilização média corresponde
)P1(
)S(E)L(E 5s
63,0
15
)05,01(10
)L(E s
b. Como mudam o número médio de carros na fila e o
tempo médio de espera na fila?
Sem limitação,tem-se E(Lq) ≈ 1,33 carro e E(Wq) ≈ 8
minutos.
Com a limitação da capacidade, tais valores mudam
para
)L(E
)1)(1(
]k)1k(1[
)L(E)L(E)L(E s1k
1k5
sq
79,0)L(E q
carro
97,4
)L(E
)W(E
q
q
minutos
5.5.3. Modelo de Fila M|M|1|GD|∞|N
Pode-se considerar filas onde a fonte de usuários da
fila é limitada. Como exemplo, pode-se citar o
atendimento do médico do trabalho dentro de uma
fábrica, onde a fonte de usuários se limita ao número
de usuários em atividade dentro da fábrica durante o
turno daquele médico.
5.6. MODELO DE FILAS PARA MÚLTIPLOS
SERVIDORES
5.6.1. Modelo de Fila M|M|m|GD|∞|∞
Tal modelo se difere do modelo M|M|1 pelo fato de
m>1, ou seja, aumenta-se o número servidores
idênticos trabalhando de forma paralela no sistema.
O fator de utilização ρ pode ser calculado da seguinte
maneira:
m
A probabilidade do sistema estar vazio é de:
1m
0n
mn0
1
1
!m
m
!n
m
1
P
Exemplo:
Para o exemplo do drive-in de um restaurante fast
food, se duplicarmos o dispositivo de serviço, ou seja,
os clientes na fila serem atendidos por dois servidores
em vez de um?
a. Qual a probabilidade de o sistema estar vazio?
acarros/hor 10
acarros/hor 15
4
60
)S(E
1
Como são 2 servidores
333,0
15.2
10
m
50,0
1
1
!m
m
!n
m
1
P
1m
0n
mn0
b. Qual o número médio de carros no drive-in e o
número médio de carros em fila no drive-in?
75,0P
1!m
m
m)L(E 02
m
Como o número de usuários em serviço está
intimamente ligado ao fator de utilização
667,0m)L(E s
Desta forma obtém-se que
)L(E)L(E)L(E qs
08,0)L(E q
c. Qual o tempo médio de permanência no drive-in e o
tempo de espera na fila do drive-in?
O tempo médio de permanência no sistema
075,0
)L(E
)W(E
horas ou 4,5 minutos
E o tempo médio de permanência na fila
Profº Túlio de Almeida
Pesquisa Operacional II
008,0
)L(E
)W(E
q
q
hora ou 0,50 minuto.
d. Qual a probabilidade de haver dois ou mais carros
(em fila e em serviço) no drive-in?
39,0
!m
m
P1PP1)2L(P
mn
010
5.6.2. Modelo de Fila M|M|∞|GD|∞|∞
Ocorre quando o usuário também é servidor. É
aplicado em auto-serviços, como por exemplo em
caixas eletrônicos, restaurantes self-service entre
outros casos corriqueiros no dia-a-dia.
Apesar da facilidade encontrar tais modelos de fila,
este é complexo de se modelar, uma vez que μ é
muito variável.
5.6.3. Modelo de Fila M|M|m|GD|K|∞
Assim como em modelos de fila M|M|1, é possível
obter um modelo M|M|2 com limitação de capacidade.
Para que o sistema seja funcional, m ≤ K.
5.7. BIBLIOGRAFIA E REFERÊNCIAS
[1] ARENALES, Marcos; ARMENTANO, Vinícius;
MORABITO, Reinaldo & YANASSE, Horácio.
Pesquisa Operacional para Cursos de Engenharia.
1ª Edição. Rio de Janeiro: Elsevier/ABEPRO, 2011.
[2] TAHA, Hamdy. Pesquisa Operacional. 8ª Edição.
São Paulo: Pearson Prentice Hall, 2008.
[3] HILLIER, Frederick S. & LIEBERMAN, Gerald J.
Introduction to Operations Research. 7th Edition.
McGraw Hill. 2001.
[4] MEZA, Lidia Angulo. Teoria das Filas.
Universidade Federal Fluminense. Disciplina:
Pesquisa Operacional II. 24 slides. 2010