6
Algoritmo Evolutivo para o Problema de Corte de Estoque Unidimensional com Redução do Número de Padrões de Corte Henrique A. Kobersztajn 1 , Kelly C. Poldi 2 , Instituto de Ciência e Tecnologia, Unifesp 12231-280, São José dos Campos, SP E-mail: 1 [email protected], 2 [email protected] Silvio A. de Araujo Depto. de Matemática Aplicada, IBILCE, UNESP 15054-000, São José do Rio Preto, SP E-mail: [email protected] Resumo: Neste trabalho são apresentadas duas abordagens para a resolução do problema de corte de estoque unidimensional no qual dois objetivos são levados em consideração na obtenção da solução final: minimizar as perdas geradas durante o processo de corte e reduzir o número de padrões de corte diferentes. Estes dois objetivos, geralmente conflitantes, são tratados de forma independente nos métodos propostos neste trabalho. Nestas duas abordagens, considera- se ainda o caso dos objetos serem de apenas um tamanho e o caso dos objetos serem de tamanhos diferentes. Testes computacionais são realizados, mostrando a eficiência dos métodos propostos. 1. Introdução O Problema de Corte de Estoque (PCE) consiste em atender uma determinada demanda de itens através do processo de corte de objetos de certo tamanho em itens de tamanhos menores que as do objeto, visando atingir um objetivo como, por exemplo, minimizar a perda de material resultante do processo de corte. Com base em alguns problemas práticos, observou-se que em alguns casos outros critérios de otimização também são importantes e devem ser levados em consideração. Por exemplo, nos casos em que se tem escassez de capacidade, o tempo necessário para a troca de padrões de corte ganha significativa importância e, consequentemente, a redução do número de padrões de corte diferentes passa a ser um critério relevante. Para o PCE tratado neste trabalho, o processo de corte está vinculado a apenas uma dimensão, ou seja, é um problema de corte de estoque unidimensional, sendo então levado em consideração apenas o comprimento dos objetos e dos itens. Este trabalho apresenta duas formas de obter soluções para o PCE com redução do número de padrões de corte distintos, que consistem na integração de um Algoritmo Evolutivo (AE) proposto em [1], com uma classe de métodos propostos em [3], chamada KOMBI. Na primeira forma de integração, o AE que, a priori, trata de minimizar as perdas obtidas durante o processo de corte dos objetos gera uma solução para o PCE e então tenta-se reduzir o número de padrões de corte diferentes desta solução através dos métodos KOMBI. Após o processo de redução do número de padrões de corte, a solução obtida é a solução final encontrada por esta primeira abordagem. Na segunda forma de integração, o processo de redução do número de padrões de corte diferentes está entremeado ao AE na busca por soluções com a menor perda, fazendo com que soluções com o mínimo de padrões de corte participem do processo evolutivo do AE na geração de novas soluções com menores perdas e padrões de corte distintos possíveis. Essas duas abordagens propostas para o PCE unidimensional com redução do número de padrões de corte distintos tratam de dois tipos de problemas de corte de estoque: em um tipo, temos a produção de itens de comprimentos variados a partir de objetos de tipos diferentes (tamanhos diferentes), onde de acordo com a tipologia proposta em [10] é classificado como 1D- SSSCSP. O outro tipo de problema de corte de estoque considerado refere-se à produção de itens de comprimentos variados a partir de um único tipo de objeto, classificado como 1D-MSSCSP. Em ambos os casos, é considerado que existe uma quantidade de objetos suficiente para atender às demandas. O 1D-SSSCSP, onde o objetivo é minimizar as perdas de material, pode ser formulado como 408

Algoritmo Evolutivo para o Problema de Corte de Estoque ... · utilizados neste trabalho foram ajustados conforme aqueles informados em [1], a menos da proporção de indivíduos

  • Upload
    vucong

  • View
    220

  • Download
    1

Embed Size (px)

Citation preview

Algoritmo Evolutivo para o Problema de Corte de Estoque

