Processos de Nascimento e Morte em Teoria de Filas

Prévia do material em texto

Prof.a. Neyde Maria Zambelli Martins 10 
4 - PROCESSOS DE NASCIMENTO E MORTE 
 
Os modelos de filas mais elementares partem do pressuposto de que as entradas 
(clientes que chegam) e saídas (clientes que saem) do sistema de filas ocorram de acordo 
com o processo de nascimento e morte. 
Esse importante processo na teoria das probabilidades tem aplicações em diversas áreas. 
Entretanto, no contexto da teoria das filas, o termo nascimento corresponde à chegada de 
um novo cliente no sistema de filas e a morte refere-se à partida de um cliente atendido. 
O estado do sistema no instante t (t  0), representado por N(t), é o número de clientes no 
sistema de filas no instante t. 
O processo de nascimento e morte descreve probabilisticamente como N(t) muda à 
medida que t aumenta. Em termos genéricos, ela diz que nascimentos e mortes 
individuais ocorrem aleatoriamente, em que suas taxas médias de ocorrência dependem 
apenas do estado atual do sistema. Mais precisamente, as hipóteses do processo de 
nascimento e morte são as seguintes: 
Hipótese 1 
Dado N(t) = n, a distribuição probabilística atual do tempo remanescente até o próximo 
nascimento (chegada) é exponencial com parâmetro n (n = 0, 1, 2, . . .). 
Hipótese 2 
Dado N(t) = n, a distribuição probabilística atual do tempo remanescente até a próxima 
morte (término do atendimento) é exponencial com parâmetro n (n = 1, 2, . . .). 
Hipótese 3 
A variável aleatória da hipótese 1 (o tempo remanescente até o próximo nascimento) e a 
variável aleatória da hipótese 2 (o tempo remanescente até a próxima morte) são 
mutuamente independentes. A próxima transição no estado do processo é 
n → n + 1 (um único nascimento) 
ou então 
n → n - 1 (uma única morte), 
dependendo de se a primeira ou a última variável aleatória for menor. 
 
5 - NOMENCLATURAS E EQUAÇÕES BÁSICAS DAS MEDIDAS DE DESEMPENHO 
 

 = ritmo médio de chegada 
IC
 = 

1
 = intervalo médio entre chegadas 

 = ritmo médio de atendimento 
TA
 = tempo médio de atendimento ou de serviço = 

1
 
Prof.a. Neyde Maria Zambelli Martins 11 
s
 = capacidade de atendimento = no. de atendentes 

 = taxa de utilização dos atendentes = fração média do tempo em que cada servidor 
está ocupado 














atendentesvários,fila1
s
atendente1,fila1
 
L = número de clientes no sistema Lq = número de clientes na fila 
W = tempo no sistema Wq = tempo na fila 
 
 
 POSTULADOS BÁSICOS 
 Em qualquer sistema estável, o fluxo que entra é igual ao fluxo que sai. 
 
 
 
 Em qualquer sistema estável, o fluxo de entrada se mantém nas diversas seções do 
sistema, desde que não haja junção ou desdobramento. 
 
 
 Em qualquer sistema estável, a junção de fluxos equivale às suas somas aritméticas, 
ou seja: 
213 
 
 
 
 
 Em qualquer sistema estável, o desdobramento percentual de um fluxo é igual ao 
desdobramento aritmético do mesmo fluxo. 
 
  
    
C B A 
1 

3 C 
B 
A 
2 
1 
80% 
C 
B 
A 
20% 
3=0,2
2=0,81 
Prof.a. Neyde Maria Zambelli Martins 12 
 INTENSIDADE DE TRÁFEGO 
È o número mínimo de atendentes necessários para atender a um dado fluxo de 
tráfego. 


i
  próximo valor inteiro 
 CICLO DE DURAÇÃO 
È o tempo gasto para que um cliente, partindo de um ponto de referência qualquer, 
percorra todo o sistema e volte ao mesmo ponto. 



populaçãodatamanho
Ciclo
 sistema do fora tempo TFS onde,TFSWCiclo 
 RELAÇÕES BÁSICAS 
Ritmo médio de chegada  
Ritmo médio de atendimento  
Quantidade de atendentes s 
Intervalo entre chegadas 


1
IC
 
Tempo de atendimento 


1
TA
 
Taxa de utilização 



s
 
