A pesquisa Operacional e os Recursos Renováveis
4 a 7 de novembro de 2003, Natal-RN
PROBLEMAS DE CORTE EM DUAS FASES: UMA REVISÃO PARCIAL
Robinson Hoto
Universidade Estadual de Londrina, CCE, Departamento de Matemática
CEP 86051-970, CP 6001, fone (43) 3371 4226, [email protected]
Campus Universitário, Londrina, PR, Brasil
Fabiano Marques
Universidade de São Paulo, ICMC, Departamento de Computação e Estatística
CEP 13560-970, fone (16) 273 9648, [email protected]
Campus Universitário, São Carlos, SP, Brasil
Resumo
Problemas de Corte e Empacotamento são amplamente estudados e diversos trabalhos sobre o
tema podem ser encontrados na literatura, seja no aspecto puramente teórico ou nas aplicações
práticas. Dentre estes inúmeros problemas, alguns autores relataram ao longo dos anos, casos
em que o processo de corte necessita ser efetuado em duas fases. Este trabalho, que é parcial,
pretende iniciar uma revisão de problemas de corte em duas fases.
Palavras-Chave: corte e empacotamento, duas fases, padrões compartimentados.
Abstract
Cutting and packing problems are widely studied and several works about these problems can
be found in literature, in theorical aspect and also practical applications. Among these various
problems, some authors had told, along years, cases in which the cutting process needs to be
done in two phases. This work, which is a partial study, intends to start a two-phases cutting
problems review.
Keywords: cut and packing, two-phases, compartmented patterns.
Introdução
No contexto dos problemas de corte e empacotamento, o termo “objeto” é usado para designar
uma peça do estoque, e o termo “itens” designa as peças a serem cortadas dos objetos. Num
problema de corte em duas fases os itens são obtidos dos objetos intermediários, induzindo uma
fase de corte (originando os objetos intermediários) e recorte (originando os itens demandados).
Caso objetos intermediários (compartimentos) necessitem ser definidos como padrões
compartimentados o problema de corte será em três fases (fase 1 de corte + fase 2 de corte +
recorte), neste caso os padrões de corte serão denominados bi-compartimentados
(compartimentos no interior de compartimentos). Um problema de corte em n+1 fases (fase 1 de
corte + fase 2 de corte + ... + fase n de corte + recorte) é aquele que apresenta padrões de corte
n-compartimentados, onde os itens demandados são obtidos após o recorte (a última fase de
corte).
Um exemplo bastante comum de corte em duas fases é o problema do corte de bobinas de aço
sujeitas a laminação. Na figura 1 observamos como é a configuração de um padrão de corte
compartimentado, onde o corte contínuo define dois objetos intermediários (sub-bobinas) e os
cortes tracejados definem os itens (fitas de aço). Observe que os itens que compõem o padrão
são provenientes de dois grupos distintos (laminações distintas). Os itens de cada grupo irão
definir compartimentos (sub-bobinas) que por sua vez definirão o padrão compartimentado.
Após a primeira fase de corte (corte) são obtidos os objetos intermediários (sub-bobinas que
sofrerão laminações distintas). Após a segunda fase de corte (recorte) são obtidos os itens (fitas
de aço). Em algumas empresas, após a laminação algumas fitas recebem um tipo especial de
revestimento, neste caso, além da compatibilidade no processo de laminação é preciso verificar
compatibilidade no processo de revestimento, pois, itens de subconjuntos distintos sofrerão
revestimentos distintos. Considere oito itens (parte de uma carteira) agrupados da seguinte
forma:
Grupo B
Grupo C
Grupo 1
Grupo 2
Grupo3
Grupo A
Revestimento Revestimento Revestimento Laminação Laminação Laminação
de Cobre
de Teflon
de Níquel
Fraca
Média
Forte
Itens
Itens
Itens
Itens
Itens
Itens
3e4
5e6
7e8
1e2
3, 4, 5 e 6
7e8
Na figura 1 ilustramos um possível padrão de corte, onde os itens 1 e 2 são cortados em duas
fases, e os demais são cortados em três fases de corte.
Padrão de Corte Compartimentado
objeto
1.o corte
objetos
intermediários
p/ laminação
2.o corte
objetos
intermediários
p/ revestimento
itens
1700
Os autores estudam o problema da mochila compartimentada com restrições adicionais
(caso restrito), essencial na obtenção de uma solução inteira viável do corte de bobinas de aço.
• Sessão 8 (Zaq, 2002) [33, 34]
O autor propõe uma técnica de geração simultânea de linhas e colunas aplicada na
resolução do corte de bobinas de papel.
1 As abordagens de Haessler
O Professor Robert Haessler da Universidade de Michigan descreveu em 1971 [09] um modelo
não-linear para o corte de bobinas de papel, numa abordagem em duas fases de corte. Em
problemas como este estudado por Haessler, fruto de sua tese de doutoramento [08], há uma
limitação no número de facas a serem usadas num padrão, ou analogamente, o número de itens
num padrão de corte deve ser limitado. Esta restrição pode ser considerada ao gerar padrões,
entretanto, Haessler optou em modelar o problema, permitindo a geração de padrões que
excedessem o limite de itens (o mesmo que a limitação no número de facas). Neste caso, há a
necessidade de efetuar um corte, dividindo a bobina em sub-bobinas, onde o número de itens
não excede o limite tolerado, seguido de um recorte para obter os rolos (itens). Na figura 2
ilustramos o caso em que o limite de itens é no máximo 5 (o mesmo que 4 facas). Na prática, do
total de facas, duas serão utilizadas para aparar as bordas das bobinas e sub-bobinas.
Outra situação técnica que Haessler encontrou, induzindo corte em duas fases, surge quando
o número de bobinas a serem cortadas, segundo um padrão, é muito reduzido. Neste caso, o
número alto de trocas de padrões na máquina de corte prejudica o rendimento da máquina de
papel (a que confecciona as bobinas) [10]. Para contornar o problema, Haessler propôs cortar e
recortar bobinas para aliviar a pressão da produção da máquina de papel sobre a de corte. Sob
este aspecto o problema difere do corte de bobinas de aço, pois, não há necessidade de agrupar
os itens já que não existem restrições quanto à compatibilidade.
Padrão de Corte com
k=1
Padrão de Corte com
k=2
corte
corte
recorte
Fig 2. Padrões de corte em bobinas de papel, segundo a abordagem de Haessler.
Vejamos como Haessler modelou o problema: considere uma carteira de n rolos (itens) de
larguras l i e demandas di , admita que as bobinas (objetos) tenham comprimento L. Sejam
ainda:
ct : (cost of trim loss) custo associado à perda de material por unidade de comprimento;
c p : (cost of processing) custo associado a processamentos de sub-bobinas em relação aos
padrões;
aijk :
número de itens do tipo i no padrão j tal que, se o número de itens no padrão excede o
limite de
facas então k=2, caso contrário k=1. Tendo em vista esta notação, seja P2 o
conjunto dos índices dos padrões para os quais k=2 e P1 o conjunto dos índices dos padrões
para os quais k=1 (
figura 2);
k
x j : número de rolos a serem cortados segundo o padrão j, conforme k=1 ou k=2;
1701
n
Observe que um padrão de corte será viável se ∑ aijk l i ≤ L , com aijk ≥ 0 e inteiro para i=1,
i =1
...,
n.
O
custo
associado
às
perdas de material pode ser dado por
n
n


