Thiago Xavier Greccho

Aplicação de técnicas de decomposição em

problemas de corte de estoque

Dissertação de Mestrado

Pós-Graduação em Matemática

Instituto de Biociências, Letras e Ciências Exatas
Rua Cristóvão Colombo, 2265, 15054-000

São José do Rio Preto - SP - Brasil
Telefone: (17) 3221-2444 - Fax: (17) 3221-2445



Thiago Xavier Greccho1

Aplicação de técnicas de decomposição em
problemas de corte de estoque

Orientadora:
Profa. Dra. Maria do Socorro Nogueira Rangel

Universidade Estadual Paulista “Júlio de Mesquita Filho”
Instituto de Biociências, Letras e Ciências Exatas

Campus de São José do Rio Preto

São José do Rio Preto

2013

1t.xavier.g@gmail.com



Greccho, Thiago Xavier.

Aplicação de técnicas de decomposição em problemas de corte de estoque /

Thiago Xavier Greccho. – São José do Rio Preto: [s.n.], 2013.

85 f. : il. ; 30 cm.

Orientador: Maria do Socorro Nogueira Rangel

Dissertação (mestrado) - Universidade Estadual Paulista, Instituto de Bio-

ciências, Letras e Ciências Exatas

1. Pesquisa operacional. 2. Otimização matemática. 3. Problema de corte

de estoque. I. Rangel, Maria do Socorro Nogueira II. Universidade Estadual

Paulista, Instituto de Biociências, Letras e Ciências Exatas III. Título.

CDU - 519.8



Thiago Xavier Greccho

Aplicação de técnicas de decomposição em

problemas de corte de estoque

Dissertação apresentada para obtenção do título

de Mestre em Matemática, área de Análise

Aplicada, junto ao Instituto de Biociências,

Letras e Ciências Exatas da Universidade

Estadual Paulista “Júlio de Mesquita Filho”,

Campus de São José do Rio Preto.

Banca Examinadora

Profa. Dra. Maria do Socorro Nogueira Rangel
Professora Adjunto

UNESP - São José do Rio Preto - SP
Orientadora

Profa. Dra. Deisemara Ferreira
Professora Adjunto

UFTM - Uberaba - MG

Prof. Dr. Silvio Alexandre de Araujo
Professor Adjunto

UNESP - São José do Rio Preto - SP

São José do Rio Preto, 2013.



Aos meus pais, Claudemir e Iraclides.

A minha irmã Aline.

Aos meus amigos.

Dedico.



Agradecimentos

A Deus, pelo dom da vida.

Aos meus pais, Claudemir e Iraclides, e à minha irmã Aline, pelo amor, carinho,
dedicação e por estarem sempre ao meu lado me apoiando. Não existem palavras para
descrever o quão especial eles são em minha vida.

À minha professora orientadora Socorro Rangel, pela orientação e dedicação. Por
acreditar nesse trabalho. Obrigado pela compreensão e conselhos, que, com certeza, me
ajudaram e continuarão me ajudando no futuro.

Aos professores de pós-graduação: Profo. Dr. Sílvio Alexandre de Araújo, Profo.
Dr. Geraldo Nunes Silva, Profo. Dr. Cláudio Aguinaldo Buzzi, Profo. Dr. Adalberto
Spezamiglio, Profo. Dr. Ali Messaoudi pelos ensinamentos, atenção e colaboração. Aos
professores de graduação, em especial a Profa. Dra. Rita de Cássia Pavani Lamas, Profo.
Hermes Antonio Pedroso, Profo. Dr. Masayoshi Tsuchida, Profo. Dr. Alagacone Sri
Ranga, Profa. Dra. Cleonice Fátima Bracciali, Profo. Dr. Waldemar Donizete Bastos,
Profo Dr. Maurílio Boaventura e a Profa Dra Tatiana Miguel Rodrigues, que sempre me
estimularam a estudar.

A todos os meus colegas do IBILCE (UNESP - Campus de São José do Rio Preto - SP)
dos tempos de graduação, em especial aos amigos da matemática: Bárbara, Renato, “Nico”
(Douglas), Fernandinho, “Bracinho” (Rafael), Moreno, “Batata” (Vínicius), Tatiana Felix
e “Xupeta” (Rodolfo), pela amizade, pelos momentos de estudo e risada principalmente.
Também aos amigos de outros cursos ou que não cursamos nenhuma disciplina juntos:
“Tanabi” (Fernando), “Farofa” (Bruno), “Cabessa” (Paulo Roberto), “Virso” (Emerson),
“Pinda” (Leandro), “Emo” (Luiz), Miguel, Hector e “Se Foda” (Rafael), pela amizade e
momentos de distração, principalmente na quadra do IBILCE. Um agradecimento especial
ao amigo “Frota” (Rafael) pelo apoio no último ano de graduação do bacharelado, no
momento mais difícil em minha vida ele se mostrou um amigo que eu não conhecia.

A todos os amigos de pós-graduação, em especial ao Matheus, Diego, Augusto, Michelli,
Gislaine e Aneliza pela amizade, pelos momentos de estudos e conversas, pelas viagens a
congressos e eventos do tipo. Ao grupo de otimização do IBILCE, em especial ao Yagor
e a Juliana.

À amiga Bárbara Brandão, muito obrigado pela dedicação e apoio. Aos meus amigos
“Gordo” (Henrique), André, Jorge, Aline Fernanda, Vander, Alex, Fabrício, Fernando,
Onha, Sílvio e galera do “Bigodaun” e agregados pela amizade e apoio. Aos meus tios,
em especial ao Denilso, Ivone, Vera e Edgar. Aos meus primos, em especial ao Lucas,
Eduardo, Larissa, Bruno, Adriana e Vanessa. Aos meus avós: Irma, Cida e Roque.



Às pessoas que cuidaram da minha saúde durante esse trabalho, em especial as minhas
fisioterapeutas: Alexandra, Ana Paula, Geovanna, Lívia, Valéria, Jozicarla e Nanci, muito
obrigado pela dedicação.

A todos os funcionários do IBILCE que, direta ou indiretamente, contribuíram para
a realização deste trabalho.

À todas as pessoas que sempre torcem pelo meu sucesso e pela minha felicidade.

À CAPES pelo auxílio financeiro.



Problemas não são obstáculos,

mas oportunidades ímpares de superação e evolução.

(Maurício Rodrigues de Morais)

Quanto mais um homem se aproxima de suas metas,

tanto mais crescem as dificuldades.

(Goethe)



Resumo

Neste trabalho apresentamos métodos de decomposição para problemas de otimização
inteira que auxiliam no processo de geração de colunas aplicado ao problema de corte de
estoque bidimensional. É feita uma revisão de literatura sobre problemas considerando
o corte simultâneo de objetos (ciclos da serra). Visando a aceleração do método de ge-
ração de colunas, propomos uma técnica de decomposição para o problema de corte de
estoque com minimização de ciclos da serra que incorpora informações duais associadas
às restrições de ciclos da serra no subproblema pricing.

Palavras-chave: Problema de corte de estoque bidimensional. Ciclos da serra. Téc-
nicas de decomposição. Geração de colunas.



Abstract

In this paper we present decomposition methods for integer optimization problems
that will help the column generation process applied to the two-dimensional cutting stock
problem. It’s made a literature review about problems considering the simultaneous cutting
of objects (cycles saw). Seeking an acceleration in the generation column method, the
propose a decomposition technique for the cutting stock problem with minimization saw
cycles which incorporates dual information associated to saw cycles restrictions in the
pricing subproblem.

Keywords: Two-dimensional cutting stock problems. Saw cycles. Decomposition
technique. Column generation.



Lista de Figuras

1 Problema de corte de estoque bidimensional. . . . . . . . . . . . . . . . p. 34

2 Padrão de corte unidimensional. . . . . . . . . . . . . . . . . . . . . . . p. 35

3 Padrão de corte bidimensional. . . . . . . . . . . . . . . . . . . . . . . . p. 36

4 Padrão de corte homogêneo maximal bidimensional. . . . . . . . . . . . p. 37

5 Corte simultâneo de objetos . . . . . . . . . . . . . . . . . . . . . . . . p. 45

6 Padrão de corte na indústria têxtil . . . . . . . . . . . . . . . . . . . . p. 51

7 Pacote . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 55



Sumário

1 Introdução p. 13

2 Geração de coluna em otimização linear inteira p. 15

2.1 Princípio de decomposição de Dantzig-Wolfe . . . . . . . . . . . . . . . p. 15

2.2 O método de geração de colunas . . . . . . . . . . . . . . . . . . . . . . p. 18

2.3 Um exemplo ilustrativo . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 20

3 O problema de corte de estoque p. 31

3.1 O problema de corte de estoque unidimensional . . . . . . . . . . . . . p. 31

3.2 O problema de corte de estoque bidimensional . . . . . . . . . . . . . . p. 33

3.3 Geração de colunas aplicado ao PCE . . . . . . . . . . . . . . . . . . . p. 38

3.4 Aplicações do PCE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 40

3.5 Extensões do PCE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 41

4 O problema de ciclos da serra p. 44

4.1 Modelos matemáticos para o problema de ciclos da serra . . . . . . . . p. 46

4.2 Aplicação do PCE-C indústria têxtil . . . . . . . . . . . . . . . . . . . p. 50

4.3 Aplicação do PCE-C na indústria de metal . . . . . . . . . . . . . . . . p. 53

5 Solução do problema de ciclos da serra via geração de colunas p. 58

5.1 Técnica de decomposição para o PCE

unidimensional com redução de padrões . . . . . . . . . . . . . . . . . . p. 58

5.2 Técnica de decomposição para o PCE

bidimensional com redução de ciclos . . . . . . . . . . . . . . . . . . . . p. 62



6 Conclusão e perspectivas futuras p. 68

Anexo A Tipologias de classificação p. 70

A.0.1 Tipologia de Dyckhoff . . . . . . . . . . . . . . . . . . . . . . . p. 70

A.0.2 Tipologia de Wäscher, HauBner e Schumann . . . . . . . . . . . p. 74

Referências Bibliográficas p. 79



13

Capítulo 1

Introdução

A competitividade industrial tem estimulado o crescimento de estudos sobre como

melhorar o processo de produção, de forma a aumentar a produção e a reduzir cus-

tos. Pequenas melhorias podem trazer ganhos significativos e representar uma vantagem

importante na competição entre indústrias do mesmo setor. No processo de produção

de diversas indústrias, como por exemplo, móveis, metais, papel, têxtil, entre outras, é

necessário cortar peças maiores (objetos) em estoque (geralmente padronizadas) em peças

menores (itens) para satisfazer uma demanda pré-estabelecida. O problema de encontrar

a melhor maneira de fazer isso dá origem ao problema de corte de estoque. Muitos pro-

blemas desse tipo têm por intuito minimizar os custos de produção.

Em nosso trabalho, esses custos serão baseados no número de objetos utilizados no

atendimento da demanda e na produtividade da máquina de corte. Esses dois objetivos,

além de concorrem para redução do custo de produção, também contribuem com o conceito

atual de sustentabilidade, uma vez que a redução da matéria-prima utilizada significa a

diminuição no uso dos recursos naturais do nosso planeta. Este fato é bem evidente

na indústria moveleira. Aumentar a produtividade da máquina de corte contribui com

esse conceito em termos da redução de energia gasta pela máquina. A produtividade da

máquina de corte está diretamente ligada ao corte simultâneo de objetos. Para melhor

compreensão deste trabalho, é interessante que o leitor tenha conhecimento em álgebra

linear ([7] e [32]), e programação inteira ([1],[44], [9] e [59]).

Neste trabalho propomos uma abordagem para resolver o problema de corte de es-

toque bidimensional baseado no método de geração de colunas proposto por Gilmore e

Gomory [27, 28, 29] e por Vanderbeck [56]. Essa abordagem envolve a decomposição do

problema original, de forma a incorporar informações duais associadas ao corte simultâneo

de objetos no subproblema pricing.



1 Introdução 14

Nossa pesquisa está estruturada da seguinte forma: No Capítulo 2, apresentamos o

princípio de decomposição de Dantzig-Wolfe aplicado ao problema de otimização linear

inteira, que servirá de base para a aplicação do método de geração de colunas, também

exposto no mesmo capítulo. Ainda no Capítulo 2, apresentamos um exemplo numérico

para exemplificar a teoria discutida.

No Capítulo 3, definimos o problema de corte de estoque, apresentamos modelos

matemáticos para esses problemas e definições que servem de alicerce para os modelos.

Discutimos o método de geração de colunas aplicado aos problemas de corte de estoque

e, por fim, faremos uma breve revisão bibliográfica sobre alguns trabalhos que tratam do

problema de corte de estoque.

No Capítulo 4, discutimos o conceito de ciclos da serra. Apresentamos algumas for-

mulações matemáticas para o problema de corte de estoque que aborda a redução de ciclos

da serra. Analisamos alguns trabalhos que apresentam problemas diretamente ligados ao

o número de preparo da máquina de corte.

No Capítulo 5, apresentamos a abordagem proposta em [56] para resolver um problema

de corte de estoque unidimensional com objetivo de redução do número de padrões de

corte. Apresentamos um método baseado nesse para resolver o problema de corte de

estoque bidimensional que visa minimizar o número de ciclos da serra e objetos cortados.

No Capítulo 6, apresentamos as conclusões sobre o nosso trabalho e fazemos algumas

considerações e propostas para a continuidade do mesmo.



15

Capítulo 2

Geração de coluna em otimização
linear inteira

De modo geral, os métodos de decomposição são utilizados para resolver um problema

através da resolução de uma sequência de problemas de menor dimensão. Tais métodos

de decomposição são aplicados não só para resolver problemas com grandes dimensões

(os quais não seriam resolvidos facilmente por outros métodos), mas também podemos

utilizar esses métodos para desenvolver algoritmos heurísticos [6].

Neste capítulo apresentaremos um método de decomposição para problemas de pro-

gramação linear inteira, desenvolvido por Dantzig e Wolfe [14] no início da década de

