Teoria das Filas e Simulação

Prévia do material em texto

Universidade Federal de Mato Grosso - Campus Universitário do Araguaia
Instituto de Ciências Exatas e da Terra
Teoria das Filas e Simulação
Bacharelado em Ciência da Computação
Prof. Ivairton M. Santos http://comp.cua.ufmt.br/ ivairton/
March 22, 2017
1
Índice
Introdução
Modelagem de Sistemas
Aplicações
Filas
Propriedades
Variáveis randômicas fundamentais
Processos de chegada e de atendimento
Apêndice - Tabelas de referências
Modelos de filas
Modelo M/M/1
Modelo M/M/1/K
Modelo M/M/c
Modelo Erlang
Simulação
Método de Monte Carlo
Ivairton | Teoria das Filas e Simulação
2
Introdução
I A Teoria das Filas e a Teoria da Simulação são técnicas de
planejamento.
I Constituem da base teórica de programas de computador
relacionados com simulação.
I Envolve matemática, modelagem e algoritmos.
Ivairton | Teoria das Filas e Simulação
3
Modelagem de Sistemas
I Sistemas balanceados
Qual é a quantidade correta de equipamentos (sejam eles máquinas,
veículos, pessoas, etc)? Ou, qual é o melhor layout e o melhor fluxo
dentro do sistema?
I O que são filas?
As filas são antipáticas e dispendiosas.
I Uma modelagem de sistema pode ser feita por duas
abordagens:
I Teoria das filas
I Simulação
Ivairton | Teoria das Filas e Simulação
4
Modelagem de Sistemas
Aplicações
I Linhas de produção
I Transportes
I Comunicações
I Bancos, supermercados, escritóriose, etc.
Ivairton | Teoria das Filas e Simulação
5
Filas
Elementos
I Em uma típica fila temos:
I População
I Clientes
I Fila
I Serviço
Ivairton | Teoria das Filas e Simulação
6
Filas
Características
I Características de uma fila
I Clientes e tamanho da população
I Processo de chegada (distribuição de frequência, tal como
distribuição normal, de Poisson e exponencial)
Ritmo de chegada = λ | Ex: λ = 20 clientes/minuto
Intervalo de Chegadas = IC | Ex: IC = 3 segundos
I Processo de atendimento
Ritmo de atendimento = µ | Ex: µ = 6 clientes/minuto
Tempo de Duração = TA | Ex: TA = 10 segundos/cliente
I Número de servidores
I Disciplina da fila (FIFO, LIFO, prioridade, randômico)
I Tamanho médio da fila
I Tamanho máximo da fila
I Tempo médio de espera
Ivairton | Teoria das Filas e Simulação
7
Filas
Características
I Variáveis randômicas
I Diretamente ligadas às filas
I Para as principais variáveis existe um valor médio
I E uma distribuição de probabilidades
I Sistemas estáveis
I A abordagem matemática de filas exige que λ e µ sejam estaveis
(constantes)
I Por mais que possam ocorrer sistuações adversas, em sistemas
estáveis todas as características randômicas das filas se mantêm
estáveis
I Tamanho da amostra
É importante escolher um tamanho correto para a amostra.
Ivairton | Teoria das Filas e Simulação
8
Filas
Características
I Dimensionamento: tipo da fila
I Uma única fila e um único servidor
I Uma única fila e diversos servidores
I Diversas filas e diversos servidores
I Filas especiais
I Alteração dinâmica no sistema de atendimento
Ivairton | Teoria das Filas e Simulação
9
Filas
Exercício
I Exercício 1 - Considere um sistema em que navios chegam a
um porto para carregar algum produto. Abaixo estão anotados
os valores de intervalos entre chegadas (em horas) para 10
navios:
Cliente: 01 02 03 04 05 06 07 08 09 10
Intervalo: 10 02 13 07 02 08 08 08 10 09
A duração do processo de carga (em horas) para cada navio é:
Cliente: 01 02 03 04 05 06 07 08 09 10
Duração: 05 05 03 03 06 07 06 08 02 05
Pede-se:
1. O intervalo médio entre chegadas
2. A duração média do carregamento
3. Tente desenhar um esquema de funcionamento da fila
4. Calcule o tamanho médio da fila
5. Calcule o tempo médio de espera na fila
Ivairton | Teoria das Filas e Simulação
10
Filas
Variáveis randômicas fundamentais
I Variáveis referentes ao sistema
I TS = Tempo médio de permanência no sistema
I NS = Número médio e clientes no sistema
I Variáveis referentes ao processo de chegada
I λ = ritmo médio de chegada
I IC = Intervalo médio entre chegadas
Por definição: IC = 1
λ
I Variáveis referentes à fila
I TF = Tempo médio de permanência na fila
I NF = Número médio de clientes na fila
I Variáveis referentes ao processo de atendimento
I TA = Tempo médio de atendimento ou de serviço
I M = Quantidade de atendentes
I NA = Número médio de clientes em atendimento
I µ = Ritmo médio de atendimento de cada atendente
Por definição: TA = 1
µ
Ivairton | Teoria das Filas e Simulação
11
Filas
Variáveis randômicas fundamentais
Ivairton | Teoria das Filas e Simulação
12
Filas
Variáveis randômicas fundamentais
I Relações básicas:
NS = NF + NA
TS = TF + TA
I Pode-se demosntrar que: NA = λµ =
TA
IC . Portanto:
NS = NF + NA = NF + λµ = NF +
TA
IC
I Taxa de utilização dos atendentes
I Para o caso de uma fila/um atendente:
ρ = λ
µ
I Para uma fila/vários atendentes:
ρ = λMµ
I Número mínimo de atendentes
i = |λµ | = |
TA
IC |
I Formulas de Litter:
NF = λ.TF
NS = λ.TS
Ivairton | Teoria das Filas e Simulação
13
Filas
Exemplos
I Exemplo 1: Em uma fábrica observou-se o funcionamento de
um dado setor, em que λ = 20 clientes/hora, µ = 25
clientes/hora e TS = 0,3 hora. Pede-se o tamanho médio da fila.
Solução:
TA = 1µ = 0,04
TF = TS - TA = 0,26
NF = λ.TF = 5,2 clientes
I Exemplo 2: Para o mesmo sistema anterior, calcular NS e NA.
Solução:
NS = λ.TS = 20 × 0,3 = 6 clientes
NA = NS - NF = 6 - 5,2 = 0,8 clientes
I Exemplo 3: Em uma mineração verificou-se que o tempo médio
(TS) dos caminhões junto às carregadeiras é de 3 minutos e
que, em média, existem 6 caminhões (NS) no setor. Qual a taxa
de chegada de caminhões?
Solução:
Pela lei de Little: NS = λ.TS ou λ = NS/TS
Logo: λ = 6/3 = 2 chegadas/minuto
Ivairton | Teoria das Filas e Simulação
14
Filas
Exemplos
I Exemplo 4: No mesmo sistema anterior, exisstindo um total de
30 caminhões em serviço, qual a duração de um ciclo?
Solução:
Chamamos de ciclo o tempo gasto para que todos os caminhões
"passem" pela carregadeira uma vez. Ao final de um ciclo o
sistema terá atendido uma vez a cada um dos 30 camnhiões.
Duração do ciclo = (Quantidade de caminhões) / λ
Duração do ciclo = 30 / λ = 30/2 = 15 minutos
I Exemplo 5: No mesmo sistema dos 2 exercícios anteriores, qual
o tempo médio para o processo completo de descarregamento
(ou TFS: Tempo Fora do Sistema)?
Solução:
Um ciclo corresponde à soma do tempo dentro do sistema
(TS=3) com o tempo de descarregamento (TFS). Logo:
TFS + TS = 15
TFS = 15 - 3 = 12
Ivairton | Teoria das Filas e Simulação
15
Filas
Postulados básicos
I Postulados básicos:
a) Em qualquer sistema estável, o fluxo que entra é igual ao fluxo que
sai
b) Em um sistema estável, o fluxo de etrada se mantém nas diversas
seções do sistema
c) Em um sistema estável, a junção de fluxos equivale às suas somas
d) Em um sistema estável, o fluxo de desdobra aritmeticamente
Ivairton | Teoria das Filas e Simulação
16
Filas
Exercícios
I Exercício 1: Em uma pizzaria que faz entregas em casa,
chegam em média 4 entregadores/minuto para pegar o produto
a ser entregue. Sabe-se ainda que o número médio de
enetregadores dentro da pizzaria é de 6 (NS). Qual o tempo
médio no sistema?
I Exercício 2: No mesmo sistema anterior, existem 40
entregadores. Qual o tempo médio da entrega (TFS)?
I Exercício 3: Em um sistema de computação tem-se:
I Tempo médio de pensar e fornecer dados (TFS) = 15 minutos
I Quantidade de terminais ativos = 40
I Taxa de chegada de transnsações = 2/segundo
Pede-se o tempo de resposta do computador (TS).
Ivairton | Teoria das Filas e Simulação
17
Filas
Exercícios
I Exercício 4: Em uma mineração temos 12 caminhões efetuando
um ciclo no qual consomem 4 minutos entre fila e carregamento
pela escavadeira (TS) e, a seguir, gastam 8 minutos para levar a
carga até o britador e voltar (TFS). Calcular λ e NS.
I Exercício 5:Em um sistema de computação temos 21 terminais.
O tempo médio de resposta do computador (TS) é de 2
segundos e existem, em média, 6 transações (NS) dentro do
sistema. Pede-se:
a) Qual a taxa de chegada de transações?
b) Qual a duração de um ciclo?
c) Qualo tempo médio de pensar e fornecer os dados (TFS)?
I Exercício 6: A representação de fluxo dada abaixo corresponde
ao fluxo de peças em um setor de uma fábrica, calcule o fluxo de
chegda em cada equipamento:
Em A: λ = 10; Em B: λ = 20
De A para C, valor de C?
De B para D e de C para D, valor de D?
De D para E, com taxa de 30%, valor de E?
De D para F, com taxa de 70%, valor de F?
Ivairton | Teoria das Filas e Simulação
18
Filas
Processos de chegada e de atendimento
I Considere um processo de chegada de uma forma quantitativa.
I Por exemplo, a tabela abaixo descreve a chegada de veículos a
um pedágio a cada intervalo de 1 minuto, no período de 1 hora.
I Nas 60 anotações, chegaram 120 veículos, com λ = 2
veículos/minuto.
I O menor valor (0) ocorreu 9 vezes.
I O maior valor (8) ocorreu 1 vez.
Ivairton | Teoria das Filas e Simulação
19
Filas
Processos de chegada e de atendimento
I Uma análise adequada desses dados deve-se valer da
estatística.
I O principal objetivo é saber como os valores se distribuem em
torno da média.
I Ao agrupar os dados temos:
I O gráfico abaixo mostra a curva para o ritmo de chegada x
frequência relativa:
Ivairton | Teoria das Filas e Simulação
20
Filas
Processos de chegada e de atendimento
Qual é a distribuição estatística que mais se aproxima dos dados
reais apresentados?
I Uma metodologia é usar como critério o teste baseado em x2.
I Para o caso, a distribuição que mais se aproxima é a de
Poisson.
Ivairton | Teoria das Filas e Simulação
21
Filas
Processos de chegada e de atendimento
Distribuição de Poisson:
f (x) = λ
x e−λ
x!
I A distribuição de Poisson tem se mostrado aplicável a inúmeros
tipos de processos de chegadas práticos.
Ivairton | Teoria das Filas e Simulação
22
Filas
Processos de chegada e de atendimento
I Exemplo: Em uma fábrica chegam em média 7 pedidos/semana
(segundo uma distribuição de Poisson). Qual a probabilidade de
ocorrer a chegada das quantidades de pedidos abaixo em uma
mesma semana?
(a) zero pedidos
(b) 7 pedidos
(c) até 7 pedidos
(d) Acima de 7 pedidos
Solução:
(a) f (0) = 0, 001
(b) f (7) = 0, 149
(c) f (0) + f (1) + f (2) + f (3) + f (4) + f (5) + f (6) + f (7) = 0, 598
(d) 1 − (f (0) + f (1) + ...+ f (7)) = 1 − 0, 598 = 0, 402
Ivairton | Teoria das Filas e Simulação
23
Filas
Processos de chegada e de atendimento
I A distribuição de Poisson está relacionada com ritmos.
Distribuição Exponencial Negativa
Pode-se demonstrar que a distribuição Exponencial Negativa é a
correspondente da distribuição de Poisson quando nos referimos a
intervalos entre chegadas.
I Considerando ainda o exemplo do pedágio, podemos
reescrevê-lo considerando os intervalos entre chegadas de
veículos, conforme tabela abaixo:
Ivairton | Teoria das Filas e Simulação
24
Filas
Processos de chegada e de atendimento
I Considere uma abordagem estatística por faixa de intervalos
entre chegadas:
Ivairton | Teoria das Filas e Simulação
25
Filas
Processos de chegada e de atendimento
Distribuição Exponencial Negativa
f (x) = λe−λx
onde, f (x) é a função densidade, sendo λ o ritmo de chegada e x o
tempo.
I Para calcularmos a frequência relativa de ocorrência de
chegadas no intervalo t e t + ∆t , devemos calcular a integral no
mesmo intervalo (de x = 0 até x = x)
F (x) = 1− e−λx
Ivairton | Teoria das Filas e Simulação
26
Filas
Processos de chegada e de atendimento
I O valor da integral de F (x) no intervalo (t , t + ∆t) é
F (t + ∆t)− F (t) e representa também a probabilidade de
ocorrência do fenômeno no intervalo (t , t + ∆t)
Ivairton | Teoria das Filas e Simulação
27
Filas
Processos de chegada e de atendimento
I Exemplo: Considerando o problema o pedágio, para o qual
λ = 2 chegadas/minuto (ou 0,033 chegadas/segundo), ou IC =
30 segundos:
(a) Cálculo da probabilidade de que o intervalo entre duas chegadas
seja de até 30 sgundos (0,5 min):
Solução: F (0, 5) = 0, 632 ou 63,2%
(b) Cálculo da probabilidade de que o intervalo entre duas chegdas
seja maior que 30 segundos:
Solução: 1 − F (0, 5) = 1 − 0, 632 = 0, 368 ou 36,8%
(c) Cálculo da probabilidade de que o intervalo entre duas chegdas
esteja compreendido entre 12 e 24 segundos (0,2 e 0,4 minutos):
Solução: F (0, 4)− F (0, 2) = 0, 551 − 0, 330 = 0, 221 ou 22,1
Ivairton | Teoria das Filas e Simulação
28
Filas
Exercícios
I Exercício 1: Um profissional foi solicitado para efetuar um
estudo em uma firma distribuidora de gasolina. Esta firma
possui um pátio com uma bomba, onde os caminhões são
carregados com gasolina. Com o aumento das vendas, tem
acontecido frequentemente a lotação do pátio por caminhões,
além de atrapalhar o trânsito local. Assim, a missão do
profissional é redimensionar o pátio no que se refere ao número
ótimo de postos de atendimento. Inicialmente, ele estudou o
ritmo de chegada, fazendo uma coleta de dados, conforme
tabela abaixo, que relaciona a quantidade de veículos que
chegou ao pátio em cada um dos 80 intervalos de 1 hora.
Pede-se: verificar graficamente se o ritmo de chegadas se
aproxima da distribuição de Poisson.
Ivairton | Teoria das Filas e Simulação
29
Filas
Exercícios
I Exercício 2: Em uma fábrica as máquinas estragam a um ritmo
de 4 falhas/semana, segundo uma distribuição de Poisson.
Quando uma máquina falha, é enviada uma solicitação de
conserto ao departamento responsável pela manutenção. Qual
a probabilidade de, em uma dada semana, chegarem as
seguintes quantidades de solicitações de conserto:
(a) zero
(b) 1 falha
(c) até 4 falhas
(d) mais que 4 falhas
(e) 12 falhas
I Exercício 3: Em um dado sistema o intervalo médio entre duas
chegadas é IC = 10 minutos (λ = 6 chegadas/hora, Dist. Exp.
Negativa). Pede-se a probabilidade de que o intervalo entre
duas chegadas seja:
(a) até 6 minutos
(b) maior que 6 minutos
(c) entre 6 e 30 minutos
(d) maior que 30 minutos
Ivairton | Teoria das Filas e Simulação
30
Filas
O processo de atendimento
I Ainda considerando o problema do pedágio, mas agora com
atenção ao atendente, considere a tabela abaixo que mostra 100
valores referentes a duração de cada atendimento:
Temos:
TA = 20 segundos/cliente (TA = 0,33 minutos/cliente)
Ou seja: µ = 3 clientes/minuto
I Para análise desses dados é necessário agrupá-los em
intervalos.
Ivairton | Teoria das Filas e Simulação
31
Filas
O processo de atendimento
I Verificando se os valores da frequência relativa seguem a
distribuição exponencial, tem-se:
I Nota-se que existe uma grande diferença entre as curvas.
Ivairton | Teoria das Filas e Simulação
32
Filas
O processo de atendimento
I Observa-se que a distribuição Exponencial prevê uma alta
probabilidade para o atendimento nos primeiros momentos, o
que é absurdo.
A distribuição Exponencial geralmente não se adapta ao processo de
atendimento.
I Um dos poucos (raros) casos em que a distribuição Exponencial
Negativa se adapta ao atendimento é o caso da duração de uma
ligação telefônica.
I Para este processo não existe uma única distribuição que
melhor se adapte.
I As candidatas com boas possibilidades são:
I Hiper-exponencial de grau m
I Erlang de grau m
Ivairton | Teoria das Filas e Simulação
33
Filas
O processo de atendimento
I Exemplo: A duração média de um telefonema é de 6 minutos e
segue a distribuição Exponencial Negativa. Qual a probabilidade
de que a duração seja:
(a) até 6 minutos
(b) acima de 6 minutos
(c) até 1 minuto
(d) entre 1 e 6 minutos
(e) acima de 30 minutos
Solução: (vide valores da distribuição exponencial acumuada)
Visto que TA = 6 minutos, pode-se considerar µ = 10
ligações/hora.
(a) F (0, 1) = 0, 632 ou 63,2%
(b) 1 − F (0, 1) = 1 − 0, 632 = 0, 368 ou 36,8%
(c) F (0, 011) = 0, 153 ou 15,3%
(d) F (0, 1)− F (0, 011) = 0, 632 − 0, 153 = 0, 479 ou 47,9
(e) 1 − F (0, 5) = 1 − 0, 993 = 0, 007 ou 0,7%
Ivairton | Teoria das Filas e Simulação
34
Filas
Exercícios
I Exercício 4: O mesmo profissional do Exercício 1 estudou o
processo de atendimento no pátio. Os dados da tabela abaixo
mostram a duração de cada atendimento em minutos:
Pede-se: verifique graficamentese a duração do atendimento
segue a distribuição Exponencial Negativa.
Ivairton | Teoria das Filas e Simulação
35
Filas
Exercícios
I Exercício 5: A duração média de carga de um caminhão em
uma empresa de atacado é de 20 minutos (µ = 3
atendimentos/hora). Considere que o proceso siga a distribuição
Exponencial Negativa e calcule a probabilidade de que o tempo
de carga seja de:
(a) até 10 minutos
(b) entre 10 e 20 minutos
(c) entre 20 e 30 minutos
(d) entre 30 e 40 minutos
Conforme visto, é pouco provavel que o processo de carregamento
de um caminhão obedeça a distribuição Exponencial. Faça
comentários qualitativos sobre quais valores seriam mais prováveis
para as respostas dos itens anteriores.
Ivairton | Teoria das Filas e Simulação
36
Filas
Apêndice - Tabelas
Ivairton | Teoria das Filas e Simulação
37
Filas
Apêndice - Tabelas
Ivairton | Teoria das Filas e Simulação
38
Filas
Apêndice - Tabelas
Ivairton | Teoria das Filas e Simulação
39
Filas
Apêndice - Tabelas
Ivairton | Teoria das Filas e Simulação
40
Filas
Apêndice - Tabelas
Ivairton | Teoria das Filas e Simulação
41
Modelo M/M/1
I O modelo de fila M/M/1 é aquele em que tanto as chegadas
quanto o atendimento são marcovianos e temos um único
atendente.
I Pode-se ter uma população infinita ou finita.
Ivairton | Teoria das Filas e Simulação
42
Modelo M/M/1
População infinita
I São as seguintes fórmulas que tram as principais variáveis
randômicas:
Nome Descrição Fórmula
NF Número médio de clientes na fila NF = λ
2
µ(µ−λ)
NS Número médio de clientes no sistema NS = λµ−λ
TF Tempo médio que o cliente fica na fila TF = λµ(µ−λ
TS Tempo médio que o cliente fica no sistema TS = 1µ−λ
Pn Probabilidade de existirem n clientes no sistema Pn = (1− λµ )
λ
µ )
n
Ivairton | Teoria das Filas e Simulação
43
Modelo M/M/1
Taxa de utilização
I Chamamos de taxa de utilização a relação entre o ritmo médio
de chegada e o ritmo médio de atendimento:
ρ = λµ
I Sistemas estáveis exigem λ menor que µ, ou ρ < 1.
Ivairton | Teoria das Filas e Simulação
44
Modelo M/M/1
Exemplo
I Exemplo 1: a cabine telefônica - Suponha que as chegdas a
uma cabine telefônica obedecem a lei de Poisson, com ritmo de
6 chegadas/hora. A duração média do telefonema é de 3
minutos e suponha que siga a distribuição exponencial. Pede-se
a) Qual a probabilidade de uma pessoa chegar à cabine e não ter
que esperar?
b) Qual o número médio de pessoas na fila?
c) Qual o número médio de pessoas no sistema?
d) Qual o número médio de clientes usando o telefone?
e) Qual o tempo na fila?
f) Para qual ritmo de chegada teríamos a situaçãm em que o tempo
médio de espra na fila seria de 3 minutos?
g) Qual é a fração do dia durante a qual o telefone está em uso?
Ivairton | Teoria das Filas e Simulação
45
Modelo M/M/1
Exemplo
Solução: Pelos dados temos: λ = 6 chegadas/hora (IC=10 minutos);
TA = 3 minutos (µ = 20atendimentos/hora
a) Probabilidade de não ter ninguém no sistema:
P0 = 1− λ/µ = 1− 6/20 = 0,7
b) NF = λ
2
µ(µ−λ) = (6
2)/(20(20− 6)) = 0,128
c) NS = λ/(µ− λ) = 0,428
d) NA = NS − NF = 0,428− 0,128 = 0,30
e) TF = λ/µ(µ− λ) = 6/20(20− 6) = 0,021hora = 1,28minutos
f) Para TF = 3 minutos ou TF = 0,05 hora e mantendo o mesmo
µ = 20 clientes/hora, temos: λ = TF×µ
2
1+µ×TF = 10 chegadas/hora
g) A fração do dia em que o telefone está em uso é dado por 1− P0,
ou seja, 30%.
Ivairton | Teoria das Filas e Simulação
46
Modelo M/M/1/K
I Um caso particular e comum é aquele em quea população de
clientes é finita.
I Exemplo: Uma mineradora com 1 escavadeira e alguns
caminhões.
I A tabela asseguir K representa a quantidade finita de clientes
que estão percorrendo o sistema
Nome Descrição Fórmula
NF número médio de clientes na fila NF = K − λ+µλ + (1− P0) +
λ
µ
NS Número médio de clientes no sistema NS = K − λ+µλ + (1− P0) +
λ
µ +
λ
µ
TF Tempo médio que o cliente fica na fila TF = Kλ −
(λ+µ)×(1−P0)
λ2
TS Tempo médio que o cliente fica no sistema TS = Kλ −
(λ+µ)×(1−P0)
λ2
+ 1µ
Pn Prob. de existirem n clientes no sistema Pn =
( µλ )
K−n
(K−n)×ΣKj=0
(
µ
λ
)j
j!
Ivairton | Teoria das Filas e Simulação
47
Modelo M/M/1/K
Exercícios
Exercícios:
1. Clientes chegam a uma barbearia em um ritmo de 3/hora e o
serviço demora, em média, 16 minutos. Qual o tempo de espera
na recepção? e no sistema?
2. Pessoas chegam a uma bilheteria de um teatro a um ritmo de
25/hora. O tempo médio de atendimento da bilheteria é de 2
min. Calcule o tamanho da fila, o tempo médio de espra e a
fração de tempo em que a bilheteria não trabalha.
3. Em um sitema no qual λ = 4 clientes/hora e µ = 6 clientes/hora,
qual a probabilidade de existir no sistema:
(a) zero clientes
(b) 1 cliente
(c) 3 ou 4 clientes
(d) 5 ou mais clietes
Ivairton | Teoria das Filas e Simulação
48
Modelo M/M/1/K
Exercícios
Exercícios:
1. No mesmo sistema anterior, admitindo-se que o custo do cliente
parado seja de R$10/hora, pede-se o custo horário de clientes
no sistema.
2. Em um sistema de filas sequenciais, no qual as peças fluem
pela linha de produção (Linha 1 e Linha 2 alimentam em paralelo
a Linha 3), temos:
λ1 = 10, λ2 = 5, µ1 = 15, µ2 = 30 e µ3 = 20
Calcule:
(a) NF, TF, NS e TS para cada servidor
(b) NS e TS para o sistema como um todo
Ivairton | Teoria das Filas e Simulação
49
O modelo M/M/c
I O modelo M/M/c é aquele em que temos uma única fila e
diversos servidores.
I Tanto a chegada como o atendimento são marcovianos.
I Será considerado que a capacidade de atendimento de cada um
dos servidores é a mesma.
I Para este modelo são válidas as seguintes definições:
I λ = ritmo médio de chegada;
I IC = intervalo médio entre chegadas (IC = 1/λ);
I TA = tempo médio de atendimento, ou de serviço em cada
atendente;
I µ = ritmo médio de atendimento de cada atendente (TA = 1/µ
Ivairton | Teoria das Filas e Simulação
50
O modelo M/M/c
População infinita: fórmulas x gráficos
Fórmulas × Gráficos
As fórmulas para o modelo M/M/c são complexas e difíceis de serem
manipuladas. De modo geral, prefere-se o uso de gráficos de
referência.
I Utilizaremos gráfico para obter o número médio dos clientes na
fila (NF) em função do fator de utilização, tendo como parâmetro
a quantidade de servidores M.
I Utilizaremos gráfico para obter o número médio de clientes no
sistema (NS).
I Para os dois casos a taxa de utilização é:
ρ = λ/Mµ
onde λ é o ritmo de chegada, M a quantidade de servidores e µ
o ritmo de atendimento.
Ivairton | Teoria das Filas e Simulação
51
O modelo M/M/c
População infinita: fórmulas x gráficos
ρ = λ/Mµ
Ivairton | Teoria das Filas e Simulação
52
O modelo M/M/c
População infinita: fórmulas x gráficos
ρ = λ/Mµ
Ivairton | Teoria das Filas e Simulação
53
O modelo M/M/c
População infinita: fórmulas x gráficos
I Em ambos os gráficos a ordenada tem escala logarítmica.
I Em ambos os gráficos o valor da ordenada tende para infinito
quando ρ tende para 1.
I Observa-se a redução acentuada quando dobra-se a
capacidade de atendimento.
I Observa-se também que, aumentando a quantidade de
servidores, o tamanho da fila diminui e aumenta a quantidade de
clientes no sistema.
I Após o uso dos gráficos, as outras variáveis randômicas
fundamentais podem ser obtidas pelas fórmulas de Little (TF =
NF/λ e TS = NS/λ).
Ivairton | Teoria das Filas e Simulação
54
O modelo M/M/c
Exemplos
I Exemplo 1 - Depósito de ferramentas: Retomando o exemplo
onde foi calculado o custo horário de um sistema com 1
atendente em que λ = 1 e µ = 1,2, sendo R$9,00 o custo
horário do atendente e R$18,00 o custo horário do operário
parado. Podemos agora acrescentar diversos atendentes,
avaliando o custo mínimo:
M ρ NS Custo atend. Custo ope. Total
1 0,833 5,0 R$9,00 R$90,00 R$99,00
2 0,417 1,0 R$18,00 R$18,00 R$36,00
3 0,277 0,7 R$27,00 R$12,60 R$39,60
4 0,208 0,6 R$36,00 R$10,80 R$46,80
5 0,200 0,59 R$45,00 R$10,62 R$55,62
Ivairton | Teoria das Filas e Simulação
55
O modelo M/M/c
Exemplos
I Exemplo 2 - Chegada superior a atendimento: Uma agência
bancária possui 5 atendentes e funcionadiariamente das 10:00
às 16:00 (6 horas). O ritmo de chegada é de 110 clientes /hora e
a duração média de atendimento é de 3 minutos (µ=20
atendimentos/hora). Pergunta-se: (a) o tamanho médio da fila;
(b) o tempo médio de espera na fila.
Solução: Temos um problema que não se enquadra no modelo
M/M/c, visto que o funcionamento da agência não tem duração
contínua e infinita, pré-requisito da teoria de filas. Caso isto
ocorresse, teríamos:
ρ = λ/Mµ = 110/(5× 20) = 1,1
Isso nos leva a concluir que tanto o tamanho médio da fila, como o
tempo médio de espera tendem a infinito.
Ivairton | Teoria das Filas e Simulação
56
O modelo M/M/c
Exemplos
I Exemplo 3 - Fila única versus diversas filas: Um banco
deseja modificar a forma de atendimento a seus clientes, que
hoje funciona comdiversas filas, pelo sistema de fina única. Os
dados atuais são:
λ = 70 clientes/hora, que se distribuem em 5 filas
M = 5 atendentes
µ = 20 clientes/hora (TA = 3 minutos)
Solução: (a) situação atual com 5 filas. Em cada fila temos:
λ = 70/5 = 14
TS = 1/(µ− λ) = 0,167 hora = 10 minutos
NS = λ× TS = 14 × 0,167 = 2,33
Nas 5 filas temos: NS (total) = 5 x 2,33 = 11,67 pessoas
Solução: (b) situação futura com fila única
ρ = λ/M.µ = 70/(5 x 20) = 0,7
Usando o gráfico como referêcia: NS = 5 pessoas
TS = NS/λ = 5/70 = 0,07 hora = 4,3 minutos
Ivairton | Teoria das Filas e Simulação
57
O modelo M/M/c
Exercícios
1. Um banco possui dois funcionários trabalhando no setor de
atendimento. O primeiro trabalha apenas com depósito e o
segundo com retiradas. Sabe-se que o tempo de serviço de
ambos segue a distribuição exponencial, com uma média de 3
minutos/cliente. As chegadas obedecem a disribuição de
Poison, com média de 16 chegadas/hora para os depositantes e
14 chegadas/hora para os que fazem retiradas. Qual seria o
efeito no tempo médio no sistema (TS) se ambos os funcionários
trabalhassem com retiradas e depósitos?
2. Um siderúrgica possui 3 veículos para atender deslocamentos
de seus funcionários. O ritmo médio de solicitação de veículos é
de 10 pedidos/hora e o tempo médio de uma viagem é de 20
minutos. Calcule o número médio de clientes na fila e o tempo
médio na fila. Qual deve ser o número adequado de veículos de
modo que o tempo médio de espera na fial seja inferior a 5
minutos?
Ivairton | Teoria das Filas e Simulação
58
O modelo Erlang
I O modelo M/M/c não dimensiona filas precisamente.
I Uma opção de modelo mais preciso é o Erlang (M/Em/c).
I Neste modelo, os atendimentos seguem a Distribuição de Erlang
de grau m.
I O modelo M/M/c fornce um valor para TF (tempo na fila) maior
que o modelo M/Em/c, ou seja, M/M/c superdimensiona a
necessidade de servidores.
Ivairton | Teoria das Filas e Simulação
59
Simulação
Simulação
É a técnica de solução de um problema pela análise de um modelo
que descreve o comportamento do sistema usando um computador.
"Simulação implica na modelagem de um processo ou sistema, de tal
forma que o modelo imite as respostas do sistema real numa
sucessão de eventos que ocorrem ao longo do tempo.”
(Schriber, 1974)
Sistema
É uma agregação de objetos que possuem alguma interação ou
interdependência.
Ivairton | Teoria das Filas e Simulação
60
Simulação
Modelo
É a representação de um sistema
I Os modelos podem ser categorizados como:
I Icônicos
I Analógicos
I Simbólicos
I Matemáticos
I Diagramáticos
Ivairton | Teoria das Filas e Simulação
61
Simulação
I Justificativa para o uso da simulação (no contexto da teoria das
filas):
1. Inviabilidade da interferência do sistema real;
2. O sistema em estudo não existe.
I Metodologia apra a simulação de sistemas:
Etapa 1 Construção do modelo da simulação atual;
Etapa 2 Inclusão de alterações no modelo da situação atual para refletir a
situação futura desejada.
I Método de Monte Carlo é fundamental em simulações de
sistemas discretos. Proporciona recriar o funcionamento de um
sistema real dentro de um modelo teórico.
Ivairton | Teoria das Filas e Simulação
62
Método de Monte Carlo
Método de Monte Carlo
É uma maneira de se transformar um conjunto de números aleatórios
em outro conjunto de números (variáveis aleatórias), com a mesma
distribuição da variável considerada.
I São conceitos importantes:
I números aleatórios;
I distribuições relativas e cumulativas;
I funções relativa e cumulativa.
Ivairton | Teoria das Filas e Simulação
63
Método de Monte Carlo
I Esperamos que a simulação forneça resultados semelhantes
aos da vida real;
I Assim, ao simular, por exemplo, um processo de atendimento,
isso seguirá etapas:
I Sorteio de um número aleatório;
I Uso do número sorteado numa função densidade (que se baseia
num gráfico obtido por uma função cumulativa);
I Obtem-se portanto, o número correspondente ao tempo de
atendimento, por exemplo.
I A garantia do método de Monte Carlo é que quando este
processo se repete em grande número, os valores simulados se
assemelham aos valores reais (no que se refere às variáveis
randômicas).
Ivairton | Teoria das Filas e Simulação
64
Bibliografia
I Estes slides são baseados predominantemente no livro:
PRADO, Darci. Teoria das Filas e da Simulação - Série
Pesquisa Operacional. Volume 2. Ed. Desenvolvimento
Gerencial, Belo Horizonte, 1999.
Ivairton | Teoria das Filas e Simulação
Obrigado!
Prof. Ivairton M. Santos
	Introdução
	Modelagem de Sistemas
	Aplicações
	Filas
	Propriedades
	Variáveis randômicas fundamentais
	Processos de chegada e de atendimento
	Apêndice - Tabelas de referências
	Modelos de filas
	Simulação
	Método de Monte Carlo