NOÇÕES SOBRE FILAS
Gabriela Servidone 141648
Gustavo Bratfisch 136015
TÓPICOS
• Introdução
• Processos de Nascimento e Morte
• Teoria de Filas
• Os Sistemas de Filas M/M/1, M/M/m, M/M/m/B,
M/M/N/N/K, M/G/1
• Noções de Arena
PROCESSOS DE NASCIMENTO E MORTE
o São Cadeias de Markov onde as transições de estado são
restritas a estados vizinhos apenas,
o É possível representar o estado através de um número
inteiro.
o Exemplo:
nascimento ou chegada
Estado
(pessoas
na fila)
0
1
2

n-1
morte ou partida
n
n+1

TEORIA DE FILAS
o Ferramenta matemática para tratar de eventos aleatórios,
o É o estudo da espera em filas,
o Proporciona uma maneira de definir o ambiente
de um sistema de filas matematicamente,
o Permite prever respostas prováveis e tempos de espera.
OBJETIVO

Avaliar o comportamento de um sistema de filas e seus
parâmetros, exemplos:

Tempo de espera médio,

Probabilidade de formação de fila,

Porcentagem de clientes rejeitados pelo sistema,

Probabilidade de um cliente esperar mais do que um certo
tempo,

Número médio de clientes na fila,

Probabilidade de que todos os servidores estejam ociosos.
CARACTERÍSTICAS DE
UM SISTEMA DE FILA
(Ex.: Usuários de computadores de uso compartilhado)
CARACTERÍSTICAS DE
UM SISTEMA DE FILA
1.
2.
3.
4.
5.
6.
Processo de Chegada
Distribuição de Tempo de Serviço
Quantidade de Servidores
Tamanho do Sistema de Fila
População de Clientes
Disciplina de Atendimento
1. PROCESSO DE CHEGADA




Se os clientes chegam em instantes t1, t2, ..., tj a variável
randômica j = tj - tj-1 é chamada Tempo Interchegadas,
Assume-se que os j formam uma sequencia de variáveis
aleatórias independentes identicamente distribuídas (v.a.
IID),
O processo de chegada mais comum é o Processo de
Poisson. Isto significa que os Tempos Interchegadas são
exponencialmente distribuídos,
Outras distribuições podem ser utilizadas, tais como a
Hiperexponencial, Erlang e Geral.
2. DISTRIBUIÇÃO DE TEMPO DE
SERVIÇO (PROCESSO DE SERVIÇO)




