Filas de Espera (Teoria das Filas)

Filas de Espera (Teoria das Filas)

Modelos de filas de espera para melhoria de serviços

Prof. Dr. Marcio Mattos Borges de Oliveira FEARP-USP

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Pedidos por telefone na L.L. Bean

Nos EUA vendas por catálogos: 13,6 bilhõesde catálogos de 10 mil empresas

Operações de telemarketing curto prazo: escala de serviço e capacidade de atendimento médio prazo: número de pessoas a contratar e treinar

Problema nas 3 semanas que antecedem o Natal (20% da venda anual)

1988 vendas de US$580 milhões

Perdas estimadas em US$10 milhões

80% das chamadas com sinal de ocupado. Nos demais, espera de 10 minutos pelo atendente

Estudo de filas para determinar as características do sistema atendentes: 500 --> 1275 linhas tronco: 150 --> 576 atendimento: Ç24% pedidos: Ç16,7% renda: Ç16,3 % (US$15 milhões) tempo de resposta: 93’-->15’ Lucro: ÇUS$ 10 milhões Custo: ÈUS$1,6 milhões Melhorou a imagem Projeto custou US$40 mil!

Elementos da análise de filas de espera

Fila uma simples fila de espera

Sistema de fila de espera chegadas servidores estruturas de fila de espera

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Determinando a população

–fonte de usuários

–uma população infinitapressupõe ser tão grande que sempre haverá possibilidade de um ou mais usuários chegarem para serem atendidos

–uma população finitaconsiste de um número contável de usuários potenciais

–freqüência de usuários chegando no sistema –tipicamente segue uma distribuição dePoisson

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Tempo de serviço

–freqüentemente segue uma distribuição exponencial negativa

A taxa de chegada deve ser menor que a taxa de serviço, caso contrário o sistema entrará em colapso

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Componentes de um sistema de filas

Fonte de usuários

ServidorUsuários atendidos chegadas Linha de espera ou fila

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Disciplina e comprimento da fila

Disciplina da fila

–ordem em que os usuários são atendidos

–FIFO (firstin, firstout), primeiro a entrar, primeiro a sair é o mais comum

Comprimento pode ser infinito ou finito

–infinito é o mais comum –finito é limitado por alguma estrutura física

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Estruturas básicas de filas

Canaissão o número de servidores paralelos

Fasesdenotam o número de servidores seqüenciais nos quais o usuário deverá passar

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

filaservidor

Estruturas de canais únicos Canal único, fase única servidores fila

Canal único, múltiplas fases

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Estruturas de canais múltiplos Múltiplos canais, fase única fila servidores

Múltiplos canais, múltiplas fases fila servidores

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Características de Operação

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

A teoria matemática das filas não fornece soluções melhores ou ótimas

Ao invés disso, características de operação são descritas para análise da performance do sistema

Em situação de continuidade se obtém o valor médio das características de performance que o sistema alcançará depois de um período longo de tempo

Características de operação

Notação Descrição

Lnúmero médio de usuários no sistema (esperando e sendo atendidos)

L q número médio de usuários na fila

Wtempo médio gasto pelo usuário no sistema (esperando e sendo atendido)

W q tempo médio gasto pelo usuário na fila

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Pn Probabilidade de n usuários no sistema ρTaxa de utilização, proporção do tempo em que o sistema é usado

Notação Descrição

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Relação de custo na análise de filas

Custo total

Nível de serviço

Custo de serviço

Custo de espera

Análise de filas e qualidade

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e coincidir com o ponto mínimo da curva de custo total

Visão de TQM -no final das contas, o serviço sem qualidade absoluta é o maior custo efetivo

Modelos de Canal único, Fase única

Sempre assumindo taxa de chegada segundo Poisson

–tempo de serviço exponencial

–distribuição geral (ou desconhecida ) de tempo de serviço

–tempo de serviço constante

–tempo de serviço exponencial com comprimento de fila finito

–tempo de serviço exponencial com população de usuários finita

Modelo básico de servidor único

–taxa de chegada Poisson –tempo de serviço exponencial

–disciplina da fila: primeiro a chegar, primeiro a sair

–fila de comprimento infinito

–população de usuários infinita

λ= taxa média de chegada

Fórmulas do modelo de servidor único

(1 - )

Probabilidade de zero usuários no sistema

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

(1 - )

