Avaliação e Controle de Sistemas de Informação
Teoria das Filas
Guilherme Amaral Avelino
[email protected]
Por que das filas?

Procura por um serviço maior do que a capacidade do
sistema de atender ao serviço


Inviabilidade econômica
Limitação de espaço
Teoria das Filas


A Teoria das Filas tenta através de análises matemáticas
detalhadas encontrar um ponto de equilíbrio que satisfaça
o cliente e seja viável economicamente para o provedor
do serviço
Exemplos de aplicação:

Fluxo de tráfego


Escalonamento


veículos, aeronaves, pessoas e comunicações
Pacientes em hospitais, processos em um computador e jobs em
máquinas
Projetos de atendimentos a serviços

Bancos, correios, restaurantes fast-foods
Elementos de uma Fila
Servidor
Clientes
Servidor
Fila
População
Servidor
Atendimento
*Obs:
•Servidores, atendentes ou canais de serviços
•Cliente, transação ou entidade

Clientes e Tamanho da População



Um cliente é proveniente da população
Quando uma população é muito grande, a chegada de um novo
cliente a fila não afeta a taxa de chegada de clientes
subseqüentes, taxa de chegada independente
Quando a população é reduzida a taxa de chegada pode ser
dependente

Ex: Uma mineradora que possui apenas 3 caminhões e os 3 estão na
fila
Processo de Chegada


Podemos quantificar o processo de chegada através de sua taxa
média de chegadas (λ) e/ou seu intervalo médio entre chegadas
(IC)
Ex: Um posto de pedágio com 5 atendentes, onde entre 7 e 8 horas
da manha chegam 20 automóveis por minuto.


λ:20 veículos por minuto
IC: 3 segundos

λ e IC são valores médios, em um dado instante diferentes

A fim de caracterizar ainda mais uma fila podemos definir sua
distribuição de freqüências
valores podem ser observados



Processos com os mesmos valores médios podem apresentar grandes
variações de seu valores individuais durante o tempo observado
Processos regulares são raros
Existe situações onde o ritmo de chegadas sofre variações durante
o dia
Processo de Atendimento


Determina como é feito o atendimento aos clientes da
fila
Ex:


Observando um atendente, podemos constatar que ele atende
6 veículos por minuto ou que gasta 10 segundos para atender
um veículo
Podemos quantificar o processo de chegada através
de sua taxa média de atendimento (μ) e/ou seu
tempo ou duração médio de serviços (TA)


μ = 6 clientes por minuto
TA = 10 clientes por minuto
Número de servidores


Uma fila pode possuir um ou mais servidores para
atender os clientes
A qualidade do serviço pode ser melhorada adicionando
convenientemente novos servidores ao sistema

Ex: fila de supermecado
Disciplina da Fila


Descreve como os clientes são escolhidos para entrar em um
serviço após a fila ser formada
First-Come-First-Served (FCFS)



Last-Come-First-Served(LCFS)



FIFO
Filas comuns onde o primeiro a chegar é o primeiro a ser atendido
LIFO
Aplicado em sistemas de controle de estoque e em filas de prioridades
Filas com Prioridades

Preemptivo


Não-preemptivo


O cliente com maior prioridade é servido imediatamente
O cliente com maior prioridade entra na frente da fila, mas deve aguardar se
algum cliente já estiver em atendimento
Filas Randômicas
Tamanho da Fila

Tamanho Médio



Característica mais visível de uma fila
O dimensionamento adequado desta característica possibilita
um atendimento satisfatório
Tamanho Máximo



Área destinada a espera por atendimento
Ex: número de cadeiras em uma barbearia, tamanho do buffer,
etc
Dependendo do tamanho e da demanda um cliente pode ser
recusado


Ex: central telefônica
Deve ser projetada de forma atender a demanda
Tempo Médio de Espera na Fila




Média do tempo gasto por cada cliente desde o
momento em que chega na fila ao que ele é atendido
Principal causa de irritação dos clientes
O ideal é que não exista tempo de espera
Ex:

Se entrarmos em uma fila com 10 pessoas à frente o tempo de
espera será igual ao somatório dos tempos de atendimento
cada um dos 10 clientes ou, possivelmente, será igual a 10
vezes a duração média de atendimento
Variáveis Randômicas




São utilizadas para modelar diversos aspectos de uma fila
Quando afirmamos que a duração média de atendimento é de
10 segundos não estamos dizendo que todo atendimento é de
10 segundos
Diferentes momentos podem registrar diferentes valores
Caso fosse coletada uma grande quantidade de dados
poderíamos deduzir que existe um padrão de atendimento
expresso por uma distribuição de probabilidade



É nula a probabilidade de atender um cliente em menos de 5
segundos
A probabilidade de atender um cliente em 10 segundos é de 18%
A probabilidade de atender um cliente em 25 segundos é de 0,5%
Duração do Atendimento
Observando a Dinâmica de uma Fila

