A Teoria das filas

Teoria das filas

A Teoria das Filas e a Teoria da Simulação são técnicas de planejamento que surgiram no início do século XX. Estudos que buscam dimensionar a quantidade de equipamentos e pessoas, o tamanho da área de armazenagem de produtos, o tamanho da área de espera por atendimento, o layout de equipamentos, podem ser realizados empregando tais teorias. A Teoria das Filas é um método analítico que trata o assunto através de equações matemáticas. A Teoria da Simulação é uma técnica que permite, a partir de um modelo do sistema do sistema real, realizar simulações em um computador de forma a reproduzir o comportamento do sistema sob condições pré-estabelecidas. A aplicação prática da primeira fica limitada a sistemas mais simples, enquanto que a segunda pode ser aplicada a sistemas complexos, permitindo inclusive a animação gráfica da operação do sistema.

Estas técnicas têm sido muito utilizadas nas mais diversas áreas, desde sistemas de manufatura, até a alocação de tarefas para serem processadas por um computador.

A figura abaixo ilustra os principais elementos de um sistema que pode ser representado empregando a Teoria das Filas. De uma certa população surgem clientes que entram no sistema e aguardam em uma fila para atendimento pelos operadores. Existe uma política de atendimento (disciplina da fila). Para este caso uma possibilidade é, o primeiro a chegar na fila é o primeiro a ser atendido. Também poderia ser estabelecida uma prioridade de atendimento para uma determinada categoria de clientes.

[pic 1]

Neste exemplo os termos clientes e operador de atendimento foram utilizados como sinônimos de entidades dinâmicas (transação) e entidades estáticas (servidores). Em um sistema de manufatura, as entidades dinâmicas poderiam ser peças a serem processadas em máquinas, estas últimas as entidades estáticas ou recursos. Sem perda de generalidade, mas para facilitar a notação, adotaremos na sequência os termos cliente e servidor em conformidade com a definição anterior.

Um estudo que emprega a Teoria das Filas busca essencialmente determinar um ponto de equilíbrio satisfatório de custo de operação do sistema. Em essência, há o custo de atendimento, que é determinado pelo número de servidores e o custo de manter os clientes em espera nas filas de atendimento. Em um sistema de manufatura clientes que aguardam por processamento correspondem a estoques intermediários aguardando por processamento. A quantidade de peças em estoque (número médio de clientes na filta) e o tempo que permanecem armazenadas (tempo médio na fila) podem ser traduzidos em custo de espera. O número de máquinas (número de servidores) e respectivos custos de operação/remuneração determinam o custo de atendimento. A Figura abaixo ilustra um comportamento típico para tais custos e o custo total obtido pela soma das duas parcelas.

[pic 2]

A população pode ser considerada infinita, se a chegada de um novo cliente no sistema não afeta o tamanho da população. Em caso contrário a população deve ser considerada finita. Por exemplo, a chegada de um cliente a uma agência bancária é irrelevante em relação ao total de clientes do banco. Por outro lado, a chegada de um caminhão de uma transportadora que possui apenas três veículos é significativa em relação ao tamanho da frota.

A análise de um sistema como o ilustrado requer a modelagem do mesmo. Para tanto é necessário representar adequadamente dois fenômenos essenciais. O processo de chegada de clientes no sistema e o processo de atendimento pelos servidores. Nesta análise considera-se uma aleatoriedade nos processos, e por isto os dois fenômenos devem ser representados por variáveis aleatórias que seguem uma determinada distribuição de probabilidade. Tais variáveis são denominadas variáveis de entrada.

O objetivo de análise de um sistema como este é determinar os parâmetros de performance do sistema, os quais podem ser denominados variáveis de saída. Como parâmetros de performance destacam-se: tamanhos (número de clientes) médio e máximo da fila, tempo médio de esperada na fila. O objetivo desta análise é dimensionar o sistema (número de servidores, área de espera) para prestar um bom atendimento para os clientes e para minimizar o custo de operação do sistema. A análise pode ser realizada para diferentes situações. Para a média de chegada de clientes, para o pico de chegada ou mesmo para um período de particular interesse.

O processo de chegada é representado por duas variáveis inter-relacionadas:

λ: número médio de chegada de clientes por unidade de tempo [cliente/s]

IC: intervalo médio entre chegadas de clientes consecutivos [s/cliente]

IC = 1/λ

Em geral o número médio de chegada de clientes por unidade de tempo é representado por uma distribuição discreta Poisson, cuja função probabilidade é dada pela equação abaixo. Na figura abaixo apresenta-se o histograma desta função para diversos valores de λ. Observa-se que à medida que o valor de λ cresce esta distribuição tende para uma distribuição normal.

[pic 3]

O intervalo médio entre chegadas de clientes consecutivos é então representado por uma distribuição exponencial (negativa), cuja função densidade de probabilidade é dada pela equação abaixo. Na figura abaixo apresenta-se o histograma desta função para diversos valores de λ.

f(x) = λ e(-λ x) 

F(x) = 1 - e(- λ x)  

λ= 1/IC

[pic 4]

Como regra geral, se o número médio de chegada de clientes por unidade de tempo é descrito por uma distribuição Poisson então intervalo médio entre chegadas de clientes consecutivos é descrito por uma distribuição exponencial. Ambas com o mesmo parâmetro λ.

O processo de atendimento é representado por duas variáveis inter-relacionadas:

μ : número médio de atendimentos por unidade de tempo [cliente/s]

TA : tempo médio de atendimento de clientes [s/cliente]

TA = 1/μ

Não há uma distribuição de probabilidades que seja válida para a representação do processo de atendimento como um caso geral. Um distribuição que tem sido muito utilizada é a distribuição de Erlang de grau "m" e valor médio μ, ela corresponde à soma de "m" variáveis aleatórias independentes distribuídas exponencialmente. Esta distribuição tem este nome em homenagem ao pioneiro na elaboração da Teoria das Filas. Quando "m=1" ela é idêntica à distribuição exponencial negativa, e conforme "m" aumenta ela tende a uma distribuição normal.