Unidimensional com Redução do Número de Padrões de Corte

Henrique A. Kobersztajn1, Kelly C. Poldi2,

Instituto de Ciência e Tecnologia, Unifesp

12231-280, São José dos Campos, SP

E-mail: [email protected], 2 [email protected]

Silvio A. de Araujo

Depto. de Matemática Aplicada, IBILCE, UNESP

15054-000, São José do Rio Preto, SP

E-mail: [email protected]

Resumo: Neste trabalho são apresentadas duas abordagens para a resolução do problema de

corte de estoque unidimensional no qual dois objetivos são levados em consideração na obtenção

da solução final: minimizar as perdas geradas durante o processo de corte e reduzir o número

de padrões de corte diferentes. Estes dois objetivos, geralmente conflitantes, são tratados de

forma independente nos métodos propostos neste trabalho. Nestas duas abordagens, considera-

se ainda o caso dos objetos serem de apenas um tamanho e o caso dos objetos serem de tamanhos

diferentes. Testes computacionais são realizados, mostrando a eficiência dos métodos propostos.

1. Introdução

O Problema de Corte de Estoque (PCE) consiste em atender uma determinada demanda de

itens através do processo de corte de objetos de certo tamanho em itens de tamanhos menores que

as do objeto, visando atingir um objetivo como, por exemplo, minimizar a perda de material

resultante do processo de corte. Com base em alguns problemas práticos, observou-se que em

alguns casos outros critérios de otimização também são importantes e devem ser levados em

consideração. Por exemplo, nos casos em que se tem escassez de capacidade, o tempo necessário

para a troca de padrões de corte ganha significativa importância e, consequentemente, a redução

do número de padrões de corte diferentes passa a ser um critério relevante.

Para o PCE tratado neste trabalho, o processo de corte está vinculado a apenas uma

dimensão, ou seja, é um problema de corte de estoque unidimensional, sendo então levado em

consideração apenas o comprimento dos objetos e dos itens.

Este trabalho apresenta duas formas de obter soluções para o PCE com redução do número

de padrões de corte distintos, que consistem na integração de um Algoritmo Evolutivo (AE)

proposto em [1], com uma classe de métodos propostos em [3], chamada KOMBI. Na primeira

forma de integração, o AE que, a priori, trata de minimizar as perdas obtidas durante o processo

de corte dos objetos gera uma solução para o PCE e então tenta-se reduzir o número de padrões

de corte diferentes desta solução através dos métodos KOMBI. Após o processo de redução do

número de padrões de corte, a solução obtida é a solução final encontrada por esta primeira

abordagem. Na segunda forma de integração, o processo de redução do número de padrões de

corte diferentes está entremeado ao AE na busca por soluções com a menor perda, fazendo com

que soluções com o mínimo de padrões de corte participem do processo evolutivo do AE na

geração de novas soluções com menores perdas e padrões de corte distintos possíveis.

Essas duas abordagens propostas para o PCE unidimensional com redução do número de

padrões de corte distintos tratam de dois tipos de problemas de corte de estoque: em um tipo,

temos a produção de itens de comprimentos variados a partir de objetos de tipos diferentes

(tamanhos diferentes), onde de acordo com a tipologia proposta em [10] é classificado como 1D-

SSSCSP. O outro tipo de problema de corte de estoque considerado refere-se à produção de itens

de comprimentos variados a partir de um único tipo de objeto, classificado como 1D-MSSCSP.

Em ambos os casos, é considerado que existe uma quantidade de objetos suficiente para atender

às demandas.

O 1D-SSSCSP, onde o objetivo é minimizar as perdas de material, pode ser formulado

como

408

Minimizar

𝑓(𝑥) = ∑ (𝐿 − ∑ 𝑙𝑖𝛼𝑖𝑗

𝑚

𝑖=1

) 𝑥𝑗

𝑁

𝑗=1

(1)

Sujeito a:

∑ ɑ𝑗𝑥𝑗 = 𝑑𝑖 ,

𝑁

𝑗=1

