A pesquisa Operacional e os Recursos Renováveis
4 a 7 de novembro de 2003, Natal-RN
O PROBLEMA DE CORTE DE ESTOQUE UNIDIMENSIONAL INTEIRO
COM RESTRIÇÕES DE ESTOQUE
Kelly Cristina Poldi
Marcos Nereu Arenales
{[email protected], [email protected]}
Instituto de Ciências Matemáticas e de Computação – ICMC
Universidade de São Paulo – USP
Av. Trabalhador São-carlense, 400 - Caixa Postal 668
13560-970 – São Carlos – SP
RESUMO
Neste trabalho estudamos o problema de corte de estoque inteiro unidimensional, o qual consiste em
cortar um conjunto de barras disponíveis em estoque para a produção de itens menores tal que a
demanda seja atendida e um objetivo seja otimizado, neste caso, minimizar a perda. Estudamos o caso
no qual há diversos tipos de barras em estoque disponíveis em quantidades limitadas (focamos o
estudo em problemas com demanda baixa). Apresentamos alguns métodos heurísticos para obtenção
da solução inteira, que podem ser classificados como construtivos ou residuais. Estas heurísticas são
analisadas empiricamente, isto é, por meio dos experimentos computacionais realizados para 360
problemas gerados aleatoriamente. Ao compararmos as abordagens residuais com as abordagens
puramente construtivas, pudemos claramente concluir que as heurísticas residuais apresentaram
resultados muito melhores que as abordagens puramente construtivas. Em particular, uma nova
heurística apresentou os melhores resultados. Um subproduto importante desta análise contraria o
folclore na área de corte e empacotamento de que heurísticas construtivas são as mais adequadas para
a solução do problema de corte de estoque quando há baixa demanda. As heurísticas residuais,
baseadas na geração de colunas, são muito superiores.
Palavras-chave: problema de corte de estoque, otimização inteira, geração de colunas.
ABSTRACT
In this paper we have studied the one-dimensional integer cutting stock problem, which consists of
cutting a set of available bars in stock in order to produce ordered smaller items in such a way as to
optimize a given objective function, in this case, minimizing waste. We have studied the case in which
there are several types of bars in stock available in limited quantities. And, we have focused our study
on problems with low requirements. Some heuristic methods are given in order to obtain an integer
solution, which can be classified as constructive or residual. These heuristics are empirically analyzed,
i.e., by solving a set of 360 randomly generated instances. The analysis showed that residual heuristics
are much more superior than constructive ones. In particular, a new proposed residual heuristic
obtained better results than the others. An important by-product from the empirical analysis
contradicts the idea that specialists believe in terms of cutting and packing, for which the constructive
heuristics should be used if one is faced with low demand problems. The residual heuristics, based on
a linear optimization approach, are clearly superior.
Key-words: cutting stock problem, integer optimization, column generation.
1. Introdução
Um problema de corte, genericamente, consiste em cortar unidades maiores (objetos) em
unidades menores (itens), otimizando uma certa função, por exemplo, minimização da perda. Estes
problemas são essenciais no planejamento da produção em vários tipos de indústrias, tais como
indústrias de papel, vidro, móveis, plástico, chapas de madeira, aço, têxtil etc. A importância
econômica das aplicações, aliada à complexidade de resolução, tem motivado muitas pesquisas na
área, aumentando com isto o número de publicações na área.
Em geral, estes problemas são formulados como problemas de otimização linear inteira. Um
problema de otimização linear inteira é muito difícil de ser resolvido computacionalmente e um
segundo complicante é a explosão combinatória dos vários tipos de itens, o que inviabiliza a resolução
direta do problema. Para contornar estas dificuldades, em 1961, Gilmore e Gomory relaxaram a
condição de integralidade e propuseram um método eficiente de geração de colunas para a resolução
do problema linear relaxado. Desta maneira, uma solução ótima fracionária para o problema de corte
de estoque é determinada, restando a tarefa de determinar uma solução inteira para o problema. Este
artigo descreve métodos heurísticos para obtenção da solução inteira, compara a qualidade destas
soluções bem como o esforço computacional. Alguns poucos trabalhos sobre este assunto são
encontrados na literatura e destacamos: Stadtler (1990), Wäscher e Gau (1996), Pinto (1999),
Hinxman (1980). Wäscher e Gau (1996) fazem uma revisão dos vários métodos para determinar a
solução inteira do problema de corte e propõem novos. Os métodos apresentados nesse artigo
(classificados como básicos, residuais e compostos) aceitam como factíveis soluções com itens
produzidos em excesso, o que difere do presente estudo, no qual demanda não pode ser excedida.
Observamos também que o artigo de Wäscher e Gau (1996) trata o problema de corte de estoque com
demanda “média” (conforme seu gerador de problemas aleatórios) e, no presente artigo, enfocamos
problemas com demanda pequena (menos de dez unidades). Poucos artigos na literatura tratam o
problema da baixa demanda, em um deles: Riehme et al.(1996) encontramos a afirmação de que para
problemas com demanda grande a abordagem residual é apropriada, mas para problemas com
demanda pequena, esta abordagem não é apropriada (embora esta afirmação seja bem difundida e
aceita entre os pesquisadores em problemas de corte, raramente é escrita. A esta crença chamamos de
folclore na área dos problemas de corte). Os testes computacionais aqui realizados estão focados em
problemas de corte de estoque com demanda baixa e limitação no número de objetos disponíveis em
estoque. Os artigos poucos artigo da literatura tratam o problema com apenas um tipo de barra
disponível em estoque, mas a extensão das heurísticas para vários tipos de barras é uma tarefa simples.
Pudemos concluir em nossa análise que a abordagem residual é a melhor maneira de se resolver o
problema de corte de estoque inteiro, tal como Wäscher e Gau (1996) já haviam concluído, mas com
os resultados aqui apresentados pudemos perceber que isso também é válido para problemas com
baixa demanda, contrariando o folclore da área.
A organização deste texto é a seguinte: na seção 2 apresentamos o problema de corte de
estoque a ser resolvido e sua modelagem matemática. Na seção 3 estão descritos dois métodos
heurísticos construtivos utilizados na solução do problema. Uma outra abordagem utilizada é baseada
em heurísticas residuais; estas heurísticas estão descritas na seção 4. A seção 5 contém breves
comentários sobre as implementações que foram realizadas. Na Seção 6 descrevemos os testes
computacionais realizados e fazemos uma análise de seus resultados. Na seção 7 apresentamos
algumas conclusões e propostas futuras.
2. Definição e Modelagem do Problema
O problema de corte de estoque unidimensional inteiro pode ser definido como:
Considere que temos disponível em estoque K tipos de objetos (barras, bobinas, etc.) de
comprimento Lk, k = 1, ..., K, cada um disponível na quantidade ek, k = 1, ..., K e um conjunto de
pedidos, com demanda conhecida di, i = 1,...,m, de itens de comprimentos li, i = 1, ..., m (os
comprimentos dos itens são tais que: li ≤ L). O problema consiste em produzir os itens demandados a
1499
partir do corte dos objetos em estoque, atendendo a demanda e de modo a minimizar a perda de
material.
Não é permitido excesso de produção, ou seja, o número total de itens cortados deve ser
exatamente igual à demanda original. Pedaços do corte que não sejam os itens demandados são
considerados perda.
Definição: Chamamos de padrão de corte a maneira como um objeto em estoque é cortado para a
produção dos itens demandados.
A um padrão de corte associamos um vetor m-dimensional que contabiliza os itens
produzidos:
a = (α1, α2, ... , αm)T
onde αι é a quantidade de itens do tipo i no padrão de corte a.
Definição: Um padrão de corte que produza apenas um tipo de item é chamado padrão de corte
homogêneo.
Em outras palavras, um padrão de corte é homogêneo se o vetor associado tem apenas uma
coordenada não-nula: (0, ... , αi, ... , 0)T , αi ≠ 0. Note que sempre teremos m padrões homogêneos,
cujos vetores associados definem uma matriz diagonal. Observe que um vetor a = (α1, α2, ... , αm)T
corresponde a um padrão de corte se e somente se satisfizer as restrições do problema da mochila,
considerando apenas as restrições físicas (1.2)-(1.3):
maximizar g(α) = v1 α1 + v2 α2 + . . . + vm αm
sujeito a: l1 α1 + l2 α2 + . . . + lm αm ≤ L
0 ≤ αi ≤ di, i = 1, ... , m e inteiro
(1.1)
(1.2)
(1.3)
supondo que o comprimento do objeto seja L. Note que, a geração dos padrões de corte deve ser
restrita (veja (1.3)), para que não ocorra excesso da demanda. (Arenales e Morabito (1997)).
Entretanto, os padrões de corte devem ser definidos para cada tipo de barra disponível em
estoque, isto é, devem satisfazer:
l1 α1k + l2 α2k + . . . + lm αmk ≤ Lk
(2.1)
0 ≤ αik ≤ di, i = 1, ... , m e inteiro, k = 1,...,K.
(2.2)
Assim, após gerar os padrões para cada uma das barras disponíveis em estoque, escolhemos
aquele que apresentar a menor perda.
Após definirmos os padrões de corte, o próximo passo será determinar o número de vezes que
cada padrão será utilizado para resolver o problema, ou seja, a modelagem matemática de um
problema de corte de estoque é feita em duas etapas:
1. Definir todos os possíveis padrões de corte (supondo Nk o número total de padrões obtidos para o
objeto em estoque k, k = 1, ..., K);
2. Definir quantas vezes cada padrão de corte será utilizado (freqüência) para atender a demanda, que
deverá ser um número inteiro e não-negativo.
Sejam
a 1k
 α11k 
 α12 k 




 α 21k 
 α22 k 
