t2-gab

Prévia do material em texto

T2 - MAB515 - 2012-2
22 de janeiro de 2013
70 pontos
Aluno: GABARITO (revisto) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Questa˜o 1 (20 pontos) Seja da uma fila com prioridades com duas classes, sendo a classe 1 a mais
priorita´ria, servida com disciplina LCFS com interrupc¸a˜o na pr´opria classe. A classe 1 interrompe a
classe 2. A classe 2 e´ servida FCFS.
a) (5) Calcule o tempo me´dio de espera para a classe 1 e a condic¸a˜o de estabilidade para esta classe.
Indique se a soluc¸a˜o e´ exata ou aproximada.
b) (5) Calcule o tempo me´dio de espera para a classe 2 e a condic¸a˜o de estabilidade para esta classe.
Indique se a soluc¸a˜o e´ exata ou aproximada.
Assuma agora que a classe 1 na˜o interrompa a classe 2. As disciplinas continuam as mesmas.
c) (5) Qual o novo tempo me´dio de espera para a classe 1 neste caso? Exato ou aproximado?
d) (5) Qual o novo tempo de espera para a classe 2 neste caso? Exato ou aproximado?
Soluc¸a˜o: Como as duas classes sofrem interrupc¸a˜o, temos que calcular primeiramente o tempo me´dio no
sistema para depois obter o tempo me´dio de espera na fila de cada classe.
a) (5)
E[T01] = E[X1]
E[T1] =
E[X1]
1− ρ1 , ρ1 < 1
E[W1] = E[T1]− E[X1] = ρ1E[X1]
1− ρ1 , ρ1 < 1
Soluc¸a˜o exata, pois todos que chegam depois da classe 1 sa˜o certamente servidos primeiro. b) (5)
ρE[Xr] = ρ1E[X1r] + ρ2E[X2r]
E[T02] = E[Nq1]E[X1] + ρ1E[X1r] + E[Nq2]E[X2] + ρ2E[X2r] + E[X2]
= ρ1E[W1] + ρ2E[W2] + ρE[Xr] + E[X2]
= ρ1E[W1] + ρ2E[T2] + ρE[Xr] + E[X2](1− ρ2)
E[T2] =
ρ1E[W1] + ρ2E[T2] + ρE[Xr] + E[X2](1− ρ2)
1− ρ1
=
ρ1E[W1] + ρE[Xr] + E[X2](1− ρ2)
1− (ρ1 + ρ2) , ρ1 + ρ2 < 1
E[W2] = E[T2]− E[X2] = ρ1E[W1] + ρE[Xr] + E[X2]ρ1
1− (ρ1 + ρ2) , ρ1 + ρ2 < 1
Soluc¸a˜o exata, pois todos que chegam depois da classe 1 sa˜o certamente servidos primeiro, pois ha´ interrupc¸a˜o
da classe 1 sobre a classe 2. Como a classe 2 e´ FCFS, o fregueˆs desta classe encontrado em servic¸o que for
interrompido pela chegada da classe 1 retornara´ a ser servido, enquanto o fregues t´ıpico da classe 2 ainda
estiver na fila de espera. O fato de haver ou na˜o interrupc¸a˜o da classe 2 pela classe 1 na˜o configura uma
soluc¸a˜o ser exata ou aproximada
1
c) (5) Continua a haver interrupc¸a˜o na classe 1, exceto que agora a classe 2 encontrada em servic¸o
interfere.
E[T01] = ρ2E[X2r] + E[X1]
E[T1] =
ρ2E[X2r] + E[X1]
1− ρ1 , ρ1 < 1
E[W1] = E[T1]− E[X1] = ρ2E[X2r] + ρ1E[X1]
1− ρ1 , ρ1 < 1
A soluc¸a˜o e´ exata pois o fregueˆs da classe 2 encontrado em servic¸o ira´ ate´ o final e todos que chegam depois
da classe 1 sa˜o servidos primeiro.
d) (5) Como agora na˜o ha´ interrupc¸a˜o da classe 1 sobre a classe 2 e ela e´ FCFS, enta˜o o fregueˆs da
classe 2 encontrado em servic¸o vai ate´ o final. Temos que calcular o tempo me´dio de espera para esta classe.
E[W02] = E[Nq1]E[X1] + ρ1E[X1r] + E[Nq2]E[X2] + ρ2E[X2r]
= ρ1E[W1] + ρ2E[W2] + ρE[Xr]
E[W2] =
ρ1E[W1] + ρ2E[W2] + ρE[Xr]
1− ρ1
=
ρ1E[W1] + ρE[Xr]
1− (ρ1 + ρ2) , ρ1 + ρ2 < 1
Soluc¸a˜o exata, pois todos que chegam depois da classe 1 enquanto o fregueˆs t´ıpico da classe 2 esta´ em espera
sa˜o certamente servidos primeiro, pois a classe 1 tem prioridade sobre a classe 2. .
Questa˜o 2 (15 pontos) Veja a rede de filas com sevidores exponenciais na figura abaixo.
a) (5) Sabendo que λ = µ/2, calcule o tempo me´dio gasto neste sistema.
b) (5) Se a taxa de entrada for sendo incrementada, qual fila entrara´ em gargalo (instabilidade) primeiro
e para qual taxa λ∗ isso acontecera´?
c) (5) Com esta fila em gargalo, qual a situac¸a˜o da outra fila em em termos de utilizac¸a˜o? Se a taxa
continua a aumentar, para qual valor a segunda fila entrara´ em instabilidade?
Soluc¸a˜o: a) (5) 0, 4λ2 = λ⇒ λ2 = 5λ2 = 5µ4 e ρ2 = 5λ4µ = 58 = 0, 625.
λ2 = 0, 4λ2 + λ1 ⇒ λ1 = 3λ2 = 3µ4 e ρ1 = 3λ2µ = 34 = 0, 75.
E[N1] =
ρ1
1−ρ1 = 3 e E[N2] =
ρ2
1−ρ2 = 5/3.
E[T ] = E[N1]+E[N2]λ (por Little), resultando em E[T ] =
28
3µ .
b) (5) Como ρ1 > ρ2, a fila 1 entrara´ em instabilidade primeiro para ρ1 = 1 =
3λ∗
2µ ⇒ λ∗ = 2µ3 . A fila 2
ficara´ operando com ρ2 =
5λ∗
4µ =
5
6 .
c) (5) Estando a fila 1 em gargalo, a sa´ıda dela sera´ uma taxa exponencial µ constante, independente
da entrada aumentar mais ou na˜o. A taxa de entrada na fila 2 ficara´ sendo λ∗2 = 0, 4λ
∗
2 + µ ⇒ λ∗2 = 5µ3 e
2
a utilizac¸a˜o ficara´ constante e igual a ρ2 =
λ∗2
2µ =
5
6 , independente da entrada λ. Esta utilizac¸a˜o e´ o valor
atingido quando a fila 1 entrou em gargalo.
Questa˜o 3 (35 pontos) Seja dada a seguinte fila FCFS, onde chegadas externas ocorrem segundo um
fluxo Poisson com taxa λ e o servic¸o Y e´ geral, com Y ∗(s) conhecido. Apo´s passar pelo servidor, com
probabilidade p a pessoa retorna novamente para o in´ıcio da fila e com probabilidade 1 − p a pessoa deixa
o sistema. Seja X o total de servic¸o recebido por uma pessoa no sistema, apo´s todas as visitas L que fez
ao servidor. Use L(z) como a T.Z do nu´mero de visitas ao servidor. Seja K o nu´mero de chegadas Poisson
durante um servic¸o Y . Seja N o nu´mero de pessoas no sistema. Use estas varia´veis e na˜o outras. Na figura,
β representa a taxa em pessoas/s deixando o servidor, que tera´ que ser calculada.
Fo´rmulas de M/G/1: N(z) = P (N = 0)X
∗(λ−λz)(1−z)
X∗(λ−λz)−z
a) (5) Calcule β e o nu´mero me´dio de pessoas no servidor, para esta fila, em func¸a˜o de λ e p.
b) (5) Calcule L(z) e obtenha X∗(s) em func¸a˜o de L(z). Mostre que X∗(s) = Y
∗(s)(1−p)
1−Y ∗(s)p . Lembrete: a
cada visita ao servidor, a pessoa recebe Y de servic¸o e a pessoa faz L visitas. Este X∗(s) pode ser u´til em
outro item.
c) (5) Usando o conceito de cadeia embutida nos instantes de partida do servidor, mostre que
N(z) = P (N = 0)
K(z)(1− p)(z − 1)
z −K(z)(1− p+ pz) , com K(z) = Y
∗(λ− λz)
.
d) (5) A partir de N(z), calcule P (N = 0). Embora seja poss´ıvel se chegar a esta probabilidade sem uso
da T.Z., quero que voceˆ use a transformada para comprovar a resposta.
e) (5) Obtenha E[T ], o tempo me´dio gasto no sistema (desde o instante de chegada ate´ deixar o sistema,
apo´s va´rias passadas eventuais pelo servidor).
f) (5) Assumindo agora que o retorno ocorre direto ao servic¸o, a pessoa recebendo um novo servic¸o com
probabilidade p de imediato, temos uma fila regular M/G/1. Usando as fo´rmulas de M/G/1, calcule o N(z)
para este caso e mostre que ele e´ igual ao do item (c). Logo, ambos os sistemas teˆm tempos me´dios iguais e
E[T ] poderia ser obtido pelas fo´rmulas de M/G/1.
g) (5) E as variaˆncias dos tempos no sistema, que dependem das tranformadas T ∗(s) e W ∗(s), seriam
iguais tambe´m? Voceˆ acha poderia deduzir estas transformadas a partir de N(z)? Comente e justifique
sua resposta com argumentos va´lidos. Sua resposta depende apenas de uma ana´lise cuidadosa da fila, dos
eventos envolvidos e da te´cnica que foi empregada.
Soluca˜o: a) (5) β = βp+ λ. Logo, β = λ/(1− p). E[Ns] = βE[Y ] = λE[Y ]1−p .
3
b) (5) L e´ uma geome´trica, com P (L = i) = pi−1(1 − p), i ≥ 1 (passa-se pelo menos uma vez pelo
servidor), e L(z) =
∑∞
i=1 z
ipi−1(1 − p) = z(1−p)1−zp . Como X =
∑L
i=1 Yi, enta˜o X
∗(s) = L(Y ∗(s)). Logo,
X∗(s) = Y
∗(s)(1−p)
1−Y ∗(s)p .
c) (5) A cadeia embutida nos instantes de partida do servidor e´ dada por:
Ni+1 =
 K, Ni = 0Ni +K − 1, Ni > 0, s/retorno