𝑖 = 1, … , 𝑚, (2)

𝑥𝑗 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜; 𝑗 = 1, … , 𝑁, (3)

onde, L é o comprimento do objeto, N é o número de padrões de corte possíveis, li é o comprimento

do item do tipo i, m é a quantidade de tipos de itens, ɑj é o vetor correspondente ao j-ésimo padrão

de corte, 𝛼𝑖𝑗 é a quantidade de itens do tipo i no padrão de corte j, di é a demanda do item de tipo

i e xj é o número de vezes que o objeto é cortado segundo o padrão de corte j, j = 1, ..., N.

O vetor 𝑎𝑗 = (𝛼1𝑗, … , 𝛼𝑚𝑗) representa um padrão de corte se e somente se satisfizer

𝑙1𝛼1𝑗 + 𝑙2𝛼2𝑗 + ⋯ + 𝑙𝑚𝛼𝑚𝑗 ≤ 𝐿

0 ≤ 𝛼𝑖𝑗 ≤ 𝑑𝑖 , 𝑖 = 1, … , 𝑚; 𝑗 = 1, … , 𝑛 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠

O 1D-MSSCSP, visando minimizar as perdas, pode ser formulado como

Minimizar

𝑓(𝑥𝑗𝑘) = ∑ ∑ (𝐿𝑘 − ∑ 𝑙𝑖αijk

m

i=1

)

Nk

j=1

𝑥jk (4)

K

k=1

Sujeito a:

∑ ∑ ɑ𝑗𝑘 𝑥𝑗𝑘 = 𝑑𝑖 , 𝑖 = 1, … , 𝑚, (5)

𝑁𝑘

𝑗=1

𝐾

𝑘=1

∑ 𝑥𝑗𝑘 ≤ 𝑒𝑘, 𝑘 = 1, … , 𝐾, (6)

𝑁𝑘

𝑗=1

𝑥𝑗𝑘 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜; 𝑘 = 1, … , 𝐾; 𝑗 = 1, … , 𝑁𝑘, (7)

onde, K é o número de diferentes tipos de objetos em estoque, Nk é o número de padrões de corte

possíveis em relação ao objeto tipo k, Lk é o comprimento do objeto do tipo k, αijk é a quantidade

de itens do tipo i no j-ésimo padrão de corte do objeto do tipo k, xjk é o número de objetos do tipo

k a serem cortados conforme o padrão de corte j, ɑjk é o vetor que corresponde ao j-ésimo padrão

de corte do k-ésimo tipo de objeto, di é a demanda do item de tipo i e ek é a disponibilidade em

estoque do objeto tipo k.

O vetor 𝑎𝑗𝑘 = (𝛼1𝑗𝑘 , … , 𝛼𝑚𝑗𝑘) representa um padrão de corte se e somente se satisfizer

𝑙1𝛼1𝑗𝑘 + 𝑙2𝛼2𝑗𝑘 + ⋯ + 𝑙𝑚𝛼𝑚𝑗𝑘 ≤ 𝐿𝑘

0 ≤ 𝛼𝑖𝑗𝑘 ≤ 𝑑𝑖 , 𝑖 = 1, … , 𝑚; 𝑗 = 1, … , 𝑁𝑘; 𝑘 = 1, … , 𝐾 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠

2. Abordagens ao problema de corte de estoque

Os métodos propostos para a obtenção de soluções para o 1D-MSSCSP e 1D-SSSCSP,

com redução do número de padrões de corte distintos, consistem na integração do AE proposto

em [1] que visa a obtenção de uma solução com o mínimo de perda possível, com a classe de

métodos propostos em [3], denominada KOMBI, na tentativa de reduzir o número de padrões de

corte diferentes da solução gerada pelo AE.

O AE consiste em gerar uma população inicial de indivíduos (soluções factíveis), através

de adaptações da Heurística de Construção Exaustiva (Repeated Exhaustion Reduction (RER)),

proposta em [5], considerando um indivíduo como uma solução factível para o problema de corte