O tempo gasto por cada cliente num computador é
chamado Tempo de Serviço,
É aceitável supor que os Tempos de Serviço de cada
cliente sejam variáveis aleatórias IID,
A distribuição mais utilizada para o Tempo de Serviço é
a Distribuição Exponencial,
Outras distribuições podem ser utilizadas, tais como a
Hiperexponencial, Erlang e Geral.
3. QUANTIDADE DE SERVIDORES
o Single Server – atende a apenas um cliente de cada vez,
o Multi-Server – possui m servidores, podendo atender
m clientes simultaneamente.
o Infinite Server – cada cliente que chega encontra
sempre um servidor disponível.
4. TAMANHO DO SISTEMA
(CAPACIDADE DO SISTEMA)
o Capacidade do sistema = capacidade da fila de
espera + quantidade de servidores (posições de
serviço)
o A capacidade máxima de clientes no sistema poderá
ser limitada por questões de espaço, custo ou para evitar
um tempo de espera muito longo
o Na maior parte dos sistemas, a capacidade da fila é
limitada (finita)
o Em sistemas com filas de capacidade infinita, todos
os clientes serão atendidos
o Em sistemas sem capacidade de espera ou com
capacidade limitada, pode ocorrer rejeição de clientes
5. POPULAÇÃO DE CLIENTES
o É a quantidade de usuários em potencial que pode, em
algum momento, usar o sistema (ex.: clientes de banco,
programa de computador, assinante de linha telefônica),
o Nos sistema reais a população é limitada (finita),
o Quando a população é finita, a taxa de chegada dependerá
da população,
o População Infinita – taxa de chegada constante,
o População Finita – taxa de chegada variável.
6. DISCIPLINA DE SERVIÇO
o De uma fila, é o método de escolha da sequencia de
atendimento dos clientes na fila,
o A disciplina mais utilizada é a FCFS ou FIFO (primeiro a
chegar é o primeiro a sair da fila),
o Outras disciplinas: LCFS, SIRO, RR,
o O atendimento pode ser priorizado em função de:
o Tempo esperado de atendimento, ex.: menos demorado
primeiro,
o Tamanho do cliente (pacote de mensagem), ex.: maior
primeiro, menor primeiro,
o Maior sensibilidade a atrasos, ex.: mais sensíveis primeiro,
o Qualidade de serviço (QoS).
TIPOS DE ATENDIMENTO
Disciplina de
Serviço
Descrição
FCFS/FIFO
LIFS/LIFO
SIRO
First Come First to be Served
Last In First to be Served
Select In Random Order
RD
Atendimento baseado em prioridade
GD
Distribuição genérica
CLASSIFICAÇÃO DE SISTEMA DE FILA
o Um sistema de fila é classificado por suas
características,
o Utiliza-se a Notação de Kendall.
A/ S / m / B / K / DS
Onde:
A = Distribuição de tempo interchegada
S = Distribuição de tempo de serviço
m = Número de canais de serviço simultâneo (servidores)
B = Quantidade de Buffers ou capacidade do sistema
K = Tamanho da população
DS = Disciplina de serviço
DISTRIBUIÇÕES
o As distribuições utilizadas para o tempo interchegada e
tempo de serviço são simbolizadas por uma letra,
conforme a seguir:
M = Exponencial
Ek = Erlang, com parâmetro K
Hk = Hiperexponencial, com parâmetro K D =
Determinístico
G = Distribuição Genérica
o A distribuição exponencial é chamada memoryless (M)
o Uma distribuição determinística (D) significa tempo de
chegada e tempo de serviço constante, ou sem variância
EXEMPLO
M/M/3/20/1500/FCFS
o
o
o
o
Tempo interchegada exponencialmente distribuído,
Tempo de serviço exponencialmente distribuído,
Existem 3 servidores,
A fila possui um total de 20 posições de buffer. Consistindo em 3
buffers para cada servidor, 17 posições de espera compartilhados
entre os três servidores. Se a quantidade de clientes no sistema
for 20, os clientes que chegam são perdidos até que a fila
diminua,
o Há uma população de 1500 clientes que podem ser atendidos,
o A disciplina de serviço é FCFS (primeiro a chegar, primeiro a ser
servido).
OUTROS EXEMPLOS
não utilizados
 /  / FCFS
Desprezar os três últimos símbolos quando: disciplina é FCFS,
população infinita e tamanho da fila infinito
•
•
•
•
M/M/1/B
M/M/m
M/M/m/B
M/M/m/m
•
•
•
•
M/M/
M/G/1
M/D/1
M/M/m//k
Prof. Gil Pinheiro
M/M/1 => M/M/1/
PROCESSOS DE CHEGADA
Hipóteses
o Dois clientes nunca chegam simultaneamente,
– O 1º cliente chega no instante t0, o 2º no instante t1
e assim por diante ( 0 < t0 < t1 ,, ... , < tn )
o Os tempos entre chegadas estão distribuídos
exponencialmente,
o A taxa de chegada (1/) também terá distribuição
exponencial.
PROCESSO DE POISSON
Número de
Chegadas
Se a taxa de chegada possui distribuição exponencial, a
probabilidade de k clientes chegarem dentro de T
segundos pode ser modelada pela distribuição de Poisson:
T T onde:  > 0, k = 0,1,2, ...
Pk (T ) 
e
k!
4
3
2
1
Chegadas
tc1
tc2
tc3
tc4
tempo
PROCESSO DE POISSON
Num sistema com  = 0,4 chegadas/s, em T = 8 s, ocorrerão 3,19959
chegadas aproximadamente. Em média: 0,4 x 8 = 3,2 chegadas
0,25
k
0
1
2
3
4
5
6
7
8
9
10
11
12
Soma =
Pk
0,04076
0,13044
0,20870
0,22262
0,17809
0,11398
0,06079
0,02779
0,01112
0,00395
0,00126
0,00037
0,00010
0,99997
k.Pk
0,00000
0,13044
0,41740
0,66785
0,71237
0,56990
0,36473
0,19452
0,08893
0,03557
0,01265
0,00405
0,00118
3,19959
Valor médio
Pk
0,20
0,15
0,10
0,05
0,00
1
2
3
4
5
6
7
8
9
10
11
12
13
k
PROPRIEDADES DOS PROCESSOS DE
POISSON
1
2
 =  i
