Aula02_-_Teoria_das_filas

Prévia do material em texto

MODELAGEM E SIMULAÇÃO DA 
PRODUÇÃO
Prof. Dr. David Custódio de Sena
sena@ufersa.edu.br
SIMULAÇÃO
 Questionário de revisão:
1. Por que a simulação é a melhor disciplina do curso de Engenharia de Produção?
2. O que é um sistema?
3. O que é um modelo?
4. Como a simulação se diferencia de abordagens analíticas?
5. Quais as vantagens e desvantagens da simulação?
6. O que é uma variável de estado?
7. O que é um evento e quais os tipos de eventos?
8. Quais são os elementos passivos em uma simulação?
9. Qual é o elemento ativo em uma simulação?
SIMULAÇÃO
TEORIA DAS FILAS
SIMULAÇÃO
 Tópicos
 Elementos de fila
 Clientes
 Serviços
 Servidores
 Principais variáveis de uma fila
 População
 Padrão de chegada
 Padrão de atendimento
 Disciplina da fila
 Tipos de fila
 Relações matemáticas elementares
 Notação de Kendall
 Aplicação de fila em uma simulação
SIMULAÇÃO
 Os elementos fundamentais de um sistema de fila envolvem 
 Clientes (peças / informações / produtos) 
 Serviço (processamento / operação / tratamento)
 Servidores (máquinas / computadores / operadores)
 E envolvem as seguinte variáveis fundamentais:
SIMULAÇÃO
 A população de potenciais clientes
 Pode ser finita ou infinita;
 Impacta principalmente nos cálculos do comportamento de chegada de um cliente em 
particular.
SIMULAÇÃO
 Padrão de chegada de cliente ( ou IC)
 Comportamento de como um cliente sai da população e entra na fila
População Fila
SIMULAÇÃO
 Padrão de chegada de cliente ( ou IC)
 A chegada de clientes acontecem geralmente em momentos ti (sendo i = 0, 1, ..., n), 
em que t0 < ti < ... < tn;
 Por exemplo, imaginemos que o momento de chegadas de clientes em uma loja foram 
os seguintes:
Cliente (i) Momento de chegada no 
relógio(ti)
1 09:00:15
2 09:00:20
3 09:01:40
4 09:02:05
5 09:02:15
6 09:02:55
7 09:03:20
SIMULAÇÃO
 Padrão de chegada de cliente ( ou IC)
 A variável aleatória rk = tk – tk-1 (em que k ≥ 1) é chamada de intervalo de 
chegada;
 Os intervalos de chegada do exemplo da loja são:
Cliente (i) Momento de chegada (ti) Intervalo de chegada (rk) em 
segundos
1 09:00:15 -
2 09:00:20 5
3 09:01:40 80
4 09:02:05 25
5 09:02:15 10
6 09:02:55 40
7 09:03:20 25
SIMULAÇÃO
 Padrão de chegada de cliente ( ou IC)
 Caso o intervalo temporal de análise seja fixo (ou seja contando o número de 
cliente que chegou nesse intervalo) utiliza-se o ritmo de chegada ().
 Inverso ao intervalo de chegada;
 O ritmo de chegada por minuto para o exemplo da loja foi:
Minuto Ritmo ()
1 2
2 1
3 3
4 1
SIMULAÇÃO
 Padrão de chegada de cliente ( ou IC)
 Pode ser representado em termos de uma função de distribuição particular de 
probabilidade. 
 Por exemplo POISSON (5), NORMAL (5,0.1);
SIMULAÇÃO
 A disciplina da fila
 Como a fila se organiza
SIMULAÇÃO
 A disciplina da fila
 Há dois aspectos básicos que precisam ser identificados
1. A maneira como clientes em fila são eventualmente selecionados para o serviço.
 FIFO, ou PEPS
 LIFO, ou UEPS
 Prioritário
 Aleatório
 Regra própria
SIMULAÇÃO
 A disciplina da fila
 Há dois aspectos básicos que precisam ser identificados
2. O comportamento desses clientes enquanto esperam na fila ou ao chegar na fila exigindo o 
seu serviço. Por exemplo:
 A não entrada na fila
 A desistência durante a espera.
