1 INÍCIO
2 Inicialização: Defina Tempo_Lim, β1, β2, β3, ϕ, δ, ε. 3 enquanto Tempo_Exec < Tempo_Lim faça
4 Resolva o modelo matemático. 5 se Existe uma solução factível então
6 Sincronize os estágios. (Use Algoritmo1). 7 se Tempo_Exec ≤ 13.Tempo_Lim então
8 β← β1
9 senão se 13.Tempo_Lim < Tempo_Exec ≤ 23.Tempo_Lim então
10 β← β2
11 para todo t ∈ T e m ∈ M faça 12 Capmt← ϕ.Capmt
13 senão
14 β← β3
15 para todo t ∈ T e m ∈ M faça 16 se CapU tilmt> CapDispmt então
17 δ ← CapU tilmt− CapDispmt. 18 Capmt← Capmt− max{β.δ, ε}.
19 Aux← 1.
20 se Aux=0 então
21 Pare e retorne a melhor solução inteira. 22 senão
23 Pare. O algoritmo não retorna uma solução factível. 24 FIM
a otimalidade pelo solver dentro de um tempo razoável para a execução das heurísticas. Assim, a otimalidade ou um tempo limite são os critérios de parada na solução desses modelos. Conforme as premissas de modelagem apresentadas no Capítulo4, são permitidos atrasos, logo o modelo sempre é factível.
Toda redução de capacidade no modelo matemático implica em mais tempo dis- ponível para inclusão das limpeza temporais e dos tempos de espera. No entanto, essas reduções geram soluções com altos níveis de atraso e, portanto, soluções com qualidade ruim. Por outro lado, reduzir pouco a capacidade implica em pouco tempo para inclusão das esperas e limpezas temporais, o que pode levar a soluções infactíveis para o problema original. Ou seja, grandes reduções podem levar a soluções com muito atraso e reduções muito pequenas podem impedir que o algoritmo convirja em um tempo razoável, isto é, que a heurística termine sem solução factível dentro do tempo máximo de execução permitido. Vemos então que existe um trade-off na redução de capacidade.
A redução da capacidade é realizada conforme descrito entre as linhas 12 e 18 do Algoritmo 2. Quando a capacidade utilizada após a sincronia (CapUtilmt) é um valor
102 Capítulo 5. Métodos heurísticos de programação matemática para o problema
próximo da capacidade disponível (CapDispmt), temos que o valor de δ (que é a diferença
entre as capacidades) é muito pequeno. Assim, se somente o valor δ fosse utilizado na redução de capacidade, essas reduções seriam muito pequenas, logo a solução do novo modelo com a capacidade reduzida seria muito próxima da solução da última iteração ou até mesmo idêntica, fazendo com que a convergência do algoritmo para uma solução factível fosse muito lenta. Assim, propõem-se aqui diferentes formas de redução para contornar essa situação. Na linha 17 a capacidade é atualizada com o maior valor entre
β.δ e ε. Tomar o valor máximo entre uma porcentagem da capacidade ultrapassada (β.δ)
e uma tolerância definida (ε) é uma maneira de equilibrar as reduções de capacidade. No início do algoritmo, o valores de δ podem ser muito grandes e portanto utiliza-se a porcentagem β. A medida que δ vai se tornando muito pequeno, a tolerância ε é um número pequeno que supera esse valor pequeno de δ e vai ser dominante nas iterações finais do algoritmo, para melhorar e garantir a convergência do algoritmo.
A ideia proposta para lidar com a infactibilidade apresentada no Algoritmo 2 é que as reduções de capacidade comecem de forma mais sutil e se tornem mais agressivas conforme o tempo vai passando, ou seja, o valor de β é atualizado ao longo da heurística. Os parâmetros que influenciam nessa redução são calculados nas linhas de 6 a 13. O valor de β começa pequeno e aumenta à medida que o tempo de execução vai se aproximando do tempo limite, assim: 0 < β1 < β2 <1 e β3 = 1. Uma outra estratégia utilizada também
para tentar encontrar uma solução factível dentro do tempo limite é reduzir a capacidade de todos os períodos e máquinas por um fator ϕ quando o tempo decorrido está entre 1/3 e 2/3 do tempo limite. Testes computacionais mostraram que essas reduções são efetivas uma vez que sempre é encontrada uma solução factível para todas as instâncias testadas no Capítulo 6. As definições dos valores de β1, β2, ϕ e ε são feitas empiricamente através
de testes iniciais.
Essa estratégia utilizada aqui para reduzir a capacidade de acordo com o tempo disponível da heurística é diferente da estratégia proposta emToscano, Ferreira e Morabito (2015) e Toscano, Ferreira e Morabito (2017), que apresentam uma heurística parecida com a HE1 e HE2. Os autores utilizam uma estratégia de redução de capacidade com o foco para obtenção de soluções com mais qualidade e portanto, acabam por não encontrar solução factível para algumas instâncias dentro de um tempo de execução definido. A diferença no Algoritmo2para os trabalhosToscano, Ferreira e Morabito(2015) eToscano, Ferreira e Morabito(2017) é a maneira com que β é calculado ao longo da heurística. Em Toscano, Ferreira e Morabito (2015) e Toscano, Ferreira e Morabito (2017) o valor de β é definido a priori e mantido durante toda a heurística.
A diferença entre as heurísticas do tipo A e do tipo B é o passo de redução de capacidade. Na heurística tipo B, a capacidade é reduzida apenas para o primeiro par (m, t) identificado com capacidade excedida. Quando o par (m, t) é identificado, a redução
5.1. Heurísticas de decomposição do problema em estágios 103
de capacidade é aplicada e o modelo matemático é resolvido novamente. Assim, as linhas de 15 a 18 no Algoritmo 2 são substituídas pelas linhas de 14 a 19 descritas no Algoritmo 3.
Nas próximas seções são descritos os modelos matemáticos utilizados nessas heurís- ticas.
Uma vez que neste trabalho foram encontradas casos de tempos e custos dependentes e independentes da sequência, são propostos modelos matemáticos para os estágios I e II para os dois casos: dependente da sequência (DS) e independente da sequência (IS). Logo, a partir das heurísticas HE1 e HE2, são obtidas oito variações definidas na Figura 23.