TEORIA DAS FILAS

A Teoria das Filas tem o objetivo de avaliar o comportamento de um sistema de filas e seus parâmetros, como:

ü  Tempo de espera médio;

ü  Probabilidade de formação de fila;

ü  Porcentagem de clientes rejeitados pelo sistema;

ü  Probabilidade de um cliente esperar mais do que o tempo estimado;

ü  Número médio de clientes na fila;

ü  Probabilidade de que todos os servidores estejam ociosos.

DESCRIÇÃO DE UM SISTEMA DE FILAS

A teoria das filas é uma aplicação do processo estocástico de tempo contínuo chamado também de Processo de Markov.

A figura abaixo mostra os componentes básicos de um sistema de filas. Os clientes potenciais e atuais são representados por círculos pequenos e podem ser pessoas, máquinas, partes ou qualquer outro ente. Os atendentes são representados por quadrados e podem ser qualquer tipo de fonte, tais como, pessoas, máquinas, oficina de reparos, que executam uma função.

Figura 1: Componentes básicos de um sistema de filas.

Fonte: www.paulonacaratti.eti.br

Os clientes que chegam ao sistema entram em atendimento imediatamente se algum dos atendentes está ocioso. Se todos os atendentes estão ocupados, o cliente espera na fila até que um atendente esteja livre. Depois de um período finito de tempo, o cliente sai do sistema. Os detalhes do processo dependem dos valores dos parâmetros e suposições adotadas pelos componentes do sistema.

A fonte de input, também conhecida como população de chamada, é um grupo de clientes potenciais que podem precisar dos serviços oferecidos pelo sistema. A fonte de input está caracterizada por seu tamanho N, que geralmente é assumido infinito por motivos de modelagem e a distribuição de probabilidade, descrevendo os tempos de chegada.

A fila de espera é o número de clientes esperando ser atendidos, e podem estar concentrados num lugar fixo como num banco ou podem estar distribuídos no tempo e espaço como aviões preparados para aterrissar. A disciplina da fila de espera define as regras pelas quais os clientes são selecionados para atendimento.

O mecanismo de atendimento é o processo pelo qual os clientes são atendidos. A suposição geral é que o atendimento é providenciado por um ou mais atendentes idênticos operando em paralelo. No caso de ter uma rede de filas de espera, várias configurações serão consideradas. As características do atendimento são o número de atendentes S, e a distribuição de probabilidade do tempo de atendimento.

Um sistema de filas é a combinação das filas de espera e os atendentes. O número de clientes no sistema é a primeira medida para analisar o sistema de filas de espera. Seu número representa o estado do sistema.

Figura 2: Rede de Transição de Estados de um Sistema de Filas

Fonte: http://www.decom.fee.unicamp.br

Na figura acima, os estados estão representados por pequenos círculos com um número indicando a quantidade de clientes nesse estado. O estado zero é um estado vazio quando não existem clientes e todos os atendentes estão ociosos.

Vale ressaltar que Estado é o número total de clientes no sistema. Ou seja, o número de clientes na fila de espera mais o número de clientes que estão sendo atendidos.

Nos estados de 1 até n, todos os clientes estão sendo atendidos e ninguém está na fila de espera. Para estados maiores que n, todos os atendentes estão ocupados e alguns clientes estão na fila de espera. Os arcos ou setas representam eventos. Uma chegada denominada pela letra λ, causa ao sistema aumentar em um, enquanto que uma saída denominada por μ, é a causa do número no sistema decrescer em um.

Posto que ambos os tempos de chegada e atendimento sejam variáveis aleatórias, o estado do sistema é um processo estocástico. Para sistemas estáveis, existem probabilidades em estados estáveis do número de clientes no sistema.

A teoria das filas envolve fórmulas para calcular as probabilidades em estado estável de diferentes configurações do sistema de filas. A maioria delas requer que os tempos de chegada e os tempos de atendimento sejam governados pela distribuição exponencial de probabilidade. Resultados aproximados existem quando as distribuições não são exponenciais.

