Results

Um dos primeiros estudos de filas foi apresentado por Erlang em 1917 na área de telefonia. Após este estudo, muitos outros têm sido realizados em diversas áreas e vêm sendo amplamente utilizados na análise de desempenho de sistemas complexos, tais como rede de computadores, sistemas de comunicação e de produção; ver, por exemplo, Kleinrock (1975, 1976), Disney e Konig (1985), Suri et al. (1993) e Whitt (1995). A teoria de filas estuda as relações entre as demandas em um sistema e os atrasos sofridos pelos usuários do mesmo, auxiliando no projeto e operação de sistemas para encontrar um balanceamento adequado entre o custo de oferecer serviços no sistema e os custos dos atrasos sofridos pelos usuários do sistema (ARENALES et al., 2007).

Um sistema de filas é aquele em que algum produto flui, movimenta, ou é transferido através de um ou mais canais de capacidade finita para ir de um ponto para outro (GROSS; HARRIS, 1998; KLEINROCK, 1975). Outros denominam esses sistemas por rede de filas e os descrevem como uma rede de centros de serviço, que representam os recursos do sistema, e clientes, que representam os usuários (LAZOWSKA et al., 1984). Esses centros de serviços são compostos por estações (nós) e cada estação pode ser composta de um único servidor ou de vários servidores. Essas estações são caracterizadas por clientes chegando para um determinado serviço (processo de chegada), clientes sendo atendidos (processo de serviço) e clientes esperando por serviço quando necessário (fila de espera). A Figura 4 mostra um exemplo de uma estação com servidores idênticos e fila única.

O processo de chegada é descrito pelo intervalo de tempo entre chegadas de sucessivos clientes ao sistema (ARENALES et al, 2007). Já o processo de serviço ocorre em cada estação e é descrito pelo tempo de processamento do cliente. Os processos de chegada e serviço podem ser determinísticos ou probabilísticos. Entretanto, em modelos de filas em geral pelo menos o processo de chegada ou o processo de serviço são probabilísticos, resultando numa fila de espera (BITRAN; MORABITO, 1995). Esses processos podem ser

descritos por diferentes distribuições de probabilidade, como a exponencial ou markoviana (M) ou a genérica (G).

Figura 4 – Estação com servidores idênticos e fila única

A fila de espera pode ter capacidade limitada ou ilimitada, que é geralmente determinada pelo espaço físico disponível (BITRAN; MORABITO, 1996). A fila tem uma disciplina ou regra que descreve a ordem em que os clientes são retirados da fila e o atendimento é iniciado (KLEINROCK, 1975). Arenales et al. (2007) citam como exemplos de disciplina: primeiro-a-chegar primeiro-a-ser-servido (first-come first-served – FCFS), último- a-chegar primeiro-a-ser-servido (last-come first-served – LCFS), fila com prioridades e aleatório (service in random order – SIRO).

Muitas medidas de desempenho de um sistema de filas podem ser obtidas, tais como tempo de espera por cliente, número de clientes no sistema, duração do período ocioso e ocupado do servidor (KLEINROCK, 1975). Vale ressaltar também que as medidas de desempenho de interesse variam de sistema para sistema e podem ser obtidas de acordo com os objetivos do gestor do sistema.

Ainda em relação à Teoria de Filas, alguns conceitos e modelos utilizados nesse estudo são apresentados. A Lei de Little é utilizada nos Sistemas de Manutenção e Borracharia, os Modelos M/M/m e M/G/m no Sistema da Borracharia e os Modelos com Múltiplas Classes de Usuários e M/M/m/C no Sistema de Manutenção.

3.1.1 Fórmula de Little

Pela Lei de Little, em condições de equilíbrio, o número médio de usuários num sistema de filas é igual à taxa média a qual estes chegam multiplicada pelo tempo médio que um usuário gasta no sistema (LITTLE; GRAVES, 2008), conforme Equação (1). Nessa equação, L representa o número médio de usuários em um sistema de filas, W o tempo médio

Fila de espera Processo de chegada Processo de serviço ... . . . Saída do sistema Fila de espera Processo de chegada Processo de serviço ... . . . . . . Saída do sistema

que um usuário permanece no sistema e _{𝜆 o número médio de usuários que chegam ao} sistema por unidade de tempo. A fórmula de Little também pode ser aplicada para analisar as medidas relacionadas com a fila de espera. Nesse caso, tem-se a Equação (2), onde _𝐿𝑞 representa o número médio de usuários em filas e _𝑊𝑞 o tempo médio de um usuário na fila.

𝐿 = 𝜆𝑊 (1)

𝐿𝑞= 𝜆𝑊𝑞 (2)

A fórmula de Little pode ser aplicada independente da disciplina da fila (KLEINROCK, 1976; LARSON; ODONI, 1981), do número de servidores, dos processos de chegada e serviço e também quando são utilizadas classes de usuários com diferentes prioridades (ARENALES et al, 2007).

