TEORIA DAS FILAS – M/M/1

Teoria das Filas

A Teoria das Filas é um ramo da probabilidade que estuda o fenômeno da formação de filas de solicitantes de serviços fornecidos por um determinado recurso. Ela permite estimar importantes medidas de desempenho de um sistema a partir de propriedades mensuráveis das filas.

Dessa forma, pode-se dimensionar um determinado sistema segundo a demanda dos seus clientes, evitando desperdícios ou gargalos. Contudo, as filas apresentam comportamentos estocásticos (TEIXEIRA, 2004).

As filas aplicam-se em: Serviços de atendimento (bancos, restaurantes, servidores), fluxo de tráfego (pessoas, redes de comunicação, veículos) e escalonamento (processos, pacientes, tarefas industriais).

A Teoria das Filas tem como objetivo principal o desenvolvimento de modelos matemáticos que permitam prever o comportamento de sistemas de prestação de serviços (MARINS, 2011).

           

Características das Filas

ü  Processo de Chegada – Apresenta um comportamento aleatório;

ü  Distribuição dos Tempos de Serviço – São variáveis aleatórias independentes e identicamente distribuídas (IID);

ü  Número de Servidores – Número de posições de atendimento disponíveis no sistema;

ü  Capacidade do Sistema – Número máximo de clientes que podem permanecer no sistema;

ü  Tamanho da População – Número potencial de clientes que podem chegar a um sistema;

ü  Disciplina de Serviço – A ordem na qual os clientes são atendidos. Os tipos de disciplina de serviço mais conhecidos são:

 FIFO (first in, first out): primeiro a chegar é o primeiro a ser atendido;

Ÿ LIFO (last in, first out): último a chegar é o primeiro a ser atendido;

ŸAleatório: os atendimentos são feitos sem qualquer preocupação com a ordem chegada;

ŸCom Prioridade: os atendimentos são feitos de acordo com prioridades estabelecidas.

Elementos de uma Fila

ü Cliente: É todo o elemento que chega e requer atendimento. Os clientes podem ser: pessoas, máquinas, peças, carros estacionados, cartas que chegam e devem ser entregues, etc.

ü Canal de atendimento: Processo ou pessoa que realiza o atendimento do cliente. Para referir-se ao canal de atendimento é bastante comum a utilização do termo atendente.

Tipos de Fila

            Um sistema de fila pode ser dividido em cinco estruturas básicas de acordo com o seu plano de prestação de serviço.

ü Canal único, fase única: É o tipo mais simples de estrutura da fila de espera, e há fórmulas diretas disponíveis para solucionar o problema do comportamento-padrão da distribuição de chegadas e dos serviços.

ü Canal único, fases múltiplas: Um fator crítico no caso do canal único com séries de serviços é a quantidade de itens permitidos à frente de cada serviço, o que, por sua vez, constitui filas de espera separadas. Como exemplo, tem-se o sistema de lavagem de carros com uma série de serviços realizada em uma sequência uniforme.

ü Canais múltiplos, fase única: A dificuldade com esse formato consiste no fato de que os diferentes tempos de serviço dedicados a cada cliente resultam em velocidade e fluxo desigual entre as filas. Os caixas em um banco e os guichês nas lojas de departamentos são exemplos desse tipo de estrutura.

ü Canais múltiplos, fases múltiplas: Este caso é parecido com o anterior, porém difere-se ao fato de que dois ou mais serviços são realizados em sequência. Como exemplo tem-se a admissão de pacientes em um hospital, que segue este padrão, porque uma sequência específica de etapas é, geralmente, completada. Pois se vários servidores estejam disponíveis para o atendimento, poderá ser atendido mais de um paciente por vez.

ü Misto: Nesse tópico, consideram-se duas subcategorias: Estruturas múltiplas para canais únicos, onde encontram-se as filas que se unem em uma única fila para o serviço de fase única, quanto as filas que se juntam em uma para o serviço de fases múltiplas. E Estruturas de caminhos alternativos, onde encontram-se duas estruturas que diferem nas exigências de fluxo direcional (MORAES; SILVA e REZENDE, 2011).

Modelo Markoviano - M/M/1

Os modelos que permitem um estudo mais completo são os modelos denominados Markovianos, do tipo M/M/1, M/M/S e suas variações.

De acordo com Cuyabano e Jung (2009), uma fila M/M/1 é o modelo mais simples dentre os existentes em teoria de filas, no entanto, é um dos modelos mais estudados. Esse tipo de fila configura um processo de nascimento e morte, no qual as chegadas em um intervalo de tempo (0, T] seguem um processo de Poisson com taxa  λ, e os tempos de serviço, seguem uma distribuição exponencial de parâmetro μ, ou seja:

E as distribuições do tempo entre as chegadas e do tempo de serviço, respectivamente:

O processo de uma fila pode ser considerado também em dois estados: estado ocupado, quando o servidor estiver continuamente em atendimento, e o estado vazio, quando não houver clientes na fila.

Segundo Pereira (2009), o modelo M/M/1 corresponde ao modelo básico onde o sistema e contém um só servidor e a capacidade do sistema e da população são infinitas e a disciplina é a mais comum, correspondendo a quem entra primeiro no sistema ser o primeiro a ser atendido e a sair. Este pode ser representado também como M/M/1/∞/∞/F IF O ou M/M/1/∞/∞/F CF S. Um exemplo deste modelo pode ser de uma loja com um único balcão de atendimento.

            A probabilidade de chegar alguém e este, aguardar para ser servido é:

A probabilidade de não chegar ninguém e haver um serviço que foi completado é:

Ou seja, {X (t)} é um processo de vida e de morte com parâmetros λ e μ, respectivamente.

           Sabendo que o número médio de clientes no sistema (L_s) é, por definição, a média de todos os estados possíveis do sistema ponderado pelas respectivas probabilidades de ocorrência, temos que:

           A Figura abaixo ilustra os elementos importantes para a análise de um sistema de filas: população, processo de chegadas de clientes, organização da fila, disciplina de atendimento e processo de atendimento de clientes.

Referências

CUYABANO, Beatriz Castro Dias; JUNG, Karen Maria. Teoria de Filas. Disponível em: <file:///C:/Users/user/Documents/filas_final.pdf> Acesso em: 26/04/2014.

MARINS, Fernando Augusto Silva. Introdução à Pesquisa Operacional. Cultura Acadêmica. – São Paulo, 2011.

MORAES, Flávio Gomes de; SILVA Gecirlei Francisco da; REZENDE; Tacyanne Assis. Introdução à Teoria das Filas. Disponível em:  <http://www.sbm.org.br/docs/coloquios/CO-2.06.pdf> Acesso em: 26/04/2014.

PEREIRA, Cláudia Rossana Velosa. Uma Introdução às Filas de Espera. Disponível em:

<http://digituma.uma.pt/bitstream/10400.13/48/1/MestradoCl%C3%A1udiaPereira.pdf> Acesso em: 26/04/2014.

TEIXEIRA, Mário Meireles. Introdução à Teoria das Filas. Disponível em: <www.ceset.unicamp.br/~marlih/ST565/intro-filas.pdf> Acesso em: 26/04/2014.