Teoria de Filas – Aula 15
Aula Passada
Prova
Aula de hoje
Correção Prova
Little, medidas de
interesse em filas
Figueiredo – de Souza e Silva – 2007
Medidas de
Desempenho
em Filas

K

Utilização: fração de tempo que o servidor está
ocupado
Tempo de espera: quantidade de tempo que
cada elemento espera na fila
Vazão (Throughput): quantidade de elementos
servidos pela fila por unidade de tempo
Fração de descarte: fração de elementos
descartados por falta de espaço na fila
Figueiredo – de Souza e Silva – 2007
Utilização
N(t)
evolução do
tamanho
da fila no
tempo
t
Sistema ocioso
Sistema ocupado
Utilização: fração de tempo que sistema
está ocupado
U=
+
+
+
+
+ ... +
Figueiredo – de Souza e Silva – 2007
Calculando a Utilização
Seja T um intervalo de tempo qualquer (grande)

T
E[X]
 T E[X]
 T E[X]
T
E[X]
Número médio de pedidos
que chegam no intervalo
Tempo médio para servir cada pedido
Tempo médio para servir todos os pedidos
Fração de tempo servindo os pedidos
Utilização
Figueiredo – de Souza e Silva – 2007
O que é  E[X] ?

: taxa média de chegada
E[X] : tempo médio de serviço
 E[X] : adimensional
 E[X] > 1 : chegada maior que serviço
Fila irá crescer indefinidamente
 E[X] < 1 : chegada menor que serviço
Fila sobre controle
 E[X]
: utilização do sistema
Fração de tempo que o sistema
passa servindo pedidos
Figueiredo – de Souza e Silva – 2007
Tempo de Espera
Como calcular o tempo de espera em uma
fila?
tempo decorrido desde o instante de chegada
até o instante de saída
IDÉIA: Decompor o tempo de espera
em tempos menores
Tempo para finalizar o pedido sendo atendido
no instante de chegada
Tempo para atender cada um dos pedidos da
fila
Tempo para atender o pedido que acabou de
chegar
Figueiredo – de Souza e Silva – 2007
Variáveis Aleatórias de uma
Fila
W
A
Nc
X
Nc : número de pedidos na fila quando nosso pedido
chega (incluindo o que está sendo atendido)
R : tempo residual (tempo para finalizar
atendimento do pedido sendo atendido)
Xi : tempo necessário para atender o i-ésimo pedido
da fila (i=1, 2, ..., Nc - 1)
W : tempo de espera de um pedido (do instante de
chegada até o instante de saída)
Figueiredo – de Souza e Silva – 2007
Tempo de
Espera
W
A
Nc
X
W: tempo de espera do pedido que chegou
Nc pedidos no sistema
1 em atendimento + Nc – 1 na fila
Quanto vale W?
W = R + X1 + X2 + ... + XNc-1 + X
tempo residual
do elemento em
atendimento
tempo de serviço
do i-ésimo elemento
da fila
tempo de serviço
do elemento que
acabou de chegar
Figueiredo – de Souza e Silva – 2007
Tempo Médio de Espera
W
A
Nc
X
Aplicar valor esperado – E[.]
Tempo médio de espera: E[W]
E[W] = E[R + X1 + X2 + ... + XNc-1 + X]
E[W] = E[R] + E[X1]+ ... + E[XNc-1]+ E[X]
E[W] = E[R] + E[Nc]E[X]
Xi são idênticamente
distribuídas
Figueiredo – de Souza e Silva – 2007
Resultado de Little
E[W]

Caixa Preta
E[N]

: taxa média de chegada
E[W] : tempo médio que cada pedido permanece
dentro da caixa preta
E[N] : número médio de pedidos dentro da caixa
(depois de um tempo muito grande)
Qual é a relação entre eles?
E[N] =
 E[W]
Vamos provar
isto hoje!
Figueiredo – de Souza e Silva – 2007
Resultado de Little
E[W]

Caixa Preta
E[N]
Número médio dentro do sistema é igual ao
produto da taxa média de chegada pelo tempo
médio de permanência no sistema
Intuitivo, mas poderoso (não depende de
nenhuma distribuição)
Exemplo:
E[W] = 3.5 minutos
=2
E[N] = ?
clientes por minuto
Figueiredo – de Souza e Silva – 2007
Resolvendo o Tempo
Média de Espera
Duas equações:
E[W] = E[R] + E[Nc]E[X]
E[N] =  E[W]
Suposição (I) :
E[N] = E[Nc]
Suposição (II) :
E[R] = E[X]
Substituindo nas equações acima, temos
E[W] = E[X] +
E[W] =
 E[W]E[X]
E[X]
1 –  E[X]
equação em função dos
parâmetros da fila
Figueiredo – de Souza e Silva – 2007
Suposição I: E[N] = E[Nc]
Duas variáveis (medidas)
Número de elementos no sistema
N – em um instante de tempo qualquer
Nc – no instante de uma chegada
Figueiredo – de Souza e Silva – 2007
Suposição I
E[N] = E[Nc]
Quando isto é verdade?
PASTA
Poisson Arrivals See
Time Averages
pas
Quando o processo de chegada é Poisson
E[N] = E[Nc]
Figueiredo – de Souza e Silva – 2007
Suposição II
E[R] = E[X]
Quando isto é verdade?
Memoryless
Distribuição não tem
memória
Quando o tempo de serviço é exponencial
Figueiredo – de Souza e Silva – 2007
Medidas de Desempenho
em Filas
Comportamento típico
Tempo
de
espera

K

Vazão



Tradeoff entre tempo de resposta e vazão
Figueiredo – de Souza e Silva – 2007
Aplicando a Lei de Little
Cálculo do número médio de clientes no
SISTEMA (fila + serviço):
E[N] = λE[W]
Cálculo do número médio de clientes na FILA
E[Nq]=λE[Wq]
Figueiredo – de Souza e Silva – 2007