Effekter på BNP i lys av IS-RR-PK- modellen

O termo heurística é derivado do grego heuriskein, que significa descobrir ou achar (Reeves, 1993). Em otimização podemos definir uma heurística como sendo um método de solução de problemas de otimização que visa encontrar, com tempo e custo razoáveis, uma boa solução para o problema, sendo que não há garantia de otimalidade para a solução encontrada. Grande parte dos trabalhos citados na revisão bibliográfica desta tese utilizam heurísticas ou métodos híbridos que incluem heurísticas para resolver os modelos estudados.

Os pacotes de otimização possuem heurísticas implementadas (em geral heurísticas de arredondamento), pois estas podem também colaborar na redução do gap de otimalidade dos problemas, fornecendo soluções inteiras de forma rápida. Assim, a utilização de um método híbrido que inclua uma heurística pode acelerar o processo de solução de métodos como Branch and Bound, reduzindo a árvore de enumeração implícita. Softwares como CPLEX possuem, inclusive opções que controlam a taxa de aplicação de heurísticas na solução dos modelos. Por exemplo, na versão 10 do software CPLEX foi incluída a heurística Relaxation Induced Neighborhood Search, Danna et al (2005). Esta heurística explora a vizinhança da solução corrente para tentar melhorá-la. A exploração da vizinhança é formulada como um problema de otimização inteiro misto (subproblema), que é resolvido recursivamente até um limite de

nós.

Para se utilizar meta-heurísticas tais como Busca Tabu, Simulated Annealing e Algo- rítmos Genéticos, é necessário especializá-las para o problema a ser resolvido (Reeves, 1993). Algoritmos híbridos que combinam heurísticas também têm sido utilizados. No trabalho de Meyr (2002), onde o GLSP é estendido para incluir várias máquinas, o modelo é resolvido com busca local, Simulated Annealing e Threshold Accepting, combinado com um algoritmo de re- otimização dual. Fleishmann e Meyr (1997) desenvolveram um algoritmo de busca local para resolver exemplares do modelo GLSP mono máquina.

Toledo (2005) e Toledo et al (2006b) utilizam uma abordagem heurística para a so- lução do problema de programação da produção de bebidas, baseada em algoritmos genéticos. Gutiérrez e Pizzolato (2004) desenvolvem uma heurística baseada no método de Singh e Fostes (1987), para resolver o problema de dimensionamento e sequenciamento da produção de bebi- das, . Essa heurística é orientada em função do período de planejamento mais apropriado às conveniências da programação, determinando assim seqüências de produção realistas e, além disto, estima os custos anuais de set up e manutenção de inventário. A heurística também usa as vantagens de outros artifícios, tais como permitir tempos ociosos, e uma maneira mais efetiva para determinação da seqüência final de produção.

Gupta e Magnusson (2005) desenvolvem uma heurística para resolver um modelo de dimensionamento e sequenciamento da produção. A idéia principal da heurística é gerar uma solução inicial factível, assumindo que o set up carryover é utilizado em cada período. Os próximos set ups são seqüenciados de forma gulosa. O passo final começa com o último período e busca as capacidades não usadas em períodos precedentes. A heurística compara os custos de set up e estoque, e verifica se a produção pode ser removida para períodos anteriores que tenham folga de capacidade suficiente, com efeito de redução do custo total. Este passo de refinamento continua até que todas oportunidades para mover a produção tenham se esgotado. A heurística foi implementada para tempos de set up positivos e fixos.

Heurística Relax and Fix

Outra heurística utilizada na solução de modelos de dimensionamento de lotes e tam- bém em modelos de dimensionamento e sequenciamento de lotes é a heurística relax and fix (Wolsey, 1998). Nessa heurística o conjunto das variáveis inteiras é particionado em P conjun- tos disjuntos Qi, i = 1, ..., P , de diferentes importâncias. O número P de conjuntos determina

o número de iterações da heurística. Em uma iteração n, as variáveis do conjunto Qn são defi-

nidas como inteiras e as variáveis dos demais conjuntos são relaxadas. O problema resultante (subproblema) é então resolvido. Se o subproblema é infactível o processo para, caso contrário, se o subproblema for factível, apenas as variáveis do conjunto Qn, ou parte delas, são fixadas