ct  ∑ ( L − ∑ aijk l i ) x1j + ∑ ( L − ∑ aijk l i ) x 2j  . Haessler observou que o custo do papel não é
i =1
j∈P2
i =1
 j∈P1

significativo se comparado com custos operacionais, de modo que, é recomendável otimizar não
apenas as perdas, mas, os custos de produção que contemplem as perdas e os processos
operacionais. Tendo em vista a pressão exercida pela máquina de papel sobre a máquina de
corte, ele sugeriu valores mínimos LBc e LB p ≤ LBc para número de bobinas completas e
parciais (sub-bobinas) a serem cortadas na máquina de corte, de modo que, os seguintes casos
foram considerados:
1. se x1j < LB p ≤ LBc , então 2 x1j sub-bobinas serão recortadas na máquina de recorte (figura
3a). Isto devido ao baixo número de bobinas a serem cortadas;
2. se LB p ≤ x1j < LBc , então x1j sub-bobinas serão recortadas na máquina de corte e x1j subbobinas serão recortadas na máquina de recorte (figura 3b);
3. se x 2j < LB p , então 2 x 2j sub-bobinas serão recortadas na máquina de recorte (figura 3c). Isto
devido ao limite de facas;
Assim, 2 x1j sub-bobinas serão processadas conforme os casos 1 e 2, este número pode ser
computado da seguinte forma: ∑ x1j δ( x1j − LB p ) + ∑ x1j δ( x1j − LBc ) , onde δ( x − LB) = 1 se
j∈P1
j∈P1
0 < x < LB , e δ( x − LB) = 0 em caso contrário. Analogamente, 2 x 2j sub-bobinas serão
processadas conforme o caso 3, este número pode ser computado da seguinte forma:
2
2
∑ x j (1 + δ( x j − LB p )) . Como nem todos os padrões de corte irão ser efetuados em duas fases
j∈P2
(figura 2), Haessler optou por computar o custo da porção de sub-bobinas processadas em
relação
aos
padrões
de
corte,
dado
por

 

c p  ∑ x1j δ( x1j − LB p ) + ∑ x1j δ( x1j − LBc ) + ∑ x 2j (1 + δ( x 2j − LB p ))   ∑ x1j + ∑ x 2j  . Na
j∈P1
j∈S 2
j∈P2
 j∈P1
  j∈P1

prática as demandas di dos itens possuem tolerâncias, de modo que, dimin ≤ di ≤ dimax para
cada i = 1, ..., n, veja [13]. O modelo não-linear proposto por Haessler é o seguinte:
n
n


minimizar ct  ∑ ( L − ∑ aijk l i ) x1j + ∑ ( L − ∑ aijk l i ) x 2j  +
i =1
j∈P2
i =1
 j∈P1



+ c p  ∑ x1j δ( x1j − LB p ) + ∑ x1j δ( x1j − LBc ) + ∑ x 2j (1 + δ( x 2j − LB p )) 
j∈P1
j∈P2
 j∈P1

sujeito a:

1
2
 ∑ x j + ∑ x j 
j∈P2
 j∈P1

