O Problema de Corte de Estoque
Características típicas:
• problema de várias mochilas - seleção de objetos
• muitos itens devem ser produzidos, porém, de poucos tipos
(alta repetição)
• muitos objetos (barras) dever ser cortados, porém, de poucos tipos.
Muitos objetos serão igualmente cortados (padrões de corte)
Exemplo: Cortar barras de 240 cm (estoque) para a produção de
1000 itens de 30 cm (tipo 1)
1250 itens de 42 cm (tipo 2)
2000 itens de 45 cm (tipo 3)
• total de 4250 itens cortados de apenas 3 tipos (bin-packing?)
• muitas barras devem ser igualmente cortadas
(padrão de corte = maneira particular de cortar uma barra,
que deve ser repetida várias vezes)
• Qual o número mínimo necessário de barras ?
• Como devem ser cortadas as barras (padrões de corte) ?
A cada padrão de corte associamos um vetor m-dimensional que
contabiliza os itens produzidos:
a  1 ,  2 ,...,  m 
onde i é o número de itens do tipo i no padrão.
L
(1)
(1)
(2)
(4) (4)
l1
l1
l2
l4
 a = ( 2 1 0 2 )T
l4
Um vetor (1 2 ...m ) corresponde a um padrão de corte se:
l11  l2 2  ...  lm  m  L
 i  0 e inteiro, i  1,2,..., m
Restricões de processo
Restrições adicionais de processo
• F = Número Máximo de Facas
Facas
(1) (1)
(3)
(4)
2 Facas laterais para
imperfeições!
5 Facas  4 itens!
Maximizar v1 x1  v2 x2  ...  vm xm
Sujeito a: l1 x1  l2 x2  ...  lm xm  L
x1  x2  ...  xm  F  1
xi  0 e inteiro, i  1,..., m.
Restricões de processo
Restrições adicionais de processo: Cortagem em estágios
O Problema da Mochila Compartimentada
Compartimentos carregados com itens de mesma classe
Ex. medicamentos, alimentos, roupas limpas, roupas sujas, etc.
Os compartimentos têm tamanhos máximos e mínimos e cada
novo compartimento inserido na mochila perde-se espaço
L = 30
limites mínimo e máximo e perdas para os compartimentos
+
Lkmin = 5
Lkmax = 9
Sk = 1
O Problema da Mochila Compartimentada
fase 1
fase 2
2
2
A2
2
2
A2
1
2
A1
6
C2
Observações:
• Ao reconhecer um padrão de corte pelo seu vetor associado,
não distinguimos entre padrões do tipo:
(1)
(3)
(1)
(1)
(2)
(1)
(2)
(3) (3)
 (2 1 2)T
(3)
 (2 1 2)T
 Padrões equivalentes
Modelagem matemática:
1. Defina todas as possíveis maneiras de se cortar os objetos em
estoque, isto é, todos os padrões de corte
problema combinatório
2. Decida quantas vezes cada padrão de corte deve ser utilizado
para atender a demanda
O Problema de Corte de Estoque
Exemplo:
Comprimento das barras em estoque: L = 120cm
Comprimentos (demanda) dos itens: (m = 3)
l1 = 30cm (d1= 1000)
l2 = 42cm (d2=1250)
l3 = 45cm (d3=2000)
30
30
30
30
Padrão 1:
42
42
36
Padrão 2:
45
45
30
Padrão 3:
45
Padrão 4:
45
30
 a1 = (4 0 0)T
 a2 = (0 2 0)T
 a3 = (0 0 2)T
 a4 = (1 0 2)T
O Problema de Corte de Estoque
Variáveis de decisão:
xj : número de vezes que o padrão j é utilizado, j = 1,2,...
a1 x1  a2 x2  a3 x3  a4 x4  ...  d
 4
0 
0 
1 
1000 
0 x  2 x  0 x  0 x  ...  1250 
  1   2   3   4


0
0
2
2
2000 
Base inicial formada pelos
padrões homogêneos
O Problema de Corte de Estoque
Modelagem Matemática
• Apenas um tipo de barra em estoque em quantidade ilimitada.
• Diversos tipos de barra em estoque em quantidade ilimitada.
• Diversos tipos de barra em estoque em quantidade limitada.
• Problemas de dimensão maiores que 1.
O Problema de Corte de Estoque
Apenas um tipo de barra em estoque
Dados do problema:
m : número de tipos de itens
li : comprimento do item tipo i
di : quantidade demandada do item tipo i
L : comprimento (único) da barra em estoque
c : custo de cada barra em estoque
Objetivo: Atender a demanda ao custo mínimo.
O Problema de Corte de Estoque
modelo básico
Etapa 1: Defina todos os possíveis padrões de corte, ou
seja, determine todas as soluções do sistema:
l11  l2 2  ...  lm  m  L
 i  0 e inteiro, i  1,2,..., m
