O problema da mochila bidimensional estudado neste trabalho se define como cortar de um retângulo que se denomina mochila (chapa, lâmina ou objeto) de altura H e largura W, um conjunto de n retângulos que se denominam peças (itens), cada peça i possui de altura hi, largura wi, número de exemplares bi e custo associado ci (aonde i = 1,..., n). A função objetivo é definida pela Equação 1 e consiste em maximizar o custo associado ao conjunto de peças cortadas, zi é uma variável inteira que indica o número de exemplares da peça i que devem ser cortadas. 1 n i i i max c z = ⋅
∑
(1) Sujeito a:1 - As peças empacotadas não devem superar os limites da mochila. 2 - As peças não devem sobrepor-se entre elas.
3 - 𝑧𝑖 ≤ 𝑏𝑖, as peças atribuídas não devem superar a demanda por tipos de peças. A Equação 1 e as Expressões 1 – 3 representam o problema geral.
Neste trabalho se estudam diferentes variantes que são encontradas na indústria. As características destas variantes podem ser incorporadas ao adicionar expressões ou modificar alguma destas.
As características deste problema são as seguintes:
i) Valores das peças: se o custo associado da peça não está relacionado com a área, a Expressão 1 representa perfeitamente esta variante. Por outro lado, se o custo associado da peça deve ser a área, deve ser agregada a Equação 2.
𝑐𝑖 =ℎ𝑖 ∙ 𝑤𝑖 (2)
ii) A orientação das peças: se a orientação das peças é fixa, não é necessário adicionar nenhuma expressão. Por outro lado, se é permitido rodar as peças 90 graus, deve-se realizar um pré-processo que identifique as peças i e k tais que ℎ𝑖 =𝑤𝑘 e 𝑤𝑖 =ℎ𝑘, e para estas fazer 𝑏𝑖 = 𝑏𝑖 +𝑏𝑘, (ou seja, agrupar por tipos de peça), além disto, se deve adicionar a Expressão 4.
4 - As peças podem rodar 90°
iii) Os padrões de corte: para os padrões tipo guilhotina se deve adicionar a expressão correspondente. A Expressão 5 para os padrões tipo guilhotina de duas etapas de corte, a Expressão 6 para os padrões tipo guilhotina de três etapas e a Expressão 7 para os padrões tipo guilhotina sem etapas. Por outro lado, para os padrões tipo não guilhotina, se deve adicionar a Expressão 8 se requeremos um padrão de corte não guilhotina de primeira ordem, caso contrário, se o padrão de corte é não guilhotina de ordem superior não é necessário adicionar nenhuma expressão.
5 - Só o uso de cortes guilhotina é permitido e duas etapas de corte no máximo. 6 - Unicamente o uso de cortes guilhotina é permitido e três etapas no máximo. 7 - Unicamente o uso de cortes tipo guilhotina é permitido.
8 - Unicamente o uso de corte tipo guilhotina e cortes tipo não guilhotina de primeira ordem.
iv) A demanda de peças ou o limite máximo de número de peças a cortar de cada tipo: se não existe um limite máximo de exemplares por tipo de peça se deve modificar a Expressão 3 por a Expressão 9. Por outro lado, foi imposto um limite máximo bi de exemplares por tipo de peça não é necessária adicionar nenhuma expressão.
9 - 𝑧𝑖 ≤ 𝑀𝑖, onde Mi é um número o suficientemente grande. 𝑀𝑖 = �𝑤𝑊∙𝐻 𝑖∙ℎ𝑖� 3.3 MODELO MATEMÁTICO
Distintos modelos matemáticos para representar os mesmos tipos de problema já têm sido propostos, com a finalidade de encontrar melhoras na solução através de uma modelagem eficiente, é por isto que neste estudo fazemos uma revisão dos diferentes modelos e se expõe somente dois porque são os mais próximos aos problemas propostos, além de apresentar resultados satisfatórios para o problema da mochila bidimensional.
Gilmore e Gomory, (1961; 1963) apresentam o primeiro modelo matemático para o problema de corte e empacotamento unidimensional. Gilmore e Gomory, (1961; 1963) estudam cuidadosamente o problema da mochila quando este é aplicado para o corte de peças em uma e duas dimensões.
Biro e Biros, (1985) caracterizam os padrões não guilhotina usando teoria de grafos. Beasley, (1986) estudou o problema da mochila com padrões de corte tipo não guilhotina, propondo um modelo de programação linear inteira para determinar as coordenadas discretas às quais os itens podem ser localizados. Um modelo similar foi introduzido por (HADJICONSTANTINOU; CHRISTOFIDES, 1995). Scheithauer e Terno (1993) propõem modelos para empacotamento de polígonos convexos e não convexos.
Fekete e Schepers, (1997) usam a teoria de grafos para determinar um empacotamento factível sem sobrepor as peças. Lodi et al. (2002; 2004) apresentam um modelo que manipula padrões formados por estantes (níveis), este modelo considera explicitamente restrições de corte tipo guilhotina (mas só uma parte dos padrões guilhotina são considerados). Beasley (2004) apresenta uma nova formulação de corte não guilhotina. Uma boa revisão dos modelos existentes está disponível em (LODI et al., 2004).
Um modelo de programação linear inteira mista (MILP, do inglês Mixed Integer Linear Programming) para o problema de empacotamento tridimensional em contêineres, com número polinomial de variáveis e restrições, é apresentado por (CHEN et al., 1995). Este modelo pode ser visto como uma extensão à técnica de modelagem proposta por (ONODERA et al., 1991). Para um problema de localização de blocos bidimensionais, o modelo tem como base a enumeração de todas as possíveis localizações relativas de cada par de peças. Os experimentos computacionais apresentados em (CHEN et al., 1995) mostram que o modelo proposto é muito ineficiente na solução de instâncias práticas de empacotamento. A mesma técnica foi usada por (DANIELS et al., 1994) para modelar o problema de empacotamento geral (bidimensional) de polígonos, neste mesmo caso, o uso direto do modelo prova ser ineficiente na prática. Benet al. (2008) apresentam um modelo baseado na caracterização e modelagem dos padrões guilhotina para o problema de empacotamento em tiras infinitas (strip packing problem), o qual pode ser facilmente adaptado para o problema da mochila. Como se mostra na revisão bibliográfica anterior não existem modelos matemáticos que descrevam completamente todo os problemas de interesse deste estudo. Porém alguns modelos propostos na literatura são facilmente adaptáveis. Por outro lado, a maioria destes modelos não são satisfatórios na resolução de casos práticos do problema na vida real (BEASLEY, 2004; BEN et al., 2008; CHEN et al., 1995). O enfoque deste trabalho é uma metodologia aproximada, dado que o objetivo é resolver aplicações reais.
Devido a grande quantidade de variantes do problema da mochila consideradas neste trabalho, não são ilustrados os modelos matemáticos das diferentes versões do problema. Na literatura existe uma grande quantidade de formulações propostas e muitas destas são adaptáveis aos problemas indicados neste trabalho, porém nem para todas as variações propostas existe uma formulação matemática na literatura. Isto dificulta uma comparação e uma medição da qualidade da metodologia de solução proposta aqui. Por outro lado, as formulações matemáticas estão fora do alcance deste estudo, pelo que se realizará uma comparação direta com os resultados alcançados com outras metodologias de solução (aproximadas) propostas na literatura.