dimin ≤ ∑ aij1 x1j + ∑ aij2 x 2j ≤ dimax ; x1j , x 2j ≥ 0 e inteiros com i = 1, ..., n e
j∈P1
j∈P2
j ∈ P1 ∪ P2
Para resolver o problema Haessler desenvolveu uma heurística [08]. Inicialmente ele avalia o
total de bobinas e o número médio de itens numa bobina, computando os seguintes valores:
n
n
n
i =1
i =1
i =1
( ∑ di l i ) L e L ( ∑ di ) ( ∑ di l i ) .
1702
(a) n.o baixo de bobinas
a serem cortadas
(b) parte das bobinas são cortadas
no corte e parte no recorte
corte
(c) o limite de facas é excedido
corte
corte
recorte
recorte
recorte
Fig 3. Corte e recorte de bobinas de papel na abordagem de Haessler.
A seguir, é construído um padrão de corte que satisfaça as seguintes condições:
n
1. L − Tmax ≤ ∑ aijk l i ≤ L , aijk ≥ 0 e inteiro, onde Tmax é a perda máxima tolerada;
i =1
n
2. N min ≤ ∑ aijk ≤ N max , onde N min e N max são respectivamente o número mínimo e máximo
i =1
de itens tolerados;
3. aijk LB ≤ di , para todo aijk > 0 , onde LB é o número mínimo de bobinas que devem ser
processadas;
O padrão obtido é usado até a exaustão, as demandas dos itens são atualizadas, as estimativas
do total de bobinas e do número médio de itens são recalculadas e gera-se um novo padrão,
segundo 1, 2 e 3. Este processo é repetido até que toda demanda seja satisfeita, ou quando não
for possível gerar um padrão, neste caso, 1, 2 e 3 são relaxadas para gerar um padrão,
finalizando com uma solução viável para o problema. Haessler citou a dificuldade de resolver o
problema como um programa linear, devido à natureza dos padrões de corte. Ele acrescentou
que o ajuste dos parâmetros necessários para gerar o próximo padrão, após a atualização das
demandas, não consiste em tarefa elementar.
Haessler estudou também um problema numa indústria de filme plástico [12], onde as
bobinas do estoque necessitam ser cortadas em sub-bobinas para processamentos em máquinas
que não suportam a largura de uma bobina do estoque. Adicionalmente este problema apresenta
uma característica peculiar, pois, as demandas são rolos de filmes de largura l i e comprimento
Li (figura 4a), de modo que, além do corte se passar em duas fases o problema é 1.5dimensional [11]. Num problema 1.5-dimensional a variável de decisão x j , associada ao padrão
j, não é mais inteira, pois, ela passa a medir o comprimento que será cortado da bobina, segundo
o padrão (figura 4b). Este problema pode ser modelado como um programa linear e novamente
a dificuldade consiste em construir um padrão de corte, uma vez que, é preciso decidir a largura
e a quantidade de cada sub-bobina (objeto intermediário) a ser cortada de uma bobina (objeto).
(a)
(b)
rolo aberto
x j2
l2
Li
rolo
x j1
l 15
li
li
l3
l9
l2
l9
L
Fig 4. a) Rolo de largura l i e comprimento Li ; b) corte 1.5-dimensional.
1703
2 Ferreira-Neves-Castro e o Corte de Bobinas de Aço
Na introdução deste trabalho citamos o problema do corte em bobinas de aço sujeitas à
laminação (figura 1). O Professor Jose Antonio Soeiro Ferreira da Universidade do Porto,
juntamente com seus colegas António Neves e Fonseca e Castro, propuseram em 1990 [04] para
o problema em questão, um procedimento heurístico que passaremos a descrever, onde di e l i
são respectivamente as demandas (em Kg) e larguras (em mm) das fitas de aço (itens) para i = 1,
..., n, e L é a largura (em mm) das bobinas do estoque (objetos):
1. Defina os fatores µi = di l i para cada i = 1, ..., n e ordene-os da seguinte forma:
µ1 ≥ µ 2 ≥ K ≥ µ n ;
2. Escolha uma quantidade p de itens segundo o fator µ do passo 1 (5 a 9 primeiros itens foram
os valores experimentados). Seja m o número de bobinas intermediárias (objetos
intermediários) do padrão que será escolhido e faça m = 3 . Seja S1 a largura (em mm) da
apara retirada das bordas da bobina e S2 a largura (em mm) da apara retirada das bordas das
bobinas intermediárias, assim a largura útil da bobina será Lútil = L − ( S1 + mS2 ) , onde
inicialmente m = 3 ;
3. Ordene as larguras dos itens da seguinte forma: l1 ≥ l 2 ≥ Kl p ;
4. Para cada j = 1, ..., p gere um padrão de corte segundo a heurística FFD (p padrões serão
gerados);
5. Determine x j ≥ 0 , o total de vezes que cada padrão será usado sem exceder as demandas dos
itens. Se nenhum padrão tiver uso, incremente o valor de p e de m , recalcule
Lútil = L − ( S1 + mS2 ) e retorne ao passo 3 para gerar novos padrões no passo 4;

p

6. Defina os fatores γ j = x j  Lútil − ∑ aij  , onde aij ≥ 0 é o número de itens do tipo i no
i =1


padrão j e ordene-os da seguinte forma: γ1 ≥ γ 2 ≥ K ≥ γ p ;
7. Selecione o padrão j* que está associado a γ1 e verifique se ele é viável, segundo as
seguintes restrições:
 L − S1 
 L − S1 
(a) 
≤m≤
 , onde L min e L max são respectivamente as larguras
 L min + S 2 
 L max + S2 