1960. Com o uso desta técnica podemos aplicar um procedimento de geração de colunas

que foi desenvolvido por Gilmore e Gomory [27, 28, 29], que será discutido na seção 2.2 e

que servirá de base para o desenvolvimento do nosso trabalho.

2.1 Princípio de decomposição de Dantzig-Wolfe

Consideremos o problema de programação linear inteira na forma padrão:

ZPI = min cx (2.1)

s.a

Ax = b (2.2)

x ≥ 0, inteiro, (2.3)



2.1 Princípio de decomposição de Dantzig-Wolfe 16

em que A, uma matriz m × n, c um vetor n × 1, b um vetor m × 1, são conhecidos e a

variável de decisão x é um vetor n× 1 inteiro.

Podemos particionar a matriz A e o vetor b como:

A =

(
A1

A2

)
e b =

(
b1

b2

)
,

em que A1 é uma matriz m1 × n, A2 é uma matriz m2 × n, b1 é um vetor m1 × 1 e b2 é

um vetor m2 × 1, com m1 +m2 = m.

O conjunto de restrições (2.2) pode ser reescrito como (2.4) - (2.5).

A1x = b1 (2.4)

A2x = b2 (2.5)

Definindo o conjunto X = {x ∈ Z
n : A2x = b2} �= ∅. Assim, o problema de progra-

mação linear inteiro (PI) pode ser escrito como (2.6) - (2.9).

ZPI−P1 = min cx (2.6)

s.a

A1x = b1 (2.7)

x ∈ X (2.8)

x ≥ 0, inteiro. (2.9)

As restrições (2.7) serão chamadas de restrições gerais e as restrições (2.8) que geral-

mente têm uma estrutura especial, serão chamadas de restrições especiais ou de acopla-

mento [18]. O princípio de decomposição de Dantzig-Wolfe [14] trabalha com essas res-

trições separadamente. O conjunto de restrições gerais definirá o problema principal, que

é chamado de problema mestre. Por conseguinte, o conjunto de restrições especiais definirá

um subproblema. Os dois problemas serão resolvidos alternadamente, sempre trocando

informações entre eles, conforme descrito na seção 2.2.

Consideremos que v1, v2, . . . , vp são os p pontos extremos de X e r1, r2, . . . , rp são os q

raios extremos de X. Como o conjunto X é um conjunto convexo, então qualquer ponto

de X pode ser escrito como combinação convexa dos pontos extremos de X, mais uma



2.1 Princípio de decomposição de Dantzig-Wolfe 17

combinação não negativa dos raios extremos de X, ou seja,

X =

{
x ∈ Z

n
+ : x =

p∑
i=1

viλi +

q∑
j=1

rjμj,

p∑
i=1

λi = 1, λi ∈ {0, 1}, ∀i, μj ∈ Z+, ∀j
}

(2.10)

Se substituirmos X definido de acordo com (2.10) em (2.6) - (2.9), obtemos uma nova

formulação para o problema (PI), dada por (2.11) - (2.15).

ZPM1 = min

p∑
i=1

(cvi)λi +

q∑
j=1

(crj)μj (2.11)

s.a
p∑

i=1

(A1vi)λi +

q∑
j=1

(A1rj)μj = b1, (2.12)

p∑
i=1

λi = 1, (2.13)

λi ∈ {0, 1}, i = 1, . . . , p, (2.14)

μj ∈ Z+, j = 1, . . . , q. (2.15)

As variáveis de decisão do problema reformulado são as variáveis λi e μj. A restrição

(2.13) é chamada de restrição de convexidade e a nova formulação (2.11) - (2.15) é o

problema mestre. A formulação do problema mestre (PM1) é equivalente à formulação

do problema original (PI), no sentido em que qualquer solução factível em termos das

variáveis do problema mestre pode ser transcrita numa solução factível para o problema

original.

Para simplificar, doravante vamos considerar X como sendo fechado, isto é, não pos-

suindo raios extremos.. Assim, o problema mestre (PM1) é dado por (2.16) - (2.19).

ZPM = min

p∑
i=1

(cvi)λi (2.16)

s.a
p∑

i=1

(A1vi)λi = b1, (2.17)

p∑
i=1

λi = 1, (2.18)

λi ∈ {0, 1}, i = 1, . . . , p. (2.19)



2.2 O método de geração de colunas 18

Apesar do problema (PM) ser em geral um problema mais simples que o original (PI),

justamente por possuir um número menor de restrições (m1 + 1 restrições, apenas as de

acoplamento (2.17) e a de convexidade (2.18)), algumas dificuldades são encontradas para

resolver o problema (PM), como por exemplo, o fato das variáveis de decisão λi serem

binárias e o elevado número de pontos extremos, principalmente quando se trata de um

problema de grande porte. O alto número de pontos extremos torna inviável a enumeração

explícita de todos os pontos extremos, para determinar a solução ótima do problema. Para

contornar essas dificuldades podemos fazer a relaxação linear das variáveis λi, isto é, as

variáveis λi podem assumir valores reais entre 0 e 1, dando origem ao problema (PM)

relaxado que será formado pelas expressões (2.16) - (2.18) e (2.20), e em seguida resolver

o problema (PM) relaxado utilizando o método de geração de colunas.

0 ≤ λi ≤ 1, i = 1, . . . , p. (2.20)

Para resolver o problema (PM) relaxado utilizando geração de colunas, considere-

mos inicialmente o problema mestre com um subconjunto restrito de variáveis, que é de-

nominado problema mestre restrito (PMR). Em cada iteração, o problema será resolvido

levando em conta apenas às variáveis do (PMR) produzindo uma solução ótima apenas

com as mesmas variáveis. Entretanto, para a solução do problema original é necessário

considerar todas as variáveis e colunas possíveis. Assim, é preciso analisar também todos

os pontos extremos do conjunto X que não fazem parte do (PMR). Caso existam pontos

extremos atrativos, as variáveis e colunas associadas a esses pontos, devem ser incluídas

ao (PMR) e o problema ser novamente otimizado. Esse processo é repetido até que não

haja mais colunas atrativas para serem incluídas ao (PMR).

2.2 O método de geração de colunas

Seja B uma matriz inversível que está associada à solução básica ótima do problema

(PMR). Suponha π = (π1, π2, . . . , πm1) e σ variáveis associadas ao conjunto das m1 + 1

primeiras restrições e da restrição de convexidade do problema (PMR), respectivamente.

Assim, a solução dual ótima é o vetor dado por (2.21).



2.2 O método de geração de colunas 19

cBB
−1 = Π = (π1, π2, . . . , πm1 , σ) = (π, σ). (2.21)

Em (2.21), cB é o vetor que representa o custo das variáveis que pertence à base. O

custo reduzido de uma variável não-básica é dado por ĉj = cj− cBB
−1Aj

1. As colunas que

correspondem aos pontos x ∈ X tem a forma (2.22).

(
A1v

1

)
(2.22)

Para uma variável x ∈ X não-básica associada a uma coluna do tipo (2.22), a ex-

pressão do custo reduzido é dado por (2.23) [9].

cj − cBB
−1Aj

1 = cv − (π1, π2, . . . , πm1) ∗ A1v − σ =

= cv − π ∗ A1v − σ = (2.23)

= (c− πA1)v − σ.

Analisaremos se algum ponto do conjunto X é atrativo para ser incluído no problema

mestre restrito. Caso haja mais que um, selecionaremos o ponto que tem o custo reduzido

mais atrativo. Essa seleção é feita em relação à solução ótima atual do problema mestre

restrito. A seleção de um ponto extremo pode ser feita resolvendo (2.24) - (2.26).

min (c− πA1)v − σ (2.24)

s.a

v ∈ X, (2.25)

v ≥ 0, inteiro. (2.26)

O problema (2.24) - (2.26) é denominado subproblema pricing. A solução ótima do

subproblema pricing corresponde a um ponto extremo do conjunto X. Se o subproblema

pricing apresentar uma solução ótima menor do que zero (< 0), existe uma variável

atrativa e a coluna associada a essa variável é adicionada ao problema mestre restrito,

sendo candidata a entrar na base. Caso contrário, quando o subproblema pricing apre-

sentar uma solução ótima maior ou igual à zero (≥ 0), nenhum ponto do conjunto X é

atrativo e assim a solução atual do problema mestre restrito é ótima, mas pode não ser

inteira e, assim, não ser solução ótima para o problema mestre original (PM), uma vez



2.3 Um exemplo ilustrativo 20

que o método de geração de colunas foi aplicado ao problema mestre relaxado. Métodos

heurísticos são utilizados para encontrar uma solução inteira para o problema (PM). Na

seção 3.3, discutiremos alguns trabalhos da literatura que apresentam métodos heurísticos

para obter uma solução inteira para os problemas de corte de estoque, que também serão

apresentados e discutidos no capítulo 3, como, por exemplo, [27], [28], [45] e [57] .

2.3 Um exemplo ilustrativo

Nesta seção iremos apresentar um exemplo numérico da aplicação do método de ge-

ração de coluna aplicado a um problema de programação linear inteira.

Exemplo 2.3.1. Considere o problema de programação linear contínua:

min x1 + x2 + x3

s.a

x1 + x2 = 2,

x1 + x3 = 1,

x1, x2, x3 ∈ Z+.

(2.27)

Para aplicarmos o princípio de decomposição de Dantzig-Wolfe, tomemos o conjunto

X da forma (2.28).

X =
{
x = (x1, x2, x3) ∈ Z

3
+ : x1 + x3 = 1 e x1, x2, x3 ≥ 0

}
. (2.28)

Desse modo temos c = (1 1 1) o vetor que representa os custos de cada variável, A1 =

(1 1 0) a matriz que representa a restrição geral, A2 = (1 0 1) a matriz que representa a

restrição de acoplamento., b1 = 2 e b2 = 1.

Sejam vi, i = 1, . . . , p os vértices de X e rj, j = 1, . . . , q os raios extremos de X.

vi =

⎛⎜⎜⎝
vi1

vi2

vi3

⎞⎟⎟⎠ i = 1, . . . , p e rj =

⎛⎜⎜⎝
rj1

rj2

rj3

⎞⎟⎟⎠ , j = 1, . . . , q.



2.3 Um exemplo ilustrativo 21

Assim, o problema mestre para o problema (2.27) é dado pelas expressões (2.29) -

(2.33).

min

p∑
i=1

(vi1 + vi2 + vi3)λi +

q∑
j=1

(rj1 + rj2 + rj3)μj (2.29)

s.a
p∑

i=1

(vi1 + vi2)λi +

q∑
j=1

(rj1 + rj2)μj = 2, (2.30)

p∑
i=1

λi = 1, (2.31)

λi ∈ {0, 1}, i = 1, . . . , p, (2.32)

μj ∈ Z+, j = 1, . . . , q. (2.33)

A relaxação para o problema mestre (2.29) - (2.33) é obtida substituindo as restrições

(2.32) e (2.33) pelas expressões (2.34) e (2.35), respectivamente.

λi ≥ 0, i = 1, . . . , p. (2.34)

μj ≥ 0, j = 1, . . . , q. (2.35)

Considerando que nenhuma solução básica factível é conhecida para o problema mestre,

portanto, utilizaremos o método simplex das duas fases com geração de colunas para en-

contrar uma solução básica factível inicial. Para mais detalhes sobre esse método ver

[1].

FASE I

Consideremos assim o problema mestre relaxado artificial que é dado por (2.36) -

(2.41).



2.3 Um exemplo ilustrativo 22

ξ = min g1 + g2 (2.36)

s.a
p∑

i=1

(vi1 + vi2)λi +
1∑

j=1

(rj1 + rj2)μj + g1 = 2, (2.37)

p∑
i=1

λi + g2 = 1, (2.38)

λi ≥ 0, i = 1, . . . , p, (2.39)

μj ≥ 0, j = 1, . . . , q, (2.40)

g1, g2 ≥ 0. (2.41)

Desse modo, para a seguir com o método simplex da duas fases. O problema mestre

artificial restrito inicial (PM-1) é formado pelas expressões (2.42) - (2.45).

ξ = min g1 + g2 (2.42)

s.a

g1 = 2, (2.43)

g2 = 1, (2.44)

g1, g2 ≥ 0. (2.45)

FASE I - Iteração 1

Na primeira iteração, a matriz básica factível inicial B é formada pelas colunas re-

lativas às variáveis g1 e g2, nesse caso B = I2. O custo básico cB, relacionado com as

variáveis que estão na base, é dado por cB = (1 1)T . As variáveis xN que não pertencem

à base têm custo zero. E o vetor de recursos b é dado por b = (2 1)T . Desse modo, uma

solução básica para o problema (PM-1) é dado por (2.46) com solução corrente ξ dado por

(2.47).

x̂B = B−1 b =

(
2

1

)
e x̂N = 0 (2.46)



2.3 Um exemplo ilustrativo 23

ξ = 3. (2.47)

A variável dual π = (π1 π2) referente às restrições (2.43) e (2.44) é dada pela expressão

(2.48).

π = (π1 π2) = cTB B−1 = cTB I2 = (1 1). (2.48)

O cálculo dos custos ĉN das variáveis não básicas é dado por (2.49).

ĉN =

⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩

ci − π Ai = 0− (1 1)

(
vi1 + vi2

1

)
= −vi1 − vi2 − 1 com i associado a λi,

cj − π Aj = 0− (1 1)

(
rj1 + rj2

0

)
= −ri1 − ri2 com j associado a μj.

(2.49)

Desse modo, após os cálculos realizados, o subproblema pricing (SP-1) relativo ao

problema (PM-1) é dado por (2.50) - (2.52).

γ = min −v1 − v2 − 1 (2.50)

s.a

v1 + v3 = 1, (2.51)

v1, v2, v3 ≥ 0. (2.52)

Para v1 = 1 e v2 = v3 = 0 as restrições do problema (SP-1) são satisfeitas, logo

v1 = (1 0 0)T é um vértice de X. Esse vértice fornece γ = −1 < 0. Como γ < 0 se

