O Problema da mochila compartimentada e aplicações

Prévia do material em texto

ISSN 0101-7438 
Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 285 
O PROBLEMA DA MOCHILA COMPARTIMENTADA E APLICAÇÕES 
 
 
Fabiano do Prado Marques 
Marcos Nereu Arenales * 
Departamento de Ciências de Computação e Estatística 
Universidade de São Paulo 
São Carlos – SP 
E-mails: araxa@icmc.sc.usp.br 
 arenales@icmc.sc.usp.br 
 
* Corresponding author / autor para quem as correspondências devem ser encaminhadas 
 
Recebido em 03/2002, aceito em 12/2002 após 2 revisões 
 
 
Resumo 
 
O Problema da Mochila Compartimentada é uma variação do clássico problema da mochila e pode ser 
enunciado considerando-se a seguinte situação hipotética: um alpinista deve carregar sua mochila com 
possíveis itens de seu interesse. A cada item atribui-se o seu peso e um valor de utilidade (até aqui, o 
problema coincide com o clássico Problema da Mochila). Entretanto, os itens são de agrupamentos 
distintos (alimentos, medicamentos, utensílios, etc.) e devem estar em compartimentos separados na 
mochila. Os compartimentos da mochila são flexíveis e têm capacidades limitadas. A inclusão de um 
compartimento tem um custo fixo que depende do agrupamento com que foi preenchido, além de 
introduzir uma perda da capacidade da mochila. O problema consiste em determinar as capacidades 
adequadas de cada compartimento e como esses devem ser carregados, maximizando o valor de utilidade 
total, descontado o custo de incluir compartimentos. Neste trabalho propomos um modelo de otimização 
não linear inteiro para o problema e algumas heurísticas para sua resolução. Uma aplicação prática de 
relevância deste problema aparece no corte de bobinas de aço, sujeito à laminação, detalhado em apêndice. 
 
Palavras-chave: problemas da mochila, problemas de corte e empacotamento, otimização 
inteira e combinatória. 
 
 
Abstract 
 
The Compartmentalized Knapsack Problem is a variation of the classical knapsack problem and can be 
stated considering the following hypothetical situation: an alpinist must load his knapsack with items. 
Two numbers, a weight and an utility value are associated with each item (so far, the problem coincides 
with the classical integer Knapsack Problem). However, the items are of different classes (food, 
medicine, utensil, etc.) and they have to be packed into separate compartments inside the knapsack. The 
compartments are flexible and have limited capacities. Each compartment has a fixed cost that depends 
on the class of the items and, in addition, each new compartment introduces a loss on the capacity of 
the knapsack. The Compartmentalized Knapsack Problem consists in determining suitable capacities 
for each compartment as well as their packing. The objective is to maximize the total utility value paid off 
the cost of the compartments. In this work, we model the problem as an integer non-linear optimization 
problem and we design some heuristic methods for its solution. A practical application of this problem 
arises in steel rolls cutting subject to lamination, which is discussed in detail in the appendix. 
 
Keywords: knapsack problems, cutting and packing problems, integer and combinatorial 
optimization. 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
286 Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 
1. Introdução 
Cortar objetos grandes (por exemplo, bobinas, placas, paralelepípedos) para a produção de 
itens menores em quantidades bem definidos, ou empacotar itens pequenos dentro de espaços 
bem definidos são problemas idênticos, considerando que um item cortado de uma certa 
posição pode ser visto como ocupando aquela posição (daí a referência na literatura a 
Problemas de Corte e Empacotamento). 
O número de combinações possíveis dos itens dentro de um objeto (cada combinação 
possível é chamada padrão de corte) é, em geral, muito grande e, a tentativa de enumerá-las 
completamente é inviável do ponto de vista prático. Uma função objetivo pode ser definida 
medindo, por exemplo, perdas no caso do problema de corte, ou vazios no caso de 
empacotamento, ou custos, ou número de objetos usados, etc. Um problema de corte e 
empacotamento consiste em determinar um padrão de corte que minimize a função objetivo. 
Dentro desta categoria de problemas estão vários clássicos da literatura de pesquisa 
operacional, tais como os problemas da mochila, bin-packing, dentre outros, os quais são, em 
geral, NP-completo (Garey & Johnson, 1979). 
Vários trabalhos de revisão nos problemas de corte e empacotamento têm sido publicados 
nas últimas duas décadas, como Hinxman (1980), Dyckhoff et al. (1985), Dyckhoff (1990), 
Martello & Toth (1990), Dowsland & Dowsland (1992), Dyckhoff & Finke (1992), Sweeney 
& Parternoster (1992), Wäscher & Gau (1996), Dyckhoff et al. (1997), Lodi et al. (2002) e 
revistas de prestígio em Pesquisa Operacional têm publicado edições especiais sobre o tema 
tais como Dyckhoff & Wäscher (1990), Bischoff & Wäscher (1995), Arenales et al. (1999). 
Várias técnicas de resolução têm sido desenvolvidas, em geral especializando procedimentos 
consagrados da Pesquisa Operacional, tais como: enumeração implícita, programação 
dinâmica, relaxação lagrangeana, busca em grafos e heurísticas. 
Há, na literatura, um grande número de problemas de corte e empacotamento e houve uma 
tentativa no trabalho de Dyckhoff (1990) de classificá-los conforme algumas características. 
Em particular, uma primeira característica consiste nas dimensões relevantes do processo de 
corte. Assim, podemos ter os problemas de corte unidimensionais, com apenas uma 
dimensão relevante para o processo de corte, como por exemplo, o corte de bobinas 
(de papel, aço, tecidos, plásticos, etc) e barras. O clássico problema da mochila pode ser 
visto como um problema de corte unidimensional. Outros problemas bidimensionais, onde 
duas dimensões são relevantes, têm aplicações diversas, como por exemplo, o corte de placas 
de madeira, chapas de aço, placas de vidro, tecido, etc. O problema de corte estudado neste 
artigo é unidimensional. 
Uma outra característica dos problemas de corte e empacotamento decorre da elevada 
repetição de itens a serem produzidos, de modo que uma solução do problema exige o corte 
de vários objetos em estoque com repetição de padrões de corte (o número de objetos 
cortados por um mesmo padrão de corte passa a ser uma variável fundamental na formulação 
do problema, que é aproximado com sucesso por um problema de otimização linear). Este 
problema é conhecido na literatura como Problema de Corte de Estoque e os trabalhos 
pioneiros de Gilmore & Gomory (1961, 1963, 1965) utilizaram a técnica de geração de 
colunas e permitiram pela primeira vez que problemas práticos pudessem ser resolvidos com 
sucesso. A terminologia de problema de corte de estoque é também usada para problemas 
onde a repetição dos padrões de corte é baixa (por exemplo, apenas um objeto deve ser 
cortado por um padrão particular), mas há uma demanda a ser atendida, mesmo que em 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 287 
quantidade pequena (por exemplo, um ou dois itens). Neste caso, a solução arredondada da 
relaxação por otimização linear pode não ser uma boa aproximação. As características 
destacadas por Dyckhoff (1990) permitem uma classificação dos problemas de corte e 
empacotamento, muito embora haja uma diversidade de problemas abrigados na mesma 
categoria. 
Técnicas de resolução de problemas de corte de estoque (sejam baseadas na geração de 
colunas ou heurísticas gulosas, veja Hinxman, 1980 e Wäscher & Gau, 1996) dependem 
fundamentalmente da resolução de um subproblema de corte e empacotamento para a 
determinação do melhor padrão de corte para um particular objeto em estoque. Nesse 
subproblema de corte não há obrigatoriedade de satisfazer a demanda (caso a demanda seja 
baixa, deve-se cuidar para que a demanda não sejaexcedida, caso contrário, o padrão de 
corte gerado não seria usado uma única vez). O problema objeto deste trabalho consiste na 
determinação de um único padrão de corte que, como observado, é um problema 
fundamental na resolução de problemas mais gerais. 
O Problema da Mochila Compartimentada modela a situação hipotética descrita no resumo 
deste trabalho com importantes aplicações práticas. Uma aplicação industrial surge no corte 
de bobinas de aço, sujeitas à laminação, que será mais bem explicado em apêndice. 
Alguns poucos pesquisadores estudaram o problema de corte de bobinas de aço, onde ocorre 
o processo de laminação, porém o problema da mochila compartimentada foi evitado com 
auxílio de heurísticas simples. Por exemplo, Carvalho & Rodrigues (1994) utilizam a técnica 
de geração de colunas, mas para a determinação dos padrões de corte (onde surge o problema 
da mochila compartimentada) reduzem a busca a soluções homogêneas para cada 
compartimento. Em Ferreira et al. (1990) uma heurística gulosa é utilizada na geração de um 
conjunto de padrões de corte, sem a restrição de compartimentação, para então descartar 
aqueles que não podem ser compartimentados através de regras heurísticas simples. Em 
Pereira (1993) encontra-se uma boa descrição do problema, considerando o processo de 
laminação e uma modelagem matemática que o autor concluiu ser ineficiente na resolução de 
problemas práticos. Hoto (1996, 2001) e Marques (2000) focalizaram seus estudos no 
problema da mochila compartimentada. Em particular, Hoto (1996) fornece os primeiros 
passos para uma modelagem e métodos heurísticos e, mais tarde Hoto (2001), apresenta 
métodos exatos e heurísticos para a mochila compartimentada, que difere do presente 
trabalho por não incluir a limitação da quantidade de itens no padrão de corte (na literatura 
de corte e empacotamento é chamado de problema irrestrito). Mais recentemente, Zak (2002) 
estudou um problema relacionado com o problema da mochila compartimentada, onde uma 
seqüência de estágios no processo de corte obriga que bobinas intermediárias sejam 
produzidas antes dos itens finais, definindo uma espécie de compartimentos. Porém, os itens 
podem ser acomodados livremente dentro de cada compartimento, isto é, não há uma 
partição dos itens em agrupamentos (medicamentos, alimentos, etc.), como suposto no 
problema da mochila compartimentada a ser estudado neste trabalho. 
Uma variedade de problemas da mochila vem sendo estudada há várias décadas pela 
comunidade de Pesquisa Operacional e revisados, por exemplo, nos trabalhos de Martelo & 
Toth (1990) e Lin (1998). Porém o problema da mochila compartimentada não foi estudado. 
Na seção 2 definimos e modelamos o problema da mochila compartimentada. Na seção 3 
propomos três métodos heurísticos e seus desempenhos computacionais são apresentados na 
seção 4. Por fim, em apêndice, mostramos uma aplicação prática de relevância que aparece 
no corte de bobinas de aço, sujeito à laminação. 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
288 Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 
2. O Problema da Mochila Compartimentada 
Nesta seção formalizamos o problema da mochila compartimentada e apresentamos um 
modelo matemático de otimização não linear inteiro. Métodos heurísticos são apresentados 
na seção 3. 
 