mínima e máxima (em mm) permitidas para uma bobina intermediária,  .  é o maior inteiro
menor ou igual a... e  .  é o menor inteiro maior ou igual a...
(b) Lmin ≤ ∑ aij*l i + S 2 ≤ Lmax , onde N kj* é o conjunto dos índices dos itens que
i ∈ N kj*
compõem a bobina intermediária k = 1, ..., m. Estes itens devem ser compatíveis entre si, de
modo que possam sofrer o mesmo tipo de laminação, do contrário o padrão não será viável;
(c) ∑ aij*l i ≤ N max , para cada bobina intermediária k = 1, ..., m, onde N max é o número
i ∈ N kj*
total de itens permitido numa bobina intermediária (é devido à limitação no número de
facas);
Se o padrão j* que está associado a γ1 não for viável, teste os demais padrões até que um
padrão viável seja encontrado, caso contrário incremente o valor de p e de m , recalcule
Lútil = L − ( S1 + mS 2 ) e retorne ao passo 3 para gerar novos padrões no passo 4;
8. Use o padrão selecionado e atualize as demandas. Se houver demanda remanescente retorne
ao passo 1, caso contrário PARE.
Os autores relataram terem obtido bons resultados práticos com a heurística descrita,
entretanto, observamos que a escolha de determinados parâmetros é crítica, por exemplo, no
passo 2 os valores de r e m são iniciados em seus “mínimos” e gradativamente são
1704
incrementados até que padrões viáveis passem a ser gerados, ocorre que em problemas como
este um procedimento guloso pode ser desastroso. A geração dos padrões é efetuada por meio
da heurística FFD, muito rápida e simples, porém, muito pobre para casos elaborados, além do
mais, ao gerar um padrão, as restrições que determinam sua natureza de ser compartimentado
não são consideradas, de modo que, no passo 7 é possível que todos os padrões gerados sejam
descartados por violarem justamente estas condições, uma situação indesejada.
3 Carvalho-Rodrigues e a abordagem de Geração de Colunas para o Corte de Bobinas de
Aço
Em 1991 o Professor Valério de Carvalho da Universidade do Minho apresentou sua tese de
doutoramento [01] (sob orientação do Professor Guimarães Rodrigues da Universidade do
Minho), cujo foco é a utilização da técnica de geração de colunas [05, 06] na resolução do
problema do corte de bobinas de aço. Posteriormente ambos publicaram dois trabalhos, um em
1994 [02] e outro em 1995 [03], que abordam o assunto.
Considere N o conjunto dos índices dos itens (fitas de aço) e J o conjunto dos padrões de
corte viáveis (padrões compartimentados). Sejam dimin e dimax as demandas mínima e máxima
de cada item i ∈ N , e aij ≥ 0 o número de itens i no padrão j ∈ J . O objetivo será o de
minimizar custos de material e processamento, onde c perda é o custo associado a perda de
material, clam é o custo associado ao processo de laminação, c1 é o custo associado ao acerto de
um padrão na primeira fase de corte (as trocas de padrões serão medidas pela função δ ), por
fim, c2 é o custo associado ao acerto de padrões na segunda fase de corte. Nestas condições, a
função
de
custo
que
Carvalho
e
Rodrigues
utilizaram
é
dada
por:
c perda ∑ T j x j + clam ∑ m j x j + c1 ∑ δ( x j ) + c2 m , onde x j é o número de vezes que o padrão
j∈J
j∈ J
j∈ J
j ∈ J é utilizado, m j é o número de bobinas intermediárias no padrão e m é o total de bobinas
intermediárias. Finalmente, o modelo que os autores formularam para o problema é escrito
como:
minimizar
c perda ∑ T j x j + clam ∑ m j x j + c1 ∑ δ( x j ) + c2 m
sujeito a:
dimin ≤ ∑ ai j x j ≤ dimax ; x j ≥ 0 e inteiro com i ∈ N e j ∈ J
j∈J
j∈ J
j∈ J
j∈J
Os autores efetuaram simplificações no modelo anterior, resolveram a relaxação contínua do
programa linear resultante, tomaram a solução arredondada para baixo e utilizaram a heurística
FFD para completar a demanda. Para construir um padrão viável (gerar uma coluna), os autores
reduziram o espaço de busca, construindo para cada item i ∈ N , todas as bobinas intermediárias
“homogêneas” (compostas por apenas um tipo de item). Assim, para cada i ∈ N , seja o
conjunto Ki dos índices das bobinas intermediárias homogêneas e mik o número de itens i na
bobina intermediária k, eles resolveram o seguinte problema clássico da mochila [26], onde πi é
um multiplicador Simplex, e yik é a variável da mochila que decide quantas bobinas
intermediárias de índice k ∈ Ki irão compor o padrão:
maximizar
sujeito a:
∑ ∑ ((πi + c perda l i )mik − clam ) yi k
i∈N k∈Ki
∑ ∑ (mik l i ) yik ≤ L ; yik ≥ 0 e inteiro com i ∈ N e
i∈N k∈Ki
k ∈ Ki
A abordagem de Carvalho e Rodrigues parece ser muito promissora, entretanto, os autores
“anularam” o poder combinatório do problema quando reduziram drasticamente o espaço de
1705
busca. Novamente podemos perceber que a dificuldade maior do problema é gerar um padrão
compartimentado.
4 A abordagem de Pereira para a Programação de Fitas Laminadas
No ano de 1993, Marcos Antonio Pereira apresentou sua dissertação de mestrado [27] (sob
orientação do Professor Miguel Taube da UNICAMP), onde descreveu um programa linear
misto (variáveis inteiras e reais) em que o objetivo é o de minimizar o custo pela utilização de
uma bobina e o custo pelo processo de laminação.
Pereira considerou que os itens de um subconjunto N − N * ⊂ N podem ser cortados a partir
de mais de um tipo de bobina do estoque (é dada a opção de decidir entre alguns tipos de aço),
onde N * constitui o subconjunto de índices que não admite esta possibilidade. O autor reuniu
os índices dos itens com compatibilidade para laminação em agrupamentos N s , s ∈ G . Cada
bobina r ∈ R do estoque pode atender um subconjunto Gr de agrupamentos N s , note que os
elementos de Gr não são índices, mas agrupamentos N s , estes por sua vez são conjuntos de
índices de itens com mesma compatibilidade para laminação. Assim, para cada item i ∈ N
existirá um único agrupamento N s , com i ∈ N s , de modo que, várias bobinas possam atender
os itens indexados por N s , este conjunto de bobinas é indexado por Rs . Os vários tipos de aço
são indexados por h = 1, ..., H. Considere cr o custo da bobina r ∈ R . Seja a variável inteira
mrs ≥ 0 , que contabiliza o número de bobinas intermediárias da bobina r ∈ R designadas ao
agrupamento N s e TLamrs o tempo de laminação de uma destas bobinas intermediárias. A


função de custo que Pereira modelou é dada por: ∑ cr yr + α ∑  ∑ TLamrs mrs  , onde yr é


r∈R
r∈R  N s ∈Gr

igual a 1 se a bobina r ∈ R foi escolhida, e igual a 0 no caso contrário. O parâmetro α é para
compatibilizar as unidades de custo das bobinas e de tempo de laminação das bobinas
intermediárias (ele mede a importância da laminação no processo). As restrições consideradas
por Pereira foram:


1. ∑  ∑ air l i  ≤ yr ( Lr − S1 − mrs S2 ) , para cada r ∈ R . A variável inteira air ≥ 0


N s ∈Gr  i∈N s