em seu valor corrente, e o processo se repete para os outros conjuntos. Dependendo do sub- problema, pode-se ter várias opções de partições do conjunto de variáveis inteiras, tais como: particionar o conjunto de variáveis de acordo com períodos, itens, estágios. No caso de modelos que consideram vários itens, períodos, máquinas e estágios, as variáveis binárias são indexadas por itens, períodos, máquinas e estágios. Estes conjuntos e a combinação entre eles são opções na definição das partições a serem usadas na heurística relax and fix. O critério para a fixação das variáveis também é flexível. Por exemplo no modelo GLSP, (3.41 )-(3.48), que possui as variáveis indexadas por sub-períodos; suponha que a partição tenha sido feita por período. Após resolver o problema resultante, pode-se escolher fixar apenas as variáveis binárias correspon- dentes a sub-períodos onde tenha ocorrido produção. Um algoritmo geral para a heurística relax and fixé:

Algoritmo Relax and Fix

Inicialização: Defina uma partição Q1, ..., QP para o conjunto de

variáveis inteiras, e o critério para fixação das variáveis. Para i = 1, ..., P :

Passo 1: Faça as variáveis de Qiinteiras, relaxe as demais, e resolva o subproblema associado.

Passo 2: Se o problema for infactível, pare.

Se o problema for factível, verifique quais variáveis satisfazem o critério para fixação, e fixe seus valores.

No passo 2 é importante observar que há fatores que podem levar o subproblema a infactíbilidade, mas dependendo do fator, pode-se inserir mais um passo no algoritmo para tentar modificar este status da solução. Isso pode acontecer, por exemplo, se forem fixadas todas as variáveis do período. Neste caso pode ser útil voltar, e relaxar algumas variáveis do subproblema, conforme Escudero e Salmeron (2005).

No trabalho de Federgruen (2004), a heurística relax and fix é considerada como um caso particular de uma heurística de intervalos progressivos. Nas heurísticas de intervalos progressivos o horizonte de planejamento é dividido em J conjuntos Ti de períodos, para i =

0...J, tal que 0 = T0 ≤ T1 ≤ T2 ≤ ... ≤ TJ; o conjunto de variáveis contínuas é dividido

em J conjuntos tj, para j = 1...J, onde 0 = t1 ≤ t2 ≤ ... ≤ tJ. Estas divisões determinam,

respectivamente, os períodos a serem considerados em cada iteração, e as variáveis contínuas a serem fixadas em cada iteração. Para determinar quantas variáveis inteiras serão fixadas, é definido o parâmetro τ, de forma que em uma iteração l, Tl− τ variáveis inteiras serão fixadas,

onde τ ≥ Tl − Tl−1 ⇒ Tl−1 ≥ Tl − τ . Em uma iteração l o problema terá Tl períodos,

tl ≤ Tl−1 variáveis contínuas fixas e (Tl− τ ) variáveis inteiras fixas. Observe que o número de

variáveis inteiras fixas pode ser diferente do número de variáveis contínuas fixas. Pode haver ainda sobreposição de períodos, pois τ pode ser maior do que Tl− Tl−1.

Federgruen et al (2004) consideram que na heurística relax and fix não há fixação de variáveis contínuas, o que dá o máximo de flexibilidade na obtenção de soluções factíveis. O caso extremo de menor flexibilidade é a fixação de todas as variáveis contínuas da iteração, ou seja, tl = Tl−1e ainda τ = Tl− Tl−1. Estes dois casos da heurística de intervalos progressivos

são denominadas, respectivamente, heurística de horizonte expandido e heurística de particiona- mento estrito. Estas heurísticas foram aplicadas na solução de um modelo de dimensionamento de lotes do tipo big bucket capacitado com set up.

No trabalho de Dillenberger et al (1994), a heurística relax and fix com a partição do conjunto de variáveis por períodos foi utilizada para resolver um modelo de dimensionamento de lotes multi máquinas, multi períodos e multi itens. O número de iterações da heurística é dado então pelo número de períodos do modelo. Em Kelly e Mann (2004), um problema de engenharia química é resolvido utilizando a heurística relax and fix em que as variáveis a serem fixadas são agrupadas de acordo com os processos de produção pelos quais os itens passam. Em Kelly e Mann (2004) a partição não é determinada previamente por meio de conjuntos. Para determinar quais variáveis serão inteiras e quais serão fixadas, a solução da relaxação linear do modelo é avaliada e as variáveis binárias com valores próximos a 0.5 são mantidas binárias, enquanto as variáveis com valores 0 e 1 são fixadas.

Escudero e Salmeron (1995) comparam variações da heurísticas relax and fix na so- lução de um modelo de sequenciamento de projetos. Cinco heurísticas utilizam o conceito de valor da variável para fazer a partição do conjunto de variáveis. Nesse critério de partição, a cada variável é atribuído um valor e as variáveis são ordenadas de forma decrescente de valor. Um parâmetro k, determina o número de iterações da heurística. Por exemplo, sendo n′ _{o nú-}