=
, a 2k = 
,
M 
M 








 α m 1k 
 αm 2 k 
. . . , aN k
k
 α1 N k k 


 α2 N k k 
, k = 1, ...,K.
=
M 


 α mN k 
k 

onde αijk é o número de itens do tipo i no padrão de corte j para o objeto em estoque k, i = 1, ..., m, j =
1, ..., Nk, k = 1, ..., K, (ajk é o vetor correspondente ao j-ésimo padrão de corte sobre o objeto k).
1500
Consideramos um dado adicional para descrição do modelo matemático: cjk que é o custo do
m
objeto k, segundo o padrão de corte j, j = 1, ..., Nk, k = 1, ..., K. Neste caso, cjk = Lk − ∑ li α ijk é a
i =1
perda no padrão de corte j do objeto k .
Dados da demanda:
•
m : número de tipos de itens;
•
li : comprimento do item i, i = 1, ..., m;
•
di : demanda do item tipo i, i = 1, ..., m.
Dados de estoque:
•
K : número de tipos de objetos em estoque;
•
Lk : comprimento do objeto k, k = 1, ..., K.
•
ek : disponibilidade em estoque do objeto k, k = 1, ..., K.
Variáveis de decisão (freqüência):
•
xjk : número de vezes que o objeto do tipo k é cortado usando o padrão j, j = 1, ...,Nk, k = 1, ..., K.
O problema pode então ser formulado por:
N1
N2
NK
j =1
j =1
j =1
minimizar
f(x11,x21,…) = ∑ cj1 xj1 + ∑ cj2 xj2 + … + ∑ cjKxjK
sujeito a:
∑
N1
j =1
N1
∑
N2
NK
j =1
j =1
aj1 xj1 + ∑ aj2 xj2 + … + ∑ ajK xjK
=d
xj1
≤
e1
≤
e2
(3.1)
(3.2)
j =1
N2
∑
xj2
(3.3)
j =1
O
M
NK
∑ xjK
j =1
xjk ≥ 0, e inteiro j=1,…,Nk, k=1,...,K.
≤
eK
(3.4)
A função objetivo (3.1) minimiza a perda total. A restrição (3.2) garante que a quantidade total
de itens produzidos seja exatamente igual à demanda. As outras restrições (3.3) garantem que a
quantidade de cada barra disponível em estoque não seja violada. E a última restrição (3.4) garante que
a repetição de cada padrão de corte j seja um número inteiro não-negativo.
Observamos que as colunas da matriz de restrições são os vetores associados aos padrões de
corte para cada objeto, agora complementado com K componentes com 1 na posição (m+k) e 0 nas
demais, onde k é a barra para a qual está definido este padrão de corte. Assim, uma coluna j do modelo
(3) pode ser escrita como:
(α
1 jk
K α mjk
0 K 1 K 0 )T
(4)
1501
A condição de integralidade sobre as variáveis xjk torna o problema (3) difícil, senão
impossível de ser resolvido computacionalmente para problemas de dimensões moderadas. Em
problemas práticos, m (que é a quantidade de tipos de itens) é da ordem de dezenas, enquanto que o
número de possíveis padrões de corte diferentes (que é o número de colunas) pode ser da ordem de
centenas de milhares, o que inviabiliza a resolução direta do problema.
Uma abordagem prática para resolver o problema (3) consiste em relaxar a condição de
integralidade e resolver o problema relaxado (problema de otimização linear) pelo Método Simplex
utilizando um processo de Geração de Colunas, proposto por Gilmore e Gomory (1961), de modo que
não é preciso gerar todas as colunas antecipadamente. De início, são colocadas as variáveis de folga
nas restrições (3.3), é realizada a fase 1 do método simplex com uma matriz básica (m+K x m+K) e,
em alguns casos, é preciso resolver um problema artificial. A cada iteração simplex, um dos padrões
básicos é substituído por um padrão de corte que melhora a solução básica atual. Tal padrão (coluna) é
determinado pela solução de um problema da mochila, dado por (1). A solução ótima obtida para o
problema (3) relaxado é, em geral, fracionária. Então, heurísticas têm sido desenvolvidas para
determinar o melhor arredondamento da solução.
3. Heurísticas Construtivas
Apresentamos duas heurísticas clássicas, bem conhecidas na literatura: Stadtler (1990),
Wäscher e Gau (1996), Pinto (1999), que são as heurísticas FFD (First-Fit-Decreasing) e Gulosa.
Estas heurísticas, que Hinxman (1980) classificou como heurísticas de repetição exaustiva, têm a
seguinte estrutura geral:
Enquanto houver demanda faça:
1. Construa um bom padrão de corte;
2. Use o padrão do passo 1 tanto quanto for possível, sem gerar excessos de itens cortados;
3. Atualize a demanda e o estoque.
3.1. Heurística FFD
A heurística construtiva FFD consiste, de forma geral, em colocar o item maior num padrão
de corte tantas vezes quanto for possível, ou seja, até que não haja mais espaço para colocar este item
ou, até que sua demanda já tenha sido atendida completamente (os itens maiores são alocados em
primeiro lugar pois são os mais difíceis de serem combinados). Quando não for mais possível colocar
o item maior, passar para o segundo maior item, e assim por diante. Quando o último item (menor
comprimento) for examinado, um padrão de corte foi construído. Este padrão é usado tantas vezes
quanto possível.
A aplicação da heurística FFD para o problema de corte com restrições de estoque (3) consiste
em, a cada iteração, gerar um padrão, seguindo o algoritmo acima, para cada tipo de barra disponível
em estoque. Como o objetivo é minimizar a perda, escolhemos, dentre os padrões gerados, aquele que
apresentar a menor perda. Atualizamos o estoque e a demanda e repetimos o procedimento, até que
toda a demanda seja completada.
3.2. Heurística Gulosa
A heurística construtiva Gulosa consiste em resolver um problema da mochila (1) com uma
função objetivo apropriada, por exemplo, o valor de utilidade vi de cada item na mochila como sendo
o próprio comprimento do item: li, de modo que a perda no padrão é minimizada. Observe que a
heurística FFD é um procedimento heurístico para resolver este problema da mochila.
maximizar G(a) = l1 α1 + l2 α2 + . . . + lm αm
(5.1)
sujeito a: l1 α1 + l2 α2 + . . . + lm αm ≤ L
(5.2)
1502
0 ≤ αi ≤ di, i = 1, ... , m e inteiro.
(5.3)
Então, a heurística gulosa consiste em, a cada iteração, resolver o problema (5) (que gera um
padrão de corte a) para cada uma das barras disponíveis em estoque. Como o objetivo é minimizar a
perda, escolhemos, dentre os padrões gerados, aquele que apresentar a menor perda. Atualizamos o
estoque e a demanda e repetimos o procedimento, até que toda a demanda seja completada. Ao final,
teremos uma solução inteira para o problema de corte com restrições de estoque.
4. Heurísticas Residuais
Os procedimentos que serão apresentados aqui geram uma solução inteira para o problema de
corte de estoque unidimensional inteiro a partir da solução ótima do problema (3) relaxado. Supomos
que pelo menos uma componente da solução ótima seja não-inteira, pois, caso contrário, o problema
de corte de estoque unidimensional inteiro já estaria resolvido.
4.1. Problema Residual
Seja y* uma solução inteira aproximada para o problema (3) tal que: Ay*≤ d.
Uma técnica simples de se obter uma solução inteira aproximada consiste em resolver o
problema (3) com a condição de integralidade relaxada, obtendo-se x*. Todos os componentes do
    
