PUC-Rio Pesquisa Operacional - Teoria das Filas

Prévia do material em texto

Material: Prof. Ulisses Carmadella 
Disciplina: Profa. Léa Benatti 
Teoria das Filas 
 
Um sistema de filas é um processo estocástico de nascimento e morte, um 
nascimento ocorre quando um usuário ou cliente chega à fila e uma morte 
ocorre quando o usuário ou cliente termina o seu atendimento. 
 
Características da fila: 
a) Modelo de chegada pode ser: determinístico (D), Exponencial (M), 
Ergland (E), outros (G); 
b) Modelo de serviço pode ser: determinístico (D), Exponencial (M), 
Ergland (E), outros (G); 
c) Capacidade do sistema (K): limitada ou infinita, entende-se por 
capacidade a fila mais quem está sendo atendido e quando o limite é 
atingido não entra mais ninguém no sistema; 
d) População (N): limitada ou infinita, considera-se a população limitada 
quando o número de possíveis usuários é menor que 50 
e) Disciplina: First in first out (FIFO), Last in first out (LIFO), Sistem in 
randon out (SIRO), Prioridades (PRI) e outros (GD). 
 
Notação de Kendall para identificação dos sistemas de filas: 
 
V/W/X/Y/Z onde: 
 
 V � modelo de chegada; 
 W � modelo de serviço; 
 X � número de atendentes; 
 Y � capacidade do sistema ou população, se nada for dito 
 considera-se infinita; e 
 Z � disciplina se nada for dito considera-se FIFO. 
 
Definição de alguns parâmetros das filas: 
 
Usaremos indistintamente usuários ou clientes por terem o mesmo 
significado na teoria das filas. 
 
L � Número médio de usuários no sistema ou estado do sistema. 
 Inclui os clientes na fila mais os que estão sendo atendidos; 
Lq � Número médio de clientes na fila; 
W � Tempo médio que um cliente leva no sistema; 
Wq � Tempo médio que um cliente leva na fila; 
 2 
W(t) � Probabilidade de um cliente levar mais que um determinado 
 tempo t no sistema; 
Wq(t) � Probabilidade de um cliente levar mais que um determinado 
 tempo t na fila; 
 
λ � taxa média de chegada de usuários; 
λ � taxa média efetiva de chegada de usuários; 
µ � taxa média de atendimento; 
1/ λ � tempo esperado entre chegadas; 
1/ µ � tempo esperado de atendimento; 
ρ � fator de utilização ou intensidade de tráfego; 
µ
λ
S
 � taxa de ocupação onde S é o número de atendentes 
µ
λ
S
−1 � taxa de ociosidade. 
 
 
Relações básicas para qualquer sistema de filas 
 
L = λ W 
Lq = λ Wq 
L = Lq + λ / µ 
W = Wq + 1/ µ 
( ) e W
t
tW −= 
( ) e W
t
q S
tW −=
µ
λ
 
 
 
Sistema M/M/1 
 
λ = λ 
µ
λρ = 
 
A probabilidade de ter n clientes no sistema é dada por: Pn = ρn(1- ρ) 
 
ρ
ρ
−
=
1
L 
ρ
ρ
−
=
1
2
qL λµ −=
1W λµ
ρ
−
=qW 
 
 
 3 
Exercício 1 
Uma oficina para pequenos reparos em automóveis possui um pátio de 
estacionamento, onde ao entrar, os clientes recebem uma senha e ficam 
aguardando sua vez. A oficina possui um mecânico experiente que leva 
em média 6 minutos para efetuar os reparos. O mecânico custa ao dono 
da oficina, por mês, R$ 7.500,00 e o preço médio dos reparos é de 
R$ 25,00 por cliente, já deduzidos os impostos. Sabendo-se que a cada 
6 min e 15 seg, em média, chega um carro, que ao fim do expediente os 
carros na fila não serão atendidos e que o expediente é de segunda à sexta 
de 11:00 às 16:00 horas, pede-se: 
 
a) O número médio de carros aguardando o início do atendimento; 
b) O número médio de carros na oficina; 
c) O tempo médio que um cliente leva para iniciar o reparo; 
d) O tempo médio que um cliente leva entre entrar na oficina e sair com 
o carro reparado; 
e) A probabilidade de um cliente levar mais de 2 horas para iniciar o 
reparo; 
f) A probabilidade de um cliente levar menos de 2 horas na oficina; 
g) A probabilidade de um cliente chegar e ser atendido imediatamente; 
h) A probabilidade de ter mais de 2 clientes na fila; 
i) A média de faturamento líquido mensal. 
 