Intensidade de tráfego - Número mínimo de 
atendentes 


i
 
Condição de estabilidade 
 1
 
Probabilidade de zero clientes no sistema 
1P0
 
Probabilidade de n clientes no sistema 
  nn .1P 
 n = 0, 1, 2, ...  
Probabilidade de n ou mais clientes no sistema 
n
nP 
 
Entre fila, sistema e atendimento L = Lq +  
W = Wq + TA 
LqL 
 
Fórmulas de Little Lq =  . Wq 
L =  . W 
Ciclo de duração 





npopulaçãodatamanho
Ciclo
TFSWCiclo 
Prof.a. Neyde Maria Zambelli Martins 13 
OBS.: Dado um sistema estável, as fórmulas de Little são importantes pois as quatro mais 
importantes variáveis randômicas de um sistema de filas: L, Lq, W e Wq podem se 
obtidas se além de  e , conhecermos o valor de W. 
 
EXERCÍCIOS 
 
2) Se chegam 4 usuários por hora e se o único atendente tem capacidade para atender 10 usuários por 
hora, qual a taxa de utilização do atendente? 
 
3) 

 = 10 usuários por hora, 
TA
 = 3 min ou 

 = 20. Qual o número mínimo de atendentes necessários 
para atender esse fluxo? E se o fluxo de chegada aumentar para 50 usuários por hora? 
 
4) Em uma fábrica observou-se o funcionamento de um dado setor, em que 

 = 20 usuários por hora, 

 = 
25 usuários por hora e 
W
 = 0,3 horas. Pede-se: 
a) o tamanho médio da fila; 
b) calcular 
L
 e 

 
 
5) Em uma mineração cada caminhão efetua um ciclo em que é carregado de minério por uma das 
carregadeiras, desloca-se para o britador para o descarregamento e retorna às carregadeiras. Verificou-se 
que o tempo médio (W) dos caminhões junto ao britador é de 12 minutos e que, em média, existem 6 
caminhões (L) no setor. 
a) Qual a taxa de chegada de caminhões? 
b) Existindo um total de 30 caminhões em serviço, qual a duração de um ciclo? 
c) Qual o tempo médio para o processo completo de carregamento (TFS)? 
 
6) Em uma pizzaria que faz entregas em casa, chegam, em média, 4 atendentes por minuto para pegar o 
produto a ser entregue. Sabe-se, ainda, que o número médio de entregadores dentro da pizzaria é de 6 
(
L
). 
a) Qual o tempo médio no sistema? 
b) Existindo 40 entregadores, qual o tempo médio da entrega (
TFS
)? 
 
7) Em um sistema de computação tem-se: 
 Tempo médio de pensar e fornecer dados (TFS) = 15 segundos 
 Quantidade de terminais ativos = 40 
 Taxa de chegada de transações = 2 por segundo 
 Pede-se o tempo de resposta do computador (W). 
 
8) Em uma mineração temos 12 caminhões efetuando um ciclo no qual consomem 4 minutos entre fila e 
carregamento pela escavadeira (W) e, a seguir, gastam 8 minutos para levar a carga até o britador e voltar 
(TFS). Calcular  e L. 
 
9) Em um sistema de computação temos 21 terminais. O tempo médio de resposta do computador (W) é de 
2 segundos e existem, em média, 6 transações (L) dentro do sistema. Pede-se: 
a) Qual a taxa de chegada de transações? 
b) Qual a duração de um ciclo? 
c) Qual o tempo médio de pensar e fornecer dados (TFS)? 
 
10) No desenho seguinte, representativo de fluxo de peças em um setor de uma fábrica, calcule o fluxo de 
chegada em cada equipamento. 
 
 
 


FDB
%30
ECA
%70
20
10
 
 
 
 
Prof.a. Neyde Maria Zambelli Martins 14 
6 - MODELOS DE FILAS 
 
6.1 - NOTAÇÃO DE KENDALL-LEE 
O Sistema de Filas é descrito por 6 características: 1 / 2 / 3 / 4 / 5 / 6 
 