2.1 Definição do Problema 
Um alpinista deve carregar sua mochila com m possíveis itens de sua utilidade. A cada 
item i, o alpinista atribui um valor de utilidade vi e seu peso li. O máximo peso que o 
alpinista suporta em sua jornada é de L. Até este ponto, o problema coincide com a 
formulação clássica do Problema da Mochila. Porém, os itens são de agrupamentos distintos 
(por exemplo: agrupamento 1: alimentos, agrupamento 2: utensílios, agrupamento 3: roupas, 
agrupamento 4: calçados, etc.) e devem estar em compartimentos separados dentro da 
mochila (isto é, cada compartimento contém somente itens de um mesmo agrupamento). 
Os compartimentos da mochila são flexíveis, permitindo que o alpinista carregue maior peso 
em alimentos do que em roupas, bem como reservar vários compartimentos para alimentos. 
As capacidades dos compartimentos (incógnitas) são limitadas inferior e superiormente 
(de acordo com os agrupamentos), caso estes sejam criados, digamos por: k
minL e k
maxL 
(isto é, a soma dos pesos li dos itens alocados no compartimento deve ser superior ou igual a 
k
minL e inferior ou igual a k
maxL ). A cada compartimento é associado um custo ck, caso este 
seja preenchido com itens do agrupamento k e, além disso, cada compartimento incluído na 
mochila produzirá uma perda da capacidade da mesma, digamos, S (isto é, se, por exemplo, 
três compartimentos forem utilizados, então a capacidade disponível na mochila será de 
L-3S, ao invés de L). 
O Problema da Mochila Compartimentada consiste em determinar as capacidades adequadas 
de cada compartimento e como estes devem ser carregados de modo que o valor de utilidade 
total (soma dos valores de utilidade de todos os itens selecionados) seja máximo, 
descontando-se os custos dos compartimentos, os quais dependem dos agrupamentos com 
que foram preenchidos (ck). 
 
