Cap17
70 pág.

Cap17

Disciplina:Planejamento da Producao15 materiais249 seguidores
Pré-visualização30 páginas
caso especial é a distribuição de Erlang, que tem as restrições de que todas suas k
fases estão em série e que essas fases têm o mesmo parâmetro para suas distribuições expo-
nenciais. Eliminar essas restrições significa que as distribuições tipo-fase, em geral, são
capazes de fornecer consideravelmente maior flexibilidade que a distribuição de Erlang em
adequar a verdadeira distribuição de tempos entre atendimentos ou de tempos de atendi-
mento observada em um sistema de filas real. Essa flexibilidade é especialmente valiosa
quando usar a distribuição real diretamente no modelo não for analiticamente tratável e a
razão entre média e desvio-padrão para a distribuição real não se aproximar muito das
razões disponíveis (�k� para k � 1, 2, . . .) para a distribuição de Erlang.

Já que elas são construídas de combinações de distribuições exponenciais, os modelos
de filas que usam distribuições tipo-fase ainda podem ser representados por uma cadeia de
Markov de tempo contínuo. Essa cadeia de Markov geralmente terá um número de estados
infinito, de forma que encontrar a distribuição de estado estável do estado do sistema requer
resolver um sistema de equações lineares infinito com uma estrutura relativamente comple-
xa. Resolver um sistema destes está longe de ser uma coisa rotineira, porém avanços teóri-
cos recentes nos permitiram solucionar esses modelos de filas numericamente em alguns
casos. Uma extensa tabulação desses resultados para modelos com várias distribuições tipo-
fase (inclusive a distribuição hiperexponencial) está disponível.21

21 SEELEN, L. P. et al. Tables for Multi-Server Queues. Amsterdã: North-Holland, 1985.

42 CAPÍTULO 17 TEORIA DAS FILAS

Portanto, assim que um atendente tiver começado a atender um cliente, o atendimento tem
de ser completado sem interrupção. O primeiro modelo supõe prioridades não-preemptivas.

Com prioridades preemptivas, o cliente de menor prioridade que está sendo atendido
é preterido (jogado de volta para a fila) toda vez que um cliente com prioridade maior entrar
no sistema de filas. Um atendente é, portanto, liberado para começar a atender imediatamen-
te a nova chegada. Quando um atendente não consegue terminar um atendimento, o próxi-
mo cliente a começar a receber atendimento é selecionado exatamente como descrito no iní-
cio desta subseção, de modo que um cliente preterido normalmente voltará a ser atendido
novamente e, após um número suficiente de tentativas, finalmente acabará de ser atendido.
Em virtude da propriedade de falta de memória da distribuição exponencial (ver Seção
17.4), não precisamos nos preocupar em definir o ponto no qual o atendimento começa
quando um cliente preterido voltar a ser atendido; a distribuição do tempo de atendimento
restante sempre é a mesma. Para qualquer outra distribuição de tempo de atendimento, é
importante distinguir entre sistemas preemptivos-retomados, em que o atendimento para um
cliente preterido é retomado no ponto onde foi interrompido, e sistemas preemptivos-repe-
tidos, nos quais o atendimento tem de começar do início novamente. O segundo modelo
supõe prioridades preemptivas.