a coluna (2.53) associada à variável λi entrasse na base do problema (PM-1) o valor da

função objetivo ξ melhoraria.

(
1 + 0

1

)
=

(
1

1

)
. (2.53)



2.3 Um exemplo ilustrativo 24

Entretanto, note que se v2 −→ +∞ então γ −→ −∞, isto é, v2 é ilimitado superior-

mente. Passaremos, assim, a determinar o raio extremo associado. Para isso, é necessário

escrever o todas as coordenadas do vértice v1 em relação a sua segunda coordenada v2 da

seguinte forma:

⎛⎜⎜⎝
v1

v2

v3

⎞⎟⎟⎠ =

⎛⎜⎜⎝
1

0

0

⎞⎟⎟⎠ +

⎛⎜⎜⎝
0 v2

1 v2

0 v2

⎞⎟⎟⎠ . (2.54)

Logo, r1 = (0 1 0)T é um raio extremo de X, associado a variável μ1. Calculemos em

(2.55) o custo reduzido da variável μ1.

ĉμ1 = 0− π r1 = 0− π

(
r11 + r12

0

)
= −(1 1)

(
0 + 1

0

)
= −1 < 0. (2.55)

Como ĉμ1 < 0 então a variável μ1 é candidata a entrar na base com a coluna associada

Aμ1 = (1 0)T . Para decidir que variável sai da base do problema (PM-1) calcularemos em

(2.56) à direção simplex y e em (2.57) o tamanho do passo ε̂, que vai decidir que variável

sai da base.

y = B−1 Aμ1 = I2

(
1

0

)
=

(
1

0

)
. (2.56)

ε̂ = min

{
x̂Bi

yi
: yi ≥ 0

}
=

{
x̂B1

y1

}
=

{
2

1

}
= 2. (2.57)

Assim, a variável g1 sai da base. Nessa iteração foi gerada a coluna Aμ1 = (1 0)T que

deve ser incluída no problema (PM-1), dando origem a um novo problema mestre restrito

(PM-2), dado pelas expressões (2.58) - (2.61).



2.3 Um exemplo ilustrativo 25

ξ = min g1 + g2 (2.58)

s.a

μ1 + g1 = 2, (2.59)

g2 = 1, (2.60)

μ1, g1, g2 ≥ 0. (2.61)

FASE I - Iteração 2

A matriz básica factível B para o problema (PM-2) é formada pelas colunas relativas

as variáveis μ1 e g2, que nesse caso também é a matriz identidade I2. O vetor custo básico

cB é dado por cB = (0 1)T . Dessa forma temos a solução básica para o problema (PM-2)

dada por (2.62), com solução corrente ξ dado por (2.63).

x̂B =

(
2

1

)
e x̂N = 0 (2.62)

ξ = 1. (2.63)

Nessas condições temos os seguintes valores:

π = (π1 π2) = (0 1). (2.64)

ĉN =

⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩

ci − π Ai = 0− (0 1)

(
vi1 + vi2

1

)
= −1 com i associado a λi,

cj − π Aj = 0− (0 1)

(
rj1 + rj2

0

)
= 0 com j associado a μj.

(2.65)



2.3 Um exemplo ilustrativo 26

O subproblema pricing (SP-2) relativo ao problema (PM-2) é dado pelas expressões

(2.66) - (2.68).

γ = min −1 (2.66)

s.a

v1 + v3 = 1, (2.67)

v1, v2, v3 ≥ 0. (2.68)

Para v1 = 1 e v2 = v3 = 0 temos que as restrições do problema (SP-2) são satisfeitas,

e como já mencionado na iteração anterior v1 = (1 0 0)T é vértice de X associado a

variável λi. Como v1 e v3 são limitadas e v2 não altera o valor da função objetivo γ, isto

é, v1 é vértice ótimo de X para a função objetivo γ atual. Logo, a coluna Aλ1 = (1 1)T

associada a variável λ1 é candidata a entrar na base.

Os cálculos que decidem a possível variável que sai da base procedem da seguinte

maneira:

y = B−1 Aλ1 = I2

(
1

1

)
=

(
1

1

)
. (2.69)

ε̂ = min

{
x̂B1

y1
,
x̂B2

y2

}
=

{
2

1
,
1

1

}
=

1

1
= 1. (2.70)

Dessa forma a variável g2 sai da base. A coluna Aλ1 = (1 1)T é gerada para o

problema (PM-2), dando origem a um outro problema mestre restrito o (PM-3) que é

dado por (2.71) - (2.74).



2.3 Um exemplo ilustrativo 27

ξ = min g1 + g2 (2.71)

s.a

λ1 + μ1 + g1 = 2, (2.72)

λ1 + g2 = 1, (2.73)

λ1, μ1, g1, g2 ≥ 0. (2.74)

FASE I - Iteração 3

Nessa iteração a matriz básica inicial factível B, dada por (2.75), para o problema

(PM-3) é formada pelas colunas relativas as variáveis μ1 e λ1, isto é, na base não existem

mais variáveis artificiais.

B =

(
1 1

0 1

)
. (2.75)

O vetor custo básico cB é dado por cB = (0 0)T . Assim a solução básica para o

problema (PM-3) é dada por (2.76), com solução corrente ξ dado por (2.77).

x̂B =

(
1

1

)
e x̂N = 0 (2.76)

ξ = 0. (2.77)

Nessas condições temos os seguintes valores:

π = (π1 π2) = (0 0). (2.78)



2.3 Um exemplo ilustrativo 28

ĉN =

⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩

ci − π Ai = 0− (0 0)

(
vi1 + vi2

1

)
= 0 com i associado a λi,

cj − π Aj = 0− (0 0)

(
rj1 + rj2

0

)
= 0 com j associado a μj.

(2.79)

O subproblema pricing (SP-3) relativo ao problema (PM-3) é dado por (2.80) - (2.82).

γ = min 0 (2.80)

s.a

v1 + v3 = 1, (2.81)

v1, v2, v3 ≥ 0. (2.82)

Como γ = 0 para o problema (SP-3), logo a base atual está associada ao valor ótimo

do problema artificial (2.36) - (2.41). E como a base não possui variáveis artificiais então

a base atual é uma base factível para o problema mestre original relaxado (2.29) - (2.31),

(2.34) e (2.35).

FASE II

Nesta fase iremos trabalhar diretamente com o problema mestre original relaxado

(2.29) - (2.31), (2.34) e (2.35).

FASE II - Iteração 1

De acordo com a FASE I do método simplex das duas fases com geração de colunas,

uma matriz básica inicial factível B, para o problema mestre original relaxado é formada

pelas colunas associadas as variáveis μ1 e λ1 e é dado por (2.75). O custo básico cB é

dado por cB = (cr1 cv1). Os valores de cr1 e cv1 são calculados da seguinte forma:



2.3 Um exemplo ilustrativo 29

c r1 = (1 1 1)

⎛⎜⎜⎝
0

1

0

⎞⎟⎟⎠ = 1. (2.83)

c v1 = (1 1 1)

⎛⎜⎜⎝
1

0

0

⎞⎟⎟⎠ = 1. (2.84)

Assim, o problema mestre restrito (PMO-1) relativo ao problema mestre original re-

laxado (2.29) - (2.31), (2.34) e (2.35) é dado por (2.85) - (2.88).

Z = min λ1 + μ1 (2.85)

s.a

λ1 + μ1 = 2, (2.86)

λ1 = 1, (2.87)

λ1, μ1 ≥ 0. (2.88)

A solução básica para o (PMO-1) é dada por (2.89) e a solução corrente por (2.90).

x̂B =

(
1

1

)
e x̂N = 0 (2.89)

Z = 2. (2.90)

O valor dual é dado por (2.91) e os custos relativos por (2.96).

π = (π1 π2) = (1 0). (2.91)



2.3 Um exemplo ilustrativo 30

ĉN =

⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩

ci − π Ai = (1 1 1)

⎛⎜⎜⎝
vi1

vi2

vi3

⎞⎟⎟⎠− (1 0)

(
vi1 + vi2

1

)
= vi3 com i associado a λi,

cj − π Aj = (1 1 1)

⎛⎜⎜⎝
rj1

rj2

rj3

⎞⎟⎟⎠− (1 0)

(
rj1 + rj2

1

)
= rj3 com j associado a μj.

(2.92)

Dessa forma o subproblema pricing (SPO-1) é dado por (2.93) - (2.95).

γ = min v3 (2.93)

s.a

v1 + v3 = 1, (2.94)

v1, v2, v3 ≥ 0. (2.95)

O valor ótimo para o problema (SPO-1) é γ = 0 ≥ 0 qualquer que seja o ponto ótimo

para o problema. Assim sendo, a solução do problema mestre restrito (PMO-1) (2.85) -

(2.88) também é ótima para o problema mestre relaxado (2.29) - (2.31), isto é, a solução

ótima do problema mestre relaxado é μ1 = 1 associado ao raio extremo r1 = (0 1 0)T e

λ1 associado ao vértice v1 = (1 0 0)T . Em termos das variáveis originais:

⎛⎜⎜⎝
x1

x2

x3

⎞⎟⎟⎠ = μ1 r
1 + λ1 v

1 = 1

⎛⎜⎜⎝
0

1

0

⎞⎟⎟⎠ + 1

⎛⎜⎜⎝
1

0

0

⎞⎟⎟⎠ =

⎛⎜⎜⎝
1

1

0

⎞⎟⎟⎠ . (2.96)

O valor ótimo é Z∗ = 2. Como a solução para o problema mestre original relaxado

(que é equivalente a problema original relaxado) é inteira, então essa solução também é

solução ótima do problema original.



31

Capítulo 3

O problema de corte de estoque

O procedimento de geração de colunas para o problema de corte de estoque foi pi-

oneiramente estudado nos trabalhos de Gilmore e Gomory em 1961 e 1962, [27] e [28]

respectivamente. Nesses trabalhos os autores formularam o problema de corte de estoque

unidimensional, propuseram para esta formulação uma relaxação linear e utilizaram o pro-

cedimento de geração de colunas para resolver o problema relaxado, obtendo uma solução

aproximada para o problema original.

Neste capítulo, definimos o problema de corte de estoque, fazemos algumas definições

necessárias para a formulação desses problemas e apresentamos alguns modelos matemáti-

cos para o problema de corte de estoque. Na seção 3.3 faremos uma adaptação do método

de geração de colunas apresentado na seção 2.2, para o problema de corte de estoque. E

por fim, nas seções 3.4 e 3.5 discutimos alguns trabalhos envolvendo estes problemas.

3.1 O problema de corte de estoque unidimensional

Motivado pelo plano econômico soviético, o matemático e economista soviético Leonid

Vitaliyevich Kantorovich, publicou, em 1939, [33] em um impresso da Universidade de

Leningrado (atualmente Universidade de São Petersburgo, na antiga União Soviética, a-

tual Rússia), um trabalho com modelos matemáticos de programação linear para a organi-

zação e planejamento da produção. Neste trabalho é apresentada também uma discussão

do sentido econômico dos problemas e métodos de solução para os mesmos. Entre os

problemas discutidos em [33] encontra-se o problema de corte de estoque unidimensional.



3.1 O problema de corte de estoque unidimensional 32

Esse trabalho permaneceu desconhecido por muitos anos pelos pesquisadores ocidentais,

em virtude dos entraves político-ideológicos ocorridos durante a Guerra Fria. Somente

nos anos 1960 o trabalho foi publicado em inglês na revista Management Science.

O problema de corte de estoque unidimensional pode ser definido da seguinte maneira

[46]: considere disponível em estoque um número K, suficientemente grande, de objetos

(bobinas, barras, etc.) de comprimento L e um conjunto de m itens, cada item tendo

demanda conhecida bi, e de comprimento li, em que li ≤ L, i = 1, . . . ,m. O problema

consiste em como cortar os objetos de forma a atender a demanda usando o menor número

possível de objetos.

Para apresentar o modelo matemático atribuído a Kantorovich [8, 10], definimos o

seguinte conjunto de variáveis aij como sendo o número de vezes que o item i é cortado

no objeto j, i = 1, . . . ,m e j = 1, . . . , K. E as variáveis λj, que recebem valor 1, se o

objeto j é cortado e zero, caso contrário. Assim, temos a formulação (3.1) - (3.5).

ZKan = min
K∑
j=1

λj (3.1)

s.a
K∑
j=1

aij ≥ bi, i = 1, . . . ,m, (3.2)

m∑
i=1

liaij ≤ Lλj, j = 1, . . . , K, (3.3)

λj ∈ {0, 1}, j = 1, . . . , K, (3.4)

aij ∈ Z+, i = 1, . . . ,m, j = 1, . . . , K. (3.5)

A função objetivo (3.1) minimiza o número total de objetos cortados. O conjunto de

restrições (3.2) garante que a demanda dos itens será atendida, permitindo o excesso de

produção. O conjunto de restrições (3.3) garante que se um objeto j é usado (λj = 1),

então as restrições físicas do objeto devem ser respeitadas. As restrições (3.4) e (3.5)

definem os domínios das variáveis.

O modelo matemático para o problema de corte de estoque mais lembrado na li-

teratura é o modelo apresentado por Gilmore e Gomore [27, 28], que será formulado na

seção 3.2. Valério de Carvalho [8, 10] apresentou um modelo matemático para o problema

de corte de estoque unidimensional baseado no problema de fluxo em arcos. O autor



3.2 O problema de corte de estoque bidimensional 33

modelou o problema de encontrar um padrão de corte factível como um problema de

determinar um caminho em um grafo acíclico e orientado G(V, S), com L+ 1 vértices. A

distância entre um vértice e outro, representa uma unidade de comprimento do objeto. O

conjunto S representa os arcos do grafo G(V, S) e é definido por (3.6).

S =

{
(s, t); 0 ≤ s < t ≤ L e t− s = li para algum i ≤ m

}
(3.6)

A expressão (3.6) destaca que existe uma arco entre o vértice s e o t se, e somente se,