de estoque, sendo constituído de um vetor contendo um padrão de corte e também do número de

vezes que tal padrão é cortado.

Gerada a população inicial, inicia-se o processo de seleção onde será escolhido um

indivíduo que irá cooperar para a formação de um nova solução, levando em consideração que tal

indivíduo escolhido seja, com uma probabilidade ∆, um dos Ω indivíduos com melhor fitness. A

função fitness considerada é a mesma que a função objetivo. Após selecionado um indivíduo,

agora chamado de indivíduo pai, inicia-se a fase de cooperação. Nesta fase, escolhe-se

409

aleatoriamente um padrão de corte do pai e tenta incluir este padrão num novo indivíduo

(indivíduo filho) tantas vezes quanto for possível. Posteriormente, o processo de seleção é

executado novamente para escolher outro indivíduo pai, cujo padrão de corte a ser escolhido

aleatoriamente será incluso no filho. Este procedimento se repete até que a demanda dos itens seja

atendida, ou até que um parâmetro g seja atingido, onde g é um parâmetro previamente definido

baseado nas características da população.

Caso o parâmetro g seja atingido, o indivíduo filho ainda não constitui uma solução factível.

Então inicia-se o processo de auto-adaptação, onde será considerada a demanda residual dos itens

e uma adaptação da RER será utilizada para tornar o filho uma solução factível.

Gerado o indivíduo filho, seu fitness é calculado e comparado ao indivíduo com o pior

fitness existente na população. Se o novo indivíduo possuir melhor fitness, então ele substituirá o

pior indivíduo presente na população (população steady-state), caso contrário, será rejeitado.

O critério de parada do AE é definido como um número máximo de gerações de novos

indivíduos. Tal parâmetro é definido previamente no algoritmo.

Desta forma, os seguintes parâmetros necessitam ser ajustados de forma a se aplicar o AE:

o tamanho da população inicial, a quantidade de indivíduos gerados conforme cada uma das

adaptações da RER, a probabilidade de seleção de um indivíduo (parâmetros ∆ e Ω), quantidade

máxima de tentativas de inserção de um padrão de corte em um indivíduo (parâmetro g) e o

critério de parada.

Para ambos os problemas de corte de estoque 1D-MSSCSP e 1D-SSSCSP, os parâmetros

utilizados neste trabalho foram ajustados conforme aqueles informados em [1], a menos da

proporção de indivíduos gerados conforme cada uma das adaptações da RER para constituir a

população inicial no 1D-SSSCSP, cujas heurísticas para a formação da população inicial foram

reduzidas a apenas duas, diferentemente do caso 1D-MSSCSP onde um indivíduo é gerado

usando a RER1, 3 através da RER2, 3 usando a RER3 e 3 indivíduos gerados usando a RER4. Os

parâmetros constantes para ambos os problemas são: população inicial constituída de 10

indivíduos, 50% de probabilidade (∆) de escolher os 5 melhores indivíduos (Ω), parâmetro g

definido como a média da quantidade de padrões de corte presentes na população inicial mais um

percentual pré-estabelecido de 20% e o critério de parada foi estabelecido em 1500 iterações.

2.1. O problema de corte de estoque 1D-MSSCSP

A integração do AE com a classe de métodos KOMBI para resolução do 1D-MSSCSP se

dá de duas formas distintas: na primeira forma de integração, tanto o método KOMBI23 que tenta

reduzir 3 padrões para 2, e 2 para 1, quanto o método KOMBI234 que tenta reduzir 4 padrões

para 3, 3 para 2 e 2 para 1 são aplicados somente sobre a solução final obtida pelo AE (resultando

nos métodos MOEAK23-F e MOEAK234-F), ou seja, somente após o AE atingir o critério de

parada e o indivíduo com o melhor fitness ser eleito como solução final é que se dá o início do

procedimento de redução de padrões diferentes dos métodos KOMBI; na segunda forma de

integração dos métodos, os métodos KOMBI23 e KOMBI234 realizam o procedimento de

