05 TEORIA DAS FILAS

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