Sistemas de Filas: Aula 3
Amedeo R. Odoni
17 de outubro de 2001
Roteiro da Apresentação
•
•
•
•
•
M/M/1: sistema com capacidade finita, K
M/M/m: sistema com capacidade finita, K
M/M/m: sistema com capacidade finita, K = m
Aspectos relacionados e extensões
Exemplo de sistema M/E2/1
• M/G/1: epochs e probabilidades de transição
• M/G/1: determinação de L
• Porque M/G/m, G/G/1, etc. são difíceis
M/M/1: sistema com capacidade finita, K; clientes
que encontram o sistema cheio são perdidos
λ
0
λ
1
µ
ρn (1 − ρ )
Pn =
1 − ρ K +1
…
2
µ
λ
λ
µ
λ
k -1
µ
k
µ
para n = 0, 1, 2, …, K
• Sistema sempre entra em equilíbrio
• Cuidado ao aplicar a lei de Little! Devem ser
considerados apenas os clientes que
efetivamente entram no sistema:
λ' = λ (1 − PK )
M/M/m: sistema com capacidade finita, K; clientes
que encontram o sistema cheio são perdidos
λ
0
λ
1
µ
λ
2
2µ
λ
λ
…
3µ mµ
m
λ
m +1
mµ
λ
…
mµ
λ
K -1
mµ
K
mµ
• É possível montar as equações de
equilíbrio e obter expressões exatas para
Pn, L, W, Lq, Wq
• De grande utilidade prática
M/M/m: sistema com capacidade finita, m;
caso especial!
λ
λ
0
1
µ
()
…
2
2µ
λ
λ
3µ
λ
m -1
(m - 1)µ
m
mµ
λ n
µ
Pn =
n!
m
∑
()
λ i
µ
para n = 0, 1, 2, …, m
i!
• Probabilidade do sistema cheio, Pm, é uma “equação de
perda de Erlang”
i=0
• Exatamente a mesma expressão obtida para Pn de um
sistema M/G/m com K = m
M/M/∞ (número infinito de servidores)
λ
0
λ
1
…
2
µ
2µ
n
λ
  ⋅e
µ

Pn =
n!
λ
λ
3µ
λ
m -1
(m –1)µ
λ
m
mµ
λ
m +1
(m + 1)µ
λ
− 
µ
para n = 0, 1, 2, …
• N segue uma distribuição de Poisson!
• L = λ/µ; W = 1/µ; Lq = 0; Wq = 0
• Várias aplicações
…
(m + 2)µ
Variações e extensões do processo de
nascimento e morte em sistemas de filas
• Grande número de extensões dos modelos já
apresentados
• Por exemplo: existem sistemas em que a taxa de
chegadas e de atendimentos dependem do estado do
sistema; para alguns deles, é possível obter expressões
analíticas exatas
• Sistemas que não constituem um processo de
renovação, mas que podem ser modelados como sendo
contínuos no tempo. Processos markovianos também
podem ser analisados
• A representação do estado é o aspecto de grande
importância (exemplo M/Ek/1)
M/G/1: aspectos gerais
• Chegadas Poissonianas, taxa λ
• Distribuição genérica para tempos de atendimento, S;
fS(s); E[S] = 1/µ; σS
• Fila com capacidade infinita
• O sistema NÃO caracteriza um processo contínuo de
Markov (na maior parte do tempo “ele tem memória”)
• É possível, entretanto, identificar instantes (“epochs”)
em que só precisamos saber qual o número de clientes
no sistema de forma a determinar a probabilidade de
que num próximo instante 0, 1, 2, …, n clientes estejam
no sistema
• “epoch”: instante imediatamente após o final de um
atendimento
M/G/1: Probabilidades de transição para os estados
do sistema nos instantes de fim de atendimento (1)
• N = número de clientes no sistema num “epoch”
aleatório, ou seja, logo após o fim de um
atendimento
• N’ = número de clientes no sistema no próximo
“epoch”, ou seja, no instante em que o próximo
atendimento é finalizado
• R = número de novos clientes chegando ao
sistema durante o atendimento do primeiro
cliente a ser atendido depois de um epoch
N’ = N + R -1 se N > 0
N’ = R
se N = 0
• Obs: certifique-se que você entendeu como R
foi definido
Epochs e o valor de R
N
Entre t1 e t2, R = 2
Entre t5 e t6, R = 0
t1
t2 t3 t4 t5
t6
t
M/G/1: Probabilidades de transição para os estados
do sistema nos instantes de fim de atendimento (2)
• As probabilidades de transição podem ser
expressas em função de probabilidades:
P[número de novas chegadas durante um
atendimento = r] =
αr = ∫
∞
0
(λt )
⋅ e − λt
⋅ f S (t ) ⋅ dt
r!
r
para r = 0, 1, 2, …
• Podemos então desenhar diagramas de
estado de transição representando os
instantes de finais de atendimentos
Uma observação importante
• As probabilidades P[N=n] de que n clientes
estejam no sistema num “epoch” aleatório são
iguais as probabilidades estacionárias, Pn, de
existirem n clientes no sistema num instante
aleatório qualquer
• Chegadas Poissonianas “vêem” tempos médios
• Podemos então usar os mesmos argumentos de
um sistema M/M/1 para obter:
P0 = 1 - λ/µ e E[B] = 1/(µ - λ)
• Podemos ainda obter expressões exatas para L,
W, Lq e Wq
Valores médios para um sistema M/G/1