1 INÍCIO
2 Defina a partição do conjunto de variáveis inteiras: S1, S2, . . . , SP. 3 Defina o critério de fixação das variáveis.
4 Relaxe todas as variáveis inteiras do modelo. 5 para k ← 1 até P faça
6 Retorne a integralidade das variáveis da partição Sk. 7 Resolva o MIP resultante.
8 se a solução encontrada for factível então
9 Fixe as variáveis da partição Sk de acordo com o critério de fixação. 10 senão
11 Pare. Não foi possível encontrar uma solução factível. 12 FIM
do primeiro até o último. Nas heurísticas relax-and-fix com overlapping, são utilizadas duas partições diferentes de variáveis, cada uma com P conjuntos disjuntos (BALDO et al., 2014). A partição Si
1, S2i, . . . , SPi é definida pelas variáveis que se tornarão inteiras a cada
iteração k, k = 1, . . . , P , e a partição Sf
1, S2f, . . . , SPf, é definida pelas variáveis que serão
fixadas a cada iteração k. Em cada iteração k, a integralidade das variáveis do conjunto
Si
k é reestabelecida, o problema é resolvido e as variáveis do conjunto S f
k são fixadas. Na
iteração seguinte, k + 1, as variáveis de Si
k+1 tornam-se inteiras e as variáveis de Ski se
mantém inteiras. Assim, as variáveis do conjunto Si
k que não estavam no conjunto S f k
e, portanto, não foram fixadas na iteração k, podem assumir outros valores durante a resolução do novo subproblema, acontecendo assim a sobreposição (overlapping). Para que a sobreposição funcione, deve-se ter que Sf
1 ⊆ S1i, S2f ⊆ S1i∪ S2i, . . . , SPf ⊆ S1i∪ S1i∪ . . . SPi .
Nesse trabalho considera-se as heurísticas relax-and-fix sem overlapping. Os sub- problemas sempre são factíveis, uma vez que no modelo MDSL-2E-LT existem variáveis de atraso da produção. As partições são feitas por períodos. Duas estratégias para percorrer os períodos foram utilizadas: do primeiro para o último (forward) e do último para o primeiro (backward). Com o intuito de deixar os subproblemas ainda menores, também foram testadas partições por período combinadas com partições por máquinas (RFX 11 e RFX12).
Várias combinações de critérios de fixação foram utilizadas, gerando um total de 16 heurísticas do tipo relax-and-fix, resumidas na Tabela19. Na primeira coluna é apresentada a sigla que representa a heurística, na segunda coluna está descrita a partição usada e como os conjuntos são percorridos e na última coluna são mostradas as variáveis que são relaxadas e fixadas. Nas heurísticas RFX13 a RFX16, as variáveis são fixadas a cada período somente quando existe produção para o lote o, do item j, no período t, no tanque preparatório/máquina m. Se não existe produção, essas variáveis ficam livres, ou seja, não são fixadas em zero. Essa técnica de fixar somente se existe produção foi usada por
118 Capítulo 5. Métodos heurísticos de programação matemática para o problema
Ferreira, Morabito e Rangel (2010) e gera bons resultados, e por esse motivo são aqui testadas.
Tabela 19 – Características das heurísticas relax-and-fix propostas.
Heurística Conjunto de partição Variáveis fixadas
relax-and-fix variáveis
RFX1 Período (forward) Ymjto e Zmijt
RFX2 Período (backward) Ymjto e Zmijt
RFX3 Período (forward) Ymjto, Zmijt, WmjtokI e WmjtokII
RFX4 Período (backward) Ymjto, Zmijt, WmjtokI e WmjtokII
RFX5 Período (forward) Ymjto, Zmijt, ωmjtokI e ωmjtokII
RFX6 Período (backward) Ymjto, Zmijt, ωmjtokI e ωmjtokII
RFX7 Período (forward) Ymjto, Zmijt e Xmjto
RFX8 Período (backward) Ymjto, Zmijt e Xmjto
RFX9 Período (forward) Ymjto, Zmijt, WmjtokI , WmjtokII , ωmjtokI e ωIImjtok
RFX10 Período (backward) Ymjto, Zmijt, WmjtokI , WmjtokII , ωmjtokI e ωIImjtok
RFX11 Período (forward) Ymjto, Zmijt, WmjtokI e WmjtokII
Linha (forward)
RFX12 Período (backward) Ymjto, Zmijt, WmjtokI e WmjtokII
Linha (forward)
RFX13 Período (forward) Ymjto, Zmijt, WmjtokI e WmjtokII , se Ymjto>0
RFX14 Período (backward) Ymjto, Zmijt, WmjtokI e WmjtokII , se Ymjto>0
RFX15 Período (forward) Ymjto, Zmijt e Xmjto, se Ymjto>0
RFX16 Período (forward) Ymjto, Zmijt, WmjtokI , WmjtokII , ωmjtokI e ωIImjtok, se Ymjto>0
5.4 Heurísticas de melhoria fix-and-optimize
Nas Seções 5.1,5.2 e5.3, foram apresentadas heurísticas para obtenção de soluções factíveis para o problema de programação da produção de bebidas à base de frutas. Nesta seção são propostas heurísticas que melhoraram uma solução factível para o problema, ou seja, heurísticas de melhoria. Na Seção5.4.1 são apresentadas heurísticas fix-and-optimize clássicas e na Seção5.4.2 heurísticas fix-and-optimize com busca em vizinhança. A partir de uma solução factível para o modelo MDSL-2E-LT, essas heurísticas decompõem esse modelo resolve apenas para parte dele.
5.4.1 Heurísticas fix-and-optimize
As heurísticas fix-and-optimize são heurísticas de melhoria, logo, precisam ser inicializadas com uma solução factível, diferentemente das heurísticas relax-and-fix que constroem uma solução factível para o problema. Entretanto, assim como as heurísticas
relax-and-fix, as fix-and-optimize também exploram a estrutura dos modelos e resolvem
subproblemas menores. A heurística fix-and-optimize surgiu como uma melhoria da relax-
5.4. Heurísticas de melhoria fix-and-optimize 119
dimensionamento e sequenciamento de lotes (HELBER; SAHLING, 2010;TOLEDO et al., 2015; GÖREN; TUNALI,2015).
A abordagem para resolver o problema da heurística fix-and-optimize é similar com a da relax-and-fix. Enquanto na relax-and-fix o problema inicia relaxado, com apenas uma partição das variáveis considerada inteira, na fix-and-optimize todas as variáveis inteiras das partições estão inicialmente fixas no valor da solução incumbente. A cada iteração da
fix-and-optimize, as variáveis de uma partição são deixadas livres para serem otimizadas,
diferente da relax-and-fix, em que as variáveis de uma partição se tornam inteiras. Dizer que uma partição de variáveis está “livre” ou “liberada” para ser otimizada significa que essas variáveis não estão fixadas em nenhum valor, mas o domínio sob o qual elas devem ser otimizadas se mantém o mesmo.
Os passos seguidos pela heurística fix-and-optimize abordada estão apresentados no Algoritmo 5. Considere novamente a partição do conjunto de variáveis inteiras em
P conjuntos disjuntos: S1, . . . , SP. A solução inicial (SOLini) é tomada como solução
incumbente (SOLinc). A solução corrente (SOLcor) é inicialmente é vazia. A cada iteração,
todas as variáveis inteiras do problema são fixadas no valor da solução incumbente, e apenas as variáveis inteiras do conjunto Sk ficam livres para serem otimizadas. Se o valor
da solução do subproblema resultante (FO(SOLcor)) for melhor do que o valor da solução
incumbente (FO(SOLinc)), esta é substituída. O processo é repetido enquanto o tempo
decorrido (T empo_Decor) não excede o tempo máximo disponível (Lim_T empo) e estão sendo encontradas soluções melhores. Se todas as partições já tiverem sido percorridas pelo menos uma vez, o algoritmo é interrompido se não há mais melhoria, antes de atingir o limite de tempo. Convém observar que a busca por uma solução melhor é realizada de forma ordenada, pois as partições são sempre percorridas de 1 até P (forward) ou de P até 1 (backward).
Neste trabalho, as partições e as variáveis que são fixadas nas heurísticas fix-and-
optimize estão apresentadas na Tabela 20. Com o intuito de testar a influência da solução inicial nas heurísticas fix-and-optimize, três estratégias para obtenção de solução inicial são testadas:
1) a solução da melhor estratégia CPLEX, gerando assim a heurística CPX+FXO (estratégia CPLEX+fix-and-optimize);
2) a solução da melhor heurística relax-and-fix, produzindo heurísticas RFX+FXO (relax-and-fix + fix-and-optimize);
3) a solução da melhor heurística dentre as de decomposição e as baseadas em modelos relaxados, gerando assim as heurísticas H+FXO (heurística + fix-and-optimize).
120 Capítulo 5. Métodos heurísticos de programação matemática para o problema