redução de padrões de corte diferentes a cada geração do AE (resultando nos métodos

MOEAK23-T e MOEAK234-T, respectivamente) de forma que os indivíduos pais já terão em

sua carga genética a quantidade mínima possível de padrões de corte diferentes que os métodos

KOMBI puderam reduzir e que serão transmitidas aos indivíduos filhos através do processo de

cooperação do AE. Desta forma, a busca pela solução com menor perda realizada pelo AE já

estará, de certa forma, imbuída da busca pela menor quantidade de padrões de corte diferentes.

2.2. O problema de corte de estoque 1D-SSSCSP

Uma adaptação do AE proposto em [1] foi realizada de forma a se obter soluções para o

PCE com um único tipo de objeto em estoque: as heurísticas de repetição exaustiva usadas em

[1] para a construção da população inicial foram reduzidas a apenas duas: a RER1 foi usada para

a construção de um único indivíduo e a RER2 (ver [1]), onde apenas a escolha dos itens é feita de

forma aleatória, foi utilizada pra a geração dos demais indivíduos da população. Então, da mesma

forma que no problema de corte de estoque com múltiplos tipos de objetos, foi realizada a

integração deste algoritmo evolutivo com os métodos KOMBI23 e KOMBI234.

410

A integração dos métodos KOMBI23 e KOMBI234 com o AE se dá da mesma forma como

no problema de corte de estoque 1D-MSSCSP, gerando os métodos SOEAK23-F, SOEAK23-T,

SOEAK234-F e SOEAK234-T. Um estudo computacional entre estes métodos propostos foi

realizado, de forma que o mais eficiente deles, o SOEAK234-T, foi eleito para comparações com

outros métodos propostos na literatura.

3. Resultados

3.1 Resultados para 1D-MSSCSP

O conjunto de dados utilizados para os testes computacionais foram obtidos através da

adaptação de [6] do gerador aleatório proposto em [9], sendo adequado ao problema de corte de

estoque onde temos vários tipos de objetos em estoque.

Este conjunto de dados é constituído de 18 classes com 20 instâncias cada. Os seguintes

parâmetros caracterizam as 360 instâncias geradas:

Número de objetos em estoque (K): 3, 5 e 7;

Número de tipos de itens (m): 5, 10, 20 e 40;

Comprimento dos objetos em estoque (Lk): os comprimentos para cada tipo de objeto foram

gerados aleatoriamente no intervalo [1, 1000];

Comprimento dos itens (li): os comprimentos foram aleatoriamente gerados no intervalo [v1 L,

v2 L], sendo v1 = 0.01 e v2 = 0.02 para gerar itens considerados pequenos e v1 = 0.01 e v2 = 0.08

para gerar itens considerados médios;

Estoque disponível dos objetos (ek): foram gerados aleatoriamente no intervalo [1, 50·m],

sendo m o número de tipos de itens;

Demanda dos itens (d): valores aleatoriamente gerados no intervalo [1, 10];

Tabela 1: Resultados obtidos e comparações entre métodos

A Tabela 1 mostra os resultados obtidos pelas diferentes abordagens para resolução do PCE

com vários tipos de objetos em estoque, levando em consideração as eficiências dos métodos em

relação à perda de material (colunas 𝑝𝑒𝑟𝑑𝑎 ) e o número de padrões de cortes distintos obtidos

AE MOEAK23-F MOEAK23-T MOEAK234-F MOEAK234-T

Classe 𝑝𝑒𝑟𝑑𝑎 𝑝𝑎𝑑𝑟õ𝑒𝑠 𝑝𝑒𝑟𝑑𝑎 𝑝𝑎𝑑𝑟õ𝑒𝑠 𝑝𝑒𝑟𝑑𝑎 𝑝𝑎𝑑𝑟õ𝑒𝑠 𝑝𝑒𝑟𝑑𝑎 𝑝𝑎𝑑𝑟õ𝑒𝑠 𝑝𝑒𝑟𝑑𝑎 𝑝𝑎𝑑𝑟õ𝑒𝑠