Suponha que as soluções sejam:
11 
 
a1   21 
 
 
 m1 
Padrão 1
12 
 
a2   22 





 m 2 
Padrão 2
...
1n 
 
an   2 n 





 mn 
Padrão n
O Problema de Corte de Estoque
Etapa 2: Seja xj o número de vezes que o objeto (barra) é cortado
usando o padrão de corte j, j = 1,…,n.
Resolva:
Minimizar f ( x)  c( x1  x2  ...  xn )
sujeito a: a1 x1  a2 x2  ...  an xn  d
x1  0, x2  0,..., xn  0 e inteiros.
Otimização linear
método simplex –
geração de colunas
m equações – algumas dezenas
n variáveis – centenas de milhares !
O Problema de Corte de Estoque
Alterações no modelo básico
1. Demanda com tolerância:
Ex: i = 0,05
1   i  di
di
di
1   i  di
di
Minimizar f ( x)  cT x
sujeito a: d   Ax  d 
x0
O Problema de Corte de Estoque
Alterações no modelo básico
2. Função “perda”:
f ( x)  c1 x1  c2 x2  ...  cn xn
c j  L  1 j l1  ...   mj lm 
L
Padrão j:
(1) (1)
1j l1
(2)
(2)
2j l2
(2)
(m)
mj lm cj
O Problema de Corte de Estoque
Alterações no modelo básico
3. Unidade de demanda em toneladas
(bobinas na indústria de papel, metalúrgica,…)
Dados adicionais:
T : peso (ton) de cada objeto
L
(i)
T/L = peso específico
(i)
(ton/cm)
li
 ij li
T = peso (ton) dos itens i no padrão j
L
T


  ij li  x j  di
L
j 1 
n
i  1,..., m
Número de bobinas cortadas
usando o padrão j.
li
T
= peso do item i
L
Mudança de variável
yj  T xj
ton. no padrão j
O Problema de Corte de Estoque
Alterações no modelo básico
4. Corte de retângulos
(indústria de papel)
wi
wi
fibra
li
Facas
(1) (1)
(3)
(4)
fibra
li
O Problema de Corte de Estoque
Alterações no modelo básico
Sentido da fibra irrelevante  bobina pode ser cortada nos
comprimentos: l1 , l2 ,..., lm , w1 , w2 ,..., wm
Padrão j:

lm1 lm  2 l2m
Mochila com 2m itens
, 2 j ,..., mj , m1, j , m 2, j ,..., w2 m, j 
T
1j
mesmo item: retângulo l1  w1
1j + m+1,j = qde. do item 1 no padrão j
1 j   m 1, j 


 2 j   m  2, j 

aj  



 mj   2 m , j 
O Problema de Corte de Estoque
Diversos tipos de barra em estoque
em quantidade ilimitada
• Máquinas diferentes produzem os objetos (comp. diferentes)
em quantidades suficientemente grandes para atender toda a
demanda (indústria de papel).
• Objetos adquiridos no mercado, em tamanhos diferentes, onde
a oferta é grande (construção civil).
O Problema de Corte de Estoque
Barras ilimitadas em estoque
• Dados de demanda
m : número de tipos de itens
li : comprimento do item tipo i
di : quantidade demandada do item tipo i
Dados de estoque:
N : número de tipos de objetos em estoque
Lk : comprimento do objeto (barra) tipo k
ck : custo da barra tipo k
 k 
 11 
 k 
a 1k   21 
 
 k 
 m1 
 k 
 12 
 k 
a 2 k   22 
 
 k 
 m 2 
...
 k
 1nk
 j
 2n

k
a n j ,k 


 j
 m nk








Padrões de corte
para barra de
comprimento Lk
O Problema de Corte de Estoque
Barras ilimitadas em estoque
Etapa 2:
xij o número de vezes que o objeto j é cortado usando o
padrão de corte i.
n1
n2
nN
i 1
i 1
Minimizar f ( x11 , x21 ,...)   c1 xi1   c2 xi 2  ...   c N xiN
sujeito a
n1
n2
i 1
nN
i 1
i 1
i 1
 ai1 xi1   ai 2 xi 2  ...   aiN xiN  d