Cenário


Fila de um banco formada por pessoas que deseja um novo
talão de cheques
Chegada

No período de meia hora chegaram ao sistema 12 pessoas
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
Momento
2
5
8
11
16
16
17
22
23
27
28
30

Onde



Intervalo – tempo entre uma chegada e outra
Momento – instante de chegada de um novo cliente
Definir


λ 24 clientes por hora
IC 2,5 minutos
Observando a Dinâmica de uma Fila

Atendimento

Dados anotados para cada atendimento em minutos
Cliente
1
2
3
4
5
6
7
8
9
10 11 12
Duração 1
2
1
1
3
2
1
4
2
3

Determinar


μ 30 clientes por hora
TA 2 minutos
1
3
Gráfico do Funcionamento da Fila
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
Momento
2
5
8
11
16
16
17
22
23
27
28
30
Fila
Atendimento
Cliente
1
2
3
4
5
6
7
8
9
10 11 12
Duração 1
2
1
1
3
2
1
4
2
3
1
3
Observando a Dinâmica de uma Fila







O primeiro cliente chegou ao banco no inicio do segundo minuto e
seu atendimento durou 1 minuto
O quinto cliente chegou ao banco no inicio do 17ᴼ minuto e seu
atendimento durou 3 minutos
O sexto cliente chegou ao banco simultaneamente com o quinto
cliente no 17ᴼ minuto e, então, esperou na fila até completar o
atendimento do quinto cliente, o que ocorreu no final do 19ᴼ minuto
O sétimo cliente chegou ao banco no 19ᴼ minuto e encontrou o
atendente ocupado e o sexto cliente na fila
Além dos clientes de número 6 e 7, também os clientes de número 9
a 12 tiveram que esperar em fila
O último cliente (12ᴼ) saiu do atendimento no final do 35ᴼ minuto
...
Conclusões

Tempos de fila
Cliente




1
2
3
4
5
6
7
8
9
10 11 12
Duração 0
0
0
0
0
3
4
0
3
1
3
2
12
Total de clientes atendidos
(3+4+3+1+3+2)/12 = 1,33 minutos
Tempo Médio na Fila (TMF)
Número Médio na Fila (NMF) (3+4+3+1+3+2)/35 = 0,46 cliente
Mesmo sendo a capacidade de atendimento (μ) superior
ao ritmo de chegada (λ) foi observada a formação de filas

Em um sistema de filas, geralmente, tanto o processo de
chegada como o de atendimento não são regulares
Sistemas Estáveis


A abordagem matemática de filas pela Teoria das Filas
exige que exista estabilidade no fluxo de chegada e no
processo de atendimento
Ex: fluxo de chegada de clientes em uma fila de banco
durante o dia


Período
10 às12h
12 às 14h
14 às 16h
Fluxo
Médio
Alto
Médio
Não existe estabilidade para o ritmo de chegada no período
de 10:00 às 16:00
Para analisar utilizando a Teoria das Filas faz-se o uso do
artifício de retalhar o período global em períodos parciais
Sistemas Estáveis

Outra exigência para que o processo seja estável é que os
atendentes sejam capazes atender ao fluxo de chegada


μ>λ
Filas ocorrem porque:


Em um dado instante podem chegar mais clientes que a capacidade de
atendimento naquele momento
O atendimento de um dado cliente pode demorar mais que o normal
Sistemas Estáveis
•Fluxo médio de entrada (λ) constante
•Ritmo medio de atendimento (μ) constante
•μ > λ

Em sistemas estáveis, todas as características randômicas das
filas se mantêm estáveis, oscilam em torno de um valor médio
Dimensionando Filas


Objetiva prestar um melhor serviço aos clientes ou obter
uma redução de custos do funcionamento do sistema
Tipo de fila e qualidade de serviço






Fila e servidor único
Fila única e diversos servidores
Diversas filas com servidores correspondentes
Filas especiais
Alteração dinâmica no sistema de atendimento
A escolha do tipo de fila depende das características do
sistema

Fila de banco x supermercado
Exercício
Considere um sistema em que navios chegam a um porto para carregar algum
produto. Abaixo estão anotados os valores entre chegadas (em horas) para 20
navios
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Intervalo 10 2 13 7 02 8 8 8 10 9 1 14 14 1 10 9
As durações da carga (em horas) de cada navio são as seguintes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Cliente
Duração 10 2 13 7 02 8 8 8 10 9 1 14 14 1 10 9
Cliente
Calcule:
a)
O intervalo médio entre chegadas
b)
A duração média da carga
c)
Monte o desenho de funcionamento do sistema
d)
O tamanho médio da fila
e)
O tempo médio de espera na fila
17 18 19 20
9 9 8 14
17 18 19 20
9 9 8 14
Características dos Processos de Filas