( Probabilidade de exatamente n usuários no sistema

L= Número médio de usuários no sistema µ(µ −λ) Número médio de usuários na fila

Tempo médio gasto pelo usuário no sistema

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e µ(µ −λ) Tempo médio gasto pelo usuário na fila µ Probabilidade de que o servidor esteja ocupado, fator de utilização

= P 0

(1 - )

= 1 −ρ

Probabilidade de servidor vazio e que o usuário possa ser atendido

Exemplo de servidor único

Dado: λ= 24 por hora, µ= 30 usuários por hora

(1 - )

Probabilidade de zero usuários no sistema

1 -(24/30) = 0,20 µ −λ Número médio de usuários no sistema

= 24/(30-24) = 4

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e µ(µ −λ) Número médio de usuários na fila

= 24 2 /30(30-24) = 3,2

Tempo médio que o usuário gasta no sistema

W = = 1(30-24) = 0,167 hora = 10 min

Tempo médio que o usuário gasta na fila µ(µ −λ) = 24/30(30-24) = 0,133 hora = 8 min

1 −ρ I =

Probabilidade que o servidor esteja vazio e o usuário possa ser atendido

= 1 -0,80 = 0,20 ρ = Probabilidade que o servidor esteja ocupado, fator de utilização

= 24/30 = 0,80

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Análise de custo das filas

O Administrador deseja testar duas alternativas para reduzir o tempo de espera do usuário:

1,Contratar outro empregado para empacotar compras

2, Abrir outro caixa, balcão de atendimento

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Alternativa 1

O empregado extra custa $150 / semana

Cada um minuto de redução no tempo de espera do usuário evita perda de $75 / semana, em vendas

O empregado extra irá aumentar a taxa de serviço para 40 usuários por hora

Recalcule as características operacionais do sistema

Wq = 0,038 horas = 2,25 minutos, originalmente era de 8 minutos

8,0 -2,25 = 5,75 minutos

5,75 x $75/minuto/semana = $431,25 por semana

O novo empregado economiza $431,25 -150,0 = $281,25 / semana

Alternativa I

Novo balcão custa $6000 mais $200 por semana para o caixa

Os usuários se dividem automaticamente pelos dois caixas

A taxa de chegada se reduz de λ = 24 para λ = 12

A taxa de serviço para cada caixa permanece µ= 30 Recalcule as características de operação do sistema

Wq = 0,022 horas = 1,3 minutos, originalmente era de 8 minutos

8,0 -1,3 = 6,67 minutos

6,67 x $75/minuto/semana = $50,0/semana -20,0 = $300/semana

O novo balcão será pago em 6000/300 = 20 semanas

O Balcão economiza $300/semana;

Se puder investir, escolha alternativa I

Tempo de serviço constante

Tempo de serviço constante ocorre com máquinas e equipamentos automáticos

Tempo de serviço constante é um caso especial do modelo de servidor único com tempo de serviço geral ou indefinido

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Características de operação para tempo de serviço constante

(1 -

Probabilidade que não haja usuários no sistema Com relação ao tempo de serviço:

µé o tempo médio de atendimento σ é o desvio padrão

Se o tempo de serviço for constante, então σ=0

Com relação ao tempo de serviço:

µé o tempo médio de atendimento σ é o desvio padrão

Se o tempo de serviço for constante, então σ=0

2 ( 1 −λ / µ )

Número médio de usuários na fila

L= Lq +

Número médio de usuários no sistema

Tempo médio gasto pelo usuário na fila

L q

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Tempo médio que o usuário gasta no sistema λ Probabilidade que o servidor esteja ocupado, fator de utilização λ 2 σ2+ (λ / µ) 2λ2 0 + (λ / µ) 2

Quando o tempo de serviço é constante, as fórmulas podem ser simplificadas

L q

2 ( 1 −λ / µ )2 ( 1 −λ / µ )

2 ( 1 −λ / µ )2 µ(µ −λ)

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Exemplo de tempo de serviço constante

Lavagem automática de carros com tempo de serviço = 4,5 min

Taxa de chegada de carros λ= 10/hora (Poisson) µ= 60/4,5 = 13,3/hora

2(13,3)(13,3-10) = 1,14 carros esperando

L q λ =1,14/10 =0 .114 hora ou 6,84 minutos

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Fila com comprimento finito

Existe um limite físico para o comprimento da fila M = máximo número de usuários no sistema

Taxa de serviço não pode ser menor que a taxa de chegada para permitir condições de estabilidade (µ > λ)

1 −λ / µ

1 −λ / µ n for n ≤ M

(M + 1)(λ / µ) M + 1

1 -(λ / µ) M+1

Probabilidade de zero usuários no sistema

Probabilidade de exatamente n usuários no sistema

Número médio de usuários no sistema

Seja PM = probabilidade de um usuário não entrar no sistema

Número médio de usuários na fila

Lq = L λ (1 -PM )

Tempo médio que o usuário gasta no sistema

Tempo médio que um usuário gasta na fila

WWq =

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Exemplo de fila finita

Quick Lube (troca rápida de óleo) tem espaço de espera para somente 3 carros λ= 20, µ= 30, M = 4 carros (1 em serviço + 3 esperando)

Probabilidade de zero carros no sistema

1 −λ / µ

= = 0,38

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Probabilidade de exatamente n carros no sistema

P m n=M

30 = 0,076

Número médio de carros no sistema

1 −λ / µ

(M + 1)(λ / µ) M + 1

1 -(λ / µ) M+1

= 1,24

= 1,24 - = 0,62

Número médio de carros na fila λ(1 -P M )

20 (1-0,076) = 0,67 horas

= 4,03 min

Tempo médio gasto por um carro no sistema

0,067 - = 0,033 horas

= 2,03 min

Tempo médio gasto por um carro na fila

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

População de usuários finita

As chegadas se originam de uma população finita (contável)

N = tamanho da população

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Pn = P n N!

Onde n = 1, 2,, N

Probabilidade de zero usuários no sistema

Probabilidade de exatamente n usuários no sistema

Número médio de usuários na fila

(λ / µ) n

(N -n)! Σ n = 0

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

W= Wq +

L q

L q

Tempo médio que o usuário gasta no sistema

Tempo médio que o usuário gasta na fila

Número médio de usuários no sistema

Exemplo de população finita

20 máquinas com média de operação de 200 horas antes de quebrar: λ= 1/200 hora = 0,005/hora

‰Tempo médio de manutenção = 3,6 horas:

µ= 1/3,6 hora = 0,2778/hora

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e n = 0

Probabilidade de zero máquinas no sistema

(λ / µ) n

(N -n)! Σ n = 0 1

(20 -n)! Σ

= 0,652 λ +µ Número médio de máquinas na fila

Lq = N

0,005 + 0,2778

Número médio de máquinas no sistema

L =L q+ (1-P0 ) = 0,169 + (1-0,62) = 0,520 q Tempo médio gasto pela máquina na fila

W q

(N -L) λ (20 -0,520) 0,005

Tempo médio que a máquina gasta no sistema

= 1,74 +

+ = 5,3 horas

Modelos de canais múltiplos, fase única

Dois ou mais servidores (s) servem uma única fila

Chegadas segundo Poisson, serviço exponencial, população de usuários

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e n = 0 ] + n! 1 s! s sµ

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

P n =P n Probabilidade de existirem exatamente n usuários no sistema for n > s s! s n-s for n <= s n!

Probabilidade de que um usuário chegando no sistema tenha que esperar sµ-λ s!

Número médio de usuários no sistema

Tempo médio gasto pelo usuário no sistema λ Número médio de usuários na fila

L q = L

1 Tempo médio que o usuário gasta na fila

W q = W

Fator de utilização λ /sµρ=

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Exemplo de múltiplos servidores

Área de atendimento ao usuário λ= 10 usuários / hora µ= 4 usuários / hora por atendente sµ= (3)(4) = 12

3 atendentes

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e n = 0 ] + n! 1 s! s sµ