Respostas: 
a) Lq = 23,04; 
b) L = 24; 
c) Wq = 2,4 horas ou 2 horas e 24 minutos; 
d) W = 2,5 horas ou 2 horas e 30 minutos; 
e) Wq(t) = 0,4314; 
f) 1-W(t) = 0,5507; 
g) P0 = 0,04; 
h) 1-(P0+P1+P2) = 0,8847;e 
i) R$ 6,228,00. 
 
Exercício 2 
Sejam dois sistemas de filas. Ambos recebem clientes com um padrão de 
chegada exponencial de um cliente a cada 10 minutos; o sistema A possui 
um padrão de atendimento exponencial de 1 cliente a cada 6 minutos; o 
tempo médio de espera no sistema B é o dobro do constatado no sistema A. 
Pede-se: 
 4 
a) Qual é o padrão de atendimento do sistema B? 
b) Qual é o número médio de pessoas no sistema A? e 
c) Qual é o número médio de pessoas no sistema B? 
 
Respostas: 
a) µB = 8; 
b) LA = 1,5;e 
c) LB = 3. 
 
Exercício 3 
Em um sistema de filas a chegada se verifica a uma média de 1 cliente a 
cada 12 minutos. O tempo médio de atendimento é de 8 minutos por cliente. 
O sistema possui apenas 1 atendente. Calcule o número médio de clientes no 
sistema e na fila, bem como o tempo médio de espera no sistema e na fila. 
 
Respostas: 
a) L = 2; 
b) Lq = 1,3336; 
c) W = 0,4 horas ou 24 minutos; e 
d) Wq = 0,2667 ou 16 minutos. 
 
Exercício 4 
As máquinas em uma fábrica quebram a uma "rate" exponencial de 6 por 
hora, em média. Existe um reparador que as repara também segundo um 
processo exponencial, em uma "rate" de 8 por hora. O custo, em perda de 
produção, devido à parada das máquinas é de R$ 20,00 por hora por 
máquina. Qual o custo médio no qual a fábrica incorre devido às falhas das 
máquinas? 
 
Resposta: R$ 60,00 por hora. 
 
Exercício 5 
Um mecânico repara carros a uma "rate" exponencial de 2 por dia. Se os 
clientes devem esperar, em média 1 dia antes de apanhar seus carros , 
determine a razão de quebra dos carros. 
 
Resposta: λ = 1 carro por dia. 
 
 
 5 
Sistema M/M/S 
 
λ = λ 
µ
λρ
S
= 
∑
−
=





+
−





=
1
0
0
!1
1
!
1
S
n
nS
n
x
S
P
µ
λ
ρ
µ
λ
 0!
xP
n
P
n
n





=
µ
λ
 se 0 ≤ n ≤ S 
 
0!
xP
SS
P Sn
n
n
−





=
µ
λ
 se n ≥ S ( )20 1! ρ
ρµ
λ
−





=
S
PL
S
q 
 
Exercício 1 
Uma oficina para pequenos reparos em automóveis possui um pátio de 
estacionamento, onde ao entrar, os clientes recebem uma senha e ficam 
aguardando sua vez. A oficina possui 5 mecânicos experientes que levam em 
média 30 minutos para efetuar os reparos. Os mecânicos custam ao dono da 
oficina, por mês, R$ 1.500,00 e o preço médio dos reparos é de 
R$ 25,00 por cliente, já deduzidos os impostos. Sabendo-se que a cada 
6 min e 15 seg, em média, chega um carro, que ao fim do expediente os 
carros na fila não serão atendidos e que o expediente é de segunda à sexta de 
11:00 às 16:00 horas, pede-se: 
 