C1 59,35 3,55 59,35 3,40 61,35 3,30 59,35 3,40 61,35 3,30

C2 367,60 4,95 367,60 4,65 390,70 4,65 367,60 4,65 387,00 4,60

C3 16,30 9,90 16,30 7,90 16,10 7,75 16,30 7,55 13,45 7,25

C4 135,70 15,15 135,70 13,45 132,05 13,70 135,70 12,60 127,70 13,05

C5 9,60 18,55 9,60 13,80 6,90 13,40 9,60 12,50 9,60 13,25

C6 112,95 29,85 112,95 26,50 119,85 25,60 112,95 24,65 119,80 23,95

Média 116,92 13,66 116,92 11,62 121,16 11,40 116,92 10,89 119,82 10,90

C7 9,80 5,90 9,80 5,50 7,05 5,10 9,80 5,45 8,95 5,35

C8 262,30 8,10 262,30 8,00 266,70 7,95 262,30 7,95 259,65 7,85

C9 4,00 9,95 4,00 8,70 3,60 8,55 4,00 8,55 3,25 8,35

C10 100,60 15,85 100,60 15,65 103,35 15,25 100,60 15,35 101,25 14,55

C11 1,45 21,05 1,45 17,85 1,50 16,95 1,45 16,75 1,45 15,70

C12 128,75 34,50 128,75 32,95 129,20 30,95 128,75 32,30 122,35 29,65

Média 84,48 15,89 84,48 14,78 85,23 14,13 84,48 14,39 82,82 13,58

C13 5,85 5,95 5,85 5,85 6,20 5,75 5,85 5,80 5,65 5,80

C14 59,70 8,10 59,70 7,95 63,65 7,70 59,70 7,95 62,65 7,80

C15 1,05 10,40 1,05 10,00 1,35 9,20 1,05 9,90 0,85 8,80

C16 30,70 14,65 30,70 14,40 32,25 14,90 30,70 14,20 32,25 15,35

C17 0,15 20,20 0,15 18,00 0,15 17,25 0,15 17,10 0,45 15,70

C18 130,35 32,85 130,35 32,20 137,45 31,65 130,35 31,80 138,90 31,60

Média 37,97 15,36 37,97 14,73 40,18 14,41 37,97 14,46 40,13 14,18

411

(colunas 𝑝𝑎𝑑𝑟õ𝑒𝑠 ). Os resultados obtidos pelo AE proposto em [1] sem a integração com a classe

de métodos KOMBI foram mostrados para base de comparação. Pode-se notar que a média da

perda de material aumentou quando os métodos KOMBI234 são executados em cada iteração do

AE, entretanto ao executar os métodos KOMBI234 a cada iteração, a quantidade de padrões

distintos se mantém abaixo daquela obtida quando combinamos padrões distintos apenas na

solução final do AE. O mesmo é válido quando se executa os métodos KOMBI23.

3.2 Resultados para 1D-SSSCSP

O gerador aleatório CUTGEN1 proposto em [9] foi usado para gerar o conjunto de dados

utilizados nos testes computacionais. Dezoito classes com 100 instâncias cada foram geradas

aleatoriamente, com a mesma semente e parâmetros usados em [3], [11], [8], [4] e [2].

Os seguintes parâmetros caracterizam as 1800 instâncias geradas:

Número de tipos de itens (m): 10, 20 e 40;

Comprimento do objeto em estoque (L): 1000;

Comprimento dos itens (li): os comprimentos foram aleatoriamente gerados no intervalo [v1 L,

v2 L], sendo v1 = 0.01 e v2 = 0.2 para gerar itens considerados pequenos, v1 = 0.01 e v2 = 0.8

para gerar itens considerados médios e v1 = 0.2 e v2 = 0.8 para gerar itens considerados grandes;

Demanda média (dbar): 10 ou 100;

KOMBI234 HH ILS1.05 Symbio5 MOGA SOEAK234-T

