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