PROBLEMAS DE OTIMIZAÇÃO ( MODELOS MATEMATICOS E ALGORITIMOS )

Prévia do material em texto

PROBLEMAS DE OTIMIZAÇÃO. ENUNCIADOS,
MODELOS MATEMÁTICOS E ALGORITMOS
PROF. MSC. DORIRLEY RODRIGO ALVES
PROBLEMAS DE OTIMIZAÇÃO. ENUNCIADOS,
MODELOS MATEMÁTICOS E ALGORITMOS
Disciplina: Pesquisa Operacional
Belo Horizonte
Junho de 2013
Sumário
1 Modelagem Analítica - Teoria das Filas e Teoria da Análise Opera-
cional 1
1.1 Definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Sistemas de Filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Componentes de um sistema de filas . . . . . . . . . . . . . . . . . . . . 2
1.4 Análise Operacional em Filas . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.1 Análise Operacional em Filas Isoladas . . . . . . . . . . . . . . . 7
1.4.2 Variáveis operacionais básicas . . . . . . . . . . . . . . . . . . . 7
1.4.3 Variáveis operacionais derivadas . . . . . . . . . . . . . . . . . . 8
1.4.4 Sequência de comportamento . . . . . . . . . . . . . . . . . . . 8
1.5 Leis Operacionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 Lei da Utilização (Ui) . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2 Número médio de visitas na Fila i (ηi) . . . . . . . . . . . . . . 11
1.5.3 Tempo Médio de Resposta (Ri) que cada visita permanece na fila i 12
1.5.4 Lei de Little . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Teoremas Operacionais . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.1 Hipótese do Equilíbrio de Fluxo (EF) . . . . . . . . . . . . . . . 12
1.6.2 Teorema da Taxa de Processamento (EF) . . . . . . . . . . . . 13
1.6.3 Teorema do Tempo de Resposta (Ri) . . . . . . . . . . . . . . . 13
1.7 Construção da Curva de Desempenho da Fila . . . . . . . . . . . . . . 14
1.7.1 Obtendo as Medições . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7.2 Simulando novos cenários . . . . . . . . . . . . . . . . . . . . . 19
iii
Capítulo 1
Modelagem Analítica - Teoria das
Filas e Teoria da Análise
Operacional
A Teoria das Filas é um ramo da probabilidade que estuda a formação de filas
por meio de análises matemáticas precisas e propriedades mensuráveis das filas. Ela
provê modelos para demonstrar previamente o comportamento de um sistema que
ofereça serviços cuja demanda cresce aleatoriamente, tornando possível dimensioná-lo
de forma a satisfazer os clientes e ser viável economicamente para o provedor do serviço,
evitando desperdícios e gargalos.
1.1 Definições
Figura 1.1. Centro de Serviço
• Rede de filas - Conjunto de entidades interligadas que oferecem serviços (centros
de serviço) e de usuários (clientes).
1
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 2
• Centro de serviço - Representa os recursos do sistema, compreendendo um ou
mais servidores e um conjunto de clientes que esperam pelo serviço.
• Fila - Representa os clientes que estão esperando pelo serviço, juntamente com
os que estão sendo atendidos pelos servidores.
• Fila de espera - Somente os clientes que estão aguardando pelo serviço.
1.2 Sistemas de Filas
Existem diversas aplicações da teoria das filas que podem ser encontradas na
literatura de probabilidade, pesquisa operacional e engenharia industrial. Entre elas
destacam-se:
• Fluxo de tráfego (aviões, carros, pessoas, comunicações)
• Escalonamento (pacientes em hospitais, programas em computadores)
• Prestação de serviços (bancos, correios, lanchonetes)
1.3 Componentes de um sistema de filas
Um sistema de filas consiste no processo de chegada, da distribuição do tempo de
serviço, do número de servidores, da capacidade do sistema, da população de usuários
e da disciplina de atendimento.
Processo de chegada
O processo de chegada indica qual o padrão de chegada dos clientes no sistema.
Apresenta comportamento estocástico, ou seja, as chegadas ocorrem no tempo e no
espaço de acordo com as leis da probabilidade; assim, é preciso conhecer qual a distri-
buição de probabilidade que descreve os tempos entre as chegadas dos clientes.
A distribuição mais comum é a de Poisson, ou seja, os tempos entre as chega-
das são exponencialmente distribuídos. Entre outras distribuições, estão a de Erlang,
hiperexponencial e arbitrária.
Clientes podem chegar simultaneamente (chegada em batch). Se for possível, é
necessário também saber a distribuição de probabilidade do tamanho do batch. A
reação do cliente na fila pode variar. Ele pode esperar independentemente do tamanho
da fila, também pode decidir não entrar no sistema caso a fila esteja muito grande
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 3
(cliente decepcionado), ele pode esperar na fila mas depois de um tempo desistir e sair
do sistema, e também pode mudar de uma fila para outra em sistemas com servidores
paralelos.
O padrão de chegada de clientes em função do tempo pode ser permanente; nesse
caso o padrão não muda no tempo, ou seja, a distribuição de probabilidade que descreve
as chegadas é independente do tempo. Também pode ser não-permanente, isto é, o
padrão de chegada muda com o tempo. Por exemplo, a chegada de clientes diminui no
horário de almoço.
Distribuição do tempo de serviço
Assim como no processo de chegada, também é necessário conhecer a distribuição
de probabilidade do tempo de serviço, sendo válidas as mesmas distribuições apresen-
tadas.
Os serviços podem também ser simples ou batch.
O estado pode ser independente: o processo de atendimento não depende do nú-
mero de clientes esperando pelo serviço. Em contrapartida, em um estado dependente,
o processo de atendimento muda de acordo com o número de clientes na fila. Por exem-
plo, um servidor pode trabalhar mais rápido quando a fila aumenta ou, ao contrário,
ficar confuso e então mais lento.
Da mesma forma que no processo de chegada, o padrão de serviço pode variar
de acordo com o tempo. Por exemplo, a experiência adquirida com o serviço pode
aumentar a produtividade; o cansaço, por outro lado, pode diminuí-la. Caso não haja
variação o padrão é estacionário.
Número de servidores
Esse componente é também conhecido como número de canais de serviço. Indica
a quantidade de “pontos de atendimento"do sistema, de forma a servir aos clientes
paralelamente. Quando um sistema possui mais de um servidor (multiservidor ou
multicanal), ele pode apresentar duas variações. Em um sistema de fila única, existe
uma única fila para todos os servidores, como em um caixa de banco. Em um sistema de
múltiplas filas, existe uma fila para cada servidor, como em um caixa de supermercado.
Quando existirem infinitos servidores, ou seja, todo cliente que chega é atendido
imediatamente, temos um caso especial conhecido como “Centro de atraso".
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 4
(a) Multiservidor (b) Servidor paralelo (c) Centro de atraso ou
servidor mínimo
Figura 1.2. Tipos de filas
Capacidade do sistema
Representa o número máximo de clientes que o sistema suporta, incluindo os
que estão em espera e os que estão sendo atendidos. A capacidade pode ser infinita
(mais fácil de analisar) ou finita (por exemplo, número limitado de atendentes). Se a
capacidade for finita, quando o sistema estiver lotado nenhum cliente pode entrar até
que um cliente saia do sistema, liberando espaço.
População de usuários
Esse componente indica o número potencial de clientes que podem chegar a um
sistema. Pode ser finita ou infinita.
Disciplina de atendimento
Descreve a forma como os clientes saem da fila de espera para serem atendidos.
Algumas disciplinas são:
• FCFS (First Come, First Served): Primeiro a Chegar, Primeiro a ser Atendido.
Disciplina mais comum, inclusive na vida diária.
• FIFO (First In, First Out): Primeiro a Entrar, Primeiro a Sair).
• LCFS (Last Come, First Served): Último a chegar, Primeiro a ser Atendido
1.Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 5
• LIFO (Last In, First Out): Último a Chegar, Primeiro a Sair. Aplicável em
sistemas em que o item mais recente é mais fácil de ser recuperado, como por
exemplo em sistemas de controle de estoque.
• Fila com prioridade: a cada cliente é atribuída uma prioridade; clientes com
maior prioridade têm preferência no atendimento. Pode ser de dois tipos:
• Preemptivo: o cliente com maior prioridade é atendido imediatamente, interrom-
pendo o atendimento ao cliente com menor prioridade. Ao terminar, o cliente
de menor prioridade volta a ser atendido, podendo continuar o processo de onde
parou ou então reiniciá-lo
• Não-preemptivo: o cliente com maior prioridade é colocado no início da fila,
recebendo o serviço somente quando o cliente em atendimento sai do sistema,
mesmo se este for de prioridade mais baixa
• Round-robin (algoritmo): cada cliente recebe uma fatia de tempo do servidor
(quantum), dentro da qual é atendido. Após o término do quantum, se a ati-
vidade não foi completada, o cliente é retirado e outro passa a ser atendido.
Posteriormente, o cliente que foi interrompido retorna ao servidor e continua a
sua atividade. É muito comum em escalonamento de processos da CPU.
Notação
As seis características apresentadas acima descrevem um sistema de filas. Para
simplificar, utiliza-se a notação de Kendall, proposta em 1953, composta por uma série
de símbolos da seguinte forma:
A/S/m/K/N/Q (1.1)
Em que:
A: Distribuição dos tempos entre as chegadas (Processo de chegada);
S: Distribuição dos tempos de serviço;
m: Número de servidores;
K: Capacidade do sistema;
N : Tamanho da população;
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 6
Q: Disciplina de atendimento;
Exemplo 1.3.0.1 Exemplos de sistemas de filas
M/G/4/50/2000/LCFS
• Processo de chegada exponencial (Markoviano)
• Distribuição dos tempos de serviço arbitrária (Geral)
• Quatro servidores
• Capacidade para cinqüenta clientes
• População de dois mil clientes
• Disciplina de atendimento "Último a Chegar, Primeiro a ser Servido"
D/M/1/∞/∞/RR
• Processo de chegada determinístico
• Distribuição dos tempos de serviço exponencial (Markoviano)
• Um servidor
• Capacidade ilimitada
• População infinita
• Disciplina de atendimento Round-robin
Muitas vezes, os três últimos símbolos são omitidos. Nestes casos, assume-se
capacidade ilimitada, população infinita e disciplina de atendimento FCFS.
Exemplo:
M/M/1
Distribuições de probabilidade:
• Exponencial (M)
• Uniforme (U)
• Arbitrária ou Geral (G)
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 7
• Erlang (Ek)
• Hiperexponencial (Hk)
1.4 Análise Operacional em Filas
A Teoria da Análise Operacional foi proposta por J. P. Buzen em 1976 e posteri-
ormente estendidas por Denning e Buzen em 1978. Baseia-se na análise do relaciona-
mento entre as variáveis obtidas por medição. Esta análise será dirigida primeiramente
à Filas Isoladas e depois, à Redes de Filas Abertas e Fechadas (multiprogramação).
É importante que o sistema de em questão seja analizado nos pontos críticos ou
de máxima carga de trabalho.
1.4.1 Análise Operacional em Filas Isoladas
Uma fila “isolada"é composta por um servidor e de um conjunto de visitas que
aguardam sua vez para ser atendidas pelo servidor.
Figura 1.3. Representação de uma fila isolada e seus parâmetros
Uma visita pode ser um atendimento realizado pelo servidor, ou uma operação
de processamento em um ambiente com entrada e saída e etc.
1.4.2 Variáveis operacionais básicas
T (time): intervalo do tempo de observação [seg. ou min.]
Ai (arrivals): número de visitas que chegam à fila i durante o intervalo de medição
[visitas]
Ci (completions): número de visitas que completam, e portanto, saem da fila i du-
rante o intervalo de medição [visitas]
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 8
Bi (busy time): tempo durante o qual o servidor i esteve ocupado (Bi≤ T )
1.4.3 Variáveis operacionais derivadas
λi: taxa média de chegada de visitas à fila i
λi =
Ai
T
[
visitas
seg.
]
(1.2)
Xi: taxa de processamento da fila i (número de transações completadas por unidade
de tempo)
Xi =
Ci
T
[
visitas
seg.
]
(1.3)
Si: tempo médio de serviço por visita
Si =
Bi
Ci
[ seg.
visitas
]
(1.4)
Ri: tempo médio de resposta no ambiente monitorado i ou tempo médio que uma
visita permanece na fila desde que entra até que sai
[ seg.
visitas
]
ou [seg.]
Ri =
Si
1− Ui
[ seg.
visitas
]
ou [seg.] (1.5)
Wi: tempo médio de espera por visita
Wi = Ri − Si
[ seg.
visitas
]
ou [seg.] (1.6)
Ui: utilização do servidor i
Ui =
Bi
T
[admensional ou %] (1.7)
1.4.4 Sequência de comportamento
É um registro do número de visitas ηi(t) na fila i incluindo o servidor, durante o
intervalo de medição (0 ≤ t ≤ T )
Sendo N+ o número máximo de visitas observado na fila i durante o período de
observação Ti tem-se:
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 9
Figura 1.4. Diagrama de sequênciamento de visitas em uma fila isolada
Ti(0) + Ti(1) + . . .+ Ti(N
+) = T (1.8)
1 + 5 + 4 + 2 + 1 = T = 13 seg.
onde:
Ti(η) : tempo durante o qual houve η visitas na fila i
Se a equação 1.8 for dividida entre T , tem-se:
Ti(0)
T
+
Ti(1)
T
+ . . .+
Ti(N
+)
T
= 1 (1.9)
onde:
Ti(η)
T
= Pi(η) : é a fração de tempo durante o qual houve η visitas na fila i
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 10
Tempo e fração do tempo durante o qual houve η visitas na fila i
Ti(1)
T
=
5
13
= 0, 38
Para o restante...
η Ti(η) Pi(η) %Pi(η)
0 1 0,08 8%
1 5 0,38 38%
2 4 0,31 31%
3 2 0,15 15%
4 1 0,08 8%
T = 13 1,00 100%
A equação 1.9 em termo de porcentagem é:
100(Pi(0) + Pi(1) + . . .+ Pi(N
+)) = 100%
Exemplo 1.4.4.1 Considerando a sequência de comportamento dada anteriormente:
T= 13 seg
Ai= 5 visitas chegam à fila i (↑)
Ci= 5 visitas saem da fila i (↓)
Bi= T − Ti(0) = 13− 1 = 12 seg. a fila esteve ocupada
λi: taxa média de chegada de visitas à fila i
λi =
Ai
T
=
5
13
= 0, 39
[
visitas
seg.
]
Xi: taxa de processamento da fila i (número de transações completadas por unidade
de tempo)
Xi =
Ci
T
=
5
13
= 0, 39
[
visitas
seg.
]
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 11
Si: taxa média de serviço da fila i (número de transações completadas por unidade de
tempo)
Si =
Bi
Ci
=
12
5
= 2, 4
[ seg.
visitas
]
Ui: utilização do servidor i
Ui =
Bi
T
=
12
13
= 0, 92⇒ 92%
1.5 Leis Operacionais
1.5.1 Lei da Utilização (Ui)
Ui =
Bi
T
=
Bi
Ci
× Ci
T
= SiXi ∴ Ui = SiXi (1.10)
sempre:
Ui ≤ 1 ou %Ui ≤ 100%
1.5.2 Número médio de visitas na Fila i (ηi)
É dada pela área abaixo da curva.
ηi =
N+∑
η=0
ηTi(η)
T
[visitas] (1.11)
Exemplo 1.5.2.1 Para a sequência de comportamento dado anteriormente.
ηi =
(0× 1 + 1× 5 + 2× 4 + 3× 2 + 4× 1)
13
= 1, 77 [visitas]
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 12
1.5.3 Tempo Médio de Resposta (Ri) que cada visita
permanece na fila i
Ri =
ηi × T
Ci
[seg.] (1.12)
no exemplo
Ri =
1, 77× 13
5
= 4, 6 [seg.]
1.5.4 Lei de Little
Desenvolvida por John Little no início dos anos 60, A Lei de Little relaciona o
número de clientes no sistema com o tempo médio despendido no sistema. Mostra a
relação entre o número médio de visitas (ηi), a taxa de processamento (Xi) e o tempo
médio que uma visita permanece na fila i.
da equação 1.12 tem-se:
ηi =
RiCi
T
⇒ ηi = RiXi [seg.] (1.13)A Lei de Little se aplica sempre que o número de chegadas é igual ao número de
saídas (denominado sistema em equilíbrio). Pode ser aplicada também em subsistemas
(caixa preta). Se o sistema está em equilíbrio, a taxa de chegada será igual a taxa de
saída conforme veremos a seguir.
1.6 Teoremas Operacionais
Todo teorema possui hipóteses para ter validade pelo qual tem-se:
1.6.1 Hipótese do Equilíbrio de Fluxo (EF)
Que diz: “ o # de visitas que chegam à fila i é igual ao # de visitas que saem
dela". Ou seja, (Ai = Ci).
Portanto, se
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 13
λi =
Ai
T
e Xi =
Ci
T
concluímos que
λi = Xi (1.14)
1.6.2 Teorema da Taxa de Processamento (EF)
Ui = SiXi = Siλi (1.15)
1.6.3 Teorema do Tempo de Resposta (Ri)
Ri =
Si
1− Ui
[ seg.
visita
]
ou [seg.] (1.16)
Exemplo 1.6.3.1 O tempo médio de serviço de um atendente de caixa é de 20 minutos
e este recebe 0,03 clientes por minutos. Qual será o tempo de resposta do serviço?
SCaixa = 20 [minutos]
λCaixa = 0, 03
[
visitas
min.
]
RCaixa =?
RCaixa =
SCaixa
1− UCaixa =
SCaixa
1− SCaixaλCaixa =
20
1− 20× 0, 03 = 50
[
minutos
visitas
]
Se a velocidade do atendende fosse duplicada, qual seria o novo tempo de resposta
no ambiente?
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 14
SCaixa = 10 [minutos]
λCaixa = 0, 03
[
visitas
minutos
]
RCaixa =?
RCaixa =
SCaixa
1− UCaixa =
SCaixa
1− SCaixaλCaixa =
10
1− 10× 0, 03 = 14, 3
[
minutos
visitas
]
1.7 Construção da Curva de Desempenho da Fila
Uma vez que é possível estabelecer o tempo médio de resposta de uma visita
(Ri) em função do taxa média de chegada (λi), é perfeitamente possível estabelecer
uma relação de desempenho seja definindo um novo tempo médio de resposta ou uma
nova taxa média de chegada. Para melhor compreensão desse estudo, utilizaremos
como exemplo nesta seção o diagrama de sequenciamento ilustrado pela Fig. 1.5 que
representa o monitoramente de uma fila em uma ambiente bancário com seguintes
condições:
Figura 1.5. Diagrama de sequenciamento (histograma) representando o número
de entrada e saída de visitas em uma fila durante um tempo de observação de 5
minutos
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 15
Inicialmente, podemos identificar a utilização máxima de uma fila a fim de iden-
tificar sua saturação.
Se Ui = 1, significa o mesmo que afirmar que devido a hipótese do de equilíbrio
de fluxo Siλi = 1. Portanto, se λ pode representra a capacidade máxima da fila quando
o sistema entrar em colapso. Ou seja, Ui = 100%, então λsat =
1
Si
.
De acordo com o diagrama ilustrado pela Fig. 1.5, temos:
T= 5 minutos
Ai= 9 visitas chegam à fila i (↑)
Ci= 9 visitas saem da fila i (↓)
Bi= T − Ti(0) = 5− 0, 25 = 4, 75 minutos a fila esteve ocupada
λi: taxa média de chegada de visitas à fila i
λi =
Ai
T
=
9
5
= 1, 80
[
visitas
minutos
]
Xi: taxa de processamento da fila i (número de transações completadas por unidade
de tempo)
Xi =
Ci
T
=
9
5
= 1, 80
[
visitas
minutos
]
Si: taxa média de serviço da fila i (número de transações completadas por unidade de
tempo)
Si =
Bi
Ci
=
5
9
= 0, 53
[
minutos
visitas
]
Ui: utilização do servidor i
Ui =
Bi
T
=
4, 75
5
= 0, 95⇒ 95%
ou
Ui = Si × λi = 0, 53× 1, 8 = 0, 95⇒ 95%
Ri: tempo médio de resposta do ambiente i
Ri =
Si
1− Ui =
0, 53
1− 0, 95 =
0, 53
0, 05
= 10, 60
[
minutos
visitas
]
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 16
Wi: tempo médio de espera na fila i
Wi = Ri − Si = 10, 60− 0, 53 = 10, 07
[
minutos
visitas
]
1.7.1 Obtendo as Medições
Uma vez que foi encontrado o valor atual de Si e seus respectivo Tempo de
Resposta (Ri), podemos contruir a curva de desempenho identificando a Carga de
Saturação (λsat) e a Carga designada a partir de um Limite de Nível de Serviço (λLNS)
- neste caso, o Tempo de resposta atribuído ao Limite de Nível de Serviço foi de Ri = 5
min/vis.).
• A Carga de Saturação do Sistema (λsat), corresponde ao valor que leva o sistema
a 100% de utilização;
• O Limite do Nível de Serviço (LNS), representa o valor aceitável normalmente
estipulado pela gerência considerado satisfatório para o sistema;
• A Carga de Capacidade do Sistema (λLNS), corresponde a carga total que o
sistema pode processar sem ultrapassar o Limite do Nível de Serviço.
A Curva de Desempenho é construída adotando os parâmetros acima e sua ite-
ração é calculada utilizando uma progressão representada por ∆ = 0, 1, além das
seguintes equações:
Si = Tempo Médio
λsat =
1
Si
(1.17)
Ri =
Si
1− (Si × λi) (1.18)
onde
(λi = [0, . . . , (λsat − 0, 1)]) assumindo ∆ progressivamente.
Analisando a Curva ilustrada pela Fig. 1.6, é possível encontrar, dado o
LNS = 5, 00 minutos / visita, o λLNS (Capacidade do Sistema para o Limite de Nível
de Serviço de 5 minutos que foi estabelecido) através da seguinte equação:
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 17
Figura 1.6. Curva de Desempenho de Si
Ri ≡ 5, 00
[
visitas
minutos
]
5, 00 =
Si
1− (Si × λLNS)
5, 00− 5, 00SiλLNS = Si
5, 00− Si = 5, 00iλCap
5, 00− Si
5, 00× Si = λLNS
5, 00− 0, 53
5, 00× 0, 53 = λLNS
⇒ λLNS = 1, 69
[
visitas
minutos
]
Portanto, se presumirmos alterações no (Si), adotando os parâmetros Si/2) para
simular o dobro da velocidade do atendimento, garantindo um tempo de resposta duas
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 18
vezes menor em relação ao tempo de resposta utlizado pelo valor original (Si) e (Si×2)
para simular um atendimento com velocidade duas vezes maior, garantindo por sua vez,
uma velocidade mais lenta que a original, basta alterar o valor de Si na fórmula que
produz o Tempo médio de Resposta
Figura 1.7. Gráfico contendo a comparação de três curvas onde cada uma
representa o desempenho de um tipo de atendimento (Siatual), (Si/2) e (Si × 2)
Sobre o tempo do processamento, é fácil notar pela curva gerada, que o tempo
se mantem constante em um período muito maior quando aumentamos a velocidade
do processador (conforme a ilustração da Fig.1.7). Por outro lado, quando simulamos
um tempo de processamento mais lento, essa constante é inversamente proporcional ao
tempo gasto no valor original de (Si).
Quanto a Capacidade do Sistema, ainda relacionado ao tempo de procesamento,
quando a velocidade é dobrada por (Si/2), o número de transações aceitas pelo sistema
sem o estouro do LNS, é mais que o dobro da capacidade aceita pelo processador no
modo Si.
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 19
Com isso, podemos concluir que em algumas situações, o simples aumento da
velocidade do atendimento não se reflete em um aumento proporcional de desempenho.
1.7.2 Simulando novos cenários
1.7.2.1 Simulando alterações no atendimento
1. Comparando com um dispositivo que gaste a metade do tempo, qual seria a
utilização, o tempo médio de resposta e o tempo médio de espera deste ambiente?
SAtual = 0, 53
Snovo =
Satual
2
=
0, 53
2
= Snovo = 0, 27
[
visitas
minutos
]
Para calcular a Utilização:
Ui = Snovoλi = 0, 27× 1, 80 = 0, 49⇒ 49%
Para calcular o Tempo de Resposta:
Ri =
Si
1− Ui =
0, 27
1− 0, 49 = 0, 53
[
minutos
visitas
]
Para calcular o Tempo de Espera:
Wi = Ri − Si ⇒ Wi = 0, 53− 0, 27 = 0, 26
[ seg.
minutos
]
1.7.2.2 Simulando alterações na carga
1. Se a carga aumenta 10%, qual seria a utilização, o tempo médio de resposta e o
tempo médio de espera?
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional20
λAtual = 1, 80
λnovo = λAtual × 1, 10 = 1, 80× 1, 10 = λnovo = 1, 98
[
visitas
minutos
]
Para calcular a Utilização:
Ui = Si × λnovo = 0, 53× 1, 98 = 1, 04⇒ 0, 99⇒ 99% (pois já está saturado)1
Para calcular o Tempo de Resposta:
Ri =
Si
1− Ui =
0, 53
1− 0, 99 = 53, 00
[
minutos
visitas
]
Para calcular o Tempo de Espera:
Wi = Ri − Si ⇒ Wi = 53, 00− 0, 53 = 52, 47
[
minutos
visitas
]
1 Observe que a utilização ultrapassou 100% pois é maior que 1,00. Isso significa que teremos
que buscar a utilização mais próxima de 1,00 que neste caso seria 0,99.
2. O aumento da carga foi monitorado durante 4 meses e foram obtidos os seguintes
dados:
Mês Jan Fev Mar Abr
Carga 1,82 1,83 1,84 1,85
Qual seria o tempo médio de resposta e o tempo médio de espera para o mês de
Maio?
Há de se observar nesta situação que queremos obter uma projeção da carga em função de um
conjunto de dados históricos. Neste caso, podemos utilizar a técnica dos mínimos quadrados tam-
bém conhecida como Técnica da Regressão Linear. Esta técnica consiste em estimar a condicional
(valor esperado) de uma variável y, dados os valores de algumas outras variáveis x.
Lembre-se que ao traçar a curva de desempenho do ambiente, temos que calcular vários parâ-
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 21
metros tais como a carga de saturação, carga de capacidade e etc. Imagine agora que podemos
calcular uma determinada carga futura a partir de uma tendência. Veja a ilustração da Fig.1.8.
Para se estimar o valor esperado, usa-se de uma equação da reta, que determina a relação entre
ambas as variáveis.
y = a+ b(x) (1.19)
Onde:
y : significa a variável explicada (dependente) (é o valor que se quer atingir);
a : é uma constante, que representa a interceptação da reta com o eixo vertical;
x : Variável explicativa (independente), representa o factor explicativo na equação;
b : É outra constante, que representa o declive da reta.
Neste caso, temos que calcular as quatro variáveis a partir das duas fórmulas seguintes:
a = y − b(x) (1.20)
b =
n(
∑
xy)− (∑x)(∑ y)
n(
∑
x2)− (∑x)2 (1.21)
Procedendo aos cálculos em função do histórico apresentado pela carga identifi-
cada no período de Janeiro a Abril, identificamos os valores dos parâmetros que
compôem as equações 1.20 e 1.21:
n = 4, 00 : significa o período de observação (4 meses);∑
xy = 18, 40 : soma das produtos (1× 1, 82) + (2× 1, 83) + (3× 1, 84) + (4× 1, 85);∑
x = 10, 00 : soma do período (1+2+3+4);∑
y = 7, 34 : soma das cargas (1,82 + 1,83 + 1,84 + 1,86);∑
x2 = 30, 0: soma do valor de cada x elevado à segunda potência (12 + 22 + 32 + 42);
(
∑
x)2 = 100, 00 : soma dos valor total de x elevado à segunda potência (102);
x = 2, 50 : significa a média do
∑
= 10;
y = 1, 84 : significa a média do
∑
y = 7, 35;
Agora é possível calcular o valor de Maio
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 22
Figura 1.8. Exemplo de Regressão Linear
Calculando o valor de b
b =
n(
∑
xy)− (∑x)(∑ y)
n(
∑
x2)− (∑x)2 ⇒ 4(18, 4)− (10)(7, 35)4(30)− (100) = 0, 01
Calculando o valor de a
a = y − b(x)⇒ 7, 34− (0, 01)(10) = 1, 84− (0, 01× 2, 5) = 1, 81
Calculando o valor de y, onde x = 5 pois é próximo item do histórico (n+ 1)
y = a+ b(x)⇒ y = 1, 81 + (0, 01)(5) = 1, 86
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 23
Sendo a carga do mês de Maio = 1, 86, podemos encontrar seu respectivo tempo
de resposta
Ri =
Si
1− Ui ⇒ Ri =
Si
1− (Si × λmaio) =
0, 53
1− (0, 53× 1, 86) = 28, 79
[
minutos
visitas
]
Para calcular o Tempo de Espera:
Wi = Ri − Si ⇒ Wi = 28, 79− 0, 53 = 28, 26
[
minutos
visitas
]
1.7.2.3 Simulando Tempo Médio de Resposta e Tempo Médio de Espera
1. Para um tempo médio de resposta que gaste a metade do tempo, qual seria o
tempo médio de atendimento?
Calculando o novo valor de Ri
Ri = 10, 60⇒ Rnovo = Ri
2
=
10, 60
2
= 5, 30
[
minutos
visitas
]
Para encontrar Si temos que derivar a fórmula do tempo médio de resposta:
Rnovo =
Si
1− Ui ⇒ como ⇒ Ui = Siλi ⇒ tem-se:
Rnovo =
Si
1− (Siλi) ⇒ Rnovo(1− (Siλi)) = Si ⇒
Rnovo −RnovoSiλi = Si ⇒ Rnovo = Si +RnovoSiλi ⇒
Rnovo = Si(1 +Rnovoλi)⇒ Si = Rnovo
1 + (Rnovoλi)
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 24
Calculando o novo Si
Si =
Rnovo
1 + (Rnovoλi)
⇒ Si = 5, 30
1 + (5, 30)(1, 80)
⇒ Si = 0, 50
[
minutos
visitas
]
2. Se quero um tempo médio de espera duas vezes menor, qual seria o novo tempo
médio de antendimento?
Calculando o novo tempo de espera
Wi = 10, 07⇒ wnovo = Wi
2
=
10, 07
2
= 5, 04
[
minutos
visitas
]
Para encontrar Si temos que derivar a fórmula do tempo médio de resposta:
Ri =
Si
1− Ui
Sabendo que Ui − Siλi e que Ri = Wi + Si portanto, Wi + Si = Si
1− (Siλi)
Wi + Si =
Si
1− (Siλi) ⇒ (5, 04 + Si) =
Si
1− Si(1, 80) ⇒
(5, 04 + Si)(1− 1, 80Si) = Si ⇒ 5, 04− 9, 07Si + Si − 1, 80S2i = Si ⇒
(5, 04 + Si)(1− 1, 80Si) = Si ⇒ 5, 04− 9, 07Si + Si − 1, 80S2i − Si = 0⇒
5, 04− 9, 07Si + Si// − 1, 80S2i − Si// = 0⇒
−1, 80S2i − 9, 07Si + 5, 04 = 0
1. Modelagem Analítica - Teoria das Filas e Teoria da Análise
Operacional 25
Sabendo que para resolver a expressão devemos utilizar a Fórmula de Báscara
(fórmula quadrática), temos:
∆ = b2 − 4ac (1.22)
x =
−b±√∆
2a
(1.23)
Temos:
∆ = b2 − 4ac⇒ ∆ = (−9, 07)2 − 4(−1, 80)(5, 04)⇒ ∆ = 82, 26 + 36, 29⇒ ∆ = 122, 55
x =
−b±√∆
2a
⇒ −(−9, 72)±
√
122, 55
2(−1, 80) ⇒
9, 07± 11, 07
−3, 60 ⇒
x1 =
9, 07 + 11, 07
−3, 60 ⇒ x = x/ descartado por não haver divisão entre sinais diferentes
x2 =
9, 07− 11, 07
−3, 60 ⇒ x = 0, 56 este é o valor do novo Si
Si = 0, 56
[
minutos
visitas
]
	1 Modelagem Analítica - Teoria das Filas e Teoria da Análise Operacional
	1.1 Definições
	1.2 Sistemas de Filas
	1.3 Componentes de um sistema de filas
	1.4 Análise Operacional em Filas
	1.4.1 Análise Operacional em Filas Isoladas
	1.4.2 Variáveis operacionais básicas
	1.4.3 Variáveis operacionais derivadas
	1.4.4 Sequência de comportamento
	1.5 Leis Operacionais
	1.5.1 Lei da Utilização (Ui)
	1.5.2 Número médio de visitas na Fila i (i)
	1.5.3 Tempo Médio de Resposta (Ri) que cada visita permanece na fila i
	1.5.4 Lei de Little 
	1.6 Teoremas Operacionais
	1.6.1 Hipótese do Equilíbrio de Fluxo (EF)
	1.6.2 Teorema da Taxa de Processamento (EF)
	1.6.3 Teorema do Tempo de Resposta (Ri)
	1.7 Construção da Curva de Desempenho da Fila
	1.7.1 Obtendo as Medições
	1.7.2 Simulando novos cenários