Para ambos os modelos, se a distinção entre clientes em diferentes classes de priori-
dades for ignorada, a Propriedade 6 para a distribuição exponencial (ver Seção 17.4) implica
que todos os clientes chegariam de acordo com um processo de entrada de Poisson. Além
disso, todos os clientes têm a mesma distribuição exponencial para tempos de atendimen-
to. Conseqüentemente, os dois modelos, na verdade, são idênticos ao modelo M/M/s estu-
dado na Seção 17.6, exceto pela ordem na qual os clientes são atendidos. Portanto, quando
contamos apenas o número total de clientes no sistema, a distribuição de estado estável
para o modelo M/M/s também se aplica a ambos os modelos. Portanto, as fórmulas para L
e Lq também são transferidas, assim como os resultados esperados de tempo de espera (pela
fórmula de Little) W e Wq, para um cliente selecionado aleatoriamente. O que muda é a dis-
tribuição dos tempos de espera, que foi obtida na Seção 17.6 sob a hipótese de uma disci-
plina de fila em que os primeiros que chegam serão os primeiros a ser atendidos. Com uma
disciplina de prioridades, essa distribuição tem uma variância muito maior, pois os tempos
de espera de clientes nas classes de prioridades mais altas tendem a ser muito menores
daqueles regidos pela regra na qual os primeiros que chegam serão os primeiros a ser aten-
didos, ao passo que os tempos de espera nas classes de prioridades mais baixas tendem a
ser muito maiores. Pelo mesmo motivo, a subdivisão do número total de clientes no siste-
ma tende a ser desproporcionalmente tendenciosa para as classes de prioridades mais bai-
xas. Porém, essa condição é apenas a razão para impor prioridades no sistema de filas em
primeiro lugar. Queremos melhorar as medidas de desempenho para cada uma das classes
de prioridades mais altas à custa de desempenho para as classes de prioridades mais bai-
xas. Para determinar o nível de melhoria que está sendo alcançado, precisamos obter tais
medidas na forma de tempo de espera previsto no sistema e número de clientes esperado
no sistema para cada uma das classes de prioridades. Expressões para essas medidas são
dadas a seguir para os dois modelos, um de cada vez.

Resultados para o Modelo de Prioridades Não-preemptivas

Façamos que Wk seja o tempo de espera previsto no estado estável no sistema (incluindo o
tempo de atendimento) para um membro da classe de prioridades k. Então

Wk � �ABk
1
�1Bk
� � �

�
1

�, para k � 1, 2, . . . , N,

em que A � s!�s�
r

�
s

�
� �

s�1

j�0
�
r

j!
j

� � s�,

B0 � 1,

Bk � 1 � �
�ki�

s�
1 �i�,

17.8 MODELOS DE FILAS DE DISCIPLINA DE PRIORIDADES 43

s � número de atendentes,
� � taxa média de atendimento por atendente ocupado,
�i � taxa média de chegada for classe de prioridades i,

� � �
N

i�1
�i,

r � �
�
�

�.

Esse resultado parte do pressuposto de que

�
k

i�1
�i 	 s�,

de modo que a classe de prioridades k possa alcançar uma condição de estado estável. A fór-
mula de Little ainda se aplica a classes de prioridades individuais, de forma que Lk, o núme-
ro esperado no estado estável de membros da classe de prioridades k no sistema de filas
(inclusive aqueles que estão sendo atendidos), seja

Lk � �kWk, para k � 1, 2, . . . , N.

Para determinar o tempo de espera previsto na fila (excluindo o tempo de atendimento) para
a classe de prioridades k, simplesmente subtraia 1/� de Wk; o comprimento esperado da fila
correspondente é novamente obtido multiplicando por �k. Para o caso especial em que s
� 1, a expressão para A reduz-se a A � �2/�.

No Courseware de PO, você poderá encontrar um gabarito em Excel para realizar os
cálculos anteriores.

A seção de Exemplos Trabalhados do CD-ROM fornece um exemplo que ilustra a apli-
cação do modelo das prioridades não-preemptivas para determinar quantos tornos-revólver
uma fábrica deveria ter quando as tarefas caem nas três classes de prioridades.

Variante com um Único Atendente do Modelo de Prioridades
Não-preemptivas

A hipótese dada anteriormente que o tempo de atendimento esperado 1/� é o mesmo para
todas as classes de prioridades é bastante restritiva. Na prática, essa hipótese algumas vezes
é violada em decorrência das diferenças nas exigências de atendimento para as diferentes
classes de prioridades.

Felizmente, para o caso especial de um único atendente, é possível permitir tempos de
atendimento esperado diferentes e ainda obter resultados úteis. Façamos que 1/�k represen-
te a média da distribuição exponencial de tempos de atendimento para a classe de priorida-
des k, de modo que

�k � taxa média de atendimento para a classe de prioridades k, para k � 1, 2, . . . , N.

Depois, o tempo de espera previsto no estado estável no sistema para um membro de classe
de prioridades k é

Wk � �bk�
ak

1bk
� � �

�
1

k
�, para k � 1, 2, . . . , N,

em que ak � �
k

i�1
�
�
�i

2
i

�,

b0 � 1,

bk � 1 � �
k

i�1
�
�
�i

i
�

44 CAPÍTULO 17 TEORIA DAS FILAS

Esse resultado