ELEMENTOS DA TEORIA DAS FILASOSWALDO FADIGAS TORRES

"As teorias podem ser descritas em têrmos simples,ainda que se refiram a fenômenos que não pareçamsê-lo." - J. D. WILLIAMS

Com êste artigo, exposição simplificada da teoria das filas,pretendemos vir de encontro à necessidade de muitos ad-ministradores que, desejosos de estudar o assunto, dificil-mente encontram trabalhos em nossa língua versando demaneira acessível êsse importante tópico. '

Datando embora a teoria e suas aplicações de meio sé-culo, sua utilização tem sido ainda restrita no Brasil.Porém, com o desenvolvimento industrial, o crescimentodas emprêsas e a necessidade de racionalização que orase verifica, pode-se prever que, nos anos imediatos, vere-mos nossos administradores recorrerem com insistência aosconceitos e métodos da teoria das filas de espera nos se-tores de fabricação, manutenção, transporte, tráfego, co-municações, vendas e serviços em geral.

A teoria das filas de espera é um método estatístico quepermite estimar as demoras que ocorrem quando um ser-viço tem de ser proporcionado a clientes cuja chegada sedê ao acaso, como, por exemplo, fregueses que esperem

OSWALDOFADIGAS TÔRRES - Professor de Tempo Parcial, do Departamentode Métodos Quantitativos, da Escola de Administn3~o de Emprêsas. de SãoPaulo, da Fundação Getúlio Vargas. Livre-Docente e Profe~sor-Assistente dePlanejamento elEl l"r9dução da ESCOM Politócnica da Universidade: de S. Paulo,

112 ELEMENTOS DA TEORIA DAS FILAS R.A.E./20

para ser atendidos numa loja e automóveis que se con-gestionem num pôsto de pedágio.

Um dos primeiros trabalhos efetuados sôbre o tema foi ode A. K. ERLANG, em relação a circuitos telefônicos, paraa Companhia Telefônica de Copenhsgen, em 1908. A Se-gunda Grande Guerra deu forte impulso a aplicaçõesmilitares, verificando-se, terminada a conflagração, inúme-ras aplicações da teoria na área civil.

CONCEITO E CLASSIFICAÇÃO DAS FILAS

Em sua forma mais familiar uma fila é gerada quandounidades (clientes), chegando a um pôsto de serviço, nãopossam ser atendidas prontamente, tendo, ocasionalmente,que esperar para sê-lo. O grupo que espera é a fila; porém,êsse têrmo geralmente indica todos os clientes presentes,isto é, os que esperam e os que estejam sendo atendidos.

A estrutura básica do problema é bastante geral, de modoque muitas situações práticas, que aparentemente nãoconstituem filas, podem ser estudadas através da teoriadas filas.

Normalmente, a fila resulta da falta - deliberada ou não- de programação, pois, se fôsse possível organizar aschegadas e os serviços, seria também possível evitar com-pletamente a espera dos clientes e não haveria fila. Namaioria dos casos, porém, é impossível programar; assim,as filas, embora não desejadas, são inevitáveis.

O processo de fila é caracterizado por três elementos:1. Regime de chegada;

2. Regime de serviço; e

3. Disciplina da fila.

O regime de chegada inclui os seguintes elementos:

1 i E:specificaç@9dapopulação de clientes: finita PU ín-finita;..· .

R.A.E./20 ELEMENTOS DA TEORIA DAS FILAS 113

2. Distribuição da probabilidade do intervalo de tempoentre chegadas: essa distribuição pode ser estacioná-ria ou variável no tempo, pode depender do tamanhoda fila etc..

No regime de serviço existem três aspectos a ser consi-derados:

1. A disponibilidade do serviço: alguns sistemas só aten-dem durante um certo intervalo de tempo; outrosestão sempre disponíveis;

2. A capacidade do sistema, isto é, o número de clientesatendidos simultâneamente;