contabiliza o número de itens i cortados da boina r. A restrição determina que o total das
larguras dos itens cortados da bobina r ∈ R seja inferior à sua largura útil Lr − S1 − mrs S 2 ( Lr é
a largura da bobina r);
P
2. ∑ r air l i ≥ shi di , para cada i ∈ N * , tal que N s é o agrupamento em que i ∈ N s ( Pr é o
r∈Rs Lr
“peso” da bobina r). A variável de decisão uhi é igual a 1 se o tipo de aço h foi escolhido para
H
atender o item i ∈ N k , e igual a 0 no caso contrário, portanto, ∑ uhi = 1 para cada i ∈ N *
h =1
(somente um tipo de aço será escolhido para o item em questão). Observe que a quantidade
produzida do item i nunca será inferior a seu pedido;
P
3. ∑ r air l i ≥ vhi , para cada i ∈ N − N * , tal que N s é o agrupamento em que i ∈ N s . A
r∈Rs Lr
variável real vhi ≥ 0 mede a quantidade produzida do item i no tipo de aço h, portanto,
H
∑ vhi ≥ di para cada i ∈ N − N * (mais de um tipo de aço poderá ser escolhido para o item em
h =1
questão). Observe que a quantidade produzida do item i nunca será inferior a seu pedido;
1706
4. wrs Lmin ≤ ∑ air l i ≤ wrs M e (mrs − 1 + ε) Lmax ≤ ∑ air l i ≤ mrs Lmax , para cada r ∈ R e
i∈N s
i∈N s
N s ∈ Gr com TLamrs > 0 . A variável de decisão wrs é igual a 1 se a bobina r ∈ R foi escolhida
para atender o agrupamento N s ∈ Gr , e igual a 0 no caso contrário. Estas restrições possuem
relação com os tamanhos das bobinas intermediárias e com o tempo de laminação, onde
0 ≤ ε < 1 e M é um número grande.
Pereira relaxou restrições relacionadas com o tempo de laminação e com a designação de
tipos de aço alternativos (cada pedido passaria a ser atendido por um único tipo de aço). O autor
procurou descrever bounds para a solução de seu modelo e relatou dificuldades, pois, algumas
bobinas intermediárias possuíam larguras inferiores à largura mínima permitida ( Lmin ), além
disto, alguns pedidos não eram atendidos. Se observarmos bem, o modelo de Pereira não
contempla a compartimentação dos padrões, de modo que, as dificuldades relatadas eram
naturais de ocorrer.
5 A Heurística de Hoto-Arenales para o Corte de Bobinas de Aço
Em 1996, sob orientação do Professor Marcos Arenales da USP de São Carlos, Hoto apresentou
em sua dissertação de mestrado [14] um procedimento heurístico para o corte de bobinas de aço
baseado nas idéias da heurística de Ferreira-Neves-Castro (seção 2), porém, os itens são préprocessados em agrupamentos, viabilizando a geração de um padrão efetivamente factível.
Um importante aspecto é que as bobinas intermediárias (compartimentos) passaram a ser
construídas por meio do seguinte problema da mochila restrito:
maximizar
∑ λis ai
i ∈ Ns
sujeito a:
∑ l i ai ≤ Lmax e ∑ ai ≤ NF −1
i ∈ Ns
0 ≤ ai ≤
i ∈ Ns
Lrem di
; ai ≥ 0 e inteiro com i ∈ N s
P li
Na mochila anterior, λ is são coeficientes calculados a partir da demanda remanescente di ,
da largura l i e da dificuldade em laminar os itens de N s , Lmax é a largura máxima que uma
bobina intermediária pode assumir, Lrem é a largura remanescente de uma bobina do estoque,
cujo peso é P, finalmente ai é a variável.
Um grande problema na heurística de Hoto-Arenales é que ela valoriza bobinas
intermediárias de largura máxima, gerando padrões com perdas consideráveis, entretanto, há
algumas fitas que não necessitam de laminação e podem completar esta ociosidade no padrão.
Outra alternativa que foi sugerida [14] e [15] consiste em retirar itens das bobinas
intermediárias, que por um lado aumenta a ociosidade, mas por outro, permite construir uma
nova bobina intermediária.
6 Hoto-Arenales-Maculan e a abordagem de Geração de Colunas com Mochila
Compartimentada
Um problema muito incômodo na prática do corte de bobinas de aço, comum em muitos outros,
é a baixa demanda dos itens (figura 5). Tendo em vista a bordagem 1.5-dimensional de Haessler
[11] (seção 1), Hoto, Maculan e Arenales [16] em 1998, sugeriram um modelo que trata o
problema em questão via geração de colunas [05, 06] sob o enfoque 1.5-dimensional.
A abordagem não foi levada adiante para o corte de bobinas de aço, porém, motivou os
autores a explorarem o problema com geração de colunas. Naturalmente o grande entrave
consistiu na geração dos padrões compartimentados. Em 1999, Hoto, Arenales e Maculan [17]
descreveram uma primeira versão da mochila compartimentada, onde não era permitida a
replicação de compartimentos (não era permitido que uma mesma bobina intermediária
figurasse mais de uma vez no padrão). Os autores descreveram um branch-and-bound com boas
1707
soluções, porém, com tempo de processamento que comprometia a geração de colunas. Em
2000 Marques apresentou sua dissertação de mestrado [22], sob orientação do Professor
Arenales, cujo foco são heurísticas para a resolução de mochilas compartimentadas, e em 2001,
Hoto apresentou sua tese de doutoramento [19], sob orientação do professor Nelson Maculan da
COPPE – UFRJ, cujo tema é a aplicação de mochilas compartimentadas no corte de bobinas de
aço.
bobina de "peso" 10.000 Kg, com largura de 1.000 mm
item de demanda
500 Kg, com
largura de 100 mm
se cortado integralmente
da bobina, a produção
será 1.000 Kg (o dobro
de sua demanda)
Fig 5. Exemplo de baixa demanda no corte de bobinas de aço.
Para descrever uma Mochila Compartimentada Irrestrita, Hoto, Arenales, Maculan e
Marques consideraram para cada agrupamento N s , o conjunto Vs , s = 1, ..., q, dos
índices dos compartimentos (bobinas intermediárias) viáveis, de modo que, Vs ∩ Vs′ = ∅
para s, s′ = 1, K, k , s ≠ s′ . Seja ck , k ∈Vs , s = 1, ..., q, um custo por utilizar o
compartimento k, o modelo da mochila compartimentada irrestrita é dado por:




maximizar ∑  ( ∑ ui aik ) − ck  yk + L + ∑  ( ∑ ui aik ) − ck  yk

k∈V1  i∈N1
k∈Vq 

 i∈N q

sujeito a:
∑ ( ∑ l i aik + S2 ) yk + L + ∑ ( ∑ l i aik + S2 ) yk + S1 ≤ L
k∈V1 i∈N1
k∈Vq i∈N q
 yk 
 yk 

 Lmin ≤ ∑ l i aik + S 2 ≤ 
 Lmax , k ∈Vs , s = 1, ..., q
i∈N s
 yk + 1 
 yk + 1 
aik , yk ≥ 0 e inteiros, i ∈ N = N1 ∪ L ∪ N q , k ∈V = V1 ∪ L ∪ Vq
No modelo anterior a variável aik contabiliza o número de itens i no compartimento k. A
variável yk contabiliza o número de vezes que o compartimento k deve ser considerado na
mochila. O parâmetro ui está relacionado com os multiplicadores Simplex na abordagem de
geração de coluna [05,06], todavia, eles medem uma utilidade do item i na composição da
 y 
mochila. Por fim,  .  é a função menor inteiro maior ou igual a..., observe que  k  é
 yk + 1 
