Teoria das filas
1 - Elementos de uma fila:
Servidores
Clientes
1
2
Fila
População
3
Atendimento
2 – Características de uma fila:
2.1 – Clientes e tamanho da população
População infinita => Chegadas independentes
População finita => Chegadas interdependentes
2.2 – Processo de chegadas:
Não basta fornecer valores médios, é necessário também
mostrar como os valores se distribuem em torno da média, i.e., qual
distribuição de probabilidades rege o processo.
= Ritmo de chegada
IC = Intervalo entre chegadas
Obs: Intervalos regulares => processos altamente automatizados
2.3 – Processo de atendimento:
= Ritmo de atendimento
TA = Tempo de atendimento
2.4 – Número de servidores:
Quantidade de servidores que atendem aos clientes
2.5 – Disciplinas das filas:
FIFO = First in, first out
LIFO = Last in, first out
Prioridade = Uma característica do cliente define sua prioridade
de atendimento
Randômico = Atendimento aleatório
2. 6 – Tamanho médio da fila:
Se e são constantes => o tamanho da fila oscila em torno de
um valor médio. Se < a fila aumentará indefinidamente.
2.7 – Tamanho máximo da fila:
Os clientes devem aguardar em uma área de espera que deve ser
dimensionada de acordo com o tamanho máximo esperado para a fila.
2.8 – Tempo médio de espera:
O tempo médio de espera depende dos processos de chegada e
atendimento.
TF = f ( , )
3 – Variáveis aleatórias:
O comportamento de uma variável aleatória pode ser expresso pelo seu valor
médio e a forma como os valores se distribuem em torno desta média.
4 – Dinâmica de uma fila:
Exemplo de um banco:
Intervalo entre chegadas (minutos):
Cliente
1 2 3 4 5 6 7 8 9 10 11 12
Intervalo
2 3 3 3 5 0 1 5 1 4
1 2 Média=2.5
Momento 2 5 8 11 16 16 17 22 23 27 28 30 = 24 / h
Duração do atendimento:
Cliente
1 2 3 4 5
Duração
1 2 1 1 4
6
2
7
1
8
4
9 10 11 12
2 3
1 3 Média=2.0
= 30 / h
Tempo de espera de cada cliente:
Cliente
Momento
Duração
Liberação
Espera
1
2
1
3
0
2
5
2
7
0
3
8
1
9
0
4 5 6 7
11 16 16 17
1 3 2 1
12 19 21 22
0
0 3 4
8
22
4
26
0
9
23
2
28
3
10 11 12
27 28 30
3
1 3
31 32 35
1 3
2
TF = (3+4+3+1+3+2)/12 = 16/12 = 1.33 min
NF = (3+4+3+1+3+2)/35 = 16/35 = 0.46 clientes
5 - Sistemas estáveis:
Sistema estável é aquele em que e se mantêm constantes ao longo do
tempo. Se e não são estáveis, a análise do comportamento do sistema
Pela teoria das filas só é possível se retalharmos o período de tempo, o que
torna a análise muito mais complexa.
6 – Tamanho da amostra:
Um estudo sobre um sistema estável, apresentará sempre os mesmos resultados
desde que adequadamente analisado.
O tamanho da amostra é fundamental.
7 – Tipos de filas:
7.1 – 1 fila e 1 servidor
7.2 – 1 fila e n servidores
7.3 – m filas e n servidores
7.4 – filas especiais (ex: caixas expressos de supermercados)
7.6 – filas que seguem uma alteração dinâmica do sistema de atendimento
8 - Variáveis aleatórias fundamentais:
8.1 - Variáveis referentes ao sistema:
TS = tempo médio de permanência no sistema
NS = nr. médio de clientes no sistema
8.2 - Variáveis referentes ao processo de chegada:
= ritmo médio de chegada
IC = intervalo entre chegadas
por definição: IC = 1/
8.3 - Variáveis referentes à fila:
TF = tempo médio de permanência na fila
NF = nr. médio de clientes na fila
8.4 - Variáveis referentes ao processo de atendimento:
TA = tempo médio de atendimento ou serviço
M = quantidade de atendentes ou servidores
NA = nr. médio de clientes que estão sendo atendidos
= ritmo médio de atendimento de cada atendente
por definição: TA = 1/
8.5 - Relações básicas:
NS = NF + NA
TS = TF + TA
Pode-se demonstrar também que:
NS = NF + / = NF + TA/IC
8.6 - Taxa de utilização dos atendentes:
para 1 fila e 1 servidor: = /
para 1 fila e M servidores: = /(M )
Assim, representa a fração média de tempo em que cada servidor está
ocupado.
Para sistemas estáveis, tem-se que : < 1
8.7 - Intensidade de tráfego ou número mínimo de atendentes:
i = | / | = |TA/IC|
i é o próximo valor inteiro que se obtém pela divisão / . Assim, i representa
o número mínimo de atendentes necessário para atender a um dado fluxo de
tráfego.
Unidade de i = erlangs ( em homenagem A. K. Erlang)
8.8 - Fórmulas de Little (J. D. C. Little):
NF = . TF
NS = . TS
8.9 - Postulados básicos:
1 - Em qualquer sistema estável, o fluxo que entra é igual ao fluxo que sai.
2 - Em um sistema estável, o fluxo de entrada se mantém nas diversas seções
do sistema.
3 - Em um sistema estável, a junção de fluxos equivale às suas somas.
4 - Em um sistema estável, o fluxo se desdobra aritmeticamente.
9 - Processos de chegada e atendimento:
Exemplo de chegadas de veículos a um pedágio: foram anotados o número
de veículos que chegaram a cada intervalo de 1 min. Entre 7 e 8 horas.
Chegaram no total 120 veículos.
Ritmo Freq. Absoluta
0
9
1
17
2
17
3
9
4
4
5
1
6
1
7
1
8
1
9
0
10
0
Freq. Relativa
0.150
0.283
0.283
0.150
0.066
0.017
0.017
0.017
0.017
0.000
0.000
= 120 veículos / 60 min = 2 veículos / min.
Dist. Poisson ( =2)
0.135
0.271
0.271
0.180
0.090
0.036
0.012
0.003
0.001
0.000
0.000
Distribuição de Poisson:
f ( x) =
λxe −λ
x!
x é a probabilidade ( freq. Relativa) de ocorrerem x chegadas na unidade
de tempo, sendo que representa o ritmo médio de chegadas. Por ex: para
x = 2 tem-se: f(2) = 0.271.
Distribuição Exponencial Negativa:
Quando um processo de chegada possui um ritmo que segue Poisson, o
intervalo entre chegadas segue uma distribuição exponencial negativa.
f (x) = λe −λx
Notação de Kendall (David Kendall):
Fila A/B/c/K/m/Z
onde:
A = distribuição dos intervalos entre chegadas
B = distribuição dos tempo de serviço
c = quantidade de servidores (atendentes)
K = capacidade max. Do sistema
m = tamanho da população
Z = disciplina da fila
A anotação condensada A/B/c é muito usada e se supõe que não há limite
para o tamanho da fila, a população é infinita e a disciplina é FIFO.
Para A e B, quando a distribuição for exp. Negativa, usa-se M (Marcoviana)
Filas: Modelo M/M/1
Modelo de fila que tanto as chegadas quanto o atendimento são marcovianos,
i.e., seguem a distribuição de Poisson (p/ ritmos) ou exponcencial negativa
(p/ intervalos). Além disso, existe apenas um servidor.
1 - População infinita - Fórmulas usuais (dedução : vide ref. 03 –Cap. 07):
1 – Nr. Médio de clientes na fila:
λ2
NF =
µ (µ − λ )
2 – Nr. Médio de clientes no sistema:
NS =
3 – Tempo médio que o cliente fica na
fila:
TF =
4 – Tempo médio que o cliente fica no
sistema:
TS =
λ
(µ − λ )
λ
µ (µ − λ )
1
(µ − λ )
5 – Probabilidade de existirem n clientes
no sistema:
Pn = (1 − λ / µ )(λ / µ ) n
Taxa de utilização:
Quando tende p/ 1 a fila tende a aumentar
Infinitamente.
NF
0
λ2
ρ2
NF =
=
µ (µ − λ ) 1 − ρ
1
2 - População finita - Fórmulas usuais (dedução : vide ref. 03 –Cap. 07):
Modelo M/M/1/K
1 – Nr. Médio de clientes na fila:
2 – Nr. Médio de clientes no sistema:
3 – Tempo médio que o cliente fica na
fila:
4 – Tempo médio que o cliente fica no
sistema:
5 – Probabilidade de existirem n clientes
no sistema:
NF = K −
NS = K −
TF =
TS =
K
λ
K
λ
−
Pn =
−
(λ + µ )
λ
(λ + µ )
λ
.(1 − P0 )
.(1 − P0 ) +
λ
µ
(λ + µ ).(1 − P0 )
λ2
( λ + µ ).(1 − P0 )
λ2
µ
λ
+
1
µ
( ) K −n
(k − n)!.
µ
λ
k
( )j
j=0
j!
Exemplo 1:
Suponhamos que as chegadas a uma cabine telefônica obedeçam a lei de
Poisson, com ritmo de 6 chegadas por hora. A duração média do telefonema
é de 3 minuts e suponhamos que siga a distribuição exponencial negativa.
Pede-se:
1 – Qual a probabilidade de uma pessoa chegar à cabine e não ter que esperar?
2 – Qual o número médio de pessoas na fila?
3 – Qual o número médio de pessoas no sistema?
4 – Qual o número médio de clientes usando o telefone?
5 – Qual o tempo médio de fila?
6 – Para qual ritmo de chegada teríamos a situação em que o tempo médio de
espera na fila seria de 3 min?
7 – Qual a fração do dia durante a qual o telefone está em uso?