3. A duração do tempo de serviço de cada cliente, quepode ser constante ou aleatória, com distribuição deprobabilidade estacionária ou não, dependendo, inclu-sive, do tamanho da fila.

A disciplina da fila é o conjunto de regras que determi-nam a ordem em que os clientes são atendidos. Há váriaspossibilidades: atendimento pela ordem de chegada, aten-dimento aleatório, prioridade para certas categorias declientes etc ..

SISTEMAS ERGÓDICOS

A fila é um processo estocástico, isto é, seu estado numinstante t (número de clientes presentes, tamanho da fila,tempo de espera etc.) é variável aleatória. O estado dosistema é, realmente, um evento condicionado, cuja pro-babilidade no instante t depende do valor da probabili-dade no instante inicial to.

Em muitos casos, essa dependência do estado inicialdesaparece depois de certo tempo (mais precisamentequando t l!J»+ co ) isto é, o sistema atinge posição de equi-líbrio (regime permanente), em que as probabilidades nãodependem mai~ do estado inicial, nem do tempo decorrido,

114 ELEMENTOS DA TEORIA DAS FILAS R.A.E./20

Se a convergência ao limite é rápida, então, torna-se pos-sível usar essa solução-limite como aproximação para cal-cular a probabilidade dos diversos estados. Os sistemasque gozam dessa propriedade de as probabilidades tende-rem para uma situação de equilíbrio são denominadossistemas ergódicos.

CRITÉRIOS DE AVALIAÇÃO

Dependendo das circunstâncias, podemos avaliar o fun-cionamento de um sistema por diversos critérios:

1. Probabilidade de espera P(D) = P(T>O). Quandoo custo de uma demora no atendimento é grande, aescolha de um valor pequeno para P(D) pode ser ocritério adequado. Exemplo: problemas de estoque.

2. Probabilidade de espera maior que t, P(T>t). Êsseé o critério adequado se os clientes não toleram a es-pera por mais do que certo tempo. Exemplo: aviõesesperando para aterrissar.

3. Tempo médio de espera E[ T]. Êsse interessa quandoo conjunto de demoras - e não uma demora indivi-dual - é importante. Exemplo: tempo perdido numafábrica por máquinas paradas aguardando serviço.

4. Probabilidade de a fila ser maior do que um certovalor m: P(M>m). É importante quando devemosdeterminar a dimensão do espaço para acomodar afila. Exemplo: número de cadeiras na sala de esperade um consultório médico.

5. Tamanho médio da fila E[M]. Como o tempo totalgasto em espera por todos os clientes em conjunto éigual ao produto do número médio de clientes na filapelo tempo em que a fila existe, segue-se que o tama-nho médio da fila dá também a perda de tempo porunidade de tempo e, portanto; pode ser usado para

. .. avaliar Q tempo total perdido na..fila. Exemplo: tem..•

R.A.E./20 ELEMENTOS DA TEORIA DAS FILAS 115

po tatal perdido por empregados esperando na filapara serem atendidos no almoxarifado da emprêsa.

6. Perda de tempo. relativa. Em muitos casos, o crité-rio de avaliação é a perda de tempo relativa, definidacamo a relação entre o tempo de espera e o tempode serviço.

ESTUDO DE UM CASO SIMPLES

A maiar parte das situações de fila exige desenvolvimen-to matemático difícil, sendo preferível. nesse caso, usarmétodas de simulação, que discutiremas adiante. Paradar ao leitar idéia do tratamento matemático, analisare-mos sistema bastante simples, com chegadas segundo umadistribuição de Poisson de média st, um único pôsto deserviço. com distribuição expanencial dos tempos de aten-dimento de média 11ft e disciplina de atendimento pelaordem de chegada.

Sabemas que o que caracteriza as distribuições de Paissone a exponencial é a fato de, dado um intervalo de tempoAt suficientemente pequeno:

1. A probabilidade de uma chegada (ou de uma saídapor término de serviço) ser proparcional a At, isto é,será respectivamente ÀAt au f1.At.

