O BLOG DO ENGENHEIRO!

TEORIA DAS FILAS

Segundo Luciano Cajado a Teoria das filas “tenta através de análises matemáticas detalhadas encontrar um ponto de equilíbrio que satisfaça o cliente e seja viável economicamente para o provedor do serviço”.

A teoria das filas é um ramo da probabilidade que estuda a formação de filas, utilizando para isto análises matemáticas e propriedades das filas. Através da teoria das filas é possível prever o comportamento de um sistema que ofereça serviços e cuja demanda cresce aleatoriamente.

Esta teoria é um tipo de técnica disponível para a modelagem de sistemas, que aborda o assunto através de fórmulas matemáticas.


A abordagem matemática das filas se iniciou em 1908 na Dinamarca, Copenhague, através de A. K. Erlang, considerado o pai da teoria das filas, quando trabalhava em uma companhia telefônica estudando o problema de redimensionamento de centrais telefônicas, porém, somente a partir da segunda guerra mundial que a teoria foi aplicada a outros problemas de filas.

A modelagem de filas tem sido usada nas seguintes áreas: no transporte ferroviário, rodoviário, marítimo e no transporte de elevadores; na comunicação, no processamento de dados, dentre outros.


Definições
Para o estudo da teoria das filas faz-se necessário o conhecimento de alguns termos comuns. São estes:

· Filas - Segundo Feofiloff fila é uma estrutura de dados que permite a entrada de novos elementos e remoção de elementos antigos.
· Rede de filas – Compreende o conjunto das entidades interligadas, que oferecem serviços, e de usuários;
· Centro de serviço - Representa os recursos do sistema, podendo incluir um ou mais servidores e um conjunto de clientes que esperam pelo serviço;
· Fila - São os clientes que estão esperando pelo serviço, juntamente com os que já estão sendo atendidos por algum dos servidores;
·Fila de espera – Neste caso somente são considerados os clientes que estão aguardando pelo atendimento.

Sistema de filas
A presença de filas ocorre quando a procura por um determinado serviço é maior que a capacidade que um determinado sistema tem de prover este serviço.
Um sistema de filas pode ser entendido como clientes chegando, esperando pelo serviço, quando não são atendidos de imediato e saindo do sistema após terem sido atendidos. É importante compreender que "Cliente", em teoria das filas, deve ser entendido como um termo genérico, e, portanto não se refere somente a seres humanos, podendo este conceito abranger outros aspectos.
São várias as aplicações da teoria das filas. Entre as muitas existentes destacam-se pela sua importância:

· Fluxo de tráfego (aviões, carros, pessoas, comunicações);

· Escalonamento (pacientes em hospitais, programas em computadores);

· Prestação de serviços (bancos, correios, lanchonetes).

Componentes de um sistema de filas

Um sistema de filas consiste no processo de chegada, da distribuição do tempo de serviço, do número de servidores, da capacidade do sistema, da população de usuários e da disciplina de atendimento.

a) Processo de chegada
O processo de chegada é o indicador do padrão de chegada dos clientes no sistema. Apresenta comportamento estocástico, isto é, as chegadas ocorrem no tempo e no espaço obedecendo as leis da probabilidade, fazendo-se necessário conhecer qual a distribuição de probabilidade que descreve os tempos entre as chegadas dos clientes.
A distribuição mais comum é a de Poisson, o que significa que os tempos entre as chegadas são distribuídos de forma exponencial.
Clientes podem chegar simultaneamente (chegada em batch) e se for possível, é necessário saber a distribuição de probabilidade do tamanho do batch. As reações do cliente na fila podem variar. O cliente pode esperar independentemente do tamanho da fila, pode decidir não entrar no sistema quando a fila está muito grande, como pode também esperar na fila durante um determinado tempo e desistir antes de ser atendido. É possível também a hipótese do cliente mudar de uma fila para outra em sistemas com servidores paralelos.
O padrão de chegada de clientes em função do tempo pode ser permanente e neste caso, a distribuição de probabilidade que descreve as chegadas não depende do tempo. Também pode ser não-permanente, ou seja, o padrão de chegada muda com o tempo.