s− t = li para algum i, i = 1, . . . ,m. As perdas serão representadas por arcos adicionais

entre os vértices (u, u+1), u = 0, 1, . . . , L−1. Assim, o problema de encontrar um padrão

de corte factível pode ser formulado como determinar um caminho entre os vértices 0 e

L no grafo G(V, S). Definimos a variável zst, s < t como sendo o número de itens de

comprimento (t− s) cortados do objeto. Dessa forma, o modelo matemático apresentado

em [8, 10] é dado pelas expressões (3.7) - (3.10).

ZV C = min f (3.7)

s.a

∑
(s,t)∈S

zst −
∑

(t,u)∈S
ztu =

⎧⎪⎪⎨⎪⎪⎩
−f, se t = 0;

0, se t = 1, 2, . . . , L− 1;

f, se t = L.

, (3.8)

∑
(h,h+li)∈S

zh,h+li = bi, i = 1, . . . ,m, (3.9)

zst ∈ Z+, ∀(s, t) ∈ S. (3.10)

A função objetivo (3.7) visa minimizar o fluxo da rede, que pode ser vista como a

quantidade de objetos cortados [34]. O conjunto de restrições (3.8) representa as restrições

de conservação do fluxo de um grafo. As restrições (3.9) garantem que a demanda é

atendida.

3.2 O problema de corte de estoque bidimensional

O problema de corte de estoque (PCE) pode ser generalizado da seguinte forma: de-

terminar como cortar peças grandes com dimensões específicas que estejam disponíveis em

estoque (chamadas de objetos) para a produção de uma determinada demanda de um con-



3.2 O problema de corte de estoque bidimensional 34

junto de peças menores de tamanhos variados e muitas vezes não padronizadas (chamadas

de itens), de acordo com algum critério de otimização, como por exemplo, minimizar o

número total de objetos cortados, minimizar o desperdício de material, maximizar lucros,

minimizar o número de ciclos da serra (este último item será melhor detalhado no capítulo

4), etc. Alguns fatores importantes podem ser considerados nos parâmetros e restrições

desses problemas, como por exemplo, capacidade da máquina de corte (limitada ou não),

quantidade de objetos em estoque (limitada ou não), tempo de produção, entre outros.

Na literatura, podemos encontrar uma grande diversidade de problemas de corte de

estoque. Para facilitar a comunicação entre os pesquisadores, foram propostas duas tipolo-

gias para classificar esses problemas, conforme algumas características descritas a seguir.

A primeira tipologia é a de Dyckhoff [20], em que o autor apresenta uma classificação

para os problemas de corte de estoque fundamentados sobre suas principais característi-

cas: dimensionalidade, tipo de alocação, variedades de objetos e variedades de itens. A

segunda proposta é a tipologia de Wäscher et al [?], na qual os autores propõem uma

tipologia baseada em [20], mas que abrange uma maior quantidade de problemas (para

mais detalhes sobre as tipologias ver anexo A).

Deste ponto em diante, iremos trabalhar com o PCE em que duas dimensões são

relevantes para o processo de corte. Neste caso, definimos o PCE bidimensional da seguinte

maneira. Considere que existam em estoque um número suficientemente grande de objetos

(placas de madeira, chapas de aço, etc.), de comprimento L e largura W , e um conjunto

de itens de comprimento li e largura wi, cada um com demanda conhecida bi, para i =

1, . . . ,m. O problema consiste em determinar como cortar os objetos de forma a atender

a demanda, de acordo com algum critério de otimização. A figura 1 mostra um exemplo

de problema de corte de estoque bidimensional com vários objetos em estoque e vários

itens com demanda pré-espeficada.

Figura 1: Problema de corte de estoque bidimensional.



3.2 O problema de corte de estoque bidimensional 35

Mais algumas definições são necessárias para dar suporte ao estudo do problema de

corte de estoque.

Definição 3.1. [2] Padrão de corte é a maneira de como os itens estão dispostos em

um objeto. Associamos a um padrão de corte um vetor m-dimensional Aj, que contabiliza

os itens incluídos no padrão de corte j, definido por (3.11).

AT
j = (a1j, a2j, . . . , amj). (3.11)

Em (3.11), aij, i = 1, . . . ,m, representa o número de vezes que o item i aparece no padrão

de corte j.

Padrões de corte que tem mesmo vetor associado são chamados de equivalentes. Um

vetor AT
j = (a1j, a2j, . . . , amj) representa um padrão de corte se, e somente se, satisfaz

as restrições físicas do objeto (3.12). No caso unidimensional as restrições físicas são

equivalentes às restrições do problema da mochila (3.12) - (3.13).

l1a1j + l2a2j + . . .+ lmamj, (3.12)

a1j, a2j, . . . , amj ∈ Z+. (3.13)

No caso bidimensional, as restrições físicas são mais complicadas de serem explicitadas,

pois as características das máquinas de corte e os tipos de corte são relevantes para a

modelagem matemática. Para mais detalhes ver, por exemplo, [23], [39], [25], [64] e [65],

entre outros. As figuras 2 e 3 apresentam exemplos de um padrão de corte unidimensional

e um bidimensional, respectivamente.

Figura 2: Padrão de corte unidimensional.



3.2 O problema de corte de estoque bidimensional 36

Figura 3: Padrão de corte bidimensional.

Na prática é muito difícil conseguirmos um padrão de corte que utilize a área total

do objeto. Nas figuras 2 e 3, as partes hachuradas nos padrões de corte, cujas dimensões

não foram pré-definidas, não serão aproveitadas no processo de produção. Essas partes

são chamadas perda. No caso unidimensional a perda de uma padrão de corte j é dada

por (3.14) e no caso bidimensional por (3.15).

Pj = L−
m∑
i=1

liaij (3.14)

Pj = LW −
m∑
i=1

(liwi)aij (3.15)

Definição 3.2. Padrão de corte homogêneo é o padrão de corte que possui apenas um

tipo de item, isto é, o vetor m-dimensional (3.16) que representa esse padrão tem apenas

uma coordenada não nula.

AT
j = (0, . . . , aij, . . . , 0). (3.16)

Quando um padrão de corte homogêneo apresenta o maior número possível do item, o

padrão é denominado padrão de corte homogêneo maximal .

Os padrões de corte homogêneos maximais podem ser determinados sem perda de

generalidade, no caso bidimensional por (3.17).



3.2 O problema de corte de estoque bidimensional 37

aij =

⎧⎨⎩
⌊
L
lj

⌋
·
⌊
W
wj

⌋
, se i = j,

0, caso contrário.
(3.17)

A figura 4 ilustra um padrão de corte homogêneo maximal no caso bidimensional.

Figura 4: Padrão de corte homogêneo maximal bidimensional.

Uma formulação importante para o PCE, em que todos n padrões de corte factíveis

são conhecidos à priori, foi apresentada em [27], [28] e [29] e é dada por (3.18) - (3.20). A

variável de decisão xj representa o número de objetos cortados de acordo com o padrão

de corte j, j = 1, . . . , n.

PCE com padrões de corte conhecidos

ZGG = min

n∑
j=1

cjxj (3.18)

s.a
n∑

j=1

aijxj ≥ bi, i = 1, . . . ,m, (3.19)

xj ∈ Z+, j = 1, . . . , n. (3.20)

A função objetivo (3.18) visa minimizar o custo total dos objetos cortados. Caso

cj = 1, para todo j = 1, . . . , n, então o problema passa a ser a um problema de redução

do número de objetos cortados. O conjunto de restrições (3.19) garante que a demanda

de todos os itens é atendida, também podendo existir o excesso de produção. O conjunto

de restrições (3.20) representa o domínio das variáveis. De acordo com Vance [54], para

o caso unidimensional o modelo matemático (3.18) - (3.20) pode ser obtido aplicando



3.3 Geração de colunas aplicado ao PCE 38

a técnica de decomposição de Dantzig-Wolfe ao modelo atribuído à Kantorovich (3.1) -

(3.5).

3.3 Geração de colunas aplicado ao PCE

A solução do PCE inteiro, na formulação (3.18) - (3.20), esbarra em duas dificuldades

computacionais: o elevado número de padrões de corte (variável xj) que pode existir;

e a existência das restrições de integrabilidade (3.20). A primeira dificuldade pode ser

contornada com a relaxação das restrições de integrabilidade (3.20) sobre as variáveis xj,

j = 1, . . . , n, isto é, as restrições (3.20) são substituídas por xj ∈ R+. Já a segunda

dificuldade pode ser contornada com a utilização do procedimento de geração de colunas

(seção 2.1).

Considere a relaxação linear do problema (3.18) - (3.20) escrita na forma (3.21) -

(3.23), em que n é muito maior que m (n� m).

Relaxação do PCE com padrões de corte conhecidos

ZGG−RL = min
n∑

j=1

cjxj (3.21)

s.a
n∑

j=1

Ajxj ≥ b, (3.22)

xj ≥ 0, j = 1, . . . , n. (3.23)

O problema mestre restrito (PMR) inicial é formulado, considerando m padrões de

corte homogêneo maximais e é dado da forma (3.24) - (3.26).



3.3 Geração de colunas aplicado ao PCE 39

ZPMR = min
m∑
j=1

cjxj (3.24)

s.a
m∑
j=1

Ajxj ≥ bi, i = 1, . . . ,m, (3.25)

xj ≥ 0, j = 1, . . . ,m. (3.26)

Note que a matriz associada ao (PMR) inicial é uma matriz diagonal inversível da

forma (3.27). Lembre-se que li ≤ L e wi ≤ W .

[A1 . . . Am] =

⎡⎢⎢⎢⎢⎢⎣
a11 0 . . . 0

0 a22 . . . 0
...

... . . . ...

0 0 . . . amm

⎤⎥⎥⎥⎥⎥⎦ . (3.27)

O subproblema a ser resolvido a cada iteração do procedimento de geração de colunas

para verificar se existe um padrão de corte diferente dos que pertencem ao (PMR) e que

melhore a solução atual é dado pelas expressões (3.28) - (3.29).

ZSUBP = min (cj − πTAj) (3.28)

s.a.

Aj é um padrão de corte factível. (3.29)

O problema (3.28) - (3.29) é o subproblema pricing para o problema de corte de es-

toque. Vale ressaltar que para Aj ser um padrão de corte é necessário e suficiente satisfazer

as condições físicas do objeto. Dado o fato do procedimento de geração de colunas ser apli-

cado ao PCE relaxado (3.21) - (3.23), na maioria das vezes obtemos soluções fracionárias,

que por vez, não são ótimas para o problema original (inteiro). Assim, a partir da solução

do PCE relaxado são utilizados alguns métodos heurísticos para encontrar uma solução

inteira para o problema original (3.18) - (3.20).

Quando o PCE permite produção em excesso, Gilmore e Gomory [27, 28, 29] propõem

utilizar a solução inteira aproximada, obtida tomando o teto da solução ótima fracionária

do PCE relaxado, isto é, sendo x∗ ∈ R
m
+ uma solução ótima fracionária do PCE relaxado,



3.4 Aplicações do PCE 40

tomemos xi = �x∗i 
, i = 1, . . . ,m, como solução inteira aproximada. Poldi e Arenales

[45, 46] propõem uma heurística para obter uma solução inteira aproximada para o PCE

original, quando a demanda deve ser atendida exatamente. A heurística inicia-se tomando

como solução inteira aproximada x, com x = (�x∗1�, �x∗2�, . . . , �x∗n�). Se esta solução não

for factível para (3.18) - (3.20), isto é,
n∑

j=1

aijxj < bi, para algum i, i = 1, . . . ,m, então

devemos resolver o problema residual (P-Res) , formado pelas expressões (3.30)-(3.32).

ZP−Res = min
n∑

j=1

xj (3.30)

s.a
n∑

j=1

aijxj = ri, i = 1, . . . ,m, (3.31)

xj ∈ Z+, j = 1, . . . , n. (3.32)

Na restrição (3.31), ri = bi −
n∑

j=1

aijxj, i = 1, . . . ,m, é a demanda que não foi aten-

dida por x. Note que (P-Res) apresentam as restrições de integrabilidade (3.32). Assim,

devemos resolver o (P-Res) relaxado, obtendo uma solução ótima para o mesmo e caso a

solução ótima para o (P-Res) seja fracionária, devemos aplicar a heurística residual nova-

mente, e assim, por diante, até obtermos uma solução inteira que satisfaça as restrições

de demanda do PCE original.

3.4 Aplicações do PCE

Devido à importância econômica do PCE, surgiram e continuam surgindo importantes

pesquisas explorando outros aspectos do problema e que vão além das suas dificuldades

básicas de resolução. Pesquisadores de todo o mundo comprovaram em seus trabalhos

a vasta aplicabilidade destes problemas em diversas áreas da indústria e o interesse em

otimizar vários critérios diferentes, que podem representar, na prática, uma melhora sig-

nificativa no processo de produção.

Nesta seção iremos destacar alguns trabalhos na literatura que tratam do PCE, em

processos industriais, cujos objetos são bobinas de papel, placas de madeira, metais e

tecidos.



3.5 Extensões do PCE 41

Dentre os trabalhos da literatura sobre PCE aplicados à industria de papel, podemos

destacar os de Morabito [37] e Poltroniere et al. [47]. Em [37], é feita uma revisão dos PCE

encontrados na literatura da época em que se discutem modelos de otimização, adaptados

do modelo de Gilmore e Gomory (3.18) - (3.20) no caso unidimensional para aplicá-los

em uma indústria de papel e papelão. Ainda em [37] são apresentos estudos reais para

os PCE bidimensionais nas indústrias de móveis. Os autores de [47] apresentam uma

formulação para um problema lot-sizing com corte de estoque acoplado, aplicado a uma

indústria de papel e propõem heurísticas para resolver este problema.

Existem muitos trabalhos de PCE no contexto de indústrias de móveis. Para este

trabalho, destacamos os trabalhos de Morabito e Arenales [40] e de Figueiredo e Rangel

[25]. Em [40] é analisado o comportamento de um modelo baseado em (3.18) - (3.20), em