Dadas as probabilidades em estado estável, se calcula uma variedade de variáveis que interessam ao desenhista ou operador de um sistema de filas. Estas englobam o valor esperado do número de clientes no sistema, o valor esperado do tempo que um cliente fica no sistema, a eficiência dos atendentes etc. Os termos average são sinônimos com os termos estatísticos média ou valor esperado. O valor esperado de número e tempo também pode ser calculado para a fila de espera e para o atendimento.

Um sistema de filas é descrito basicamente por três características: Processo de chegada; Disciplina da fila: SIRO (atendimento em ordem randômica), FCFS (o primeiro a chegar é o primeiro a ser atendido), LCFS (o último a chegar é o primeiro a ser atendido pelo servidor) etc.; e Processo de atendimento.

FILA M/M/1

Fila M/M/1 é um modelo amplamente usado devido a suas distribuições de probabilidades que descrevem o processo de entrada e o processo de serviço de uma forma matemática simples.

Oferece um modelo mais realístico para sistemas de fila reais, pois os padrões de chegada de cliente em sistemas reais seguem uma distribuição de probabilidade de Poisson. Assim, as mensagens chegam com distribuição de Poisson, entram em um buffer infinito com uma distribuição de tempo de serviço exponencial e são manipuladas por um servidor na base primeiro a chegar primeiro a ser servido (FCFS – First Come First Served). Observe o esquema abaixo:

Figura 3: Esquema de uma fila M/M/1

Fonte: http://www.decom.fee.unicamp.br

As mensagens (jobs) que chegam ao buffer são armazenadas em fila e esperam pelo serviço de um único elemento de processamento (servidor único). As mensagens que chegam ao buffer podem vir de um grupo de fontes que são diretamente conectadas ao nó (fila de mensagens) ou elas podem vir de uma linha externa que é conectada a outro nó.

A fonte de mensagem pode ser finita ou infinita. Um sistema de fontes finitas não pode ter uma fila de serviço arbitrariamente longa, mas quanto maior for o número de fontes de mensagens maior será a taxa de chegada de mensagem. E em um sistema de fontes infinitas, o comprimento da fila de serviço é ilimitado, e a taxa de chegada de mensagem não é afetada pelo número de fontes.

Mensagens chegam no buffer a uma taxa de λ mensagens/segundo e possuem um comprimento de X unidades de dados (bits, bytes, caracteres, etc.). Assume-se que todas as mensagens possuem mesmo comprimento L. Além disso, funções em um nó são caracterizadas pela taxa de serviço e pela disciplina da fila.

Taxa de serviço = número de jobs deixando o nó por unidade de tempo de serviço. Taxa de serviço pode ser dependente da carga, isto é, pode depender do comprimento da fila.

Disciplina da fila = regra utilizada para determinar a ordem na qual os jobs enfileirados recebem o serviço.

Exemplo: fila de bancos, supermercados, etc.

Se uma mensagem chega e existem n mensagens a sua frente no buffer, então o tempo total T para processar essa mensagem consiste no tempo w gasto esperando na fila mais o tempo de processamento s:

Onde:

T: Tempo total de espera ou tempo de atraso.

μ = C/L: Taxa de serviço (mensagens/segundo).

Figura 4: Modelo de uma fila de servidor único.

Fonte: http://www.decom.fee.unicamp.br

REFERÊNCIAS

Disponível em: <www.paulonacaratti.eti.br/aluno/EPR/PO2_Notas_Aula.doc> Acesso em: 20/04/2014.

Disponível em: <www.uece.br/mpcomp/index.php/arquivos/doc.../175-dissertacao-16‎.pdf> Acesso em: 20/04/2014.

Disponível em: <www.lee.eng.uerj.br/~gil/filas/Filas.pdf> Acesso em: 20/04/2014.

Disponível em: <http://www.decom.fee.unicamp.br/~baldini/IE509/ParteIII.pdf> Acesso em: 22/04/2014.