Sistemas de Filas
Espacialmente Distribuídas
M/G/1
2 Servidores
N servidores
Aproximações
M/G/1
Direções
das viagens
(0,Y0)
YA
(0,0)
Ambulância
XA
(X0,0)
M/G/1
Direções
das viagens
(0,Y0)
YA
(0,0)
Ambulância
XA
(X0,0)
M/G/1
!A ambulância sempre retorna para a base
operacional em cada atendimento;
modelado como um sistema M/G/1 de filas
!Suponha porém um veículo de serviços
mecânicos emergenciais que se desloca
direto do local de atendimento de um
cliente para o local onde encontra-se o
próximo cliente… (?)
M/G/1
S1 , σS2 =
valor médio e variância, respectivamente, do 1o
tempo de atendimento num período em que o
servidor permanece ocupado
S2 , σS21 =
valor médio e variância, respectivamente, do 2o
tempo de atendimento e seguintes num período
em que o servidor permanece ocupado
1
λS2 < 1
ρ = 1 – P0 = porcentagem do tempo em que o servidor fica
ocupado
M/G/1
λ S1
ρ=
1 − λ (S2 − S1 )
2
1
2
2
2
1
σ + S + λ{S1(σ +S )−S 2(σ +S )
λ
L = ρ+
[
]
2(1− λ S2)
1− λ(S2 −S1 )
2
2
S1
2
S2
2
S1
M/G/1
Lei de Little: compre uma e leve outras
três de graça!
L = λW
Lq = λWq
Veja o livro, equações (5.0) – (5.5)
Sistema “Hipercubo” de
Filas com Dois Servidores
!Servidores diferenciados
!Diferentes cargas de trabalho (em função
da área atendida)
!Pode ter ou não filas
"Com fila – normalmente FCFS
"Sem fila – significa que provavelmente existe
um serviço alternativo (“backup”) para
atender os chamados quando todos os
servidores estão ocupados
A
B-A
B = “Setor de atendimento”
Chegadas Poissonianas de qualquer sub-setor A
λ(B-A)=λ2
A
B-A
λ(A)=λ1
B = “Setor de Atendimento”
λ = λ1+ λ2
Disciplina de atendimento
!O atendimento é feito preferencialmente
pelo “servidor principal”
!Caso contrário, o atendimento deve ser
feito por outro servidor, desde que
disponível
!Para quaisquer outros casos, o cliente
não é atendido, ou “perdido” (O que
acontece na prática?)
1,0
1,1
0,0
0,1
λ
1,0
λ2
1,1
µ
λ
µ
µ
λ1
0,0
0,1
µ
Equações de equilíbrio
λ
OK?
1,0
λ2
1,1
µ
λ
µ
µ
λ1
0,0
0,1
µ
OK?
Equações de equilíbrio
P00 (λ1 + λ2) = P01µ + P10µ
P01 (λ + µ) = P11µ + P00 λ1
Etc.
P00 + P10 + P01 + P11 = 1
Carga de trabalho (workload) e
desbalanceamento do sistema
!ρ1 = W1 = P01 + P11
!ρ2 = W2 = P10 + P11
!Desbalanceamento das cargas de trabalho:
∆W = |W1 - W2|
Para obter tempos de viagem,
devemos conhecer o padrão de
atendimento dos servidores
!fnj: porcentagem de despachos do servidor n
para atendimento no setor j
!Tn(C): tempo médio de viagem do servidor
n até o local de atendimento de um cliente
no setor C
!T(A): tempo médio de viagem para o sistema,
considerando que o setor A deve ser
atendido com prioridade pelo servidor
principal
Tempo médio de viagem
para todo o sistema
T(A)=f11T1(A) + f22T2(B-A)
+f12T1(B-A) + f21T2(A)
Tempo médio de viagem
para todo o sistema
T(A)=f11T1(A) + f22T2(B-A)
+f12T1(B-A) + f21T2(A)
Fila
Tempo médio de viagem
para todo o sistema
T(A)=f11T1(A) + f22T2(B-A)
+f12T1(B-A) + f21T2(A)
Geometria
Como obtemos os fnj’s?
! Considere um intervalo de tempo T de longa duração
! f12 =(no chamados que devem ser atendidos pelo servidor 1
no setor 2)/(no total de chamados atendidos)
! no total de chamados atendidos = (1 – P11)λT
! no total de chamados do servidor 1 no setor 2 é igual a
λ2TP10. Por que?
! Portanto, f12 =(λ2TP10 / [1 – P11]λT) = {λ2/(1 – P11)λ)}P10
Como este resultado pode ser
generalizado para N servidores?
Exemplo: cidade retangular
y
+1
x
-1
x=-0.25
x=0.75
Exemplo: cidade retangular
Setor de grande
demanda: carga de
trabalho = 50%
y
1-w
-1
x=-0.25
w
*
x=0.75
Limite para
igualdade dos tempos
de viagem
+1
x
Download

Sistemas de Filas Espacialmente Distribuídas