2.2 Um Modelo Matemático para o Problema da Mochila Compartimentada 
Nesta seção propomos uma modelagem matemática para o Problema da Mochila 
Compartimentada. Observe que a cada compartimento da mochila, tem-se associado um 
único agrupamento k de itens, ou seja, não se admite itens de agrupamentos distintos no 
mesmo compartimento. 
Dados do problema: 
• M = {1,...,m}: conjunto dos tipos de itens; 
• li : peso (Kg) do item i (li > 0), i=1,...,m; 
• vi : valor de utilidade do item i (vi ≥ 0), i=1,...,m; 
• di : limite máximo de itens i na mochila, i=1,...,m; 
• K : número total de agrupamentos distintos; 
• Ak : agrupamento k, k=1,...,K, (M = A1 ∪ A2 ...∪ AK , Ai ∩ Aj = ∅, com i ≠ j); 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 289 
• Nk : número total de possíveis compartimentos para o agrupamento k (por exemplo: 
A1={1,2}, então L11 = 2l1+l2 , L21 = l1+2l2 , L31 = 2l1+2l2 , etc., são duas possíveis 
capacidades de compartimentos para o agrupamento 1. Ljk referencia o j-ésimo 
compartimento associado ao agrupamento k. O número Nk depende essencialmente dos 
itens do agrupamento k); 
• ck : custo de um compartimento de itens do agrupamento k, onde ck ≥ 0, k=1,...,K; 
• L: capacidade (Kg) da mochila; 
• k
minL : capacidade mínima (Kg) de cada compartimento associado ao agrupamento Ak; 
• k
maxL : capacidade máxima (Kg) de cada compartimento associado ao agrupamento Ak 
( LLL k
max
k
min << ); 
• S : perda (Kg) decorrente da inclusão de um novo compartimento na mochila. 
Variáveis: 
• αijk: número de itens do tipo i, do agrupamento k, no compartimento do tipo j, i=1,...,m, 
k=1,...,K e j=1,...,Nk; 
• βjk: número de vezes que o compartimento (padrão) do tipo j alocado com o agrupamento 
k é repetido na mochila, k=1,...,K e j=1,...,Nk. 
Assim, o j-ésimo compartimento com itens do agrupamento k tem: 
• A capacidade ocupada dada por: 
.1 e 1, k
Ai
ijkijk ,...,Nj,...,KklL
k
=== ∑
∈
α (1) 
• O valor de utilidade dado por: 
.1 e 1, k
Ai
ijkijk ,...,Nj,...,KkvV
k
=== ∑
∈
α (2) 
Um modelo matemático para o problema da mochila compartimentada pode ser escrito por: 
∑∑
= =
−
K
1k
N
1j
jkkjk
k
cV β)(Maximizar (3.1) 
k
Ai
ijkijk ,...,Nj,...,KkvV
k
1 e 1,:a Sujeito === ∑
∈
α (3.2) 
k
Ai
ijkijk ,...,Nj,...,KklL
k
1 e 1, === ∑
∈
α (3.3) 
k
k
maxjk
k
min ,...,Nj,...,KkLSLL 1 e 1, ==≤+≤ (3.4) 
,m1,idi
N
j
jkijk
k
K=≤∑
=
,
1
βα (3.5) 
LSL
K
1k
N
1j
jkjk
k
≤+∑∑
= =
β)( (3.6) 
kijk 1,...,Nj1,...,K k1,...,mi0 ===≥ e ,,inteiro,α (3.7) 
kjk 1,...,Nj1,...,Kk0 ==≥ e ,inteiro,β (3.8) 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
290 Pesquisa Operacional,v.22, n.3, p.285-304, julho a dezembro de 2002 
A função objetivo (3.1), a ser maximizada, fornece o valor total de utilidade, descontado o 
custo de alocar os compartimentos; as restrições (3.2) e (3.3) fornecem, respectivamente, o 
valor de utilidade e a capacidade de cada compartimento (obviamente, estas restrições podem 
ser eliminadas, substituindo-as nas demais restrições); as restrições (3.4) impõem limites 
físicos aos compartimentos, onde uma perda S deve ser considerada; as restrições (3.5) 
limitam o número de itens na mochila (esta restrição é importante quando um número 
excessivo de itens deve ser evitado, embora introduza não-linearidade nas restrições) e, por 
fim, a restrição (3.6) correspondente aos limites físicos da mochila. Observe que o problema 
(3.1-3.8) é um problema de otimização não linear inteiro. 
O modelo (3.1-3.8) permite considerar um agrupamento especial de itens, chamados “itens 
livres”, os quais podem ser incluídos na mochila sem necessidade de compartimentação. Nas 
heurísticas a seguir, denominamos o agrupamento K como o agrupamento de itens livres. 
Assim, para k=K, a restrição (3.4) é desnecessária (ou, LLL K
max
K
min == e0 de modo que é 
redundante) e cK=0. Na aplicação em interesse, isto é, no corte de bobinas de aço sujeito à 
laminação, os limitantes dos compartimentos são idênticos: min
k
min LL = e max
k
max LL = , 
exceto para o compartimento dos itens livres. Nas heurísticas propostas na próxima seção 
usamos esta característica, embora seja facilmente implementável quando os limitantes para 
os compartimentos dependem dos agrupamentos. 
 
3. Heurísticas para o Problema da Mochila Compartimentada 
Três heurísticas “gulosas” são propostas para a resolução do Problema da Mochila 
Compartimentada, considerando uma quantidade máxima de itens a serem alocados na 
mochila (di, para i=1,...,m). As heurísticas apostam que o alto custo de incluir um novo 
compartimento sugere que, quando criado, seja o maior possível (no caso do corte de bobinas 
de aço, apêndice A, este custo corresponde à laminação que é um processo caro e demorado, 
justificando a aposta). A seguir, fazemos uma exposição das heurísticas propostas e na seção 
4 analisamos seus desempenhos computacionais. 
 
3.1 Heurística de Decomposição 
Esta heurística consiste de duas fases: Na primeira fase são resolvidos (K–1) Problemas da 
Mochila de capacidade Lmax, um para cada agrupamento (exceto o agrupamento K dos itens 
livres), resultando nos melhores compartimentos associados aos agrupamentos. Na segunda 
fase, um problema da mochila clássico é resolvido, considerando os compartimentos obtidos 
na primeira fase como superitens (na verdade, uma combinação de itens) juntamente com os 
itens livres, para o carregamento da mochila. 
Uma solução particular para (3.1-3.8) é construída com as seguintes características: 
• Com o intuito de maximizar a função objetivo (3.1) é conveniente a construção de Vjk 
grande e, portanto, para cada agrupamento k, construímos apenas o melhor 
compartimento (Nk = 1, de modo que j pode ser suprimido) maximizando (3.2) restrito a 
(3.3), (3.4) e (3.7) (veja problema (4.1-4.3)). O valor de αik (j suprimido) é determinado, 
isto é, para cada agrupamento k, temos um compartimento; 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 291 
• Com Nk = 1 (apenas um compartimento por agrupamento) e αik já determinado: 
determina-se Lk (tamanho do compartimento k, veja (3.3), com o índice j suprimido). 
O valor de βk é determinado de modo a otimizar (3.1), sujeito às demais restrições do 
problema (3.1-3.8) (veja problema (5.1-5.5)). 
O algoritmo para a resolução desta heurística é apresentado a seguir. 
 
Algoritmo: 
Passo 1: Selecionar o melhor compartimento para o agrupamento k, k=1, …, K–1, 
resolvendo o seguinte Problema da Mochila, de capacidade Lmax: 
∑
∈
=
kAi
ikik vV αMaximizar (4.1) 
max
Ai
iki LSl
k
≤+∑
∈
α:aSujeito (4.2) 
1.1,...,KkAi dα0 kiik −=∈≤≤ ,para inteiro, e (4.3) 
 Seja ∑
∈
=
kAi
ikik lL α : tamanho do compartimento k. 
(note que αik são fixados neste passo). 
 
Passo 2: Resolver o seguinte problema da mochila envolvendo os compartimentos 
determinados no passo 1 e os itens livres: 
• βk é o número de vezes que o compartimento associado ao agrupamento k é repetido na 
mochila, 
• γk é o número de vezes que o item livre k é repetido na mochila. 
∑∑
∈
−
=
+−
KAk
kk
K
k
kkk vcV γβ
1
1
)(Maximizar (5.1) 
∑ ∑
−
= ∈
≤++
1
1
)(:aSujeito
K
k Ak
kkkk LlSL
K
γβ (5.2) 
11,, −=∈≤ ,...,KkAid kikik βα (5.3) 
,, Kkk Akd ∈≤γ (5.4) 
.,11,,inteirose0 Kkkik Ak,...,KkAi, ∈−=∈≥γα (5.5) 
 
3.2 Heurística do Melhor Compartimento 
Nesta heurística, como na anterior, o melhor compartimento para cada um dos agrupamentos 
de itens é determinado. Temos definido, então: 



≤≤−
−≤−
=



≤≤−
−≤+
=
mkKv
KkcV
V
mkKl
KkSL
L
k
kk
k
k
k
k
1se,
1se,
1se,
1se),(
'
'
 (6) 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
292 Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 
Em seguida, escolhe-se, o compartimento de maior valor por unidade ( ''
kk LV ), sendo então, 
alocado na mochila. Atualizam-se os dados e repete-se o processo até que um padrão seja 
gerado. Com isto é evitado o problema (5.1-5.5) do procedimento anterior. Porém, apesar de 
apenas um compartimento ser gerado por agrupamento, a cada passo, é possível ter 
diferentes compartimentos com o mesmo agrupamento, algo excluído na heurística anterior, 
onde era permitida apenas a repetição do melhor compartimento. O algoritmo é apresentado 
passo a passo a seguir. 
 
Algoritmo: 
Passo 1: lutil ← L; “lutil guarda a capacidade disponível na mochila a cada iteração” 
Passo 2: Para k = 1 a K–1, faça: 
2.1 Se (lutil ≥ maxL ) 
então L_compartimento = maxL 
senão Se (lutil < minL ) 
então L_compartimento=lutil e considera-se apenas os itens livres em (7.1-7.3), 
senão ( minL ≤ lutil < maxL ) L_compartimento = lutil 
Observação: se L_compartimento < Lmin ou se di = 0, ∀i ∈ Ak, então Vk = 0, k=1,...,K–1, 
restando apenas os itens livres para serem alocados. 
2.2 Selecionar o melhor compartimento para o agrupamento k resolvendo o seguinte 
Problema da Mochila de capacidade L_compartimento: 
∑
∈
=
kAi
ikik vV αMaximizar (7.1) 
mentoL_compartiSl
kAi
iki ≤+∑
∈
α:aSujeito (7.2) 
1.K,...,1kAi d0 kiik −=∈≤≤ , para inteiro, eα (7.3) 
Passo 3: 
3.1 Escolha k* tal que: Max{ K
k
k
k
kk Ak
l
v1,K1,k
L
cV
∈−=
− ,;, L } 
3.2 Atualização: 
Se k* em (3.1) corresponder a um compartimento 
então lutil ← lutil – *kL “alocar um compartimento” 
di ← di – αik* 
senão lutil ← lutil – *kl “alocar um item livre” 
di ← di – 1 
3.3 Se lutil ≥ Min{Min{Lk, k=1,...,K-1},Min{li, ∀ i∈ AK}}, volte ao Passo 2. 
 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 293 
3.3 Heurística dos “z” Melhores Compartimentos 
Esta heurística consiste basicamente na determinação dos “z” melhores compartimentos 
associados a cada agrupamento, ou seja, nas “z” melhores soluções dos Problemas da 
Mochila para cada agrupamento. A resolução de um problema de programação linear inteira 
considerando estes compartimentos como superitens, juntamente com os itens livres, 
determina um padrão de corte para a mochila compartimentada. O algoritmo é apresentado 
a seguir. 
 
Algoritmo: 
Passo 1: Selecionar os “z” melhores compartimentos para o agrupamento k determinando 
as “z” melhores soluções para o seguinte Problema da Mochila de capacidade Lmax, sendo 
V1k≥V2k≥...≥Vzk os “z” melhores valores de (8.1) e suas respectivas soluções αijk. 
 Para k=1,...,K-1 e j=1,...,z, resolva: 
∑
∈
=
kAi
ijkijk vV αMaximizar (8.1) 
max
Ai
ijki LSl
k
≤+∑
∈
α:aSujeito (8.2) 
.para inteiro, e kiijk Ai d0 ∈≤≤ α (8.3)Passo 2: Resolver o seguinte problema de programação inteira envolvendo os ((K–1)*z) 
compartimentos selecionados e os |AK| itens livres: 
• βjk é o número de vezes que o compartimento j para o agrupamento k é repetido na mochila, 
• γk é o número de vezes que o item livre k é repetido na mochila. 
∑∑∑
∈= =
+−
KAk
kkjk
1-K
1k
kjk
z
1j
vcV γβ)(Maximizar (9.1) 
S :aSujeito −≤+ ∑∑∑
∈= =
LlL
KAk
kk
1-K
1k
z
1j
jkjk γβ (9.2) 
1.,...,K1kAid ki
z
j
jkijk −=∈≤∑
=
 e ,α
1
β (9.3) 
.Akd Kkk ∈≤≤ ,0 γ (9.4) 
z.,...,1j 1K,...,1k0jk =−=≥ e inteiro,,β (9.5) 
∑
∈
−=+=
kAi
ijkijk ,...,KkSlL .11, onde α 
Nota: Embora a Heurística de Decomposição seja um caso particular da Heurística dos “z” 
Melhores Compartimentos, com z = 1, destacamo-la por resolver uma seqüência de 
problemas da mochila. O problema (9.1-9.5) é um problema otimização inteira com várias 
restrições, ao contrário de (5.1-5.5) que é um problema da mochila restrito. Para resolver os 
problemas que surgem nas heurísticas, propusemos algumas modificações para o método de 
enumeração implícita proposto por Gilmore & Gomory (1963), as quais são resumidamente 
apresentadas na próxima seção. 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
294 Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 
3.4 Resolução das Mochilas dentro das Heurísticas 
O método de enumeração implícita proposto por Gilmore & Gomory (1963) resolve 
eficientemente o problema da mochila irrestrito, nos tamanhos que ocorrem no contexto dos 
problemas de corte, isto é, com algumas dezenas de itens. A implementação usa a estratégia 
backtracking de modo que o espaço de soluções é percorrido de maneira bem simples, usando 
basicamente um vetor solução α = (α1 α2… αk 0…0), o qual tem o número de coordenadas 
igual ao número de itens da mochila, sendo αi o número de itens do tipo i, e k o último item 
incluído na mochila (αk > 0). O vetor solução é suficiente para caracterizar um nó na árvore 
de busca, de modo que o nó anterior é caracterizado por α’ = (α1 α2… αk–1 0…0). Regras 
simples para incluir novos itens na mochila (portanto, novas soluções ou novos nós na árvore 
de busca) são facilmente derivadas, dada a simplicidade das restrições da mochila, bem como 
limitantes superiores. Sempre que uma solução mais valiosa é identificada, seu valor é 
armazenado, descartando-se a anterior. Entretanto, os problemas da mochila que 
necessitamos resolver dentro de cada heurística apresentam características adicionais que 
podem ser incluídas no processo de busca, são elas: i) a limitação do número de itens na 
mochila, ii) a determinação das “z” melhores soluções e, iii) restrições adicionais dadas por 
(9.3). A inclusão de restrições adicionais no processo de busca no método de enumeração 
implícita de Gilmore e Gomory é bastante utilizada, porém nem sempre publicada. 
Por exemplo, os autores do método em seu artigo de 1963 sugeriram que restrições simples, 
do tipo limitação do número de facas, podem ser incluídas no processo de busca. Morabito & 
Garcia (1998) também incluíram restrições adicionais no processo de busca quando 
estudaram um problema prático de corte (originário de uma indústria de madeira 
reconstituída) onde surgiam restrições difíceis de serem descritas, mas razoavelmente 
simples de serem incluídas no processo de busca e anunciaram excelentes resultados. 
A seguir, damos uma breve descrição de como incluímos as características dos problemas da 
mochila que ocorrem dentro das heurísticas (seções 3.1 – 3.3). 
 
