Teoriadasfilas

Prévia do material em texto

Escola de Engenharia de Lorena – EEL/USP
Curso de Engenharia de Produção
Prof. Fabrício Maciel Gomes
Teoria da Filas
Por quê 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
Teoria das Filas
Servidor
Servidor
ServidorPopulação
Fila
Clientes
Atendimento
*Obs:
•Servidores, atendentes ou canais de serviços
•Cliente, transação ou entidade
Elementos de uma Fila
• 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
Elementos de uma Fila
• 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
Processos de Chegada
• 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
Processos de Atendimento
• 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
Número de Servidores
 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
Disciplina 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
Tamanho da 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
Tempo Médio de Espera
• 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%
Variáveis Randômicas
Duração do Atendimento
• 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
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
24 clientes por hora
2,5 minutos
Dinâmica de uma Fila
• Atendimento
• Dados anotados para cada atendimento em minutos
• Determinar
• μ
• TA
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
30 clientes por hora
2 minutos
Dinâmica de uma Fila
• 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
Número de Canais 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ágios de Serviço
Estágios de Serviço
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
Descrição de um Sistema de Filas
• 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 uma Fila
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
Notação de uma Fila
• 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
Notação de uma Fila
• 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
Medidas de Desempenho
• 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
Medidas de Desempenho
SISTEMA
CLIENTE NA FILA
CLIENTE SENDO ATENDIDO
chegada fila atendimento saída
IC TF NF TA NA 
sistema
TS NS
 
Estrutura do Sistema
26
 - taxa de chegada
 - taxa de 
atendimento
chegada fila atendimento saída
IC TF NF c TA NA
sistema
TS NS
IC – tempo médio entre chegadas IC= 
TF - tempo médio na fila
NF – número médio de clientes na fila
TA - tempo médio de atendimento TA=
NA – número médio de clientes em atendimento
TS - tempo médio no sistema
NS – número médio de clientes no sistema
1/ 
1/ 
 
Estrutura do Sistema
Sistema de 1 canal, 1 fila
com população infinita
Pr( )
n
n
  
 
   
    
   
1
Pr( )
r
n r



 
   
 
Probabilidade de haver n clientes no sistema
Probabilidade de que o número de clientes 
no sistema seja superior a um valor r
Sistema de 1 canal, 1 fila
com população infinita
Pr( 0)n
 

 
   
 Pr( 0)n


 
   
 
Probabilidade do sistema estar ocioso
Probabilidade do sistema estar ocupado
Sistema de 1 canal, 1 fila
com população infinita
NS

 

  
2
NF

  

 
Número Médio de Clientes no Sistema
Número Médio de Clientes na Fila
Sistema de 1 canal, 1 fila
com população infinita
( 0)NF Fila

 
 
Número Médio de Clientes na Fila
 
1
TF
  

 
Tempo Médio de Espera na Fila por Clientes
Sistema de 1 canal, 1 fila
com população infinita
 
1
TS
 


Tempo Médio Gasto no Sistema por Clientes
Sistema de 1 canal, 1 fila
com população infinita
Relações Entre TF, TS, NF e NS
TF TF 
1
TF TS

 
   
 
NS TS 
NF NS


 
  
 
Taxa de Serviço para Mínimo Custo Total do Sistema
Unit UnitCT CE CA
     
* Unit
Unit
CE
CA

 

 
CT = Custo total do sistema
CEUnit = Custo de permanência unitário médio por período do cliente 
CAUnit = Custo de atendimento unitário médio por período do cliente 
= Taxa de serviço que resulta no menor custo Total no modelo de 1 fila 
e 1 canal
*
Taxa de Serviço para Mínimo Custo Total do Sistema
Sistema de 1 canal, 1 fila
com população infinita
Sistema de diversos canais, 1 fila
com população infinita    
1
1
1
Pr( 0)
! 1 !
j SS
j
n
j S S
 



 

  

Probabilidade do sistema estar ocioso
Sendo:
S = número de canais de atendimento




 
 .Pr Pr( ) Pr 0
( 1)!
S
Oc Total n S n
S S

      
Probabilidade do todos os canais estiverem ocupados
Sistema de diversos canais, 1 fila
com população infinita
Número Médio de Clientes na Fila
.PrOc TotalNF
S


 

NS NF  Número Médio de Clientes no SistemaSistema de diversos canais, 1 filacom população infinita
1
TF NF

 
Tempo Médio de Espera na Fila por Clientes
1
TS NS

 
Tempo Médio de gasto no Sistema
A cabine telefônica:
 as chegadas ocorrem de acordo com uma distribuição
exponencial com taxa de 0,1 pessoas/min;
 a duração média dos telefonemas é de 3 minutos e também
segue uma distribuição exponencial.
a) Qual a probabilidade de uma pessoa chegar à cabine e não
precisar esperar?
b) Qual o tempo médio na fila?
c) Qual ritmo de chegada de pessoas determinaria um tempo 
médio na fila de 3 minutos?
Exercício 1
Os operários da fábrica, para realizarem as atividades diárias, 
precisam recorrer ao auxílio da ferramentaria. Observou-se 
que o ritmo de chegada de solicitações à ferramentaria segue 
uma distribuição exponencial com ritmo de chegada de =1 
solicitação/min. O ritmo de atendimento da ferramentaria
também segue uma exponencial com =12 atendimentos/min. 
Pergunta-se:
a) Qual a probabilidade de um operário chegar à 
ferramentaria e não precisar esperar?
b) Qual o tempo médio de espera do operário na fila?
c) Qual o tempo médio de atendimento do operário?
d) Qual o tempo médio do operário na ferramentaria?
e) Quantos operários em média estão na fila?
f) Quantos operários em média estão na ferramentaria?
Exercício 2
Um lava rápido automático funciona com somente uma baia. Os carros chegam 
conforme uma distribuição de Poisson com um tempo médio de 8 minutos e 
podem esperar num estacionamento com cinco vagas disponíveis. Se o 
estacionamento estiver cheio os clientes que chegam desistem e procuram outro 
lava rápido. O tempo para lavar e limpar um carro segue uma distribuição 
exponencial, com uma média de sete minutos e 30 segundos. O proprietário quer 
determinar o impacto das vagas limitadas sobre a perda de clientes para a 
concorrência. Considerando essa situação, determine: 
a) A probabilidade de que um carro que chega passe imediatamente à baia de 
lavagem. 
b) Tempo de espera estimado até o início do serviço. 
c) Número esperado de vagas vazias no estacionamento. 
d) A probabilidade de todas as vagas estarem ocupadas. 
e) A taxa de utilização do servidor. 
Exercício 3