vetor solução são arredondados para o número inteiro abaixo, obtendo-se: y* = ( x*1 , x*2 ,L , x*n ) .
Veremos adiante outras técnicas para se obter uma solução inteira aproximada.
Definimos agora a demanda residual por: r = d - Ay* e resolvemos o problema (3) novamente
– chamado agora de problema residual – substituindo a demanda d pela demanda residual r.
Uma nova solução (possivelmente fracionária) é obtida e um arredondamento para o inteiro
inferior é novamente feito, gerando nova demanda residual.
Repete-se o processo, até que o arredondamento gere um vetor y* nulo (freqüências nulas).
Se ainda restarem itens com demandas não atendidas, então teremos um último problema
residual que pode ser resolvido por alguma das heurísticas FFD e Gulosa que foram descritas na seção
3.
4.2. Heurística Residual FFD
A heurística residual FFD consiste em obter o problema residual conforme a técnica simples
dada na seção 4.1. Ao final, quando a freqüência é nula, aplica-se a heurística FFD (seção 3.1.).
4.3. Heurística Residual Gulosa
Mesmo procedimento que a heurística residual FFD, porém, ao final, é aplicada a heurística
Gulosa (seção 3.2.).
4.4. Heurística Residual ‘Nova’
Esta heurística se diferencia das duas heurísticas residuais descritas anteriormente na forma de
se obter uma solução inteira aproximada. Com a técnica simples descrita na seção 4.1, todas as
freqüências são arredondadas para o número inteiro abaixo e, agora tentamos arredondar para o inteiro
acima, observando componente por componente do vetor x*, porém sem exceder a demanda. Deve-se
observar que a heurística de Stadtler (1990) também procede de maneira similar, mas admite excessos,
arredondando para o inteiro superior sempre a componente de x* de maior freqüência.
A cada iteração heurística nova resolve-se um problema de corte de estoque relaxado e
ordena-se o vetor solução de forma decrescente, isto é, dá-se prioridade aos padrões que são mais
utilizados.
1503
Para cada posição deste vetor, nesta ordem, arredonda-se a freqüência para o número inteiro
acima do fracionário obtido e testa-se a factibilidade desta solução (no sentido de que excessos de
itens não foram gerados).
Caso não seja factível (isto é, houve excesso de itens), a freqüência é reduzida de uma unidade
até que excessos sejam eliminados.
Quando o último padrão de corte gerado for examinado, atualiza-se a demanda e o estoque
(problema residual).
O problema residual é resolvido e o procedimento de arredondamento (para o inteiro superior
ou inteiro inferior como descrito acima) é repetido até que a toda a demanda seja satisfeita.
Deve-se observar que a geração de colunas neste procedimento deve ser restrita, pois cada
padrão de corte gerado pode ser utilizado pelo menos uma vez.
4.5. Heurística Residual ‘Nova’- versão 2
Esta heurística difere da versão original (seção 4.4.) apenas onde é feita a ordenação dos
padrões de corte. Aqui, um outro critério é utilizado. Ordenamos o vetor solução em ordem nãocrescente de perda no padrão. Caso haja empate, o critério de desempate é o mesmo da versão original,
colocamos primeiro o padrão com maior freqüência xjk.
5. Desenvolvimento Computacional das Técnicas Utilizadas
As implementações foram realizadas em Delphi 5. Foi implementado o método simplex com
geração de colunas proposto por Gilmore e Gomory (1961). O problema da mochila fornece, a cada
iteração do método simplex, uma coluna para entrar na base. O método utilizado para resolução do
problema da mochila foi o método da Enumeração Implícita, proposto por Gilmore e Gomory (1963).
Este método é implementado utilizando uma busca em profundidade primeiro e consiste em enumerar
implicitamente todas as soluções do problema da mochila (mais detalhes em Marques (2000)).
Ressaltamos que o procedimento da enumeração implícita foi modificado para a resolução do
problema da mochila restrito, isto é, onde a demanda é levada em conta e não pode ser excedida. Os
padrões iniciais, para obtenção de uma base para o método simplex, foram gerados para a maior das
barras disponíveis em estoque. São padrões homogêneos que não excedem a demanda, pois, como
lidamos com demanda baixa, pode facilmente ocorrer de um padrão homogêneo já exceder a demanda
de algum item e isso não pode ocorrer para o funcionamento da heurística. Em seguida, foram
implementados todos os procedimentos heurísticos descritos nas seções 3 e 4.
6. Testes Computacionais
Realizamos alguns testes computacionais para comparar os resultados obtidos pelas quatro
heurísticas residuais e também as heurísticas puramente construtivas. Para isto, geramos,
aleatoriamente, 18 classes com 20 exemplos em cada classe, totalizando 360 exemplos. As
implementações foram desenvolvidas em Delphi 5 e todos os testes foram realizados em um
computador Pentium III (866MHz) com 256 MB de memória RAM. A seguir, mostramos em detalhes
os critérios usados para gerar os dados e os resultados obtidos.
6.1. O Gerador Aleatório
Definimos um gerador aleatório de exemplos para testar e comparar os métodos
implementados. Gau e Wäscher (1995) descreveram uma forma de construir geradores de problemasteste para o problema de corte de estoque unidimensional. Estes autores consideraram apenas um tipo
de barra disponível em estoque; consideramos, neste trabalho, vários tipos de barras em estoque e em
quantidade limitadas, ou seja, mais dados devem ser gerados. Assim, o gerador descrito por Gau e
Wäscher (1995) serviu apenas como base para o gerador aqui apresentado:
•
Número de barras em estoque: K = 3, 5 e 7.
1504
•
Comprimento das barras em estoque: Os valores de Lk, k = 1,...,K foram gerados aleatoriamente
no intervalo [10,100].
•
Estoque disponível: os valores de ek , k = 1,K , K foram gerados aleatoriamente no intervalo [1,
100(m/2)].
•
Número de tipos de itens: Foram utilizados diferentes valores de m = 5, 10, 20, e 40.
•
Comprimento dos itens: Os comprimentos dos itens li foram gerados aleatoriamente nos intervalos
[v1L, v2L], L é a média entre os valores Lk, k = 1,...,K, e v1 e v2 definem o menor e o maior valor,
respectivamente, de li , i = 1,K , m . Utilizou-se: v1 = 0,01 e v2 = 0,2 e 0,8. Combinado estes
valores, gerou-se classes com problemas com itens pequenos (P) (v2 = 0,2) e itens médios (M) (v2
= 0,8).
•
Demanda: d i , i = 1,K , m no intervalo [1, 10].
Foram criadas 18 classes de problemas combinando K, m e li e gerados 20 exemplos para cada classe.
6.2. Resultados
A Tabela 1 mostra as 18 classes de problemas com a perda total (média) ocorrida em cada
classe, que é o objetivo a ser minimizado. A Tabela 2 mostra o número médio de objetos cortados e,
também, o número médio de padrões de corte para cada uma das classes. Em cada uma destas tabelas
usamos negrito para a melhor solução e itálico para a pior. O tempo computacional médio dos 360
problemas, em segundos, estão na Tabela 3.
Tabela1: Média dos resultados dos 20 problemas-teste para cada uma das 18 classes.
Dados
Perda total (média)
Heurísticas Construtivas
K
itens
M
FFD
Gulosa
Heurísticas Residuais
FFD
Gulosa
Nova
N-v2
C1
3
5
P
207
177
185
176
166
151
C2
3
5
M
692
524
407
395
438
409
C3
3
20
P
167
187
142
185
129
133
C4
3
20
M
897
842
219
276
131
136
C5
3
40
P
189
115
152
120
154
155
C6
3
40
M
835
852
297
373
191
133
C7
5
10
P
121
125
121
125
90
95
C8
5
10
M
672
1034
383
428
331
364
C9
5
20
P
115
125
116
127
98
100
C10
5
20
M
559
846
226
290
168
159
C11
5
40
P
132
127
134
134
106
114
C12
5
40
M
478
780
174
214
116
110
C13
7
10
P
47
81
49
80
56
59
C14
7
10
M
292
466
131
172
112
118
C15
7
20
P
109
97
94
98
96
95
C16
7
20
M
138
274
114
160
85
61
C17
7
40
P
94
91
107
82
100
102
C18
7
40
M
410
1159
139
220
93
89
1505
Podemos observar que as heurísticas Nova e Nova-versão 2, seguidas das Residual FFD e
Residual Gulosa foram as que melhor se comportaram, enquanto que as heurísticas construtivas FFD e
Gulosa Puras, apenas para poucas classes obtiveram bons resultados. Como a heurística Nova é
também do tipo residual, os resultados mostram claramente que a abordagem de resolver o problema
original relaxado da condição de integralidade (usando o método simplex com geração de colunas) e
procurar uma estratégia de arredondamento é bem eficiente, independentemente da demanda ser baixa
ou alta.
A heurística que mais obteve soluções com perdas menores (Tabela 1) foi a heurística Nova,
que apresentou-se melhor em 7 das 18 classes de exemplos, seguida da heurística Nova-versão 2, que
ganhou em 6 das 18 classes. A heurística Gulosa Residual foi a melhor em 2 classes, enquanto que as
outras três: FFD Residual, FFD Pura e Gulosa Pura foram as melhores em apenas uma classe cada
uma. Observe, também na Tabela 1, que as heurísticas Nova e Nova-versão 2, para as classes em que
tiveram os resultados piores, não foram tão ruins, veja por exemplo, as classes 13 e 15. Por outro lado,
as heurísticas puras, para as classes em que tiveram os resultados piores, produziram péssimas
soluções, por exemplo, a classe 18, com perda 13 vezes superior à melhor solução encontrada.
Quanto ao número de padrões de corte, podemos notar na Tabela 2 que a heurística Nova e
também a heurística Nova-versão 2 obtiveram em média o menor número de padrões de corte. Este
não foi o objetivo proposto, mas é um sub-produto interessante destas heurísticas, que foi tratado em
Poldi (2003) e Haessler (1980).
Tabela2: Média dos resultados dos 20 problemas-teste para cada uma das 18 classes.
Número de objetos cortados
Número de padrões de corte
Heurísticas
Heurísticas
Heurísticas
Heurísticas
Construtivas
Residuais
Construtivas
Residuais
FFD
Gulosa
FFD
Gulosa
Nova
N v2
FFD
Gulosa
FFD
Gulosa
Nova
N v2
C1
6,3
5,4
6,2
5,3
4,2
4,3
4,4
4,5
4,3
4,4
3,9
4,0
C2
12,2
10,8
10,7
10,5
10,4
10,4
6,4
5,9
5,9
5,8
5,1
5,1
C3
15,7
17,3
14,1
17,3
9,2
9,4
12,6
13,1
12,1
13,2
9,1
9,2
C4
48,8
26,9
35,8
34,8
31,5
31,4
20,7
19,3
20,9
20,2
16,6
16,5
C5
24,6
25,5
21,6
22,6
14,3
14,3
21,9
21,9
20,5
21,3
14,3
14,3
C6
72,7
56,4
52,3
48,3
46,1
46,1
38,1
34,2
38,2
34,9
29,3
29,3
C7
8,8
9,2
8,8
9,2
5,3
5,5
7,1
7,4
7,1
7,4
5,2
5,4
C8
27,3
24,6
20,2
19,6
18,6
19,2
11,1
10,9
11,0
10,7
8,8
9,1
C9
16,8
17,7
16,4
17,2
8,5
8,5
13,3
14,8
12,8
14,4
8,4
8,4
C10
42,5
35,2
33,9
31,7
30,1
30,2
19,9
18,3
21,4
19,8
15,3
15,4
C11
27,4
36,2
25,3
32,5
14,4
14,5
24,3
29,3
23,5
27,7
14,4
14,5
C12
82,4
68,9
58,5
57,2
54,5
54,4
39,1
36,4
38,4
37,6
30,3
30,2
C13
11,2
12,7
11,2
12,6
5,9
6,2
8,2
8,6
8,1
8,5
5,4
5,7
C14
22,0
19,9
17,8
16,9
16,3
16,1
10,8
10,8
10,9
10,5
8,6
9,1
C15
15,7
18,1
15,3
18,0
8,4
8,4
13,4
13,5
13,2
13,6
8,3
8,3
C16
35,5
29,4
26,9
24,8
22,1
22,2
19,7
18,6
19,1
18,1
14,6
14,6
C17
30,3
39,1
26,6
34,3
15,3
15,3
23,2
27,7
22,9
27,5
15,2
15,2
C18
87,0
74,4
62,4
60,4
57,8
57,7
39,3
35,5
40,1
38,7
30,5
30,6
1506
Quanto ao tempo computacional, mostrado na Tabela 3, a heurística mais lenta é a Gulosa
Residual, pois ela consiste em resolver o problema da mochila muitas vezes, sendo este o passo “mais
caro”. A heurística FFD Pura foi a mais rápida (o problema da mochila é resolvido heuristicamente),
mas podemos notar que não se comporta muito bem quanto à qualidade das soluções. Apesar de mais
lentas, as heurísticas residuais são viáveis para a resolução de problemas práticos. Observamos que,
nas heurísticas residuais, o tempo computacional foi medido desde o início do procedimento, que
inclui o tempo para encontrar a solução ótima relaxada.
Tabela3: Média do tempo computacional (em segundos) dos 360 problemas-teste.
Construtivas
Residuais
FFD
Gulosa
FFD
Gulosa
Nova
Nova versão 2
0,07
0,94
9,3
9,35
6,86
6,68
Para uma melhor análise comparativa entre heurísticas construtivas e residuais, foi feita a
média dos valores dados nas tabelas anteriores para as heurísticas construtivas e residuais. Os três
gráficos: 1, 2 e 3 referem-se a estas médias.
O Gráfico 1 mostra que as heurísticas residuais utilizaram, em média, um número menor de
objetos em estoque para produzir todos os itens demandados.
Gráfico 1: Número médio de objetos cortados.
O Gráfico 2 mostra que as heurísticas residuais utilizaram, em média, um número menor de
padrões de corte que as heurísticas puramente construtivas.
1507
Gráfico 2: Número médio de padrões de corte.
O Gráfico 3 mostra que as heurísticas residuais obtiveram as menores perdas. Notamos
claramente que as heurísticas construtivas foram ainda piores nas classes de números pares que são
classes onde os itens considerados são de tamanho médio, mais difíceis de serem combinados que
itens pequenos.
Gráfico 3: Perda total (média).
Observa-se na Tabela 1 que as classes ímpares são aquelas que contêm itens pequenos e as
classes pares contêm itens médios, que são mais difíceis de serem combinados; observando o Gráfico
3, podemos notar que as heurísticas construtivas apresentam perdas muito maiores que as heurísticas
residuais principalmente para os problemas das classes pares, cujos itens são mais difíceis de serem
combinados.
Assim, concluímos que não se deve usar heurísticas puramente construtivas mesmo em
problemas com baixa demanda, sob pena de produzir soluções desastrosas, ao contrário do que muitos
acreditavam, como observado em Riehme et al. (1996). A abordagem residual já havia sido
considerada a melhor maneira de se resolver o problema inteiro nas conclusões de Wäscher e Gau
(1996) para problemas sem considerar a demanda baixa. Reafirmamos, com os resultados aqui
apresentados que isso também é válido para problemas com baixa demanda. As duas novas heurísticas
(Nova e Nova-versão 2), que são residuais, são as mais recomendadas.
1508
7. Conclusão e Perspectivas Futuras
A abordagem por otimização linear com a aplicação de heurísticas para a resolução de
problemas de corte de estoque inteiro mostrou-se muito eficiente. As heurísticas residuais
apresentaram excelentes resultados até mesmo para problemas com baixa demanda, discordando do
folclore na área de problemas de corte e empacotamento de que a abordagem por otimização linear
(geração de colunas) é inadequada para problemas com baixa demanda, como comentado em Riehme
et al. (1996). Como propostas futuras, pretende-se uma nova comparação das heurísticas aqui
estudadas com uma extensão da proposta de Wäscher e Gau(1996) para o caso de múltiplas barras em
estoque, resolvendo-se otimamente o último problema residual como um problema ‘bin-packing’
Pretende-se também estender as heurísticas de arredondamento para o problema de corte de estoque
bidimensional.
8. Reconhecimento
Este trabalho teve apoio da FAPESP e CNPq.
9. Bibliografia
ARENALES, M.N., Modelos e Métodos Básicos dos problemas de corte, em ARENALES, M. N.,
MORABITO, R., (editores), O Problema de Corte e Empacotamento e Aplicações Industriais,
Capítulo I do Livro-texto de Mini curso, XX CNMAC - Congresso Nacional de Matemática
Aplicada e Computacional, Gramado - RS, (1997).
GAU, T., WÄSCHER, G., CUTGEN: A problem generator for the standard one-dimensional cutting
stock problem. European Journal of Operational Research, 84: 572-579 (1995).
GILMORE, P. C., GOMORY, R. E., A linear programming approach to the cutting stock problem.
Operations Research, 9: 848-859 (1961).
GILMORY, P. C., GOMORY, R. E., A linear programming approach to the cutting stock problem Part II. Operations Research, 11: 863-888 (1963).
GILMORY, P. C., GOMORY, R. E., Multi-stage cutting stock problems of two and more dimensions.
Operations Research, 13: 94-120 (1965).
HAESSLER, R. W., A note on computational modifications to the Gilmore-Gomory cutting stock
algorithm. Operations Research, 28: 1001-1005 (1980).
HINXMAN, A., The trim-loss and assortment problems: a survey. European Journal of Operational
Research, 5: 8-18 (1980).
MARQUES, F. P., O problema da mochila compartimentada. Dissertação de Mestrado, ICMC - USP,
(2000).
PINTO, M. J., O problema de corte de estoque inteiro. Dissertação de Mestrado, ICMC - USP, (1999).
POLDI, K. C., Algumas extensões do problema de corte de estoque. Dissertação de Mestrado, ICMC USP, (2003).
RIEHME, J., SCHEITHAUER, G., TERNO, J., The solution of two-stage guillotine cutting stock
problems having extremely varying order demands. European Journal of Operational Research,
91: 543-552 (1996).
STADTLER, H., A one-dimensional cutting stock problem in the Aluminum Industry and its solution.
European Journal of Operational Research, 44: 209-223 (1990).
WÄSCHER, G., GAU, T., Heuristics for the integer one-dimensional cutting stock problem: a
computational study. OR Spektrum, 18: 131-144 (1996).
1509