3.4.1 O Problema Restrito 
Os problemas de mochilas restritas que ocorrem em (4.1-4.3), (5.1-5.5) e (7.1-7.3) foram 
resolvidos por uma modificação simples no algoritmo de enumeração implícita de Gilmore 
& Gomory (1963). As variáveis devem obedecer à limitação na quantidade de cada item 
dentro da mochila. Para isto, o valor atribuído à variável associada ao item i (que consiste 
numa busca em profundidade na árvore de decisões) é calculado por: 
.1,, ,...,mi
l
Ldmin
i
ii =
















=α (10) 
onde L é a capacidade ociosa na mochila atualizada a cada nó percorrido na árvore de busca. 
O cálculo do limitante superior, importante para a eficiência do método de enumeração 
implícita sofre também ligeira modificação, devido à canalização das variáveis. 
 
3.4.2 As “z” Melhores Soluções 
Os problemas (8.1-8.3) consistem nas “z” melhores soluções de um problema da mochila. 
Para determinar tais soluções, basta armazenar no processo de busca as “z” melhores 
soluções, ao invés de armazenar apenas a melhor, como é feito no algoritmo de Gilmore & 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 295 
Gomory (1963). Assim, sempre que uma nova solução é determinada, o correspondente valor 
da função objetivo, digamos V, é comparado com os “z” valores previamente armazenados 
(por facilidade estão ordenados, por exemplo: V1 ≥ V2 ≥ …≥ Vz), sendo rejeitado caso V ≤ Vz, 
ou Vz é descartado e o valor de V armazenado ordenadamente. Observe que a nova solução 
gerada difere das anteriores, pois o processo de busca do algoritmo de Gilmore e Gomory 
evita repetições de soluções. Um método alternativo pseudo-polinomial para o cálculo das 
melhores soluções do problema da mochila pode ser encontrado em Yanasse et al. (2000). 
 
