Teoria das Filas

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Teoria das Filas
Guilherme Amaral Avelino
gavelino@gmail.com
Avaliação e Controle de Sistemas de Informação
*
*
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 
veículos, aeronaves, pessoas e comunicações
Escalonamento
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
Servidor
Servidor
População
Fila
Clientes
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 valores podem ser observados
A fim de caracterizar ainda mais uma fila podemos definir sua distribuição de freqüências
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)
FIFO
Filas comuns onde o primeiro a chegar é o primeiro a ser atendido
Last-Come-First-Served(LCFS)
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
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
Gráf1
		0
		0
		0
		0
		0
		1
		2
		8
		14
		17
		18
		11
		6
		4.5
		4
		3.5
		3
		2.8
		2.5
		2.2
		1.8
		1.4
		1
		0.8
		0.6
		0.5
Variável randômica
Duração do Atendimento (s)
Probabilidade
Plan1
				Variável randômica
		0		0
		1		0
		2		0
		3		0
		4		0
		5		1
		6		2
		7		8
		8		14
		9		17
		10		18
		11		11
		12		6
		13		4.5
		14		4
		15		3.5
		16		3
		17		2.8
		18		2.5
		19		2.2
		20		1.8
		21		1.4
		22		1
		23		0.8
		24		0.6
		25		0.5
*
*
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
Onde
Intervalo – tempo entre uma chegada e outra
Momento – instante de chegada de um novo cliente
Definir
λ 
IC
24 clientes por hora
2,5 minutos
*
*
Observando a Dinâmica de uma Fila
Atendimento
Dados anotados para cada atendimento em minutos
Determinar
μ
TA
30 clientes por hora
2 minutos
*
*
Gráfico do Funcionamento da Fila
*
*
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
Total de clientes atendidos
Tempo Médio na Fila (TMF)
Número Médio na Fila (NMF)
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
12
(3+4+3+1+3+2)/12 = 1,33 minutos
(3+4+3+1+3+2)/35 = 0,46 cliente
*
*
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
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
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
Sistemas Estáveis
Fluxo médio de entrada (λ) constante
Ritmo medio de atendimento (μ) constante
μ > λ
*
*
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
As durações da carga (em horas) de cada navio são as seguintes
Calcule:
O intervalo médio entre chegadas
A duração média da carga
Monte o desenho de funcionamento do sistema 
O tamanho médio da fila
O tempo médio de espera na fila
*
*
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)
FIFO
Filas comuns onde o primeiro a chegar é o primeiro a ser atendido
Last-Come-First-Served(LCFS)
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
5. Número de canais de serviço
...
6. Estágios de serviços
n
*
*
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
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
medida da maneira como os clientes podem ir se acumulando
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
*
*
*
*
*