Influência principal:
Tamanho da fila
Influência principal:
Tempo de atendimento
SIMULAÇÃO
 O mecanismo de atendimento
 O motivo da geração da fila;
 Habilidade de um ou mais servidores oferecem um atendimento aos clientes 
durante um período de tempo;
 Dimensões tempo de atendimento (análogo ao intervalo de chegada) e ritmo 
de atendimento  (análogo ao ritmo de chegada  ).
SIMULAÇÃO
 O mecanismo de atendimento
 Segue algumas suposições
1. Cada servidor atende apenas um cliente por vez;
2. Se um servidor está livre e um cliente entra na fila, aquele precisa fornecer seus serviços 
imediatamente;
3. Ao completar um serviço, o servidor precisa atender ao próximo cliente disponível;
4. O serviço é normalmente independente do número de clientes esperando em fila e dos 
clientes já atendidos.
SIMULAÇÃO
 Tipos de fila
 Simples servidor / uma fila um atendente
 Mais simples
 Apenas um servidor para a fila
População Fila Servidor
SIMULAÇÃO
 Tipos de fila
 Múltiplos servidores / uma fila vários atendentes
 Finito número de servidores
População Fila Servidor 2
Servidor 1
Servidor 3
SIMULAÇÃO
 Tipos de fila
 Múltiplos servidores com múltiplas habilidades
 Finito número de servidores
 Servidores polivalentes
População Fila
Servidor 1
Servidor 2
População Fila
Servidor 4
Servidor 3
SIMULAÇÃO
 Variáveis Aleatórias Fundamentais
Número médio de 
clientes na fila
Número de atendentes 
(capacidade)
Número médio de 
clientes em atendimento
Número de 
clientes no sistema
Tempo no sistema
SIMULAÇÃO
 Relações matemáticas elementares
 NS = NF + NA;
 TS = TF + TA;
 NA =  / = TA/IC; 
 NS = NF + NA = NF + (/) = NF + (TA/IC);
 NS = TS (Fórmula de Little).
SIMULAÇÃO
 Variáveis Aleatórias Fundamentais
 Para o caso de “uma fila / um atendente”, chamamos de taxa de utilização do 
atendente a expressão
 =  / 
 No caso de “uma fila / vários atendentes”, a expressão se torna:
 =  / c 
  representa a fração média do tempo em que cada servidor está ocupado.
SIMULAÇÃO
 Exemplo
 Qual a taxa de utilização de um atendente, se chegam 4 clientes por hora e se o 
atendente tem capacidade de atender 10 clientes por hora?
0.4 ou 40%
E se os valores fossem 
inversos?
SIMULAÇÃO
 Variáveis Aleatórias Fundamentais
 Chamamos de intensidade de tráfego a expressão
i = | / | = |TA / IC|
 i representa o número mínimo de atendentes necessários para atender a um dado 
fluxo de tráfego.
 Exemplo
 Se  = 10 clientes/hora e TA = 3 minutos, qual será a intensidade de tráfego?
 Se o fluxo de chegada aumentar para  = 50 clientes/hora, qual vai ser a intensidade de tráfego? 
0.5 ou 50% → 1 atendente
2.5 ou 250% → 3 atendentes
SIMULAÇÃO
 Exemplo
 Em uma fábrica observou-se o funcionamento de um dado setor, em que  = 20 peças 
por hora,  = 25 peças por hora e TS = 0,3 hora. Qual o tamanho médio da fila? Qual 
o número médio de peças no sistema e o número médio de peças no atendimento? 
Qual o mínimo de equipamentos necessários? E se dobrarmos o fluxo de entrada de 
peças?
Tamanho médio da fila = 5,2 peças
Número médio de peças no sistema = 6 peças
Número médio de peças no atendimento = 0,8 peça
Mínimo de equipamentos necessários = 1
Mínimo de equipamentos necessários 
com o fluxo dobrado = 2
Relações matemáticas elementares
NS = NF + NA;
TS = TF + TA;
NA =  / = TA/IC; 
NS = NF + NA = NF + (/) = NF + (TA/IC);
NS = TS (Fórmula de Little).
SIMULAÇÃO
 Ciclo é o tempo gasto para que um elemento, partindo de um ponto de 
referência qualquer, percorra todo o sistema e volte ao mesmo ponto;
 É utilizado em sistemas fechados, em que os clientes não entram e nem saem 
