Teoria das Filas

Prévia do material em texto

Teoria das Filas
ENGG66 - Avaliação e Desempenho do Sistema
Juliete Barros dos Santos 
Jorge Lukas Bandarra
Definição: Fila
 Uma fila é formada por unidades que chegam a um posto de serviço, onde não possam ser atendidas prontamente, tendo ocasionalmente que esperar para sê-lo.
 A formação de uma fila, embora em muitos casos são indesejáveis, elas são inevitáveis.
 As filas existem em todas as parte nos bancos nas lojas, nos hospitais, nos sistemas operacionais.
Teoria das Filas
A teoria das filas é um ramo da probabilidade que estuda a formação de filas, através de análises matemáticas precisas e propriedades mensuráveis das filas.
Foi desenvolvida para prover modelos que retratam previamente o comportamento de um sistema que forneça serviços que possuam demandas que aumentem aleatoriamente.
A abordagem matemática das filas se iniciou em 1908, na Dinamarca. 
O pioneiro da investigação foi o matemático Agner Krarup Erlang no redimensionamento de centrais telefônicas.
Configuração do Sistemas de filas
O Sistema:
Processo de chegada
Distribuição do tempo de serviço
Configuração da fila
Disciplina de atendimento
Processamento
Configuração do Sistemas de filas
Sistemas de filas:
Processos de Chegada:
Comportamento determinístico ou estocástico;
O lambda (𝛌)é a taxa média de chegada de itens na fila;
As chegadas podem ser individuais ou em grupos;
A taxa de chegada pode ser expressa em minutos, dias ou ano
Distribuição de Poisson:
Número de chegadas que chegam, segue um processo de Poisson com média de chegada 𝛌
Para 𝛌 = 4 tem-se:
Estabelecendo uma distribuição de chegada de Poisson discreta
Dado um valor de 𝛌,
P(X) = Probabilidades de X chegadas 
X = número de chegadas por unidade de tempo
𝛆 = 2.7183 (base do logaritmo natural)
Exemplo:
Se a taxa média de chegada por hora é de duas pessoas (𝛌=2), qual é a probabilidade de (X=3) chegadas por hora?
 