3.1.2 Filas com capacidade ilimitada: os modelos M/M/m e M/G/m

Os modelos de filas são geralmente representados utilizando a notação de Kendall (KENDALL, 1953). Em muitos casos, é utilizada apenas a notação condensada (ex.

M/M/m e M/G/m) e assume-se que, da esquerda para a direita, tem-se a distribuição dos intervalos entre chegadas, distribuição dos tempos de serviço e número de servidores. Nessa notação, fica implícito que a disciplina dessa fila é FCFS (First Come First Served), que a fila tem capacidade ilimitada (infinita) e que o tamanho da população de origem é ilimitado (infinito).

No modelo M/M/m, tanto os intervalos entre chegadas quanto dos tempos de serviço são exponencialmente distribuídos. Nesses modelos, a chegada de usuários acontece de forma totalmente aleatória, ou seja, a chegada de um usuário não é influenciada pelo instante atual ou pelo intervalo decorrido desde a última chegada ou término de serviço e são descritos pela distribuição exponencial (ARENALES et al., 2007). Quanto ao atendimento, assume-se m servidores idênticos e em paralelo e a existência de uma única fila de espera. A distribuição de equilíbrio deste modelo é dada por (3), onde, para _{𝜌 < 1,}

𝑃0 = _∑ (𝜌𝑚)𝑛1 𝑛! +(𝜌𝑚)𝑚𝑚! (1−𝜌1 ) 𝑚−1 𝑛=0 . 𝑃𝑛= { (𝜌𝑚)𝑛 𝑛! 𝑃0, 𝑛 = 1, 2, … . , 𝑚 − 1 𝜌𝑛_𝑚𝑚 𝑚! 𝑃0, 𝑛 = 𝑚, 𝑚 + 1, … . . (3)

O número de usuários no sistema (L) e na fila (𝐿𝑞) pode ser obtido através das

Equações (4) e (5). Já os tempos médios no sistema (_{𝑊) e em fila (𝑊𝑞}) podem ser obtidos pelas Equações (4) e (5) e pela Fórmula de Little (Equações (1) e (2)).

𝐿 = 𝐿𝑠+ 𝐿𝑞 (4)

𝐿 = 𝜌𝑚 +_{𝑚! (1 − 𝜌)}(𝜌𝑚)𝑚𝜌₂𝑃0 (5)

O modelo M/G/m difere do modelo M/M/m uma vez que a distribuição do tempo de serviço não é exponencial. Usa-se a letra G para representar uma distribuição genérica. Em geral, de acordo com Arenales et al. (2007), sistemas que não podem ser descritos por distribuições exponenciais são mais complexos e difíceis de analisar. Existem poucos resultados desenvolvidos para modelos M/G/m e, em função disso, serão utilizadas aproximações desenvolvidas para o modelo G/G/m, uma vez que o M/G/m é um caso particular do modelo G/G/m. Segundo Kleinrock (1976), filas G/G/m são pouco conhecidas e os resultados disponíveis para aproximar seu comportamento são extremamente úteis e a maioria dos trabalhos têm se dedicado a limitar a espera média.

A fórmula de Kraemer e Lagenbach-Belz é uma aproximação para calcular o número médio de usuários (L) em sistemas G/G/m e é dada por (6) (ARENALES et al., 2007; GALVÃO; MORABITO, 2008). Nessa expressão, calcula-se o número de clientes em fila para um sistema M/M/m (_{𝐿𝑞 𝑀/𝑀/𝑚}), o coeficiente _𝐶𝑥2 ₌ 𝑉(𝑋)

𝐸(𝑋)2, onde 𝑉(𝑋) representa a

variância do intervalo de tempo entre as chegadas X e _𝐸(𝑋)2 a esperança do quadrado do intervalo de tempo entre as chegadas X e o coeficiente _𝐶𝑠2 ₌ 𝑉(𝑆)

𝐸(𝑆)2, onde 𝑉(𝑆) representa a

variância do tempo de serviço S e _𝐸(𝑆)2 a esperança do quadrado do tempo de serviço S. Ainda segundo Arenales et al. (2007), essa expressão é exata quando _𝐶𝑥2 _{= 1 e 𝐶𝑆}2 _{= 1 ou} quando _{𝜌 → 1.}

𝐿 ≈ 𝜌𝑚 +(𝐶𝑥2+ 𝐶₂ 𝑠2)𝐿𝑞 𝑀/𝑀/𝑚 (6)

As medidas de desempenho _{𝑊e 𝑊𝑞} também podem ser obtidas através da Fórmula de Little (Equações (1) e (2)).

Em alguns casos, pode ser necessário limitar o tamanho da fila de espera em função do espaço físico disponível (BITRAN; MORABITO, 1996) ou apenas para garantir a agilidade do atendimento caso exista um sistema backup disponível para atender os chamados.

O modelo M/M/m/C difere do modelo M/M/m apenas em função da capacidade do sistema ser limitada a C unidades. A distribuição de equilíbrio deste modelo é dada por (7).

𝑃𝑛= { (𝜌𝑚)𝑛 𝑛! 𝑃0, 𝑛 = 1, 2, … . , 𝑚 − 1 𝜌𝑛_𝑚𝑚 𝑚! 𝑃0, 𝑛 = 𝑚, 𝑚 + 1, … . , 𝑘 (7) Onde, 𝑃0= { 1 ∑𝑚−1𝑛=0(𝜌𝑚)𝑛_𝑛! +(𝜌𝑚)𝑚_𝑚! (1−𝜌𝑘−𝑚+1_1−𝜌 ) , 𝜌 ≠ 1 1 ∑𝑚−1(𝜌𝑚)𝑛_𝑛! +(𝜌𝑚)𝑚_𝑚! (𝐾−𝑚+1) 𝑛=0 , 𝜌 = 1

O número de usuários na fila (_𝐿𝑞) e no sistema (L) pode ser obtido através das Equações (8) e (9). Já os tempos médios no sistema (_{𝑊) e em fila (𝑊𝑞}) podem ser obtidos pelas Equações (8) e (9) e pela Fórmula de Little.

𝐿𝑞= { (𝜌𝑚)𝑚_𝜌 𝑚! (1 − 𝜌)2(1 − 𝜌𝐾−𝑚+1− (𝐾 − 𝑚 + 1)𝜌𝑘−𝑚(1 − 𝜌))𝑃0, 𝜌 ≠ 1 (𝜌𝑚)𝑚_{(𝐾 − 𝑚)(𝐾 − 𝑚 + 1)} 2𝑚! 𝑃0, 𝜌 = 1 (8) 𝐿 = 𝐿𝑠+ 𝐿𝑞= 𝜌𝑚 + 𝐿𝑞 (9)

Entretanto, deve-se atentar ao aplicar a Fórmula de Little que é necessário calcular a taxa de entrada de usuários no sistema (𝜆̅), uma vez que quando o usuário encontra o sistema cheio ele não entrará. Essa taxa pode ser obtida através da Equação (10), onde _{𝑃𝑙𝑜𝑠𝑠} é a probabilidade de perda de usuários.

𝜆̅ = 𝜆(1 − 𝑃𝑙𝑜𝑠𝑠) (10)

3.1.4 Modelos de Filas com múltiplas classes de usuários

Em alguns sistemas faz-se necessário separar os usuários em múltiplas classes e atribuir prioridades no atendimento em determinadas classes. Por exemplo, num sistema com três classes de usuários, a classe 1 tem prioridade em relação às classes 2 e 3 e a classe 2, por sua vez, tem prioridade em relação à classe 3. Nesse caso, ao finalizar o atendimento, o próximo usuário a ser atendido é o da classe de maior prioridade e quando existem mais de um usuário dessa classe aguardando a escolha acontece segundo a disciplina da fila

(ARENALES et al., 2007), uma vez que, de acordo com Larson e Odoni (1981), as classes de usuário podem utilizar diferentes disciplinas da fila.

No caso de filas com prioridades, tem-se o caso preemptivo e o não- preemptivo (BITRAN; MORABITO, 1995; LARSON; ODONI, 1981). No caso preemptivo, o cliente com maior prioridade entra em serviço assim que chegar à fila, mesmo que outro cliente com menor prioridade já esteja em serviço. No caso não-preemptivo, um cliente já iniciado não pode ser interrompido enquanto não for completado.

No modelo Mi/M/m sem interrupção, os usuários são divididos em i classes e

admite-se que os processos de chegada e serviço sejam descritos por distribuições exponenciais. Nesse caso, para _{𝜌 < 1, o tempo médio de espera em fila da classe k (𝑊𝑞𝑘}) pode ser obtido pela Equação (11). E, quando r = 1, a expressão do _𝑊𝑞𝑘 se reduz ao tempo médio de espera em fila em um sistema M/M/m (ARENALES et al., 2007).

𝑊𝑞𝑘=

(𝜌𝑚)𝑚_𝜌 𝑚𝜇(1 − 𝜌)𝑚! 𝑃0

(1 − ∑𝑘−1𝑖=1𝜌𝑖)(1 − ∑ 𝜌𝑘𝑖=1 𝑖), 𝑘 = 1, 2, . . . , 𝑟

(11)

As medidas de desempenho número médio de usuários na fila (_𝐿𝑞𝑘), no sistema (𝐿), em atendimento (𝐿𝑠) e tempo no sistema (𝑊) podem ser obtidas através da Fórmula de

Little (Equações (1) e (2)) e da relação (12).

𝐿 = 𝐿𝑠+ ∑ 𝐿𝑞𝑘 𝑘 𝑖=1

(12)