Classe Σx Σδ(x) Σx Σδ(x) Σx Σδ(x) Σx Σδ(x) Σx Σδ(x) Σx Σδ(x)

C1 11,49 3,40 11,56 3,31 12,24 2,43 14,49 2,02 11,80 6,03 11,59 3,36

C2 110,25 7,81 110,40 6,95 114,49 3,18 116,26 5,28 112,06 9,56 110,86 6,81

C3 22,13 5,89 22,17 4,96 23,53 3,98 27,43 4,80 23,32 10,68 22,16 5,71

C4 215,93 14,26 215,98 10,32 223,92 4,89 236,89 9,86 222,22 20,83 216,62 12,69

C5 42,96 10,75 42,99 7,63 45,29 6,68 60,85 8,44 45,42 20,62 ----- -----

C6 424,71 25,44 424,89 13,31 442,00 7,25 518,81 14,16 432,57 45,32 ----- -----

Média 137,91 11,26 138,00 7,75 143,58 4,74 162,46 7,43 141,23 18,84 ----- -----

C7 50,21 7,90 51,69 7,66 51,35 5,52 53,05 5,48 54,94 8,41 50,27 7,88

C8 499,52 9,96 502,23 9,62 507,92 5,75 512,92 8,16 504,85 9,46 500,28 9,77

C9 93,67 15,03 99,49 13,64 96,35 10,05 99,41 10,47 99,37 14,38 93,79 14,53

C10 932,32 19,28 948,41 18,21 954,55 10,30 975,56 16,28 946,99 18,50 933,83 18,60

C11 176,97 28,74 195,67 24,60 182,88 18,32 201,43 22,24 188,20 29,08 177,26 27,44

C12 1766,20 37,31 1847,42 33,23 1818,35 18,40 1932,79 31,74 1789,50 38,14 1767,04 35,91

Média 586,48 19,70 607,49 17,83 601,90 11,39 629,19 15,73 597,31 19,66 587,08 19,02

C13 63,27 8,97 64,20 8,93 64,16 6,68 66,51 6,70 82,12 9,30 63,50 8,93

C14 632,12 10,32 633,26 10,51 637,03 6,85 646,31 8,30 638,20 10,02 632,88 10,36

C15 119,43 16,88 123,90 16,28 122,44 12,34 128,43 13,18 126,55 16,24 119,65 16,32

C16 1191,80 19,91 1197,66 19,89 1217,91 12,46 1253,79 16,57 1204,20 18,67 1193,43 19,58

C17 224,68 31,46 244,02 29,76 231,41 22,44 248,60 25,82 238,52 30,32 225,01 30,52

C18 2242,40 38,28 2268,30 37,90 2307,70 22,50 2419,34 32,03 2270,20 36,48 2245,39 37,38

Média 745,62 20,97 755,22 20,55 763,44 13,88 793,83 17,10 759,97 20,17 746,64 20,52

Tabela 2: Resultados obtidos e comparações com outros métodos

A Tabela 2 apresenta um comparativo entre o método SOEAK234-T e os métodos

propostos em [3] (KOMBI234), [11] (HH), [8] (ILS1.05), [4] (Symbio5) e [2] (MOGA), onde as

colunas referenciadas por Σx representam a média do número de objetos cortados (perda gerada)

e as colunas referenciadas por Σδ(x) representam a média do número de padrões de corte distintos,

para cada classe.

É importante salientar que o método SOEAK234-T demorou demasiadamente para a

obtenção da solução de 11 instâncias da classe 5 e de 40 instâncias da classe 6, sendo abortado

nestas classes e não contabilizado na média geral das classes 1 a 6.

412

Em relação ao número de objetos cortados, o método SOEAK234-T obteve resultados

melhores, para as classes 1 a 4, em relação aos métodos ILS1.05, Symbio5 e MOGA. Para as classes

7 a 18, apenas o método KOMBI234 foi mais eficiente que o SOEAK234-T.