uma fábrica de móveis com produção em grande escala em que são priorizados os padrões

de corte que facilitam o processo de corte. Por fim, é discutido o trade-off entre padrões

de corte que melhora o processo de corte e padrões de corte que geram menos desperdício

de matéria prima. Em [25] é proposta uma heurística para gerar um conjunto de padrões

de corte de uma fábrica de móveis, dando prioridade também aos padrões de corte que

melhoram a produtividade do equipamento de corte.

No contexto dos PCE aplicados às metalúrgicas, podemos ressaltar o trabalho de Chu

e Antonio [13]. Nele, é abordado um problema em relação ao caso unidimensional aplicado

a uma pequena fábrica de peças de metais em que os objetos não são de comprimento

padronizado, pois as sobras de um objeto cortado retornam para o estoque como um novo

objeto. O problema permite o corte simultâneo de objetos e visa não apenas minimizar o

desperdício de material, como também otimizar o tempo de corte.

Tratando do PCE aplicado à indústria têxtil podemos destacar os trabalhos de De-

graeve e Vandebroek [16] e Degraeve et al. [17]. Em ambos os trabalhos, o PCE consiste

em encontrar boas combinações de padrões de corte e altura da pilha associada ao tecido,

visando minimizar o excesso de produção e o custo de setup.

3.5 Extensões do PCE

O PCE clássico, em que a função objetivo é definida pela minimização do número de

objetos padronizados [48] juntamente com o PCE que visa reduzir o número de padrões de

cortes, é o mais recorrente na literatura. Entretanto, existem algumas extensões para esses



3.5 Extensões do PCE 42

problemas, isto é, existem outras possibilidades para o critério de otimização e restrições

do problema, dependendo tanto do interesse industrial quanto das características das

indústrias no qual os PCE serão aplicados. Nesta subseção iremos realizar uma breve

discussão dos PCE na literatura, conforme seus critéros de otimização.

Para o PCE na qual a função objetivo é a minimização do número de padrões de corte,

podemos destacar alguns trabalhos. Haessler [31] propõe uma modelagem matemática

não-linear para o PCE unidimensional. É apresentado um método heurístico sequencial

para resolver o problema, penalizando as trocas de padrões de corte para reduzir o número

de padrões de corte na solução. Esse método heurístico fornece bons resultados, pois

reduz o número de padrões de corte sem aumentar muito o número de objetos cortados.

O trabalho [31] serviu como base para muitos outros trabalhos da literatura (e.g [41], [53]

e [63]). Em [41] é apresentada uma linearização para o modelo de [31], tornando possível

a utilização do procedimento de geração de colunas para a resolução do problema.

Vanderbeck [56] propõe um modelo matemático, obtido aplicando o procedimento de

decomposição de Dantzig-Wolfe (seção 2.1) ao modelo (3.1) - (3.5). O autor apresenta um

método de geração de colunas para resolver o problema representado pelo modelo obtido,

em que os valores duais associados às restrições de demanda e de setup são utilizados no

subproblema pricing que gera colunas para o problema mestre. Foerster e Wäscher [26]

desenvolvem uma heurística de redução de padrões de corte para o caso unidimensional,

em que a partir de uma solução inicial para o problema, a ideia é obter padrões de corte

através de combinações dos padrões de corte originais do problema, de maneira que a soma

das frequências dos padrões obtidos seja a mesma da soma das frequências dos padrões de

corte originais, mantendo assim a mesma quantidade de objetos na nova solução. Diegel

et al. [19], a fim de reduzir o número de padrões de corte na solução, analisam os custos e

a viabilidade de aumentar a frequência de um padrão de corte pouco utilizado na solução.

Ao contrário do PCE, cuja função objetivo é a minimização do número de padrões

de corte, existem poucos trabalhos na literatura abordando o PCE, considerando o corte

simultâneo de objetos. Podemos destacar [13], [16], [17], [43], [48] e [62]. Yanasse et al.

[62] apresentam uma heurística para resolver esse tipo de PCE no caso bidimensional,

em que padrões de corte são gerados por um problema auxiliar (com demandas ajustadas

por um fator F0). Caso o padrão gerado satisfaça alguns critérios, será aceito e usado F0

vezes. As demandas serão atualizadas e definirão um novo problema auxiliar. Repete-se

esse processo até que todas as demandas sejam atendidas exatamente. Os trabalhos [43]

e [48] apresentam modelos matemáticos e métodos de solução para esses modelos, que



3.5 Extensões do PCE 43

serão apresentados e discutidos na seção 4.1. Os trabalhos [16] e [17] serão discutidos na

seção 4.2 e o trabalho [13] na seção 4.3.

Vale ressaltar que existem outros critérios de otimização importantes na prática in-

dustrial. Para alguns casos, é interessante o ponto de vista industrial para a associação

de mais de um critério de otimização em uma mesma função objetivo do problema.



44

Capítulo 4

O problema de ciclos da serra

No processo de corte de algumas indústrias, como por exemplo, de móveis (e.g. [52] e

[36]) e têxtil (e.g. [16] e [17]), um critério tão importante quanto à minimização do número

de objetos cortados é a maximização da produtividade dos equipamentos de corte. Tal

produtividade está relacionada, entre outros fatores, com o tipo e número de padrões de

corte distintos e ao número de objetos que podem ser cortados simultaneamente. Uma vez

que, cortar apenas um objeto e cortar mais de um objeto simultaneamete gera o mesmo

gasto de tempo no processo de corte. Aumentar a produtividade do equipamento de

corte pode trazer benefícios, como por exemplo, a economia de energia elétrica, a redução

do tempo de uso da máquina de corte e a redução do custo operacional da máquina.

Neste trabalho estamos interessados em analisar o PCE considerando a produtividade da

máquina de corte.

Considere um conjunto de objetos com a mesma espessura. A capacidade da máquina

de corte (cap) é o número máximo de objetos que a máquina pode cortar simultaneamente,

de acordo com um padrão de corte. O valor de cap pode ser calculado por (4.1), em termos

da altura da serra, alt, e da espessura dos objetos, esp.

cap =

⌊
alt

esp

⌋
. (4.1)

Definição 4.1. Ciclo da serra é o conjunto de todas as operações necessárias para

cortar um ou mais objetos de acordo com um determinado padrão de corte, até que todos

os itens nele contidos sejam produzidos [62].



4 O problema de ciclos da serra 45

Considerando que o tempo necessário para concluir um ciclo da serra não varia com

o número de objetos cortados simultaneamente, o tempo utilizado para cortar apenas

um objeto é o mesmo para cortar até um número cap de objetos. Desta forma, cortar

um conjunto de objetos simultaneamente diminui o tempo de utilização da máquina e,

portanto, aumenta a produtividade do processo de corte. Em uma máquina de corte com

capacidade cap, o número de ciclos da serra yj, necessário para cortar xj objetos de acordo

com o padrão de corte j é dado por (4.2).

yj =

⌈
xj

cap

⌉
. (4.2)

A figura 5 ilustra o corte simultâneo de objetos no contexto de uma fábrica de móveis,

onde a máquina tem a capacidade de cortar 6 objetos simultaneamente (cap = 6).

Figura 5: Corte simultâneo de objetos, adaptado de [52].

Definição 4.2. Ciclo completo é quando a capacidade da máquina em um determinado

ciclo da serra é utilizada em sua totalidade. Caso contrário, é dito ciclo incompleto

[48].

Assim, a utilização de ciclos completos, quando a frequência do padrão permite, pode

contribuir com o objetivo de minimizar o número de ciclos da serra. Na seção 4.1 apre-

sentaremos alguns modelos matemáticos para o PCE com o objetivo de minimizar ciclos

da serra. Nas seções 4.2 e 4.3 iremos discutir o problema no contexto da indústria têxtil

e de metal, respectivamente.



4.1 Modelos matemáticos para o problema de ciclos da serra 46

4.1 Modelos matemáticos para o problema de ciclos da
serra

Yanasse [60] apresenta um modelo matemático para o problema de redução do número

de ciclos da serra (4.3) - (4.6), baseado no modelo PCE (3.18) - (3.20) discutido na seção

3.2.

PCE com redução do número de ciclos da serra (formulação 1)

ZPCE−C = min
n∑

j=1

yj (4.3)

s.a
n∑

j=1

aijxj ≥ bi, i = 1, . . . ,m, (4.4)

yj =

⌈
xj

cap

⌉
, j = 1, . . . , n, (4.5)

xj, yj ∈ Z+, j = 1, . . . , n. (4.6)

A função objetivo (4.3) visa minimizar o número de ciclos da serra. O conjunto de

restrições (4.4) garante que a demanda de todos os itens é atendida, sendo permitido o

excesso de produção. O conjunto de restrições (4.5) é definido similarmente à (4.2). As

restrições (4.6) representam o domínio das variáveis. Podemos reescrever o modelo para

redução de ciclos (PCE-C) como (4.7) - (4.10).

PCE com redução do número de ciclos da serra (formulação 2)

ZPCE−C = min

n∑
j=1

yj (4.7)

s.a
n∑

j=1

aijxj ≥ bi, i = 1, . . . ,m, (4.8)

yj ≥ xj

cap
, j = 1, . . . , n, (4.9)

xj, yj ∈ Z+, j = 1, . . . , n. (4.10)



4.1 Modelos matemáticos para o problema de ciclos da serra 47

Ainda em [60] o autor demonstra que o valor ótimo da função objetivo do modelo

(4.7) - (4.10) é o mesmo da função objetivo do modelo (4.11) - (4.13).

PCE com redução do número de ciclos da serra (formulação 3)

ZPCE−C2 = min

n∑
j=1

yj (4.11)

s.a
n∑

j=1

aijyj ≥
⌈

bi
cap

⌉
, i = 1, . . . ,m, (4.12)

yj ∈ Z+, j = 1, . . . , n. (4.13)

Além da redução de ciclos da serra, podemos também usar como critério de otimização

o número de objetos cortados. Nesse caso, substituiremos a função objetivo do modelo

(4.7) pela função objetivo (4.14) e obteremos o modelo redução-ciclos-objetos (PCE-CO).

PCE com redução dos números de ciclos da serra e de objetos (PCE-CO)

ZPCE−CO = min
n∑

j=1

xj +
n∑

j=1

yj = min
n∑

j=1

(
xj + yj

)
. (4.14)

s.a
n∑

j=1

aijxj ≥ bi, i = 1, . . . ,m, (4.8)

yj ≥ xj

cap
, j = 1, . . . , n, (4.9)

xj, yj ∈ Z+, j = 1, . . . , n. (4.10)

O modelo (PCE-CO) formado pelas expressões (4.14) , (4.8) - (4.10) envolve a otimiza-

ção simultânea de dois objetivos, geralmente conflitantes, minimizar o número total de

objetos e minimizar o total de ciclos da serra. Por exemplo, quando é permitido o excesso

de demanda, o melhor uso da capacidade de serra (ciclos completos) pode implicar em um

aumento do número de objetos cortados. Segundo [15], quando estamos otimizando dois

ou mais objetivos conflitantes, busca-se um conjunto de soluções eficientes, no qual não

é possível afirmar se uma solução é melhor do que a outra. Essas soluções são chamadas



4.1 Modelos matemáticos para o problema de ciclos da serra 48

de soluções não-dominadas.

No modelo (PCE-CO), se os valores de xj, j = 1, . . . , n são menores ou iguais a cap,

então as variáveis yj, j = 1, . . . , n, são binárias. E neste caso o modelo reduz-se ao PCE

que visa minimizar o número de padrões de corte [60]. Em problemas de redução-ciclos-

objetos ligados ao processo de produção de algumas indústrias, quando a diversidade de

padrões de corte utilizados no processo de corte é reduzida, então a frequência de alguns

padrões de corte pode aumentar. O aumento da frequência pode aumentar o número de

ciclos completos. Assim, uma maneira de tentar reduzir o número de ciclos da serra é

diminuir o número de padrões de corte distintos, mas redução de padrões de corte não

significa necessariamente em redução de ciclos da serra [51].

Na literatura podemos encontrar outras formulações para o problema de redução de

ciclos da serra. Mosquera e Rangel [43] propõem um modelo focado no PCE bidimensional

na indústria moveleira, que é semelhante ao modelo (PCE-CO) e é considerado que a

quantidade de objetos cortados de acordo com um padrão de corte j, é um múltiplo de

cap, isto é, são permitidos apenas ciclos completos. O modelo proposto, denominado

modelo de multiplicidade (PCE-CO-MM), é definido por (4.15) - (4.18).

Modelo de multipilicade para redução de ciclos e objetos (PCE-CO-MM)

ZPCE−CO−MM = min

n∑
j=1

(
xj + yj

)
(4.15)

s.a
n∑

j=1

aijxj ≥ bi, i = 1, . . . ,m, (4.16)

xj = cap yj, j = 1, . . . , n, (4.17)

xj, yj ∈ Z+, j = 1, . . . , n. (4.18)

Ranck Jr. [48], observa que o modelo (PCE-CO-MM) não permite a utilização de

ciclos com capacidade incompleta. Propõe então o modelo (PCE-CO-RJ) (4.19) - (4.21)

que permite que 1, 2, ..., cap objetos sejam cortados simultaneamente em um ciclo e as

demandas são atendidas sem excesso de produção. A variável de decisão yαj representa o

número de ciclos da serra utilizados pelo padrão j com (cap− α) objetos cortados.



4.1 Modelos matemáticos para o problema de ciclos da serra 49

Modelo para redução de ciclos da serra de Ranck Jr. [48]

ZPCE−CO−RJ = min

n∑
j=1

cap−1∑
α=0

yαj (4.19)

s.a
n∑

j=1

cap−1∑
α=0

aijyαj
(
cap− α

)
= bi, i = 1, . . . ,m, (4.20)

yαj ∈ Z+, j = 1, . . . , n, α = 0, 1, . . . , cap− 1. (4.21)

Toscano et. al [52] propõem uma formulação para o problema utilizando a frequência