xij  0 e inteiros.
O Problema de Corte de Estoque
Diversos tipos de barra em estoque
em quantidades limitadas
Dado adicional:
Minimizar
ej : quantidade disponível da barra j, j=1,…,N.
n2
nN
i 1
i 1
i 1
f ( x11 , x21 ,...)   c1 xi1   c2 xi 2  ...   c N xiN
n1
sujeito a
n1
a
nN
i 1
i 1
x   ai 2 xi 2  ...   aiN xiN  d
i1 i1
i 1
n2
n1
x
i 1
 e1
i1
n2
x
i 1
 e2
i2

nN
x
i 1
xij  0 e inteiros.
iN
 eN
O Problema de Corte de Estoque
Problemas de dimensões maiores que 1
A modelagem anterior ainda é válida:
Etapa 1: definição dos padrões de corte (mais dificil)
caso unidimensional: o número de itens no padrão descreve
facilmente o padrão de corte.
Caso bidimensional: arranjar uma quantidade de retângulos
sobre uma placa, sem sobreposição, não é trivial.
Regras de cortagem: cortes guilhotinados, estagiados,
não guilhotinados guillotinados
Etapa 2: quanto usar de cada padrão para atender a demanda
(mesmo modelo de otimização linear)
O Problema de Corte de Estoque Bidimensional
LW
li wi
(2)
(2)
(1)
(1)
(2)
(3)
(5)
(4)
(5)
(3)
(3)
(4)
(3)
(3)
(4)
Definição. Um corte sobre uma placa retangular que produza
dois novos retângulos é chamado corte guilhotinado ortogonal,
ou simplesmente, corte guilhotinado.
Uma sequência de cortes guilhotinados, aplicados sobre a placa e
sobre os retângulos resultantes produz um
padrão de corte guilhotinado
1
3
2
1
1
2
5
5
4
1
3
3
6
a = (3, 1, 2, 0, 1)T.
Os cortes guilhotinados podem ser organizados em estágios da seguinte
forma: Num primeiro estágio, cortes guilhotinados são feitos
sobre a placa. Em seguida, num segundo estágio, os retângulos obtidos
são cortados perpendicularmente ao cortes do estágio anterior, e assim
por diante, são definidos estágios de corte.
Definição Se o número permitido de estágios é limitado por k,
dizemos que o padrão de corte resultante é um padrão de corte
guilhotinado em k-estágios.
1º estágio
2º estágio
2
1
5
2
4
Um padrão de corte bidimensional guilhotinado 2-estágios:
1º estágio: corte vertical e 2º estágio: corte horizontal
O problema de corte bidimensional guilhotinado em 2-estágios
i) Determinar os melhores padrões para as faixas: Lw1 , Lw2 … Lwm.
j
wk
k
i
L
Itens que podem ser cortados na faixa k: Wk = { i tal que: wi  wk }
Vk  Máximo
sujeito a:

vi  ik

li  ik  L
i  Wk
i  Wk
ik  0, inteiro, i=1,..,m
ii) Determinar quantas vezes cada faixa deve ser utilizada no padrão
bidimensional.
Como cada faixa k tem largura wk e a largura da placa é W, temos então
de resolver o seguinte problema da mochila:
V= Maximizar V11 + V22 + …+Vrr
sujeito a: w11 + w22 + …+wrr  W
10, 2 0,…, r0 e inteiros.
Exemplo. Placa LW = 110110 m = 4 itens,
comprimentos, larguras e valores de utilidade:
i
li  wi
vi
1
20 30
6
2
30 40
12
3
50 60
30
4
60 60
36
Faixa 1: 11030
W1 = { 1 }
1
1
1
1
L=110
1
Faixa 2: 11040
W2 = { 1, 2 }
Faixa 3: 11060
W3 = { 1, 2, 3,4 }
1
2
2
2
3
4
L=110
L=110
V1 =30
V2 =42
V3 =66
V = Maximizar 30 1 + 42 2 + 663
sujeito a: 301 + 402 + 603 110
10, 2 0, 30 e inteiros.
Solução: 1 =1, 2 = 1, 3 = 1, V = 138.
1
1
1
1
1
1
W=110
2
2
2
3
4
L=110
O Problema de Corte de Estoque Inteiro
Heurísticas de arredondamento da solução
Minimizar
sujeito a
f  x   cT x
Ax  d
x  0 e inteiro.
~
x
geração de
colunas
y  ~x 
?
Arredondamento
da solução
Problema Residual: dd-Ay
heurísticas alternativas:
Revisão do arredondamento
Repetir até que:
~
x 0
 