XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
GERAÇÃO DE PADRÕES DE CORTE PRODUTIVOS
PARA A INDÚSTRIA DE MÓVEIS
Altamir G. de Figueiredo
Socorro Rangel
DCCE / IBILCE / UNESP
Rua Cristóvão Colombo, 2265, Jd. Nazareth
150054-000, S.J. do Rio Preto,
[email protected], [email protected]
RESUMO
Neste trabalho, analisamos os padrões de corte adotados por uma Indústria de Móveis, e
identificamos características básicas desses padrões de corte. Conceituamos, a partir dessas
características, os padrões tabuleiros compostos, que pertencem à classe dos padrões de corte ngrupos, apresentada por Gilmore e Gomory (1965). Os padrões tabuleiros compostos preservam
as facilidades de corte dos padrões tabuleiros, e apresentam baixos índices de sobra de matériaprima. Propomos uma heurística para a geração de um pool de padrões tabuleiros compostos,
usados para resolver o problema de corte de estoque na Indústria de Móveis. São apresentados
também resultados computacionais comparando os padrões tabuleiros compostos, com padrões
em 2-estágios de Gilmory e Gomory e padrões usados pela indústria.
.
PALAVRAS CHAVE. Padrões de Corte Bidimensionais, padrões n-grupos, Corte de estoque.
Área de classificação principal: Otimização Combinatória
ABSTRACT
In this work, we analyze the cutting patterns used by a furniture Industry, and determine some of
its basic characteristics. We defined a composed cutting pattern that belongs to the class of ngroup cutting patterns presented by Gilmore and Gomory (1965). The composed cutting patterns
preserve the easiness of the cutting process and have low index of waste. We propose a heuristic
for the generation of a pool of composed cutting patterns to solve the cutting stock problem in the
furniture Industry. We compare the heuristic solution with the solution given by the 2-stage
Gilmory-Gomory method and the industry practice.
KEYWORDS. Two-dimensional cutting patterns, n-group patterns, cutting stock problem
Main area: Combinatorial Optimization
XXXVIII SBPO
[ 1626 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
1 - Introdução
A indústria moveleira no Brasil, predominantemente composta por micro e pequenas
empresas, apresenta uma forte dispersão geográfica, porém está concentrada em pólos regionais
localizados basicamente nas regiões Sul e Sudeste do país (ABIMÓVEL, 2005). Dentre esses
pólos, destacamos o Pólo de Votuporanga, localizado no noroeste do estado de São Paulo, que é
hoje o maior do estado e um dos quatro mais importantes do país (Landi e Gusmão, 2005). Esse
pólo já foi considerado o segundo maior pólo moveleiro do Brasil (Suzigan, 2000), e apesar de
hoje representar apenas 3,7% do total de emprego da indústria, é altamente relevante do ponto de
vista do desenvolvimento local, e tem despertado interesse de diversos pesquisadores (e.g.:
Suzingan, 2000; Stipp, 2002; Silva, 2003). A maioria das empresas fabricantes de móveis do Pólo
de Votuporanga são de pequeno e médio porte caracterizadas por uma grande diversidade no grau
de organização das mesmas (Stipp, 2002).
O setor moveleiro, assim como demais setores da indústria, enfrenta hoje o desafio de
melhorar sua competitividade, para isto busca produzir mais, com melhor qualidade e menor
custo. Um dos fatores preponderantes para a redução do custo de produção é o melhor
aproveitamento da matéria prima. O estudo apresentado neste trabalho foi baseado em dados de
uma indústria de médio porte característica do Pólo de Votuporanga. Esta empresa concentra sua
produção em móveis de quarto (e.g. guarda roupas, cômodas), e utiliza como matéria prima
principal painéis retangulares de MDF em diversas espessuras. Para a produção de um móvel, os
painéis (objetos) são cortados em retângulos menores (itens) que após passarem por outras fases
do processo de produção, originam as peças que irão compor o produto final. Uma preocupação
importante para aumentar a eficiência da empresa é criar padrões para o corte dos objetos
(padrões de corte) que minimize a perda de matéria prima, sem criar um gargalo na linha de
produção. O bom aproveitamento dos objetos passa, necessariamente, pela elaboração de um
bom conjunto de padrões de corte.
Por limitações operacionais do equipamento de corte (seccionadora), um padrão de corte
é considerado viável se for guilhotinado. Um corte feito de uma extremidade a outra de um
retângulo, dividindo o objeto em retângulos menores é denominado corte guilhotinado ortogonal,
ou simplesmente corte guilhotinado (Arenales et al., 2004). Em entrevistas com o gerente de
produção da fábrica estudada foi possível perceber a preferência por padrões 2-estágios (cada vez
que a direção do corte muda, isto é o objeto recebe uma rotação de 90º, temos um estágio de
corte), sendo admissível uma fase a mais de ajuste, para aparo das sobras. É fácil perceber que a
cada rotação do objeto o tempo de produção é penalizado, o que justifica a preferência por
padrões 2-estágios. Dizemos que um padrão de corte é 2-estágios exato quando ao término do
segundo estágio todos os itens tiverem sido obtidos, se forem necessários cortes adicionais
dizemos que é um padrão de corte 2-estágios não-exato. A Figura 1 abaixo ilustra as etapas de
corte de um padrão de corte guilhotinado em 3-estágios.
Figura 1- Etapas do corte de um objeto de acordo com padrão de corte 3-estágios
1º Estágio
2º Estágio
3º Estágio
Dois outros aspectos importantes a serem considerados na elaboração de um bom padrão
de corte são: tempo necessário para o ajuste dos batentes de fixação do objeto na seccionadora e
capacidade de corte da seccionadora. Na empresa estudada, o ajuste dos batentes é manual, e o
tempo necessário de 50s a 2 min é considerado alto, quando comparado à velocidade de corte da
seccionadora que é de aproximadamente 14 m por minuto. Os corte efetuados no objeto no
primeiro estágio produzem faixas. A cada largura de faixa distinta é necessário um novo ajuste
XXXVIII SBPO
[ 1627 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
dos batentes para determinar a largura da faixa a ser cortada. Assim, é desejável usar padrões de
corte com poucas faixas de larguras diferentes. Na empresa estudada a seccionadora pode cortar
objetos com até 60 mm de espessura. Esta capacidade de corte permite, por exemplo, o corte de
quatro objetos de 15 mm ou 20 objetos de 3 mm. A empresa procura trabalhar com o menor
número possível de padrões de corte distintos para, com o agrupamento deles, reduzir o custo
com o consumo de energia e o tempo de operação da seccionadora. Isto é, a empresa tem também
interesse em reduzir o número de ciclos da serra (Yanasse et al. 1993). Maiores detalhes sobre o
processo de produção das empresas de móveis do Pólo de Votuporanga podem ser encontrados
em Silva(2003) e Figueiredo (2006).
Na próxima seção fazemos uma análise dos padrões de corte utilizados pela indústria e
propomos um algoritmo que sistematiza a construção desses padrões de corte. Na seção 3
apresentamos resultados obtidos comparando o algoritmo proposto com o método em 2-estágios
de Gilmory e Gomory contido no sistema CorteBi_r (Cavali e Rangel, 2004) e com dados
fornecidos pela indústria, na seção 4 apresentamos as considerações finais. Uma versão
preliminar deste trabalho esta descrita em Figueiredo e Rangel (2005).
2 - Padrões de Corte produtivos
O Problema de corte de estoque bidimensional (PCE) consiste em determinar como
cortar um conjunto de objetos de dimensões ( L,W ) para produzir um conjunto de m itens (de
dimensões (li , wi ) e demanda d i i = 1...m , respectivamente). Os objetos estão disponíveis em
estoque e os itens são partes que compõem o produto final, e.g. guarda-roupas, cômodas, criados.
A forma clássica de resolver o problema é supor que são conhecidos todos os padrões de corte
viáveis ( N ) e que existe um numero suficiente de objetos em estoque. A relaxação linear do
problema de otimização inteira associado é então resolvida pelo método de geração de colunas
(e.g. Morabito e Arenales, 2000; Cavali e Rangel, 2004). A diferença entre as diversas
abordagens está em como o problema de geração de colunas (CG):
CG : max π y : y ∈ {A1 ,..., AN }, ( A j , j = 1...N é um padrão de corte bidimensional)
{
}
associado é resolvido.
Neste trabalho, o problema CG é um problema de corte bidimensional onde apenas um
objeto, retangular, esta disponível (classificado como 2/B/O de acordo com a tipologia de
Dyckhoff, 1990). Na indústria de móveis, diferentes aspectos devem ser considerados na
definição de padrão de corte. Além do tipo de corte, guilhotinado em 2-estágios como visto na
seção 1, a indústria busca determinar um balanço entre padrões de corte com índices de perda alta
e baixo custo operacional, e padrões de corte que possuem um baixo índice de perda, mas com
um custo operacional alto. A indústria considera aceitável padrões com perda abaixo de 6% da
área do objeto. É interessante fazer uma distinção entre a perda e a sobra de material em um
padrão de corte. Em geral a perda é calculado pela fórmula:
P = L⋅ W −
∑ (a
n
i =1
i
⋅ l i ⋅ wi ) , ai é o número de itens do tipo i no padrão .
No entanto, neste cálculo estão incluídas perdas inerentes ao processo de corte propriamente dito,
chamada de desgaste da serra. Uma outra parte que compõe esta perda são as peças cortadas e
não demandadas, ou seja, retalhos quaisquer do objeto de dimensões não predefinidas,
denominada sobra de material. A perda devido ao desgaste da serra, em certos tipos de matéria
prima (painéis de madeira, por exemplo), é inevitável e precisa ser levada em conta quando
queremos avaliar o custo de produção. Porém, quando da avaliação da eficiência do padrão de
corte, esta perda pode gerar uma distorção, pois padrões compostos por muitos itens pequenos
irão sempre apresentar um alto percentual de perda devido ao desgaste da serra, sem que isso
implique que sejam perdulários. Se incluirmos na formula do cálculo da perda o desgaste devido
a espessura da serra (Morábito e Arenales, 2000), e refizermos os cálculos, o valor encontrado
representará, exatamente a perda por sobra de material (Ps):
Ps = (L + δ ) ⋅ (W + δ ) −
XXXVIII SBPO
∑ (a ⋅ (l
n
i =1
i
i
+ δ ) ⋅ (wi + δ ))
[ 1628 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
onde δ é o desgaste provocado pela serra. A perda relativa ao desgaste da serra ( Pd ) poderá ser
calculada pela diferença entre a perda total ( P ) e a perda por sobra de material:
Pd = P − Ps .
Na avaliação da eficiência de um conjunto de padrões de corte é necessário, ainda, levar em conta
os excessos na produção dos itens (produção de um número de itens maior que a demanda). Estes
excessos, em geral, acarretam um aumento do custo de estocagem.
Em Cavali e Rangel (2004) o sistema CorteBi (Perin e Rangel, 1989), que gera padrões
de corte em 2-estágios de acordo com o Método de Gilmory e Gomory (1965), foi revisado para
incorporar a rotação de itens e considerar a perda de material relativa à serra. O sistema revisado
(CorteBi_r) foi usado para resolver o problema de corte de estoque da industria estudada e se
mostrou útil como sistema de apoio a tomada de decisões devido ao tempo de resposta e
qualidade da solução. O sistema resolveu problemas com até 20 itens em menos que dois
segundos e gerou padrões de corte com índice de perda entre 3,07% e 5,27% considerando a
rotação dos itens. A Figura 2 a seguir mostra dois padrões de corte gerados pelo sistema
CorteBi_r. Os dois padrões de corte possuem perda abaixo do aceitável pela indústria (4,19% e
2,73% respectivamente), mas o padrão de corte 2a foi rejeitado pela indústria por causa da
dificuldade no processo de corte. O padrão de corte 2b (aceito pelo indústria) possui dois
conjuntos de faixas que podem ser cortadas simultaneamente no segundo estágio, caracterizando
um padrão 2-grupos.
Figura 2– Padrões de Corte gerados pelo sistema CorteBi_r
2a) Padrão Rejeitado (perda 4.19%)
2b) Padrão aceito (perda 2.73%)
Um padrão n-grupo, estudado por Gilmory e Gomory (1965) em aplicações na indústria
de vidro e metal, é um padrão de corte guilhotinados em 2-estágios no qual as faixas resultantes
do primeiro estágio são divididas em grupos de forma que cada grupo de faixas é cortado
simultaneamente no segundo estágio. Se o padrão contiver apenas um grupo de faixas temos um
padrão tabuleiro ou 1-grupo (Katsurayama e Yanasse , 2001). Uma característica destes padrões é
que todos os itens apresentam-se distribuídos em linhas e colunas, num formato que nos faz
lembrar um tabuleiro de xadrez ou dama (Figura 3). Os padrões tabuleiros necessitam de poucos
manuseios do objeto e portanto possuem um baixo custo operacional (Morabito e Arenales, 2000;
Katsurayama e Yanasse, 2001), e tal como os demais padrões 2-estágios, podem ser exatos e nãoexatos, conforme a necessidade ou não de ajuste.
Figura 3 – Processo de corte do padrão tabuleiro
1º estágio
XXXVIII SBPO
2º estágio
[ 1629 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Se tomarmos um padrão de corte usado na indústria (Figura 4) e o orientar, da esquerda
para a direita e de cima para baixo (Figura.4a), veremos no canto superior esquerdo um bloco
principal que compõe um padrão tabuleiro (Figura 4b).
Figura 4 – Padrão de Corte usado na indústria de Móveis
b) Subpadrão Tabuleiro
a) Padrão de corte
Neste caso dizemos que o padrão da indústria foi obtido a partir de um padrão tabuleiro.
As sobras do padrão tabuleiro foram reaproveitadas, sendo tratadas como novos objetos, e novos
padrões tabuleiro foram obtidos, mantendo o padrão final em 2-estágios. Isto é, o padrão da
indústria é um padrão em 2-estágios resultante da composição de padrões tabuleiros, ou seja, um
padrão tabuleiro composto. Esta idéia foi explorada em dois procedimentos heurísticos para gerar
padrões de corte similares aos usados pela indústria descritos a seguir.
Heurística 1 – Gera padrões 2-grupos
Etapa 1 – Construção de faixas
Passo 1 – Leia os dados referentes a dimensão do objeto e dos itens: ( L,W ) , ( (li , wi ) i = 1...m , se
desejado faça a rotação dos itens e ordene os p ≤ 2m itens de forma que wi ≤ wi +1 , i = 1... p .
Passo 2 - Use o item k (item pivô), k = 1... p , para criar até duas faixas de largura wk : uma
faixa homogênea (apenas um item de cada tipo) e se possível uma segunda faixa contendo
apenas itens j tais que w j = wk . Seja S o conjunto de itens incluídos na faixa.
Passo 3– Para cada uma das faixas criadas no passo 2, inclua, se possível, mais itens na faixa
(área B da Figura 5 a seguir). Isto é, inclua o item i se ( L − ∑ l j ) > li , ∀i : wi ≤ wk .
j∈S
Etapa 2 - Geração do pool de padrões 2-grupos
Passo 4 – Para cada faixa criada na Etapa 1, gere um padrão tabuleiro (no máximo dois padrões
para cada wk ) usando W  faixas.

wk 
Passo 5 – Para cada padrão tabuleiro criado no Passo 4 crie K padrões de corte derivados
removendo faixas do padrão. A área livre associada as faixas removidas será considerada um
novo objeto (área A na Figura 5 a seguir).
Figura 5: Padrão de corte derivado
Remoção de
Faixas
XXXVIII SBPO
[ 1630 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Passo 6 – A área livre (área A da Figura 5) em cada padrão de corte derivado obtido no Passo 5 é
considerada um novo objeto de dimensões L × W A . Um padrão tabuleiro exato é então gerado
para este objeto resolvendo o seguinte modelo de otimização inteira (Yanasse e Morabito, 2004).
Supondo:
; Q = W A
;
P = L
wmin 
 l min 

L j : é o comprimento da j - ésima faixa, j = 1..P ;
Wk : é a largura da k - ésima faixa, k = 1..Q;
xijk = 1 se o item i for alocado ao retângulo L j xWk ; 0 c.c.; e
M
é uma constante de valor alto (e.g. M ≥ max( L, W ) ).
max
∑∑∑ (l
temos:
n
P
Q
i
⋅ wi ⋅ xijk
)
(1)
i =1 j =1 k =1
P
s.t. :
∑
Q
∑W
L j ≤ L;
j =1
k
≤W A
( 2)
k =1
n
∑x
≤1 ,
ijk
∀ j, k
(3)
i =1

l i ⋅ xijk ≤ L j + M 1 −
i =1

n
∑
Lj ≤

l i ⋅ xijk + M 1 −
i =1

n
∑
n
∑w ⋅ x
i
ijk
i =1
Wk ≤

≤ Wk + M 1 −

n
i =1
L j ≥ L j +1
∑x

 , ∀ j, k


( 4a )
ijk

 , ∀ j, k


(4b)
i =1
n
∑x
i =1
n
∑x
i =1
ijk

 , ∀ j, k


n


+ M 1 −
xijk  , ∀ j , k
i =1


, ∀ j; Wk ≥ Wk +1 , ∀ k
∑w ⋅ x
i
ijk
n
ijk
∑
(5a )
(5b)
(6)
xijk ∈ {0,1}; L j , Wk ≥ 0 ; i = 1..m ; j = 1..P ; k = 1..Q (7)
onde:
(1)
(2)
função objetivo, maximizar a área ocupada do objeto (Lx WA);
o comprimento total (largura total) ocupado pelos itens não ultrapassa o comprimento,
L, (largura , WA) do objeto;
(3) permite a alocação de no máximo um item no retângulo LjxWk;
(4a e 4b) garantem que se houver um item i alocado no retângulo LjxWk então li = Lj ;
(5a e 5b) garantem que se houver um item i alocado no retângulo LjxWk então wi = Wk ;
(6) eliminação de simetrias.
Etapa 3 – Resolução do Problema do Corte de Estoque
Passo 7 – Resolva o problema do corte de estoque considerando o pool de padrões gerados nos
Passos 1 a 6 acima. O pool irá conter até 2 p ( K + 1) padrões de corte diferentes.
Note que a maior dificuldade da Heuristica 1 descrita acima está na solução do problema
de otimização inteira do Passo 6. O número de variáveis e restrições deste modelo depende das
relações entre a dimensão do objeto e dos itens ( P e Q ). Figueiredo (2006) apresenta um estudo
computacional do modelo (1)-(7) com dados da indústria de móveis. Os resultados apresentados
XXXVIII SBPO
[ 1631 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
mostram que para problemas com mais de 12 itens o tempo computacional para encontrar a
solução ótima do modelo é muito alto. Além disso, a eficiência do modelo varia de acordo o grau
de dispersão da largura e/ou comprimento dos itens. Conjuntos de dados com muito variação nas
dimensões dos itens provoca a geração de padrões homegênios ou próximos, aumentando assim o
índice de sobra no padrão. Itens com dimensões muito pequenas em relação à dimensão do objeto
também dificultam a resolução do modelo. Essas caracteristicas do modelo influenciaram muito o
desempenho da Heuristica 1 conforme será visto na Seção 3. Uma alternativa para o modelo (1)(7), baseada em Morabito e Arenales (2000), é usar o modelo (8)-(12), descrito a seguir, para
gerar um padrão tabuleiro no Passo 6, resultando num novo procedimento chamado de
Heuristica 2.
max ∑i =1 vi ⋅ xi
m
(8)
s.a : ∑i =1 wi ⋅ xi ≤ W A
m
xi ≤ My i ,
∑
m
i =1
∀i
yi ≤ 1
x i ∈ Z + , y i ∈ {0,1} ∀i
(9)
(10)
(11)
(12)
onde:
xi é o número de vezes que a faixa de largura wi gerada na Etapa 2 é usada para compor o
padrão de corte;
yi é igual a 1 se a faixa de largura wi é usada e 0 caso contrário;
vi é a área ocupada da faixa de largura wi .
(8) função objetivo, maximizar a área ocupada do objeto (Lx WA);
(9) largura total ocupada pelas faixas não ultrapassa a largura , WA, do objeto;
(10 e 11) Limitam o número de faixas que irão compor o padrão de corte.
3 - Estudo Computacional
Os móveis produzidos na indústria estudada são fabricados com itens de diferentes
espessuras (e.g. 3, 9, 15,18, 20, e 25mm). Assim, para obter todos os itens necessários para
compor um determinado móvel, é necessário resolver um problema de corte de estoque para cada
espessura de objeto. Todos os objetos tem dimensão (2750 x 1830), exceto o objeto de 15mm
cujas dimensões são (2750 x 1850). Nesta seção são apresentados resultados dos problemas de
corte de estoque necessários para a fabricação de dois produtos (P1 e P2). O produto P1 é
fabricado com itens de quatro espessuras diferentes (3, 9, 12, e 15 mm) e o produto P2 com itens
de seis espessuras diferentes (3, 9, 12, 15, 20, 25). As características principais dos conjuntos de
itens utilizados nos testes estão descritas na Tabela 1. Os conjuntos foram nomeados de acordo
com o produto e a espessura do objeto, assim P1-15 quer dizer conjunto de itens de 15 mm de
espessura necessários para a produção de P1, e P2-20 é o conjunto de itens de 20 mm de
espessura necessários para a produção de P2. Os demais conjuntos são nomeados de maneira
similar. Na Tabela 1 são fornecidos para cada conjunto de dados, o número de itens (n_item), as
dimensões e demanda de cada item (li × wi , d i ) , e o valor da demanda total (T_dem). Alguns
itens na tabela tem demanda nula ( d i = 0 ). Esses itens são facilmente aproveitados pela indústria
para a produção de um item chamado pinázio, e mesmo que não sejam necessários para a
confecção de um determinado produto, são incluídos no conjunto de itens para um melhor
aproveitamento do objeto. Assim, reproduzimos no estudo computacional uma prática adotada
pela indústria. Os dados usados neste estudo foram gentilmente cedidos pela Empresa Luapa
Móveis (http://www.luapa.com.br/).
XXXVIII SBPO
[ 1632 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
Nome n_item
P1-03
P1-09
3
3
P1-12
6
P1-15
7
P2-03
8
P2-09
P2-12
4
3
P2-15
9
P2-20
P2-25
9
3
12 a 15/09/06 Goiânia, GO
Tabela 1 – Características dos Conjuntos de itens
T_dem
(li xwi , d i )
1600
(710x535, 320),(1062x530,320) (647 x 453,960)
(630 x50,480), (433x 50,320), (295x 50,480)
1280
(440x65,320), (635x50,160), (454x180,960), (635x180,480),
2880
(454x135,640), (635x135,320)
(970x570,320), (700x75,160), ( 700x 212,480), (700x163,320),
1280
(600,400,0), (430x 60,0), (500x60,0)
(2500x565,240), (647x453,160), (710x454,80), (454x454,80),
1080
(1080x454,200), (530x454,200), (1050x500,40), (483x215,80)
(510x450,40), (630x50,0), (433x50,0), (295x50,0)
40
(454x180,320), (635x180,160), (454x135,0)
680
(1049x452,200), (499x452,200), (452x429,80), (1050x535,80),
680
(535x500,80), (535x430,80), (700x212,160), (430x60,0), (500x60,0)
(2500x60,480), (445x60,480), (445x40,1040), (490x60,40),
(500x60,120), (1050x60,200), (430x60,120), (440x60,160),
2720
(1060x60,80)
400
(430x60,80), (500x60,160), (1050x60,160)
Cada PCE foi resolvido usando três estratégias diferentes, as Heurísticas 1 e 2 (Heurística
1 e Heurística 2 respectivamente) apresentadas na Seção 2, e o sistema CorteBi_r (CorteBi_r). As
Heurísticas foram implementadas usando o sistema XPRESS-MP (Dash Optimization, 2004).
Todos os testes foram executados em microcomputador AMD-Athlon 2200 com 256 MB RAM.
Na Tabela 2 são apresentados os resultados referente a resolução do PCE pelas
Heurísticas 1 e 2. Os resultados para Heurística 2 estão em negrito. A Heurística 2 foi executada
sempre considerando a rotação dos itens, enquanto que nos problemas marcados com * a
Heurística 1 foi executada considerando a orientação fixa dos itens. Para cada conjunto e método
de resolução são apresentados o Tempo de CPU em segundos (Tempo Cpu), o Número de
Padrões (Nr. Pdr.), o número de objetos (Nr. Obj.) e a sobra de material, valor máximo (Max),
médio (Med) e mínimo (Min). Analisando a coluna Sobra é possível verificar que para a maioria
dos PCE os padrões gerados pelos dois procedimentos heurísticos possuem índices de perda
médio abaixo do tolerado pela indústria (6%). Observamos ainda que a Heurística 2 apresenta,
em geral, uma menor amplitude nos índices de sobra (colunas Max–Min), o que nos sugere a
geração de um conjunto de padrões de corte com um índice de perda mais uniforme. O número
de objetos e o número de padrões diferentes necessários para a produção dos itens obtidos pelos
dois procedimentos foi igual na maioria dos casos, sendo que para P1-12, P1-15 e P2-20 a
Heurística 2 obteve um número menor de objetos. Note na Tabela 1, que estes conjuntos são
compostos por muitos itens pequenos, críticos para a execução do modelo de otimização inteira
usado no Passo 6 da Heurística 1. Só foi viável, para estes casos, a execução da Heurística 1 com
orientação fixa dos itens, o que reduziu o espaço solução e não permitiu um melhor
aproveitamento do objeto. Um outro aspecto importante foi que o tempo consumido pela
Heurística 1 para resolver um PCE pode chegar a centenas de segundos. Enquanto o tempo
utilizado pela Heurística 2 é da ordem de dezenas de segundos. O tempo mais alto verificado
pela Heurística 2 foi de 94,4s (P2-20), contra mais de 10h para a Heurística 1(P2-03).
XXXVIII SBPO
[ 1633 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Tabela 2 – Aproveitamento da matéria prima - resultados Heurística 1 e Heurística 2
Tempo
Nr
Nr
Sobra (%)
Nome
CPU
Pdr.
Obj.
Max.
Med.
Min.
5,00
2,00
124
5,90
5,80
5,80
P1-03
4,00
2,00
124
5,90
5,80
5,80
292,00
3,00
7
10,50
4,40
3,30
*
P1-09
8,60
3,00
7
1,80
1,50
0,20
136,00
7,00
47
8,60
4,50
1,50
P1-12 *
36,20
8,00
45
1,70
0,70
0,20
64,00
5,00
83
27,90
12,50
9,70
P1-15*
19,00
3,00
64
5,00
4,30
3,70
16600,00
9,00
130
9,00
5,80
0,30
P2-03
33,40
9,00
133
9,00
6,00
0,30
27,00
1,00
2
2,00
2,00
2,00
P2-09
5,40
1,00
2
2,00
2,00
2,00
1920,00
2,00
10
4,70
4,40
1,50
P2-12
7,70
2,00
10
2,20
2,10
1,50
46,00
10,00
57
6,00
4,10
1,60
P2-15
66,20
9,00
57
5,40
4,00
1,50
3070,00
10,00
33
15,10
8,50
2,30
P2-20*
94,40
10,00
30
6,60
3,10
0,50
69,00
3,00
5
10,60
7,00
2,60
P2-25*
9,20
2,00
4
2,30
2,00
1,00
*
Execução da Heurística 1 considerando a orientação fixa dos itens
Na Tabela 3 a seguir são apresentados os dados relativos à resolução dos PCE pela
Heuristica 2, pelo sistema CorteBi_r e pela Indústria (Indústria). Para facilitar a análise,
repetimos os dados relativos apenas à Heurística 2 considerando que o desempenho apresentado
tanto em termos de qualidade da solução (índice de sobra e número de objetos e padrões) quanto
em tempo computacional foi melhor que o desempenho da Heurística 1. Podemos observar que a
Heurística 2 mantém a qualidade da solução quando comparada também à solução do CorteBi_r e
da Indústria. Na maioria dos casos o número de objetos e o índice de perda média apresentado
pela Heurística 2 é menor que os valores obtidos pelos outros dois métodos de solução. É
importante lembrar que o sistema CorteBi_r e os padrões de corte da indústria não são
necessariamente padrões tabuleiros compostos. O CorteBi_r gera padrões de corte em 2-estágios
gerais e alguns padrões de corte da indústria são padrões em 3-estágios. Além disso, a indústria
às vezes considera a utilização de apenas meio objeto (e.g. 63,5 objetos cortados para o obter os
itens do conjunto P1-15), o que não é possível ocorrer nas soluções obtidas com o CorteBi_r ou
com a Heurística 2. No entanto, o número de padrões de corte gerados pela Heurística 2 é
ligeiramente maior. Um número maior de padrões de corte implica em um número maior de
ajustes na seccionadora e pode reduzir o número de objetos cortados simultaneamente de acordo
com um determinado padrão (aumenta o número de ciclos da serra). Um aspecto importante para
aumentar a produtividade do processo de corte é minimizar o número de ciclos da serra e deverá
ser considerado em trabalhos futuros.
XXXVIII SBPO
[ 1634 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Tabela 3 - Aproveitamento da matéria prima: resultados Heurística 2, Cortebi_r e Indústria
Heurística 2
CorteBi_r
Sobra(%)
Sobra(%)
Nr Nr
Nr Nr
Nome
Pdr. Obj. Max. Med. Min. Pdr. Obj. Max. Med. Min.
Indústria
Sobra(%)
Nr Nr
Pdr. Obj. Max. Med. Min.
P1-03
2 124 5,9
5,8
5,8
2
124
5,9
5,8
5,8
2
124
5,9
5,8
5,8
P1-09
3
7
1,8
1,5
0,2
3
7
2,8
1,5
0,2
1
6,5
3,3
3,3
0,2
P1-12
8
45
1,7
0,7
0,2
6
48
2,6
0,6
0,2
6
46
2,8
1,4
0,2
P1-15
3
64
5,0
4,3
3,7
4
63
5,8
4,8
4,4
3
63,5
4,9
4,4
4,4
P2-03
9 133 9,0
6,0
0,3
7
135
9,0
6,2
0,3
7
134
9,0
6,6
0,3
P2-09
1
2
2,0
2,0
2,0
1
2
1,7
1,7
1,7
1
2
1,8
1,8
1,8
P2-12
2
10
2,2
2,1
1,5
2
11
4,7
4,6
4,0
2
10,5
4,5
3,3
2,3
P2-15
9
57
5,4
4,0
1,5
7
60
8,4
5,4
3,6
6
57
4,3
2,6
2,3
P2-20 10 30
6,6
3,1
0,5
9
31
2,6
1,9
0,1
8
32
6,5
2,7
1,5
P2-25
2,3
2,0
1,0
3
5
2,8
2,5
2,3
3
4,5
3,3
3,2
3,2
2
4
4 - Considerações Finais
O entendimento do processo de corte da matéria prima e a análise dos padrões de corte
adotados pela Indústria de móveis nos permitiram identificar um tipo especial de padrão de corte
que nomeamos de padrão tabuleiro composto. Os padrões tabuleiros compostos, que pertencem à
classe dos padrões n-grupos, exibem as facilidades de corte dos padrões tabuleiros, porém com
um melhor aproveitamento do objeto. A geração de padrões tabuleiros compostos pela
Heurística 1 esbarrou na sensibilidade da mesma à quantidade de itens distintos considerados e ao
processamento de itens com dimensões pequenas. Com a Heurística 2 contornamos estes
problemas, obtendo resultados que, de uma forma geral, se mostraram melhores que os praticados
pela Indústria estudada. Contudo, dois aspectos merecem maior atenção: o primeiro é a
quantidade de padrões distintos usados no processo de corte, o que pode provocar a subutilização
da seccionadora em algumas operações de corte. Se a diversidade de padrões utilizados no
processo de corte é reduzida, a quantidade de vezes que os padrões escolhidos serão usados pode
aumentar, o que irá favorecer a taxa de utilização da seccionadora. Minimizar o número de ciclos
da serra é um aspecto importante para aumentar a produtividade do processo de corte que deverá
ser considerado em trabalhos futuros. Um outro aspecto importante é o fato da Heurística 2
trabalhar com um Pool de padrões tabuleiros compostos com várias dezenas de padrões, sendo
que a solução ótima utiliza poucos padrões. Apesar da Heurística 2 apresentar tempos
plenamente aceitáveis pela Indústria, essa questão indica um esforço computacional
desnecessário. A Heurística 2 pode ser facilmente incorporada no sistema CorteBi_r para gerar
colunas necessárias a cada iteração do método simplex.
AGRADECIMENTOS
Os autores agradecem ao CNPq pelo apoio recebido, e as sugestões dos revisores AD-HOC.
Referências Bibliograficas
Abimóvel, Panorama do Setor Moveleiro no Brasil, ABIMÓVEL-Associação Brasileira das
Indústria do Mobiliário, V1.3, August, 2005.
Arenales, M. N.; Morabito, R.; Yanasse, H. H. Problemas de Corte e Empacotamento. In:
Simpósio Brasileiro De Pesquisa Operacional, 36., 2004, São João Del Rei. Mini curso...,
São João Del Rei: SOBRAPO, 2004. p. 2690 - 2769. CD-ROM
XXXVIII SBPO
[ 1635 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Cavali, R. e Rangel, S., Production Planning: A Cutting Stock Problem In The Furniture Industry.
In: Anais do XII CLAIO,. Havana, 2004. v. único. p. T137
Dash Optimization, Modeling with Xpress-MP, Blisworth: Dash Associates, 2004.
Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational
Research, 1990, 44, 145-160.
Gilmore, P.C. and Gomory, R. E., Multistage cutting stock problems of two and more
dimensions, Operations Research, 1965, 13, 94-120.
Figueiredo, A., Análise de produtividade dos padrões de corte na indústria de móveis,
Dissertação, Pós-Graduação em Matemática Aplicada, UNESP, São José do Rio Preto,
Brasil, 2006..
Figueiredo, A. e Rangel, S., Aplicação de modelos 2-estágios e 1-grupo na geração de padrões de
corte na indústria moveleira. In: Anais do XXVIII CNMAC. São Carlos - SP : SBMAC,
2005. v. único.
Katsurayama, D. M. e Yanasse, H. H. Uma análise de produtividade do equipamento de cortes
utilizando-se padrões tabuleiro. In: XXI ENEGEP/ VII International Conference on Industrial
Engineering and Operations Management, 2001, Salvador. CDROM ENEGEP. Porto Alegre
: ABEPRO, 2001. v. 1.
Landi, F.R. e Gusmão, R., Indicadores de ciência, tecnologia e inovação em São Paulo 2004,
FAPESP, São Paulo, V 1, 2005..(disponível em: www.fapesp.br/indicadores - última visita
03/2006)
Morabito, R. and Arenales, M., Optimizing the cutting of stock plates in a furniture company,
Int. J. Prod Res, 2000, vol.38, no. 12, 2725-2742.
Perin, C. and Rangel, S., O Problema do Corte Bidimensional, Anais do XII Congresso Nacional
de Matemática Aplicada e Computacional, São Carlos - SP : SBMAC, 1989.
Silva, E. M., Alinhamento das Estratégias competitivas coma as estratégias de produção: Estudo
de casos no Pólo Moveleiro de Votuporanga/SP, Dissertação, Pós-Graduação em Engenharia
de Produção, USP, São Carlos, Brasil, 2003.
Stipp, M.S., Cluster Industrial: O Pólo moveleiro de Votuporanga-SP (1962-2001), Dissertação
de Mestrado, FCL - UNESP, Campus de Araraquara, SP, Brasil, 2002.
Suzigan, W., Industrial Clustering in the state of Sao Paulo, working paper CBS-13-00(E),
University of Oxford Centre for Brazilian Studies, Oxford, U.K., 2000.
Yanasse, H.H.; Harris, R.G.; Zinober, A.S.I. Uma heurística para redução do
número de ciclos da serra no corte de chapas. XIII ENEGEP - Encontro Nacional
de Engenharia de Produção/ I Congresso Latino Americano de Engenharia
Industrial, Florianópolis, SC, 05 a 08 de outubro de 1993. Publicado nos Anais
do XIII ENEGEP, Florianópolis, Universidade Federal de Santa Catarina, 1993.
Vol.II, p.879-885.
Yanasse, H. e Morabito, R., A note on linear models for one-group two-dimensional guillotine
cutting problems, Relatório Técnico, UFSCAR, 2004.
XXXVIII SBPO
[ 1636 ]