do sistema.
ciclo = (tam. da população) / 
ciclo = TS + TFS (tempo fora do sistema)
Fora do sistema
Sistema (Fila + Atendimento)
SIMULAÇÃO
 Exemplo
 Em uma mineração cada caminhão efetua um ciclo em que é carregado de minério 
por uma das carregadeiras, desloca-se para o britador para o descarregamento e 
retorna às carregadeiras. Verificou-se que o tempo médio (TS) dos caminhões junto ao 
britador é de 12 minutos e que, em média, existem 6 caminhões (NS) no setor. Qual a 
taxa de chegada de caminhões? No mesmo sistema, existindo um total de 30 
caminhões em serviço, qual a duração de um ciclo? Qual o tempo médio para o 
processo completo de carregamento?
SIMULAÇÃO
 Modelos de filas
 Notação Kendall
 De uma maneira geral, um modelo de filas pode ser descrito pela seguinte notação:
A/B/c/K/m/Z
onde:
A descreve a distribuição dosintervalos entre chegada;
B descreve a distribuição do tempo de serviço;
c é a capacidade de atendimento ou quantidade de atendentes;
K é a capacidade máxima do sistema (número máximo de clientes no sistema);
m é o tamanho da população que fornece clientes;
Z é a disciplina da fila.
SIMULAÇÃO
 Modelos de filas
 Notação Kendall
 A e B dependem do tipo de distribuição a que elas se referem:
 M: Exponencial negativa (ou Markoviana ou Poisson);
 Em: Erlang de estágio m;
 Hm: Hiper-exponencial de estágio m;
 Determinística;
 Geral.
 Assim, por exemplo, M/E2/5/20//Randômico significa chegadas Markoviana (ou Poisson), 
atendimento Erlang de segundo grau, 5 atendentes, capacidade máxima do sistema igual a 20 
clientes, população infinita e atendimento randômico;
 A notação A/B/c é muito usada e se supõe que não há limite para o tamanho da fila, a 
população é infinita e a disciplina da fila é FIFO.
SIMULAÇÃO
 Modelos M/M/1
 O ritmo de chegada segue uma distribuição de probabilidade de Poisson em que a 
chegada de clientes segue uma ocorrência aleatória dada uma taxa média λ;
 O tempo de atendimento segue uma distribuição exponencial negativa
representado pelo inverso do fluxo de atendimento médio ;
 Apenas 1 atendente.
SIMULAÇÃO
 Modelos M/M/1
 População infinita
