Baixe o app para aproveitar ainda mais
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
Compartilhar