Cap17
70 pág.

Cap17


DisciplinaPlanejamento da Producao27 materiais264 seguidores
Pré-visualização31 páginas
de filas se baseia no processo de nascimento-e-morte, de modo que
o estado do sistema n represente o número de clientes no sistema de filas, as medidas de
desempenho fundamentais para o sistema de filas (L, Lq, W e Wq) podem ser obtidas ime-
diatamente após calcular os Pn das fórmulas anteriores. As definições de L e Lq dadas na
Seção 17.2 especificam que
L \ufffd \ufffd
\ufffd
n\ufffd0
nPn, Lq \ufffd \ufffd
\ufffd
n\ufffds
(n \ufffd s)Pn.
Além disso, as relações dadas no final da Seção 17.2 levam a
W \ufffd \ufffdL
\ufffd\ufffd
\ufffd, Wq \ufffd \ufffd
L
\ufffd\ufffd
q
\ufffd,
\ufffdn\ufffd1\ufffdn\ufffd2 \ufffd\ufffd\ufffd \ufffd0\ufffd\ufffd
\ufffdn\ufffdn\ufffd1 \ufffd\ufffd\ufffd \ufffd1
Estado:
0: P1 \ufffd \ufffd\ufffd
\ufffd0
1
\ufffdP0
1: P2 \ufffd \ufffd\ufffd
\ufffd1
2
\ufffdP1 \ufffd \ufffd\ufffd
1
2
\ufffd(\ufffd1P1 \ufffd \ufffd0P0) \ufffd \ufffd\ufffd
\ufffd1
2
\ufffdP1 \ufffd \ufffd\ufffd
\ufffd1
2
\ufffd
\ufffd
0
1
\ufffdP0
2: P3 \ufffd \ufffd\ufffd
\ufffd2
3
\ufffdP2 \ufffd \ufffd\ufffd
1
3
\ufffd(\ufffd2P2 \ufffd \ufffd1P1) \ufffd \ufffd\ufffd
\ufffd2
3
\ufffdP2 \ufffd \ufffd\ufffd
\ufffd
3
2
\ufffd
\ufffd1
2
\ufffd
\ufffd
0
1
\ufffdP0
\ufffd \ufffd
n \ufffd 1: Pn \ufffd \ufffd
\ufffd
\ufffd
n\ufffd
n
1\ufffdPn\ufffd1 \ufffd \ufffd\ufffd
1
n
\ufffd(\ufffdn\ufffd1Pn\ufffd1 \ufffd \ufffdn\ufffd2Pn\ufffd2) \ufffd \ufffd\ufffd\ufffd
n\ufffd
n
1\ufffdPn\ufffd1 \ufffd \ufffd
\ufffd
\ufffd
n\ufffd
n\ufffd
1\ufffd
n\ufffd
n\ufffd
1
2
\ufffd\ufffd
\ufffd
\ufffd
\ufffd\ufffd
\ufffd
\ufffd
1
0\ufffdP0
n: Pn\ufffd1 \ufffd \ufffd\ufffd
\ufffd
n\ufffd
n
1
\ufffdPn \ufffd \ufffd\ufffdn
1
\ufffd1
\ufffd(\ufffdnPn \ufffd \ufffdn\ufffd1Pn\ufffd1) \ufffd \ufffd\ufffd
\ufffd
n\ufffd
n
1
\ufffdPn \ufffd \ufffd\ufffd
\ufffd
n
n
\ufffd
\ufffdn
1
\ufffd
\ufffd
1
n
\ufffd
\ufffd
\ufffd
\ufffd
\ufffd
\ufffd
\ufffd
\ufffd
0
1
\ufffdP0
\ufffd \ufffd
Como cada uma das taxas médias \ufffd0, \ufffd1, . . . e \ufffd1, \ufffd2, . . . para o processo de nascimento-
e-morte pode receber qualquer valor não-negativo, temos grande flexibilidade na modela-
gem de um sistema de filas. Provavelmente os modelos mais usados na teoria das filas se
baseiam diretamente nesse processo. Em virtude das hipóteses 1 e 2 (e a Propriedade 4 para
a distribuição exponencial), diz-se que esses modelos possuem uma entrada de Poisson e
tempos de atendimento exponenciais. Os modelos diferem somente em suas hipóteses
sobre como \ufffdn e \ufffdn mudam com n. Apresentamos três desses modelos nesta seção para três
tipos importantes dos sistemas de filas.
Modelo M/M/s
Conforme descrito na Seção 17.2, o modelo M/M/s parte do pressuposto de que todos os
tempos entre atendimentos sejam distribuídos de forma independente e idêntica de acordo
com uma distribuição exponencial (isto é, o processo de entrada é de Poisson), que todos
os tempos de atendimento sejam distribuídos de forma independente e idêntica de acordo
com outra distribuição exponencial e que o número de atendentes seja s (qualquer inteiro
positivo). Conseqüentemente, esse modelo é simplesmente o caso especial do processo de
nascimento-e-morte em que a taxa média de chegada e a taxa média de atendimento por
atendente ocupado do sistema de filas são constantes (\ufffd e \ufffd, respectivamente) independen-
te do estado do sistema. Quando o sistema tem apenas um único atendente (s \ufffd 1), a impli-
cação é que os parâmetros para o processo de nascimento-e-morte são \ufffdn \ufffd \ufffd (n \ufffd 0, 1, 2,
. . .) e \ufffdn \ufffd \ufffd (n \ufffd 1, 2, . . .). O diagrama de taxas resultante é mostrado na Figura 17.5a.
17.6 MODELOS DE FILAS BASEADOS NO PROCESSO DE NASCIMENTO-E-MORTE 21
\u25a0 17.6 MODELOS DE FILAS BASEADOS NO PROCESSO DE 
NASCIMENTO-E-MORTE
em que \ufffd\ufffd é a taxa de chegada média a longo prazo. Como \ufffdn é a taxa média de chegada
enquanto o sistema se encontra no estado n (n \ufffd 0, 1, 2, . . .) e Pn é a proporção de tempo
de que o sistema se encontra nesse estado,
\ufffd\ufffd \ufffd \ufffd
\ufffd
n\ufffd0
\ufffdnPn.
Diversas das expressões dadas anteriormente envolvem somatórios com um número de
termos infinito. Felizmente, esses somatórios possuem soluções analíticas para um número
de interessantes casos especiais7, conforme visto na próxima seção. Caso contrário, eles
podem ser aproximados somando-se um número finito de termos via computador.
Esses resultados de estado estável foram obtidos sob a hipótese de que os parâmetros
\ufffdn e \ufffdn tenham valores tais que o processo possa realmente alcançar a condição de estado
estável. Essa hipótese sempre é válida se \ufffdn \ufffd 0 para algum valor de n maior que o estado
inicial, de modo que sejam possíveis somente um número de estados finito (aqueles menores
que esse n). Ela sempre é válida quando \ufffd e \ufffd são definidos (ver \u201cTerminologia e Notação\u201d
na Seção 17.2) e \ufffd \ufffd \ufffd/(s\ufffd) 	 1. Ela não é válida se \ufffd\ufffdn\ufffd1 Cn \ufffd\ufffd.
A Seção 17.6 descreve vários modelos de filas que são casos especiais do processo de
nascimento-e-morte. Portanto, os resultados de estado estável gerais que acabamos de dar
nos retângulos serão usados repetidamente para obter resultados de estado estável específi-
cos para esses modelos.
7 Essas soluções se baseiam nos seguintes resultados conhecidos para a soma de qualquer série geométrica:
\ufffd
N
n\ufffd0
xn \ufffd \ufffd
1
1
\ufffd
\ufffd
xN
x
\ufffd1
\ufffd, para qualquer x \ufffd 1,
\ufffd
\ufffd
n\ufffd0
xn \ufffd \ufffd1
1
\ufffdx
\ufffd, se \uf8e6x\uf8e6 	 1.
22 CAPÍTULO 17 TEORIA DAS FILAS
Entretanto, quando o sistema tem vários atendentes (s \ufffd 1), \ufffdn não pode ser expresso
dessa forma tão simples. Tenha em mente que \ufffdn representa a taxa média de términos de
atendimento para o sistema de filas global quando existem n clientes atualmente no sistema.
Quando a taxa média de atendimento por atendente ocupado for \ufffd, a taxa média de térmi-
nos de atendimento global para n atendentes ocupados deve ser n\ufffd. Portanto, \ufffdn \ufffd n\ufffd quan-
do n \ufffd s, ao passo que \ufffdn \ufffd s\ufffd quando n \ufffd s de modo que todos os s atendentes estejam
ocupados. O diagrama de taxas para esse caso é mostrado na Figura 17.5b.
Quando s\ufffd excede a taxa média de chegada \ufffd, isto é, quando
\ufffd \ufffd \ufffd
s
\ufffd
\ufffd
\ufffd 	1,
um sistema de filas que se ajusta a esse modelo vai, finalmente, atingir uma condição de
estado estável. Nessa situação, os resultados de estado estável obtidos na Seção 17.5 para o
processo de nascimento-e-morte geral são diretamente aplicáveis. Entretanto, esses resulta-
dos simplificam consideravelmente para esse modelo e levam a expressões de forma fecha-
da para Pn, L, Lq e assim por diante, conforme mostrado a seguir.
Resultados para o Caso com um Único Atendente (M/M/1). Para s \ufffd 1, os fato-
res Cn para o processo de nascimento-e-morte se reduz a 
Cn \ufffd \ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
n
\ufffd \ufffdn, para n \ufffd 0, 1, 2, . . . 
Portanto,
Pn \ufffd \ufffdnP0, para n \ufffd 0, 1, 2, . . . ,
em que
P0 \ufffd \ufffd\ufffd
\ufffd
n\ufffd0
\ufffdn\ufffd
\ufffd1
\ufffd \ufffd\ufffd1 \ufffd1 \ufffd\ufffd\ufffd
\ufffd1
\ufffd 1 \ufffd \ufffd.
0 1 2 n3 n \ufffd 2 n \ufffd 1 n \ufffd 1Estado: \u2026

 
 
