8.+Teoria+das+Filas Copia

Prévia do material em texto

Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Teoria das Filas 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Exemplo Protótipo 
 Um pronto socorro atende a casos de 
emergência, fornecendo cuidados médicos 
a pacientes. Os pacientes chegam no 
hospital em ambulâncias ou carros 
particulares. A qualquer momento há um 
médico de plantão no pronto socorro. 
Devido ao crescimento de pacientes 
chegando no horário de pico (início da 
noite) com casos de urgência (ao invés de 
emergência), foi feita uma proposta de se 
alocar um segundo médico para o pronto 
socorro neste horário. 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
 Processo de Filas Básico: 
 Clientes que necessitam de atendimento são 
gerados ao longo do tempo por uma fonte de 
entradas. Esses clientes entram no sistema de 
filas e pegam uma fila. Em certos momentos, 
um integrante da fila é selecionado par o 
atendimento por alguma regra conhecida como 
disciplina da fila. O atendimento necessário é 
então realizado para o cliente pelo mecanismo 
de atendimento, após o qual o cliente deixa o 
sistemas de filas. 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
 Fonte de Entradas (população solicitante) 
 Tamanho: número total de clientes que poderiam 
precisar de atendimento de tempos em tempos, isto 
é, o número total de possíveis clientes distintos. 
 Pode ser de tamanho finito ou infinito (entradas 
limitadas ou ilimitadas). 
 Como os cálculos são mais fáceis no caso infinito, 
caso o tamanho seja grande, por simplificação, 
considera-se infinito. 
 Padrão estatístico de geração de clientes: 
 Processo de Poisson (distribuição poisson) 
 Distribuição exponencial 
 Em ambos casos observar tempo entre chegadas 
 Outros comportamentos incomuns como recusa. 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
 Fila 
 É o local onde os clientes aguardam antes de 
serem atendidos. 
 Finita ou infinita. 
 Finito é de maior complexidade, mas o número 
finito pode ser muito relevante em casos reais 
 Disciplina da Fila 
 Regra pela qual os integrantes da fila são 
selecionados para atendimento 
 FIFO (PEPS), LIFO (UEPS), por prioridades, 
aleatório. 
 Normalmente FIFO 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
 Mecanismo de atendimento 
 Formado por instalações de atendimento, que 
contém canais de atendimentos paralelos, 
chamados atendentes. 
 As instalações de atendimento podem ser múltiplas 
e o cliente pode ser atendida por uma sequência 
delas (canais de atendimento série) 
 O tempo decorrido entre o início de atendimento 
até o seu término para um cliente em uma 
instalação de atendimento é denominado tempo de 
atendimento (ou tempo de permanência). 
 Este tempo deve ser modelado. Boas aproximações 
são: 
 Distribuição exponencial, degenerada ou Erlang. 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
atendimento μ 
atendimento μ 
atendimento μ 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
 Processo de Filas Elementar 
 A teoria das filas foi aplicada a vários tipos diferentes de 
situações com filas. 
 O tipo mais freqüente e básico é: uma fila de espera única 
(que pode ou não estar vazia) se forma na frente de uma 
única instalação de atendimento na qual se encontram um 
ou mais atendentes. Cada cliente gerado por uma fonte 
de entradas é atendido por um dos atendentes, após 
aguardar um tempo na fila de espera (se for o caso). 
 Um atendente não precisa corresponder a uma única 
pessoa. Pode ser uma equipe, uma pessoa com 
maquinário, uma máquina ou um conjunto de máquinas. 
 Os clientes não precisam ser pessoas podem ser 
trabalhos, processos, equipamentos, materiais, etc. 
 A fila não precisa ser física e concentrada em algum lugar. 
 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
 Processo de Filas Elementar 
 A maioria dos sistemas de filas 
pressupõem que: 
 Tempos entre chegadas são 
independentes e distribuídos de forma 
idêntica, e 
 Tempos de atendimento são 
independentes e distribuídos de forma 
idêntica 
 São identificados como: 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
 
 Processo de Filas Elementar: 
 Onde 
 M: distribuição exponencial (markoviana) 
 D: distribuição degenerada (tempos constantes) 
 Ek: distribuição de Erlang (parâmetro de forma = k) 
 G: distribuição geral (distribuição arbitrária) 
 Exemplo, modelo M/M/s, pressupõe que os tempos entre 
atendimentos e os tempos de atendimento possuem 
distribuição exponencial e o número de atendentes é s, sendo 
s um número inteiro positivo. 
Chegadas 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
 Terminologia e Notação 
 𝐿 : Estado do sistema: número de clientes no sistema de filas 
 𝐿𝑞 :Comprimento da fila: número de clientes que aguardam o 
início do seu atendimento = estado do sistema menos o número 
de clientes que estão sendo atendidos. 
 L(t): número de clientes sistema de filas no instante t (t≥0) 
 Pn(t): probabilidade de exatamente n clientes no sistema de filas 
no instante t, dado o número no instante 0. 
 s: número de atendentes (canais de atendimento paralelos) no 
sistema de filas. 
 λn: taxa média de chegada (número de chegadas esperado por 
unidade de tempo) de novos clientes quando n clientes se 
encontram no sistema. 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
 Terminologia e Notação 
 : taxa média de chegada global de clientes 
 μn: taxa média de atendimento para o sistema global (número de 
clientes esperado que completa o atendimento por unidade de 
tempo) quanto n clientes se encontram no sistema. 
 Quando λn for constante para todo n, essa constante é 
representada por λ. 
 Quando a taxa média de atendimento por atendente ocupado for 
uma constante para todo n≥1, essa constante é representada por 
μ. Logo, quando n≥s, μn=s.μ 
 Nestes casos 1/λ: é tempo esperado entre chegadas; e 1/μ: é o 
tempo de atendiemento esperado. 

Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Estrutura Básica dos Modelos de Fila 
 Terminologia e Notação 
 𝜌 : Fator de utilização para a instalação de atendimento. 
 𝑃𝑛 : Probabilidade de haver n clientes no sistema 
 𝑃0 : Probabilidade de haver 0 clientes no sistema 
 𝑊 : Tempo de espera no sistema (wait time) 
 𝑊𝑞 : Tempo de espera na fila (wait time in queue) 
 𝑃 °𝑤 > 𝑡 : Probabilidade do tempo de espera no sistema ser maior 
do que t. 
 𝑃 °𝑤𝑞 > 𝑡 : Probabilidade do tempo na fila no sistema ser maior do 
que t. 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Distribuição Exponencial 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Distribuição Poisson 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Distribuição Erlang 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Distribuição Normal 
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 
 
Distribuição Uniforme