a) O número médio de carros aguardando o início do atendimento; 
b) O número médio de carros na oficina; 
c) O tempo médio que um cliente leva para iniciar o reparo; 
d) O tempo médio que um cliente leva entre entrar na oficina e sair com 
o carro reparado; 
e) A probabilidade de um cliente levar mais de 2 horas para iniciar o 
reparo; 
f) A probabilidade de um cliente levar menos de 45 minutos na oficina; 
g) A probabilidade de um cliente chegar e ser atendido imediatamente; 
h) A probabilidade de ter mais de 2 clientes na fila; 
i) A média de faturamento líquido mensal; 
j) Compensaria contratar mais um mecânico se o investimento inicial de 
R$ 15.000,00 (obras, compra de material, ferramentas etc) tivesse sua 
amortização desejada em um mês?6 
Respostas: 
a) Lq = 21,66; 
b) L = 26,46; 
c) Wq = 2,26 horas ou 2 horas e 16 minutos; 
d) W = 2,76 horas ou 2 horas e 46 minutos; 
e) Wq(2) = 0.4651; 
f) 1 – W(0,75) = 0,2379; 
g) P0 + P1 + P2 + P3 + P4 = 0,0989; 
h) 1 – (P0 + P1 + P2 + P3 + P4 + P5 + P6 + P7) = 0,7966 ; 
i) R$ 6.987,00; e 
j) Sim pois o faturamento liquido médio mensal passará a ser 
R$ 16.261,50, que é maior que os R$ 15.000,00 investidos. 
 
Exercício 2 
Uma copiadora alugada para uso de um escritório é usada principalmente 
pelas secretárias. A máquina leva em média 5 minutos para efetuar as cópias 
e as secretárias chegam ao compartimento da copiadora a cada 6 minutos em 
média. Sendo o tempo de trabalho de uma secretária estimado em cerca de 
R$ 6,50 por hora, e o aluguel das máquinas R$ 500,00 por mês. 
Responda: 
 
a) Se o expediente é de 8 horas por dia, qual é o tempo ocioso da 
máquina? 
b) Qual é o custo médio diário devido à espera e operação da máquina 
pelas secretárias? 
c) Qual é a probabilidade de uma secretária esperar menos de 15 minutos 
para completar sua cópia? 
d) Qual é a probabilidade de uma secretária esperar mais de 9 minutos 
para iniciar a sua cópia? 
e) Sabendo-se que duas mulheres quando se encontram começam a 
conversar, qual é a probabilidade de haver chacrinha no 
compartimento da copiadora? 
f) Qual é o número médio de secretárias no compartimento da 
copiadora? 
g) Qual é o tempo médio que uma secretária dispende antes de iniciar 
sua cópia? 
h) Qual seria o número ótimo de copiadoras no compartimento? 
 
Respostas: 
a) 1 hora e 20 minutos; 
b) R$ 260,00; 
 7 
c) 1 - Wq(0,25) = 0,3935; 
d) W(0,15) = 0,6173; 
e) 1 – (P0 + P1) = 0,6944; 
f) L = 5; 
g) Wq = 0,46 da hora ou 25 minutos; 
h) 2 copiadoras com um custo total de R$ 2.153,61. 
 
Exercício 3 
Em um grande supermercado os clientes chegam ao "checkout" a uma taxa 
de 80 por hora. O "checkout" é provido de 20 postos de atendimento e cada 
caixa leva em média 5 minutos para despachar um cliente. O tempo ideal 
para o cliente completar o atendimento é de 6 minutos. Cada minuto a amis 
que o cliente leva para pagar suas contas o supermercado incorre num custo 
mensal de R$ 15.000,00. O valor para contratação de um caixa é de 
R$ 3.800,00. O custo de treinamento para redução de um minuto no tempo 
de atendimento é de R$ 20.000,00. Qual das quatro alternativas abaixo é a 
mais econômica, sabendo-se que os custos totais para passar para fila única 
orçam em torno de R$ 5.500,00? 
 
a) Não faz nada � R$ 22.500,00; 
b) Contrata mais caixas e quantos? � R$ 76.000,00 20 caixas; 
c) Treina pessoal � R$ 14.285,71;e 
d) Passa para fila única � R$ 5.500,00. 
 
Obs: Como o número de atendentes é maior que 15, podemos aproximar o 
cálculo do Lq (apenas o Lq) para a fila única utilizando a fórmula do M/M/1, 
pois a precisão desejada no problema permite. 
 
Modelo M/M/1/k 
 
λ = λ se n = 0,1,2,...., k – 1 λ = 0 se n ≥ k 
µ
λρ = 
( ) ( )01
0
11 PPP kk
k
n
n ρλλλλ −=−==∑
−
=
 fila máxima = k – 1 
 
