1
O Problema do Corte
Bidimensional
Indústrias de papel, tecido, vidro, barras de aço , entre outras,
fabricam seus produtos em peças de tamanho fixo (tamanho
padrão).
Estas peças são depois divididas em tamanhos
menores a serem definidos de acordo com a necessidade do
cliente.
O problema do corte consiste em determinar como
cortar o menor número de peças de tamanho padrão LxC,
atendendo a uma demanda , bi, por itens de tamanho ,lixci
i=1,...,m.
2
O Problema do Corte
Bidimensional
Peça Padrão de tamanho LxC:
C
L
Itens pedidos:
l1xc1
l2xc2
l3xc3
3
Esquemas de corte para o Problema do Corte
Bidimensional
Corte tipo Guilhotina:
O corte é feito de uma aresta à aresta oposta, paralelo
as duas arestas restantes.
C
Esquema 1:
4 peças l1xc1
Esquema 2:
2 peças l1xc1
1 peça l2xc2
1 peça l3xc3
l1xc1
l1xc1
l1xc1
l1xc1
L
C
l1xc1
l2xc2
l1xc1
l3xc3
L
4
Esquemas de corte para o Problema do Corte
Bidimensional
Esquema Não Guilhotinado
1 peça l1xc1
1 peça l2xc2
1 peça l3xc3
C
l1xc1
l2xc2
l3xc3
L
5
O Problema do Corte Bidimensional Exemplo 1
Vamos considerar um problema onde:
Tamanho Padrão
L = 85 cm
C = 170 cm
Itens
l1xc1= 50x20 cm, l2xc2=30x60cm, l3xc3=80x85cm
demanda para os itens menores é:
d1= 100, d2=150, d3=130
6
Esquemas de corte para o Problema do Corte
Bidimensional
170
Como Definir
um
Esquema de corte?
30
170
50
Estágio 1:
Construção
das
faixas
170
50
7
Esquemas de corte para o Problema do Corte
Bidimensional
Estágio 2: Placa 85x170
Montagem
das
faixas
na largura
da
peça padrão
Esquema 1
30
170
50
8
Esquemas de corte para o Problema do Corte
Bidimensional
Estágio 2:
Montagem
das
faixas
na largura
da
peça padrão
Esquema 2
170
85
9
Esquemas de corte para o Problema do Corte
Bidimensional
Como Definir um Esquema de corte?
Dois estágios:
ordene os itens: li<=li+1
Estágio 1:
- Para todas as larguras li, posicione os itens lj <= li na faixa
lixC
(defina um esquema de corte unidimensional - C)
Estágio 2
- Posicione as faixas lixC na largura L
(defina um esquema de corte unidimensional - L)
10
Construindo um modelo para o Problema do Corte
Bidimensional
Neste problema temos:
elementos conhecidos: esquema de corte, demanda de cada ítem
elementos desconhecidos: quantas vezes um determinado esquema
de corte será usado
objetivo a ser alcançado: usar o menor número possível de
esquemas de corte
restrições: o número de itens obtidos com os esquemas de corte
usados de ser maior ou igual a demanda
11
Construindo um modelo para o Problema do Corte
Bidimensional
Variáveis de decisão
Defina então:
x j = número de vezes que o esquema de corte j
será usado.
Objetivo
Usar o menor número possível de esquemas de corte:
minz  x1  x2  ...  xn
12
Construindo um modelo para o Problema do Corte
Bidimensional
Restrições
O número de itens obtidos de cada tipo deve ser maior ou
igual a demanda.
Seja aij o número de peças do tipo i obtidas usando o
esquema de corte j. Para atender a demanda do item i
temos que:
ai1 x1  ai 2 x2  ...  ain xn  bi
13
Modelo de Otimização Para o Problema do Corte
Bidimensional
min(ou max)z  x1  x 2  ...  x n
sujeit o a
a11 x1  a12 x 2  ...  a1n x n  b1
a 22 x1  a 22 x 2  ...  a 2 n x n  b2
...
a m1 x1  a m 2 x 2  ...  a mn x n  bm
x1 , x 2 ,...x n  0, e int eiras
14
Modelo de Otimização Para o Problema do Corte
Bidimensional
Podemos escrever as restrições do problema na forma
matricial:
 a11 a12 ... a1n
a
 21 a 22 ... a 2 n
 ...

a m1 a m 2 ... a mn

  x1   b1 
 x  b 
  2  2 
 *     
    
  x n  bm 
    
Observe que cada coluna da matriz esta associada a
um esquema de corte.
Em geral n ==> 
Impossível de ser gerado ou mesmo armazenado:
Geração de colunas em dois estágios
15
Problema do Corte Bidimensional
Exemplo 1 - Solução
16
Problema do Corte Bidimensional
Exemplo 1 - Solução
17
Problema do Corte Bidimensional
Exemplo 1 - Solução
18
Problema do Corte Bidimensional
Exemplo 1 - Solução
19