ads:
Milene Souza Castro
Algoritmos para Otimiza¸c˜ao de Filas
Finitas Configuradas em Redes
Disserta¸c˜ao de mestrado apresentada
ao Departamento de Engenharia de
Produ¸c˜ao da Escola de Engenharia da
Universidade Federal de Minas Gerais,
como requisito parcial `a obten¸c˜ao do
t´ıtulo de Mestre em Engenharia de
Produ¸c˜ao.
Orientador: Frederico R. B. Cruz
Universidade Federal de Minas Gerais
Belo Horizonte, mar¸co de 2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
“ALGORITMOS PARA OTIMIZAC¸
˜
AO DE FILAS FINITAS
CONFIGURADAS EM REDES”
Milene Souza Castro
Disserta¸c˜ao submetida `a Comiss˜ao Examinadora designada pelo Colegiado do
Programa de P´os-Gradua¸c˜ao em Engenharia de Produ¸c˜ao da Universidade
Federal de Minas Gerais como requisito parcial para obten¸c˜ao do grau de
Mestre em Engenharia de Produ¸c˜ao.
Aprovada em 28 de mar¸co de 2007.
Por:
Prof. Frederico Rodrigues Borges da Cruz, Dr. (UFMG)
Orientador
Prof. Samuel Vieira Concei¸c˜ao, Dr. (UFMG)
Prof. Ademar Nogueira Nascimento, Dr. (UFBA)
Aprovado pelo Colegiado do PPGEP
Prof. Eduardo Romeiro Filho
Vers˜ao final aprovada por
Professor Orientador
ii
ads:
Sum´ario
Lista de Figuras
vi
Lista de Tabelas vii
Resumo viii
Abstract ix
Lista de S´ımbolos x
1 Introdu¸c˜ao 1
Introdu¸c˜ao 1
1.1 Escopo e Objetivos da Disserta¸c˜ao . . . . . . . . . . . . . . . 4
1.2 Principais Contribui¸c˜oes . . . . . . . . . . . . . . . . . . . . . 5
1.3 Organiza¸c˜ao da Disserta¸c˜ao . . . . . . . . . . . . . . . . . . . 6
2 Conceitos Fundamentais 7
2.1 Aloca¸c˜ao de
´
Areas de Circula¸c˜ao em Filas
´
Unicas . . . . . . . 7
2.1.1 Express˜ao para sistemas markovianos . . . . . . . . . . 7
2.1.2 Express˜ao para sistemas gerais . . . . . . . . . . . . . . 8
2.2 Estimativa de Medidas de Desempenho em Redes de Filas . . 10
2.2.1 Reconfigura¸c˜ao da Rede . . . . . . . . . . . . . . . . . 12
iii
2.2.2 Estima¸c˜ao dos Parˆametros . . . . . . . . . . . . . . . . 12
2.2.3 Elimina¸c˜ao da Realimenta¸c˜ao . . . . . . . . . . . . . . 13
2.3 Simula¸c˜ao a Eventos Discretos . . . . . . . . . . . . . . . . . . 14
2.4 Programa¸c˜ao N˜ao-linear . . . . . . . . . . . . . . . . . . . . . 17
2.4.1 M´etodos de Busca . . . . . . . . . . . . . . . . . . . . 18
2.4.2 M´etodos de Pesquisa . . . . . . . . . . . . . . . . . . . 18
2.4.3 Metaheur´ısticas . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Relaxa¸c˜ao Lagrangeana . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Observa¸c˜oes Finais . . . . . . . . . . . . . . . . . . . . . . . . 23
3 O Problema de Aloca¸c˜ao de
´
Areas de Espera 24
3.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Formula¸c˜ao Matem´atica e Algoritmos de Resolu¸c˜ao . . . . . . 25
3.3 Observa¸c˜oes Finais . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Resultados Experimentais 28
4.1 Rede Dois N´os/Trˆes Servidores . . . . . . . . . . . . . . . . . 29
4.1.1 Configura¸c˜ao Homogˆenea . . . . . . . . . . . . . . . . . 29
4.1.2 Configura¸c˜ao Heterogˆenea . . . . . . . . . . . . . . . . 30
4.2 Redes Trˆes N´os/Cinco Servidores . . . . . . . . . . . . . . . . 32
4.3 Rede Primal/Dual . . . . . . . . . . . . . . . . . . . . . . . . 36
5 Estudo de Caso em Usina Sucro-Alcooleira 38
5.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Aplica¸c˜ao e Desenvolvimento . . . . . . . . . . . . . . . . . . . 39
5.2.1 Modelos de Filas Aplicado `a Ind´ustria Sucro-Alcooleira 42
5.3 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3.2 Levantamento e tratamento de dados . . . . . . . . . . 44
iv
5.3.3 Fonte e taxa de chegada . . . . . . . . . . . . . . . . . 44
5.3.4 Mecanismo e taxa de servi¸co . . . . . . . . . . . . . . . 45
5.4 Modelagem Matem´atica . . . . . . . . . . . . . . . . . . . . . 46
5.4.1 Fila . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.5 Resultados e Discuss˜oes . . . . . . . . . . . . . . . . . . . . . 47
5.6 Conclus˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6 Conclus˜oes e T´opicos para Trabalhos Futuros na
´
Area 52
Referˆencias Bibliogr´aficas 54
v
Lista de Figuras
1.1 Uma fila finita geral com servidores m´ultiplos. . . . . . . . . .
2
1.2 Filas finitas configuradas em rede. . . . . . . . . . . . . . . . . 3
2.1 Representa¸c˜ao gr´afica do m´etodo da expans˜ao generalizado. . 11
2.2 Algoritmo de Powell. . . . . . . . . . . . . . . . . . . . . . . . 19
3.1 Algoritmo de otimiza¸c˜ao proposto. . . . . . . . . . . . . . . . 27
4.1 Topologia dois n´os/trˆes servidores. . . . . . . . . . . . . . . . 29
4.2 Topologia trˆes n´os/cinco servidores. . . . . . . . . . . . . . . . 35
4.3 Rede primal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4 Rede dual. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.1 Representa¸c˜ao do sentido do fluxo de caminh˜oes de cana da
lavoura para a ind´ustria. . . . . . . . . . . . . . . . . . . . . .
41
vi
Lista de Tabelas
4.1 Resultados para a topologia dois n´os/trˆes servidores. . . . . .
31
4.2 Resultados para a topologia dois n´os/trˆes servidores com gargalo. 32
4.3 Resultados para a topologia trˆes n´os/cinco servidores. . . . . . 33
4.4 Resultados adicionais para a topologia trˆes n´os/cinco servidores. 34
4.5 Resultados para a rede primal. . . . . . . . . . . . . . . . . . . 37
4.6 Resultados para a rede dual. . . . . . . . . . . . . . . . . . . . 37
5.1 Taxas de chegada e de servi¸co, por minuto, em fun¸c˜ao do per´ıodo. 47
5.2 Resultados do sistema de filas, em fun¸c˜ao do per´ıodo. . . . . . 49
vii
Resumo
Esta disserta¸c˜ao aborda um dos temas de planejamento mais desafiado-
res, que ´e o problema de otimiza¸c˜ao de redes de filas finitas gerais com ser-
vidores m´ultiplos. Diversos problemas, configurados em topologias diversas,
s˜ao analisados atrav´es de um m´etodo aproximado de estima¸c˜ao de medidas
de desempenho e de um algoritmo iterativo p ara encontrar a aloca¸c˜ao ´otima
das ´areas de espera na rede. O coeficiente de varia¸c˜ao do servi¸co desem-
penhou um papel significativo no espa¸co alocado em redes uniformes e com
gargalos. Resultados computacionais evidenciam a simetria nos padr˜oes de
aloca¸c˜ao que surgem nas redes analisadas. Um estudo de caso numa usina
sucro-alcooleira ilustra o assunto.
Palavras-chave: Servidores m´ultiplos; redes finitas; probabilidades de blo-
queio; aloca¸c˜ao de ´area de espera; otimiza¸c˜ao; a¸c´ucar e ´alcool.
viii
Abstract
This dissertation deals with one of the most complex topological network
design problems, which is the optimization of general service, finite waiting
room, multi-server queueing networks. Several topologies were examined by
means of an approximation method to estimate the performance measures
of these queueing networks and an iterative search methodology to find the
optimal buffer allocation within the network. The coefficient of variation
of the service is shown to be a significant factor in the buffer allocation for
multiple servers in uniform and bottleneck server networks. Computational
results are included to confirm the symmetries in the buffer patterns which
emerge from the networks analyzed. A case study in the field of sugar and
alcohol industry illustrates the the subject.
Keywords: Mu lti-server; finite networks; blocking probabilities; buffer allo-
cation; optimization; sugar and alcohol.
ix
Lista de S´ımbolos
λ
i
:= taxa de chegada `a esta¸c˜ao i;
µ
i
:= taxa de servi¸co m´edia na esta¸c˜ao i;
c
i
:= n´umero de servidores na esta¸c˜ao i;
ρ
i
= λ
i
/(µ
i
c
i
) := intensidade do tr´afego na i-´esima esta¸c˜ao de atendimento
(taxa de utiliza¸c˜ao da esta¸c˜ao);
B
i
:= capacidade da i-´esima esta¸c˜ao de atendimento excluindo-se aqueles
em servi¸co;
K
i
:= capacidade da i-´esima esta¸c˜ao de atendimento incluindo-se aqueles
em servi¸co;
p
K
:= probabilidade de bloqueio para uma fila finita de capacidade K;
n := n´umero de esta¸c˜oes (filas) em uma rede;
c
2
a
= Var(T
a
)/E(T
a
)
2
:= quadrado do coeficiente de varia¸c˜ao do tempo en-
tre chegadas T
a
; ´e utilizado para caracterizar a sua distribui¸c˜ao; neste
trabalho, ser´a sempre igual a 1,0 (distribui¸c˜ao exponencial);
c
2
s
= Var(T
s
)/E(T
s
)
2
:= quadrado do coeficiente de varia¸c˜ao do tempo de
atendimento T
s
; ´e utilizado para caracterizar a sua distribui¸c˜ao (geral);
x
x := vetor de capacidades que cont´em as vari´aveis de decis˜ao no algoritmo
de otimiza¸c˜ao;
Θ := taxa de atendimento m´edia;
Θ
τ
:= taxa de atendimento limiar.
xi
Cap´ıtulo 1
Introdu¸c˜ao
Sempre que h´a incerteza sobre o fluxo de produtos, com uma taxa de chegada
λ, e seu processamento, com uma taxa de servi¸co µ, tem-se como resultado
um sistema de filas, conforme visto na Figura
1.1. O seu arranjo em uma con-
figura¸c˜ao em redes, conforme apresentado n a Figura
1.2, ´e uma generaliza¸c˜ao
natural e relevante, pelos diversos sistemas reais que pode modelar.
H´a, assim, um grande interesse em investigar o comportamento de redes
de filas, sobretudo as do tipo M/G/c/K, aqui representadas segundo a conhe-
cida nota¸c˜ao de Kendall (1953), em que o M indica que as chegadas seguem
um processo markoviano, o G representa um servi¸co que segue uma distri-
bui¸c˜ao geral, o c refere-se ao n ´umero de servidores em paralelo e, por fim,
assume-se que a capacidade m´axima do sistema est´a restrita a K usu´arios,
incluindo aqueles em servi¸co. Redes de filas M/G/c/K, como a apresentada
na Figura
1.2, p odem ser ´uteis para modelar v´arios sistemas reais, tais como
sistemas de produ¸c˜ao em geral, armazenagem, sistemas de telecomunica¸c˜oes,
de transporte, e outros em que as chegadas podem ser razoavelmente mode-
ladas por um processo markoviano, mas n˜ao necessariamente o servi¸co, que
pode seguir uma distribui¸c˜ao geral (Smith & Cruz, 2005).
1
0.0 0.2 0.4 0.6 0.8 1.0
t_a, tempo entre chegadas
densidade de probabilidade
0.0 0.05 0.10 0.15 0.20
t_s, tempo de servico
densidade de probabilidade
Θ
λ
µ
B
C
Figura 1.1: Uma fila finita geral com servidores m´ultiplos.
2
. . .. . .
. . .. . .
divisão
série
1
2
3
. . .
4
5 6
7
n
oo
K
K
K
K
K
K
K
fusão
λ
θ
K
Figura 1.2: Filas finitas configuradas em rede.
3
No contexto desta d isserta¸c˜ao entende-se por otimiza¸c˜ao de redes de fi-
las a minimiza¸c˜ao do espa¸co alocado para espera (do inglˆes buffers) ou do
n´umero de servidores, sujeito ao atendimento com uma taxa de sa´ıda (do
inglˆes thoughput) Θ, n˜ao inferior a um valor limiar, Θ
τ
. A capacidade finita
de tais redes d´a origem ao problema do bloqueio (do inglˆes blocking), que
´e particularmente mais complexo de ser levado em considera¸c˜ao quando as
filas est˜ao configuradas em red es (
Cruz & Smith, 2007). Assim, problemas
instigantes e desafiadores tˆem surgido recentemente nesta ´area (
Smith et al.,
2006).
1.1 Escopo e Objetivos da Disserta¸c˜ao
O tipo de problema de interesse ´e o de desenvolvimento e an´alise de algorit-
mos para aloca¸c˜ao d e ´areas de espera e determina¸c˜ao ´otima do n´umero de
servidores em redes de filas M/G/c/K. Busca-se a aloca¸c˜ao ´otima, o planeja-
mento da topologia ´otima, incluindo a determina¸c˜ao da ordem dos servidores,
bem como a itera¸c˜ao destes dois fatores. A quest˜ao colocada neste trabalho
´e de como pode-se modelar sistemas reais envolvendo incerteza no fluxo de
produtos e no seu processamento, predizer com precis˜ao medidas de desem-
penho dos modelos e planejar adequadamente tais sistemas para que tenham
desempenho ´otimo.
Nesta disserta¸c˜ao procura-se caracterizar e otimizar a topologia de um sis-
tema de redes de filas finitas, bem como propriedades que permitam modelar
e construir algoritmos para otimiz´a-los. Trabalhos anteriores s˜ao estendidos,
nos quais somente redes de filas finitas com um ´unico servidor foram con-
sideradas (
Smith & Cruz, 2005; Duarte, 2005). Assim, para sistemas com
servidores m´ultiplos, precisa-se compreender como estes servidores p odem
4
afetar a aloca¸c˜ao de ´areas de espera e como as v´arias topologias e varia¸c˜oes
sistem´aticas no coeficiente de varia¸c˜ao do tempo de servi¸co influenciam a
configura¸c˜ao ´otima do sistema.
1.2 Principais Contribui¸c˜oes
As contribui¸c˜oes incluem:
• apresenta¸c˜ao de uma bibliografia atualizada na ´area de aloca¸c˜ao de
´areas de circula¸c˜ao e de servidores em redes de filas finitas gerais;
• confirma¸c˜ao da acur´acia de m´etodos aproximados recentemente desen-
volvidos para estimar o desempenho destas redes de filas configuradas
em topologias diversas;
• utiliza¸c˜ao de uma metodologia de busca iterativa, simples e de f´acil
implementa¸c˜ao, para encontrar uma aloca¸c˜ao ´otima para as ´areas de
circula¸c˜ao na rede;
• avalia¸c˜ao do desempenho dos algoritmos recentemente propostos, em
fun¸c˜ao da topologia e do tamanho (n´umero de filas) das redes;
• caracteriza¸c˜ao e modelagem de sistemas reais e otimiza¸c˜ao da sua es-
trutura.
• apresenta¸c˜ao de um estudo de caso numa usina sucro-alcooleira, que
ilustra o assunto.
5
1.3 Organiza¸c˜ao da Disserta¸c˜ao
A organiza¸c˜ao ´e como se segue. No cap´ıtulo
2 apresentam-se conceitos fun-
damentais, relevantes para a melhor compreens˜ao dos problemas de aloca¸c˜ao
de ´area de espera em filas finitas configuradas em redes. A formaliza¸c˜ao do
problema de alo ca¸c˜ao de ´areas de circula¸c˜ao, como um problema de pro-
grama¸c˜ao matem´atica inteira estoc´astica, ´e apresentada no cap´ıtulo
3, jun-
tamente com os algoritmos de resolu¸c˜ao. No cap´ıtulo
4 apresentam-se resul-
tados dos experimentos computacionais realizados. O estudo de caso numa
usina sucro-alcooleira ´e apresentado no cap´ıtulo
5. Finalmente, no cap´ıtulo 6
s˜ao apresentadas as principais conclus˜oes obtidas, juntamente com t´opicos
para trabalhos futuros.
6
Cap´ıtulo 2
Conceitos Fundamentais
2.1 Aloca¸c˜ao de
´
Areas de Circula¸c˜ao em Filas
´
Unicas
2.1.1 Express˜ao para sistemas markovianos
A probabilidade de bloqueio para uma fila finita de capacidade K do tipo
M/M/1/K ´e aquela probabilidade de haver exatamente K entidades (por
exemplo, usu´arios, clientes, produtos etc.) no sistema. Sua express˜ao ´e
bem conhecida de qualquer livro b´asico de processos estoc´asticos (veja, por
exemplo,
Gross & Harris, 1985):
p
K
=
(1 − ρ)ρ
K
1 − ρ
K+1
,
para ρ = 1.
Pode-se ent˜ao expressar K em fun¸c˜ao de ρ e p
K
e obter uma express˜ao
7
fechada para a aloca¸c˜ao ´otima de ´areas de espera:
K =
ln
p
K
1−ρ+p
K
ρ
ln(ρ)
, (2.1)
para ρ < 1, em que ⌈x⌉ ´e o menor inteiro n˜ao inferior a x.
Resultados anal´ıticos para sistemas M/M/c/K produzem a seguinte ex-
press˜ao para p
K
:
p
K
=
1
c
K−c
c!
λ
µ
K
p
0
,
em que, para λ/(cµ) = 1:
p
0
=
c−1
n=0
1
n!
λ
µ
n
+
(λ/µ)
c
c!
1 − [λ/(cµ)]
K−c+1
1 − λ/(cµ)
−1
.
A express˜ao composta para sistemas M/M/c/K ´e dada por:
p
K
=
λ
µ
K
(c!)
−1
(c
K−c
)
−1
e
λ
µ
Γ(c,
λ
µ
)Γ
−1
(c) +
(
λ
µ
)
c
1−
(
λ
cµ
)
K−c+1
c!
(
1−
λ
cµ
)
.
Como a probabilidade de bloqueio ´e muito complexa, n˜ao se pode ex-
pressar o valor de K como feito anteriormente, sem antes fixar o valor de c.
Assim, fixando-se c = 1, obt´em-se exatamente a mesma express˜ao anterior-
mente desenvolvida para sistemas M/M/1/K.
2.1.2 Express˜ao para sistemas gerais
Para sistemas gerais com servidores m´ultiplos, aproxima¸c˜oes come¸caram a
surgir essencialmente a partir do trabalho de
Gelenbe (1975), com seu m´etodo
8
baseado em t´ecnicas de difus˜ao. Tamb´em express˜oes baseadas em distri-
bui¸c˜oes estacion´arias de sistemas infinitos surgem, com destaque para os tra-
balhos de
Schweitzer & Konheim (1978), Tijms (1994b) e Sakasegawa et al.
(1993). Finalmente surgem as aproxima¸c˜oes a dois momentos de Tijms (1992,
1994a), Kimura (1996a,b) e Smith (2003).
Smith (2003) mostrou que uma vez que haja dispon´ıvel uma express˜ao
fechada para a ´area de circula¸c˜ao, B = K − 1, para um sistema M/M/c/K,
´e poss´ıvel utilizar um esquema de aproxima¸c˜ao a d ois momentos baseado nos
trabalhos de
Tijms (1992, 1994a) e Kimura (1996a,b) para desenvolver uma
express˜ao para a aloca¸c˜ao ´otima em sistemas com servi¸co geral, M/G/c/K.
Esta express˜ao, baseada na aloca¸c˜ao ´otima de sistemas markovianos, deno-
tada por B
M
, ´e:
B
Kimura
ǫ
(c
2
s
) = B
M
+
(c
2
s
− 1)
2
√
ρB
M
,
´
E importante ressaltar que a express˜ao de
Kimura (1996a,b) estima ape-
nas a ´area de circula¸c˜ao, excluindo-se aqueles usu´arios em servi¸co. Para
c = 1 e c
2
s
arbitr´ario, tem-se a seguinte aproxima¸c˜ao para a ´area de espera
´otima para sistemas M/G/1/K desenvolvida por
Smith (2003), baseada na
aloca¸c˜ao ´otima de sistemas markovianos, B
M
, apresentada na Eq. (
2.1), sub-
tra´ıda do espa¸co do servidor ´unico:
B
Smith
ǫ
(c
2
s
) =
ln
p
K
1−ρ+p
K
ρ
ln(ρ)
K
M
−1
+
(c
2
s
− 1)
2
√
ρ
ln
p
K
1−ρ+p
K
ρ
ln(ρ)
K
M
−1
,
resultando, ap´os fatora¸c˜ao e rearranjo dos termos, em:
B
Smith
ǫ
(c
2
s
) =
ln
p
K
1−ρ+p
K
ρ
− ln(ρ)
2 +
√
ρc
2
s
−
√
ρ
2 ln(ρ)
,
9
a qual, fazendo-se c
2
s
= 1, reduz-se exatamente `a Eq. (2.1), para sistemas
M/M/c/K, com c = 1, a menos do espa¸co do servidor.
Pode-se prosseguir com este processo de desenvolvimento de p
K
para di-
ferentes valores de c e ent˜ao obter formas fechadas aproximadas para a ´area
de espera ´otima em sistemas M/G/c/K. O leitor interessado em detalhes
pode consultar o artigo de
Smith (2003).
Esta disserta¸c˜ao restringe-se ao processos de chegada markovianos, uma
vez que estes representam uma boa aproxima¸c˜ao para in´umeras situa¸c˜oes
pr´aticas e tamb´em por ser poss´ıvel a deriva¸c˜ao de resultados exatos para
alguns casos particulares destes sistemas. Resultados para chegadas gerais
s˜ao escassos e limitados a servidores ´unicos (
Kim & Chae, 2003).
Como observa¸c˜ao final, ´e importante mencionar a seguinte liga¸c˜ao exis-
tente entre a probabilidade de bloqueio p
K
e a taxa de atendimento Θ(x):
Θ(x) = λ(1 − p
K
),
sendo esta uma das mais importantes medidas de desempenho.
2.2 Estimativa de Medidas de Desempenho
em Redes de Fil as
O problema de determina¸c˜ao das probabilidades de bloqueio, e, conseq¨uente-
mente, da taxa de atendimento, fica bem mais complexo em filas finitas confi-
guradas em redes. O M´etodo da Expans˜ao Generalizado (MEG) ´e uma forma
robusta e eficaz para determina¸c˜ao aproximada de medidas de desempenho
em redes de filas finitas. O MEG foi desenvolvido p or Kerbache & Smith
(1987) e tem uma longa hist´oria de aplica¸c˜oes bem sucedidas a diversas si-
tua¸c˜oes similares. Descrito em detalhes em v´arios artigos, o m´etodo ´e uma
10
combina¸c˜ao de tentativas repetidas e decomposi¸c˜ao n´o-a-n´o. Considere uma
rede ´unica, com capacidade finita K (incluindo os servidores). Este n´o essen-
cialmente oscila entre dois estados: (i) uma fase saturada, com exatamente
K usu´arios, ou (ii) uma fase n˜ao-saturada, caso contr´ario. Na fase n˜ao-
saturada, o n´o j tem no m´aximo K − 1 usu´arios (em servi¸co ou n a ´area de
espera). Por outro lado, quando o n´o est´a na fase saturada, nem mais um
´unico usu´ario pode juntar-se `a fila. A Figura
2.1 representa graficamente
estes dois cen´arios.
✲
M/G/c
i
/K
i
✲
✒✑
✓✏
✲
i
M/G/c
j
/K
j
✲
✒✑
✓✏
✲
j
✲ ✲
M/G/c
i
/K
i
✲
✒✑
✓✏
✲
i
M/G/∞
✲
✒✑
✓✏
✲
h
j
M/G/c
j
/K
j
✲
✒✑
✓✏
✲
j
✻
❄
λ
i
θ
j
λ
i
λ
j
λ
h
j
λ
h
j
(1 − p
′
K
j
)
θ
j
λ
j
(1 − p
K
j
)
Figura 2.1: Representa¸c˜ao gr´afica do m´etodo da expans˜ao generalizado.
O MEG possui os seguintes est´agios:
Est´agio I: Reconfigura¸c˜ao da rede;
Est´agio II: Estima¸c˜ao dos parˆametros;
Est´agio III: Elimina¸c˜ao da realimenta¸c˜ao.
Ser˜ao dados agora maiores detalhes sobre o MEG, que podem tamb´em
ser encontrados no artigo de
Kerbache & Smith (1987). O objetivo central
do m´etodo ´e prover um esquema aproximado para atualizar a taxa de servi¸co
m´edia dos n´os que possuem outros n´os com capacidade finita `a sua frente
11
(por exemplo, o n´o i, na Figura 2.1), de forma a levar em considera¸c˜ao o
bloqueio entre n´os finitos adjacentes, isto ´e:
˜µ
−1
i
= µ
−1
i
+ p
K
j
(µ
′
h
j
)
−1
. (2.2)
2.2.1 Reconfigura¸c˜ao da Rede
A cada n´o com capacidade finita adiciona-se um n´o artificial, como mostra a
Figura
2.1. O fluxo ´e redirecionado para esse n´o, quando o pr´oximo n´o estiver
com sua capacidade m´axima. Em virtude disso, sabe-se que a probabilidade
de uma entidade entrar no n´o j ´e (1 −p
K
j
), enquanto que a de ser bloqueado
´e p
K
j
. Tais espa¸cos artificiais s˜ao modelados como uma fila M/G/∞, fazendo
com que n˜ao haja nenhuma espera. Se ap´os o servi¸co no n´o artificial o n´o j
estiver ainda ocupado, o usu´ario ser´a bloqueado com uma nova probabilidade
p
′
K
j
retornando novamente ao n´o artificial h
j
. Caso contr´ario, prosseguir´a
para a pr´oxima fila com probabilidade (1 − p
′
K
j
).
2.2.2 Estima¸c˜ao dos Parˆametros
Nesta fase estimam-se os parˆametros envolvidos na an´alise. Desse modo,
o valor de p
K
j
pode ser determinado de forma anal´ıtica, enquanto que o
p
′
K
j
´e determinado a partir de m´etodos aproximados. Uma aproxima¸c˜ao
desenvolvida por Labetoulle & Pujolle (1980) para calcular p
′
K
j
, utilizando
t´ecnicas de difus˜ao, ´e a seguinte:
p
′
K
j
=
µ
j
+ µ
h
j
µ
h
j
−
λ
(r
K
j
2
− r
K
j
1
) − (r
K
j
−1
2
− r
K
j
−1
1
)
µ
h
j
(r
K
j
+1
2
− r
K
j
+1
1
) − (r
K
j
2
− r
K
j
1
)
−1
,
sendo r
1
e r
2
ra´ızes da equa¸c˜ao λ − (λ − µ
h
j
− µ
j
)x + µ
h
j
x
2
= 0, em que
12
λ = λ
j
− λ
h
j
(1 − p
′
K
j
)
e
λ
j
= λ
i
(1 − p
K
j
) = λ
i
− λ
h
j
.
Usando a teoria da renova¸c˜ao, a taxa de servi¸co no n´o artificial ´e:
µ
h
j
=
2µ
j
1 + σ
2
j
µ
2
j
,
em que σ
2
j
´e a variˆancia do tempo de servi¸co.
2.2.3 Elimina¸c˜ao da Realimenta¸c˜ao
Nesse momento realiza-se uma reconfigura¸c˜ao do n´o artificial h
j
, de maneira
que as dependˆencias nos processos de chegada causadas por visitas repetidas
a esse n´o sejam retiradas. Assim, quando o la¸co de retorno ´e eliminado, a
taxa de servi¸co nesse local ´e recomputada da seguinte forma:
µ
′
h
j
= (1 − p
′
K
j
)µ
h
j
.
Finalmente, a m´ed ia de tempo de servi¸co que uma entidade gasta entre
os n´os i e j ´e dada pela Eq.
2.2, e repetida aqui para maior clareza:
˜µ
−1
i
= µ
−1
i
+ p
K
j
(µ
′
h
j
)
−1
.
Em outras palavras, primeiramente a rede ´e expandida, acrescentando-se
antes de cada n´o finito um n´o artificial de espera h
j
de capacidade ilimitada,
para receber as entidades que forem bloqueadas. Em seguida, os parˆametros
do n´o de espera s˜ao estimados . Finalmente, a realimenta¸c˜ao ´e eliminada,
13
a taxa de servi¸co ´e atualizada de acordo com a Eq. (2.2) e o arco de reali-
menta¸c˜ao e o n´o de espera artificial h
j
s˜ao eliminados. Completado estes trˆes
est´agios, tem-se uma rede expandida que pode ser utilizada para o c´alculo
das medidas de desempenho para a rede original. Como uma t´ecnica de de-
composi¸c˜ao, este m´etodo permite sucessivas adi¸c˜oes de n´os de espera para
cada n´o finito, estima¸c˜ao de parˆametros e subseq¨uente elimina¸c˜ao do n´o de
espera. Uma observa¸c˜ao importante sobre o processo ´e que n˜ao se modificam
fisicamente as r edes, mas t˜ao somente utiliza-se a expans˜ao como um artif´ıcio
para implementa¸c˜ao computacional do m´etodo de aproxima¸c˜ao. O resultado
final deste processo sofisticado ´e a obten¸c˜ao de uma aproxima¸c˜ao para Θ(x)
bastante precisa (
Kerbache & Smith, 1987).
2.3 Simula¸c˜ao a Eventos Discretos
Uma das mais tradicionais t´ecnicas da pesquisa operacional, a simula¸c˜ao
de sistemas ´e uma das ferramentas mais importantes e ´uteis para anali-
sar a opera¸c˜ao de sistemas complexos, b em como projetar novos sistemas
(Kelton et al., 2001). Uma grande vantagem da simula¸c˜ao ´e permitir que
sistemas reais sejam estudados, sem modific´a-los. Assim, alternativas de
mudan¸ca para o sistema po dem ser experimentadas e estudadas antes de
qualquer mudan¸ca n o sistema f´ısico. Modelos de simula¸c˜ao possuem, de
forma combinada ou isolada, os seguintes elementos (Kelton et al., 2001):
Entidades: As entidades podem ser, por exemplo, pe¸cas que necessitam ser
processadas. Elas s˜ao criadas quando chegam ao sistema, movem-se
atrav´es de filas, s˜ao processadas por uma m´aquina, e ent˜ao deixam
o sistema, sendo descartadas do modelo de simula¸c˜ao. As simula¸c˜oes
envolvem entidades, que se movem, mudam de estado, afetam e s˜ao
14
afetadas por outras entidades e estados do sistema, interferindo nas
medidas de desempenho do sistema.
Atributos: Um atributo ´e uma caracter´ıstica da entidade, mas com um
valor espec´ıfico que a difere das demais entidades. Por exemplo, uma
pe¸ca pode ter atributos tais como tempo de chegada ao sistema, prazo
de entrega, prioridade e cor. Para individualizar as entidades, anexam-
lhes atributos.
Vari´aveis: Uma vari´avel ´e uma ´area de mem´oria do computador destinada a
armazenar uma parcela da informa¸c˜ao que reflete alguma caracter´ıstica
do sistema em estudo. Pode-se ter diferentes vari´aveis no modelo, mas
cada uma ´e ´unica. As vari´aveis s˜ao acess´ıveis a todas as entidades e
muitas podem ser alteradas por qualquer entidade. As vari´aveis s˜ao
usadas para muitos prop´ositos diferentes. Por exemplo, pode-se criar
uma vari´avel denominada n´umero
no sistema cujo valor ´e o n´umero
total de pe¸cas, incluindo aquelas na fila e aquelas em processo numa
m´aquina. Quando uma pe¸ca entra no sistema para ser processada,
adiciona-se 1 (um) `a vari´avel n´umero
no sistema e, quando uma pe¸ca
´e conclu´ıda, subtrai-se 1 (um) da vari´avel n´umero
no sistema.
Recursos: Um recurso pode representar, por exemplo, um grupo de v´arios
servidores individuais, cada um sendo uma unidade de tal recurso. Isto
´e ´util na modelagem, por exemplo, de v´arios atendentes paralelos e
idˆenticos em uma agˆencia banc´aria. As entidades frequentemente com-
petem umas com as outras pelo servi¸co de um recurso, que representam,
por exemplo, pessoal, equipamento ou espa¸co em uma ´area limitada
para estocagem. Uma entidade requisita um recurso quando dispon´ıvel
e o libera quando conclu´ıdo.
15
Filas: F ilas s˜ao locais de espera. Quando uma entidade n˜ao pode seguir em
frente no processo — talvez porque precise de requisitar um recurso
que esteja ocupado por uma outra entidade — esta necessita ent˜ao de
uma fila.
´
E parte da modelagem decidir como lidar com uma entidade
que chega a uma fila que j´a esteja cheia.
Acumuladores de Estat´ısticas: S˜ao vari´aveis espec´ıficas para armazena-
mento dos estados da simula¸c˜ao ao longo do tempo. Para que as medi-
das de desempenho do sistema simulado sejam calculadas, ´e necess´ario
que os valores intermedi´arios dos acumuladores de estat´ısticas sejam
acompanhados, `a medida que a simula¸c˜ao caminha. Por exemplo, pode-
se acompanhar o n´umero de partes produzidas ao longo do t empo, o
tempo total gasto na fila ao longo do tempo, o maior tempo gasto na
fila at´e ent˜ao, a integral da fun¸c˜ao que descreve o tamanho da fila ao
longo do tempo at´e ent˜ao, entre outras. Todos esses acumuladores pre-
cisam ser iniciados com 0 (zero) e quando alguma evento acontece na
simula¸c˜ao precisam ser atualizados os acumuladores afetados, de forma
apropriada.
Eventos: O evento ´e uma ocorrˆencia que muda o estado no sistema simu-
lado, em um instante do tempo e que po de alterar os atributos das enti-
dades, as vari´aveis ou os acumuladores de estat´ısticas. Na simula¸c˜ao a
eventos discretos basicamente tudo est´a centrado em torno de eventos.
Normalmente, tˆem- se os seguintes tipos de eventos:
chegada: Uma nova pe¸ca chega ao sistema para ser processada;
partida: Uma nova pe¸ca ´e conclu´ıda na m´aquina e deixa o sistema;
final: A simula¸c˜ao ´e conclu´ıda ap´os t
f
segundos.
16
Rel´ogio da Simula¸c˜ao:
´
E uma vari´avel que mant´em o tempo corrente da
simula¸c˜ao. Ao contr´ario do tempo real, o rel´ogio da simula¸c˜ao n˜ao
passa continuamente por todos os valores, mas passa da ocorrˆencia de
um evento at´e a ocorrˆencia do pr´oximo evento. Desde que nada ocorre
entre dois eventos, n˜ao h´a porquˆe gastar tempo de processamento para
simular o sistema n este intervalo.
In´ıcio e Fim: S˜ao eventos que marcam o in´ıcio e a conclus˜ao da simula¸c˜ao.
Importantes, mas muitas vezes desprezadas, s˜ao quest˜oes a respeito de
como uma simula¸c˜ao inicia-se e como conclui-se. Precisam-se determi-
nar as condi¸c˜oes de in´ıcio apropriadas, se o sistema inicia-se vazio ou
em regime permanente. Tamb´em ´e necess´ario determinar por quanto
tempo a simula¸c˜ao durar´a, se deve parar porque um tempo particular
foi alcan¸cado (por exemplo, 15 minutos de simula¸c˜ao) ou se porque
uma determinada condi¸c˜ao foi atingida (por exemplo, 20 pe¸cas foram
fabricadas).
2.4 Programa¸c˜ao N˜ao-linear
Muitos dos problemas relevantes de otimiza¸c˜ao podem ser vistos como pro-
blemas de programa¸c˜ao n˜ao-linear (PNL). Da larga experiˆencia relatada na
literatura da ´area, sabe-se que os PNL’s n˜ao possuem um m´etodo geral de
resolu¸c˜ao (veja, por exemplo,
Mateus & Luna, 1986, e as referˆencias apresen-
tadas). Existem v´arios algoritmos que se prop˜oem a solucionar PNL’s. No en-
tanto, a grande maioria deles ´e voltada para modelos espec´ıficos. Mencionam-
se a seguir, alguns m´etodos, entre os mais conhecidos, para resolver PNLs
irrestritos:
17
min f(x),
sujeito a:
x ∈ R
n
.
2.4.1 M´etodos de Busca
Dentre aqueles que utilizam derivadas (conhecidos tamb´em como m´etodos
de busca), pode-se citar o m´etodo m´etodo do gradiente, tamb´em conhecido
por m´etodo de Cauchy ou m´aximo declive (do inglˆes steepest descent).
´
E
um m´etodo bastante conhecido e, por sua simplicidade, ´e bastante aplicado,
apesar da convergˆencia poder ser muito lenta. Tem-se tamb´em o m´etodo de
Newton, que aproxima a fun¸c˜ao f(x) a ser minimizada por uma quadr´atica.
O algoritmo necessita de um ponto de partida pr´oximo da solu¸c˜ao, pois caso
contr´ario poder´a divergir. O m´etodo de Newton pode n˜ao ser adequado
para os casos em que n ´e grande ou o c´alculo anal´ıtico de derivadas ´e dif´ıcil.
Maiores detalhes sobre os m´etodos de busca podem ser obtidos no livro de
Bazaraa et al. (1990).
2.4.2 M´etodos de Pesquisa
Dentre os m´etodos que n˜ao u sam o c´alculo das derivadas, denominados
m´etodos de pesquisa, podem-se mencionar v´arios. Apesar de serem lentos na
resolu¸c˜ao de problemas simples, podem desempenhar um papel satisfat´orio
para situa¸c˜oes mais complexas. Um dos mais utilizados ´e o m´etodo de Powell,
Figura
2.2. Bem sucedido na resolu¸c˜ao de problemas de otimiza¸c˜ao em ´areas
de espera em filas finitas (
Smith & Cruz, 2005; Smith et al., 2006), o m´etodo
18
algoritmo
leia G(N, A, P ), λ, µ, x
(0)
e ε
/* escolha conjunto de di re¸c˜oes conjugadas */
escolha d
(1)
, . . . , d
(n)
x
(opt)
← x
(0)
repita
x
(1)
← x
(opt)
para i = 1 at´e n fa¸ca
/* busca unidirecional */
x
(i+1)
← arg min
γ∈R
f
x
(i)
+ γd
(i)
fim para
x
(n+2)
← 2x
(n+1)
− x
(1)
se f(x
(n+2)
) ≥ f(x
(1)
) ent˜ao
x
(opt)
← x
(n+1)
sen˜ao
x
(opt)
← arg min
γ∈R
f
x
(n+1)
+ γ(x
(n+1)
− x
(1)
)
escolha novo d
(1)
, . . . , d
(n)
fim se
at´e x
(opt)
− x
(1)
< ε
imprima x
(opt)
fim algoritmo
Figura 2.2: Algoritmo de Powell.
19
de Powell ´e um m´etodo de dire¸c˜oes conjugadas, as quais s˜ao geradas a cada
itera¸c˜ao, de forma a minimizar uma fun¸c˜ao n˜ao-linear f(x) atrav´es de su-
cessivas buscas uni-direcionais de um ponto de partida inicial x
0
ao longo de
um conjunto de dire¸c˜oes conjugadas. Essas dire¸c˜oes conjugadas s˜ao geradas
dentro do pr´oprio procedimento. O m´etodo de Powell baseia-se na id´eia de
que se um m´ınimo de uma fun¸c˜ao f(x) ´e encontrado ao longo de n dire¸c˜oes
conjugadas em determinado est´agio da procura, ent˜ao uma etapa adequada
´e realizada em cada dire¸c˜ao. Al´em do mais, a etapa global desde o in´ıcio at´e
a n-´esima etapa ´e conjugada para todas as n subdire¸c˜oes da procura.
2.4.3 Metaheur´ısticas
Metaheur´ısticas s˜ao m´etodos modernos de pesquisa, computacionalmente in-
tensivos, que usam uma s´erie de regras gerais que determinam solu¸c˜oes vi´aveis
do problema, sendo algumas delas, eventualmente, pr´oximas da solu¸c˜ao
´otima. T´ecnicas de solu¸c˜ao t´ıpicas nessa ´area incluem o simulated annealing,
a pesquisa tabu e algoritmos gen´eticos (
Spinellis et al., 2000). A principal
vantagem das metaheur´ısticas sobre os m´etodos de pesquisa tradicionais ´e a
possibilidade de atingir pontos ´otimos globais. Por outro lado, eles muitas
vezes n˜ao utilizam a estrutura especial do problema, que pode estar d is-
pon´ıvel na fun¸c˜ao objetivo ou nas restri¸c˜oes, para guiar sua pesquisa, sendo
necess´ario sintonias finas p ara produzir solu¸c˜oes para uma situa¸c˜ao espec´ıfica.
Maiores detalhes po d em ser encontrados no livro de
Reeves (1993).
2.5 Relaxa¸c˜ao Lagrangeana
A relaxa¸c˜ao ´e uma t´ecnica largamente empregada na resolu¸c˜ao de problemas
de otimiza¸c˜ao (
Lemar´echal, 2003). A relaxa¸c˜ao lagrangeana ´e baseada na
20
observa¸c˜ao de que muitos problemas dif´ıceis de programa¸c˜ao matem´atica
inteira podem ser modelados como um problema relativamente simples, mas
complicado por um subconjunto de restri¸c˜oes. Para explorar este fato, cria-se
um problema lagrangeano no qual as restri¸c˜oes complicantes s˜ao substitu´ıdas
como um termo de penalidade na fun¸c˜ao objetivo, envolvendo o produto de
alguma pequena viola¸c˜ao dessas restri¸c˜oes e as resp ectivas vari´aveis duais.
O problema lagrangeano geralmente ´e mais f´acil de ser resolvido, al´em de
sempre gerar um limite inferior (para um problema de minimiza¸c˜ao) para o
´otimo do problema original.
Primeiramente ser´a considerado um problema de programa¸c˜ao inteira da
seguinte forma:
Z = min cx,
sujeito a:
Ax ≥ b,
Dx ≥ e,
x ∈ N
n
,
em que x ´e um vetor n × 1, b e um vetor m × 1 e todas as demais matrizes
tˆem dimens˜oes adequadas.
Assume-se que as restri¸c˜oes do problema possam ser particionadas em dois
sub-conjuntos, Ax ≥ b e Dx ≥ e, tal que o problema de programa¸c˜ao inteira
fique consideravelmente mais simples de resolver, caso a restri¸c˜ao Ax ≥ b
seja removida. Para criar um problema lagrangeano, define-se um vetor
de dimens˜ao m de multiplicadores u e adicionamos o termo n˜ao-positivo
u(b − Ax) `a fun¸c˜ao objetivo, para obter:
21
min cx + u(b − Ax),
sujeito a:
Dx ≥ e,
x ∈ N
n
,
u ∈ R
m
.
´
E claro que o valor ´otimo do problema relaxado, para um dado valor do
vetor u, ´e um limite inferior de Z, uma vez que apenas adicionou-se um
termo n˜ao-positivo `a fun¸c˜ao objetivo. Neste ponto, criou-se um problema
lagrangeano, pela remo¸c˜ao das restri¸c˜oes Ax ≥ b, para obter:
Z
D
(u) = min cx + u(b − Ax),
sujeito a:
Dx ≥ e,
x ∈ N
n
,
u ∈ R
m
.
Notando-se que a remo¸c˜ao da restri¸c˜ao Ax ≥ b n˜ao pode aumentar
o valor ´otimo do problema original, Z
D
(u) pode ser visto como um limite
inferior para Z. Adicionalmente, assume-se que o problema lagrangeano ser´a
relativamente mais f´acil de resolver do que o problema original.
22
2.6 Observa¸c˜oes Finais
Conceitos b´asicos sobre sistemas estoc´asticos, t´ecnicas de simula¸c˜ao e re-
solu¸c˜ao de problemas de programa¸c˜ao n˜ao linear foram apresentados resumi-
damente, com o objetivo de que fique mais claro a defini¸c˜ao do problema de
otimiza¸c˜ao de redes de filas finitas, conforme ser´a feito a seguir.
23
Cap´ıtulo 3
O Problema de Aloca¸c˜ao de
´
Areas de Espera
3.1 Introdu¸c˜ao
O problema de aloca¸c˜ao de ´areas de espera em filas finitas configuradas em
redes ´e bastante desafiador e tem recebido uma aten¸c˜ao constante dos pes-
quisadores. Abordagens exatas tˆem sido limitadas aos casos de distribui¸c˜oes
exponenciais, mas mesmo nestes casos o tratamento ´e limitado a redes de
pequeno tamanho, u ma vez que o espa¸co de estados nas cadeias de Mar-
kov envolvidas explode, al´em de que freq¨uentemente o inter-relacionamento
probabil´ıstico entre as filas fica muito complexo e de dif´ıcil compreens˜ao.
Servi¸cos n˜ao-exponenciais nas redes n˜ao tornam os problemas mais f´aceis,
uma vez que a propriedade de falta de mem´oria da distribui¸c˜ao exponencial
deixa de valer. Assim, o desenvolvimento de aproxima¸c˜oes tem sido conside-
rado uma estrat´egia razo´avel e pr´atica.
24
3.2 Formula¸c˜ao Matem´atica e Algoritmos de
Resolu¸c˜ao
Considera-se aqui a seguinte formula¸c˜ao de programa¸c˜ao matem´atica para o
problema de otimiza¸c˜ao, que tamb´em foi aquela utilizada por
Duarte (2005),
Smith & Cruz (2005) e Smith et al. (2006):
Z = min
f(x) =
∀i
x
i
, (3.1)
sujeito a:
Θ(x) ≥ Θ
τ
, (3.2)
x
i
∈ {1, 2, . . .}, ∀i, (3.3)
que minimiza a aloca¸c˜ao total de ´areas de espera,
∀i
x
i
, restrito a garantir
uma taxa m´ınima de atendimento, Θ
τ
. Nesta formula¸c˜ao, Θ
τ
´e a taxa de
atendimento limiar e x
i
≡ K
i
´e a vari´avel de decis˜ao, que ´e a ´area de aloca¸c˜ao
total na i-´esima fila, incluindo-se aqueles em servi¸co.
Os problemas de aloca¸c˜ao de ´areas de espera possuem uma longa e
detalhada hist´oria, com uma grande riqueza de autores que abordaram
o tema. V´arios algoritmos baseados em programa¸c˜ao dinˆamica, em me-
taheur´ısticas, em simula¸c˜ao ou em m´etod os de busca surgiram, com des-
taque para as abordagens por programa¸c˜ao dinˆamica de
Kubat & Sumita
(1985) e Yamashita & Onvural (1994), o algoritmo de simulated annealing
de
Spinellis et al. (2000), os m´etodos baseados em simula¸c˜ao de Soyster et al.
(1979), Baker et al. (1990) e Harris & Powell (1999), e, finalmente, os algorit-
mos baseados em busca de
Altiok & Stidham (1983) e, mais recentemente,
o m´etodo de
Smith & Cruz (2005) e Smith et al. (2006). Uma vez que a
25
aloca¸c˜ao ´otima de ´areas de espera ´e um problema de programa¸c˜ao inteira
estoc´astica, as abordagens heur´ısticas tendem a ser mais bem sucedida que
os algoritmos que garantem a otimalidade. Para este problema, portanto,
necessita-se de um procedimento de otimiza¸c˜ao robu sto e acurado, acoplado
a uma forma efetiva de determina¸c˜ao de medidas de desempenho do sistema.
Isto ´e que buscamos.
O problema aqui examinado ´e o da determina¸c˜ao ´otima de ´areas de espera
em sistemas de filas M/M/c/K e M/G/c/K configuradas em redes, dado pe-
las Eq. (3.1)–(3.3). Uma forma de incorporar a restri¸c˜ao de taxa de servi¸co
m´ınima ´e atrav´es de uma fun¸c˜ao penalidade, tal como a relaxa¸c˜ao lagran-
geana. Assim, definindo-se uma vari´avel dual α e relaxando-se a restri¸c˜ao
Eq. (
3.2), o seguinte problema penalizado surge:
Z
α
= min
∀i
x
i
+ α
Θ
τ
− Θ(x)
≤0
, (3.4)
sujeito a:
x
i
∈ {1, 2, . . .}, ∀i, (3.5)
α ≥ 0. (3.6)
Note que Θ
τ
pode ser previamente especificado e servir como taxa de
chegada λ para um algoritmo aproximado para determina¸c˜ao de med idas de
desempenho como o MEG, que fornecer´a o taxa de sa´ıda resultante Θ(x).
Assim, o termo α
Θ
τ
− Θ(x)
ser´a n˜ao-positivo para qualquer x vi´avel e
ser´a uma penalidade para a fun¸c˜ao objetivo relacionada com a diferen¸ca
entre a taxa de atendimento pr´e-determinada λ = Θ
τ
e a taxa de servi¸co
efetivamente alcan¸cada Θ(x). Desta forma, segue que Z
α
≤ Z, sendo Z
α
um
26
limite inferior para a solu¸c˜ao ´otima do problema, Z.
A relaxa¸c˜ao lagrangeana do problema pr imal, Z
α
, acrescida de uma re-
laxa¸c˜ao adicional na integralidade das restri¸c˜oes para x
i
, torna-se um pro-
blema cl´assico de otimiza¸c˜ao irrestrita. Neste formula¸c˜ao em p articular,
as vari´aveis x
i
, s˜ao as vari´aveis de decis˜ao. Mesmo sendo essencialmente
vari´aveis inteiras, elas podem ser razoavelmente aproximadas por arredonda-
mento de solu¸c˜oes provenientes de um algoritmo de otimiza¸c˜ao n˜ao-linear.
3.3 Observa¸c˜oes Finais
Para acoplar o problema de otimiza¸c˜ao com o MEG, o algoritmo de Powell
(
Himmelblau, 1972) ser´a utilizado para a busca pelo vetor ´otimo, enquanto
calcula-se pelo MEG a taxa de sa´ıda resultante, resultando no algoritmo
apresentado na Figura
3.1. Tˆem-se visto relatos de grande sucesso do algo-
ritmo de Powell e do MEG (
Smith & Cruz, 2005; Smith et al., 2006) e por
essa raz˜ao o mesmo ser´a utilizado aqui.
Figura 3.1: Algoritmo de otimiza¸c˜ao proposto.
27
Cap´ıtulo 4
Resultados Experimentais
Ser˜ao apresentados resultados exp erimentais obtidos da metodologia de pla-
nejamento de redes de filas gerais com servidores m´ultiplos. Ser´a adotada
a t´atica de apresentar resultados para redes pequenas, por´em configuradas
em topologias interessantes, para em seguida mostrar redes mais complexas.
Primeiramente, ser´a apresentado uma rede de filas com dois n´os e trˆes n´os.
Em seguida ser˜ao examinados resultados para uma rede que agrega uma
combina¸c˜ao d e topologias em s´erie, com fus˜ao e divis˜ao.
Para validar os resultados anal´ıticos obtidos pelo algoritmo de otimiza¸c˜ao,
simula¸c˜oes foram utilizadas como referˆencia, o que ´e um procedimento tradi-
cional na ´area (ver referˆencias bib liogr´aficas, em particular,
Smith & Cruz,
2005). As simula¸c˜oes foram conduzidas no programa Arena, vers˜ao 3.0
(
Kelton et al., 2001), com 20 replica¸c˜oes, e um per´ıodo de estabiliza¸c˜ao (do
inglˆes warm-up) de 2.000 unidades de tempo, com um tempo total de si-
mula¸c˜ao igual a 200.000 unidades de tempo. Este tempo de simula¸c˜ao e
este n´umero de replica¸c˜oes foram necess´arios para r eduzir o desvio-padr˜ao
dos resultados da simula¸c˜ao a um n´ıvel de precis˜ao aceitavel. Para simular
os tempos de servi¸cos gerais com c
2
s
= {0, 5; 2, 0}, utilizou-se a distribui¸c˜ao
28
Gamma (Kelton et al., 2001). Os experimentos foram conduzidos em um PC
Pentium 4, 3,0 GHz, 2,0 MB CPU, 1,0 GB RAM, sob o sistema operacioanl
Windows XP.
4.1 Rede Dois N´os/Trˆes Servidores
Um das topologias mais simples poss´ıvel ´e a configura¸c˜ao com dois n´os e trˆes
servidores. Os servidores s˜ao conectados em s´erie, sendo que dois deles tra-
balham em paralelo, como visto na Figura
4.1. Ser´a analisado o desempenho
do algoritmo de otimiza¸c˜ao e, em seguida, se uma top ologia ´e melhor que a
outra, ou seja, se a ordem dos servidores em s´erie influencia o desempenho da
rede de filas p´os otimiza¸c˜ao. Estendem-se aqui os experimentos apresentados
por Cruz et al. (2006).
topology A
topology B
M/G/2/K
M/G/1/K
M/G/1/K
M/G/2/K
Figura 4.1: Top ologia dois n´os/trˆes servidores.
4.1.1 Configura¸c˜ao Homogˆenea
No primeiro experimento, apresentado na Tabela
4.1, fixa-se a taxa de che-
gada na red e com λ = {1; 2} entidades por unidade de tempo e taxa de
servi¸co para cada servidor com µ = {4; 8}. Ser´a examinado o tamanho da
29
´area de espera necess´ario para as alternativas de topologias A e B. Ser´a vari-
ado o coeficiente de varia¸c˜ao da taxa de servi¸co c
2
s
para verificar-se se a ´area
de espera seria afetada pela variabilidade do tempo de servi¸co.
Os resultados, vistos na Tabela
4.1, s˜ao bem elucidativos. O δ na nona
coluna refere-se `a semi-amplitude do intervalo de 95% de confian¸ca (IC 95%).
Em quase a totalidade dos v´arios casos testados, o valor da taxa de atendi-
mento anal´ıtico, Θ(x), encontra-se dentro dos IC 95%. A aloca¸c˜ao da ´area
de espera ´e sim´etrica para todos os casos, e n˜ao existe nenhuma diferen¸ca no
valor da solu¸c˜ao ´otima para qualquer topologia. Consequentemente, torna-se
dif´ıcil dizer que uma topologia ´e melhor que outra, simplesmente porque a
metodologia de otimiza¸c˜ao utilizada garante que as alocacoes resultantes se-
jam apropriadas para cada topologia. Se as aloca¸c˜oes n˜ao fossem otimizadas,
ent˜ao talvez uma topologia fosse melhor que a outra.
´
E dificil determinar re-
gras heur´ısticas (por exemplo, sempre coloque os servidores m´ultiplos `a frente
da topologia) para determinar qual topologia tem melhor desempenho.
4.1.2 Configura¸c˜ao Heterogˆenea
Em outra categoria de experimentos com redes de filas com dois n´os e trˆes
servidores, assume-se que o tempo de servi¸co do n´o com dois servidores ´e
menor que o tempo de servi¸co do n´o com um ´unico servidor. Esta confi-
gura¸c˜ao caracteriza um gargalo na rede. Ser´a assumido que a taxa de servi¸co
no n´o com dois servidores seja µ = 4 e a taxa de servi¸co n o n´o com um
´unico servidor seja µ = 8. Resultados experimentais s˜ao apresentados na
Tabela
4.2.
Confirmando a tendˆencia observada nos exp erimentos anteriores, a Ta-
bela
4.2 indica que mais ´area de espera ´e alocada para o n´o com dois servido-
res e menor taxa de servi¸co. Aloca¸c˜oes de ´area de espera sim´etricas ocorrem
30
Tabela 4.1: Resultados para a topologia dois n´os/trˆes servidores.
Simula¸c˜ao
λ µ c
2
s
c x θ(x) Z
α
θ(x)
s
δ Z
s
α
1 (4;4) 0,5 (2;1) (3;4) 0,999 8,000 0,997
∗
0,001 9,710
(1;2) (4;3) 0,999 8,000 0,998 0,001 8,780
1,0 (2;1) (3;4) 0,998 9,000 0,997 0,001 9,670
(1;2) (4;3) 0,998 9,000 0,997 0,001 10,26
2,0 (2;1) (4;5) 0,999 10,00 0,999 0,001 10,38
(1;2) (5;4) 0,999 10,00 0,997
∗
0,001 12,01
(8;8) 0,5 (2;1) (2;3) 1,000 5,000 0,993
∗
0,001 12,18
(1;2) (3;2) 1,000 5,000 0,999 0,001 5,650
1,0 (2;1) (2;3) 0,999 6,000 0,993
∗
0,001 12,35
(1;2) (3;2) 0,999 6,000 0,998 0,001 7,050
2,0 (2;1) (2;3) 0,999 6,000 0,993
∗
0,001 12,28
(1;2) (3;2) 0,999 6,000 0,996
∗
0,001 8,870
2 (4;4) 0,5 (2;1) (7;7) 1,997 17,00 2,001
∗
0,002 13,40
(1;2) (7;7) 1,997 17,00 1,997 0,001 16,80
1,0 (2;1) (9;9) 1,997 21,00 2,000
∗
0,002 17,60
(1;2) (9;9) 1,997 21,00 1,999 0,002 18,90
2,0 (2;1) (9;11) 1,996 24,00 2,000
∗
0,001 20,20
(1;2) (11;9) 1,996 24,00 1,997 0,001 23,50
(8;8) 0,5 (2;1) (4;4) 1,999 9,000 2,001 0,002 7,500
(1;2) (4;4) 1,999 9,000 1,998 0,001 10,40
1,0 (2;1) (4;5) 1,999 10,00 2,000 0,002 8,900
(1;2) (5;4) 1,999 10,00 2,000 0,002 8,800
2,0 (2;1) (4;5) 1,997 12,00 1,999 0,002 10,50
(1;2) (5;4) 1,997 12,00 1,994
∗
0,001 14,90
∗
O IC 95% n˜ao cobre o resultado anal´ıtico.
31
Tabela 4.2: Resultados para a topologia dois n ´os/trˆes servidores com gargalo.
Simula¸c˜ao
λ µ c
2
s
c x θ(x) Z
α
θ(x)
s
δ Z
s
α
1 (4;8) 0,5 (2;1) (3;3) 0,999 7,000 0,997
∗
0,001 8,670
(8;4) (1;2) (3;3) 0,999 7,000 0,999 0,001 6,720
(4;8) 1,0 (2;1) (3;3) 0,999 7,000 0,997
∗
0,001 8,870
(8;4) (1;2) (3;3) 0,999 7,000 0,998 0,001 8,130
(4;8) 2,0 (2;1) (4;3) 0,999 8,000 0,999 0,001 8,320
(8;4) (1;2) (3;4) 0,999 8,000 0,996
∗
0,001 10,93
2 (4;8) 0,5 (2;1) (8;5) 1,998 15,000 1,999 0,002 14,10
(8;4) (1;2) (5;8) 1,998 15,000 1,999 0,002 14,40
(4;8) 1,0 (2;1) (9;6) 1,998 17,000 2,001
∗
0,002 14,30
(8;4) (1;2) (6;9) 1,998 17,000 2,000
∗
0,001 15,20
(4;8) 2,0 (2;1) (9;5) 1,997 17,000 2,000
∗
0,001 14,30
(8;4) (1;2) (5;9) 1,997 17,000 1,995 0,002 19,20
∗
O IC 95% n˜ao cobre o resultado anal´ıtico.
e nenhuma diferen¸ca ocorre no valor da fun¸c˜ao objetivo, comparando-se as
topologias A e B. Adicionalmente, a taxa de atendimento est´a dentro dos IC
95% em v´arios casos.
4.2 Redes Trˆes N´os/Cinco Servidores
Estendendo-se para redes em s´erie mais complexas os experimentos realizados
por
Cruz et al. (2006), uma rede de filas com trˆes n´os e cinco servidores ´e
examinada. A Figura
4.2 representa as trˆes topologias poss´ıveis: um n´o com
um ´unico servidor e dois n´os com dois servidores.
Os resultados podem ser vistos na Tabela
4.3.
´
E interessante que n˜ao
importa o valor de c
2
s
, a ´area de circula¸c˜ao no servidor ´unico, que ´e o gargalo,
32
Tabela 4.3: Resultados para a topologia trˆes n´os/cinco servidores.
Simula¸c˜ao
λ µ c
2
s
c x θ(x) Z
α
θ(x)
s
δ Z
s
α
1 (4;4;4) 0,5 (1;2;2) (4;3;3) 0,998 12,00 0,999 0,001 10,980
(2;1;2) (3;4;3) 0,998 12,00 0,997 0,001 12,840
(2;2;1) (3;3;4) 0,998 12,00 0,997 0,001 12,520
1,0 (1;2;2) (4;3;3) 0,997 13,00 0,997 0,001 12,680
(2;1;2) (3;4;3) 0,997 13,00 0,997 0,001 12,980
(2;2;1) (3;3;4) 0,997 13,00 0,996 0,001 13,520
2,0 (1;2;2) (5;4;4) 0,998 15,00 0,998 0,001 15,390
(2;1;2) (4;5;4) 0,998 15,00 0,999 0,001 13,840
(2;2;1) (4;4;5) 0,998 15,00 1,000
∗
0,001 13,430
(8;8;8) 0,5 (1;2;2) (3;2;2) 0,999 8,000 0,999 0,001 7,720
(2;1;2) (2;3;2) 0,999 8,000 0,994
∗
0,001 12,91
(2;2;1) (2;2;3) 0,999 8,000 0,994
∗
0,001 13,29
1,0 (1;2;2) (3;2;2) 0,999 8,000 0,999 0,001 8,400
(2;1;2) (2;3;2) 0,999 8,000 0,994
∗
0,001 13,24
(2;2;1) (2;2;3) 0,999 8,000 0,994
∗
0,001 13,46
2,0 (1;2;2) (3;2;2) 0,999 8,000 0,996
∗
0,001 10,55
(2;1;2) (2;3;2) 0,998 9,000 0,993
∗
0,001 14,20
(2;2;1) (2;2;3) 0,998 9,000 0,993
∗
0,001 14,10
2 (4;4;4) 0,5 (1;2;2) (7;7;7) 1,996 25,00 1,998
∗
0,001 23,40
(2;1;2) (7;7;7) 1,996 25,00 2,000
∗
0,001 20,70
(2;2;1) (7;7;7) 1,996 25,00 2,000
∗
0,001 21,20
1,0 (1;2;2) (9;9;9) 1,995 32,00 1,998
∗
0,001 28,90
(2;1;2) (9;9;9) 1,995 32,00 2,000
∗
0,002 27,20
(2;2;1) (9;9;9) 1,995 32,00 2,000
∗
0,001 27,20
2,0 (1;2;2) (11;9;9) 1,994 35,00 1,996
∗
0,002 32,60
(2;1;2) (9;11;9) 1,994 35,00 2,000
∗
0,002 28,80
(2;2;1) (9;9;11) 1,994 35,00 2,000
∗
0,002 29,30
(8;8;8) 0,5 (1;2;2) (4;4;4) 1,999 13,00 1,998 0,001 14,30
(2;1;2) (4;4;4) 1,999 13,00 2,000 0,001 12,30
(2;2;1) (4;4;4) 1,999 13,00 2,000 0,001 12,10
1,0 (1;2;2) (5;4;4) 1,998 15,00 1,998 0,002 15,20
(2;1;2) (4;5;4) 1,998 15,00 1,998 0,001 15,10
(2;2;1) (4;4;5) 1,998 15,00 1,999 0,001 13,90
2,0 (1;2;2) (5;4;4) 1,996 17,00 1,994 0,002 18,60
(2;1;2) (4;5;4) 1,996 17,00 1,998 0,002 15,00
(2;2;1) (4;4;5) 1,996 17,00 1,999
∗
0,001 13,90
∗
O IC 95% n˜ao cobre o resultado anal´ıtico.
33
Tabela 4.4: Resultados adicionais para a t opologia trˆes n´os/cinco servidores.
Simula¸c˜ao
λ µ c
2
s
c x θ(x) Z
α
θ(x)
s
δ Z
s
α
1 (4;4;4) 0,0 (1;2;2) (3;3;3) 0,998 11,00 0,997 0,001 12,20
0,1 (1;2;2) (3;3;3) 0,998 11,00 0,996
∗
0,001 13,10
0,2 (1;2;2) (3;3;3) 0,998 11,00 0,996
∗
0,001 13,14
0,3 (1;2;2) (3;3;3) 0,997 12,00 0,995
∗
0,001 14,50
0,4 (1;2;2) (4;3;3) 0,998 12,00 0,999 0,001 10,89
0,5 (1;2;2) (4;3;3) 0,998 12,00 0,999 0,001 10,98
0,6 (1;2;2) (4;3;3) 0,998 12,00 0,999 0,001 11,26
0,7 (1;2;2) (4;3;3) 0,998 12,00 0,998 0,001 12,00
0,8 (1;2;2) (4;3;3) 0,997 13,00 0,998 0,001 12,06
0,9 (1;2;2) (4;3;3) 0,997 13,00 0,998 0,001 12,08
(8;8;8) 0,0 (1;2;2) (2;2;2) 0,999 7,000 0,993
∗
0,001 13,48
0,1 (1;2;2) (2;2;2) 0,999 7,000 0,992
∗
0,001 13,81
0,2 (1;2;2) (2;2;2) 0,999 7,000 0,992
∗
0,001 14,21
0,3 (1;2;2) (2;2;2) 0,999 7,000 0,991
∗
0,001 15,25
0,4 (1;2;2) (2;2;2) 0,998 8,000 0,990
∗
0,001 15,71
0,5 (1;2;2) (3;2;2) 0,999 8,000 0,999 0,001 7,72
0,6 (1;2;2) (3;2;2) 0,999 8,000 0,999 0,001 8,12
0,7 (1;2;2) (3;2;2) 0,999 8,000 0,999 0,001 7,64
0,8 (1;2;2) (3;2;2) 0,999 8,000 0,999 0,001 8,08
0,9 (1;2;2) (3;2;2) 0,999 8,000 0,998 0,001 8,56
∗
O IC 95% n˜ao cobre o resultado anal´ıtico.
34
topology A
topology B
topology C
M/G/2/K
M/G/1/K
M/G/2/K
M/G/1/K
M/G/2/K
M/G/2/K
M/G/2/K
M/G/2/K
M/G/1/K
Figura 4.2: Top ologia trˆes n´os/cinco servidores.
´e maior em rela¸c˜ao aos n´os com dois servidores. Acrescenta que, com uma
variabilidade maior, c
2
s
= 2, 0, as ´areas de espera s˜ao superiores `aquelas com
menor c
2
s
. Consequentemente, o efeito da variabilidade ´e importante para
aloca¸c˜ao da ´area de espera. Mais uma vez torna-se dif´ıcil determinar qual
topologia ´e a melhor, uma vez que entre as topologias A e B as taxas de
atendimento θ(x) apresentam o mesmo valor.
Com o intuito de determinar o efeito do coeficiente de varia¸c˜ao c
2
s
na
aloca¸c˜ao das ´areas de espera, a configura¸c˜ao c = (1; 2; 2) ´e avaliada em mais
detalhes, com uma varia¸c˜ao no c
2
s
de 0, 0 a 0, 9. A Tabela 4.4 apresenta os
resultados. Qu ando c
2
s
= 0, a aloca¸c˜ao da ´area de espera para o n´o com um
´unico servidor apresenta a mesma aloca¸c˜ao para os n´os com dois servidores.
Entretanto, a partir de c
2
s
> 0, 3, a ´area de espera da fila para um ´unico
servidor ´e maior do que para dois servidores. Isto ´e bastante interessante, e
tamb´em imprevis´ıvel, al´em de mostrar que a aloca¸c˜ao da ´area de espera pode
ser bem sens´ıvel a pequenas varia¸c˜oes na variabilidade do tempo de servi¸co.
35
1
2
4
3
5
6
Figura 4.3: Rede primal.
1
2
4
3
5
6
Figura 4.4: Rede dual.
4.3 Rede Primal/Dual
Ser´a examinada uma rede que agrega uma combina¸c˜ao interessante de topo-
logias s´erie, fus˜ao e divis˜ao. Esta combina¸c˜ao ser´a denominada rede primal
e ´e apresentada na Figura
4.3. Na rede primal, os n´os 1 e 6 s˜ao gargalos,
uma vez que o bloqueio ser´a mais severo nestes n´os e uma ´area maior de
espera dever´a ser alocada a eles. A rede dual, derivada da grafo dual da rede
primal, representa uma topologia em ´arvore, conforme pode ser observado
na Figura 4.4. Na rede dual, os n´os 3 e 4 ´e que s˜ao os gargalos. Assim como
na rede primal, a aloca¸c˜ao de ´areas dever´a ser direcionada a estes n´os.
Para ambas as redes, experimentos foram conduzidos, para diversos valo-
res de c
2
s
. Em todos os experimentos escolheram-se λ = {1; 2} como taxa de
chegada, e µ = {4; 8}, como taxa de servi¸co m´edia. Os resultados s˜ao apre-
sentados nas Tabelas
4.5 e 4.6. Estes experimentos estendem os resultados
obtidos por
Cruz & Castro (2006).
Nota-se pelos resultados que a aloca¸c˜ao ´e sim´etrica para a rede primal e
dual, exatamente conforme esperado, haja visto os mecanismos de gargalo
das duas redes. Neste ponto, seria poss´ıvel continuar realizando mais e mais
experimentos, com redes maiores e mais complexas. Entretanto, escolheu-se
parar neste ponto, p ois este ´e um processo ilimitado e que, talvez, n˜ao revele
muito mais do que j´a foi mostrado.
36
Tabela 4.5: Resultados para a rede primal.
λ µ c
2
s
c x θ(x) Z
α
1 (4;4;4;4;4;4) 0,5 (1;1;1;1;1;1) (4;2;2;2;2;4) 0,997 19,00
(2;1;1;1;1;2) (3;2;2;2;2;3) 0,996 18,00
1,0 (1;1;1;1;1;1) (4;2;2;2;2;4) 0,995 21,00
(2;1;1;1;1;2) (3;2;2;2;2;3) 0,994 20,00
2,0 (1;1;1;1;1;1) (5;3;3;3;3;5) 0,997 25,00
(2;1;1;1;1;2) (4;3;3;3;3;4) 0,998 22,00
(8;8;8;8;8;8) 0,5 (1;1;1;1;1;1) (3;2;2;2;2;3) 0,999 15,00
(2;1;1;1;1;2) (2;2;2;2;2;2) 0,999 13,00
1,0 (1;1;1;1;1;1) (3;2;2;2;2;3) 0,999 15,00
(2;1;1;1;1;2) (2;2;2;2;2;2) 0,999 13,00
2,0 (1;1;1;1;1;1) (3;2;2;2;2;3) 0,998 16,00
(2;1;1;1;1;2) (2;2;2;2;2;2) 0,998 14,00
∗
O IC 95% n˜ao cobre o resultado anal´ıtico.
Tabela 4.6: Resultados para a rede dual.
λ µ c
2
s
c x θ(x) Z
α
1 (4;4;4;4;4;4) 0,5 (1;1;1;1;1;1) (2;2;4;4;2;2) 0,997 19,000
(1;1;2;2;1;1) (2;2;3;3;2;2) 0,996 18,000
1,0 (1;1;1;1;1;1) (2;2;4;4;2;2) 0,995 21,000
(1;1;2;2;1;1) (2;2;3;3;2;2) 0,994 20,000
2,0 (1;1;1;1;1;1) (3;3;5;5;3;3) 0,997 25,000
(1;1;2;2;1;1) (3;3;4;4;3;3) 0,998 22,000
(8;8;8;8;8;8) 0,5 (1;1;1;1;1;1) (2;2;3;3;2;2) 0,999 15,000
(1;1;2;2;1;1) (2;2;2;2;2;2) 0,999 13,000
1,0 (1;1;1;1;1;1) (2;2;3;3;2;2) 0,999 15,000
(1;1;2;2;1;1) (2;2;2;2;2;2) 0,999 13,000
2,0 (1;1;1;1;1;1) (2;2;3;3;2;2) 0,998 16,000
(1;1;2;2;1;1) (2;2;2;2;2;2) 0,998 14,000
∗
O IC 95% n˜ao cobre o resultado anal´ıtico.
37
Cap´ıtulo 5
Estudo de Caso em Usina
Sucro-Alcooleira
5.1 Introdu¸c˜ao
O estudo de caso aborda a modelagem, via rede de filas, de uma ind´ustria
sucro-alcooleira, localizada no Estado da Bahia, Brasil. Parˆametros s˜ao defi-
nidos e quantificados, tais como o n´umero m´edio de ve´ıculos na fila de espera
e em atendimento, o tempo m´edio em espera na fila e para a opera¸c˜ao de
descarga, bem como as probabilidades dos tombadores (guindastes) estarem
ocupados.
Quando o fluxo de caminh˜oes com cargas de cana em dire¸c˜ao `a base
industrial ´e muito maior do que a capacidade de descarga, ocorre a forma¸c˜ao
de longas filas de espera para o servi¸co ( descarregamento), implicando em
excessiva demanda de oper´arios e recursos materiais. Portanto, modelar o
comportamento da fila ´e bastante ´util para o planejamento da capacidade
dessas instala¸c˜oes.
Neste sentido foram analisados dados de descarregamento da cana, em-
38
pregando-se ferramental estat´ıstico e aplicativos computacionais, a fim de se
modelar o estado da fila para predizer a probabilidade do seu comportamento
futuro, conhecer as taxas de chegada e de servi¸co dos ve´ıculos transportado-
res de cana, dentre outros parˆametros, e suas implica¸c˜oes nas opera¸c˜oes de
descarga e moagem de cana.
A taxa de chegada poder´a interferir na concentra¸c˜ao do a¸c´ucar contido
na cana podendo implicar na m´a forma¸c˜ao dos cristais durante o cozimento
do caldo, refletindo em p oss´ıveis conseq¨uˆencias sobre a qualidade do produto
final: a¸c´ucar (Payne, 1990).
Todavia esta primeira fase do trabalho, diz resp eito apenas `a modelagem
do sistema de fila. Destaca-se, por´em, que a presente modelagem pode ser
pr´e-requisito para a otimiza¸c˜ao do processo produtivo industrial.
5.2 Aplica¸c˜ao e Desenvolvimento
A propriedade da mat´eria-prima entregue nas Usinas geralmente ´e de tercei-
ros e/ou da pr´opria empresa ind ustrial. No caso em quest˜ao apenas 20% da
cana processada ´e de terceiros, sendo restante da usina.
Para as atividades agro-industriais, como ´e o caso das produtoras de
a¸c´ucar e ´alcool (usinas sucro-alcooleiras), ´e imprescind´ıvel estabelecer uma
perfeita sincronia entre lavoura e ind´ustria, j´a que o eficiente controle do fluxo
de transporte de mat´eria-prima em dire¸c˜ao `a usina tem efeito decisivo sobre a
taxa de utiliza¸c˜ao da moagem. Fluxos de chegadas abaixo da capacidade das
moendas poder˜ao implicar em ociosidade do processo pr odutivo, enquanto
que taxas de chegadas elevadas poder˜ao sobrecarregar o sistema, colocando
a plataforma de descarga e o tandem (conjunto de rolos de moagem) em seus
respectivos limites de capacidade.
39
O processo de descarga na usina inicia-se com a entrada dos caminh˜oes
na ´area industrial. Nesse momento o motorista p´ara o ve´ıculo com a carga
de cana sobre a balan¸ca, onde ´e registrado o peso bruto, a data e o hor´ario
de entrada. Em seguida parte dos ve´ıculos direcionam-se para a plataforma
de coleta de amostra para exame de qualidade enquanto a outra parte segue
diretamente para uma das plataformas de descarga onde aguarda a sua vez
de descarregar. Ap´os a coleta, os ve´ıculos posicionados na plataforma do
laborat´orio juntam-se aos demais ve´ıculos na fila do descarregamento. A
Figura 5.1 mostra o fluxo dos ve´ıculos de carga na usina.
O procedimento interno da Usina exige que todos os ve´ıculos de terceiros
sejam direcionados `a plataforma de coleta de qualidade, e apenas 10% dos
ve´ıculos que conduzem cana pr´opria, para o mesmo fim. Constata-se, por-
tanto, a forma¸c˜ao de uma rede de filas que ´e formada em pelo menos trˆes
momentos, quais sejam: 1) pesagem da carga bru ta; 2) coleta de amostra
para exame da qualidade; 3) descarregamento. A Figura
5.1 mostra o fluxo
dos ve´ıculos de carga na Usina, com os pontos de forma¸c˜ao de fila de espera.
Uma vez conclu´ıdo o servi¸co de descarga o ve´ıculo deixa a ´area industrial
passando novamente pela balan¸ca (lado oposto) a fim de registrar o hor´ario
de sa´ıda e o peso do caminh˜ao vazio (tara). Assim, por diferen¸ca, ´e calcu-
lado o peso l´ıquido que foi entregue `a Usina. Esse procedimento ´e realizado
continuamente durante a safra sendo registrado em tabelas denominadas de
relat´orios de pesagem.
Nesses sistemas industriais, as filas geralmente ocorrem porque as taxas
de chegadas dos ve´ıculos transportadores de cana transcendem, em m´edia, a
capacidade de servi¸co prestado pelas esta¸c˜oes de descarga, promovendo com
isto a demora do ve´ıculo na usina. Tal comportamento justifica a necessidade
de modelagem do sistema de fila formada durante as opera¸c˜oes de descar-
40
Figura 5.1: Representa¸c˜ao do sentido do fluxo de caminh˜oes de cana da lavoura para a ind´ustria.
41
regamento da mat´eria-prima nas usinas, de modo que venha a favorecer o
estabelecimento do processo de colheita, transporte e descarga sob controle.
5.2.1 Modelos de Filas Aplicado `a Ind´ustria Sucro-
Alcooleira
Os conceitos de filas utilizados, inclusive a dedu¸c˜ao das equa¸c˜oes, podem ser
encontrados em diversas referˆencias b´asicas da ´area de Pesquisa Operacional,
a exemplo de Wagner (1986) e de Hillier & Lieberman (2005). Para a mode-
lagem da fila de caminh˜oes a servi¸co na Usina, fez-se necess´ario calcular suas
taxas m´edias de chegada (λ) e de servi¸co (µ), identificar as correspondentes
distribui¸c˜oes de probabilidade das mesmas, estabelecer o n´umero de servi-
dores dispon´ıveis (s), a ordem de descarga (disciplina da fila, geralmente do
tipo pri meiro a chegar, primeiro a ser atendido), bem como o tamanho da
fonte de chegada.
Esses dados consistem em entradas do processo de modelagem. A nota¸c˜ao
a seguir denota-os:
N(t) := n ´umero de clientes no sistema de fila no tempo t (t > 0);
λ
n
:= taxa m´edia de chegada (n ´umero esperado de chegadas de caminh˜oes,
quando n ve´ıculos est˜ao no sistema);
µ
n
:= taxa m´edia de servi¸co (n´umero esperado de ve´ıculos concluindo o ser-
vi¸co, quando n ve´ıculos est˜ao no sistema);
s := n´umero de servidores no sistema de fila.
Os referidos dados de sa´ıda s˜ao:
L := n´umero esperado de ve´ıculos no sistema de fila (ve´ıculos na fila e em
atendimento);
42
L
q
:= n´umero esperado de ve´ıculos apenas na fila;
W := tempo d e espera dos ve´ıculos no sistema (tempo de fila e em atendi-
mento);
W
q
:= tempo de espera dos ve´ıculos exclusivamente na fila;
P
n
:= probabilidade de existirem exatamente n ve´ıculos no sistema de fila;
ρ = λ/(sµ) := corresponde ao fator de utiliza¸c˜ao da instala¸c˜ao de servi¸co, ou
seja a fra¸c˜ao de tempo esperada em que os servidores est˜ao ocupados.
Este ´ultimo parˆametro, ρ, ´e determinante para a continua¸c˜ao dos traba-
lhos, visto que um sistema de filas s´o poder´a ser modelado em seu estado de
equil´ıbrio, ou seja quando λ/(sµ) < 1, caso contr´ario, quando ρ ≥ 1, diz-se
que o sistema encontra-se fora de controle e a fila explode.
5.3 Metodologia
5.3.1 Introdu¸c˜ao
O presente trabalho foi desenvolvido nas instala¸c˜oes da Usina Alian¸ca, loca-
lizada no munic´ıpio de Am´elia Rodrigues, interior da Bahia, durante a safra
2006. A usina ´e produtora de a¸c´ucar e ´alcool e tem capacidade de moagem
de 170 toneladas de cana/hora, produzindo em m´edia 7,0 milh˜oes de litros
de ´alcool e 40.000 t de a¸c´ucar por safra. A usina disp˜oe de infra-estrutura
de transporte com 50 caminh˜oes de carga (pr´oprios e de terceiros) e capa-
cidade m´edia de 12 t de cana por viagem, balan¸ca de pesagem autom´atica,
sonda eletro-mecˆanica para amostragens de mat´eria-prima, bem como de trˆes
esta¸c˜oes de descarga (tombadores).
43
A fim de se trabalhar em um intervalo de tempo onde o processo de oferta
de cana fosse supostamente mais regular, optou-se por utilizar apenas parte
dos registros de entrada de mat´eria-prima, os quais foram considerados em
per´ıodos hor´arios entre 8:00h e 18:00h de cada um dos dias dispon´ıveis nos
boletins de pesagens. Esse intervalo de tempo foi desagregado entre per´ıodo
da manh˜a (das 08:00h `as 13:00h) e per´ıodo da tarde (das 13:00h `as 18:00h).
5.3.2 Levantamento e tratamento de dados
Para a modelagem da fila foram acompanhados e analisados 513 dados (des-
carregamentos) registrados no Relat´orio de Pesagem, distribu´ıdos em cinco
datas ao longo de diferentes meses de safra. Com base nestes dados foram cal-
culadas as taxas de chegada e de servi¸co, bem como testadas as distribui¸c˜oes
de probabilidade que mais se ajustavam aos dados coletados.
5.3.3 Fonte e taxa de chegada
A fonte de chegada corresponde ao n´umero de caminh˜oes que possam requi-
sitar servi¸cos de tempos em tempos, ou seja, o n´umero total de ve´ıculos na
popula¸c˜ao. Este n ´umero pode ser finito ou infinito, de modo que a fonte de
chegada ´e dita ser limitada ou ilimitada. Apesar do n´umero de caminh˜oes `a
disposi¸c˜ao para realizar o transporte da cana ser finito, o elevado n ´umero de
vezes que este retorna `a fila faz supor uma fonte ilimitada.
Por sua vez, o padr˜ao estat´ıstico (distribui¸c˜ao de probabilidade) no qual os
ve´ıculos s˜ao gerados no tempo tamb´em precisa ser especificado. A suposi¸c˜ao
mais comum ´e que o n´umero de clientes gerados at´e qualquer tempo espec´ıfico
tenha uma distribui¸c˜ao de probabilidade de Poisson. Esta distribui¸c˜ao ´e
caracterizada pela aleatoriedade dos eventos (chegadas), por´em a uma certa
taxa m´edia.
44
Com base no teste χ
2
, foi analisada a hip´otese de os n´umeros contidos
no Relat´orio de Pesagem pertencerem a uma distribui¸c˜ao de Poisson, j´a que
por suas caracter´ısticas, por exemplo, de ser uma distribui¸c˜ao discreta, seria
uma das mais prov´aveis para o caso em estudo (
Nascimento, 2006).
5.3.4 Mecanismo e taxa de servi¸co
Os mecanismos de servi¸co na usina consistem em um sistema de m´ultiplas
fases (pesagem, amostragem e descarregamento) e m´ultiplos canais (disp˜oe-se
de trˆes tombadores em paralelo). De um modo geral, para um cliente em uma
instala¸c˜ao de servi¸co, o intervalo de tempo desde o come¸co deste servi¸co at´e
sua conclus˜ao, ´e chamado de tempo de servi¸co (1/µ). Assim como no caso do
processo de chegada, o mecanismo de servi¸co deve especificar a distribui¸c˜ao
de probabilidade dos tempos envolvidos.
O teste de aderˆencia para o tempo de servi¸co foi substitu´ıdo pela Pro-
priedade de Equivalˆencia, conforme consta em
Hillier & Lieberman (2005).
Tal Propriedade afirma que se uma instala¸c˜ao de servi¸co com s servidores
apresenta chegadas de acordo com um processo de Poisson, com parˆametro
λ, em que sλ > µ, ent˜ao a sa´ıda desta instala¸c˜ao, em estado de equil´ıbrio,
tamb´em est´a de acordo com a distribui¸c˜ao de Poisson, podendo-se supor que
o intervalo de tempo entre sa´ıdas (tempo de servi¸co) ´e exponencial. Assim,
adotou-se que a distribui¸c˜ao do tempo de servi¸co transcorreria de acordo com
esta distribui¸c˜ao exponencial.
45
5.4 Modelagem Matem´atica
5.4.1 Fila
A depender do comportamento estat´ıstico gerado pelos dados levantados,
pode-se dispor de grande variedade de formul´ario para representar determi-
nado sistema de fila. Assim, assumindo-se que o sistema em estudo comporte-
se como o modelo b´asico (taxas de chegadas de acordo com o processo de
Poisson e tempos de servi¸co exponencial) encontram-se dispon´ıveis equa¸c˜oes
matem´aticas que podem vir a represent´a-lo. Nesse caso, as equa¸c˜oes ma-
tem´aticas empregadas para calcular os parˆametros de sa´ıda, s˜ao:
W = W
q
+ 1/λ,
W
q
= L
q
/λ,
L = (L
q
+ λ/µ),
L
q
= (λ
2
δ
2
+ ρ
2
)/2(1 − ρ),
P
o
= 1/
(ρ)
n
/n! + ρ
s
/s!(1/(1 − ρs))
,
ρ = λ/sµ.
Entretanto, dadas as dificuldades operacionais no que se refere ao trata-
mento e emprego dessas equa¸c˜oes, algumas envolvendo somat´orio e fatorial,
bem como a fim de permitir a simula¸c˜ao de diferentes estados do sistema,
optou-se pela utiliza¸c˜ao do aplicativo QSB
+
(Quantitative System for Busi-
ness Plus, veja
Chang & Sullivan, 1996), o qual permite rapidamente calcu-
lar cen´arios atuais e futuros apenas variando-se os parˆametros de entrada do
sistema de fila.
46
5.5 Resultados e Discuss˜oes
Com base nos dados contidos nos relat´orios de pesagem e o conseq¨uente
tratamento realizado sobre os mesmos, pˆode-se compor a Tabela
5.1, que
apresenta as taxas de chegadas (λ) e de servi¸co (µ) em fun¸c˜ao dos turnos
estabelecidos. Para todos os casos, com base em correspondente aplica¸c˜ao
de teste, o processo de chegada ´e de Poisson e o tempo de servi¸co est´a de
acordo com a distribui¸c˜ao exponencial.
Tabela 5.1: Taxas de chegada e de servi¸co, por minuto, em fun¸c˜ao do per´ıodo.
Balan¸ca Laborat´orio Tombadores
Per´ıodo λ µ λ µ λ µ
Manh˜a 0,1407 0,5 0,033 0,25 0,1061 0,25
Tarde 0,1653 0,5 0,037 0,25 0,1194 0,25
Pelo exposto na Tabela 5.1, constata-se que as taxas de chegadas (λ) va-
riam em fun¸c˜ao do per´ıodo analisado, o mesmo n˜ao ocorrendo com a taxa de
servi¸co (µ). Os ve´ıculos chegam `a usina a uma taxa de 0,1407 por minuto pela
manh˜a e 0,1653 por minuto pela tarde. Parte dos ve´ıculos que chegam, ap´os
registro de peso bruto, destinam-se para a coleta de amostra ou s˜ao desviados
diretamente ao servi¸co de descarga. Essa divis˜ao gera novas taxas de chega-
das nas instala¸c˜oes subseq¨uentes, quais sejam: 0,033/minuto e 0,037/minuto,
no laborat´orio, e 0,1061/minuto e 0,1194/minuto, nos tombadores, para os
per´ıodos da manh˜a e da tarde, resp ect ivamente.
Constata-se assim, que existe alguma variabilidade no processo de che-
gada dos ve´ıculos `a Usina, bem como a sua transferˆencia entre as diferentes
instala¸c˜oes de servi¸co, quando comparados os per´ıodos da manh˜a e da tarde.
Isto, entretanto, n˜ao ´e observado nas opera¸c˜oes de servi¸co, talvez por serem
47
semi-automatizadas, em que a participa¸c˜ao de oper´arios, pelo menos em al-
gumas fases de cada processo, ´e limitada. N˜ao se constatou aqui, ou pelo
menos n˜ao se mostrou relevante quando simulado, a caracter´ıstica apresen-
tada por alguns sistemas de fila em que os servi¸cos tendem a ser realizados
mais r´apido `a medida que a fila aumenta.
Ap´os os dados terem sido devidamente tratados, e assumindo-se que este
sistema de fila apresente comportamento com entrada de Poisson e servi¸co ex-
ponencial, foram feitas simula¸c˜oes com o n´umero de tombadores (s) variando
a disponibilidade dos mesmos entre 1 e 3, sendo anotados os resultados. As
decis˜oes foram embasadas na observa¸c˜ao e an´alise do processo, bem como em
consultas ao engenheiro respons´avel e oper´arios da usina, que conhecem o sis-
tema de transporte e descarga de cana da mesma e, portanto, tˆem condi¸c˜oes
de avaliar se os resultados encontrados s˜ao pelo menos satisfat´orios. As si-
mula¸c˜oes para tanto foram geradas pelo software QSB+, cujos resultados
encontram-se na Tabela
5.2.
Observa-se ainda que como λ/µ ´e menor que 1, pode-se inclusive traba-
lhar com servidor ´unico, gerando 0,74 ve´ıculos no sistema. Aumentando-se,
entretanto, o n´umero de tombadores de dois para trˆes, os ganhos talvez n˜ao
fossem relevantes, j´a que o tamanho da fila seria muito p ouco afetado, dimi-
nuindo de 0,44 ve´ıculos para apenas 0,43 ve´ıculos, respectivamente. Entre-
tanto, isto implica no aumento da ociosidade dos equipamentos (de 65,60%
para 68,20%), reduzindo-se a probabilidade de que um ve´ıculo que adentre
`as instala¸c˜oes industriais tenha que esperar pelo servi¸co.
O per´ıodo vespertino apresenta um comportamento similar ao matutino,
no que diz respeito `a regularidade das chegadas, cuja taxa m´edia, no conjunto
da amostragem tratada apresentou um valor de 0,1653 chegadas/minuto (ou
9,62 chegadas/h). Dispondo-se de apenas um equipamento, observa-se a me-
48
Tabela 5.2: Resultados do sistema de filas, em fun¸c˜ao do per´ıodo.
Balan¸ca
Per´ıodo S L
q
L W
q
W P
0
(%) P
w
(%) ρ
Manh˜a 1 0,39 0,11 2,78 0,78 72,3 28,2 28,2
Tarde 1 0,49 0,16 2,99 0,99 67,4 33,4 33,1
Laborat´orio
Per´ıodo S L
q
L W
q
W P
0
(%) P
w
(%) ρ
Manh˜a 1 0,15 0,02 4,60 0,60 8,16 13,6 13,2
Tarde 1 0,17 0,025 4,69 0,69 85,2 15,5 14,8
Tombadores
Per´ıodo S L
q
L W
q
W P
0
(%) P
w
(%) ρ
Manh˜a 1 0,74 0,31 6,94 2,95 58,5 42,0 42,2
2 0,44 0,02 4,18 0,18 65,6 7,40 21,22
3 0,43 0,001 4,02 0,015 68,2 0,90 14,14
Tarde 1 0,91 0,43 7,65 3,65 52,4 47,7 47,70
2 0,50 0,03 4,24 0,24 61,3 9,01 24,5
3 0,48 0,002 4,02 0,021 61,98 1,33 16,7
nor ociosidade dos tombadores (52,4%), bem como, evidentemente, a maior
chance d os ve´ıculos terem que esperar na fila pelo atendimento do servi¸co
(47,7%). Constata-se ainda, que ´e poss´ıvel de se trabalhar com apenas u m
tombador, uma vez que tamb´em ocorre λ/(sµ) < 1. Entretanto, operando-se
o sistema com um segundo tombador, o tempo de espera reduz-se em 44,58%,
saindo de 7,65 minutos para 4,24 minutos.
5.6 Conclus˜oes
Pelo exposto pode-se concluir que o dimensionamento do sistema de fila da
uma usina ´e de fundamental importˆancia para o planejamento da capacidade
da instala¸c˜ao, n˜ao apenas porque revela o tamanho da fila e o correspondente
49
tempo de espera na mesma, mas principalmente porque contribui de modo
significativo para o planejamento da capacidade dessas instala¸c˜oes. Com os
resultados obtidos pode-se, por exemplo, inferir quanto `a necessidade em se
operar com um determinado n´umero de tombadores para que o sistema de
descarga funcione em ritmo de equivalˆencia com a capacidade de moagem.
Isto ´e de importˆancia decisiva uma vez que descarregando-se uma quanti-
dade de cana muito distante desta capacidade dever´a implicar em o ciosidade
ou sobrecarga do sistema, podendo comprometer a qualidade dos produtos
finais, bem como os custos desse processo.
O conhecimento pr´evio de poss´ıveis comportamentos do sistema de fila
auxilia tamb´em no planejamento da disponibilidade de recursos humanos e
materiais a serem assegurados nos diferentes turnos de trabalho. Quando
se prevˆe, por exemplo, que para determinado per´ıodo ´e suficiente trabalhar
com um certo n´umero de tombadores, isto favorece `a indica¸c˜ao de quantos
oper´arios deveriam encontrar-se dispon´ıveis naquele hor´ario, bem como, por
exemplo, a vaz˜ao de ´agua de lavagem de cana a ser assegurada para tanto.
Outras vari´aveis `a jusante do ponto de descarga certamente tamb´em seriam
afetadas, ´e o caso da disponibilidade de insumos, a exemplo da quantidade
de enxofre aplicado por tonelada de caldo para a fabrica¸c˜ao de a¸c´ucar.
De acordo com os resultados obtidos, pode-se inferir que provavelmente
o n´umero ´otimo de tombadores em opera¸c˜ao seria 2, pois, nos casos onde se
passa de apenas um equipamento para 2, as diferen¸cas no tempo de espera
s˜ao mais expressivas do que quando se passa de 2 para 3 equipamentos. Na
verdade essa conclus˜ao s´o poder´a ser confirmada caso se proceda uma mo-
delagem da fila focada na otimiza¸c˜ao das plataformas de descarga, fato que
exigiria o levantamento dos custos marginais em se oferecer o servi¸co, bem
como os custos da espera pelo servi¸co; entretanto, este n˜ao ´e o objeto do
50
presente trabalho. A contribui¸c˜ao ora oferecida diz respeito simplesmente `a
modelagem da fila, a otimiza¸c˜ao do n´umero de tombadores a partir da mini-
miza¸c˜ao dos referidos custos envolvidos, bem como o balanceamento da taxa
de descarga de cana com a capacidade do tandem de moagem, encontram-se
em fase de estudo.
Uma limita¸c˜ao a ser destacada diz respeito `as restri¸c˜oes do software em-
pregado, QSB+. Esse aplicativo basicamente restringe-se ao emprego de
taxas de servi¸co exponenciais e chegadas de Poisson, ou seja, processos ti-
picamente markovianos. Numa primeira tentativa de se analisar o per´ıodo
integral (24 horas ininterruptas), em que o comportamento real distanciou-se
do modelo b´asico, a modelagem para servidores m´ultiplos ficou dificultada,
j´a n˜ao se disp˜oe de formul´arios que apresentem resultados aplicados satis-
fat´orios nestes casos, o que justificou a redu¸c˜ao para o per´ıo d o de apenas 10
horas (8:00h `as 18:00h).
Outro elemento a ser destacado diz respeito `as datas dos dados que foram
analisados. Pelo menos a maioria dos mesmos (trˆes dias) corresponde ao mˆes
de fevereiro, per´ıodo relativamente irregular da produ¸c˜ao sucro-alcooleira da
regi˜ao onde est´a instalada a Usina (Recˆoncavo baiano). Este per´ıodo, al´em
de estar pr´oximo ao final da safra, quando a disponibilidade de cana ´e bem
menor, o que implica na significativa redu¸c˜ao da oferta de mat´eria-prima
e, portanto, do fluxo de caminh˜oes p ara a usina, tem ainda o agravante
de ser um per´ıodo chuvoso, fato que geralmente interrompe o processo da
colheita. Isto provavelmente deve ter levado `a ocorrˆencia de tamanho da fila
freq¨uentemente menor que a unidade.
51
Cap´ıtulo 6
Conclus˜oes e T´opicos para
Trabalhos Futuros na
´
Area
Apresentamos uma abordagem para o p roblema de aloca¸c˜ao de ´areas de
espera em filas configuradas em redes com distribui¸c˜ao geral do tempo de
servi¸co e servidores m´ultiplos. Descrevemos as express˜oes desenvolvidas para
as probabilidades de bloqueio, bem como a metodologia de otimiza¸c˜ao empre-
gada. V´arios experimentos foram apresentados e detalhadamente discutidos,
para ilustrar o escopo e as limita¸c˜oes da abordagem. Esperamos que o leitor
sinta a for¸ca desta nova abordagem na sua habilidade em atacar complexos
problemas de planejamento de redes de filas finitas.
Dentre as poss´ıveis dire¸c˜oes que esta pesquisa pode tomar, p odemos citar
a aplica¸c˜ao do algoritmo a problemas da ´area de manufatura e montagem,
planejamento de plantas e leiautes, bem como a problemas de planejamento
de redes de telecomunica¸c˜oes e sistemas de computa¸c˜ao.
Tamb´em n˜ao examinamos situa¸c˜oes nas quais o n´umero de servidores, c,
fosse uma vari´avel de decis˜ao. Isto poder´a requerer uma reestrutura¸c˜ao da
abordagem e decidimos n˜ao tratar este aspecto neste momento da pesquisa.
52
Um aspecto desanimador com respeito ao n´umero de servidores ´e que
ele n˜ao parece ser t˜ao cr´ıtico quanto a ´area de espera, conforme evidenciado
pelos nossos resultados. Outros pesquisadores chegaram a resultados simi-
lares a respeito da importˆancia da ´area de espera (
Kubat & Sumita, 1985;
Jafari & Shanthikumar, 1989).
Outra possibilidade ´e incluir nos estudos experimentais exemplos de re-
des com la¸cos de realimenta¸c˜ao, bastante encontrados em manufatura e no
setor de servi¸cos. La¸cos de realimenta¸c˜ao causam forte dependˆencia entre
as chegadas e necessitam cuidadosa considera¸c˜ao. Estas s˜ao apenas algumas
dire¸c˜oes interessantes para futuros trabalhos na ´area.
53
Referˆencias Bibliogr´aficas
Altiok, T. & Stidham, S. (1983). The allocation of inter-stage buffer capaci-
ties in production lines, IIE Transactions 15(4): 292–299.
Baker, K., Powell, S. & Pyke, D. (1990). Buffered and unbuffered assem-
bly systems with variable processing times, Journal of Manufacturing and
Operations Management 3(3): 200–223.
Bazaraa, M. S., Jarvis, J. J. & Sherali, H. D. (1990). Linear Programming
and Networks Flows, 2nd edn, John Wiley & Sons, New York.
Chang, Y. & Sullivan, R. S. (1996). QSB
+
, Prentice Hall.
Cruz, F. R. B. & Castro, M. S. (2006). Planejamento de topologia de redes
de filas finitas com servidores m´ultiplos, Anais do IX Simp´osio de Pesquisa
Operacional e Log´ıstica da Marinha, Rio de Janeiro, pp. 471–480.
Cruz, F. R. B., Castro, M. S. & Barbosa, H. A. L. (2006). Optimal design
of networks of general finite multi-server queues, Anais do IX Encontro de
Modelagem Computacional, Belo Horizonte, pp. 1–10.
Cruz, F. R. B. & Smith, J. M. (2007). Approximate analysis of M/G/c/c
state-dependent queueing networks, Computers & Operations Research
34(8): 2332–2344.
54
Duarte, A. R. (2005). Aloca¸c˜ao de ´areas de circula¸c˜ao em redes de filas gerais,
Disserta¸c˜ao de Mestrado, Departamento de Estat´ıstica - ICEx - UFMG,
Belo Horizonte, MG.
Gelenbe, E. (1975). On approximate computer system models, Journal of
the ACM 22(2): 261–269.
Gross, D. & Harris, C. (1985). Fundamentals of Queueing Theory, J. Wiley
& Sons, New York.
Harris, J. H. & Powell, S. G. (1999). An algorithm for optimal buffer place-
ment in reliable serial lines, IIE Transactions 31: 287–302.
Hillier, F. S. & Lieberman, G. J. (2005). Introduction to Operations Research,
8th edn, McGraw Hill Higher Edu cation.
Himmelblau, D. M. (1972). Applied Nonlinear Programming, McGraw-Hill
Book Company, New York.
Jafari, M. A. & Shanthikumar, J. G. (1989). Determination of optimal buffer
storage capacities and optimal allocation in multistage automatic transfer
lines, IIE Transactions 21(2): 130–135.
Kelton, D., Sadowski, R. P. & Sadowski, D. A. (2001). Simulation with
Arena, MacGraw Hill College Div., New York, NY, USA.
Kendall, D. G. (1953). Stochastic processes occurring in the theory of queues
and their analysis by the method of imbedded markov chains, Annals
Mathematical Statistics 24: 338–354.
Kerbache, L. & Smith, J. M. (1987). The generalized expansion method for
open finite queueing networks, European Journal of Operational Research
32: 448–461.
55
Kim, N. K. & Chae, K. C. (2003). Transform-free analysis of the GI/G/1/K
queue thr ough the decomposed Little’s formula, Computers & Operations
Research 30(3): 353–365.
Kimura, T. (1996a). Optimal buffer design of an M/S/s queue with finite
capacity, Communications in Statistics - Stochastic Models 12(1): 165–180.
Kimura, T. (1996b). A transform-free approximation for the finite capacity
M/G/s queue, Operations Research 44(6): 984–988.
Kubat, P. & Sumita, U. (1985). Buffers and backup machines in automatic
transfer lines, International Journal of Production Research 23(6): 1259–
1280.
Labetoulle, J. & Pujolle, G. (1980). Isolation method in a network of queues,
IEEE Transactions on Software Engineering SE-6(4): 373–381.
Lemar´echal, C. (2003). The omnipresence of Lagrange, 4OR 1: 7–25.
Mateus, G. R. & Luna, H. P. L. (1986). Programa¸c˜ao N˜ao-Linear, V Escola
de Computa¸c˜ao, Belo Horizonte, Brasil.
Nascimento, A. N. (2006). Otimiza¸c˜ao da Capacidade de Instala¸c˜oes Sucro-
alcooleiras, Tese de Doutorado, Departamento de Engenharia Qu´ımica -
FEQ - UNICAMP, Campinas, SP, Brazil.
Payne, J. H. (1990). Opera¸c˜oes Unit´arias na Produ¸c˜ao de A¸cucar de Cana,
Brasil.
Reeves, C. R. (1993). Modern Heuristic Techniques for Combinatorial Pro-
blems, John Wiley & Sons, Inc., New York - Toronto.
56
Sakasegawa, H., Miyazawa, M. & Yamazaki, G. (1993). Evaluating
the overfl ow probability using the infinite queue, Management Science
39(10): 1238–1245.
Schweitzer, P. J. & Konheim, A. G. (1978). Buffer overflow calculations
using an infinite-capacity model, Stochastic Processes and their Applicati-
ons 06(3): 267–276.
Smith, J. M. (2003). M/G/c/k blocking probability models and system
performance, Performance Evaluation 52(4): 237–267.
Smith, J. M. & Cruz, F. R. B. (2005). The buffer allocation problem for
general finite buffer queueing networks, IIE Transactions on Design &
Manufacturing 37(4): 343–365.
Smith, J. M., Cruz, F. R. B. & van Woensel, T. (2006). Topological network
design of general, finite, multi-server queueing networks (submetido).
Soyster, A. L., Schmidt, J. W. & Rohrer, M. W. (1979). Allocation of buffer
capacities for a class of fixed cycle production lines, AIIE Transacti ons
11(2): 140–146.
Spinellis, D., Papadoulos, C. T. & Smith, J. M. (2000). Large production
line optimization using simulated annealing, International Journal of Pro-
duction Research 38(3): 509–541.
Tijms, H. C. (1992). Heuristics for finite-buffer queues, Probability in the
Engineering and Informational Sciences 06: 267–276.
Tijms, H. C. (1994a). Stochastic Modelling: An Algorithmic Approach, John
Wiley & Sons, New York.
57
Tijms, H. C. (1994b). S tochastic Modelling and Analysis: A Computational
Approach, John Wiley & Sons, New York.
Wagner, H. M. (1986). Pesquisa Operacional, 2a edi¸c˜ao, Prentice-Hall do
Brasil Ltda., Rio de Janeiro.
Yamashita, H. & Onvural, R. (1994). Allocation of buffer capacities in queu-
eing networks with arbitrary topologies, Annals of Operations Research
48: 313–332.
58
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