1  distribuição dos intervalos entre chegadas. 
M – Poisson ou Exponencial. Intervalos de tempo entre chegadas são 
independentes e identicamente distribuídos. Possui a propriedade de não 
apresentar memória, isto é o próximo estado dependendo do estado atual e não 
dos estados anteriores (Markoviana). 
D – Determinística. Intervalos de tempo entre chegadas são independentes e 
identicamente distribuídos. Define tempos constantes, portanto não existe 
nenhuma variabilidade. 
E - Intervalos de tempo entre chegadas são independentes e identicamente 
distribuídos e variáveis aleatórias tendo distribuição de Erlang de ordem k. 
G – Genérica. Intervalos de tempo entre chegadas são independentes e 
identicamente distribuídos. Significa uma distribuição não especificada. Os 
resultados assim obtidos são válidos para qualquer distribuição. 
 
2  distribuição dos tempos de serviços.M – Poisson ou Exponencial. Tempos de serviço são independentes, 
identicamente distribuídos. 
D – Determinístico. Tempos de serviço são independentes, identicamente 
distribuídos. 
E – Erlang de ordem k. Tempos de serviço são independentes, identicamente 
distribuídos. 
G – Genérico. Tempos de serviço são independentes, identicamente distribuídos e 
obedecendo a uma distribuição genérica. 
 
3  número de servidores; canais de atendimento; capacidade de atendimento; 
quantidade de atendentes. 
 
4  número máximo de usuários no sistema. Suprimido quando não há limite para o 
tamanho da fila. 
 
5  tamanho da população que usa o sistema; capacidade do sistema de fila. Caso seja 
considerada capacidade infinita não é especificado. 
 
6  descreve a disciplina da fila. Se for FIFO, este parâmetro é omitido. 
FIFO = First in, first out 
LIFO = Last in, first out 
PRI = Prioridade 
SIRO = Randômico 
RR = Tempo máximo pré-definido 
 
6.2 - MODELOS USUAIS 
6.2.1 MODELO M/M/s 
Processo de entrada Poisson 
Tempos entre atendimento Exponencial 
Número de atendentes s (qualquer inteiro positivo) 
Prof.a. Neyde Maria Zambelli Martins 15 
 Esse modelo é o caso especial do processo de nascimento-e-morte em que a taxa 
média de chegada e a taxa média de atendimento por atendente ocupado do 
sistema de filas são constantes independente do estado do sistema. 
 
a) Caso com um único atendente, s = 1 
n
 para n = 0, 1, 2, ... 
n
 para n = 1, 2, ... 
 
 
b) Caso com vários atendentes, s > 1 
n
 para n = 0, 1, 2, ... s-1 






,...1s,snparas
1s,...,2,1nparan
n
 
 
 
Quando a taxa média de atendimento por atendente ocupado for 

, a taxa média de 
términos de atendimento global para n atendentes ocupados deve ser 
n
. 
 
Portanto, 
snses
snsen
n
n

 
 
Quando 
1
s




 
o sistema de filas atinge a condição de estado estável. 
 
 Medidas de desempenho para M/M/1 
 
  n
n
n 11P 
















  probabilidade de existirem n usuários no 
sistema 
 
Em sistemas estáveis

 ou 
1
. Quando 

 tende para 1 a fila tende a 
aumentar infinitamente, 
1
. 
 


L
  número de usuários no sistema 
 
 


2
qL
  número de usuários na fila 
 


1
W
  tempo durante o qual o usuário fica no sistema 
Prof.a. Neyde Maria Zambelli Martins 16 
 
 

qW
  tempo durante o qual o usuário fica na fila 
 
 Medidas de desempenho para M/M/s 
 Se 
1s 
 
 probabilidade de existirem n usuários no sistema 






































1s
0n
sn0
s
1
1
.
!s!n
1
P
 






























snseP.
s!s
sn0seP.
!n
P
0sn
n
0
n
n
 
 









 qq L
1
WL
  número de usuários no sistema 
 
 2
s
0
q
1!s
..P
L









  número de usuários na fila 
 


1
WW q
  tempo durante o qual o usuário fica no sistema 
 


q
q
L
W
  tempo durante o qual o usuário fica na fila 
 
 
 P(W>t) =  







































 









1s
e1
1!s
P1
e
1st
s
0
t
 e P(Wq>t) =(1-P{Wq=0}).  t1se  
Prof.a. Neyde Maria Zambelli Martins 17 
 em que 
 P{Wq=0} = 



1s
0n
nP
 
 
 Se 
 s
, de modo que a taxa média de chegada exceda a taxa média de 
términos de atendimento máxima, então a fila cresce sem limites, de 
maneira que as soluções de estado estável anteriores não se aplicam. 
 
