-
Teoria das FilasGuilherme Amaral
[email protected] e Controle de Sistemas de
Informao
-
Por que das filas?Procura por um servio maior do que a
capacidade do sistema de atender ao servioInviabilidade
econmicaLimitao de espao
-
Teoria das FilasA Teoria das Filas tenta atravs de anlises
matemticas detalhadas encontrar um ponto de equilbrio que satisfaa
o cliente e seja vivel economicamente para o provedor do
servioExemplos de aplicao:Fluxo de trfego veculos, aeronaves,
pessoas e comunicaesEscalonamentoPacientes em hospitais, processos
em um computador e jobs em mquinasProjetos de atendimentos a
serviosBancos, correios, restaurantes fast-foods
-
Elementos de uma Fila
Servidor
Servidor
ServidorPopulaoFilaClientesAtendimento*Obs:Servidores,
atendentes ou canais de serviosCliente, transao ou entidade
-
Clientes e Tamanho da PopulaoUm cliente proveniente da
populaoQuando uma populao muito grande, a chegada de um novo
cliente a fila no afeta a taxa de chegada de clientes subseqentes,
taxa de chegada independenteQuando a populao reduzida a taxa de
chegada pode ser dependenteEx: Uma mineradora que possui apenas 3
caminhes e os 3 esto na fila
-
Processo de ChegadaPodemos quantificar o processo de chegada
atravs de sua taxa mdia de chegadas () e/ou seu intervalo mdio
entre chegadas (IC)Ex: Um posto de pedgio com 5 atendentes, onde
entre 7 e 8 horas da manha chegam 20 automveis por minuto.:20
veculos por minutoIC: 3 segundos e IC so valores mdios, em um dado
instante diferentes valores podem ser observadosA fim de
caracterizar ainda mais uma fila podemos definir sua distribuio de
freqnciasProcessos com os mesmos valores mdios podem apresentar
grandes variaes de seu valores individuais durante o tempo
observadoProcessos regulares so rarosExiste situaes onde o ritmo de
chegadas sofre variaes durante o dia
-
Processo de AtendimentoDetermina como feito o atendimento aos
clientes da filaEx:Observando um atendente, podemos constatar que
ele atende 6 veculos por minuto ou que gasta 10 segundos para
atender um veculoPodemos quantificar o processo de chegada atravs
de sua taxa mdia de atendimento () e/ou seu tempo ou durao mdio de
servios (TA) = 6 clientes por minutoTA = 10 clientes por minuto
-
Nmero de servidoresUma fila pode possuir um ou mais servidores
para atender os clientesA qualidade do servio pode ser melhorada
adicionando convenientemente novos servidores ao sistemaEx: fila de
supermecado
-
Disciplina da FilaDescreve como os clientes so escolhidos para
entrar em um servio aps a fila ser formadaFirst-Come-First-Served
(FCFS)FIFOFilas comuns onde o primeiro a chegar o primeiro a ser
atendidoLast-Come-First-Served(LCFS)LIFOAplicado em sistemas de
controle de estoque e em filas de prioridadesFilas com
PrioridadesPreemptivoO cliente com maior prioridade servido
imediatamenteNo-preemptivoO cliente com maior prioridade entra na
frente da fila, mas deve aguardar se algum cliente j estiver em
atendimentoFilas Randmicas
-
Tamanho da FilaTamanho MdioCaracterstica mais visvel de uma
filaO dimensionamento adequado desta caracterstica possibilita um
atendimento satisfatrioTamanho Mximorea destinada a espera por
atendimentoEx: nmero de cadeiras em uma barbearia, tamanho do
buffer, etcDependendo do tamanho e da demanda um cliente pode ser
recusadoEx: central telefnicaDeve ser projetada de forma atender a
demanda
-
Tempo Mdio de Espera na FilaMdia do tempo gasto por cada cliente
desde o momento em que chega na fila ao que ele atendidoPrincipal
causa de irritao dos clientesO ideal que no exista tempo de
esperaEx:Se entrarmos em uma fila com 10 pessoas frente o tempo de
espera ser igual ao somatrio dos tempos de atendimento cada um dos
10 clientes ou, possivelmente, ser igual a 10 vezes a durao mdia de
atendimento
-
Variveis RandmicasSo utilizadas para modelar diversos aspectos
de uma filaQuando afirmamos que a durao mdia de atendimento de 10
segundos no estamos dizendo que todo atendimento de 10
segundosDiferentes momentos podem registrar diferentes valoresCaso
fosse coletada uma grande quantidade de dados poderamos deduzir que
existe um padro de atendimento expresso por uma distribuio de
probabilidade nula a probabilidade de atender um cliente em menos
de 5 segundosA probabilidade de atender um cliente em 10 segundos
de 18%A probabilidade de atender um cliente em 25 segundos de
0,5%
-
Durao do Atendimento
Grf1
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
Varivel randmica
Durao do Atendimento (s)
Probabilidade
Plan1
Varivel randmica
00
10
20
30
40
51
62
78
814
917
1018
1111
126
134.5
144
153.5
163
172.8
182.5
192.2
201.8
211.4
221
230.8
240.6
250.5
-
Observando a Dinmica de uma FilaCenrioFila de um banco formada
por pessoas que deseja um novo talo de chequesChegadaNo perodo de
meia hora chegaram ao sistema 12 pessoas
OndeIntervalo tempo entre uma chegada e outraMomento instante de
chegada de um novo clienteDefinir IC24 clientes por hora2,5
minutos
Cliente123456789101112Intervalo233350151412Momento258111616172223272830
-
Observando a Dinmica de uma FilaAtendimentoDados anotados para
cada atendimento em minutos
DeterminarTA30 clientes por hora2 minutos
Cliente123456789101112Durao121132142313
-
Grfico do Funcionamento da Fila
Cliente123456789101112Intervalo233350151412Momento258111616172223272830
Cliente123456789101112Durao121132142313
-
Observando a Dinmica de uma FilaO primeiro cliente chegou ao
banco no inicio do segundo minuto e seu atendimento durou 1 minutoO
quinto cliente chegou ao banco no inicio do 17 minuto e seu
atendimento durou 3 minutosO sexto cliente chegou ao banco
simultaneamente com o quinto cliente no 17 minuto e, ento, esperou
na fila at completar o atendimento do quinto cliente, o que ocorreu
no final do 19 minutoO stimo cliente chegou ao banco no 19 minuto e
encontrou o atendente ocupado e o sexto cliente na filaAlm dos
clientes de nmero 6 e 7, tambm os clientes de nmero 9 a 12 tiveram
que esperar em filaO ltimo cliente (12) saiu do atendimento no
final do 35 minuto...
-
ConclusesTempos de fila
Total de clientes atendidosTempo Mdio na Fila (TMF)Nmero Mdio na
Fila (NMF)Mesmo sendo a capacidade de atendimento () superior ao
ritmo de chegada () foi observada a formao de filasEm um sistema de
filas, geralmente, tanto o processo de chegada como o de
atendimento no so regulares
12(3+4+3+1+3+2)/12 = 1,33 minutos(3+4+3+1+3+2)/35 = 0,46
cliente
Cliente123456789101112Durao000003403132
-
Sistemas EstveisA abordagem matemtica de filas pela Teoria das
Filas exige que exista estabilidade no fluxo de chegada e no
processo de atendimentoEx: fluxo de chegada de clientes em uma fila
de banco durante o dia
No existe estabilidade para o ritmo de chegada no perodo de
10:00 s 16:00Para analisar utilizando a Teoria das Filas faz-se o
uso do artifcio de retalhar o perodo global em perodos parciais
Perodo10 s12h12 s 14h14 s 16hFluxoMdioAltoMdio
-
Sistemas EstveisOutra exigncia para que o processo seja estvel
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 momentoO atendimento de um
dado cliente pode demorar mais que o normal
Em sistemas estveis, todas as caractersticas randmicas das filas
se mantm estveis, oscilam em torno de um valor mdioSistemas
EstveisFluxo mdio de entrada () constanteRitmo medio de atendimento
() constante >
-
Dimensionando FilasObjetiva prestar um melhor servio aos
clientes ou obter uma reduo de custos do funcionamento do
sistemaTipo de fila e qualidade de servioFila e servidor nicoFila
nica e diversos servidoresDiversas filas com servidores
correspondentesFilas especiaisAlterao dinmica no sistema de
atendimentoA escolha do tipo de fila depende das caractersticas do
sistemaFila de banco x supermercado
-
ExerccioConsidere um sistema em que navios chegam a um porto
para carregar algum produto. Abaixo esto anotados os valores entre
chegadas (em horas) para 20 navios
As duraes da carga (em horas) de cada navio so as seguintes
Calcule:O intervalo mdio entre chegadasA durao mdia da
cargaMonte o desenho de funcionamento do sistema O tamanho mdio da
filaO tempo mdio de espera na fila
Cliente1234567891011121314151617181920Intervalo1021370288810911414110999814
Cliente1234567891011121314151617181920Durao1021370288810911414110999814
-
Caractersticas dos Processos de FilasNa maioria dos casos
podemos descrever um sistema de filas atravs de seu:Padro de
chegada dos clientesPadres de servioDisciplina de filasCapacidade
do sistemaNmero de canais de serviosNmero de estgios de servios
-
Padro de Chegada dos ClientesPadres de chegadas so processos
estocsticos, ou seja desenvolvem-se no tempo e no espao conforme
leis de probabilidadeDistribuies probabilsticasTempos de
interchegadaChegada em batchReaes do clienteClientes decepcionados
Recusa do cliente a entrar na filaClientes impacientesCliente sai
aps algum tempoCliente muda de fila
-
Padro de Chegada dos ClientesO padro de chegada muda com o
tempo?EstacionrioNo-estacionrio
-
Padres de ServioPodem ser simples ou em batchPode depender do
nmero de clientes na filaServio dependente do estadoPode trabalhar
mais rpido ou se atrapalhar com o aumento do nmero de clientesPode
melhorar com o tempoServio no-estacionrioAprendizado como fator de
produtividade
-
Disciplina de FilasDescreve como os clientes so escolhidos para
entrar em um servio aps a fila ser formadaFirst-Come-First-Served
(FCFS)FIFOFilas comuns onde o primeiro a chegar o primeiro a ser
atendidoLast-Come-First-Served(LCFS)LIFOAplicado em sistemas de
controle de estoque e em filas de prioridadesFilas com
PrioridadesPreemptivoO cliente com maior prioridade servido
imediatamenteNo-preemptivoO cliente com maior prioridade entra na
frente da fila, mas deve aguardar se algum cliente j estiver em
atendimento
-
Capacidade do SistemaSistemas 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
-
Nmero de Canais de ServioO nmero de canais correspondem ao nmero
de estaes de servios paralelos que podem servir os clientes
simultaneamenteClientes multi-canais podem ser de:Fila nicaFila
individual
-
Estgio de ServioEstgio nicoO atendimento do cliente acontece de
um vez sBarbearia, supermecado, etcVrios estgiosO cliente passa por
vrios estgios de atendimento, antes de finalizar um servioDurante o
atendimento o cliente pode enfrentar diversas filas com
caractersticas diversasExame fsico, atendimento servio pblico
-
Estgio de Servio
-
Descrio de um Sistema de Filas1.Padro de chegada2.Padro de
servio3.Disciplina de filas4.Capacidade do sistema5. Nmero de
canais de servio...6. Estgios de serviosn
-
Notao de FilaProposta em 1953 por Kendall descrita por um srie
de smbolos, tais como, A/B/m/k/MA a distribuio de inter-chegada de
dos clientesB padro de servio de acordo com um distribuio de
probabilidade para o tempo de serviom o nmero de canais servios
paralelos (servidores)k a capacidade do sistemaM a disciplina de
filasEm muitas situaes s os trs primeiros smbolos so utilizados, de
maneira que, assumido que o sistema tem capacidade ilimitada e
possui uma disciplina FCFS
-
Notao de Fila Tabela A/B/m/k/M
O smbolo G representa uma distribuio de probabilidade geral,
isto , resultados nestes casos so aplicveis para qualquer
distribuio de probabilidade
-
Exemplo:M/D/2//FCFS
Processo de filas com:tempos de inter-chegada exponencialtempos
de servio determinsticodois servidores paraleloscapacidade
ilimitadadisciplina de fila FCFS
-
Medindo o Desempenho do SistemaGeralmente existem 3 tipos de
respostas de interesse do sistema:medida do tempo de espera que um
cliente tpico obrigado a esperarTempo gasto na fila X Tempo total
no sistemaImportncia de cada tipo depende do sistema analisado. Ex:
Parque de diverso x concerto de um equipamentomedida da maneira
como os clientes podem ir se acumulandoNmero de clientes na fila X
nmero de clientes no sistemaAuxilia na definio do espao de espera
dos clientesmedida do tempo ocioso dos servidoresTempo em que um
servidor em particular esta ociosoTempo em que o sistema est
desprovido de clientes
-
Medindo o Desempenho do SistemaA 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 sistemaTempo de espera X custosClculo do tamanho da fila de
esperaUso de mtodos analticos como primeira alternativa e simulaes
onde mtodos analticos no forem suficientes
-
***