igual a 1 se yk > 0 e igual a 0 se yk = 0 .
Para resolver o modelo anterior, Hoto, Arenales, Maculan e Marques [19, 20, 24, 25]
construíram todos os compartimentos viáveis, utilizando o algoritmo de Yanasse-Soma [31]
para mochilas com restrição física de igualdade, em seguida resolveram uma mochila irrestrita
para decidir quais compartimentos viáveis integrariam o padrão. Os autores provaram que a
decomposição descrita obtém a solução ótima da compartimentação, desde que cada mochila
clássica do processo detecte uma solução ótima [19, 20]. Hoto [19] propôs substituir os valores
1708
das utilidades das mochilas resolvidas pelo algoritmo de Yanasse-Soma por bounds [26],
fornecendo soluções competitivas em qualidade e tempo [20].
Hoto usou mochilas compartimentadas para gerar padrões no corte de bobinas de aço sujeitas
a
laminação,
ele
adotou
n
m rj
i =1
k =1
cr
custos
associados
à
perda
de
aço
T jr = ( Lr − S1 ) − ( ∑ l i aijr ) − ( S2 ∑ ykjr ) numa bobina r do estoque, e custos ckjr associados à
laminação de uma bobina intermediária k definida por um padrão de corte compartimentado j
[19]. Na expressão de T jr , n é o número total de itens (fitas de aço), m rj é o número total de
bobinas intermediárias (compartimentos) na bobina r, e a variável ykjr contabiliza o número de
bobinas intermediárias k na bobina r, segundo o padrão compartimentado j. Hoto contabilizou o
número de bobinas do tipo r, cortadas segundo o padrão j, pela variável x rj , e admitiu um
estoque de bobinas limitado, considerando e r a disponibilidade de bobinas do tipo r, de modo
que modelo por ele proposto é dado por:
mrj

m pr 
r
r
minimizar ∑ ∑  c T j + ∑ (ckjr ykjr )  x rj

r =1 j =1 
k =1


m pr P
r r
sujeito a:
∑ ∑ r l i aij x j = di , i = 1, K, n
r =1 j =1 Lr
p1
1
≤ e1
∑ xj
j =1
O
M
pm
m
m
∑ xj ≤ e
j =1
x rj
≥ 0 e inteiro, j = 1, K, pr , r = 1, K, m
Uma solução inteira viável foi obtida por meio de uma heurística sugerida por Stadtler [29],
veja também [28] e [30]. A abordagem de geração de colunas com mochilas compartimentadas
de Hoto, Maculan e Arenales [16, 19] obteve soluções superiores em qualidade quando
comparada com a abordagem de Carvalho-Rodrigues [01, 02 ,03], que restringiu o espaço de
busca.
7 Marques-Arenales e a Mochila Compartimentada Restrita
O caso restrito da compartimentação de uma mochila [19, 22, 23, 24, 25] prevê as seguintes
condições adicionais:
1. a quantidade de cada item i que compõe a mochila deve ser limitada por di :
q
∑ ∑ aik yk ≤ di , i ∈ N = N1 ∪ L ∪ N q ;
s =1 k∈Vs
2. a quantidade de itens em cada compartimento k deve ser limitada por bk :
∑ aik ≤ bk , k ∈V = V1 ∪ L ∪ Vq , s = 1, ..., q;
i∈N s
3. a quantidade de compartimentos na mochila deve ser limitada por c:
q
∑ ∑ yk ≤ c ;
s =1 k∈Vs
Em sua dissertação, Marques [22] abordou o problema restrito da mochila
compartimentada, considerando apenas a adição da restrição 1. Três heurísticas gulosas
foram descritas por Marques [22, 25]:
1709
A heurística de decomposição de Marques-Arenales
Nesta heurística é construído um compartimento de largura máxima associado a cada
agrupamento. Destes compartimentos serão escolhidos aqueles que melhor montarão a mochila
compartimentada. Aqui, como na heurística de Hoto-Arenales (seção 5), pode haver ociosidade
no padrão que é eliminada com a adição de itens que não necessitam de laminação.
A heurística do melhor compartimento de Marques-Arenales
Semelhante a heurística anterior, ele visa a construção de compartimentos com larguras
adequadas, procurando evitar a ociosidade no padrão.
A heurística dos k-melhores compartimentos de Marques-Arenales
Consiste num aperfeiçoamento das heurísticas anteriores, de modo que, ao invés de construir
apenas um compartimento associado a cada agrupamento, constroem-se os k-melhores
compartimentos, isto pode ser feito por meio do algoritmo de Yanasse-Soma-Maculan [32] que
determinando as k-melhores soluções de uma mochila clássica.
Em sua tese [19], Hoto também descreveu uma heurística baseada na construção de todos os
compartimentos viáveis para a resolução de uma mochila compartimentada restrita, porém, a
variável yk , que contabiliza o número de ocorrências do compartimento de índice k na mochila,
é considerada binária, indicando que o compartimento em questão poderá figurar apenas uma
vez na mochila.
Atualmente estamos trabalhando numa abordagem de geração de colunas para resolver uma
mochila compartimentada restrita. Assim, ao utilizar geração de colunas no corte de bobinas de
aço, por exemplo, uma coluna será gerada por outra geração de colunas, isto é, teremos uma
geração de colunas embutida noutra. Este raciocínio é compatível com a abordagem de Eugene
Zaq que veremos a seguir.
8 Zaq e a abordagem de Geração de Linhas e Colunas
Em 2002, Eugene Zaq da empresa americana de desenvolvimento de softwares TietoEnator
Majiq, Inc. (Redmond, WA, USA), especializada no segmento industrial de papel, apresentou
dois trabalhos [33, 34] que abordaram o corte de bobinas de papel descrito por Haessler [08, 09]
(seção 1).
Zak considerou que as bobinas intermediárias (compartimentos) devem possuir suas larguras
limitadas entre um valor mínimo Lmin e um valor máximo Lmax , assim como feito no corte de
bobinas de aço. Para modelar o problema, ele distinguiu os padrões compartimentados em dois
momentos: na primeira fase de corte (os padrões são construídos para cortar as bobinas do
estoque) e na segunda fase de corte (os padrões são construídos para cortar bobinas
intermediárias). O autor introduziu a variável x1j ≥ 0 que contabiliza as ocorrências do padrão j
da primeira fase de corte, e xk2 ≥ 0 que contabiliza as ocorrências do padrão k da segunda fase
de corte. A quantidade de itens (bobinas intermediárias) do tipo k, cortadas do padrão j da
primeira fase de corte, é contabilizada por a1kj ≥ 0 , já a quantidade de itens (rolos de papel) do
tipo i, cortados do padrão k da segunda fase de corte, é contabilizada por aik2 ≥ 0 . O objetivo de
Zak foi simplesmente minimizar o total de bobinas do estoque cortadas para atender a demanda
di de cada item, tomando o cuidado de que a utilização de bobinas intermediárias na segunda
fase de corte não deve exceder a respectiva produção na primeira fase. O modelo que Zak
propôs é dado por:
minimizar
1 1
∑ akj x j
j
1710
sujeito a:
1 1
2
∑ akj x j ≥ xk , k = 1, ..., m
j
2 2
∑ aij x j ≥ di ; x1j , xk2 ≥ 0 e inteiros para todo j, k e i = 1, ..., n
j
Na modelagem de Zak, além de conhecermos todos itens i, necessitamos conhecer todas as
bobinas intermediárias (compartimentos) k. Zak efetuou a geração das colunas (dos padrões)
com o mesmo raciocínio que Hoto et al. [19, 20] (seção 6) empregou para resolver mochilas
compartimentadas. De fato, a geração dos padrões de Zak pode ser feita por uma mochila
compartimentada, cujos itens estão reunidos num único agrupamento, portanto, seus padrões
podem ser considerados compartimentados.
Zak, entretanto, considerou a situação em que o número de bobinas intermediárias não é
computável e sugeriu a geração simultânea de linhas e colunas (compartimentos e padrões), e
embora a cada passo do Simplex revisado [05, 06], saibamos gerar colunas desconhecidas, nada
sabemos sobre linhas desconhecidas. Assim, ele restringiu a busca de bobinas intermediárias,
gerando não mais que uma nova bobina intermediária a cada passo do Simplex. Na geração de
linhas e colunas simultâneas (bobinas intermediárias e padrões), Zak utilizou o seguinte
problema de otimização que gera uma bobina intermediária de largura Lk = ∑ l i aik2 + S2 a ser
i
π1k
1
πi2
e
são respectivamente os multiplicadores Simplex
utilizada a vezes no padrão j, onde
da primeira e segunda fase de corte (variáveis duais do modelo principal):
maximizar
1 1
2 2
k
sujeito a:
1
∑ πk akj + (∑ πi aij )a
i
1
2
1
∑ Lk akj + (∑ l i akj + S2 )a + S1 ≤ L
k
i
Lmin ≤ ∑ l i aij2 + S2 ≤ Lmax ; a1kj , aij2 , a1 ≥ 0 e inteiros
i
 L − S1 