3.4.3 O Problema (9.1-9.5) 
Dentre os subproblemas que surgem nas heurísticas, o problema (9.1-9.5) é o mais 
complexo, pois várias restrições (9.3) são adicionadas à restrição da mochila (9.2). 
Procedemos analogamente ao caso restrito, introduzindo uma modificação no processo de 
busca do método de enumeração implícita de Gilmore & Gomory (1963), de modo a garantir 
a satisfação das restrições (9.3) e (9.4). Como estamos tratando com superitens (isto é, 
compartimentos que armazenam itens de um mesmo agrupamento) e considerando que temos 
“z” superitens associados a um mesmo agrupamento, surge a necessidade de um maior 
cuidado durante a busca para que as quantidades máximas di, i=1,...,m, não sejam violadas 
(veja restrições (9.3)). Para evitar tal violação é necessário primeiramente limitar a inclusão 
do superitem (j, k), j = 1,…,z e k = 1,…,K–1 (j-ésimo compartimento associado ao 
agrupamento k obtido pelo problema (8.1-8.3)) por:’ 
βjk ≤ Mínimo








∈








k
ijk
i Aitodoparad ,
α
. (11) 
Isto reduz ao caso restrito já discutido, mas não é suficiente. Por exemplo, se β1k > 0 e β2k > 0 
(isto é, o primeiro e segundo compartimentos associados ao agrupamento k são carregados na 
mochila) e, além disso, αi1k > 0 e αi2k > 0 (isto é, o item i aparece nos compartimentos 1 e 2) 
então o total de itens do tipo i já incluídos na mochila é dado por: αi1k β1k + αi2k β2k (veja 
restrição (9.3)). Portanto, a quantidade de superitem do tipo 3, por exemplo, é limitada por: 
β3k ≤ 








ki
id
3α
, (12) 
onde kkikkiii dd 2211 βαβα −−= é a folga da restrição (9.3). A busca é similar ao caso 
anterior, porém considerando tais limitações para o número de compartimentos. 
 
4. Resultados Computacionais 
As heurísticas apresentadas na seção 3 foram testadas para uma série de exemplos gerados 
aleatoriamente, classificados de acordo com as seguintes 4 características: 
i) número de itens livres; 
ii) comprimentos dos itens; 
iii) limites sobre o número de itens dos agrupamentos e, 
iv) limites sobre o número de itens livres. 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
296 Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 
Tais características tentam simular situações observadas com dados reais. A seguir 
apresentaremos as características que foram consideradas para cada conjunto de dados. 
Alguns parâmetros foram fixados para todos os exemplos, representando dados reais. Ao 
invés de peso, como temos utilizado até agora, usamos comprimentosda bobina e itens. 
 
• Parâmetros fixados: 
1. Capacidade da Mochila: L = 1200 mm; 
2. Capacidades mínima e máxima para os compartimentos: Lmin = 154 mm e 
Lmax = 456 mm. 
3. Perda devido à inclusão de compartimento (imperfeições nas bordas): S = 12 mm. 
4. Número de agrupamentos gerados aleatoriamente: K∈[3, 8]. 
5. Número de itens por agrupamento gerado aleatoriamente: |Ak|∈[2, 6]. 
6. vi = li + σ, σ ∈[1,100] (Obs: Na geração de colunas, cada mochila compartimentada, 
quando a função objetivo é minimizar a perda, terá os valores de utilidade neste 
formato, onde σ é o multiplicador simplex). 
7. ck ∈[1,100]. 
 
• Parâmetros variados: (para cada parâmetro, consideramos duas possibilidades) 
i) Número de Itens Livres: 
1: número pequeno de itens livres: |AK|∈[1, 3] 
2: número grande de itens livres: |AK|∈[4, 10] 
ii) Comprimentos dos Itens: 
3: Itens pequenos: li ∈ [36 mm, 105 mm]. 
4: Itens grandes e pequenos: li ∈ [36 mm, 444 mm]. 
(Obs: na indústria, os comprimentos dos itens variam bastante de modo que a 
situação 4 melhor representa a realidade; a situação 3 explora o pior caso). 
iii) Limites sobre o Número de Itens dos Agrupamentos: 
5: limitante baixo: di∈[1, 3], i∈Ak, k = 1,…,K–1. 
6: limitante alto: di∈[4, 15], i∈Ak, k = 1,…,K–1. 
iv) Limites sobre o Número de Itens Livres: 
7: limitante baixo: di∈[1, 3], i∈AK. 
8: limitante alto: di∈[4, 15], i∈AK. 
 
