t2-2013-1gab

Prévia do material em texto

MAB-515
Segunda Prova (90 pontos)
Prof. Paulo Aguiar (DCC/IM/UFRJ)
Aluno: Gabarito
25 de junho de 2013
Questa˜o 1 (30 pontos)
Assuma que dois fluxos chegam a um servidor. O fluxo 1 tem taxa de chegada λ1 e servic¸o X1, enquanto
o fluxo 2 tem taxa de chegada λ2 e servic¸o X2. Considere λ = λ1 + λ2, ρ1 = λ1E[X1], ρ2 = λ2E[X2] e
ρ = ρ1 + ρ2.
a) (5) Se os dois fluxos sa˜o servidos em uma u´nica fila FCFS, calcule o tempo me´dio de espera E[WFCFS ]
para esta fila.
R: Para a fila FCFS alimentada pelos dois fluxos temos direto da fo´rmula de M/G/1 que E[WFCFS ] =
ρE[Xr ]
1−ρ , ρ < 1 com ρE[Xr] = ρ1E[X1r] + ρ2E[X2r].
b) Assuma agora os fluxos sa˜o separados em duas classes HOL, a classe 1 para o fluxo 1 e a classe 2 para
o fluxo 2. Considere que a classe 1 e´ servida priorita´ria e exaustivamente.
b.1) (5) Para esta fila HOL, qual o servic¸o me´dio pendente encontrado no instante de chegada de um
fregueˆs t´ıpico de qualquer classe?
R: E[U ] = E[Nq1]E[X1] + E[Nq2]E[X2] + ρE[Xr] = ρ1E[W1] + ρ2E[W2] + ρE[Xr].
b.2) (10) Calcule E[W1 e E[W2]. Compare E[W1 e E[W2] com E[WFCFS ], indicando se a relac¸a˜o destes
tempos me´dios de espera em relac¸a˜o a E[WFCFS ] e´ sempre a mesma ou depende das taxas e da distribuic¸a˜o
do servic¸o. Justifique analiticamente.
R: Para a fila 1, podemos deduzir o tempo me´dio de espera usando a metodologia padra˜o. Como os que
chegam depois na˜o interferem com o fregues t´ıpico da classe 1, temos:
E[W1] = E[W01] = E[Nq1]E[X1] + ρE[Xr], E[W1]. Enta˜o, E[W1] =
ρE[Xr ]
1−ρ1
= (1−ρ)E[WFCFS]1−ρ1 , ρ1 < 1.
Este resultado poderia ter sido escrito diretamente da fo´rmula da M/G/1 com a interfereˆncia da classe 2
acontecendo apenas no servic¸o, pois a classe 1 na˜o interrompe a classe 2. Observar que E[W1] < E[WFCFS ],
sempre.
Para a classe 2, podemos deduzir o tempo me´dio de espera usando a metodologia padra˜o:
E[W02] = E[U ] = ρ1E[W1] + ρ2E[W2] + ρE[Xr]
E[W2] =
E[W02]
1− ρ1
=
ρ1E[W1] + ρ2E[W2] + ρE[Xr]
1− ρ1
=
ρ1E[W1] + ρE[Xr]
1− ρ
=
ρE[Xr]
(1 − ρ1)(1− ρ)
=
E[W1]
1− ρ
=
E[WFCFS ]
1− ρ1
, ρ < 1
Observar que E[W2] > E[WFCFS ], sempre.
1
b.3) (10) Calcule a me´dia do tempo de espera quando consideramos as duas classes, ou seja, E[WHOL =
E[WHOL|classe1]P (classe1) + E[WHOL|classe2]P (classe2). Determine as condic¸o˜es para que se tenha:
1. E[WHOL > E[WFCFS ]
2. E[WHOL = E[WFCFS ]
3. E[WHOL < E[WFCFS ]
R:
E[WHOL] =
λ1
λ
E[W1] +
λ2
λ
E[W2] = E[WFCFS ]
(
λ1(1− ρ1)
λ(1 − ρ1)
+
λ2
λ(1 − ρ1)
)
= E[WFCFS ]
(
λ− λ1ρ1 − λ1λ2E[X2]
λ1 − λ1ρ1 − λ1λ2E[X1])
)
Fica fa´cil ver:
Se E[X2] > E[X1], teremos E[WHOL] < E[WFCFS ] e sera´ melhor usar HOL.
Se E[X2] = E[X1], teremos E[WHOL] = E[WFCFS ].
Se E[X2] < E[X1], teremos E[WHOL] > E[WFCFS ] e sera´ melhor usar FCFS.
Questa˜o 2 (30 pontos)
Assuma uma fila M/G/1 modificada em que apenas o primeiro servic¸o do per´ıodo ocupado X0 e´ diferente
dos outros. Considere que a taxa de chegada e´ λ e a T.L. do servic¸o e´ dada por X∗(s). Seja N o nu´mero de
pessoas no sistema.
a) (10) Usando o me´todo da cadeia embutida, mostre que
N(z) = P (N = 0)
X∗(λ− λz)− zX∗0 (λ− λz)
X∗(λ− λz)− z
R: Vamos analisar a evoluc¸a˜o do nu´mero deixado para tra´s nos instantes da i-e´sima e i+1-e´sima partidas.
Seja Ni e Ni+1 os nu´meros de pessoas deixadas para tra´s nestes instantes, respectivamente. Seja K o nu´mero
de chegadas Poisson durante um servic¸o X, com K(z) = X∗(λ−λz). Seja K0 o nu´mero de chegadas Poisson
durante um servic¸o X0, com K0(z) = X
∗
0 (λ− λz). E´ fa´cil ver que
Ni+1 =
{
K0 , se Ni = 0
Ni +K − 1 , se Ni > 0
Usando transformadas e condicionamento, temos
E[zNi+1] = E[zK0 |Ni = 0]P (Ni = 0) + E[z
Ni+K−1|Ni > 0]P (Ni > 0)
No comportamento limite, Ni → N e Ni+1 → N com i → ∞, e para ρ < 1 havera´ uma distribuic¸a˜o
estaciona´ria do nu´mero de pessoas na fila com T.Z. dada por N(z) = E[zN ]. Rescrevendo a expressa˜o acima
para a situac¸a˜o limite, temos
E[zN ] = E[zK0 |N = 0]P (N = 0) + E[zN+K−1|N > 0]P (N > 0)
= K0(z)P (N = 0) +
K(z)
z
E[zN |N > 0](1− P (N = 0)
Como
E[zN ] = E[zN |N = 0]P (N = 0) + E[zN |N > 0]P (N > 0)
= P (N = 0) + (1 − P (N = 0))E[zN |N > 0]
2
enta˜o E[zN |N > 0] = N(z)−P (N=0)1−P (N=0) . Substituindo este valor acima na expressa˜o anterior de E[z
N ] e simpli-
ficando obtemos
E[zN ] = K0(z)P (N = 0) +
K(z)
z
(N(z)− P (N = 0))
zE[zN ] = zK0(z)P (N = 0) +K(z)N(z)−K(z)P (N = 0)
(K(z)− z)E[zN ] = P (N = 0) (K(z)− zK0(z))
N(z) = P (N = 0)
X∗(λ− λz)− zX∗0 (λ− λz)
X∗(λ− λz)− z
Esta e´ a expressa˜o para a T.Z. da pmf de N , nu´mero de pessoas presentes na fila em um instante aleato´rio.
Cabe observar que a distribuic¸a˜o do nu´mero de pessoas na fila e´ independente da disciplina de atendimento,
se ela na˜o leva em considerac¸a˜o nenhum aspecto relativo ao nu´mero de pessoas presentes.
b) (10) Calcule P (N = 0). Voceˆ pode usar a metodologia que quiser para obter este valor.
R: Podemos obter P (N = 0) a partir de N(1) = 1 e usando a regra de l’Hoˆspital, pois teremos 0/0.
Partiremos de N(z) = P (N = 0)K(z)−zK0(z)(K(z)−z) e derivaremos o numerador e o denominador antes de fazer
z=1.
N(z)|z=1 = 1 = P (N = 0) lim
z→1
(
K ′(z)−K0(z)− zK
′
0(z)
K ′(z)− 1)
)
1 = P (N = 0)
(
λE[X ]− 1− λE[X0]
λE[X ]− 1
)
P (N = 0) =
1− λE[X ]
1− λE[X ] + λE[X0]
Para E[X0] = E[X ], P (N = 0) = 1− λE[X ] = 1− ρ, como esperado.
Uma segunda forma de obter P(N=0) e´ observar que apenas durante o per´ıodo ocioso temos N = 0 e
E[ocioso] = E[I] = 1/λ. Por outro lado, E[ocupado] = E[G0] =
E[X0]
1−λE[X] . Pela teoria da renovac¸a˜o,
P (N = 0) =
E[ocioso]
E[ocioso] + E[ocupado]
=
1
λ
1
λ
+ E[X0]1−λE[X]
=
1− λE[X ]
1− λE[X ] + λE[X0]
Por outro lado, como P (N = 0) = 1−ρ = 1−λE[servico], pode-se concluir que E[servico] = E[X0]1−λE[X]+λE[X0] .
c) (10) A partir de N(z) acima, obtenha E[W ].
R: E[N ] = λ(E[W ] + E[servico]), ou seja, E[W ] = E[N ]−ρ
λ
. Enta˜o, resta calcular E[N ] = N ′(1).
N(z)(K(z)− z) = P (N = 0)(K(z)− zK0(z))
N ′(z)(K(z)− z) +N(z)(K ′(z)− 1) = P (N = 0)(K ′(z)−K0(z)− zK
′
0(z))
N ′′(z)(K(z)− z) + 2N ′(z)(K ′(z)− 1) +N(z)K ′′(z) = P (N = 0)(K ′′(z)− 2K ′0(z)− zK
′′
0 (z))
2E[N ](λE[X ]− 1) + λ2E[X2] = P (N = 0)(λ2E[X2]− 2λE[X0]− λ
2E[X20 ])
E[N ] =
P (N = 0)(λ2E[X20 ]− λ
2E[X2] + 2λE[X0])
2(1− λE[X ])
+
λ2E[X2]
2(1− λE[X ])
=
λ2E[X2]
2(1− λE[X ])
+
λ2(E[X20 ]− E[X
2])
2(1− λE[X ] + λE[X0])
+
λE[X0]
1− λE[X ] + λE[X0]
3
Como E[N ] = λE[T ] = λ(E[W ] + E[servico]) = λE[W ] + ρ, resulta
E[W ] =
λE[X2]
2(1− λE[X ])
+
λ(E[X20 ]− E[X
2])
2(1− λE[X ] + λE[X0])
Questa˜o 3 (30 pontos)
Assuma o sistema de filas com servic¸os exponenciais acima (taxas µi conhecidas), alimentado por dois fluxos
independentes. O fluxo 1, ao sair da fila3 retorna para o final da fila1 com probabilidade p1 ou parte com
probabilidade 1 − p1. O fluxo 2, ao sair da fila3 retorna para o final da fila2 com probabilidade p2 ou
parte com probabilidade 1 − p2. Use β1 e β2, mostrados na figura, como as taxas de sa´ıda das filas 1 e 2,
respectivamente. Estes valores na˜o sa˜o conhecidos e teˆm que ser determinados.
a) (5) Calcule ρi, a utilizac¸a˜o de cada fila.
R:
β1 = λ1 + p1β1 =⇒ β1 =
λ1
1−p1
, ρ1 =
β1
µ1
β2 = λ2 + p2β2 =⇒ β2 =
λ2
1−p2
, ρ2 =
β2
µ2
ρ3 =
β1+β2
µ3
b) (5) Calcule o nu´mero me´dio de pessoas do fluxo 1 na fila 3 (fila de espera e servidor). Dica: Na˜o se
esquec¸a do servidor!
R:E[N31] =
(
β1
β1+β2
)
E[N3] =
(
β1
β1+β2
)(
ρ3
1−ρ3
)
.
Outra forma de racioc´ınio seria usar Little e dizer que E[N31] = β1E[T3]. Mas como (β1 + β2)E[T3] =
E[N3], resulta igualmente que E[N31] =
(
β1
β1+β2
)
E[N3].
c) (5) Calcule E[T ], o tempo me´dio gasto no sistema,considerando os dois fluxos.
R: A partir do resultado de Little, E[T ] =
(
1
λ1+λ2
)∑3
i=1
ρi
1−ρi
.
d) (10) Calcule E[T1] e E[T2], os tempos me´dios gastos no sistema pelos fregueses dos fluxos 1 e 2,
respectivamente. Na˜o use forc¸a bruta tentando contar o nu´mero de vezes que se passa pelas filas. Estou
dando um desenho fa´cil na prova, mas queremos uma soluc¸a˜o que possa ser aplicada a situac¸o˜es mais
complexas.
R: Do resultado de Little, E[T1] =
1
λ1
∑3
i=1E[Ni1] =
1
λ1
(
ρ1
1−ρ1
+ E[N31]
)
, pois as pessoas do fluxo 1
apenas esta˜o na fila 1 e na fila 3. Similarmente, E[T2] =
1
λ2
∑3
i=1 E[Ni2] =
1
λ2
(
ρ2
1−ρ2
+ E[N32]
)
, pois as
pessoas do fluxo 1 apenas esta˜o na fila 2 e na fila 3. Na fila 3, o nu´mero de pessoas da fluxo 2 presentes e´
dado por E[N32] =
(
β2
β1+β2
)
E[N3].
e) (5) Mostre a como E[T ] poderia ser obtido a partir de E[T1] e E[T2].
4
R: E[T ] =
(
λ1
λ1+λ2
)
E[T1] +
(
λ2
λ1+λ2
)
E[T2].
5