Ni +K, Ni > 0, c/retorno
E[zNi+1 ] = E[zK |Ni = 0]P (Ni = 0)
+E[zNi+K−1|Ni > 0, s/retorno]P (Ni > 0)(1− p)
+E[zNi+K |Ni > 0, c/retorno]P (Ni > 0)p
Fazendo i → ∞, Ni → N,Ni+1 → N , e sabendo que as probabilidades de retorno sa˜o fixas e independentes
das outras varia´veis,
E[zN ] = K(z)P (Ni = 0) +
K(z)
z
E[zN |N > 0]P (N > 0)(1− p) +K(z)E[zN |N > 0]P (N > 0)p
= K(z)P (Ni = 0) +
K(z)
z
(
E[zN ]− P (N > 0)
P (N > 0)
)
P (N > 0)(1−p)
+K(z)
(
E[zN ]− P (N > 0)
P (N > 0)
)
P (N > 0)p
= P (N = 0)
K(z)(1− p)(z − 1)
z −K(z)(1− p+ pz)
d) (5) Sabemos que N(1) = 1 e apo´s aplicar l’Hoˆspital, derivando o numerador e o denominador para
levantar a indeterminac¸a˜o,
1 = P (N = 0)(1− p) K
′(z)(z − 1) +K(z)
1−K ′(z)(1− p+ pz)− pK(z) |z=1 =
P (N = 0)(1− p)
1−K ′(1)− p =
P (N = 0)(1− p)
1− λE[Y ]− p
P (N = 0) = 1− λE[Y ]
1− p = 1− E[Ns] = 1− βE[Y ]
e) (5) E[T ] = E[N ]/λ = N ′(1)/λ.
N(z)(z −K(z)(1− p+ pz)) = P (N = 0)(1− p)(z − 1)K(z)
N ′(z)(z −K(z)(1− p+ pz)) +N(z)(1−K ′(z)(1− p+ pz)− pK(z)) = P (N = 0)(1− p)(K(z) + (z − 1)K ′(z))
N ′′(z) (z −K(z)(1− p+ pz)) + 2N ′(z) (1−K ′(z)(1− p+ pz)− pK(z)) +N(z) (−K”(z)(1− p+ pz)− 2pK ′(z))
= P (N = 0)(1− p)(2K ′(z) + (z − 1)K ′′(z))
Fazendo z = 1, obtemos 2E[N ](1 − E[K] − p) − λ2E[Y 2] − 2pE[K] = 2p(N = 0)(1 − p)E[K]. Observando
que 1− E[K]− p = 1− p− λE[Y ] = (1− p)(1− ρ) e simplificando
E[N ] =
λ2E[Y 2] + 2λE[Y ](p+ (1− p)(1− ρ))
2(1− p)(1− ρ) = λ
(
λE[Y 2] + 2λE[Y ](1− ρ(1− p))
2(1− p)(1− ρ)
)
= λE[T ]
f) (5) Para fila com retorno direto ao servidor, a taxa de entrada e´ λ, Poisson, e a varia´vel X e´ a mesma
da fila anterior. A utilizac¸a˜o sera´ ρ = λE[X] = βE[Y ], mostrando que os dois sistemas tem o mesmo ρ.
Usando X∗(s) = Y
∗(s)(1−p)
1−Y ∗(s)p , dado no item (b), obtemos X
∗(λ− λz) = Y ∗(λ−λz)(1−p)1−Y ∗(λ−λz)p = K(z)(1−p)1−K(z)p .
4
Substituindo na fo´rmula de N(z), dada no enunciado, obtemos
N(z) = P (N = 0)K(z)
(1− p)(1− z)
K(z)(1− p)− z + zpK(z)
que e´ igual ao N(z) calculado para o sistema com retorno ao in´ıcio da fila de espera. Assim, o nu´mero no
sistema e´ o mesmo para os dois sistemas e o tempo me´dio tambe´m o sera´.
g) (5) Para a fila M/G/1 com retorno direto ao servic¸o, o tempo de espera me´dio e´ o mesmo para qualquer
cliente, ja´ que a disciplina e´ FCFS. No caso do retorno ao in´ıcio da fila, as pessoas que sairam do sistema
com probabilidade 1 − p passaram somente uma vez pela fila de espera, o tempo me´dio delas no sistema e´
menor, comparado com o tempo me´dio de outras que retornaram mais de uma vez a` fila de espera. Enta˜o,
alguns tera˜o um tempo no sistema bem diferente dos outros e a variaˆncia sera´ maior, ainda que a me´dia
seja a mesma, comparado com M/G/1 normal.
Na˜o e´ poss´ıvel fazer a deduc¸a˜o de T ∗(s) a partir de N(z) como feito em outros sistemas na apostila para
M/G/1 e M/G/1 com fe´rias. A raza˜o e´ que o nu´mero deixado para tra´s ao deixar o sistema na˜o e´ igual ao
nu´mero de chegadas durante o tempo no sistema. Chegadas que ocorreram durante o tempo do fregueˆs t´ıpico
no sistema podem ja´ ter deixado a fila antes dele. E fregueses encontrados na sua chegada, podem ainda
estar no sistema. Logo, N(z) 6= T ∗(λ− λz) que foi a relac¸a˜o utilizada nos casos vistos em sala.
5