b) Distribuição do tempo de serviço
Assim como ocorre no processo de chegada, também é necessário conhecer a distribuição de probabilidade do tempo de serviço, sendo válidas as mesmas distribuições apresentadas.
O estado pode ser independente o que significa que o processo de atendimento não depende do número de clientes que esperam pelo serviço. Em compensação, em um estado dependente, o processo de atendimento muda de acordo com o número de clientes que aguardam na fila.
Assim como acontece no processo de chegada, o padrão de serviço pode variar de acordo com o tempo e caso não ocorra variação o padrão é dito estacionário.

c) Número de servidores
Também conhecido como número de canais de serviço, este indicador refere-se a quantidade de "pontos de atendimento" do sistema, de forma a servir aos clientes paralelamente. Um sistema que possui mais de um servidor pode ocorrer de duas formas: Em um sistema de fila única para todos os servidores, como em um caixa de banco ou em um sistema de múltiplas filas, uma para cada servidor, como em um caixa de supermercado.

d) Capacidade do sistema
Está relacionado ao número máximo de clientes que o sistema suporta. A capacidade pode ser infinita, sendo mais fácil de estudar, ou finita. Se a capacidade de um sistema for finita, quando este estiver lotado nenhum cliente pode entrar no sistema até que um cliente saia dele, liberando espaço.

e) População de usuários
Refere-se ao potencial de clientes que podem chegar a um sistema. Este componente pode ser finito ou infinito.

f) Disciplina de atendimento
Descreve a forma como os clientes saem da fila de espera para serem atendidos. São estas:
· FCFS (First Come, First Served): O primeiro cliente a chegar é o primeiro a ser atendido. Esta disciplina é a mais comum, principalmente na vida diária;
· FIFO (First In, First Out): O primeiro a entrar é o primeiro a sair;
· LCFS (Last Come, First Served): O último cliente a chegar é o primeiro a ser atendido;
· LIFO (Last In, First Out): Último a Chegar, Primeiro a Sair. Esta disciplina de fila é aplicável em sistemas em que o item mais recente é mais fácil de ser recuperado, por exemplo, um sistema de controle de estoque;
· Fila com prioridade: A cada cliente é atribuída uma prioridade; e aqueles clientes que possuem maior prioridade têm preferência no atendimento. Pode ser de dois tipos:
Preemptivo: o cliente com maior prioridade é atendido imediatamente, sendo necessário interromper o atendimento ao cliente com menor prioridade. Ao terminar o atendimento do cliente preferencial, o cliente de menor prioridade volta a ser atendido, devendo continuar o processo de onde parou ou então reiniciá-lo;
Não-preemptivo: o cliente com maior prioridade é direcionado para o início da fila, mas só é atendido quando o cliente em atendimento sai do sistema, mesmo se este for de prioridade mais baixa;
· Round-robin (algoritmo): Cada cliente recebe uma fatia de tempo do servidor, denominado quantum, dentro da qual deve ser atendido. Após o término do quantum, se a atividade não foi completada, o cliente deve ser retirado do sistema e outro passa a ser atendido em seu lugar. Posteriormente, o cliente que foi interrompido retorna ao servidor e continua a sua atividade. É muito comum em escalonamento de processos da CPU.

Tipos de filas:

· · 1 fila e 1 servidor;

· · 1 fila e n servidores;

· · m filas e n servidores;

· · filas especiais (ex: caixas expressos de supermercados);

· · filas que seguem uma alteração dinâmica do sistema de atendimento.

texto elaborado por: Felipe Ribeiro, Katiucia Almeida, Rafaela dos Anjos, Raymundo Neto, Vanessa Prado.