Na prática das indústrias metalúrgicas, onde surge o Problema da Mochila 
Compartimentada, o percentual de itens livres é bastante variado pode ser da ordem de 60% 
(itens livres correspondem a itens que não passam pela laminação). Embora as heurísticas 
descritas na seção 3 sejam projetadas para uma única mochila, devem ser executadas em 
outras ocasiões onde as várias situações acima podem ocorrer (por exemplo, na técnica de 
geração de colunas, uma mochila compartimentada deve ser resolvida a cada iteração do 
método simplex ou como geradora de padrões eficientes na heurística de exaustão Hinxman, 
1980), de modo que observar seus desempenhos nas características acima. 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 297 
A seguir, é feito um resumo dos resultados obtidos para vários exemplos gerados. Para 
cada situação combinada 20 exemplos foram gerados aleatoriamente e executados para as 
3 heurísticas (Decomposição, Melhor Compartimento e “z” Melhores Compartimentos com 
z = 2). 
 
4.1 Resultados Obtidos 
A seguir será apresentada uma tabela que mostra os valores médios obtidos para a função 
objetivo nos 20 exemplos executados para cada conjunto de dados. 
 
Tabela 1 – Valores médios da função objetivo obtidos executando as heurísticas para os 
conjuntos de dados. 
 Parâmetros 
dos Conjuntos Decomposição Melhor 
Compartimento 
"z" Melhores 
Compartimentos 
Conjunto A 1,3,5,7 2212,50 2143,00 2298,40* 
Conjunto B 1,3,5,8 2172,00 2140,30 2206,70* 
Conjunto C 1,3,6,7 2400,90 2647,70* 2439,70 
Conjunto D 1,3,6,8 2850,40 2895,50* 2875,20 
Conjunto E 1,4,5,7 1549,30 1578,90 1679,30* 
Conjunto F 1,4,5,8 2032,40 1983,60 2044,50* 
Conjunto G 1,4,6,7 2474,20 2480,80* 2474,20 
Conjunto H 1,4,6,8 2138,30 2193,10* 2180,40 
Conjunto I 2,3,5,7 2376,40 2364,90 2412,50* 
Conjunto J 2,3,5,8 2594,10 2465,80 2602,10* 
Conjunto K 2,3,6,7 2779,50 2702,20 2806,20* 
Conjunto L 2,3,6,8 2988,20 2937,60 3001,90* 
Conjunto M 2,4,5,7 2007,10 1920,90 2038,20* 
Conjunto N 2,4,5,8 1920,70 1939,20 2075,50* 
Conjunto O 2,4,6,7 1949,00 1914,40 2055,80* 
Conjunto P 2,4,6,8 2476,00 2319,20 2537,10* 
Média Total Todas as 
Combinações 2307,56 2289,19 2357,98 
* Melhor desempenho obtido para o conjunto de dados. 
 
Baseado nesta tabela, o gráfico a seguir foi construído. Neste gráfico, traçamos um 
comparativo entre os valores médios obtidos para a função objetivo (vistos na tabela 1) 
considerando as heurísticas executadas. Para tal, consideramos como base os valores médios 
obtidos para a heurística dos “z” Melhores Compartimentos (correspondendo a 100%) e de 
acordo com os valores obtidos nas outras heurísticas, verificamos se eles estão acima ou 
abaixo dos valores base. O gráfico 1 ilustra esta comparação. 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
298 Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 
Funções Objetivos nas Heurísticas
80,00%
85,00%
90,00%
95,00%
100,00%
105,00%
110,00%
Conjunto
A
Conjunto
B
Conjunto
C
Conjunto
D
Conjunto
E
Conjunto
F
Conjunto
G
Conjunto
H
Conjunto
I
Conjunto
J
Conjunto
K
Conjunto
L
Conjunto
M
Conjunto
N
Conjunto
O
Conjunto
P
Conjuntos de Dados
Va
ria
çã
o 
em
 P
er
ce
tu
al
Decomposição Melhor Compartimento "z" Melhores Compartimentos 
Gráfico 1 – Comparativo entre os valores obtidos para a função objetivo nas diversas heurísticas. 
 
4.2 Análise dos Resultados Obtidos 
A execução de vários exemplos permitiu-nos fazer uma comparação entre as três heurísticas 
apresentadas. Embora, de modo geral, a Heurística dos “z” Melhores Compartimentos tenha 
se destacado em relação às demais, a Heurística do Melhor Compartimento apresentou 
resultados melhores em alguns casos específicos (conjuntos C, D, G, H). Tal situação pode 
ser explicada analisando as características presentes nos conjuntos de dados onde essa 
melhora ocorreu. 
Devido à possibilidade de calcular, em seguidas iterações, compartimentos com capacidades 
diferentes e reduzidas, a Heurística do Melhor Compartimento não é tão dependente de 
muitos itens livres para gerar bons padrões de corte (exceto quando o espaço restante na 
mochila é inferior à capacidade mínima permitida para os compartimentos – Lmin). Em outro 
aspecto, a presença de um número considerável de itens nos agrupamentos faz melhorar os 
valores dos compartimentos (superitens). 
A Heurística dos “z” Melhores Compartimentos teve um desempenho superior na maioria dos 
casos, pois tal heurística permite um número maior de combinações para o preenchimento da 
mochila (maior número de compartimentos são gerados para cada agrupamento). 
Quanto à Heurística de Decomposição, por se tratar de um caso particular da Heurística dos 
“z” Melhores Compartimentos (onde z = 1), já era esperado que não obtivesse resultados tão 
destacados. Porém, ainda assim, esta heurística não perdeu tanto em desempenho para as 
demais, sendo, inclusive, melhor que a Heurística do Melhor Compartimento quando 
consideramos todos os exemplos executados para todas as combinações. 
Em relação ao tempo de execução, os resultados têm mostrado que as heurísticas rodam 
utilizando, em média, frações de segundo e, nos piores casos, em torno de 1 segundo. Tal 
característica torna-se importante se desejarmos usar estas heurísticas na geração de colunas 
para um problema de corte de estoque (onde demandas devem ser satisfeitas). 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 299 
5. Conclusões e Perspectivas Futuras 
Este trabalho abordou o Problema da Mochila Compartimentada, um problema de 
otimização combinatória, que é uma variação do clássico Problema da Mochila (porém, sua 
formulação matemática sofre profundas mudanças) e de importantes aplicações práticas, 
como no corte de bobinas de aço na indústria metalúrgica. 
Um modelo matemático de otimização não linear inteiro foi proposto e nos permitiu definir 
um conjunto de métodos heurísticos para a sua resolução. Uma nova heurística está em 
desenvolvimento considerando-se a possibilidade de gerar, para cada agrupamento, “w” 
compartimentos distintos (i.e., distintas capacidades para os compartimentos, ao invés de 
fixar em Lmax), o que melhoraria o poder combinatório para o preenchimento da mochila. 
Além disso, um método de geração de colunas para o problema de corte de estoque, onde 
demandas dos itens devem ser satisfeitas e os padrões de corte sãomochilas 
compartimentadas vem sendo desenvolvido. 
Uma outra continuação deste trabalho consiste em estender o problema aqui estudado para o 
caso de diversos tipos de mochilas com características diferentes (como, por exemplo, 
capacidades variadas). Isto levaria a considerar custos (ck) diferenciados de cada 
agrupamento a cada tipo de mochila. 
Por fim, poderíamos estudar o Problema da Mochila Compartimentada para casos 
bidimensionais envolvendo situações encontradas na prática como, por exemplo, o problema 
de corte de placas de circuitos impressos (os compartimentos são sub-retângulos menores da 
placa original, sobre os quais incidem os mesmos processos); problemas tridimensionais, 
como no caso de empacotamento de caixas que devem estar agrupadas (compartimentadas) 
por cliente. 
 