número máximo de clientes no sistema = k 
taxa de ocupação = 
µ
λ
 taxa de ociosidade = 
µ
λ
−1 
10 1
1
−
−
−
= kP ρ
ρ
 0PP
n
n ρ= se n ≤ k Pn = 0 se n > k 
 
 8 
( )
1
1
1
1
1 +
+
−
+
−
−
= k
kkL
ρ
ρ
ρ
ρ
 
 
Exercício 
J. J. Cortarrente possui uma barbearia com 10 cadeiras na espera. Apesar de 
ser um excelente barbeiro, quando todas as cadeiras estão ocupadas os 
clientes que chegam não ficam esperando, vão embora. Sendo ele o único 
barbeiro, e sabendo-se que: os clientes chegam a cada 25 minutos, 
Cortarrente leva em média 20 minutos para atender um cliente, o 
atendimento custa em média R$ 15,00 e o expediente é de 08:00 às 16:00 de 
segunda a sexta. Pede-se: 
 
a) Número médio de clientes na barbearia; 
b) Número médio de clientes aguardando a sua vez; 
c) Tempo médio que um cliente dispende até iniciar o seu atendimento; 
d) Tempo médio que um cliente leva para entrar e sair com o cabelo 
cortado; 
e) Probabilidade de um cliente chegar e ir embora imediatamente; 
f) Probabilidade de um cliente chegar e ser atendido imediatamente; 
g) Probabilidade de um cliente chegar e encontrar 4 pessoas esperando 
para ser atendido; 
h) Tempo disponível para Cortarrente fazer um lanche; 
i) O faturamento médio bruto mensal; 
j) Probabilidade de um cliente passar menos de 2 horas na barbearia; e 
k) Probabilidade de um cliente levar mais de 2 horas para iniciar seu 
atendimento. 
 
Respostas: 
a) L = 3,1145; 
b) Lq = 2,3299; 
c) Wq = 0,9898 horas ou 59 minutos; 
d) W = 1,3232 horas ou 1 hora e 19 minutos; 
e) P11 = 0,1925; 
f) P0 = 0,2241; 
g) P5 = 0,0734; 
h) 1,723 horas ou 1 hora e 43 minutos; 
i) R$ 6.213,90; 
j) 1 – W (2) = 0,7794; e 
k) Wq(2) = 0,1731. 
 
 9 
Modelo M/M/S/k 
 
 λ = λ se n = 0,1,2,...., k – 1 λ = 0 se n ≥ k 
µ
λρ
S
= 
( )k
k
n
n PP −==∑
−
=
1
1
0
λλλ fila máxima = k – S 
 
número máximo de clientes no sistema = k 
taxa de ocupação = 
µ
λ
S
 taxa de ociosidade = 
µ
λ
S
−1 
∑ ∑
−
= =
−





+





=
1
0
0
!!
1
S
n
k
Sn
Sn
Sn
x
Sn
P
ρµ
λ
µ
λ
 
 
0!
P
n
P
n
n





=
µ
λ
 se n ≤ S 0!
P
SS
P Sn
n
n
−





=
µ
λ
 se S ≤ n ≤ k 
 
 Pn = 0 se n > k 
 
( ) ( ) ( )[ ]ρρρρ
ρµ
λ
−−−−
−





=
−− 11
1! 2
0
SkSk
S
q SkS
P
L 
 
Exercício 
Cortarrente ficou famoso e seus clientes passaram a chegar em média a cada 
8 minutos. Assim sendo, contratou 2 barbeiros que foram por ele treinados e 
levam em média cada um 20 minutos para atender um cliente. O 
atendimento custa em média R$ 15,00, o expediente é de segunda a sexta de 
08:00 às 16:00 horas, o número de cadeiras na espera continua sendo 10 e o 
custo de cada barbeiro é de R$ 1.000,00 por mês. Pede-se: 
 
a) Número médio de clientes na espera; 
b) Número médio de clientes na barbearia; 
c) Tempo médio que um cliente fica na barbearia; 
d) Tempo médio que um cliente leva para iniciar o seu atendimento; 
e) Probabilidade de um cliente chegar e ir embora imediatamente; 
f) Probabilidade de um cliente chegar e ser atendido imediatamente; 
 10 