Na maioria dos casos podemos descrever um sistema de
filas através de seu:






Padrão de chegada dos clientes
Padrões de serviço
Disciplina de filas
Capacidade do sistema
Número de canais de serviços
Número de estágios de serviços
Padrão de Chegada dos Clientes


Padrões de chegadas são processos estocásticos, ou seja
desenvolvem-se no tempo e no espaço conforme leis de
probabilidade
Distribuições probabilísticas



Tempos de interchegada
Chegada em batch
Reações do cliente

Clientes decepcionados


Recusa do cliente a entrar na fila
Clientes impacientes


Cliente sai após algum tempo
Cliente muda de fila
Padrão de Chegada dos Clientes

O padrão de chegada muda com o tempo?


Estacionário
Não-estacionário
Padrões de Serviço


Podem ser simples ou em batch
Pode depender do número de clientes na fila



Serviço dependente do estado
Pode trabalhar mais rápido ou se atrapalhar com o aumento
do número de clientes
Pode melhorar com o tempo


Serviço não-estacionário
Aprendizado como fator de produtividade
Disciplina de Filas


Descreve como os clientes são escolhidos para entrar em um
serviço após a fila ser formada
First-Come-First-Served (FCFS)



Last-Come-First-Served(LCFS)



FIFO
Filas comuns onde o primeiro a chegar é o primeiro a ser atendido
LIFO
Aplicado em sistemas de controle de estoque e em filas de
prioridades
Filas com Prioridades

Preemptivo


O cliente com maior prioridade é servido imediatamente
Não-preemptivo

O cliente com maior prioridade entra na frente da fila, mas deve aguardar
se algum cliente já estiver em atendimento
Capacidade do Sistema


Sistemas de filas podem ter um limite de capacidade (filas
finitas)
Quando atingido o limite da fila nenhum cliente novo
poderá ser adicionado até que um cliente desocupe a fila
Número de Canais de Serviço


O número de canais correspondem ao número de
estações de serviços paralelos que podem servir os
clientes simultaneamente
Clientes multi-canais podem ser de:


Fila única
Fila individual
Estágio de Serviço

Estágio único



O atendimento do cliente acontece de um vez só
Barbearia, supermecado, etc
Vários estágios



O cliente passa por vários estágios de atendimento, antes de
finalizar um serviço
Durante o atendimento o cliente pode enfrentar diversas filas
com características diversas
Exame físico, atendimento serviço público
Estágio de Serviço
Descrição de um Sistema de Filas
1.Padrão de
chegada
2.Padrão de
serviço
3.Disciplina
de filas
...
4.Capacidade
do sistema
n
5. Número de
canais de
serviço
6. Estágios de
serviços
Notação de Fila


Proposta em 1953 por Kendall
é descrita por um série de símbolos, tais como,
A/B/m/k/M






A é a distribuição de inter-chegada de dos clientes
B é padrão de serviço de acordo com um distribuição de
probabilidade para o tempo de serviço
m é o número de canais serviços paralelos (servidores)
k é a capacidade do sistema
M é a disciplina de filas
Em muitas situações só os três primeiros símbolos são
utilizados, de maneira que, é assumido que o sistema tem
capacidade ilimitada e possui uma disciplina FCFS
Notação de Fila – Tabela A/B/m/k/M
O símbolo G representa uma distribuição de probabilidade geral, isto é, resultados
nestes casos são aplicáveis para qualquer distribuição de probabilidade

Exemplo:
M/D/2/∞/FCFS

Processo de filas com:





tempos de inter-chegada exponencial
tempos de serviço determinístico
dois servidores paralelos
capacidade ilimitada
disciplina de fila FCFS
Medindo o Desempenho do Sistema

Geralmente existem 3 tipos de respostas de interesse do
sistema:

medida do tempo de espera que um cliente típico é obrigado a
esperar



medida da maneira como os clientes podem ir se acumulando



Tempo gasto na fila X Tempo total no sistema
Importância de cada tipo depende do sistema analisado. Ex: Parque de
diversão x concerto de um equipamento
Número de clientes na fila X número de clientes no sistema
Auxilia na definição do espaço de espera dos clientes
medida do tempo ocioso dos servidores


Tempo em que um servidor em particular esta ocioso
Tempo em que o sistema está desprovido de clientes
Medindo o Desempenho do Sistema

A tarefa do analista de filas é determinar as medidas
apropriadas de efetividade de um dado processo, ou
projetar um sistema ótimo.




Tempo de espera X ociosidade do sistema
Tempo de espera X custos
Cálculo do tamanho da fila de espera
Uso de métodos analíticos como primeira alternativa e
simulações onde métodos analíticos não forem suficientes