Agradecimentos 
Os autores agradecem os vários comentários e sugestões do Prof. Dr. Robison Hoto que 
muito enriqueceram o trabalho. Algumas figuras deste artigo foram inspiradas ou retiradas de 
sua tese de doutoramento. Esta pesquisa teve apoio da FAPESP e CNPq. 
 
Referências Bibliográficas 
(1) Arenales, M.N.; Morabito, R. & Yanasse, H. (eds.) (1999). Cutting and Packing 
Problems. Pesquisa Operacional, 19(2). 
(2) Bischoff, E. & Wäscher, G. (eds.) (1995). Cutting and Packing. European Journal of 
Operational Research, 84(3), special issue. 
(3) Carvalho, J.M.V. & Rodrigues, A.J.G. (1994). A Computer Based Interactive Approach 
to a Two-stage Cutting Stock Problem. INFOR, 32, 243-252. 
(4) Dowsland, K.A. & Dowsland, W.B. (1992). Packing Problems. European Journal of 
Operational Research, 56, 2-14. 
(5) Dyckhoff, H.; Abel, D. & Gal, T. (1985). Trim Loss and Related Problems. Omega, 13, 
59-72. 
(6) Dyckhoff, H. (1990). A Typology of Cutting and Packing Problems. European Journal 
of Operational Research, 44, 145-159. 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
300 Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 
(7) Dyckhoff, H. & Wäscher, G. (eds.) (1990). Cutting and Packing. European Journal of 
Operational Research, 44(2), special issue. 
(8) Dyckhoff, H. & Finke, U. (1992). Cutting and Packing in Production and Distribution: 
Typology and Bibliography. Springer-Verlag Co., Heidelberg. 
(9) Dyckhoff, H.; Scheithauer, G. & Terno, J. (1997). Cutting and Packing. Annotated 
Bibliographies in Combinatorial Optimization [edited by M. Amico, F. Maffioli and 
S. Martello], John Wiley & Sons, New York, 393-414. 
(10) Ferreira, J.S.; Neves, M.A. & Castro, P.F. (1990). A Two-phase Roll Cutting Problem. 
European Journal of Operational Research, 44, 185-196. 
(11) Garey, M.R. & Johnson, D.S. (1979). Computers and Intractability: A Guide to the 
Theory of NP-Completeness. W.H. Freeman and Co., San Francisco. 
(12) Gilmore, P. & Gomory, R. (1961). A Linear Programming Approach to the Cutting 
Stock Problem. Operations Research, 9, 849-859. 
(13) Gilmore, P. & Gomory, R. (1963). A Linear Programming Approach to the Cutting 
Stock Problem, part II. Operations Research, 14, 94-120. 
(14) Gilmore, P. & Gomory, R. (1965). MultiStage Cutting Stock Problems os Two and 
More Dimensions. Operations Research, 14, 1045-1074. 
(15) Hinxman, A.I. (1980). Trim-Loss and Assortment Problems: A Survey. European 
Journal of Operational Research, 5, 8-18. 
(16) Hoto, R.S.V. (1996). Otimização no Corte de Peças Unidimensionais com Restrições de 
Agrupamento. Dissertação de Mestrado, ICMSC-USP, São Carlos, São Paulo. 
(17) Hoto, R.S.V. (2001). O Problema da Mochila Compartimentada Aplicado no Corte de 
Bobinas de Aço. Tese de Doutoramento, COPPE-UFRJ, Rio de Janeiro, Rio de Janeiro. 
(18) Lin, E.Y.H. (1998). A Bibliographical Survey on Some Well-Known Non-Standard 
Knapsack Problems. INFOR, 36(4), 274-317. 
(19) Lodi, A.; Martello S. & Monaci, M. (2002). Two-Dimensional Packing Problems: 
A Survey. European Journal of Operational Research, 141, 241-252, 
(20) Marques, F.P. (2000). O Problema da Mochila Compartimentada. Dissertação de 
Mestrado, ICMC-USP, São Carlos, São Paulo. 
(21) Martello, S. & Toth, P. (1990). Knapsack Problems: Algorithms and Computer 
Implementations. John Wiley & Sons, Chichester. 
(22) Morabito, R. & Arenales, M. (1992). Um exame dos problemas de corte e 
empacotamento. Pesquisa Operacional, 12(1), 1-20. 
(23) Morabito, R. & Garcia, V. (1998). The Cutting Stock Problem in a Hardboard Industry: 
A Case Study. Computers and Operations Research, 25(6), 469-485. 
(24) Pereira, M.A. (1993). Uma Abordagem Matemática para o Problema de Corte e 
Laminação de Fitas de Aço. Dissertação de Mestrado, UNICAMP, Campinas, São Paulo. 
(25) Sweeney, P. & Paternoster, E. (1992). Cutting and Packing Problems: A Categorized, 
Application-Oriented Research Bibliography. Journal of the Operational Research 
Society, 43, 691-706. 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 301 
(26) Wäscher, G. & Gau, T. (1996). Heuristics for the Integer One-Dimensional Cutting 
Stock Problem: A Computacional Study. OR Specktrum, 18, 131-144. 
(27) Yanasse, H.H.; Soma, N.Y. & Maculan, N. (2000). An algorithm for determining the 
K-best solutions of the one-dimensional knapsack problem. Pesquisa Operacional, 
20(1), 117-134. 
(28) Zak, E.J. (2002). Modeling multistage cutting stock problems. European Journal of 
Operational Research, 141, 313-327. 
 
Apêndice: Aplicação no Corte de Bobinas de Aço 
Descrevemos aqui o corte em bobinas de aço, sujeito à laminação, o que foi a motivação 
inicial deste estudo, procurando enfocar os principais aspectos envolvidos no processo. Além 
disso, fazemos uma descrição dos custos envolvidos no processo de produção. 
Este problema foi observado em uma empresa que produz tubos de aço para diversas 
aplicações. A linha de produção consiste em produzir fitas, a partir de bobinas de aço em 
estoque. Essas fitas, por sua vez, serão utilizadas na confecção dos tubos soldados, que terão 
finalidades específicas. 
 