3
A junção de fluxos de Poisson resulta num fluxo de Poisson

p1
p2
p3
1 =  pi
A partição de um fluxo de Poisson resulta em fluxos de Poisson
PROPRIEDADES DOS PROCESSOS DE
POISSON



>
Partidas de um sistema de fila M/M/1 é um fluxo de Poisson

1
2
3

 i >
Partidas de um sistema de fila M/M/m é um fluxo de Poisson
NOTAÇÃO DE MODELOS DE FILA
 = Tempo interchegada = tempo decorrido entre duas chegadas
sucessivas
NOTAÇÃO DE MODELOS DE FILA
m

Quantidade de servidores idênticos.
Taxa média de chegada, de clientes (=1/E[]). Em alguns sistemas, poderá
depender do estado do sistema (quantidade de clientes).
s Tempo de serviço (de atendimento) de um cliente.
 Taxa média de serviço por servidor (=1/E[s])). Para m servidores, a taxa
média de serviço é m
n
Quantidade total de clientes no sistema, também chamada tamanho da fila.
Inclui os clientes em espera por um servidor e os que estão sendo atendidos.
nq Quantidade de clientes aguardando atendimento. É sempre menor que n, pois
não inclui os clientes em serviço.
ns Quantidade de clientes em serviço.
Tempo de resposta do sistema. Ou tempo total de residência dos clientes
r
dentro do sistema de fila (tempo de espera + tempo de atendimento).
w
Tempo de espera para ser atendido. É o tempo decorrido entre a chegada e o
início do atendimento (serviço) do cliente.

B

Utilização do servidor (= / )
Tamanho da fila, quando esta for finita (tamanho do Buffer)
Tempo interchegadas (= 1/)
Todas as variáveis, exceto  e , são variáveis aleatórias.
EQUAÇÃO DE LITTLE
o Permite calcular a quantidade de clientes (itens) em
qualquer Sistema de Fila. Resume-se a:
quantidade média = taxa de chegada x tempo médio de
resposta
o Esta relação se aplica a um Sistema Inteiro ou parte de
um Sistema de Fila
o Baseia-se numa visão tipo “Caixa Preta” do
Sistema de Fila
Chegada
s
Sistema de
Fila
(Caixa Preta)
Partidas
EQUAÇÃO DE LITTLE - APLICAÇÃO
A equação de Little pode ser aplicada a um subsistema
ou todo o sistema de Fila.
Quantidade
Tempo
EQUAÇÃO DE LITTLE - APLICAÇÃO
Aplicando a equação de Little num subsistema ou em todo o
sistema de Fila:
– Na fila de espera: nq =  . w
– No servidor:
ns =  . s =  / 
– No sistema inteiro: n =  . r
O SISTEMA DE FILA M/M/1
Sistema de fila com um servidor –
Exemplo: clientes na fila do caixa eletrônico
MODELO DO SISTEMA DE FILA M/M/1
Modelo
Simbologia


CARACTERÍSTICAS DO M/M/1
o
o
o
o
Processo de chegada tipo Poisson (M)
Tempo de serviço - distribuição exponencial (M)
Quantidade de servidores (= 1)
Infinitas posições na fila de espera (clientes não são
perdidos)
o Disciplina de serviço do tipo FIFO
o População de clientes é infinita (taxa de chegada é
constante)
SISTEMA DE FILA M/M/1 DIAGRAMA DE TRANSIÇÃO DE ESTADOS
0
Estado:
0
1
1
1

2
2
n-2
2
3
n-1
n–1
n-1
n
n
n+1
n
n+1
n+1
n+2
Estado = quantidade total de clientes no sistema
Para o sistema M/M/1, temos:
n =  Cte, n = 0, 1, 2, .... (taxa de chegadas no sistema)
n =  Cte, n = 1, 2, 3, .... (taxa de partidas do sistema)