De forma geral, ao comparar os métodos considerando tanto o número de objetos cortados

quanto o número de padrões de corte distintos, pode-se dizer que o método proposto é competitivo

perante os demais métodos encontrados na literatura. De acordo com a Tabela 2, podemos

observar que o método SOEAK234-T domina o método HH nas classes 14, 16 e 18, e domina o

método MOGA nas classes 1 a 4, 7 e 11 a 13, ou seja, para estas classes o método SOEAK234-T

é mais eficiente tanto para reduzir padrões de corte distintos quanto para minimizar a quantidade

de objetos cortados. Nas classes 1 e 4, o método HH domina o método SOEAK234-T, e apenas

na classe 1 e na classe 14, o método KOMBI234 com a heurística de [7] dominou o método

SOEAK234-T.

4. Conclusões

Neste trabalho foram apresentadas novas abordagens metaheurísticas para a resolução do

problema de corte de estoque unidimensional tendo por objetivo tanto minimizar o número de

objetos cortados quanto reduzir o número de padrões de corte distintos, sendo considerados os

casos em que temos em estoque apenas um tipo de objeto e o caso em que temos múltiplos tipos

de objeto em estoque, sendo que neste último caso, há poucos trabalhos publicados.

Os testes computacionais entre os vários métodos utilizados atualmente revelaram que o

método proposto possui boa eficiência, sendo competitivo entre os demais. Conclui-se que

nenhum método domina o método proposto, no sentido que tenham eficiência melhor tanto no

quesito número de objetos cortados quanto número de padrões de corte distintos gerados.

Para o caso em que temos múltiplos tipos de objeto em estoque, este trabalho contribui de

forma significante apresentando uma metaheurística para o problema de corte de estoque

unidimensional visando minimizar o número de objetos cortados e o número de padrões de corte

distintos, visto que trabalhos neste sentido são escassos na literatura.

Referências

[1] Araujo, Constantino, Poldi. An evolutionary algorithm for the one-dimensional cutting stock

problem. International Transactions in Operational Research. vol. 18, n. 1, pp. 274-294, (2010).

[2] Araujo, Florentino, Poldi. Multiobjective genetic algorithms to the one-dimensional cutting

stock problem. Anais do 25th EURO – European Conference on Operational Research, Vilnius,

Lituânia, pp. 155, (2012).

[3] Foerster, Wäscher. Pattern reduction in one-dimensional cutting stock problems. International

Journal of Production Research, vol. 38, n. 7, pp. 1657-1676, (2000).

[4] Golfeto, Moretti, SallesNeto. A genetic symbiotic algorithm applied to the one-dimensional

cutting stock problem. Pesquisa Operacional, vol. 29, n. 2, pp. 365-382, (2009).

[5] Hinxman. The trim-loss and assortment problems: a survey. European Journal of Operational

Research, vol. 5, pp. 8-18, (1980).

[6] Poldi, Arenales. Heurísticas para o problema de corte de estoque unidimensional inteiro.

Pesquisa Operacional, vol. 26, pp.473-492, (2006).

[7] Stadtler. A one-dimensional cutting stock problem in the aluminium industry and its solution.

European Journal of Operation Research, vol. 44, pp.209-223, (1990).

[8] Umetani, Yagiura, Ibaraki. One-dimensional cutting stock problem with a given number of

setups: A hybrid approach of metaheuristics and linear programming. Journal of Mathematical

Modelling and Algorithms, vol. 5, pp. 43-64, (2006).

[9] Wäscher, Gau. CUTGEN1: A problem generator for the standard one-dimensional cutting

stock problem. European Journal of Operational Research, vol. 84, pp.572-579, (1995).

[10] Wäscher, Haubner, Schumann. An improved typology of cutting and packing problems.

European Journal of Operation Research, vol. 183, pp. 1109-1130, (2007).

[11] Yanasse, Limeira. A hybrid heuristic to reduce the number of different patterns in cutting

stock problems. Computer & Operations Research, vol. 33, pp. 2744-2756, (2006).

413