Zak considerou a1 = 1, 2, K, 
 como um parâmetro a ser ajustado, e resolveu o
 Lmin 
modelo anterior como uma mochila clássica com a restrição adicional
Lmin ≤ ∑ l i aij2 + S2 ≤ Lmax .
i
Teoricamente, as limitações impostas por Zak restringiram as escolhas na geração das
bobinas intermediárias. Note que quando não existem novos padrões de corte envolvendo
apenas uma nova bobina intermediária, no mínimo duas novas bobinas intermediárias devem ser
incluídas num padrão da primeira fase de corte. Pode-se esperar que esta situação seja mais
provável no início do Simplex revisado, quando o número de bobinas intermediárias ainda é
escasso, por outro lado, à medida que o procedimento gera mais bobinas intermediárias, a
situação torna-se menos provável.
Considerações Finais
Neste trabalho iniciamos um texto de revisão sobre corte em duas ou mais fases. Fizemos a
descrição parcial de trabalhos da literatura que tratam de problemas de corte em duas fases.
Os primeiros trabalhos são os de Haessler que trata do corte de bobinas de papel e filme
plástico (seção 1), onde os itens não necessitam de pré-processamento (não precisam estar
agrupados). A seguir foi apresentado o problema do corte de bobinas de aço, estudado por
Ferreira-Neves-Castro (seção 2), Carvalho-Rodrigues (seção 3), Pereira (seção 4), HotoArenales-Maculan (seções 5 e 6) e Marques-Arenales (seção 7), cujos itens necessitam estar
agrupados segundo compatibilidades. Vimos que uma mochila compartimentada encontra um
padrão de um problema de corte unidimensional em duas fases (seção 6). O caso restrito desta
mochila não apresenta uma resolução elementar, sendo justificável o desenvolvimento de
1711
heurísticas (seção 7), tendo em vista sua aplicabilidade em problemas de corte que se passam
em duas fases. Por fim, vimos o trabalho de Zak (seção 8), que sugere um mecanismo de
geração de linhas e colunas simultâneas para o corte de bobinas de papel, onde uma linha
representa uma bobina intermediária (um compartimento) e uma coluna representa um padrão
de corte.
A noção de compartimentação de padrões pode ser aplicada em problemas de corte em duas
fases com ou sem restrições de agrupamento, por exemplo, o corte de bobinas de aço e de papel
respectivamente. Quando não há restrições quanto à compatibilidade de itens, basta considerar
um único agrupamento, e em vista deste fato, sugerimos a seguinte definição para Problemas de
Corte em duas Fases:
Corte em duas Fases
Um problema possui corte em duas fases quando seus padrões são compartimentados.
Padrões Compartimentados
Um padrão de corte é denominado compartimentado quando é necessário definir objetos
intermediários (compartimentos) a serem cortados dos objetos em estoque, neste caso os itens
serão cortados dos objetos intermediários.
Como contribuição, esperamos que este trabalho seja o início de um texto que possa servir
como um documento de consulta. Vale destacar que durante a elaboração deste texto surgiu a
idéia de se resolver mochilas compartimentadas restritas via geração de colunas, o que
esperamos ser uma contribuição futura significativa por abordar questões relevantes.
Agradecimentos
Agradecemos ao Professor Arenales pelos seus valiosos apontamentos, e pelas proveitosas
discussões durante a escrita deste texto. Agradecemos também aos revisores deste trabalho, que
em tarefa anônima, fizeram excelentes e importantes observações. O autor Fabiano Marques
contou com apoio da FAPESP, a quem agradecemos.
Bibliografia
[01] J. M. V. Valério de CARVALHO (1991). A two-phase cutting problem. Doctor Thesis,
University of Minho, Portugal. (in portuguese)
[02] J. M. V. Valério de CARVALHO and A. J. Guimarães RODRIGUES (1994). A computer
based interactive approach to a two-stage cutting-stock problem. INFOR, 32(4), 243-252.
[03] J. M. V. Valério de CARVALHO and A. J. Guimarães RODRIGUES (1995). An LP-based
approach to a two-stage cutting-stock problem. European Journal of Operational Research, 84,
580-589.
[04] J. S. FERREIRA, M. A. NEVES and P. F. CASTRO (1990). A two-phase roll cutting
problem. European Jounal of Operational Research, 44, 185-196.
[05] P. C. GILMORE and R. E. GOMORY (1961). A linear programming approach to the
cutting stock problem, Operations Research, 9(6), 849-859.
[06] P. C. GILMORE and R. E. GOMORY (1963). A Linear Programming Approach to the
cutting stock problem, parth II, Operations Research, 11(6), 863-888.
[07] P. C. GILMORE and R. E. GOMORY (1965). Multistage cutting stock problems of two
and more dimensions. Operations Research, 13(1), 94-120.
[08] R. W. HAESSLER (1968). An application of heuristic programming to a nonlinear
cutting-stock problem occurring in the paper industry. Unpublished Doctoral Dissertation, The
university of Michigan, Ann Arbor, USA.
[09] R. W. HAESSLER (1971). A heuristic programming solution to a nonlinear cutting-stock
problem. Management Science, 17(12), 793-802.
[10] R. W. HAESSLER (1975). Controlling cutting pattern changes in one dimensional trim
problems. Operations Research, 23(3), 483-493.
1712
[11] R. W. HAESSLER (1978). A procedure for solving the 1.5 - dimensional coil slitting
problem. AIIE Transactions, 10, 70-75.
[12] R. W. HAESSLER (1979). Solving the two-stage cutting-stock problem. Omega, The
International Journal of Management Science, 7(2), 145-151.
[13] R. W. HAESSLER (1980). A note on computational modifications to the Gilmore-Gomory
cutting stock algorithm. Operations Research, 28(4), 1001-1005.
[14] R. HOTO (1996). Optimization in the cut of the one-dimensional items with restrictions of
grouping. MSc. Dissertation, ICMC, USP, São Carlos, S.P., Brazil. (in portuguese)
[15] R. HOTO and M. ARENALES (1996). A one-dimensional cutting problem with restriction
of grouping and industrial applications. I ON PCE, IME-USP, São Paulo, S.P., Brazil. (in
portuguese)
[16] R. HOTO, N. MACULAN and M. N. ARENALES (1998). The steel roll cutting stock
problem with columns generation. XXX Brazilian Symposium of Operational Research,
Curitiba, P.R., Brazil, 267-268. (in portuguese)
[17] R. HOTO, M. N. ARENALES and N. MACULAN (1999). The compartmented knapsack
problem. Technical Report, Department of Mathematics, Center of Exact Sciences, State
University of Londrina, Londrina, P.R., Brazil. (in portuguese)
[18] R. HOTO, N. MACULAN and M. N. ARENALES (2000). A branch-and-bound for a
simplified version of the compartmented knapsack problem. XXXII Brazilian Symposium of
Operational Research, Viçosa, M.G., Brasil, 1824-1836 (in portuguese).
[19] R. HOTO (2001). The compartmented knapsack problem applied in steel roll cutting stock
problem. Doctor Thesis, COPPE/UFRJ, Engineering of Systems and Computation, Rio de
Janeiro, R.J., Brazil. (in portuguese)
[20] R. HOTO, N. MACULAN, M. N. ARENALES and F. P. MARQUES (2002). A new
procedure for the calculation of the compartmented knapsacks. Operational Research - APDIO,
22, 213-234. (in portuguese)
[21] R. HOTO, N. MACULAN, F. P. MARQUES and M. N. ARENALES (2003). A cut
problem with compartmented patterns. Operational Research – SOBRAPO. (to be published in
portuguese)
[22] F. P. MARQUES (2000). The compartmented knapsack problem. MSc. Dissertation,
ICMC, USP, São Carlos, S.P., Brazil. (in portuguese)
[23] F. P. MARQUES and M. N. ARENALES (2000). “The compartmented knapsack
problem.” XXXII Brazilian Symposium of Operational Research, Viçosa, M.G., Brasil, 803-816.
(in portuguese)
[24] F. P. MARQUES, M. N. ARENALES and R. HOTO (2002). The compartmented knapsack
problem: a review of the unrestrict and restrict cases. VI ON PCE. Campinas, S.P., Brasil.( in
portuguese)
[25] F. P. MARQUES and M. N. ARENALES (2002). The compartmented knapsack problem
and applications. Operational Research - SOBRAPO, 22(3), 285-304. (in portuguese)
[26] S. MARTELLO and P. TOTH (1990). Knapsack problems: algorithms and computer
implementations. John Wiley & Sons, Chichester.
[27] M. A. PEREIRA (1993). A mathematical approach for the cut problem and lamination of
ribbons of steel. MSc. Dissertation, UNICAMP, Campinas, São Paulo, Brazil. (in portuguese)
[28] K. C. POLDI (2003). Extensions of the cutting-stock problem. MSc. Dissertation, ICMC,
USP, São Carlos, S.P., Brazil. (in portuguese)
[29] H. STADTLER (1990). A one dimensional cutting-stock problem in the aluminium
industry and its solution. European Journal of Operational Research, 44, 209-223.
[30] G. WÄSCHER and T. GAU (1996). Heuristics for the integer one dimensional cuttingstock problem: a computacional study. OR Spektrum, 18, 131-144.
[31] H. H. YANASSE, N. Y. SOMA (1987). A new enumeration scheme for the knapsack
problem. Discrete Applied Mathematics, 18, 235-245.
[32] H. H. YANASSE, N. Y. SOMA and N. MACULAN (2000). An algorithm for determining
the k-best solutions of one-dimensional knapsack problem. Operational Research – SOBRAPO,
20(1), 117-134.
1713
[33] Eugene J. ZAK (2002). Modeling multistage cutting stock problems. European Journal of
Operations Research, 141, 313-327.
[34] Eugene J. ZAK (2002). Row and column generation technique for a multistage cutting
stock problem. Computers & Operations Research, 29, 1143-1156.
1714