g) Probabilidade de ter pelo menos um cliente aguardando o 
atendimento; 
h) Faturamento médio líquido mensal; 
i) Probabilidade de um cliente levar menos de 50 minutos para iniciar o 
seu atendimento; 
j) Probabilidade de um cliente passar mais de 45 minutos na barbearia; e 
k) Tempo disponível para almoço. 
 
 P(o) = 0,0496 =λ 7,3435 
 
Respostas: 
a) Lq = 2,2057; 
b) L = 4,6535; 
c) W = 0,6337 horas ou 38 minutos; 
d) Wq = 0,3003 horas ou 18 minutos; 
e) P13 = 0,0209; 
f) P0 + P1 + P2 = 0,3286; 
g) 1 – (P0 + P1 + P2 + P3) = 0,542; 
h) R$ 17.384,20; 
i) 1 – Wq(50) = 0,781; 
j) W(45) = 0,3062; e 
k) 1,4667 horas ou 1 hora e 28 minutos; 
 
Modelo M/M/1/N 
 
( ) ( )LNPnN n
N
n
−=−=∑
−
=
λλλ
1
0
 
( )∑
= 













−
=
N
n
n
nN
N
P
0
0
!
!
1
µ
λ
 
( ) 0!
! P
nN
NP
n
n 





−
=
µ
λ
 se n ≤ N e Pn = 0 se n > N 
 
( ) ( )0
2
11 PNPnLN
n
nq −
+
−=−=∑
=
λ
µλ
 
( )0
0
1 PNnPL
N
n
n −−==∑
=
λ
µ
 
 
Exercício 
João Chave de Fenda é o único mecânico de uma fábrica que possui 5 
máquinas idênticas que avariam a uma taxa de 2 avarias por hora. O tempo 
médio de reparação é de 15 minutos. Sabe-se que o custo horário de 
 11 
inatividade de uma máquina é de R$ 360,00 e o custo horário de João é 
R$ 150,00. Calcular: 
 
a) O número médio de máquinas aguardando reparos; 
b) O número médio de máquinas paradas; 
c) O número médio de máquinas funcionando; 
d) O tempo médio que uma máquina leva entre quebrar e ser 
completamente reparada; 
e) O tempo médio que uma máquina leva para iniciar o seu reparo; 
f) O custo total diário sabendo-se que o expediente é de 8 horas; 
g) Quantas horas por dia João descansa;e 
h) A probabilidade de ter 2 máquinas na fila. 
 
Respostas: 
a) Lq = 2,1101; 
b) L = 3,0736; 
c) 5 – L = 1,9265; 
d) W = 47,86 min; 
e) Wq = 32,86 min; 
f) R$ 10.051,97; 
g) 17,64 min; 
h) P3 = 0,2753. 
 
Modelo M/M/S/N 
 
( ) ( )LNPnN n
N
n
−=−=∑
−
=
λλλ
1
0
 
( ) ( )∑ ∑
−
= =
−






−
+





−
=
1
0
0
!!
!
!!
!
1
S
n
nN
Sn
sn
n
SSnN
N
nnN
N
P
µ
λ
µ
λ
 
 
( ) 0!!
! P
nnN
NP
n
n 





−
=
µ
λ
 se n ≤ S ( ) 0!!
! P
SSnN
NP
n
Snn 





−
=
− µ
λ
 se S ≤ n ≤ N 
 
Pn = 0 se n > N ( )∑
=
−=
N
Sn
nq PSnL ∑
=
=
N
n
nnPL
0
 
 
Exercício 
A companhia em que João Chave de Fenda trabalha comprou mais três 
máquinas e contratou Pedro Alicate, também mecânico com as mesmas 
habilidades de Chave de Fenda (tempo de reparo das máquinas 15 minutos). 
 12 
As máquinas novas também avariam a uma rate de 2 por hora. O custo 
horário das máquinas é R$ 360,00 e dos mecânicos R$ 150,00. Calcular: 
a) Lq; 
b) L; 
c) W; 
d) Wq; 
e) Custo total diário para um expediente de 8 horas; 
f) Tempo em que o sistema está ocioso; 
g) Probabilidade de uma máquina quebrar e ter que esperar na fila. 
 
Respostas: P0 = 0,0154 ; λ = 7,616 
a) 2,2814; 
b) 4,1854; 
c) 0,5496 horas ou 33 min; 
d) 0,2996 horas ou 18 min; 
e) R$ 14.453,95; 
f) 0,384 horas ou 23 minutos; e 
g) 0,923.