ESTADOS DO SISTEMA M/M/1
o Um sistema de fila M/M/1 será estudado a
seguir visando determinar seu equilíbrio, ou seja,
quando atinge a condição de regime permanente
o Nessas condições, o sistema pode ser identificado através
de suas propriedades estatísticas (tempo de espera, tempo
de residência, tamanho da fila, tempo de espera na fila,
etc)
o Esse estudo poderá ser estendido para
outros sistemas de fila (M/M/N, M/M/N/N, etc)
SISTEMA DE FILA M/M/1 CÁLCULO DO ESTADO DO SISTEMA
1. Parâmetros:  = Taxa de chegada (por unidade de tempo)
 = Taxa de serviço (por unidade de tempo)
2. Utilização do servidor (=intensidade de tráfego):    / 
3. Condição de Estabilidade:   
4. Probabilidade de zero clientes no sistema:
p0 = 1 – 
5. Probabilidade de n clientes no sistema:
pn = P[N = n] = (1 – n , n = 0, 1, 2, ....
6. Probabilidade de haver mais que n clientes no sistema:
pn+ = P[R > n] = n
7. Quantidade média de clientes no sistema: n = /(1– )
8. Quantidade média de clientes na fila: nq = /(1– )
9. Tempo de residência (tempo de resposta) médio: r = 1 / [ (1 – )]
10. Probabilidade acumulada do tempo de residência:
P[ r  t ]= 1 – e–t
SISTEMA DE FILA M/M/1 CÁLCULO DO ESTADO DO SISTEMA



P(r < t) é a probabilidade do
tempo de residência ser
menor do que t
Do gráfico, para t = 1.2 rmédio
, então P(t) = 0.7, é a
probabilidade de um cliente
ter seu tempo de residência
menor que 1.2 rmédio
Sendo rmédio o tempo médio
de residência = 1/(1–)
11. Percentil do tempo de residência:
m(q) = r ln [ 100 / (100 – q) ]
m(q): é o tempo máximo de residência para q (%) de clientes
12.Tempo médio de espera na fila:
w = nq /  = ( /    (1 - )
SISTEMA DE FILA M/M/1 EXEMPLO 1
Um servidor de rede esta associado a 100 computadores através de uma
rede (LAN). O servidor mantêm um banco de dados para consultas dos
computadores. O tempo médio de resposta de uma consulta no servidor é
de 0,6 segundos e o desvio do tempo é igual a média. No horário de pico, a
taxa de consultas atinge a taxa de 20 consultas/minuto. Responda as
seguintes questões:
(1) Qual o tempo de resposta médio?
(2) Se o tempo de resposta máximo aceitável for 1,5 s (para 90% das
consultas), qual o percentual de aumento de tráfego?
(3) Com um acréscimo de 20% de tráfego, qual o aumento no tempo de
resposta?
SISTEMA DE FILA M/M/1 EXEMPLO 1
Assumindo um modelo M/M/1 para o sistema servidor, rede e micros. Os
atrasos na rede (tempo de propagação) e as colisões) são ignorados.
(1) Tempo de Resposta Médio:
• Taxa de chegada:  = 20 / 60 = 1/3 clientes/segundo
• Taxa de atendimento:  = 1 / 0,6 = 10 / 6 clientes/segundo
• Intensidade de tráfego (=utilização do servidor):    /  = 1/3 x 6/10
= 0,2
• Tempo de Resposta do Sistema: r = 1 / [1 –   0,6 / (1 – 0,2) =
0,75 s (=0,6 s no atendimento + 0,15 s na fila de espera do servidor)
SISTEMA DE FILA M/M/1 EXEMPLO 1
(2) Aumento de tráfego:
•
Acréscimo no Tráfego quando r = 1,5 s para 90 %
das requisições: 1,5 = r x ln[100/(100 - 90)] então:
r = 0,65
Como r = (1/  1 –     1 –   5
Logo:   
Assim, a intensidade de tráfego () deve cair de 0,2 para 0,077 para
que o tempo de residência (r) caia de 0,75 para 0,65
(3) Acréscimo no tempo de resposta:
• A intensidade de tráfego (utilização) foi aumentada em 20%, então: 
= 0,2 + 0,2 = 0,4
• Logo: r = (1/  1 –   (1/1,667) / (1 – 0,4) = 1,00 s
•
•
•
SISTEMA DE FILA M/M/M
o Sistema com m servidores iguais
o Cada servidor possui uma taxa de serviço igual a 
o Sistema sem perdas - se todos os servidores estiverem
ocupados, novos clientes aguardam na fila de espera
SISTEMA DE FILA M/M/M - DIAGRAMA
DE TRANSIÇÃO DE ESTADOS

Estado:
0


1


.

m–1
m. m.

m

m+1
m.
Para o sistema M/M/m:
n =  , n = 0, 1, 2, ..., 
n =
n. , n = 1, 2, 3, ..., m-1
m., n = m, m+1, m+2, m+3, ..., 
m.

SISTEMA DE FILA M/M/M - CÁLCULO
DO ESTADO DO SISTEMA
1. Parâmetros:  = Taxa de chegada
 = Taxa de serviço
m = Quantidade de servidores
2. Utilização (intensidade de tráfego) média de um servidor:   m) / 
3. Condição de Estabilidade:   
4. Intensidade de tráfego do sistema (dos m servidores): ’   / 
5. Tempo de residência médio:
Pq 
1
r  1

  m(1  ) 
6. Quantidade média de clientes no sistema:
.Pq
n  m. 
(1  )
Pq 

w  r  s  s 1
s
 m(1  ) 
7. Tempo de espera médio, sendo:
Logo:
w
sPq
m(1  )

sPq
m A
Pq = probabilidade de todos os servidores estarem ocupados (ocorre
formação de fila). Onde:
.mm P0
Pq =
m! 
A equação anterior é conhecida como equação de Erlang-C. Tendo sido
tabulada e é bastante utilizada em sistemas de telefonia.
P0 = probabilidade do sistema estar vazio (sem clientes). Dada por:
m-1
P0 =

n=0
.mn
n!
.mm
+
m! 
1
SISTEMA DE FILA M/M/
o Sistema com quantidade infinita de servidores,
o Todo o cliente que chega ao sistema encontra um
servidor livre e é imediatamente atendido,
o Taxas de chegada e de serviço possuem distribuição
exponencial,
o Não existe fila de espera, o comprimento da fila e o
tempo de espera são nulos,
o É um sistema que introduz apenas um atraso
equivalente ao tempo de serviço,
o Utiliza as equações do sistema M/M/m na situação
limite, quando m = .
SISTEMA DE FILA M/M/
o Probabilidade de sistema vazio:
p0  e


o Probabilidade de n clientes no sistema:

 e 
p n   
   n!
n
Para n > 0
n
o Quantidade de clientes no sistema:
o Tempo médio de residência:
r
1



SISTEMA DE FILA M/M/M/B
o
o
o
o
o
Distribuição do tempo entre chegadas: Exponencial
Distribuição do tempo de serviço: Exponencial
Quantidade de Servidor(es): m
Capacidade do Sistema: B
Trata-se de um sistema com m servidores e B buffers, onde
B  m (cada servidor possui uma posição de buffer)
o Se as B posições estiverem ocupadas, os clientes
subseqüentes são perdidos
SISTEMA DE FILA M/M/M/B DIAGRAMA DE TRANSIÇÃO DE ESTADOS
0
Estado:
0

1
1
m-2
1
2
m-1
m–1
m-1
m
m
m
m+1
m+1
k-1

m+1 m+2
B
b
Estado = quantidade de clientes no sistema
Para o sistema M/M/m/B , onde B  m
n = 0, 1, 2, ..., B-1 e
n =  ,
n = 0, para n  B
n = n. , n = 1, 2, 3, ..., m e n = m., para n  B
SISTEMA DE FILA M/M/M/B DIAGRAMA DE TRANSIÇÃO DE ESTADOS

Estado:
0


1


.

m–1
m. m.

m

m+1
m.
m.
Estado = quantidade de clientes no sistema
Sistema M/M/m/B , onde: B(buffers)  m(servers)


B
m.
SISTEMA DE FILA M/M/M/B
o Probabilidade do sistema estar vazio, nenhum servidor
ocupado:
m
n
Bm1
m1

p0
1  
 1

m 
m!1  

o Probabilidade de haverem n clientes no sistema:

m n

Para n < m:
pn
Para m ≤ n ≤ B:
mm n
pn 
p0
m!
n!
p0
n1
m  

n! 
1
o Quantidade de clientes na fila:
nq 
B
 (n  m) p
nm1
o Tempo de espera na fila:
w
nq
'
n
CASOS PARTICULARES DO
SISTEMA M/M/M/B
o O sistema M/M/m/B pode originar dois tipos
de sistemas de fila:
o Sistema M/M/m/m, onde m=B, que é aplicável a sistemas
de capacidade m e quantidade de servidores m, sem
espaço de espera. Cada um dos m servidores comporta
um cliente
o Sistema M/M/1/B, onde m=1, que é aplicável a sistemas
de capacidade B e 1 servidor. Ou seja, B- 1 posições de
espera
SISTEMA DE FILA M/M/N/N/K
o Sistema representado esquematicamente conforme a figura:


1
2
1
2

K
N


  n.

o Sistema com N servidores, população K finita (onde: K
 N). Sem espaço de espera
o A taxa de serviço  possui distribuição exponencial
o Em dado instante, existirão n clientes (onde: 0 ≤ n ≤ N)
e cada um será atendido por um único servidor
o Se n > N, pode haver rejeição de clientes (bloqueio)
SISTEMA DE FILA M/M/N/N/K

Pode ser utilizado para modelar:
–
–
Uma central telefônica com K assinantes entradas e
N troncos de saída
Uma ERB com K usuários e N frequências de RF
(canais)
SISTEMA DE FILA M/G/1
o Sistema de fila onde a taxa de serviço atende a
distribuição Geral
o Pode ser utilizado, por exemplo, para modelar o
tráfego em:
o Sistemas com prioridade não preemptivos
o Sistemas onde o tempo de serviço está dividido em
classes conhecidas
SISTEMA DE FILA M/G/1
   

n  
 1  1   2 2 

 1    2

o Quantidade de clientes no sistema:
o Tempo de residência no sistema:
o Tempo de espera na fila:

 1   

r   
 1 1   2 2 
  1    2

n
wrs
o Um caso particular do sistema M/G/1 é o M/D/1
(sistema determinístico), onde: =0


PRATICANDO

Porque analisar diferentes modelos?
OBTENÇÃO DE DADOS

Dados:


É preciso estimar valores para a o tempo médio entre
duas chegadas de automóveis no sistema e para o
tempo médio de uma lavação.
Tais informações podem ser obtidas de duas
possíveis fontes:
das estimativas do proprietário;
 amostragem realizada no sistema.


Possível ser feito uma analise “grosseira” a partir
de estimativas.

Normalmente é usado a distribuição exponencial
para o processo de chegadas.
EXEMPLO CARWASH

Ideia:


Carros em fila para lavagem.
Objetivo:
Analisar se um posto de atendimento é suficiente,
 Testar outros modelos,
 Encontrar n ótimo.

EXEMPLO SUPERMARKET

Ideia:


Primeiro é necessário passar as compras e depois
pagar em outro local.
Objetivo:
Analisar se um posto de atendimento é suficiente,
 Testar outros modelos,
 Encontrar n ótimo.

EXEMPLO FABRICA DE PIPAS
Exemplo Paulo Freitas
 Objetivo:


Analisar o comportamento de uma fábrica.
DADOS
DADOS
DADOS
BIBLIOGRAFIA
http://www.lee.eng.uerj.br/~gil/filas/Filas.pdf
 Introdução a Simulação de Sistemas – Clovis Filho
 Introdução à Modelagem e Simulação de Sistemas –
Paulo Freitas
 http://www.deinf.ufma.br/~mario/grad/filas/filas.pdf
 http://digituma.uma.pt/bitstream/10400.13/48/1/Mes
tradoCl%C3%A1udiaPereira.pdf
 http://www.uff.br/anibalvilcapoma/aulas/03Simulacao/APOSTILA_ARENA_11.pdf