Nome Descrição Fórmula
NF Número médio de clientes na 
fila
NS Número médio de clientes no 
sistema
TF Tempo médio na fila
TS Tempo médio no sistema
Pn Probabilidade de existirem n 
clientes no sistema
)(
2


−
=NF


−
=NS
)( 

−
=TF
 −
=
1
TS
nPn ))(1(




−=
SIMULAÇÃO
 Exemplo
 Suponhamos que as chegadas a uma cabine telefônica obedecem a lei de Poisson, com 
ritmo de 6 chegadas por hora. A duração média do telefonema é de 3 minutos e 
suponhamos que siga a distribuição exponencial. Pede-se:
 A probabilidade de uma pessoa chegar à cabine e não ter que esperar;
 O número médio de pessoas na fila;
 O número médio de pessoas no sistema;
 O número médio de clientes usando o telefone;
 O tempo na fila;
 Para qual ritmo de chegada teríamos a situação em que o tempo médio de espera na fila seria de 
3 minutos?
 A fração do dia durante o qual o telefone está em uso.
70%
0.12 pessoa
0.42 pessoa
0.30 pessoa
0.02 hora ou 1.2 minutos
10 chegadas/hora
30%
SIMULAÇÃO
 Modelos M/M/1
 População finita
 Notação K (Tamanho da população)
4
3
2
1
0
0 5 10 15 20 25 30 
NF
SIMULAÇÃO
 Modelos M/M/1
 População finita
Nome Descrição Fórmula
NF Número médio de clientes na 
fila
NS Número médio de clientes no 
sistema
TF Tempo médio na fila
TS Tempo médio no sistema
Pn Probabilidade de existirem n 
clientes no sistema




+−+
+
−= )1( 0PKNF






++−+
+
−= )1( 0PKNS
2
0)1()(



PxK
TF
−+
−=





+
−+
−=
2
0 )1()( PxKTS
 =
−
−
=
K
j
j
nK
n
j
xnK
P
0 !
)(
)(
)(




SIMULAÇÃO
 Modelos M/M/c
 Única fila e diversos servidores;
 O ritmo de chegada segue uma distribuição de probabilidade de Poisson em que a 
chegada de clientes segue uma ocorrência aleatória dada uma taxa média λ;
 O tempo de atendimento segue uma distribuição exponencial negativa
representado pelo inverso do fluxo de atendimento médio ;
 As fórmulas para o modelo M/M/c são complexas e difíceis de serem 
manipulados;
 A preferência generalizada é pelo uso de gráficos.
SIMULAÇÃO
 Modelos M/M/c
 NF versus Fator de utilização ( =  / c)
SIMULAÇÃO
 Modelos M/M/c
 NS versus Fator de utilização ( =  / c)
SIMULAÇÃO
 Conclusões
 Quando  tende para 1, o tamanho da fila tende para o infinito;
 Um sistema no qual temos fila imensa ( próximo e menor que 1) pode se 
transformar em outro praticamente sem fila pela duplicação da capacidade de 
atendimento;
 Um sistema em que o tempo de resposta é importante ( a fila deve ser sempre 
pequena) deve ser tal que  fique abaixo de 0,6. Caso este sistema esteja em 
processo de crescimento ( está crescendo), deve-se pensar em substituir a 
capacidade de atendimento antes de  atingir 0,9.
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 No tempo 0 o sistema está vazio e ocioso;
 Unidades de tempo: minutos;
 A primeira entidade chega no momento 0;
 Tempo de simulação: 15 minutos;
 Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59, 0.73
 Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
 Momentos de chegada: ???
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Medidas de desempenho
 Produção total de peças (P)
 Tempo médio de espera das peças na fila
 Tempo máximo de espera na fila:
N = Número total de peças
Di = tempo de espera da i-ésima peça
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Medidas de desempenho
 Número máximo de peças na fila:
 Número médio de clientes na fila 
T
Di
N
i

=1
T = Tempo total de simulação
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Setup
t0
1
t0
1
2
3
Peça em processo
Peças em fila
P Tempo médio de 
espera das peças na 
fila
Tempo 
máximo de 
espera na fila
Número 
máximo de 
peças na fila
Número 
médio de 
clientes na fila 
0 0 0 0 0
Peça 
(i)
Tempo em 
fila (Di)
Em processamentoEm fila
Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59, 0.73
Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 t = 0.00
t0
1
t0
1
2
3
t0
1
t0
1
2
3
Peça em processo
Peças em fila
Peça 
(i)
Tempo em 
fila (Di)
P Tempo médio de 
espera das peças na 
fila
Tempo 
máximo de 
espera na fila
Número 
máximo de 
peças na fila
Número 
médio de 
clientes na fila 
0 0 0 0 0
Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59, 0.73
Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Chegada da peça 1 em t = 0.00
t0
1
t0
1
2
3
1
t0
1
t0
1
2
3
Peça em processo
Peças em fila
Peça 
(i)
Tempo em 
fila (Di)
P Tempo médio de 
espera das peças na 
fila
Tempo 
máximo de 
espera na fila
Número 
máximo de 
peças na fila
Número 
médio de 
clientes na fila 
0 0 0 0 0
Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59, 0.73
Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Partida da peça 1 em t = 4.58
t0
1
2
3
t0
1
t0
1
t0
1
2
3
Peça em processo
Peças em fila
Peça 
(i)
Tempo em 
fila (Di)
1 0
P Tempo médio de 
espera das peças na 
fila
Tempo 
máximo de 
espera na fila
Número 
máximo de 
peças na fila
Número 
médio de 
clientes na fila 
1 0 0 0 0
Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59, 0.73
Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Chegada da peça 2 em t = 6.84
t0
1
t0
1
2
3
2
t0
1
t0
1
2
3
Peça em processo
Peças em fila
Peça 
(i)
Tempo em 
fila (Di)
1 0
2 0
P Tempo médio de 
espera das peças na 
fila
Tempo 
máximo de 
espera na fila
Número 
máximo de 
peças na fila
Número 
médio de 
clientes na fila 
1 0 0 0 0
Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59, 0.73
Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Chegada da peça 3 em t = 9.24
t0
1
t0
1
2
3
23
t0
1
t0
1
2
3
Peça em processo
Peças em fila
Peça 
(i)
Tempo em 
fila (Di)
1 0
2 0
3 0
P Tempo médio de 
espera das peças na 
fila
Tempo 
máximo de 
espera na fila
Número 
máximo de 
peças na fila
Número 
médio de 
clientes na fila 
1 0 0 1 0
Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59,0.73
Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Partida da peça 2 em t = 9.80
t0
1
t0
1
2
3
3
t0
1
t0
1
2
3
Peça em processo
Peças em fila
Peça 
(i)
Tempo em 
fila (Di)
1 0
2 0
3 0,56
P Tempo médio de 
espera das peças na 
fila
Tempo 
máximo de 
espera na fila
Número 
máximo de 
peças na fila
Número 
médio de 
clientes na fila 
2 0,187 0,56 0 0,057
Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59, 0.73
Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Chegada da peça 4 em t = 11.94
t0
1
t0
1
2
3
34
t0
1
t0
1
2
3
Peça em processo
Peças em fila
Peça 
(i)
Tempo em 
fila (Di)
1 0
2 0
3 0,56
4 0
P Tempo médio de 
espera das peças na 
fila
Tempo 
máximo de 
espera na fila
Número 
máximo de 
peças na fila
Número 
médio de 
clientes na fila 
2 0,187 0,56 1 0,046
Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59, 0.73
Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Chegada da peça 5 em t = 14.53
t0
1
t0
1
2
3
345
t0
1
t0
1
2
3
Peça em processo
Peças em fila
Peça 
(i)
Tempo em 
fila (Di)
1 0
2 0
3 0,56
4 2,59
5 0
P Tempo médio de 
espera das peças na 
fila
Tempo 
máximo de 
espera na fila
Número 
máximo de 
peças na fila
Número 
médio de 
clientes na fila 
2 0,7875 2,59 2 0,216
Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59, 0.73
Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Fim da simulação em t = 15.00
t0
1
t0
1
2
3
345
t0
1
t0
1
2
3
Peça em processo
Peças em fila
Peça 
(i)
Tempo em 
fila (Di)
1 0
2 0
3 0,56
4 3,06
5 0,47
P Tempo médio de 
espera das peças na 
fila
Tempo 
máximo de 
espera na fila
Número 
máximo de 
peças na fila
Número 
médio de 
clientes na fila 
2 3,694 3,06 2 0,272
Produção total 
de peças
Tempo médio de espera 
em fila =
0+0+0,56+3,06+0,47
5
= 0,818
Tempo máximo 
de espera na fila
Número máximo 
de peças na fila
Número médio de 
clientes na fila =
0+0+0,56+3,06+0,47
15
≅ 0,273
Tempos entre chegadas: 6.84, 2.40, 2.70, 2.59, 0.73
Tempos de processamento: 4.58, 2.96, 5.86, 3.21, 3.11
SIMULAÇÃO
 Exemplo de fila com simulação
 Exemplo de uma fila de simples servidor
 Taxa de utilização (em vermelho)
t0
1
t0
1
2
3
345
t0
1
t0
1
2
3
Peça em processo
Peças em fila
T
dttB
T

0
)(
=
4.58 + 2.96 + 15 − 9.80
15
≅ 84,93%
Tempo de operação 
da terceira entidade
SIMULAÇÃO
 Resumo
 Elementos de fila
 Clientes
 Serviços
 Servidores
 Principais variáveis de uma fila
 População
 Padrão de chegada
 Padrão de atendimento
 Disciplina da fila
 Tipos de fila
 Relações matemáticas elementares
 Notação de Kendall
 Aplicação de fila em uma simulação
SIMULAÇÃO
 Referências:
 Teoria das filas e da simulação. Darci Prado.
 Introduction to Operactions Research. Frederick S. Hillier e Gerald J. Lieberman.
 Queuing Theory: A problem Solving Approach. Leonard Gorney.
 mcu.edu.tw/~hyu/Queue-534.xls
SIMULAÇÃO
ATÉ BREVE!!!
	Slide 1: MODELAGEM E SIMULAÇÃO DA PRODUÇÃO
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55