Estabelecendo uma distribuição de chegada de Poisson discreta
Distribuição do tempo de serviço
Os Serviços podem ser:
Simples;
Batch.
O estado pode ser independente.
Distribuição do tempo de serviço
Disciplinas das filas
FCFS (First Come, First Served): Primeiro a Chegar, Primeiro a ser Atendido
FIFO (First In, First Out): Primeiro a Entrar, Primeiro a Sair).
LCFS (Last Come, First Served): Último a chegar, Primeiro a ser Atendido
LIFO (Last In, First Out): Último a Chegar, Primeiro a Sair.
Fila com prioridade:
Preemptivo: 
Não-preemptivo:
Round-robin (algoritmo)
Capacidade do Sistema
Finita ou Infinita
Limitação física para o número de pessoas que podem fazer parte do sistema.
Modelos sofisticados:
Troca de filas;
Desistências
Atendimento/chegada dependente do tamanho da fila
Notação de Kendall:
A/S/m/K/N/Q
Um modelo de filas é descrito por uma sucessão de símbolos, colocados em campos delimitados por barras inclinadas:
A: Distribuição dos tempos entre as chegadas (Processo de chegada);
S: Distribuição dos tempos de serviço;
m: Número de servidores;
K: Capacidade do sistema;
N: Tamanho da população;
Q: Disciplina de atendimento.
Nos casos em que a capacidade é ilimitada, a população muito grande e a disciplina é a FCFS, os três últimos símbolos podem ser omitidos.
Distribuições de probabilidade
Exponencial (M)
Uniforme (U)
Arbitrária ou Geral (G)
Erlang ( Ek )
Hiperexponencial ( Hk )
Exemplo: Ilustração da notação de Kendall
M/G/4/50/2000/LCFS
Processo de chegada exponencial (Markoviano) ou de Poisson
Distribuição dos tempos de serviço arbitrária (Geral)
Quatro servidores
Capacidade para cinquenta clientes
População de dois mil clientes
Disciplina de atendimento "Último a Chegar, Primeiro a ser Servido"
Exemplo: Ilustração da notação de Kendall
D/M/1/ ∞ /∞ /RR
Processo de chegada determinístico
Distribuição dos tempos de serviço exponencial (Markoviano) ou de Poisson
Um servidor
Capacidade ilimitada
População infinita
Disciplina de atendimento Round-robin
Lei de Little
A Lei de Little foi apresentada em 1961 por John DC Little
Relaciona o número de clientes no sistema com o tempo médio despendido no sistema:
Número médio de clientes = Taxa de chegada x Tempo médio de resposta
Tempo médio de resposta = Tempo médio de serviço + Tempo médio de espera
Fila M/M/1
As chegadas ocorrem a uma taxa λ de acordo com um processo de Poisson e movem o processo do estado i + 1 .
Tempos de serviço têm uma distribuição exponencial com o parâmetro de taxa μ na fila M/M/1, em que 1 / μ é o tempo médio de serviço.
Um único servidor atende os clientes um por vez no fim da fila, de acordo com a disciplina first-come, first served ("primeiro a chegar, primeiro a ser servido"), Quando o serviço está completo, o cliente deixa a fila e o número de clientes no sistema é reduzido em um.
O buffer tem tamanho infinito, então não há limite ao número de clientes que pode conter.
Fila M/M/1
Fila M/M/1
Fila M/M/1
Fila M/M/1
Fila M/M/1
Fila M/M/1
Fila M/M/1
Fila M/M/1
Fila M/M/1
Fila M[X]/M/1
Clientes chegam em grupos de tamanho X
cada grupo chega de acordo com um processo de Poisson com razão λ
Tempo de serviço tem distribuição exponencial de razão μ.
Um exemplo dessa fila é formada em restaurantes, onde os clientes chegam em grupos de tamanho aleatório, e são atendidos um a um, como por exemplo em uma fila de Fast Food.
Fila M/M[X]/1
Configura uma fila em que as entradas são um a um;
As saídas são em grupos;
O servidor aguarda um grupo de tamanho K se formar para iniciar o atendimento, ou quando o primeiro cliente chega, o servidor inicia o atendimento e os demais clientes que chegam se juntam `a esse cliente durante o atendimento, e também são atendidos em grupos de no máximo;
Um exemplo deste tipo de fila pode ser encontrado em parques de diversão, se considerarmos que as entradas são um a um. Uma atração, como por exemplo uma montanha-russa só é iniciada quando há pessoas o suficiente para completar o carrinho.
Fila M/M/c
Semelhante ao M/M/1
Agora considera um sistema com c servidores.
Agora as taxas de chegadas e saídas são dadas por:
A intensidade de tráfego é:
O estado se encontrar em equilíbrio
Fila M/M/c
Valor esperado do número de clientes:
Medida de desempenho do sistema:
Exemplo: Fila M/M/C
Seja um aeroporto, agora com duas pistas de pouso/decolagem. Os aviões chegam a uma taxa de 15/hora, e levam em média 3 minutos para aterrissar. Assumindo que as chegadas são um processo de Poisson, e o tempo de aterrissagem seguem uma distribuição exponencial.
Exemplo: Fila M/M/C
Fila M/M/1/K
Fila M/M/1/K
Fila M/M/1/K
Simulação computacional
As fórmulas abaixo para o tempo médio, e para o comprimento da fila permitem a validação dos resultados obtidos experimentalmente e comparados com a simulação. Os parâmetros ρ e λ correspondem à intensidade de tráfego e taxa de chegada, respectivamente, e n é o número de servidores. A equação 3 fornece os valores de Tq em ms. 
Simulação computacional
Curva de tempo médio de espera em função da intensidade de tráfego ρ
Simulação computacional
Comparação de tempo médio entre o resultado experimental e a expressão teórica.
Pela figura, observa-se que os resultados experimentais são bastante próximos das expressões teóricas apresentadas em [1]. Nota-se que quanto maior for a intensidade de tráfego, ou seja, a razão entre as taxas de chegada e de partida, maior será o tempo médio de espera, o que é absolutamente natural e intuitivo.
Referências
https://pt.wikipedia.org/wiki/Teoria_das_filas
https://www.ime.unicamp.br/~hlachos/ME323-Teoria%20Filas.pdf
Pesquisa Operacional: Vídeos-Aulas UNIVASF