\ufffd \ufffd \ufffd
\ufffd
\ufffd
\ufffd
0 1 2 s3 s \ufffd 2 s \ufffd 1 s \ufffd 1Estado: \u2026 \u2026

 
 
\ufffd 2\ufffd 3\ufffd
(s \ufffd 1)\ufffd
s\ufffd
s\ufffd
(a) Caso com um único atendente (s \ufffd 1)
(b) Caso com vários atendentes (s \ufffd 1)

n \ufffd 
, 
\ufffdn \ufffd \ufffd, 

n \ufffd 
,
 
\ufffdn \ufffd 
n\ufffd, 
s\ufffd, 
\u2026
para n \ufffd 0, 1, 2, ...
para n \ufffd 1, 2, ..., s
para n \ufffd s, s \ufffd 1, ...
para n \ufffd 0, 1, 2, ...
para n \ufffd 1, 2, ...
\u25a0 FIGURA 17.5
Diagramas de taxas para o
modelo M/M/s.
17.6 MODELOS DE FILAS BASEADOS NO PROCESSO DE NASCIMENTO-E-MORTE 23
Portanto,
Pn \ufffd (1 \ufffd \ufffd)\ufffdn, para n \ufffd 0, 1, 2, . . . .
Conseqüentemente,
L \ufffd \ufffd
\ufffd
n\ufffd0
n(1 \ufffd \ufffd)\ufffdn
\ufffd (1 \ufffd \ufffd)\ufffd \ufffd
\ufffd
n\ufffd0
\ufffdd
d
\ufffd
\ufffd (\ufffdn)
\ufffd (1 \ufffd \ufffd)\ufffd \ufffdd
d
\ufffd
\ufffd \ufffd\ufffd
\ufffd
n\ufffd0
\ufffdn\ufffd
\ufffd (1 \ufffd \ufffd)\ufffd \ufffdd
d
\ufffd
\ufffd \ufffd\ufffd1 \ufffd1 \ufffd\ufffd\ufffd
\ufffd \ufffd1 \ufffd
\ufffd
\ufffd
\ufffd \ufffd \ufffd
\ufffd \ufffd
\ufffd
\ufffd
\ufffd.
De forma similar,
Lq \ufffd \ufffd
\ufffd
n\ufffd1
(n \ufffd 1)Pn
\ufffd L \ufffd 1(1 \ufffd P0)
\ufffd \ufffd
\ufffd(\ufffd
\ufffd
\ufffd
2
\ufffd)\ufffd.
Quando \ufffd \ufffd \ufffd, de modo que a taxa média de chegada exceda a taxa média de atendi-
mento, a solução anterior \u201cestoura\u201d (pois o somatório para calcular P0 diverge). Para esse
caso, a fila \u201cexplodiria\u201d e cresceria sem limites. Se o sistema de filas iniciar operação sem
nenhum cliente presente, o atendente poderia ser bem-sucedido suportando os clientes que
chegam ao longo de um curto período, mas isso é impossível no longo prazo. Mesmo quan-
do \ufffd \ufffd \ufffd, o número de clientes esperado no sistema de filas cresce lentamente sem limites
ao longo do tempo, pois, embora um retorno temporário para nenhum cliente presente sem-
pre é possível, as probabilidades de números imensos de clientes presentes se torna signifi-
cativamente maior ao longo do tempo.
Supondo novamente que \ufffd 	 \ufffd, agora podemos obter a distribuição probabilística do
tempo de espera no sistema (portanto, incluindo tempo de atendimento) \ufffd para uma chega-
da aleatória quando a disciplina da fila é aquela na qual os primeiros que chegam serão os
primeiros a ser atendidos. Se essa chegada encontrar n clientes já no sistema, então a che-
gada terá de esperar ao longo dos n \ufffd 1 tempos de atendimento exponenciais, inclusive o
seu próprio. Para o cliente que está sendo atendido no momento, relembre-se da proprieda-
de de falta de memória para a distribuição exponencial discutida na Seção