Relatorio MODAD TG 2

“A column generation heuristic for the twodimensional two-staged guillotine cutting stock problem with multiple stock size”

Instituto Superior de Engenharia do Porto

Trabalho realizado por: Nuno Correia nº1070599
Fábio Pinto nº 1080813
Tiago Silva nº 1091365

Introdução
Este problema de corte consiste em determinar a "melhor" solução de cortar unidades de material, de maneira a produzir um conjunto de unidades menores
(itens),o problema aparece em diversos processos industriais de corte onde os objectos, em geral disponíveis em Stock, correspondem placas metálicas e de madeira, chapas de vidro e fibra de vidro, folhas de papel, etc., esses itens contêm dimensões especificadas e procuras diferentes. Esses cortes vão ser realizados por guilhotinas de duas fases de corte, com tamanho stock múltiplo (MS2DCSP), isto é, o bidimensional problema de corte de stock
(2DCSP) em que: todos os itens devem ser obtidos com cortes em duas fases, onde cada fase é composta por um conjunto de paralelo guilhotina cortes realizados na forma obtida na anterior fase (que permitem o corte, isto é, uma terceira fase de corte pode ser utilizado para separar um rectângulo de uma área de resíduos); e caixas de tamanhos diferentes estão disponíveis. O nosso trabalho está organizado da seguinte forma na primeira parte temos um modelo clássico de corte com stock, na segunda parte, temos um modelo e um algoritmo heurístico para a geração de padrões de corte, e na terceira parte apresenta-se a heurística geral de geração de colunas e por fim os resultados computacionais e o seu comentário.

(1) Restrição para da procura (produção≥ procura) (2) Padrões de corte inteiros positivos
(3)
(3) Padrões de corte

Fig1- À esquerda encontra-se um corte feito por uma guilhotina de duas etapas, cortes que não podem ser realizados pela guilhotina de duas etapas.
2 Descrição do Problema

Como este modelo contem uma quantidade exponencial de variáveis é necessário adicionar restrições para optimizar.

2.1