= 0,045

Número médio de usuários no sistema L=

(10)(4) (10/4) 3

(3-1)! [3(4)-10] 2

(0,045) + (10/4) = 6

Tempo médio de gasto por um usuário no sistema λ = 6/10 = 0,60 hr= 36 min

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

λ Número médio de usuários na fila

L q

= 3,5/10 = 0,35 hrs= 21 min

L q

Tempo médio gasto por um usuário na fila

() s! sµ-λ

Probabilidade de que um usuário que chegue no sistema tenha que esperar

(0,45) = 0,703

© 1998by Prentice-HallInc Russel l/T aylor Oper Mgt 2/e

Melhorando o serviço

Colocar um quarto atendente para melhorar o serviço

Recalcule as características da operação

Po = 0,073 probabilidade de zero usuários

L = 3,0 usuários

W = 0,30 horas, 18 min no serviço

L q = 0,5 usuários esperando

W q = 0,05 horas, 3 min esperando, contra 21 anteriores

P w = 0,31 probabilidade de que o usuário tenha que esperar

Competindo com cadeia de serviço local

A maior cadeia de comércio de títulos no varejo dos EUA.

Mais de 450 escritórios e 10,0 corretores

Informações disponíveis por redes de computadores

Desejo aumentar a rapidez das atualizações nos horários de negócios

Estudo via filas permitiu determinar que as consultas (Poisson) poderiam ser atendidas por dois servidores.

Isto permitiu o estudo de viabilidade financeira e a implantação do projeto

Programaçãode turnosde trabalho

Demanda diáriade serviços: fixa (polícia, hospitais) ou variável (telefonistas)

A alocação de turnos deve contemplar a demanda dentro de um nível de serviço pré-estabelecido

Restrições: diasde folga e pagamento de horas extras

Programaçãode turnosde trabalho -exemplo

Problema de Programação linear inteira

Primeirose determina o número de funcionários desejado em cada dia da semana (teoria das filas)

Cada turno consiste de 5 dias de trabalho e dois de folga

São possiveis 7 turnos (turno 1 folga domingo e segunda)

Programaçãode turnosde trabalho - exemplo

Xi = número de empregados alocados no turno i e que folga 2 dias consecutivos a partir do dia i b j = número de empregados desejados no dia j inteiro e0

x xSábado x xSexta x xQuinta x xQuarta x xTerça x xSegunda

x xDomingo Restrições xxxxxxMin x objetivo Função i x b b

Programação de turnosde trabalho - formulação

Programaçãode turnosde trabalho – dados

Sala de emergência hospitalar: 24 horas/dia Enfermeiras necessárias durante os turnos diários

5556563Enfermeiras SabSexQuiQuaTerSegDomDia

Programaçãode turnosde trabalho - resultados

O problema possui várias soluções:

A) x 1=1, x2=1, x3=2, x4=0, x5=3, x6=0, x7 =1 mostrada a seguir

Comentários