do padrão de corte para controlar os ciclos da serra. Se um padrão de corte j é usado,

ou seja, xj > 0, então a sua frequência deve ser maior ou igual à frequência mínima,

fmin = β cap, em que β é um parâmetro pré-definido que representa um percentual mínimo

de uso da capacidade da máquina de corte em cada ciclo da serra.

São definidos os conjuntos N1 e N2 que são, respectivamente, o conjunto de padrões

de corte gerados para o PCE (3.18) - (3.20) e o conjunto de padrões de corte gerados para

o problema de corte de estoque reformulado (PCE-R1) relaxado, descrito por (4.24) -

(4.29). Uma solução factível xj obtida para o (PCE-R1) relaxado é analisada. Se existem

padrões com frequência abaixo de fmin, isto é, xj < fmin. Então o padrão de corte j é

incluído no subconjunto N3 e são adicionadas as restrições (4.22). Mbig é um valor muito

grande e δj uma variável binária definida por (4.23).

fmin δj ≤ xj ≤Mbig δj, j ∈ N3. (4.22)

δj =

{
1, se o padrão de corte j é usado

0, caso contrário.
(4.23)

Com a adição das restrições de frequência mínima (4.22), pode haver uso “excessivo”

de objetos. Para evitar essa situação um parâmetro de tolerância, TOL, é definido para

controlar o número máximo de objetos que podem ser utilizados.



4.2 Aplicação do PCE-C indústria têxtil 50

Após as definições anteriores, o problema (PCE-R1) pode ser formulado pelas ex-

pressões (4.24) - (4.29).

Modelo para redução de ciclos da serra com frequência mínima

ZPCE−R1 = min
∑

j∈N1∪N2

xj (4.24)

s.a ∑
j∈N1∪N2

aijxj ≥ bi, i = 1, . . . ,m, (4.25)

fmin δj ≤ xj ≤Mbig δj, j ∈ N3, (4.26)∑
j∈N1∪N2

xj ≤ TOL, (4.27)

xj ∈ Z+, j ∈ N1 ∪N2, (4.28)

δj ∈ {0, 1}, j ∈ N3. (4.29)

Para resolver (4.24) - (4.29) é aplicado um procedimento de geração de colunas baseada

na metodologia descrita na seção 2.2. As restrições (4.28) são relaxadas para xj ∈ R,

j ∈ N1 ∪ N2, dando origem a um problema inteiro misto. O subproblema de geração de

colunas é resolvido usando apenas os valores duais associados às restrições de demanda

(4.25). Apenas uma coluna é gerada por iteração. No capítulo 5 discutiremos uma

proposta para resolver o problema PCE considerando a redução dos ciclos da serra.

4.2 Aplicação do PCE-C indústria têxtil

Os trabalhos de Degraeve e Vandebroek [16] e de Degraeve et al. [17] apre-sentam um

modelo matemático para um PCE diretamente ligado com o problema de ciclos da serra.

Tal problema faz parte do contexto de uma indústria têxtil de alta costura, com algumas

características exclusivas. Os itens produzidos fazem uso de tecidos caros e são fabricados

apenas uma pequena quantidade de cada item, o que exige desperdício mínimo no processo

de produção. O estiramento do tecido na mesa de corte, a fixação das camadas e padrões

de corte, e o próprio corte em si são operações que demandam tempo. O problema, então,

consiste em encontrar a combinação do número de camadas de tecido na mesa de corte e

o conjunto associado de padrões de corte, que resultará no número mínimo de preparos



4.2 Aplicação do PCE-C indústria têxtil 51

da máquina desde que satisfaça a demanda com pouco ou nenhum excesso.

Outra característica do problema é que todo item tem o mesmo comprimento l. Em

cada item estão dispostas todas as partes que formam uma peça de roupa, por exemplo,

mangas, bolsos, frente, costa, etc. A figura 6 representa um padrão de corte com as peças

da roupa representada em cada item. A capacidade da faca de corte cap limita o número

de camadas de tecido que podem ser cortados simultaneamente. O número de itens em

um padrão de corte é limitado pelo comprimento da mesa de corte L. Assim, o número

máximo de itens em um padrão de corte é dado por (4.30).

Figura 6: Padrão de corte na indústria têxtil , adaptado de [16].

H =

⌊
L

l

⌋
. (4.30)

Tomando aij, xj e λj como variáveis, em que λj é definida como em (4.23). Definindo

C como custo de setup, o modelo matemático apresentado em [16] e [17] é dado por (4.31)

- (4.36).



4.2 Aplicação do PCE-C indústria têxtil 52

Modelo para corte simultâneo de objetos de Degraeve et al. [16] e [17]

ZDEG = min C
n∑

j=1

λj +
m∑
i=1

n∑
j=1

aijxj (4.31)

s.a
n∑

j=1

aijxj ≥ bi, i = 1, . . . ,m, (4.32)

n∑
j=1

l aij ≤ Lλj, j = 1, . . . , n, (4.33)

xj ≤ cap λj, j = 1, . . . , n, (4.34)

aij, xj ∈ Z+, i = 1, . . . ,m, j = 1, . . . , n, (4.35)

λj ∈ {0, 1}, j = 1, . . . , n. (4.36)

A função objetivo (4.31) visa minimizar o custo de preparos da máquina de corte e

o número de objetos cortados (camada de tecidos), isto é, minimiza setup e o excesso de

produção. O conjunto de restrições de demanda (4.32) são não-lineares, pois as variáveis

aij e xj aparecem como um produto. As restrições da mochila (4.33) garante que o número

de itens em um padrão de corte não exceda o tamanho da mesa de corte. Essas restrições

permitem que os objetos tenham tamanhos flexíveis, isto é, em um padrão de corte o

número de itens (todos com mesmo comprimento) pode variar. O conjunto de restrições

(4.34) garante que o número de objetos cortados de acordo com um mesmo padrão de

corte, quando usado, não exceda a capacidade da máquina de corte. As restrições (4.35)

e (4.36) são as restrições de domínio das variáveis.

O modelo (4.31) - (4.36) é não-linear e pode ser linearizado se os padrões de corte

forem gerados antecipadamente. Vale ressaltar que, esta estratégia é viável apenas se a

capacidade da mesa de corte H não é muito grande, pois, para m itens distintos, existem
H∑
k=1

mk padrões de corte factíveis. Porém nem sempre é possível gerar todos os padrões

de corte, em [16] e [17] são apresentadas três propostas para a linearização do modelo.

Segundo os autores de [16] e [17] o modelo (4.31) - (4.36) é explicitamente focado

na indústria têxtil de alta costura com baixa demanda. Esse fato pode tornar o modelo

inviável para representar problemas com alta demanda. Por exemplo, se é demandado um

número muito alto de apenas um tipo de item, o problema não produzirá solução factível.

Para esse caso o limitante superior para o número de itens é dado por
H∑
i=1

i cap, isto é, a



4.3 Aplicação do PCE-C na indústria de metal 53

demanda b1 do único item tem que satisfazer a expressão (4.37), para o modelo poder ser

usado.

b1 ≤
H∑
i=1

i cap (4.37)

Desse modo, o modelo não pode representar um modelo de ciclos da serra de uma

forma geral, uma vez que o conjunto de restrições (4.34) não permite que um padrão de

corte quando usado possa ser cortado em um número maior que a capacidade da máquina

de corte cap, isto é, o modelo permite que apenas um ciclo possa ser cortado para cada

padrão de corte.

4.3 Aplicação do PCE-C na indústria de metal

O trabalho de Chu e Antonio [13] apresenta um modelo matemático para um PCE

unidimensional real que permite o corte simultâneo de objetos, proveniente de uma fábrica

especializada em corte de barras de metal com varias formas (quadrado, redondo, triangu-

lar, etc.). O modelo matemático leva em consideração algumas características exclusivas

dessa fábrica. Uma característica muito relevante dessa fábrica é que quando um objeto

não é totalmente utilizado, é possível que a parte restante possa ser reutilizada no futuro,

se seu comprimento for superior a um limite pré-determinado r. Nesse caso, a parte re-

utilizável torna-se um novo objeto. Segundo os autores, embora o material reutilizável

não seja uma perda de matéria-prima, essa situação deve ser evitada por algumas razões.

A primeira delas é o alto custo de transporte dos objetos reutilizáveis, uma vez que esses

objetos têm de ser deslocados a partir da máquina de corte para a área onde são armazena-

dos para cortes futuros. A segunda razão é que os comprimentos dos objetos reutilizáveis

não são padronizados de modo que eles são guardados em uma área específica da fábrica

que tem capacidade limitada de armazenamento. E em terceiro lugar, porque não se sabe

quando os objetos reutilizáveis serão realmente utilizados, gerando, assim, imobilização

de capital. Desse modo, é necessário atribuir um custo de penalidade C, dado por (4.38),

associado ao objeto reutilizável de comprimento W .



4.3 Aplicação do PCE-C na indústria de metal 54

C = C(W ) =

{
W, se W < r,

C1 + C2W, caso contrário.
(4.38)

Em (4.38) o parâmetro C1 representa o custo de transporte do objeto reutilizável. O

parâmetro C2 representa o custo de imobilização de capital, proporcional ao comprimento

do objeto.

Outra característica do problema está relacionada com a tolerância dos itens, rigorosa

ou normal. Um item com tolerância rigorosa deve ser entregue com boa qualidade (sem

deformação geométrica e com composição química uniforme). Para garantir isso, devem

ser feitos “ajustes” nas duas extremidades do objeto (exceto nos objetos reutilizados), pois

podem existir defeitos de qualidade. Desse modo para alocar um item na extremidade

de um objeto com tolerância rigorosa, um comprimento h deve ser cortado antes que o

item desejado seja cortado do objeto, isto é, qualquer item com tolerância rigorosa deve

ser separado por um comprimento h a partir das extremidades do objeto do qual ele será

cortado. Por outro lado, um item com tolerância normal pode ser colocado em qualquer

extremidade de um objeto. Portanto, dois itens com mesmo comprimento - mas com

tolerância diferente - são considerados itens de tipos diferentes. A tolerância dos itens do

tipo i é dado por τi e definida pela expressão (4.39).

τi =

{
1, se o item do tipo i tem tolerância rigorosa,

0, caso contrário.
(4.39)

Uma vez que no processo de corte mais do que um objeto do mesmo tipo pode ser

cortado simultaneamente, chamamos de pacote o conjunto de objetos cortados simultane-

amente e de tamanho do pacote o número de objetos no pacote. O custo de um corte em

um pacote k de tamanho de xk é dado por p(xk). O custo de cortar um pacote grande

em uma só vez sempre é menor do que separar os objetos do pacote em dois pacotes

menores e depois cortá-los. Definindo η como o custo de preparar um pacote k, dk o

número de cortes necessários para cortar um pacote e μk, dado por (4.40), como o custo

de preparação e de corte de um pacote de tamanho xk e que requer dk cortes.

μk = μ(xk, dk) = η + dk ∗ p(xk). (4.40)



4.3 Aplicação do PCE-C na indústria de metal 55

A figura 7 ilustra um pacote de tamanho quatro, cuja tolerância dos objetos é rigorosa,

que tem material reutilizável e que são necessários quatro cortes para cortar um pacote

de acordo com um determinado padrão de corte.

Figura 7: Pacote, adaptado de [13].

Sejam N o número de objetos distintos e b0 o vetor N -dimensional em que a j-ésima

entrada representa o número de objetos do tipo j em estoque. Sejam ωk = ω(Wk, Ak),

ϕk = ϕ(Wk, Ak) e dk = d(Wk, Ak), respectivamente, a perda de matéria-prima (que não

constitui um objeto reutilizável), o comprimento da parte reutilizável e o número de cortes

necessário, quando um subconjunto Ak de itens é alocado sobre um objeto de comprimento

Wk no pacote k. E tomando ρk = ρ(W,A), dado por (4.41), como custo total incorrido

pela perda de matéria-prima e a parte reutilizável, quando subconjunto Ak de itens é

alocado sobre um objeto de comprimento Wk no pacote k. Em [13] é explicado como

obter os valores de ωk, ϕk e dk

ρk = ρ(Wk, Ak) ≡ ω(Wk, Ak) + C(ϕ(Wk, Ak)) = ωk + C(ϕk). (4.41)

Sejam M o número de pacotes e eN um vetor com N -ésima entrada igual a 1 e as

demais igual a zero. Para cada pacote k associamos um vetor N -dimensional λk em que

a j-ésima entrada é igual a 1 se objetos do tipo j são usados no pacote, e zero, caso

contrário. Com base nas definições apresentadas, o modelo matemático que representa o

problema é dado pelas expressões (4.42) - (4.48).



4.3 Aplicação do PCE-C na indústria de metal 56

Modelo para corte simultâneo de objetos de Chu e Antonio [13]

ZCHU = min

M∑
k=1

(xk ρk + μk) (4.42)

s.a
M∑
k=1

Akxk = b, (4.43)

M∑
k=1

λkxk ≤ b0, (4.44)

eTN λk = 1, k = 1, . . . ,M, (4.45)

λk ∈ {0, 1}N , k = 1, . . . ,M, (4.46)

xk ∈ Z+, k = 1, . . . ,M, (4.47)

Ak ∈ Z
n
+ k = 1, . . . ,M. (4.48)

A função objetivo (4.42) visa minimizar no primeiro termo os custos incorridos pela

perda de material e dos materiais reutilizáveis, enquanto o segundo termo minimiza os

custos de corte. O conjunto de restrições (4.43) assegura que todos os itens demandados

são alocados, mas não permite o excesso de produção. As restrições (4.44) garantem

que nenhum objeto é usado mais do que o disponível em estoque, isto é, o tamanho do

pacote de objetos do tipo k é limitado pelo número de objetos do tipo k em estoque.

Os conjuntos de restrições (4.43) e (4.44) são compostos por restrições não-lineares, o

que torna o modelo matemático não-linear. O conjunto de restrição (4.45) garante que

exatamente um tipo de objeto é usado em cada pacote. As restrições (4.46), (4.47) e

(4.48) são as restrições de domínio das variáveis.

Nesse modelo, um padrão de corte equivalente a um pacote especificado k é dado por

(λk, Ak), porque a partir de um λk pode-se deduzir o tipo de objeto. Assim, um padrão

de corte é um pacote para o qual o tamanho não é especificado. Em uma abordagem

de programação linear, para resolver a não-linearidade do problema, todos os padrões de

corte factíveis seriam identificado antecipadamente. Desse modo, a variável de decisão

xk que representa o tamanho do pacote (número de vezes que cada padrão de corte deve

ser produzido) passaria a ser a única variável do problema. Na resolução do problema,

essas variáveis seriam relaxadas. Uma solução ótima inteira seria obtida através de um

arredondamento da solução dada pelo problema relaxado. No entanto, como o modelo

(4.42) - (4.48) é não-linear os autores de [13] discutem algoritmos para resolver o problema.



4.3 Aplicação do PCE-C na indústria de metal 57

O modelo matemático (4.42) - (4.48) não é recomendado para representar de forma

geral o problema redução-ciclos-objetos, pois em um (PCE-CO) se também tivermos

objetos reutilizáveis (ou tamanhos variados) a tendência é cortar apenas os objetos que

não são provenientes de materiais reutilizáveis (objetos maiores), já que geralmente esses

objetos são capazes de produzirem mais itens por padrão de corte, reduzindo, assim, o

número de ciclos e de objetos cortados.



58

Capítulo 5

Solução do problema de ciclos da
serra via geração de colunas

Neste capítulo apresentaremos a abordagem proposta por Vanderbeck [55, 56] para o

PCE unidimensional que considera o problema de minimização do número de padrões de

corte (PCE-P) e que usa a informação dual relativa às restrições de frequência do padrão

de corte no subproblema pricing. Adaptamos esta abordagem para o PCE bidimensional

que considera a minimização de ciclos da serra e do número de objetos (PCE-CO) de

forma a incorporar no subproblema pricing as informações duais associadas às restrições

que controlam o número de ciclos da serra.

5.1 Técnica de decomposição para o PCE
unidimensional com redução de padrões

O modelo proposto em Vanderbeck [56] para o PCE-P considera K um limite superior

para o número de objetos necessário para atender a demanda de itens. As variáveis de

decisão aij representam o número de vezes que o item i é incluído no padrão de corte j,

xj representa o número de objetos cortados de acordo com o padrão j e a variável binária

λj indica se o padrão de corte j é usado (λj = 1) ou (λj = 0). O modelo não-linear inteiro

é dado por (5.1) - (5.8).



5.1 Técnica de decomposição para o PCE unidimensional com redução de padrões 59

Modelo para o PCE unidimensional com redução de padrões de Vander-

beck [56]

ZPCE−P = min
K∑
j=1

λj (5.1)

s.a
K∑
j=1

xjaij = bi, i = 1, . . . ,m, (5.2)

K∑
j=1

xj ≤ K, (5.3)

xj ≤ Kλj, j = 1, . . . , K, (5.4)
m∑
i=1

wiaij ≤ Wλj, j = 1, . . . , K, (5.5)

aij ∈ Z+, i = 1, . . . ,m, j = 1, . . . , K, (5.6)

λj ∈ {0, 1}, j = 1, . . . , K, (5.7)

xj ∈ Z+, j = 1, . . . , K. (5.8)

A função objetivo (5.1) minimiza o número de diferentes padrões de corte. As res-

trições de demanda (5.2) são não lineares, pois apresentam a multiplicação das variáveis

xj e aij. As restrições (5.3) impõem um limite superior para o número de objetos. As

restrições (5.4) asseguram que há objetos cortados com o padrão de corte j apenas se este

padrão é usado. O conjunto de restrições (5.5) garante que as restrições físicas do objeto

não sejam violadas. Os conjuntos de restrições (5.6), (5.7), e (5.8) são os domínios das

variáveis.

Se as restrições (5.2) e (5.3) são dualizadas e a frequência dos padrões de corte são

fixadas, o problema resultante se decompõe em K subproblemas independentes e idênticos,

que consistem em determinar um padrão de corte unidimensional. Seja Q o conjunto de

soluções factíveis para as restrições (5.4) - (5.8) definido por (5.9) - (5.11).

Q =

{
qj = (q0j, q1j, q2j, . . . , qmj) ∈ Z

m+1
+ , j = 1, . . . , K :

Qj = (q1j, q2j, . . . , qmj) é um padrão de corte factível, (5.9)

q0jqij ≤ bi, i = 1, . . . ,m, (5.10)

q0j ∈ Z é a frequência do padrão de cortej
}
. (5.11)



5.1 Técnica de decomposição para o PCE unidimensional com redução de padrões 60

A restrição (5.10) garante que o número de itens i cortados de acordo com o padrão

de corte j não ultrapasse a demanda bi. Se for permitido o excesso de produção, esta

restrição é desnecessária.

Associando a cada elemento do conjunto Q uma variável binária δj, que assume valor

1 se o padrão de corte Qj é usado com a freqüência q0j e zero caso contrário. Podemos

reformular o problema (PCE-P) como (5.12) - (5.15).

Problema mestre (PCE-M) de Vanderbeck [56]

ZPCE−M = min
∑
qj∈Q

δj (5.12)

s.a ∑
qj∈Q

q0jqijδj = bi, i = 1, . . . ,m, (5.13)

∑
qj∈Q

q0jδj ≤ K, (5.14)

δj ∈ {0, 1}. (5.15)

Assumir que δj = 1 na formulação (PCE-M) é equivalente a definir

(a1j, a2j, . . . , amj, δj, xj) = (q1j, q2j, . . . , qmj, 1, q0j) para algum j na formulação (PCE-

P). O problema (PCE-M), formado pelas expressões (5.12) - (5.15) é um problema de

otimização linear binário com um número muito grande de colunas do tipo (5.16).

⎛⎜⎜⎜⎜⎜⎜⎜⎜⎝

q0jq1j

q0jq2j
...

q0jqmj

q0j

⎞⎟⎟⎟⎟⎟⎟⎟⎟⎠
(5.16)

Para superar parcialmente a dificuldade causada pelo elevado número de colunas,

pode-se usar um procedimento de geração de colunas para resolver a relaxação linear do

problema. A relaxação linear do problema (PCE-M) é formada pelas expressões (5.12) -

(5.14) e o conjunto de restrições (5.17).



5.1 Técnica de decomposição para o PCE unidimensional com redução de padrões 61

0 ≤ δj ≤ 1 (5.17)

O procedimento de geração de colunas aplicado à solução da relaxação linear de (PCE-

M) consiste em inicialmente resolver até a otimalidade uma formulação restrita do pro-

blema, formada por um subconjunto de colunas geradas a priori e as respectivas variáveis.

A solução dual associada é usada para verificar se a inclusão de outras variáveis pode gerar

soluções melhores.

Sejam π ∈ R
m e σ ∈ R as variáveis duais associadas às restrições (5.13) e (5.14),

respectivamente. Quando a expressão (5.18) é satisfeita, uma nova coluna j e a variável

associada, podem ser úteis para a obtenção de uma solução melhor.

1−
( m∑

i=1

(q0jqijπi) + q0jσ
)
< 0 ⇔

m∑
i=1

(q0jqijπi) + q0jσ > 1. (5.18)

Manipulando algebricamente a expressão (5.18), obtemos o subproblema geração de

coluna (5.19) - (5.22). Resolvendo este subproblema verificamos se a solução ótima para

o (PCE-M) relaxado foi obtida.

Subproblema pricing de Vanderbeck [56]

ν = max q0j

( m∑
i=1

qijπi − σ
)

(5.19)

s.a

Qj = (q1j, q2j, . . . , qmj) é um padrão de corte factível, (5.20)

q0jqij ≤ bi, i = 1, . . . ,m, (5.21)

q0j, q1j, q2j, . . . , qmj ∈ Z+. (5.22)

Quando q0j é fixado, o subproblema (5.19) - (5.22) se reduz a um problema da mochila

restrito. Note que a informação dual associada à restrição (5.4) está incluída na geração

da coluna, uma vez que a variável q0j que controla a frequência do padrão de corte faz

parte do subproblema princing.

No problema (PCE-M) a informação sobre a dimensão do padrão de corte está im-

plícita. Assim, esta informação pode ser usada para resolver o problema de minimização



5.2 Técnica de decomposição para o PCE bidimensional com redução de ciclos 62

de padrões de corte, tanto no caso unidimensional quanto no caso bidimensional. Adap-

tar a formulação para o caso bidimensional consiste em formular de forma adequada a

definição de “padrão de corte factível” na definição do conjunto Q dada por (5.9). Na

seção 5.2 a seguir será discutida uma proposta para o uso das variáveis duas asssociadas

as restrições que controlam a frequência dos padrões de corte no subproblema princing

para o problema de ciclos da serra.

5.2 Técnica de decomposição para o PCE
bidimensional com redução de ciclos

Os métodos de solução baseados em geração de colunas para o (PCE-C) e (PCE-

CO) encontrados na literatura usam apenas a informação dual associada às restrições de

demanda no subproblema pricing. Nesta seção, apresentamos uma adaptação da proposta

descrita na seção 5.1 para incorporar no subproblema pricing informações duais relativas

ao número de ciclos da serra associado à frequência de um padrão de corte. Definimos o

conjunto Pd de acordo com a expressão (5.23).

Pd =

{
Aj ∈ Z

n : Aj é um padrão de corte bidimensional factível
}

(5.23)

Consideremos novamente problema (PCE-CO) descrito na seção 4.1, e reproduzido

por (5.24) - (5.28). Se as restrições (5.25) e (5.26) são dualizadas e a frequência dos

padrões de corte é fixada, o problema resultante consiste em determinar os padrões de

corte.



5.2 Técnica de decomposição para o PCE bidimensional com redução de ciclos 63

PCE com redução dos números de ciclos da serra e de objetos (PCE-CO)

ZPCE−CO = min
n∑

j=1

(xj + yj) (5.24)

s.a
n∑

j=1

Ajxj ≥ b, (5.25)

yj ≥ xj

cap
, j = 1, . . . , n, (5.26)

Aj ∈ Pd, j = 1, . . . , n, (5.27)

xj, yj ∈ Z+, j = 1, . . . , n. (5.28)

Note que o problema (PCE-CO), formado pelas expressões (5.24) - (5.28), é um pro-

blema não-linear, pois o conjunto de restrições (5.25) apresentam uma multiplicação de

variáveis. Seja Q o conjunto definido por (5.29) - (5.31).

Q =

{
qj = (q0j, q1j, q2j, . . . , qmj) ∈ Z

m+1
+ , j = 1, . . . , K :

Qj = (q1j, q2j, . . . , qmj) é um padrão de corte factível, (5.29)

y0j =

⌈
q0j
cap

⌉
(5.30)

q0j ∈ Z é a frequência do padrão de cortej
}
. (5.31)

O parâmetro y0j representa o número de ciclos da serra necessários para cortar q0j

objetos de acordo com o padrão de corte Qj. No caso bidimensional existem várias possi-

bilidades para definir se um padrão de corte Qj é factível (ver seção 3.2). Se associarmos

a cada elemento do conjunto Q uma variável binária δj, definida por (5.32),

δj =

{
1, se o padrão de corte Qj é usado com a frequência q0j,

0, caso contrário.
(5.32)

e supondo conhecidos todos os padrões de corte Qj, podemos reescrever o problema (PCE-

CO) como (5.33) - (5.36).



5.2 Técnica de decomposição para o PCE bidimensional com redução de ciclos 64

Problema mestre (PCE-CO-M) para o PCE redução ciclos e objetos

ZPCE−CO−M = min
∑
qj∈Q

(q0j + y0j)δj (5.33)

s.a ∑
qj∈Q

q0jQjδj ≥ b, (5.34)

(
y0j −

q0j
cap

)
δj ≥ 0, ∀qj ∈ Q, (5.35)

δj ∈ {0, 1}. (5.36)

Devido ao enorme número de colunas do tipo (5.37) e variáveis associadas, é indicado

resolver o problema (PCE-CO-M) usando um procedimento de geração de colunas.

⎛⎜⎜⎜⎜⎜⎜⎜⎜⎝

q0jq1j

q0jq2j
...

q0jqmj

y0j − q0j
cap

⎞⎟⎟⎟⎟⎟⎟⎟⎟⎠
(5.37)

O problema (PCE-CO-M) é relaxado mantendo as expressões (5.33) - (5.36) e substi-

tuindo as restrições (5.36) pelo conjunto de restrições (5.38).

0 ≤ δj ≤ 1 (5.38)

O problema mestre restrito inicial é obtido considerando os m padrões de corte ho-

mogêneos maximais. Assim, a matriz básica inicial é uma matriz diagonal. A resolução do

problema mestre restrito relaxado, permite a recuperação dos valores duais associados às

restrições (5.34) e (5.35). O subproblema pricing a ser resolvido a cada iteração do método

de geração de colunas, para verificar se existe uma nova coluna e variável associada que

melhore a solução do problema (PCE-CO-MR) é dado por (5.39).



5.2 Técnica de decomposição para o PCE bidimensional com redução de ciclos 65

min

{
(q0jy0j)−

(
m∑
i=1

(q0jqijπi) +
(
y0j −

q0j
cap

)
σ

)
: qj ∈ Q

}
(5.39)

Em (5.39), π = (π1, π2, . . . , πm) ∈ R
m e σ ∈ R são variáveis duais associadas às

restrições (5.34) e (5.35) do problema (PCE-CO-M) relaxado, respectivamente. Mani-

pulando algebricamente o subproblema (5.39), podemos reescrevê-lo como (5.40) - (5.43).

Subproblema pricing para o PCE redução ciclos e objetos

ν = max y0j(σ − 1) + q0j

(
m∑
i=1

(qijπi)− σ

cap
− 1

)
(5.40)

s.a

Qj = (q1j, . . . , qmj) é um padrão de corte bidimensional factível, (5.41)

y0j =

⌈
q0j
cap

⌉
, (5.42)

q0j, q1j, q2j, . . . , qmj ∈ Z+. (5.43)

Um limite superior qmax
0j para a frequência de um padrão de corte Qj é dado pela

expressão (5.44). Podemos observar que na formulação do subproblema (5.40) - (5.43)

está incluída a informação dual associada ao atendimento da demanda e do número de

ciclos da serra.

qmax
0j = max

i
{bi}. (5.44)

Para resolvermos o subproblema pricing, formado pelas expressões (5.40) - (5.43),

utilizaremos uma abordagem de “força bruta”, que deve enumerar q0j = 1, . . . , qmax
0j e

para cada valor de q0j resolver o subproblema pricing associado. Se fixarmos q0j então

y0j também será fixo, e assim a restrição (5.42) não é necessária. Para cada valor de q0j,

resolvemos o problema (5.45) - (5.48).



5.2 Técnica de decomposição para o PCE bidimensional com redução de ciclos 66

max

m∑
i=1

(qijπi) (5.45)

s.a

Qj = (q1j, . . . , qmj) é um padrão de corte bidimensional factível, (5.46)

qij ≤ χi(q0j) (5.47)

qij ∈ Z+. (5.48)

Em que os limites superiores para qij são dados por (5.49).

χi(q0j) = min

{⌊
L

li

⌋
,

⌊
W

Wi

⌋
,

⌊
bi
q0j

⌋}
. (5.49)

Assim, o processo que usamos para resolver o subproblema geração de colunas é:

Faça q0j = 1 e c = q0j + y0j.

Enquanto (q0j ≤ qmax
0j ) faça:

Calcule χi(q0j) para i = 1, 2, . . . , n de acordo com (5.49).

Faça de ν∗ =
c+ y0j
qmax
0j

(1−σ) + σ
cap

+ 1 um limitante inferior para (5.40) - (5.43).

Resolva o problema (5.45) - (5.48).

Faça ν∗ e q∗0j, valor ótimo e solução ótima de (5.45) - (5.48), respectivamente.

Se q∗0j(ν
∗ − σ

cap
− 1) > c faça c = q∗0j(ν

∗ − σ
cap
− 1).

Faça q0j = q0j + 1.

Fim-Enquanto.

Fim.



5.2 Técnica de decomposição para o PCE bidimensional com redução de ciclos 67

Caso o processo indique que existem colunas e variáveis associadas que melhorem a

solução atual do problema, elas devem ser incluídas no subproblema mestre restrito. Esse

procedimento é repetido até que nenhuma coluna possa ser incluída.



68

Capítulo 6

Conclusão e perspectivas futuras

Esta pesquisa teve como principal objetivo analisar o problema de corte de estoque

bidimensional, considerando a minimização de dois objetivos: número de objetos cortados

e número de ciclos da serra. Neste capítulo, relatamos os estudos realizados ao longo

desse trabalho e apresentamos as contribuições dadas. Também discutimos propostas

para continuar o trabalho e pontos que merecem uma melhor investigação.

Um ponto importante no desensolvimento deste trabalho foi a definição de qual modelo

matemático que trata de corte simultâneo de objetos seria utilizado para aplicar a técnica

que foi desenvolvida. Dessa forma, dedicamos as seções 4.2 e 4.3 deste trabalho para

discutirmos dois possíveis modelos matemáticos para representar o problema de ciclos

da serra, o modelo de Degraeve et al. [16, 17] e o de Chu e Antonio [13]. Entretanto,

concluímos que os dois modelos não representam o problema de ciclos da serra de forma

geral devido às características exclusivas do contexto para os quais são propostos.

A modelagem matemática do problema de corte de estoque bidimensional, que trata

da possibilidade da máquina de corte realizar o corte de diversos objetos simultaneamente,

exige a existência de uma restrição de preparo para controlar a frequência de uso de

um padrão de corte. Com o intuito de melhorar a eficiência computacional e acelerar

a convergência do método de geração de colunas aplicado na resolução de problemas

com essa característica, apresentamos na seção 5.2 uma técnica de decomposição para o

problema para melhorar a eficiência do método de geração de colunas. Em linhas gerais,

tal técnica consiste na decomposição do problema e incorporação da informação dual

associada às restrições de preparo no subproblema pricing que está associado ao método

de geração de colunas usado para resolver o problema. Essa abordagem permite a geração

de mais de uma coluna a cada iteração do método de geração de colunas.



6 Conclusão e perspectivas futuras 69

Sugerimos como próximos passos do trabalho:

- Implementar a técnica desenvolvida, realizar testes computacionais e compará-los

com os da literatura, em especial [52];

- Investigar a aplicação da técnica de decomposição em outros tipos de problemas de

otimização inteira, por exemplo o problema lot scheduling.



70

ANEXO A

Tipologias de classificação

A grande importância econômica e operacional dos problemas de corte de estoque, bem

como o grau de dificuldade de resolução, despertaram interesse de muitos pesquisadores

de pesquisa operacional e áreas relacionadas, na busca de métodos eficientes para sua res-

olução. Dyckhoff [20, 21] apresenta uma tipologia abrangente para classificá-los, tipologia

essa fundamentada com base nas características e estruturas lógicas comum desses pro-

blemas. O objetivo era unificar o uso das diferentes notações encontradas na literatura até

então e melhorar a comunicação entre os muitos pesquisadores do assunto, podendo assim

concentrar estudos em alguns tipos especiais de problemas. Foi neste trabalho também

que ocorreu a integração dos estudos de problemas de corte e empacotamento, já que até

então os problemas eram estudados separadamente.

Com o elevado número de publicações sobre PCE, a tipologia de Dyckhoff em [20, 21]

apresentou algumas limitações, tal como em que uma mesma classe de problemas era pos-

sível encontrar problemas com grande diversidade. Tendo isto em vista, Wäscher et al.

[58] desenvolveram uma nova tipologia parcialmente baseada na tipologia de Dyckhoff. A

nova tipologia acrescentou novos critérios de classificação à tipologia anterior, tornando

a classificação desses problemas mais abrangente que na tipologia em [20, 21] e não per-

mitindo mais que um problema tenha mais de uma classificação. A seguir descrevemos as

tipologias de Dyckhoff [20, 21] e Wäscher et al. [58].

A.0.1 Tipologia de Dyckhoff

Dyckhoff [20, 21] apresenta uma classificação para os PCE fundamentados sobre a

estrutura lógica dos mesmos e sobre suas principais características: dimensionalidade,

mensurarão das quantidades, forma dos objetos e itens, variedades de objetos e itens,



Anexo A Tipologias de classificação 71

disponibilidade, restrições de padrões, restrições de alocação, objetivos e "status"de infor-

mação. Todas essas características são reunidas em apenas quatro características básicas:

dimensionalidade, tipos de alocação, variedades de objetos e variedades de itens. Faremos

a seguir alguns comentários sobre essas características.

i. Dimensionalidade: é o número mínimo de dimensões necessárias para descrever

a geometria dos padrões, isto é, esta característica está associada com o número de

dimensões relevantes no processo de corte e/ou empacotamento. O autor afirma que

esta é a característica mais importante e segundo o autor os PCE são classificados

de acordo com a dimensionalidade em:

(1) Unidimensional: quando no processo de corte e/ou empacotamento apenas

uma dimensão é relevante e fixa, geralmente o comprimento, exemplos desses

problemas ocorrem no processo de corte de bobinas de papel, barras de aço,

etc.

(2) Bidimensional: quando no processo de corte e/ou empacotamento duas di-

mensões são relevantes e fixas. Neste caso, gerar um padrão bidimensional con-

siste em agrupar geometricamente os itens ao longo do comprimento e largura

dos objetos em estoque. Exemplos desses problemas ocorrem no processo de

corte de placas de vidros, chapas metálicas, painéis de madeira para a confecção

de móveis.

(3) Tridimensional: quando no processo de corte e/ou empacotamento mais de

três dimensões são relevantes e fixas. Gerar um padrão tridimensional consiste

em agrupar itens a objetos sem sobrepô-los onde se considera o comprimento,

a largura e a altura. Exemplos clássicos desses problemas ocorrem em car-

regamento de contenderes e o corte de espuma para a confecção de colchões e

travesseiros.

(N) N -dimensional, com N > 3: quando no processo de corte e/ou empa-

cotamento mais de três dimensões são relevantes. Neste caso, podem existir

dimensões não espaciais como tempo, memória, entre outros. Por exemplo,

um problema 4-dimensional pode ser obtido quando um problema de empaco-

tamento tridimensional no espaço tem o tempo como a quarta dimensão, tal



Anexo A Tipologias de classificação 72

como quando caixas devem ser armazenadas em contêineres com períodos fixos

de tempo sem interrupções.

Além das dimensões já citadas podemos encontrar também problemas N 1
2
-dimensio-

nais, denominados assim, pois têm N+1 dimensões, mas com uma das dimensões não

fixa. Denominado simplesmente ’N+1-dimensional’. Por exemplo, um problema 11
2
-

dimensional tem duas dimensões relevantes, porém apenas uma delas tem tamanha

fixo, podemos citar com exemplo de Problema 11
2
-dimensional um rolo de tecido

que tem largura fixa e comprimento relativamente grande, onde devem ser cortadas

peças para confecção de roupas.

ii. Tipo de alocação: nesta característica os itens demandados são associados de

acordo com as restrições impostas pela quantidade de objetos em estoque. De

acordo com esta tipologia, as duas associações que podem ser feitas para selecionar

os itens e objetos são:

(B) Todos os objetos e uma seleção de itens: quando em estoque não existe

uma quantidade de objetos suficientes para satisfazer a demanda de todos os

itens. Neste caso, seguindo algum critério de otimização é preciso fazer uma

seleção de quais itens serão cortados dos objetos. O problema da mochila e o

problema bin packing dual são exemplos de problemas com esta característica.

(V) Uma seleção de objetos e todos os itens: quando em estoque existe uma

quantidade de objetos suficientes para satisfazer a demanda de todos os itens.

Neste caso, é possível fazer uma seleção de quais objetos do estoque serão

cortados. São exemplos de problemas com esta característica o PCE clássico e

o problema bin packing.

iii. Variedade de objetos: essa característica classifica a diversidade dos tipos de

objetos que serão utilizados na solução do problema. Os três tipos de classificação

de variedades de objetos são:



Anexo A Tipologias de classificação 73

(O) Apenas um objeto: o problema com esta característica utiliza apenas um

tipo de objeto em sua solução. Exemplos de problema com esta característica

são o problema da mochila clássico e o problema de carregamento de palete.

(I) Objetos idênticos: os objetos utilizados na solução do problema têm todos a

mesma forma (entende-se, mesma forma como congruente). Os problemas bin

packing e PCE clássicos têm esta característica.

(D) Objetos diferentes: essa característica é utilizada para classificar problemas

em que objetos com diferentes formas são utilizados. O problema Bin Packing

bidimensional e o PCE que utiliza peças residuais de outros períodos, são

problemas com essa característica.

iv. Variedade de itens: é a característica que classifica a diversidade de itens deman-

dados de um problema. Os conjuntos de tipos de itens são:

(F) Poucos itens de diferentes formas: o problema com esta característica

tem poucos itens demandados e muita diversidade de formas entre eles. Por

exemplo, o problema de carregamento de veículos com aproximadamente 10

itens tem esta característica.

(M) Numerosos itens de muitas formas diferentes: esta característica aplica-

se a problemas onde muitos itens são demandados e com grande diversidade

de forma. O problema bin packing e o problema de alocação de memória, são

problemas com esta característica.

(R) Numerosos itens de poucas formas diferentes: são muitos os itens de-

mandados do problema, mas as formas desses itens são quase todas congru-

entes. O PCE bidimensional clássico é um exemplo de problema que tem esta

característica.

(C) Formas congruentes: todos os itens demandados do problema têm a mesma

forma geométrica. Por exemplo, o problema de carregamento de paletes.



Anexo A Tipologias de classificação 74

De acordo com a tipologia de Dyckhoff [20, 21] ao combinar as quatro características

apresentadas obtém-se 4 × 2 × 3 × 4 = 96 diferentes tipos de PCE. Essa tipologia é

representada por uma quádrupla ordenada com as siglas das características apresentadas

com a seguinte sequência: dimensionalidade / tipo de alocação / variedades de objetos /

variedades de itens.

A.0.2 Tipologia de Wäscher, HauBner e Schumann

Segundo Wäscher et al. [58] a tipologia de Dyckhoff de 1990 não foi suficiente para

acompanhar o desenvolvimento das pesquisas dos PCE. Assim, os autores apresentaram

uma nova tipologia, na qual pretendem evitar interpretações errôneas que poderem ocorrer

na tipologia de [20, 21] e aumentar o grau de aceitação entre os pesquisadores da área.

A nova tipologia apresentada em [58] é baseada na tipologia proposta por Dyckhoff

para classificar os PCE. Esta nova tipologia abrange uma maior quantidade de problemas,

que não eram classificados em [20, 21]. A tipologia de [58] classifica os PCE de acordo

com cinco características: dimensionalidade, tipo de alocação, variedades de itens, varie-

dades de objetos e formas de itens. Faremos alguns comentários a seguir sobre essas

características.

i. Dimensionalidade: considerada similarmente a Dyckhoff [20, 21], onde os PCE

são classificados de acordo com a sua quantidade de dimensões relevante em: uni-

dimensional, bidimensional, tridimensional e N -dimensional (N > 3).

ii. Tipo de alocação: é a característica que expressa à relação entre itens e objetos,

também é similar a classificação de Dyckhoff. Na caracterização de Wäscher et al.

[58] os problema se distinguem nesta característica em:

– Maximização da produção (output maximisation): um conjunto de itens

tem que ser atribuído para um dado conjunto de objetos, o a quantidade de

objetos disponível não é suficiente para satisfazer a demanda de itens. Nesse

caso, são utilizados todos os objetos e é feita uma seleção dos subconjuntos de