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.