mero de variáveis inteiras e n o número total de variáveis que se deseja por iteração, pode-se definir então k = ⌈n

n′⌉. As cinco estratégias variam então pelo valor atribuído a cada variável e

pelo parâmetro k.

No trabalho de Pochet e Van Vyve (2004), a heurística relax and fix é comparada à Heurística Iterativa de Estimativa de Produção, (Iterative Production Estimate Heuristic - IPE). Esta heurística trabalha com soluções fracionárias próximas de boas soluções inteiras, ao invés de trabalhar com a solução da relaxação linear do problema original. A idéia é usar uma aproximação linear para melhorar o limitante inferior da variável de set up y. Quando uma solução fracionária é fornecida, o valor da variável de produção fornece um limitante inferior C′ _{para o set up. Se for possível melhorar este limitante, a variável y pode ficar mais próxima}

de 0 ou 1, e assim de uma solução inteira. O melhor candidato para o limitante é então o valor da variável de produção na relaxação linear. A heurística (IPE), atualiza o limitante e resolve um novo modelo linear. O processo é feito até que y seja 0 ou 1 (um vetor Γ guarda o valor dos limitantes). Este processo pode resultar em saltos no valor da variável x, uma vez que a variável assume no máximo o valor C′_{, que podem levar o algoritmo a não alcançar a solução}

ótima. Para resolver o problema o limitante C′_{é substituído pela função λx}LP

i + (1 − λ)Ci′que

evita saltos grandes. Outra opção para se evitar saltos é remover o limitante superior de xipara

que o valor da variável possa ser maior que C′ _{se necessário, assim os valores de x}

i não saltam

de uma iteração para outra. O modelo estudado é um modelo de dimensionamento de lotes capacitado com tempo e custos de set up. A heurística relax and fix obteve resultados melhores que a heurística (IPE) em exemplares de dimensões pequenas e médias.

A heurística relax and fix também é utilizada de forma híbrida com meta-heurísticas como a Busca Tabu (Pedroso, 2004; Pedroso e Kubo, 2005). Na utilização da heurística relax and fix com Busca Tabu, a heurística relax and fix pode ser utilizada tanto para fornecer uma solução inicial para a Busca Tabu, quanto para reconstrução de soluções. Pedroso e Kubo (2005) utilizam um algoritmo híbrido com a meta-heurística Busca Tabu e a heurística relax and fixna solução de um modelo de dimensionamento de lotes capacitado com set up e atraso. Neste trabalho também é construída uma heurística relax and fix denominada relax-and-fix-one- product. Como o nome sugere, nessa heurística a partição do conjunto de variáveis é feita por período/máquina e itens. A vantagem é resolver subproblemas menores, uma vez que alguns modelos de dimensionamento de lotes mono máquinas, mono períodos e multi itens, ainda são

difíceis de serem resolvidos.

Araújo et al (2004) modelaram o problema de sequenciamento de ligas em indústrias de fundição utilizando a técnica de Horizonte Rolante, e aplicaram uma heurística relax and fixpara melhorar a técnica de Horizonte Rolante. Um método de busca local foi utilizado para fixar as variáveis binárias da heurística.

Em Toledo (2005), uma heurística relax and fix foi aplicada na solução do problema de dimensionamento e sequenciamento da produção de bebidas apresentado no Anexo A. O modelo é capacitado, multi máquinas, multi itens, multi períodos, dois níveis, com tempos e custos de set up dependentes. Nesta aplicação, a heurística não apresentou resultados satisfató- rios. O maior exemplar resolvido possui 258 variáveis binárias, 1390 contínuas e 924 restrições. Para fixar as variáveis, o algoritmo percorre cada período t do fim para o início do horizonte de planejamento, e todos os lotes de xarope dos tanques e de bebidas nas linhas também são percorridos do último para o primeiro lote. A partição do conjunto de variáveis é feita por lotes, sendo que primeiro são fixados os lotes das linhas, e depois os lotes dos tanques. Assim, apenas as variáveis pertencentes a um determinado conjunto de lotes em cada iteração são mantidas binárias. A cada iteração, as variáveis binárias indexadas pelos lotes são então fixadas em seus valores 0 ou 1.

Na presente tese, que também trata o problema de dimensionamento e sequencia- mento da produção de bebidas, é explorada a utilização de heurísticas relax and fix na solução dos modelos propostos (Seção 5.1).