2. A probabilidade de mais de uma chegada ou saída emAt ser desprezível. Em conseqüência, num intervalo Atsó podemos ter uma chegada, cam possibilidade ÀAt,ou nenhuma, com probabilidade 1- ÀAt. O mesmovale para os términos de serviço em At: ou terminaum serviço, com probabilidade f1.At, ou então. nenhum,com probabilidade 1- f1.At.

Nessas condições, a probabilidade de que existam n>Oclientes no sistema, no instante t+At, pode ser expressapela soma das probabilidades dos seguintes. eventos:

116 ELEMENTOS DA TEORIA DAS FILAS R.A.E./20

a) existem (n - 1) clientes no instante t, há umachegada no intervalo Át e não há término deserviço em Át;

b) existem n clientes no instante t e não há nemchegada nem saída no intervalo Át;

c) existem n clientes no instante t, há uma chega-da e uma saída no intervalo Át;

d) existem (n ] 1) clientes no instante t, não háchegada e há uma saída no intervalo =t,

Para o caso n = 0, basta considerar as duas situações se-guintes:

a) existem ° clientes no instante t e não há che-gada no intervalo Át;

b) existe 1 cliente no instante Át, não há chegadae há uma saída no intervalo Át.

Temos, portanto, indicando por P« ( t) a probabilidade dehaver n clientes no sistema no instante t:

Po(t+Át) = Po(t)( l-ÀÁt) + Pl(t) . /lÁt

P (t-j-At ) = P (t). ÀÁt . (l-/lÁt) +n n-l

+ P (t) (1 - ÀÁt)(1- /lÁt) + P (t ) . ÀÁt. I'Át+n n

+ P (t ) (1-ÀÁt) . I'Átn+ln>O

Pn(t+Át) - Pn(t)Calculando a expressão e fazendo Át

Áttender a zero, lembrando que, no equilíbrio, as probabi-

dPn(t)lidades não dependem de t e, portanto, a derivada ---

dté nula, temos,indicando por P« a probabilidade de equi-líbrio de haver n cítentes no sistema :'

R.À.E./ió ELEMENTOS DA TEORIA bAs FItAS 117

dPo(t)

dt

dPn(t)

dtn>O

Resolvendo por substituição sucessiva, temos:,

PI = -"-PoIL

Para obter P, lançamos mão da condição:

~P, = 1, e temos:11"-0

Po[ 1 + ( : ) + ( : ) 2+ ... + ( ~ ) 11+ ... ] = 1.

A expressão entre colchêtes é a soma de uma progressãogeométrica de razão À/IL, com infinitos têrmos. Para que

a soma seja .convergente devemos ter À < 1, o que éIL

evidente por considerações de ordem física, pois sendo À

o número médio de chegadas na unidade de tempo e sen-do IL o número médio de saídas (quando haja clientesno sistema) se À > IL, então haveria congestionamentocrescente.

Em virtude da importância da relação ( ~ ) :la recebe

nome e símbolo especiais: chama-se fator de utilização,ou intensidade de tráfego. Ela tem uma unidade própria:

i18 ELEMENTOS DA TEORlA DAs FItAS R.A.E./2Ô

I

é medida em "erlangs" (em homenagem a ERLANG, pio-neiro da teoria das filas). Utilizaremos a letra grega ppara indicar o fator de utilização, isto é:

Àp =-

p.

ÀVoltando à determinação de Ps, se p = - < 1 temos,

então:1

[1+p+p2 + ..... + pn + ... ] = (p<l)1 - p

e as probabilidades em regime permanente são:

P, = (1 - p)

P, = (1 - p )pn

Temos, também:00

A probabilidade em particular de o sistema estar ocupadoserá:

P(N)O) = P,

o que justifica a denominação "fator de utilização".

O sistema estará vazio durante percentagem do tempoigual a Ps, isto é (1 - p).

Conhecida a distribuição de probabilidade de N, podemoscalcular o número médio de clientes presentes no sistema:..

00