1. Considerações Iniciais 
Terminologia: 
• Bobinas mestres são os objetos a serem cortados (mochilas a serem preenchidas). Tais 
bobinas são identificadas pelos seus pesos (entre 12000 e 13500 Kg), larguras (variando 
de 1100 a 1200 mm), espessura do aço e pelo teor de carbono do aço segundo os critérios 
do SAE (Society of Automotive Engineers). Os mais utilizados são: SAE 1008, SAE 1010, 
SAE 1012, SAE 1017 e SAE 1021. 
• Bobinas intermediárias são as bobinas obtidas durante a primeira etapa de corte (os 
compartimentos). As bobinas intermediárias herdam algumas de suas características das 
bobinas mestres, como a espessura e o teor de carbono do aço. Porém, por sua vez, as 
bobinas intermediárias terão seus próprios pesos e larguras. 
• Fitas são os itens obtidos durante a segunda etapa de corte, a partir das bobinas 
intermediárias. As fitas possuem características bem definidas como a largura (de acordo 
com o diâmetro dos tubos a serem produzidos), a espessura e o tipo de aço. 
Observe que uma bobina com o tipo de aço SAE 1008 somente poderá produzir fitas com 
esta característica. No que se segue, supomos que o conjunto de fitas selecionado para ser 
produzido tenha as características necessárias de uma mesma bobina mestre a ser cortada. 
 
2. O Processo de Corte 
Uma peculiaridade do problema ao se efetuar cortes em bobinas de aço sujeitas a um 
processo técnico de laminação, reside no fato de que as bobinas mestres não podem ser 
laminadas devido a sua largura, pois existem restrições físicas, impostas pelo laminador, 
estabelecendo limites nas larguras das bobinas para que essas possam ser laminadas. 
Portanto, as bobinas mestres devem ser cortadas em bobinas intermediárias, cujas larguras 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
302 Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 
respeitem as restrições do laminador e, posteriormente,recortadas em fitas. Além disso, vale 
enfatizar que o processo de laminação é executado visando ajustar a espessura das bobinas 
intermediárias de acordo com as fitas demandadas. 
Sendo assim, temos duas etapas de corte bem caracterizadas, definindo um compartimento 
de fitas (bobinas intermediárias deverão produzir fitas de mesma espessura) na construção de 
um padrão de corte. 
Denomina-se “Refugo” todo tipo de perda inevitável de material durante o processo de 
obtenção das fitas, e “Sobra” todas as outras categorias de perdas de material. Temos dois 
refugos intrínsecos: um durante a primeira etapa de corte e outro durante a segunda etapa de 
corte, ilustrado na figura 1. 
 
 
Largura Útil 
Largura Total 
Refugo 
Bobina mestre 
Primeira 
Etapa 
de 
Corte 
Segunda 
Etapa 
de 
Corte 
Refugo 
Bobinas intermediárias 
Fitas 
Refugos 
+ Sobras
Neste ponto, poderá, ou não, ocorrer laminação. 
 
Figura 1 – Corte em bobinas de aço com refugos embutidos. 
 
Na prática, por uma restrição no número de facas, o número de bobinas intermediárias na 
primeira etapa é limitado. Uma dificuldade adicional no processo de corte decorre da 
existência de demandas baixas, de maneira que a utilização de uma bobina mestre com peso 
consideravelmente alto poderá proporcionar excesso de produção, mesmo que apenas uma 
fita de um determinado tipo apareça no padrão de corte. Para evitar este excesso, 
(Hoto, 2001) considera uma formulação 1.5-dimensional, introduzindo uma variável no 
comprimento da bobina mestre. 
 
3. A Cortadeira 
Uma bobina mestre é desenrolada e o processo de corte para obtenção das bobinas 
intermediárias é feito longitudinalmente por “discos de corte” (não há cortes transversais e 
por isso podemos entender que o problema é unidimensional). Nesta etapa, existem 
perdas intrínsecas (que podem ser visualizadas na figura 1 como refugos) nas laterais da 
bobina, para eliminar as irregularidades das bordas, variando entre 6 a 8 mm por borda. 
Posteriormente, as bobinas intermediárias são enroladas e passarão, ou não, para o processo 
de laminação se as espessuras das fitas forem idênticas à espessura da bobina mestre, não 
será necessário o processo de laminação. 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 303 
O tempo de preparação da máquina de corte é cerca de 40 minutos e o tempo médio para o 
corte de uma bobina gira em torno de 15 minutos. A figura 2 ilustra o processo de corte. 
 
 
BOBINA MESTRE 
CORTADEIRA 
BOBINA INTERMEDIÁRIA 
 
Figura 2 – Perfil do processo de corte em bobinas de aço. 
 
4. Laminação 
O processo de laminação tem por objetivo diminuir (quando necessário) a espessura do 
material de uma bobina intermediária. Esse processo se dá à temperatura ambiente 
(laminação a frio) por meio de cilindros de laminação que efetuam pressão sobre a lâmina de 
aço (figura 3). Cabe notar que, eventualmente, uma mesma bobina intermediária poderá 
sofrer mais de uma laminação. Isto é necessário para que se possa obter a espessura desejada 
do material (a redução é cerca de 15 a 20% da espessura em cada passo, e de 50 a 60% no 
total). Como todas as outras, a máquina que executará a laminação (o laminador) possui 
restrições do tipo: Não é possível laminar uma bobina intermediária com menos de 154 mm e 
mais de 456 mm de largura (isto limita os tamanhos dos compartimentos, conforme definição 
do Problema da Mochila Compartimentada, seção 2). A figura 3 ilustra o processo de 
laminação em perfil. 
 
 
Carretel 
Desenrolador 
Cilindros de
Laminação 
Sentido de Operação 
Carretel 
Enrolador 
 
Figura 3 – Perfil do processo de laminação. 
Marques & Arenales – O problema da mochila compartimentada e aplicações 
304 Pesquisa Operacional, v.22, n.3, p.285-304, julho a dezembro de 2002 
Após a laminação, a bobina intermediária é novamente cortada para a produção das fitas. 
Quando uma bobina intermediária é submetida ao processo de laminação, o material adquire 
alguns fatores físicos indesejáveis e se faz necessário, após o recorte, um tratamento térmico 
ao material denominado recozimento. No recozimento, as fitas são acondicionadas em fornos 
especiais onde permanecem por um certo período e, em seguida, são lentamente resfriadas 
até atingirem a temperatura ambiente. O processo todo leva cerca de 24 horas e constitui um 
gargalo na produção. 
Em síntese, as diversas peculiaridades da linha de produção aqui citadas apontam para um 
problema complexo. Além disso, a necessidade do processo de laminação induz padrões de 
corte pouco evidentes, pois nem todas as fitas têm a mesma espessura. Uma empresa na 
capital paulista que trabalha com este problema indica uma perda de material da ordem de 
10%, o que corresponde a uma média mensal de 500 toneladas de aço (Hoto, 2001).