EXERCÍCIOS 
 
11) Suponhamos que as chegadas a uma cabine telefônica obedecem a lei de Poisson, com ritmo 
de 6 chegadas por hora. A duração média do telefonema é de 3 minutos e suponhamos que siga 
a distribuição exponencial. Pede-se: 
a) Qual a probabilidade de uma pessoa chegar à cabine e não ter que esperar? 
b) Qual o número médio de pessoas na fila? 
c) Qual o número médio de pessoas no sistema? 
d) Qual o número médio de usuários usando o telefone? 
e) Qual o tempo na fila? 
f) Para qual ritmo de chegada teríamos a situação em que o tempo médio de espera na fila seria 
de 3 minutos? 
g) Qual a fração do dia durante a qual o telefone está em uso? 
 
12) Uma fábrica possui um depósito de ferramentas onde os operários vão receber as ferramentas 
especiais para a realização de uma determinada tarefa. Verificou-se que o ritmo de chegada, 
1
 chegada/minuto, e o ritmo de atendimento, 
2,1
 atendimento por minuto, seguem o 
modelo Markoviano, M/M/1. A fábrica paga $9,00 por hora ao atendente e $18,00 ao operário. 
Pede-se: 
a) O custo horário do sistema. 
b) A fração do dia em que o atendente não trabalha. 
 
13) Uma empresa deseja contratar um reparador para efetuar manutenção em suas máquinas, 
que estragam a um ritmo de 3 falhas por hora. Para tal possui 2 opções: um reparador lento, que 
é capaz de consertar a um ritmo médio de 4 falhas por hora ou um reparador rápido, que é capaz 
de consertar a um ritmo médio de 6 falhas por hora. O salário/hora do reparador lento é de $3,00 
e o do reparador rápido é de $5,00. Qual contratação deve ser efetuada para que o custo total, 
reparador + máquinas paradas, seja mínimo? Sabe-se que uma máquina parada implica um 
custo horário de $5,00. 
 
14) Em um sistema de filas seqüenciais, calcule a fila que se forma em cada servidor. 
inspeçãofabricaçãochegada
301510  
 
 
 
 20% 
 
 
 
 
2
 
 
 
20
 
 
 reparo 
Prof.a. Neyde Maria Zambelli Martins 18 
15) Usuários chegam a uma barbearia em um ritmo de 3 por hora e o serviço demora, em média, 
16 minutos. Qual o tempo médio de espera na recepção? E no sistema? 
 
16) Pessoas chegam a uma bilheteria de um teatro a um ritmo de 25 por hora. O tempo médio de 
atendimento da bilheteria é de 2 minutos. Calcule o tamanho da fila, o tempo médio de espera e a 
fração de tempo em que a bilheteria não trabalha. 
 
17) Com os dados do exercício 12, acrescente diversos atendentes até chegar ao custo mínimo. 
1
 chegada/minuto, 
2,1
 atendimento por minuto, $9,00 a hora do atendente, $18,00 a hora 
do operário. 
Depois de escolhido o melhor número de atendentes, aplique a descentralização quebrando o 
sistema no mesmo número de atendentes tornando, assim, cada um com um único atendente. 
Divida também o ritmo de chegada por esse número. Compare e conclua. 
 
18) Uma agência bancária possui 5 atendentes e funciona diariamente de 10:00 às 16:00. O ritmo 
de chegada é de 110 usuários por hora e a duração média de cada atendimento é de 3 minutos. 
Pergunta-se: 
a) o tamanho médio da fila 
b) O tempo médio de espera na fila 
 
19) Um banco deseja modificar a forma de atendimento a seus usuários, que hoje funciona com 
diversas filas, pela introdução do sistema de fila única. Os dados de hoje são: 
 = 70 usuários por hora, que se distribuem em 5 filas 
s = 5 atendentes 
 = 20 usuários por hora 
 
20) Em um sistema de filas seqüenciais, conforme figura a seguir, supondo que o ritmo de 
chegada cresça para  = 25 peças por minuto, calcule a quantidade de servidores de cada 
estação de trabalho tal que o tamanho da fila correspondente (Lq) seja menor que 1. 
 
inspeçãofabricaçãochegada
301510  
 
 
 20% 
 
 
 
 
2
 
 
 
20
 
 
 reparo