E[ N] = ~ nPn = ( 1- p) [p + 2p2 + 3p3 + .,. +npn] =O

=p(1- p) [1 + 2p + 3p2 + ... + npn-l + ... ]

R.A.c./20 ELEMENTOS DA TEORIA DAs FItAs 119

A expressão entre colchêtes é fàcilmente calculada obser-vando que é a derivada de [l +p+p2+ •.. + pn] e por-

1tanto vale ---

( 1-\fl)2·

Logo: o número médio de clientes no sistema é:

E(N)p= ---- = -----

1 - p

Para determinar o comprimento médio da fila, basta notarque se M é o número de clientes na fila, temos:

M

M

o se N

o se N

o1

M N-l se N>1.

Portanto, a distribuição de probabilidade de M é:

P(M = O) = (l .- p) + (1 - p) p = 1 p2

P (M = m) = (l - p) pffi+ 1 (m;?l)

o tamanho médio da fila é:

E[M] =~ m( l-I') pffi+l

1

(l - p) 1'2 [l + 2p + 3p2 + ... ]

E [M]1 - p

Êsse valor inclui as filas de tamanho zero. Em geral, inte-ressa-nos o tamanho médio da fila, quando há fila, isto é,E(MjM>O). Como P(M=O) = 1 - p2, segue-se que

120 ELEMENTOS DA TEORIA DAS FILAS R.À.E./20

P(M>O) = p2 e, portanto, o tamanho médio da fila(quando há fila) é:

1E(M[M>O)

1 - p À - p.

Distribuição dos Tempos

O tempo total V gasto por um cliente no sistema é asoma do tempo de espera W e do tempo de serviço S,isto é: V = W + S.

Vejamos, primeiramente, como se distribui o tempo deespera W. A probabilidade de um cliente não ter de es-perar (W = O) é a de encontrar o sistema vazio, isto é,P(W = O) = Po= 1 - P. Isso quer dizer que W temuma distribuição de probabilidade mista, pois é discreta(no ponto W = O) e tem uma parte contínua (regiãoW>O), com densidade de probabilidade f(W).

Para determinar f(W) observamos que o evento (esperade um cliente estar situado entre w e w + dw) é a com-posição, para n= 1até n = (X) dos eventos: (n elementosno sistema antes dêsse cliente chegar); [( n -. 1) serviçosno intervalo w]; (1 serviço em dw).

Temos, portanto:

P[w ::; W ::; w-l-dw] =(X) (/Lw)n-l e-/LW

~[(1- p) pn] [ 1 [iLdw]n=l (n - 1)!= f(w)dw.

Simplificando, temos:

(X) À~n-l

f(w) = (1 - p) e-/Lw ~ ---n=l (n-l)!

ou

R.A.E./20 ELEMENTOS DA TEORIA DAS FILAS 121

A

co A co -(p..-A)WEvidentemente !Of(W)dW = -;-!o (p..-A)e dw =

À

- = P, pois temos uma probabilidadep.

1 - P.P(W = O)

A distribuição dos tempos de espera condicionada a haverespera será:

f(wjW>O)f(w)

P(w>O) P

É, portanto, uma exponencial de parâmetro (p. - À) e po-demos escrever diretamente:

Tempo médio de espera (quando há espera)

E(WjW>O)1

Evidentemente, teremos:

Tempo médio de espera (incluindo o zero)

AE(W)

Para determinar a distribuição de probabilidade do tempototal V gasto no sistema por um cliente, basta lembrarque um segundo cliente, que chegue imediatamente depois

122 ELEMENTOS DA TEORIA DAS FILAS R.A.E./20

dêsse, irá demorar um tempo W = V para ser atendido;logo, a distribuição de V é a mesma de (W jW>O), isto é:

(exponencial)

Tempo médio Basto no sistema

1E(V)

p.-À

Probabilidade de um cliente ter de esperar mais queum tempo v:

Determinaremos a seguir os tempos médios de espera ede atendimento por outro método, utilizando a idéia defluxo médio no regime permanente.

Em média, chegam no sistema À clientes por unidade detempo; evidentemente, estando em equilíbrio, saem emmédia À = p.p, isto é, são atendidas em média p. pessoasdurante um intervalo p (fração de tempo em que o sistemaestá ocupado).

Como há em média E( N)p

l-p

À

-- clientes nop.-À

sistema, a demora média no sistema é:

E(N)E(V) = 1

À p.-À

E(M)O tempo médio na fila será E[W] = ---

À

À

R.A.E./20 ELEMENTOS DA TEORIA DAS FILAS 123

Êsse resultado também poderia ser obtido de E[ V]

= E[W] + E[S] ou E[W] = E[V] - E[S] =1 1

p.-À

Exemplo de Aplicação

Um almoxarifado recebe em média 12 pedidos por hora,com distribuição de Poisson. O encarregado pode atenderem média 20 pedidos por hora, tendo o tempo de atendi-mento distribuição exponencial. Calcular o tempo médioperdido na fila, o tempo médio gasto na fila por um ope-rário e a porcentagem de tempo em que o encarregadonão tem o que fazer.

Temos: À = 12/horaÀ

=- = 0,60./lo

Probabilidade de estar desocupado P. = 1 - pTamanho médio da fila, quando há fila:

I' = 20/hora p=

0,40.

1E[MjM>O] = -- = 2,5 homens.

1-p

Isso equivale a dizer que, em cada hora de trabalho dafábrica, há uma perda de tempo de 2,5 homens-horasna fila.

O tempo médio de espera é:

À 12E[W] = - = 0,075 h

p.(p.-À) 20(20-12)= 4,5 minutos.

O tempo médio de espera quando há fila é:

1 1E[WjW>O] = -- =- = 0,125 h = 7,5 minutos.

p.-À 8

124 ELEMENTOS DA TEORIA DA~ FILAS R.A.E./20

Êsse é também o tempo médio gasto no sistema.

E[V] = 0,125 h = 7,5 minutos.

SOLUÇÃO POR SIMULAÇÃO

Em casos complexos o estudo do comportamento dosistema pode ser feito por simulação. Para tal, devemosgerar aleatõriamente chegadas e serviços, de modo a re-produzir o funcionamento do sistema durante um períodode tempo suficientemente longo para que as médias cal-culadas sejam representativas do sistema em equilíbrio.

Para gerar eventos de uma distribuição aleatória utiliza-mos a curva das probabilidades ou freqüências acumu-ladas que, como sabemos, vai de zero a um. Sorteamosum número ao acaso (tirado de uma tabela de númeroseqüiprováveis, por exemplo) e o transformamos em por-centagem, de modo a ter sempre números entre zero e um.O valor da variável aleatória cuja probabilidade acumu-lada corresponder ao número sorteado será o valor esco-lhido para a simulação.

Para exemplificar, simularemos o funcionamento do sis-tema utilizado anteriormente como exemplo.

Obedecendo as chegadas a uma Poisson de média 12/horaou 0,20/minuto (Gráfico 1), sabemos que o intervaloentre duas chegadas consecutivas será uma exponencial

1de média -- = 5 minutos (Gráfico 2) cuja curva de

0,20probabilidades acumuladas tem a expressão: F(t) -= 1 - e~O.20t.

Para gerar intervalos de tempo desta distribuição podemosutilizar um gráfico ou uma tabela.

Assim, por exemplo, se o número sorteado na tabela denúmeros eqüiprováveis foi 768, procuramos na tabela ovalor de t mais próximo, por excesso, de 0,768, e encon-tramos t = 8 minutos, valor que utilizaremos como inter-valo para a próxima chegada.

R.A.E./20 ELEMENTOS DA TEORIA DAS FILAS 125

GRÁFICO 1: As chegadas obedecem GRÁFICO 2: O intervalo entre duasa uma distribuição de Poissott chegadas consecutivas obedece a uma

distribuição exponencial negativa

0,2

PROMBllID.4.0E e - 0.20 (0,201 x

P(,);---~-

0,3,I

0,1

° 0,1 0,2 0,3 O,, 0,5 0,6 0,7 0,8 0,9

NÚMERO DE CHEGADAS

0,4

0,3

0,2

0.1

° 5 1D 15 20 25 30TEMPO (MINUTOS)

De maneira idêntica simularemos os tempos de serviço,a partir da distribuição exponencial de média 3 minutos(20 atendimentos por hora), usando a tabela de F(s)= 1 - e-tl3•

TABELA DE 1 - e-I/5

t = Intervalo entre chegadas

It) II

It I P (T < t J P (T / t )

I II I

° I 0,000 23 I 0,9901 I 0,181 24 I 0,9922 I 0,330 25 I 0,9933 I 0,451 26 I 0,9944 I 0,551 27 I 0,9955 I 0,632 28 I 0,9966 I 0,699 29 I 0,9977 I 0,753 30 I 0,9988 I 0,798 31 I 0,9999 I 0,835 32 I 1.000

10 I 0,865 33 I 1.00011 I 0,88912 I 0,90913 I 0,92614 I 0,93915 I 0,95016 I 0,95917 I 0,96718 I 0,97319 I 0,97820 I 0,982

j21 I 0,98522 I 0,988

Tabela de 1 - e-I/3s = Duração do

serviço

Is I P (S s)

-- II

° I 0,0001 I 0,2842 I 0,4873 I 0,6324 I 0,7365 I 0,8126 I 0,8657 I 0,9038 I 0,9309 I 0,950

10 I 0,96411 , 0,97412 I 0,98213 I 0,98714 I 0,99115 I 0,99416 I 0,99517 I 0,99618 I 0,99719 I 0,99820 I 1.000

o

~o•..Q)

!3'::l.:08•..'<li.,.,IJUQ)

.:

.:°ã

OOOONNONO~~~NNMMOO~~~ ~•....•NNNNNNNNN li')N

N~V~OOVO~OOOOOOOOOOO~

I ~O~~~~MvvM~~N~~MOO~O~O~N~~V~~O~N~~~MV~Vll')lI')ww~~~~~~~~~~~~~~~~~~

NOOV~~~~MlI')VMOO~NlI')~MOO~OOONNMMVll')lI')O~NMMMMVVVll')oooooowoooooooooo~~~~~~~~~~~

NOOv~~V~~lI')~OO~~ONVll')"""MlI')00 NNNMvll')lI')lI')lI')Oo •....••....•""""""NNNoooooooooooooooooooooo~~~~~~~~~11

\I

\I

R.A.E./20 ELEMENTOS DA TEORIA DAS FILAS 127

CONCLUSÃO

Em contraste com a extensa literatura estrangeira exis-tente sôbre a teoria das filas, pouco se tem escrito emnosso País sôbre o assunto. A administração de emprêsasestá evoluindo rápidamente para fase de crescente utili-zação da metodologia quantitativa. O administrador en-frenta o desafio de ter que utilizar métodos especiais, quepressupõem conhecimentos matemáticos extensos e, àsvêzes, altamente avançados, sem possuir êsses conheci-mentos de base. Aos leitores ansiosos por se atualizar nasáreas da Pesquisa Operacional expusemos, neste artigo-limitando nossa apresentação aos casos mais simples - oessencial sôbre a teoria e a aplicação das filas de espera.

BIBLIOGRAFIA

D. R. Cox e W. L. SMITH,Queues, Nova Iorque: Wiley & Sons, 1961.

P. M. MORSE,Queues, Inventaries and Maintenance, Nova Iorque: Wiley& Sons, 1958.

M. SASIENJ,A. YASPANe L. FRIEDMAN,Operations Research, Nova Iorque:Wiley & Sons, 1959.

T. L. SAATY,Elemcnts 01 Queueing Theory, Nova Iorque: McGraw-HillBook Co., 1961.