ads:
CENTRO FEDERAL DE E DUCAÇÃO
TECNOLÓGICA DE MINAS GERAIS
Diretoria de Pesquisa e Pós-Graduação
Curso de Mestrado e m Modelagem
Matemática e Co mputacional
Algoritmos Evolutivos Mono e
Multiobjetivos para Problemas
Bidimensionais de Corte
Dissertação de Mestrado, submetida ao Curso de
Mestrado em Modelagem Matemática e Computa-
cional, como pa r te dos requisitos exigidos para a
obtenção do título de Mestre em Modelagem Ma-
temática e Computacional.
Aluno: Mariana Silva Faleiro de Andrade
Engenheira de Produção Civil (CEFET/MG)
Orientador: Prof. Dr. Sérgio Ricardo de Souza (CEFET/MG)
Co-Orientador: Prof. Dr. Marcone Jamilson Freitas Souza (UFOP)
Belo Horizonte, setembro de 20 09.
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Aos meus pais,
Carlos e Lúcia.
ii
ads:
Agradecimentos
Agradeço a Deus, pela incrível dádiva da vida e por ter colocado no meu caminho,
durante esse período, tantas pessoas boas, generosas e solidárias.
Agradeço aos meus pais, Carlos e Lúcia, pelo amor imenso e incondicional, pelo
calor do ninho e pelo constante incentivo, em todos os momento s da minha vida.
Ao meu orientador, Sérgio Ricardo de Souza, pela amizade dispensada desde os
tempos da graduação, pela extrema paciência, pela confiança, e, principalmente, por
acreditar em mim, tantas e tant as vezes, muito mais do que eu mesma.
Ao meu pro fessor e co-orientador Marcone Jamilson Freitas Souza, pelo conheci-
mento transmitido em sua disciplina, pela permanente boa vontade e pelas valio sas
sugestões durante o desenvolvimento deste trabalho.
Às minhas irmãs, Valéria e Siomara, pelo carinho e apoio durantes esses anos.
A minha irmã Isabela, por ser minha querida amiga e companheira de todas as
horas.
A minha irmãzinha Gabriela, por tornar minha vida mais alegre e mais leve neste
período tão atribulado.
A minha sobrinha Catarina, por ter chegado e po r ser a prova de que as pessoas
ainda têm esperança num mundo melhor.
Agradeço especialmente ao meu querido amigo, Elias, pela parceria na progra-
mação (pela paciência em me ensinar a programar) e pela generosa colaboração no
desenvo lvimento de todo este trabalho.
Agradeço, em especial, a o meu querido noivo Elias, por ser o amigo do agrade-
cimento anterior e por ser, ago ra, esse noivinho que tenta, a todo custo, me fa zer
feliz (t endo alcançado, muitas vezes, resultados ótimos).
A todos os professores que contribuíram para meu aperfeiçoamento , através das
disciplinas que cursei durante o mestrado.
iii
Aos colegas do CEFET-MG, em especial os irmãos Fábio e Felipe, que me in-
centivaram e com quem compartilhei bons momentos.
A CAPES e ao CEFET-MG, pela credibilidade e apoio financeiro.
Enfim, agradeço a todas as pessoas que contribuíram, direta o u indiretamente,
na elaboração deste trabalho.
iv
“O correr da vida embrulha tudo, a vida é assim: esquenta e esfria, aperta e da í
afrouxa, sossega e depois desinquieta. O que ela quer da gente é coragem.”
Guimarães Rosa
v
Resumo
Diversas indústrias têm a necessidade de cortar peças maiores, de modo a produ-
zir peças menores, atendendo a uma determinada demanda, ou, ainda, necessitam
empacotar peças menores. Estes problema são chamados de Problemas de Corte e
Empacotamento (PCE), e, geralmente, são problemas difíceis de serem solucionados,
sendo, muitos deles, classificados como problemas NP-Difíceis. Em muitas situações
reais, as peças maiores (objetos) e as peças menores (itens) possuem duas dimensões
relevantes para o corte, além de serem retangulares, como ocorre, por exemplo, no
corte de placas de madeira. Dentre estes problemas, classificados como Problemas
de Corte Bidimensionais, existem aqueles nos quais cada corte deve ser feito de
forma paralela a um dos lados do retângulo, se estendendo de um lado até o lado
oposto do objeto. Cortes que apresentam essa restrição são conhecidos como cortes
guilhotinados. Problemas com as características descritas acima são chamados de
Problemas de Corte Bidimensionais Guilhotinados. Métodos de solução para estes
problemas constituem o tema central dessa dissertação.
Foram estudados dois problemas de corte muito citados na litetatura: o Problema
de Corte com Dimensão Aberta (PCDA) (mais conhecido como Open Dimension
Problem ou Strip Packing Problem) e o Problema de Corte de Estoque Bidimensional
(PCEB). No primeiro, o corte para produção de itens retangulares é feito a partir
de um único objeto, que possui uma dimensão fixa e a outra grande o bastante para
cortar todos os itens, como ocorre no corte de rolos e bobinas. No problema de corte
de estoque, t emos vários objetos idênticos em estoque, com as duas dimensões fixas,
que devem ser cortados para a produção de itens com uma demanda pré-definida.
Devido à natureza NP-Difícil destes, desenvolvemos métodos heurísticos para sua
resolução, tendo em vista a comprovada eficiência destes métodos na solução de tais
problemas.
No PCDA, consideramos como critério de o t imização a minimização da perda de
material. Para solucioná-lo, utilizamos um algoritmo genético híbrido, que incorpora
a um algoritmo genético tradicional operadores de busca local e metaheurísticas,
em diferentes etapas do processo. Foram testadas diferentes metaheurísticas, assim
como diferentes métodos aproximados para o encaixe dos itens. Nos testes realizados
em pro blemas-teste da literatura, foram obtidas soluções ótimas em quase todos os
casos. O algo r itmo também mostrou um bom desempenho, em termos de tempo
de execução. Tais evidências empíricas mostram a possibilidade de utilização deste
algoritmo na resolução de problemas-teste associados a problemas reais.
No PCEB, consideramos como objetivos, além da minimização da perda, a mini-
mização do número de padrões distintos. Estes objetivos são, geralmente, conflitan-
vi
tes. Tratamos o problema com uma abordagem de otimização multiobjetivo, com o
intuito de o bter soluções que apresentem um compromisso entre os dois objetivos.
Para tanto, utilizamos um algoritmo evolutivo multiobjetivo, baseado no método
NSGA-II. Para a geração dos padrões, utilizamos um método de duas fases. Na
resolução do problema, ainda são utilizadas metaheurísticas em diversas partes do
algoritmo evolutivo. Nos testes realizados, na resolução de problemas da literatura
e de problemas gerados aleatoriamente, verificamos que o algoritmo é capaz de en-
contrar soluções competitivas em termos da perda de material, além de ser capaz
de encontrar um conjunto de soluções que mostram o compromisso entre os dois
objetivos. Verificamos também que o algoritmo apresenta curvas de trade-off que
melhoram ao longo das gerações. Ressaltamos que não foram encontramos traba-
lhos que tratassem do problema de corte bidimensional considerando os objetivos
de minimizar a perda e o número de padrões distintos.
Palavras-Chave: Problema de Corte com Dimensão Aberta, Problema de Corte
de Estoque Bidimensional, Metaheurísticas, Otimização Multiobjetivo.
vii
Abstract
This paper deals with the development of heuristic methods for solving two bidimen-
sional cutting problems: the Open Dimensional Problem (ODP) and the Cutting
Stock Multiobjective Problem (CSMP). In the first problem, given a set of rectan-
gular small items and a rectangular large object of fixed width a nd variable length,
the pro blem consists of placing all the items within the large object, such that the
material waste is minimised. To solve this problem, a hybrid genetic algorithm is
proposed, which incorporates local search and metaheuristics, in different stages of
the solution process, in one traditional genetic algorithm. Variations of this hybrid
algorithm are evaluated, a s well as different approximate methods to fit the items.
Computational experiments realized with instances from the literature show that
the proposed algorithms are able to reach the o ptimal solution in almost all cases.
The algorithms also showed a good performance in terms of run t ime. Such empi-
rical evidences indicate the possibility of using these algorithms to solve instances
associated with real problems. In the CSMP, several identical objects with two fi-
xed dimensions are in stock, which must be cut to the production of items with a
pre-defined demand. The objectives are to minimize loss mat erial and number of
different patterns. These objectives are usually conflicting. It is therefore a problem
with multiobjective optimization approach, in order to obtain solutions to present a
compromise between the two goals. A multiobjective evolutionary algor ithm, based
on NSGA-II method, is proposed to solve the problem. For the pattern generation,
it is used a two-staged method. Computational experiments realized with instan-
ces from the literature and randomly generated instances show that the prop osed
method is able to find a set of competitive solutions in terms of loss of material as
well as being able t o find a set of solutions that show compromise between the two
goals. The trade-off curves showed by the a lg orithm are improved over the genera-
tions. It is noteworthy that no research were fo und that addressed the problem of
two-dimensional considering simultaneously the objectives of minimizing both the
loss o f material a nd the number of distinct patterns.
Keywords: Open Dimensional Problem; Bidimensional Cutting Stock Problem;
Metaheuristic; Multiobjective O ptimization; Evolutionary Algorithm.
viii
Sumário
1 Introdução 1
1.1 Considerações Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Problemas de Corte e Empacotamento 5
2.1 Caracterização dos Problemas de Corte e Empacotamento . . . . . . 5
2.2 Tipologia de Dyckhoff . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Problemas de Corte Bidimensional . . . . . . . . . . . . . . . . . . . 11
2.4 Problema de Corte com Dimensão Aberta . . . . . . . . . . . . . . . 14
2.4.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.2 Revisão Bibliográfica . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.3 Formulação Matemática . . . . . . . . . . . . . . . . . . . . . 15
2.5 Problema de Corte de Estoque Multiobjetivo . . . . . . . . . . . . . . 17
2.5.1 Caracterização do Problema . . . . . . . . . . . . . . . . . . . 17
2.5.2 Revisão Bibliográfica . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.3 Formulação Matemática do Problema . . . . . . . . . . . . . . 23
3 Métodos Heurísticos 26
3.1 Otimização Combinatória Mono-objetivo . . . . . . . . . . . . . . . . 26
3.2 Heurísticas Construtivas . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Heurísticas de Refinamento . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.1 Método de Descida . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.2 Método de Descida Randômico . . . . . . . . . . . . . . . . . 29
3.4 Metaheurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4.1 Metaheurísticas baseadas em Busca Local . . . . . . . . . . . 30
3.4.2 Algoritmos evolutivos . . . . . . . . . . . . . . . . . . . . . . . 32
3.4.3 Algoritmos Genéticos Híbridos . . . . . . . . . . . . . . . . . . 38
3.5 Otimização Combinatória Multiobjetivo . . . . . . . . . . . . . . . . 38
3.6 Otimização Multiobjetivo Evolutiva . . . . . . . . . . . . . . . . . . . 41
3.6.1 Algoritmos Multiobjetivos baseados em Algoritmos Géneticos 42
4 Algoritmos Evolutivos aplicados ao PCDA 50
4.1 Representação de uma solução . . . . . . . . . . . . . . . . . . . . . . 50
4.2 Operadores genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.1 Operadores de Recombinação . . . . . . . . . . . . . . . . . . 53
ix
4.2.2 Operadores de Mutação . . . . . . . . . . . . . . . . . . . . . 53
4.3 Função de custo e função de aptidão dos indivíduos . . . . . . . . . . 54
4.4 Seleção dos indivíduos para a próxima geração . . . . . . . . . . . . . 55
4.5 Geração da população inicial . . . . . . . . . . . . . . . . . . . . . . . 56
4.5.1 Geração da população inicial - ILS . . . . . . . . . . . . . . . 56
4.5.2 Geração da população inicial - Multi-Start . . . . . . . . . . . 56
4.6 Experimentos Computacionais . . . . . . . . . . . . . . . . . . . . . . 56
4.6.1 Problemas teste para o PCDA . . . . . . . . . . . . . . . . . . 57
4.6.2 Resultados do AEH-MS . . . . . . . . . . . . . . . . . . . . . 59
4.6.3 Resultados do AEH-ILS . . . . . . . . . . . . . . . . . . . . . 60
4.7 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5 Algoritmo Evolutivo Multiobjetivo aplicado ao PCEB 63
5.1 Geração de Padrões . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.1 Etapa de Geração das Faixas . . . . . . . . . . . . . . . . . . 64
5.1.2 Etapa de Geração dos Padrões . . . . . . . . . . . . . . . . . . 69
5.2 Algoritmo Evolutivo Multiobjetivo aplicado a o Problema de Corte
Bidimensional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.2.1 Representação da solução . . . . . . . . . . . . . . . . . . . . 70
5.2.2 Geração da População Inicial . . . . . . . . . . . . . . . . . . 70
5.2.3 Avalia ção das soluções e Função de Aptidão . . . . . . . . . . 73
5.2.4 Operadores Genéticos . . . . . . . . . . . . . . . . . . . . . . . 75
5.3 Experimentos Computacionais . . . . . . . . . . . . . . . . . . . . . . 76
5.3.1 Problemas-teste de um indústria de móveis . . . . . . . . . . . 77
5.3.2 Experimentos com exemplos aleatórios . . . . . . . . . . . . . 80
5.4 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6 Conclusões Gerais e Trabalhos Futuros 85
6.1 Conclusões Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Referências 88
x
Lista de Tabe las
3.1 Método da Roleta: análise de aptidão. . . . . . . . . . . . . . . . . . 36
3.2 Método da Roleta: seleção. . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1 Problemas-teste de Hopper e Turton (2001) . . . . . . . . . . . . . . 58
4.2 Parâ metros dos métodos AEH
MS
e AEH
ILS
, sendo n o número de
itens do problema-teste. . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.3 Resutados do AEH
MS
aplicado ao PCDA. . . . . . . . . . . . . . . . 60
4.4 Resutados do AEH
ILS
aplicado ao PCDA. . . . . . . . . . . . . . . . 62
5.1 Exemplo de solução. . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2 Parâ metros do algoritmo. . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.3 Problemas-teste de Figueiredo (2 006)- Armário de 5 portas ( 15 mm). 78
5.4 Problemas-teste de Figueiredo (2 006) - Cômoda ( 12 mm). . . . . . . . 78
5.5 Resultados - Armário de 5 portas (15 mm). . . . . . . . . . . . . . . . 79
5.6 Resultados - Cômoda (12 mm). . . . . . . . . . . . . . . . . . . . . . 80
5.7 Problemas gerados aleator ia mente . . . . . . . . . . . . . . . . . . . . 80
5.8 Resultados Médios para os 10 exemplos de cada classe. . . . . . . . . 81
xi
Lista de Figuras
2.1 Problema de corte de bobinas. . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Problema de corte de placas: (a)Objetos em estoque, (b)Itens de-
mandados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Problema de carregamento de contêineres. . . . . . . . . . . . . . . . 6
2.4 Tipologia dos Problemas de Corte e Empacotamento. . . . . . . . . . 9
2.5 Estrutura Intermediária dos PCE - Minimização do consumo . . . . . 10
2.6 Tipos de corte: (a)Guilhotinado, (b)Não -Guilhotinado. . . . . . . . . 12
2.7 Exemplo de itens com orientação fixa e rotacionados. . . . . . . . . . 13
2.8 Problema de corte com dimensão aberta . . . . . . . . . . . . . . . . 14
2.9 Faixas no PCDA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.10 Problema de corte de estoque bidimensional. . . . . . . . . . . . . . . 17
2.11 Padrão de corte bidimensional. . . . . . . . . . . . . . . . . . . . . . . 18
2.12 Exemplo de problema de corte de estoque. . . . . . . . . . . . . . . . 19
2.13 Padrões do exemplo de problema de corte de estoque. . . . . . . . . . 20
2.14 Solução viável com 5 padrões. . . . . . . . . . . . . . . . . . . . . . . 20
2.15 Solução viável com 4 padrões. . . . . . . . . . . . . . . . . . . . . . . 21
3.1 pseudocódigo de Heurística Construtiva. . . . . . . . . . . . . . . . . 28
3.2 Pseudocódigo do método de descida. . . . . . . . . . . . . . . . . . . 29
3.3 pseudocódigo do Método de Descida Ra ndômico. . . . . . . . . . . . 30
3.4 Pseudocódigo da Metaheurística ILS. . . . . . . . . . . . . . . . . . . 31
3.5 Esquema do método ILS, para o caso de funções contínuas. . . . . . . 32
3.6 pseudocódigo do Método Multi-Start. . . . . . . . . . . . . . . . . . . 33
3.7 pseudocódigo de um AG simples. . . . . . . . . . . . . . . . . . . . . 34
3.8 Representação da Roleta - Seleção do primeiro indivíduo. . . . . . . . 36
3.9 Fronteiras geradas pelo método Fast-non-dominated-sort. . . . . . . . 45
3.10 pseudocódigo do procedimento Fast Non Domi nated Sort. . . . . . . . 46
3.11 Crowding distance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.12 Pseudocódigo do procedimento crowding distance. . . . . . . . . . . . 47
3.13 Pseudocódigo do procedimento NSGA-II. . . . . . . . . . . . . . . . . 48
3.14 Compo rt amento do NSGA−II. . . . . . . . . . . . . . . . . . . . . . . 49
4.1 Ação dos algor itmos a proximados First-Fi t e Best-Fit. . . . . . . . . 51
4.2 pseudocódigo do algoritmo First-Fit. . . . . . . . . . . . . . . . . . . 52
4.3 pseudocódigo do algoritmo Best-Fit. . . . . . . . . . . . . . . . . . . 52
4.4 Operador de Recombinação. . . . . . . . . . . . . . . . . . . . . . . . 53
4.5 Operador de mutação: troca. . . . . . . . . . . . . . . . . . . . . . . . 54
4.6 Operador de mutação: realocação. . . . . . . . . . . . . . . . . . . . . 54
xii
4.7 Pseudocódigo da Metaheurística ILS para geração de solução inicial
para o PCDA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1 Exemplo da Abordagem 1. . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2 Faixa formada pela Abordagem 1. . . . . . . . . . . . . . . . . . . . . 66
5.3 Pseudocódigo da Abordagem 1 para a geração de faixas. . . . . . . . 66
5.4 Pseudocódigo da Abordagem 2 para a geração de faixas. . . . . . . . 67
5.5 Faixas formadas pela Abordagem 2. . . . . . . . . . . . . . . . . . . . 68
5.6 Pseudocódigo da Abordagem 3 para a geração de faixas. . . . . . . . 68
5.7 Faixas formadas pela Abordagem 3. . . . . . . . . . . . . . . . . . . . 69
5.8 Padrões formados pela abo rda gem 1. . . . . . . . . . . . . . . . . . . 69
5.9 Crossover uniforme. . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.10 Fronteiras no problema dos armários de 5 portas. . . . . . . . . . . . 78
5.11 Fronteiras no problema das cômodas. . . . . . . . . . . . . . . . . . . 79
5.12 Curva de trade-off entre a perda e o número de padrões distintos no
exemplo da classe 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.13 Curva de trade-off entre a perda e o número de padrões distintos no
exemplo da classe 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.14 Curva de trade-off entre a perda e o número de padrões distintos no
exemplo da classe 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.15 Curva de trade-off entre a perda e o número de padrões distintos no
exemplo da classe 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.16 Curva de trade-off entre a perda e o número de padrões distintos no
exemplo da classe 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.17 Curva de trade-off entre a perda e o número de padrões distintos no
exemplo da classe 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
xiii
Capítulo 1
Introdução
Neste capítulo, além da introdução sobre o trabalho desenvolvido, são apresentados
os objetivos, motivação e organização do trabalho.
1.1 Considerações Iniciais
Problemas que envolvem o corte de matéria-prima são comuns a diversas ativi-
dades produtivas. Geralmente, deseja-se atender uma demanda por peças menores
(itens), que devem ser cortada s a partir de peças maiores (o bjetos), a um custo
mínimo. Isso ocorre, por exemplo, quando é preciso cortar placas de vidro para
produção de portas e janelas, ou cortar placas de madeira em peças menores, para
a confecção de móveis. Podem ser citadas ainda diversas indústrias, tais como as
de aço, papel, alumínio e espuma, em que situações como estas fazem par t e do
cotidiano industrial.
Geralmente, os problemas de corte têm como objetivo minimizar a quantidade
de material utilizado, ou seja, minimizar o número de objetos utilizados ou a perda
(desperdício) de material. Esses objetivos interferem diretamente sobre os custos da
produção. Entretanto, outro s custos podem ser importantes na atividade de corte,
como, po r exemplo, o tempo de preparação de máquina para a troca de padrões de
corte (setup), ou seja, o número de padrões de corte distintos utilizados, e os custos
de estoque para a produção excedente.
Outra at ividade comum nas indústrias, análoga à atividade de corte, é o empa-
cotamento de itens dentro de objetos, que ocorre, por exemplo, no carregamento
de containers. Devido à semelhança na estrutura lógica dos problemas de corte e
empacotamento, e à grande variedade de situações práticas que envolvem essas ati-
vidades, tais problemas foram agrupados em uma classe de problemas de o t imização
combinatória conhecidos na literatura como Problemas de Corte e Empacotamento
(PCE).
As pesquisas sobre o s PCE f oram iniciadas por Ka ntorovich (1960), sendo in-
tensificadas nos anos 60, a partir do trabalho de Gilmore e Gomory (1961). Desde
então, os PCE têm sido extensivamente tratados na literatura. Isso se deve a sua
importância econômica, aliada à dificuldade de resolução destes problemas. Nas
últimas duas décadas, vários artigos, de revisão bibliográ fica, relacionados ao pro-
blema de corte e empacotamento foram publicados, sendo relevante citar os devidos
1
1.1 Introdução 2
a Dyckhoff (1990), Sweeney e Parternoster ( 1992), Dowsland e Dowsland (1992) e
Wäscher et al. (2 006).
Um PCE, dependendo do número de dimensões relevantes para o corte ou empa-
cotamento, pode ser unidimensional (corte de barras de aço), bidimensional (corte
de placas de madeira) ou tridimensional (corte de espuma para produção de col-
chões). Existem, entretanto, diversos outros critérios necessários para definir um
PCE. Essa fato, somado à grande diversidade de problemas, originou a propo sição
de sistemas de classificação dos PCE.
O sistema mais recente de classificação é a tipo lo gia proposta por Wäscher et al.
(2006). Nela, são considerados aspectos como dimensionalidade, tamanho e varie-
dade dos itens e objetos, além de diversos outros critérios que buscam diferenciar e
definir de maneira única cada pro blema de corte.
Neste trabalho, são estudados os problemas de corte bidimensionais classificados,
segundo Wäscher et a l. (2006), como:
• Problema de Corte Bidimensional com Dimensão Aberta - PCDA (Open Di-
mensional Problem): o problema consiste em cortar da melhor for ma po ssível
um o bjeto retangular, dado que uma dimensão do obj eto é va r iável, para a
produção de itens retangulares. Esse problema ocorre, por exemplo, quando
a produção envolve o corte de itens a partir de uma bobina ou de um ro lo de
material. Diversos problemas de corte que surgem nas indústrias papeleira,
têxtil e metalúrgica podem ser modelados como um PCDA.
• Problema Bidimensional de Corte de Estoque - PCEB: trata-se do problema
classificado, segundo a tipologia de Wäscher et al. (200 6), como Single Stock-
Size Cutting Stock Probl e m - SSSCSP. Consiste em cort ar, da melhor maneira,
objetos retangulares idênticos disponíveis em estoque, de forma a produzir
itens também retangulares. Como exemplo, tem-se os problemas de corte da
indústria de móveis, que geralmente são modelados como um PCEB.
Como estes problemas são bidimensionais, ainda são acrescidas outras restrições,
além dos critérios propostos por Wäscher et al. (2006) . Tais restrições se devem
a detalhes do processo de produção e à características do equipamento de corte.
Dentre elas, estão as restrições relativas ao tipo de corte, que pode ser guilhotinado
ou não; à limitação no número de cortes em uma determinada direção (restritos
pelo equipamento); além de impo sições relativas à orientação do corte (com rotações
permitidas ou não), que acrescentam maiores dificuldades à resolução do problema.
Em geral, os PCE são formulados como problemas de otimização linear inteira
e são difíceis de serem tratados, devido ao grande número de variáveis envolvidas
e à restrição de integralidade das variáveis. Estes problemas pertencem à classe
de problemas NP-Difícil, o que significa que é improvável obter soluções exatas
em tempos computacionais razoáveis. Esse fato justifica a intensa utilização de
heurísticas para solução destes problemas.
Neste trabalho, para solucionar o PCDA, tendo como objetivo, a minimização da
perda de material, foram utilizados métodos heurísticos e algoritmos aproximados.
Os últimos são algoritmos desenvolvidos especificamente para a resolução do PCDA.
Quanto às heurísticas, f oram utilizados alg oritmos conhecidos como metaheurísti-
cas, que apresentam uma série de vantagens em relação aos métodos heurísticos
1.3 Introdução 3
convencionais, sendo que a principal delas é sua capacidade de escapar de ótimos
locais. Foram implement adas e comparadas, mais esp ecificamente, metaheurísticas
populacionais e metaheurísticas populacionais híbridas.
Na resolução do PCEB, foi considerado mais de um objetivo: buscou-se soluci-
onar o problema de forma a mostrar o compromisso entre a minimização da perda
de material e a redução no número de padrões distintos (tempo de preparação de
máquina - setup). Trata-se o problema, port anto, com uma abordagem multiobje-
tivo. Para gerar as soluções do problema, utilizou-se um método exato da literatura
(método das duas fases, Hifi e Hallah (2006) e (Morabito e Garcia, 1998)) para a
geração dos padrões de corte. Para a resolução do problema de corte de estoque
multiobjetivo , foi implementado um algoritmo evolutivo multiobjetivo, baseado em
um algoritmo bastante eficiente, conhecido como NSGA- II (Deb et al., 2002).
Para comprovar o potencial da técnica proposta e a possibilidade de sua utilização
em situações práticas, os algoritmos acima foram testados, utilizando-se problemas-
teste da literatura. Os resultados obtidos foram comparados com outros r elata do s
em t rabalhos anteriores.
1.2 Objetivos
O presente trabalho tem como objetivos principais:
• Desenvolver métodos heurísticos híbridos eficientes para a minimizar as perdas
no PCDA.
• Tr atar, através de uma abordagem da otimização multiobjetivo o PCBE, com
os objetivos de minimizar, simultaneamente, a perda e o número de padrões
distintos.
Mais especificamentte, este trabalho buscou:
• Testar algoritmos aproximados propostos na literatura para o encaixe de itens,
no PCDA.
• Combinar heurísticas de refinamento e metaheurísticas , tanto aquelas base-
adas em busca local quanto as metaheurísticas evolutivas (ou populacionais),
com o intuito de obter um algoritmo híbrido eficiente para solucionar o PCDA.
• Apresentar, com base nos modelos para o caso unidimensional, um modelo
matemático para tr atar o PCEB multiobjetivo.
• Gerar os padrões necessários à solução do PCBE, através de um método de
duas fases.
• Desenvolver um algoritmo evolutivo híbrido, inspirado nos algoritmos descritos
na literatura , para a resolução do PCBE.
• Analisar a adequação dos métodos de solução, através de testes com problemas
da literatura e instâncias geradas aleator ia mente.
1.4 Motivação 4
1.3 Motivação
A motivação para estudar e solucionar um problema de cort e vem, principal-
mente, do grande número de aplicações prá t icas deste problema. Em particular, os
problemas de corte bidimensional aparecem na fabricação de chapas de aço, vidro,
papel, móveis, dentr e outros.
Além disso, o estudo dos PCE por diversos autores tem contribuído de forma
significativa para o desenvolvimento de diversas áreas do conhecimento, tais como
programação linear, programação dinâmica, complexidade computacional, algorit-
mos de aproximação e metaheurísticas.
Os problemas de corte, ap esar de serem facilmente entendidos, têm uma natu-
reza complexa, sendo que muitos deles são comprovadamente problemas da classe
NP-Difícil. A dificuldade de resolução destes problemas levou ao emprego de mé-
todos heurísticos na resolução dos mesmos. Assim, além de solucionar o problema,
este trabalho foi motivado pelo interesse em estudar, desenvolver e combinar mé-
todos heurísticos, assim como verificar a adequação destes métodos a os problemas
estudados.
1.4 Organização do Trabalho
Este trabalho está organizado da seguinte maneira: no próximo capítulo, é feita
a caracterização dos problemas de corte estudados, além de u ma revisão bibliográ-
fica acerca do s PCE. No capítulo 3, são apresentados os conceitos básicos sobre
otimização mono e multiobjetivo, além de serem descritos os métodos de resolução
aplicados neste trabalho. No capítulo 4, é apresentada a metodologia de resolu-
ção do PCDA, além de serem descritos os testes computacionais e apresent ados os
resultados obtidos e sua respectiva análise. O capítulo 5 descreve os métodos de re-
solução do PCEB, além de apresentar os testes utilizados para validá-lo, assim como
os resultados obtidos. No capítulo 6, são apresentadas as conclusões do trabalho e
sugestões para trabalhos futuros.
Capítulo 2
Problemas de Corte e
Empacotamento
Neste capítulo, são apresentados os principais sistemas de classificação dos Pro-
blemas de Corte e Empacotamento (PCE), além de serem caracterizados, de uma
forma geral, os Problemas de Corte Bidimensionais (PCB) trat ados neste trabalho:
Problema de Corte com Dimensão Aberta e Problema de Corte de Estoque.
2.1 Caracterização dos Problemas de Corte e Em-
pacotamento
A estrutura lógica de diferentes PCE pode ser compreendida através de exemplos
como:
• O corte de bobinas de aço em estoque (Fig. 2.1(a)), que serão usadas para a
produção de bobinas menores (Fig. 2.1(b)), que devem ser produzidas para
atender a uma determinada demanda.
(a)
(b)
Figura 2.1: Problema de corte de bobinas.
5
2.2 Tipologia de Dyckhoff 6
• O corte de uma placa de vidro, ou de um pa inel de madeira, que consiste em
encontrar a melhor forma de cortar o o bjeto (Fig . 2.2).
(a)
(b)
Figura 2 .2 : Problema de corte de placas: (a)Objetos em estoque, (b)Itens deman-
dados.
• O corte de blocos de espuma para produção de colchões, ou o carregamento
de contêineres (Fig. 2 .3 ) .
Figura 2.3: Problema de carregamento de contêineres.
Os problemas apresentados mostram como são diversas as aplicações práticas dos
PCE. Em decorrência disso e devido à dificuldade de resolução desses problemas,
foram publicados, a partir dos ano s 60, diversos estudos tratando deste tema. Os
trabalhos pioneiros foram realizados por Kantorovich (1960), que apresentou mode-
los matemáticos de programação linear e métodos de solução para o planejamento
e organização da produção, e por Gilmore e Gomory (1961), que pro puseram uma
técnica de geração de colunas para obtenção de uma solução aproximada para os
problemas de corte.
A gra nde quantidade de estudos feitos a part ir de então levou Dyckhoff (1990) a
propor uma classificação que considera a estrutura lógica dos PCE e suas principais
características. Esta classificação é descrita a seguir.
2.2 Tipologia de Dyckhoff
Em Dyckhoff (1990) é apresentada uma sistematização dos diversos tipo de Pro-
blemas de Corte e Empacotamento (PCE). Os seguintes critérios são utilizados para
classificá-los:
2.2 Tipologia de Dyckhoff 7
1. Dimensionalidade: esta característica está relacionada com o número de
dimensões relevantes para o processo de corte. Um problema de corte pode
ser:
− Unidimensional: quando o corte do objeto é feito em apenas uma
dimensão, como ocorre no corte de bobinas de aço.
− Bidimensional: nesse caso, duas dimensões, largura e comprimento, são
relevantes para o problema. Esses problemas são encontrados, por exemplo,
nas indústrias de móveis e vidros.
− Tridimensional: nestes problemas, uma terceira dimensão é conside-
rada. Ele acontece, por exemplo, em empresas de transp orte, que querem
minimizar o número de viagens e, por isso, têm que empacotar as caixas nos
caminhões da melhor maneira possível.
− n-dimensional: ocorre quando mais de três dimensões são releva ntes
para o problema. Neste caso, além das dimensões dos objetos, outras carac-
terísticas do problema podem ser consideradas, como, por exemplo, o tempo
disponível para realizar os cortes.
2. Seleção de itens e objetos: os itens a serem produzidos são combinados
respeitando-se restrições associadas aos objetos. Itens e objetos podem ser
selecionados de acordo com as seguintes possibilidades de combinação:
− Alocar todos os objetos e uma pa r te dos itens.
− Alocar uma parte dos objetos e todos o s itens.
3. Sortimento dos Objetos: classifica o corte quanto à diversificação dos ob-
jetos. O corte pode ser realizado a partir de:
− Um objeto;
− Objetos idênticos;
− Objetos diferentes.
4. Sortimento dos itens: classifica o corte quanto à diversificação dos itens. O
conjunto de itens a serem cortados pode ser constituído de:
− Poucos itens (diferentes);
− Muitos itens de muitos tamanhos diferentes;
− Muitos itens com relativamente poucos tamanhos diferentes;
− Tamanhos congruentes.
A tipologia de Dyckhoff (1990) f oi um marco na pesquisa dos PCE, pois, ao
destacar a estrutura básica comum entre os problemas de corte e os problemas de
empacotamento, promoveu a integração dessas duas áreas de pesquisa, vistas até
então separadamente. No entanto, a tipologia de Dyckhoff tornou-se limitada para
acompanhar o desenvo lvimento dos estudos sobre o problema.
Motivado pela constatação das limitações da tipologia de Dyckhoff ( 1990) e pelo
crescente número de publicações sobre PCE, principalmente nas últimas duas déca-
das, Wäscher et al. (2006) desenvolveram uma nova tipologia, parcialmente baseada
2.2 Tipologia de Dyckhoff 8
na tipologia de Dyckhoff (1 990). Atualmente, a tipologia de Wäscher et al. (2006)
é utilizada em vários t r abalhos, além de ser adotada pelo European Special Interest
Group on Cutting and Packing (ESICUP) para fins de classificação de trabalhos.
Trata-se de uma classificação mais consistente e abrangente que a de Dyckhoff. Para
comprovar essa abrangência e a maior aplicabilidade de sua tipologia, em Wäscher
et al. (2006 ) é apresentada a classificação de diversos trabalhos da literatura, publi-
cados entre 1995 e 2002.
A nova tipologia introduziu novos critérios de classificação à tipologia de Dyckhoff
(1990), definindo, assim, novas categorias de problemas. A tipologia de Wäscher
classifica os PCE com base em cinco critérios:
1. Dimensionalidade: os problemas são divididos, segundo esse critério, em
problemas unidimensionais, bidimensionais e tr idimensionais.
2. Tip o de Designação (Alocação): Os problemas, de acordo com este crité-
rio, podem ter objetivos de:
• Maximização da produção (output max i misation): neste caso, os objetos
disponíveis não são suficientes para alocar todos os itens, ou seja, não é possível
produzir todos os itens. Como o objetivo é maximizar a produção dos itens,
serão utilizados todos os objetos. Assim, em geral, tem-se um problema de
seleção de itens;
• Minimização do consumo (input minim i sation): neste caso, os objetos
disponíveis são suficientes para alocar todos os itens. Assim, é necessário
acomodar todos os itens, buscando minimizar o valor dos objetos necessários
para o atendimento da demanda, de acordo com a função objetivo adotada,
que pode ser, por exemplo, o custo ou a quantidade de material desperdiçado.
3. Tip o dos Itens:
• Idênticos;
• Pouco heterogêneos;
• Muito heterogêneos.
4. Tip o de Objetos:
• Um único objeto:
− com todas dimensões fixas;
− com uma ou mais dimensões variáveis.
• Muitos objetos
− idênticos;
− pouco heterogêneos;
− muito heterogêneos.
5. Forma dos Itens:
• regulares;
• irregulares.
2.2 Tipologia de Dyckhoff 9
Problema de Corte e
Empacotamento
Minimização
da Entrada
Maximização
da Saída
Arbitrário
Fracamente
Heterogêneos
Problema da
Mochila
Problema de
Alocação
Open
Dimensional
Problem
Problema de
Corte e Estoque
Todas dimensões fixas
Dimensão(ões) variáveis
Todas dimensões fixas
Fortemente
Heterogêneos
Fracamente
Heterogêneos
Idênticos
Problema de
Empacotamento
de Itens Idênticos
Fortemente
Heterogêneos
Problema de
Empacotamento
Tipo de
Atribuição
Objetos
Tipo de
Itens
Figura 2.4: Tipolog ia dos Problemas de Corte e Empacotamento.
2.2 Tipologia de Dyckhoff 10
A partir do objetivo do problema e dos critérios apresentados acima, a classifi-
cação de um PCE, de acordo com a tipologia de Wäscher et a l. (20 06), é realizada
da seguinte maneira:
• Os critérios tipo de designação e tipo de itens são combinados, definindo assim
a estrutura básica do PCE. A estrutura básica dos PCE é apresentada na Fig.
2.4.
• Em seguida, o critério tipo de objetos é combinado a o problema básico, for-
mando assim a estrutura intermediária. Na Fig. 2.5, é apresentada a estrutura
intermediária para os problemas que possuem como objetivo geral a minimi-
zação da entrada. Este é o foco deste trabalho. Estão destacados nessa fig ura
os problemas a serem trat ados neste trabalho.
Mutiple Stock Size
Cutting Stock Problem
(MSSCSP)
Mutiple Bin Size
Bin Stock Problem
(MBSBSP)
Single Stock Size
Cutting Stock Problem
(SSSCSP)
Single Bin Size
Bin Stock Problem
(SBSBSP)
Residual
Cutting Stock Problem
(MSSCSP)
Residual
Bin Stock Problem
(MBSBSP)
Pouco
Heterogêneos
Muito
Heterogêneos
Idênticos
Pouco
Heterogêneo
Muito
Heterogêneo
Todas
Dimensões
Fixas
Um único objeto
com uma dimensão variável
Open Dimensional Problem
ODP
Tipo de
Itens
Tipo de
Objetos
Figura 2.5: Estrutura Intermediária dos PCE - Minimização do consumo
• Por fim, são adicionados os critérios d i mensionalidad e e fo rma dos itens à
estrutura intermediária do problema, sendo definida, assim, a classe do mesmo.
O resultado final da estrutura proposta por Wäscher et al. (200 6), p ortant o, é
dado pela seguinte regra:
{1,2,3}-D {retangular, circular, ..., irregular} {classificação intermediária}.
Nos termos da classificação de Wäscher, neste tra balho são estudados os proble-
mas de cort e classificados como:
• 2D - (Rectangular) Open Dimensional Problem - ODP: Problema de corte
bidimensional (r etangular) com uma dimensão aberta;
• 2D - (Rec tangular) Singl e Stock Size Cutting Stock Problem - SSSCSP: Pro-
blema de corte de estoque bidimensional ( r etangular ), com um único tipo de
objeto em estoque.
2.3 Problemas de Corte Bidimensional 11
Neste tr abalho, denota-se o Problema de Corte Bidimensional com Dimensão
Aberta apenas por PCDA, e o Problema do Corte de Estoque por PCEB.
O PCDA e o PCEB possuem as seguintes características em comum:
• São problemas bidimensionais (com objetos e itens retangulares);
• Os objetos disponíveis são suficientes para alocar todos os itens ( minimização
da entrada);
• Tr atam de itens muito heterogêneos.
As características que diferenciam os dois problemas são:
• Número de objetos: no PCDA, é utilizado um único objeto para cortar todos
os itens, ao passo que, no PCEB, são utilizados vários objetos idênt icos para
atender à demanda dos itens.
• Número de dimensões fixas: no PCDA, uma dimensão é fixa e a outra é
considerada infinita. No PCEB, as duas dimensões são fixas.
As características gerais dos problemas de corte bidimensional são discutidas na
próxima seção.
2.3 Problemas de Corte Bidimensional
O problema do corte bidimensional aparece quando, no processo de corte, os
objetos em estoque e os itens a serem produzidos possuem duas dimensões relevantes.
Este problema é bastante comum em indústrias que utilizam como matéria-prima
placas de vidro, aço, papel, plástico, couro, tecidos, madeira, dentre outros produtos.
A combinação dos itens dentro do objeto é chamada de padrão de corte. Os
padrões de corte, no caso bidimensional, devem obedecer a diversas restrições fí-
sicas impostas pelo tipo de material (por exemplo, no caso da madeira, quando é
necessário o corte ao longo de suas fibras) e aos equipamento d e corte (por exemplo,
quando há limitação no número de facas). Essas restrições têm que estar presentes
nos algoritmos desenvolvidos para solucioná-los. As características mais relevantes
e present es na literatura para problemas de corte bidimensionais são descritas a
seguir.
Tipo de corte
Em muitos casos, o equipamento de corte opera somente de forma paralela aos
lados do objeto e sempre corta o material de um lado ao outro. Este t ipo de corte
é conhecido como corte guilhotinado. Nesse tipo de corte, a cada corte são gerados,
sempre, dois retângulos, como pode ser visto pela Fig.2.6(a).
No caso contrário, ou seja, quando o corte descaracteriza o objeto (o corte con-
torna o item), o corte é dito não-guilhotinado, como na Fig.2.6(b)). Neste tr abalho,
para os dois pro blemas, consideram-se cortes guilhotinado s.
2.3 Problemas de Corte Bidimensional 12
1º
2º
2º
3º
3º
4º
3º
(b)
(a)
Figura 2.6: Tipos de corte: (a)Guilhotinado, (b)Não-Guilhotinado.
Estágios de corte
Como pode ser visto na Fig.2.6, no corte do tipo guilhotina ocorrem mudanças
ortogonais na direção do corte. Cada uma dessas mudanças, ou seja, cada sequência
de cortes, feitos na mesma direção, é chamada de estágio de corte. A Fig.2.6(a)
mostra o exemplo de um cort e em 4 estágios.
Em muitos processos de corte, o número estágios, deve ser limitado. Os cortes
guilhotinados, com estágios limitados, são muito comuns na indústria, devido ao
intenso uso de guilhotinas. Neste trabalho, para os dois problemas de corte, são
considerados cortes feitos em 2 estágios (o u seja, é necessária apenas uma mudança
na direção de corte).
Rotação do s itens
Em algumas indústrias, o material dos objetos possui uma característica que de-
termina a orientação do cort e (fibras de madeira, estampas em tecidos, etc). Quando
os itens não podem ser rotacionados, diz-se que os itens têm orientação fixa e, caso
contrár io , diz-se que os itens têm rotação permitida. Considere objetos com dimen-
sões L ×W e itens i de dimensões l
i
×h
i
. No caso de rotação permitida do s itens, se
o problema original tem n itens, o problema da geração de pa drões de corte passa
a ter, no máximo, o dobro do número de itens (2n), pois os itens tais que h
i
> L
ou l
i
> H não podem ser incluídos no padrão de corte depois de rota ciona dos. A
rotação dos itens pode permitir um melhor aproveitamento da matéria-prima, como
pode ser visto pela Fig. 2.7.
Quantidade de itens por padrão
Em problemas nos quais são usados mais de um o bjeto, pode haver uma limitação
na quantidade de vezes que um determinado item pode ser cortado a partir de um
objeto. Nesse caso, tra t a-se de um problema restrito. Caso contrário, tem-se um
problema irrestrito. Neste trabalho, ambos os problemas são considerados irrestritos.
2.4 Problemas de Corte Bidimensional 13
1
l
1
h
1
2
h
2
l
2
1
1 1
2
2
2
2
1
1 1
2
2
2
22 2
2
Itens não-rotacionados
Item 2 rotacionado
Figura 2.7: Exemplo de itens com orientação fixa e rotacionados.
Objetivos
Os objetivos relacionados aos problemas de corte podem envolver os itens, o
objeto, os padrões, ou ainda o processo de alocação. Exemplos de critérios de
otimização são:
• Minimização da quantidade de objetos utilizados;
• Minimização do custo dos objetos utilizados (neste caso, cada objeto deve t er
um custo a ssociado);
• Minimização do desperdício ( perda) nos padrões;
• Maximização do valor dos itens produzidos.
Apesar desses exemplos serem os mais tratados, existem outros objetivos con-
siderados, como a minimização do número de pilhas abertas (uma pilha é aberta
quando se inicia a produção (corte) de um determinado item, sendo fechada apenas
quando sua demanda é totalmente produzida) e a minimização do número de trocas
de padrões (que geralmente implicam em perda de tempo de produção (setup)).
Outros trabalhos ainda consideram mais de um objetivo. Um exemplo é o tra-
balho de Pileggi et al. (2006), no qual os autores buscaram minimizar, de forma
integrada, a perda de material e o número de pilhas abertas, considerando o com-
promisso entre os objetivos. Outro exemplo é o trabalho de Golfeto et al. (2007),
que desenvolveu um algoritmo genético simbiótico para o problema de corte unidi-
mensional multiobjetivo (minimização da perda de material e tempo de preparação
da máquina de corte (setup)).
Nesta dissertação, são desenvolvidos algoritmos para solucionar problemas de
corte com os seguintes objetivos:
• Para o PCDA: minimização da utilização do objeto;
• Para o PCEB: minimização da perda de material e minimização do número de
padrões distintos.
A seguir serão apresentados, para cada um dos problemas tratados neste traba-
lho, sua definição, caracterização e formulação matemática.
2.4 Problema de Corte com Dimensão Aberta 14
2.4 Problema de Corte com Dimensão Aberta
2.4.1 Definição
O PCDA é um problema que trata do corte em objetos com dimensões variáveis,
sendo, portanto, definido para itens e objetos com duas ou mais dimensões. Além
disso, usualmente este problema t r ata do corte de um único objeto. Conforme dito
no Capítulo 1, neste trabalho é tratado o PCDA bidimensional, com o objeto e os
itens retangulares.
Considerando estas características, o PCDA pode ser enunciado como na Defi-
nição 1 a seguir.
Definição 1 Dado um objeto com o comprimento (L) fixo e altura (H) gran de o
bastante para cortar todos itens, o PCDA cons i s te em determinar sobre ele o arranjo
de um conjunto de itens (l
i
× h
i
) que minimiz e a altura utilizada.
A Fig. 2 .8 ilustra o PCDA conforme definido.
Este problema ocorre, por exemplo, em fábricas de papel, ou de tecidos, onde
grandes rolos devem ser corta dos. A largura destes rolos geralmente é bem definida,
mas sua altura pode ser considerada infinita, pois é muito maior que a altura neces-
sária para cortar todos os itens demandados. O PCDA também é muito comum na
indústria de polímeros e na metalurgia.
Conforme dito na seção 2.3, o PCDA tratado neste trabalho considera que os
cortes são guilhotinados em 2-estágios e que os itens possuem orientação fixa.
L
Altura utilizada
l
i
h
i
Figura 2.8: Problema de corte com dimensão aberta
2.4.2 Revis ão Bibliográfica
O PCDA é bastante estudado, devido ao grande interesse teórico e prático des-
pertados por esse problema. O PCDA é encontrado na literatura, principalmente,
com o nome de (Rectang ular) Strip Packing Problem ou Two-Dimensional Strip
Packing Problem, conforme pode ser visto em Hopper e Turton (2001b), Martello
et al. (2003) e Yeung e Tang (2004). O utro nome foi dado por Jakobs (1996), Ho pper
2.4 Formulação Matemática 15
e Turton (2001a) e Martello et al. (2003), que o denominam de Orthogonal Rectan -
gular Strip Packing Problem, enquanto Lodi et al. (2004) denominam o problema
de Level Pac king Probl e m.
Diversos autores já mostraram que o PCDA pertence à classe dos problemas
NP-Difíceis (Hochbaum e Wolfgang, 1985), (Leung et al., 1990 ) . Esse fato, aliado
ao enorme número de aplicações práticas do problema, como, por exemplo, no corte
de bobinas de papel (Maculan, 1988), de tecido (Richter, 1992), de bobinas de
alumínio (Helmberg, 1995), dentre outras, são as principais motivações para que
vár ios t r abalhos na literatura tenham seu foco em técnicas para resolvê-lo.
Dentre os trabalhos que solucionam o PCDA de forma exata, podemos citar Hifi
(1998), que apresenta um método para o PCDA guilhotinado e com rotações orto-
gonais, baseado em um procedimento branch-a nd-bound, que soluciona problemas
de pequeno porte. Lesh et al. (2004) também apresenta um método baseado em
branch-and-bound para o PCDA sem perdas, para problemas com até 30 itens. No
entanto, os métodos exatos não se mostraram capazes de solucionar problemas de
grande porte, sendo estimulada, assim, a utilização de métodos heurísticos.
A maioria dos trabalhos que propõem uma solução heurística para o PCDA uti-
lizam algoritmos evolutivos, em especial algoritmos baseados em Algoritmos Gené-
ticos (AG). Dentre eles, podemos citar Yeung e Tang (2004), que tra t am um PCDA
não-guilhotinado através de uma heurística de encaixe de itens, que transforma o
PCDA em um simples problema de permutação, que, então é solucionado pelo AG.
Métodos baseados em AG também são apresentados em Kroger (19 95), Liu e Teng
(1999) e Yeung e Tang (2004). Uma revisão sobre a utilização de AG na resolução
do PCDA é feita em K r oger (1995).
Neste trabalho, para representar o PCDA, foi utilizado o modelo de programação
linear inteira proposto por Lodi et al. (2004 ) , apresentado a seguir.
2.4.3 Fo rmulação Matemática
O modelo de Lodi et al. (2004) trata do PCDA guilhotinado, de fo r ma que os
itens alocados no objeto formam faixas ou níveis (com a ltura corresponde à altura
do item mais alto da faixa), conforme indicado na Fig.2.9. Assim, minimizar a perda
de material corresponde, nesta formulação, à minimização da soma das alturas das
faixas.
1ª Faixa
2ª Faixa
Figura 2.9: Faixas no PCDA.
2.4 Formulação Matemática 16
As seguintes observações acerca do modelo são feitas no trabalho de Lodi et al.
(2004):
(i) Os itens são previamente ordenados de f orma decrescente com relação à altura;
(ii) Em cada faixa, o item mais à esquerda é o mais alto;
(iii) A primeira faixa é a faixa mais alta.
Sejam, então, os seguintes dados de um PCDA:
- L: comprimento do objeto;
- l
i
: comprimento do item, para i = 1, . . . , n.
- h
i
: altura do item, par a i = 1, . . . , n;
Sendo n o número de faixas formadas para alocar todos os itens demandados,
pode-se definir a seguinte variável de decisão:
• y
i
: é uma var iável binária que assume valor 1 se o item i inicializa a faixa i e
assume valo r 0 caso contrário.
Deve-se observar que, devido à observações (i) e (iii), somente os itens j, tais
que j > i, podem ser alocados na faixa iniciada pelo item i. Essa condição se deve
ao fato de que, se um item j, tal que j = i, inicializa a f aixa i, não pode ser atribuído
novamente a essa fa ixa. Assim sendo, uma segunda variável de decisão é dada por:
• x
ij
: variável binária, que assume valor 1 se o item j estiver alocado na faixa i
e assume va lo r 0 caso contrário,j > i.
O modelo de Programação Linear Inteira, segundo Lodi et al. (2004), é apresen-
tado a seguir:
min f =
n
i=1
h
i
y
i
(2.1)
sujeito a
j−1
i=1
x
ij
+ y
j
= 1, (j = 1, . . . , n); (2.2)
n
j=i+1
l
j
x
ij
≤ (L − l
i
)y
i
, (i = 1, . . . , n); (2.3)
x
ij
, y
i
∈ {0, 1}, ∀i, j (2.4)
A função objetivo, representada pela expressão (2.1), tem, como critério de oti-
mização, a minimização da altura utilizada do objeto. A restrição (2.2) gara nte que
cada item é alocado apenas uma vez, ou seja, ou o item inicializa a faixa ou está
2.5 Problemas de Corte de Estoque Multiobjetivo 17
numa faixa inicializada por outro item. A restrição (2.3) garante que, em cada faixa,
o comprimento L do objeto não será ultrapassada. A restrição (2 .4) define o tipo
das va riáveis do problema.
Ressalta-se que o modelo de Lodi et al. (2004) trata do PCDA restrito, enquanto
o present e trabalho considera o caso irrestrito. O modelo de Lodi et al. (2004) é
restrito, pois considera que todos os itens são de tipos diferentes, mesmo que tenham
as mesmas dimensões, ou seja, mesmo que sejam itens idênticos. Neste trabalho,
apesar de se considerar que os métodos propostos são aplicavéis a problemas irr es-
tritos, utilizou-se, para validar tais méto do s, o modelo de Lo di et al. (2004). Isso
pode ser feito, sem maiores problemas, porque é p ossível solucionar um problema
irrestrito utilizando o modelo de Lodi et al. (2004). Para isso, basta considerar os
itens com uma demanda d, t al que d > 1, com d itens com demanda igual a 1.
Assim, tranforma-se um problema irrestrito em um problema restrito.
O capítulo 4 apresenta a metodologia utilizada para a resolução do PCDA.
2.5 Problema de Corte de Estoque Multiobjetivo
2.5.1 Caracterização do Problema
Os problemas de corte de esto que bidimensionais (PCEB) consistem, de um
modo geral, em determinar a melhor maneira de se cortar objetos em estoque, com
dimensões L × H, de forma a produzir um conjunto de itens com uma demanda d
i
,
de dimensões l
i
× h
i
, e otimizar uma função objeto de interesse, como, por exemplo,
minimizar a perda de material. Neste trabalho, considera-se o comprimento (L)
como a dimensão horizontal e a altura (H) como a dimensão vertical. A Fig. 2.10
mostra um exemplo de problema de corte de estoque bidimensional.
h
i
1
2
3
4
5
6
l
i
C
Itens demandados
L
Objetos em estoque
H
7
Figura 2.10: Problema de corte de estoque bidimensional.
Para intr oduzir a formulação do problema de corte de estoque aqui trata do , é
necessário definir formalmente um padrão de corte.
Definição 2 Cada arranjo geométrico dos itens dentro do objeto é ch amado de
padrão de corte.
2.5 Problemas de Corte de Estoque Multiobjetivo 18
A Fig. 2.11 representa um exemplo de padrã o de corte bidimensional, utilizando o
objeto e os itens mostrados na Fig. 2.10.
1
1
4
2
3
6
6
6
1
Figura 2.11: Padrão de corte bidimensional.
A cada padrão de corte j está a ssociado um vetor n-dimensional:
a
j
= (α
1j
, α
2j
, . . . , α
nj
)
em que α
ij
corresponde a o número de vezes que o item i aparece no padrão j.
O vetor correspondente ao padrão mostrado da Fig. 2.11, considerando que são
demandados 7 itens diferentes, é dado por (3 1 1 1 0 3 0). As partes do objeto
cortado não utilizadas com o corte dos itens são denominadas perdas (representada
pela parte cinza na Fig. 2.11). Com elas, parte da matéria-prima, muitas vezes, fica
inutilizada, por não possuir as dimensões requeridas para a produção.
Considerando, entã o, conhecidos a priori todos os p padrões de corte possíveis, o
problema de corte de estoque pode ser formulado como (Gilmore e Gomory, 1961):
min
p
j=1
c
j
x
j
(2.5)
sujeito a
p
j=1
α
ij
x
j
≥ d
i
, (i = 1, . . . , n); (2.6)
x
j
≥ 0 e inteiro, (j = 1, . . . , p); (2.7)
em que c
j
é o custo associado ao padrão j, x
j
é o número de vezes que o padrão j é
utilizado e d
i
é a demanda de cada um dos itens. A função objetivo (2.5) minimiza
o custo dos objetos, as restrições (2.6) garantem que toda a demanda seja atendida
e as restrições (2.7) garantem que o número de vezes que cada pa drão de corte é
utilizado é um número inteiro não-negativo.
O custo c
j
tem valor c
j
= 1, ∀ j, no caso da minimização do número de objetos.
Caso o objetivo seja a minimização da perda, esse custo é substituído pela soma da
perda dos padrões que integram a solução. No caso de padrões bidimensionais, o
custo c
j
é dado por:
c
j
= LH −
n
i=1
α
ij
l
i
h
i
(2.8)
2.5 Problemas de Corte de Estoque Multiobjetivo 19
Esta f ormulação apresenta duas dificuldades em termos computacionais. A pri-
meira, é a resolução deste problema de programação linear inteira; a segunda, é
a determinação de todos os padrões, que em casos práticos, pode ser um número
muito grande, o que inviabiliza solucionar o problema otimamente.
Apesar da extensa literatura que trata do problema de corte com o objetivo de
minimizar a perda de material, na prática, existem outros objetivos importantes a
serem considerados. Um objetivo pouco citado na literatura, mas que tem consi-
derável importância em diversas indústrias, é a redução no número de padrões de
corte distintos.
A troca de padrões em um plano de corte demanda tempo (setup), podendo
aumentar consideravelmente o tempo total do processo de corte. Isso ocorre, por
exemplo, quando é preciso preparar um equipamento para cada novo padrão. Du-
rant e o tempo de preparação, os equipament os se encontram ociosos, o que pode
ocasionar uma diminuição na produtividade (Figueiredo, 2006 ) . Segundo Fogliatto
e Fagundes (2003), em média, 6,5% do tempo total de operação no setor de corte é
gasto pelo setup, podendo chegar a mais de 8%.
Assim, quando o custo de preparação para o corte de um novo padrão é signifi-
cativo, po de-se estar disposto a aceitar uma solução com um desperdício levemente
maior, mas com um número menor de padrões distint os.
Isso o corre, geralmente, porque reduzir o número de padrões distintos aumenta a
perda de material, ou seja, há um conflito de objetivos entre o diminuição da perda
de material e a diminuição do número de padrões de corte distintos. Daí o interesse
em avaliar os efeitos destes fatores em uma minimização global de custo (Limeira,
2003).
Considere, o seguinte exemplo de um problema bidimensional de corte de estoque,
mostrado na Fig. 2.12, que tem objetos de dimensõ es (L × H) em quantidade
ilimitadas em estoque, que devem ser cortados em itens menores de dimensõ es (l
i
×
h
i
), i = 1, 2, 3, para atender uma demanda d
i
de cada item.
35
30
Objetos
Itens ( )l ,h
i i
3
8
5
2
13
10
d
1
= 12 d
2
= 10
Demanda (d
i
)
d
3
= 40
1
15
16
Figura 2.12: Exemplo de problema de corte de estoque.
A partir dos itens, foram construídos os padrões de corte mostrados na F ig . 2.13,
a serem usados na solução do problema:
2.5 Problemas de Corte de Estoque Multiobjetivo 20
Padrões de Corte
1 1
1
11
11
111
2 2
22222
22
2
2
3
3
3
3
3
333
3
3
3
3 33
33
3
33
333 3
1
2
3
4
5
6
Figura 2.13: Padrões do exemplo de problema de corte de estoque.
Uma solução viável para este exemplo po de ser obtida utilizando-se cinco pa-
drões, mostrados na Fig. 2.14, que esquematiza uma solução viável, indicando a
freqüência de cada padrão, de modo a atender à demanda, além da perda de mate-
rial da solução.
Solução 1
Perda padrão = 14,3% 23% 18,3% 15,2% 8,6%
Freqüência = 1 2 2 2 1
Perda total = 17,0 %
11
1111
22
2222
22
2
2
33
333
33
333
3
3
3
3
3
3
3
3
3
3
3
3
11
Padrão: 1 2 3 5 6
Figura 2.14: Solução viável com 5 padrões.
No entanto, é possível encontrar uma outra solução viável alternativa com um nú-
mero menor de padrões de corte distintos (apenas 4), atendendo à mesma demanda,
conforme esquematizado na Fig. 2.15.
Tomando-se a segunda solução, pode-se obter uma redução nos custos produtivos
em que o tempo de preparação de máquina é significativo. No caso do exemplo
acima, o índice de perda de material foi menor na primeira solução. Esse fato é
comum em problemas práticos (maior número de itens), pois geralmente a redução
do número de padrões produz soluções com maior índice de perda.
Os trabalhos que tratam do problema de redução de padrões geralmente apre-
sentam as seguintes prio ridades relativas aos critérios de otimização:
• considerar como objetivo principal a redução de padrões. Conforme já dito,
isso resulta em soluções que utilizam uma quantidade maior de objetos. Ape-
nas quando o custo da matéria-prima for realmente insignificante, o número
de padrões deve ser individualmente minimizado.
• Combinar os dois objetivos, sendo que esta abordagem tem se mostrado a
2.5 Problemas de Corte de Estoque Multiobjetivo 21
Perda padrão = 23% 18,3% 22,3% 8,6%
Freqüência = 3 3 2 1
Perda total = 19,7 %
Solução 2
2
22 2
11
11
1
1
1 1
3
33
333
3
3
3
3
3
33
3
3
Padrão: 2 3 4 6
Figura 2.15: Solução viável com 4 padrões.
melhor para a realidade das aplicações industriais. Esta abordagem leva em
conta o compromisso (trade-off ) entre a perda e o número de padrões.
Observou-se, com relação ao s problemas de corte bidimensionais multiobjetivos,
que a literatura mostra-se bastante limitada com respeito aos problemas de corte
bidimensional. Este fato, aliado à dificuldade de resolução do problema, são as moti-
vações para que este trabalho tenha seu foco no problema de, conjuntamente, reduzir
os padrões e a perda de material num problema de corte de estoque bidimensional.
Neste t r abalho, o problema de corte de estoque bidimensional, considerando-se
os objetivos de minimizar a perda de material e o número de padrões, foi resolvido
através de uma abordagem multiobjetivo. Deve-se ressaltar que, na pesquisa biblio-
gráfica realizada, não foram encontrados artigos que tratassem desse problema para
o caso de o bjetos e itens bidimensionais.
A seguir, é apresentada uma revisão sobre o problema de corte de estoque e sobre
o problema de redução de padrões.
2.5.2 Revis ão Bibliográfica
O problema de corte de estoque fo i formulado inicialmente por Gilmore e Gomory
(1961) e Gilmore e Gomory (1963). A partir de entã o, diversos estudos foram
realizados, principalmente nas duas ultimas décadas. Existe, po r tanto, uma vasta
literatura sobre os problemas de corte de estoque.
A literatura a respeito dos problemas de corte de estoque bidimensionais também
é bastante extensa, conforme mostram os ar t ig os de revisão e edições especiais em
Bischoff e Wäscher (1995), Dyckhoff et al. (1997), Arenales et al. (1999), Wang
e Waescher (2002), Hifi (2002) e Lodi et al. (2002). Também tratam desse tema
os seguintes trabalhos: Gilmore e Gomory (1 965), Christofides e Whitlock (1977),
Wang (1983), Beasley (1985), Morabito e Arenales (1992), Yanasse et al. (1991),
Morabito e Arenales (199 6), Gramani (1996), Pinto (1999), Katsurayama (2002) ,
dentre outros.
No que se refere ao problema de redução de padrões, uma das referências mais
antigas é a de Haessler (1975), que propôs uma formulação para o problema de
2.5 Problemas de Corte de Estoque Multiobjetivo 22
corte de estoque unidimensional, considerando os custos da troca de padrões. Neste
método, um padrão é repetido se satisfizer determinados níveis de aspiração com
relação à perda e à freqüência.
O problema de redução de padrões é fortemente NP-difícil, mesmo quando o
problema de corte de estoque correspondente tem uma solução trivial (McDiarmid,
1999). Por essa razão, geralmente são encontradas abordagens heurísticas para sua
resolução. Uma revisão detalhada sobre os principais métodos heurísticos aplicados
ao problema de redução de padrões pode ser encontrada em Limeira (2003).
Dentre estes métodos, está aquele desenvolvido por P. e Gascon (1995). Nele, os
autores analisam quatro diferentes abordagens para o problema de corte de estoque:
1. Heurística de Haessler (1975);
2. Heurística utilizada pela companhia (estudo de caso);
3. SGPI: heurística baseada no método de resolução de Gilmore e Gomory, mi-
nimizando apenas a perda;
4. SGPI*: heurística baseada na adaptação da heurística de Haessler (1975) à
SGPI.
Foram realizados testes com as quatro heurísticas, em que fora m calculadas, para
cada uma, as perdas de material e o número de padrões distintos. O estudo concluiu
que a heurística de Haessler (1975) é a mais vantajosa, pois diminui a quantidade de
padrões distintos (em alguns casos, reduções maiores que 5 0%), mantendo o índice
de perda em um nível aceitável.
Em Diegel et al. (1993) é apresentado um método que identifica pares de padrões
que podem ser substituídos por um único padrão. Uma g eneralização deste método
foi feita por Foerster e Wäscher (2000), surgindo assim a heurística KOMBI, que
apresentou resultados melhores (apesar de um aumento no tempo computacional).
Morabito e Arenales (2000) analisam o compromisso entre cortar padrões mais
simples de serem produzidos e padrões que resultam em menores perdas de material,
apesar de reduzir a produtividade do equipamento de corte.
Vanderbeck (2000) apresenta um método exato para o problema de minimização
da troca de padrões de corte para problemas com um número pequeno de itens.
Umetami et al. (2003) apresentam um procedimento baseado na metaheurística
Iterated Local Search (ILS), em que, a priori, o número de diferentes padrões de
corte é limitado.
Em um estudo recente, Yanasse e Limeira (2006) apresentaram um algor itmo
híbrido para reduzir a quantidade de padrões de corte. Inicialmente, são gerados
padrões de corte com perda limitada, atendendo a demanda de no mínimo dois itens.
Em seguida, estes padrões são cortados o número máximo de vezes possível, sem
que ocorra produção excedente. Resta, então, um problema residual, sobre o qual é
aplicada uma técnica de r edução de padrões.
Quanto à literatura sobre a aplicação de métodos de otimização multiobjetivo,
destaca-se que foram encontrados apenas os trabalhos de Kolen e Spieksma (200 0) e
Golfeto et al. (2007), que tratam de problemas de corte de estoque unidimensionais.
2.5 Problemas de Corte de Estoque Multiobjetivo 23
O primeiro trabalho utiliza um método baseado em branch-and-bound para so-
lucionar problema de pequeno porte, com até 8 tipos de itens, sendo que os próprios
autores afirmam que o método somente se aplica a esta dimensão de problemas.
No segundo artigo, os autores desenvolveram um algoritmo genético simbiótico,
com uma estratégia de nicho, e testaram o método em problemas com até 20 ti-
pos de itens. Entretanto, não foram encontrados trabalhos que tratassem do corte
bidimensional através de um tratamento multiobjetivo.
Em vista das motivos apresentados, este trabalho traz uma abordagem multiob-
jetivo que visa encontrar soluções para o PCEB, que mostrem o compromisso entre
os seguintes objetivos:
(i) Minimização da perda de material;
(ii) Minimização do número de padrões distintos.
Neste trabalho, optou-se pela utilização de um algoritmo evolutivo multiobje-
tivo, em virtude dos bons resultados encontrados por este método em problemas da
mesma natureza. Na seção 3.5, é feita uma breve revisão sobre estes métodos.
Resta ainda observar que, conforme dito na seção anterior, os problemas de
corte bidimensional apresentam outras restrições, definidas pelo processo de corte.
No estudo do Problema de Corte Bidimensional, considera-se, no presente trabalho,
que os cortes são guilhotinados, irrestritos e com a rotação ortogonal dos itens
permitida.
2.5.3 Fo rmulação Matemática do Problem a
Considere os seguintes os seguintes dados de um PCEB:
• L: comprimento do objeto;
• H: altura do objeto;
• l
i
: comprimento do item i = 1;
• h
i
: altura do item i;
• d
i
: demanda do item i.
O problema de otimização multiobjetivo que visa minimizar o número de padrões
e a perda de material pode ser formulada como:
2.5 Problemas de Corte de Estoque Multiobjetivo 24
min(f
1
, f
2
) =
p
j=1
c
j
x
j
,
p
j=1
δ(x
j
)
(2.9)
sujeito a
p
j=1
α
ij
x
j
≥ d
i
, (i = 1, . . . , n); (2.10)
x
j
≥ 0 e inteiro, (j = 1, . . . , p); (2.11)
δ(x
j
) =
1, se x
j
> 0;
0, caso contrário.
(2.12)
c
j
= LH −
n
i=1
α
ij
l
i
h
i
(2.13)
em que p é o número de padrões de corte do problema, n é número total de itens,
α
ij
é número de vezes que o item i aparece no padrão j e x
j
é a variável de decisão
que representa o número de vezes que o padrã o j é utilizado (fr eqüência).
A expressão (2.9) minimiza os dois objetivos considerados: a perda de material,
dada pela função f
1
(que avalia a perda em área, dada pela soma da perda c
j
de cada
padrão mutiplicada pelo número de vezes que o padrão aparece na solução (x
j
)) e o
número de padrões distintos, dado por f
2
. A restrição 2.10 garante que a demanda
de to dos os itens é atendida. A restrição 2.11 garante que o número de vezes que
cada padrão é cortado é um número inteiro não negativo. As expressões 2.12 e 2.13,
mostram, respectivamente, a função que indica o uso ou não do padrão j e a função
que calcula a perda em área de cada padrão j.
Conforme apresentado na seção 2.5.1, os pa drões bidimensionais possuem carac-
terísticas especiais, em função dos equipamentos de corte e do tipo de material a
ser cortado. Algumas destas características podem ser introduzidas como restrições
no problema apresentado acima. Considerando que neste trabalho é permitida a
rotação ortogonal dos itens (desde que l
i
< H ou h
i
< L), para o caso de n itens, a
restrição (2.10) do problema de corte de estoque será dada por:
p
j=1
(α
ij
+ α
(i+n)j
)x
j
≥ d
i
, (i = 1, . . . , n); (2.14)
em que o item (i + n) corresponde a o item i rotacionado.
Segundo Golfeto et al. (2007), em problemas multiobjetivos discretos, mesmo que
lineares, como é o caso do problema descrito acima, nem sempre é possível obter
soluções através da resolução de problemas de programação linear, a o contrário de
problemas lineares multiobjetivos ( em que as soluções eficientes são obtidas pela
resolução de um problema ponderado).
Encontrar soluções que apresentam um compromisso entre os objetivos citados
pode ser de fundamental importância na prática, pois os custos envolvidos com o
2.5 Problemas de Corte de Estoque Multiobjetivo 25
processo de corte (material, tempo de preparação de máquinas) podem variar de
acordo com a variação da demanda. A partir disso, pode-se afirmar que a apre-
sentação destas soluções ao decisor pode contribuir de forma significativa para o
planejamento da produção (Golfeto et al., 2007). Fica demonstrada, assim, além da
relevância teórica, a importância prática deste problema. O capítulo 5 apresenta a
metodologia proposta de resolução do PCBE.
Capítulo 3
Métodos He ur ísticos
Este capítulo discute o s principais métodos heurísticos apresenta do s na literatura
para a resolução de problemas de otimização combinató r ia , com ênfase nos algorit-
mos evolutivos, foco deste trabalho.
3.1 Otimização Combinatória Mono-objetivo
Na sua forma geral, problemas de otimização têm como objetivo minimizar ou
maximizar uma função, dentro de certo domínio. Na teoria clássica da otimização,
são trata do s os casos em que esse domínio é infinito. Nos problemas de otimização
combinatória, entretanto, esse domínio é tipicamente finito, sendo, portanto, possível
a enumeração de seus elementos, assim como verificar se um elemento pertence ou
não a esse domínio. No entanto, testar todos os elementos desse domínio em busca do
melhor, mostra-se, em geral, inviável na prática, mesmo para problemas de tamanho
médio.
Muitos problemas de otimização combinatória são classificados como NP-Difíceis,
o que significa que, at é hoje, não existe um algoritmo que seja capaz de obter a
solução ótima desses pro blemas em tempo polinomial.
Devido à essa característica, o uso de métodos exatos torna-se ba stante limi-
tado. No entanto, na prática, é satisfatório encontrar uma boa solução, num tempo
razoável, em vez da solução ótima, que pode demandar muito tempo e grande es-
forço computacional. Tais soluções podem ser obtidos pelo uso de heurísticas. As
heurísticas buscam soluções próximas da otimalidade, em um tempo computacional
razoável, não sendo, no entanto, capaz de definir se esta é a solução ótima, nem
quão distante ela está da solução ótima. O esforço das pesquisas nessa área se con-
centram, portanto, em métodos que obtenham soluções o mais próximas possíveis
da solução ótima, em menores tempos de execução.
Muitas heurísticas foram desenvolvidas para resolver uma classe particular de
problemas. Somente na década de 1980 começaram a ser criados métodos heurísticos
com um caráter mais geral, que podem ser aplicadas a uma variedade maior de
problemas. Esses procedimentos heurísticos foram chamados de metaheurísticas,
sendo que sua característica básica é uma menor rigidez, quando comparadas aos
métodos clássicos de resolução de problemas de otimização. Segundo Blum e Roli
(2003), as metaheurísticas se fundamentam nas seguintes propriedades:
26
3.2 Heurísticas Construtivas 27
• O objetivo é explorar eficientemente o espaço de busca, para encontrar soluções
próximas do ótimo (em um problema de otimização combinatória definido por
um conjunto de variáveis X = (x
1
, x
2
, ..., x
n
), um conjunt o de restrições sobre
as variáveis e uma função obj etivo, o espaço de busca é o conjunto de todas
as soluções factíveis para o problema, o u seja, todas aquelas que satisfazem o
conjunto de restrições);
• Os algoritmos de metaheurísticas variam de um simples procedimento de busca
local a processos complexos de aprendizagem;
• As metaheurísticas devem incorporar mecanismos capazes de escapar de ótimos
locais;
• Metaheurísticas não são voltadas para a solução de problemas específicos;
• Metaheurísticas podem utilizar exp eriências de busca para guiar sua busca.
As metaheurísticas têm, portanto, o objetivo de guiar a exploração do espaço de
busca utilizando diversas estratégias. Dentre as estratégias que permitem escapar de
ótimos locais, estão os movimentos de piora da solução, geração de novas soluções
iniciais e o uso de memória (baseada em decisões tomadas anteriormente ou em
experiências de busca), ou, até mesmo, decisões probabilísticas.
No enta nto, os melhores resultados encontrados com uso de metaheurísticas fo-
ram obtidos a pa rt ir de técnicas de hibridismo (Blum e Roli, 2003) . Um algoritmo
híbrido combina uma ou mais metaheurísticas e/ou estratégias, com o objetivo de
melhorar o desempenho da busca. A utilização de operadores de busca local em
métodos como os algoritmos evolutivos é uma forma de hibridismo.
As metaheurísticas utilizam, em seu processo de busca, heurísticas subo rdinadas,
métodos de construção e refinamento (melhoria) das soluções. Geralmente, para a
fase de refinamento, as metaherísticas utilizam métodos baseados em busca local.
Estes métodos buscam soluções, trocando, sistematicamente, a solução corrente por
uma solução melhor, contida numa vizinhança previamente definida. Os métodos de
construção geram uma solução inicial, ou um conjunto de soluções para o problema.
Tais soluções são geradas, geralmente, de forma aleatória o u através de heurísticas
ou metaheurísticas.
As subseções 3.2 e 3.3 descrevem com detalhes estas heurísticas. A subseção
3.4 faz uma introdução sobre as metaheurísticas que serão aplicadas aos problemas
tratados neste trabalho.
3.2 Heurísticas Construtivas
As heurísticas construtivas são responsáveis pela construção de uma solução viá-
vel para um dado problema. Essas heurísticas constroem uma solução s, elemento
por element o, de acordo com a função de avaliação escolhida, que, por sua vez,
depende do problema em questão.
O procedimento geral das heurísticas construtivas pode ser visto no pseudocódigo
representado pela Fig. 3.1.
3.3 Heurísticas de Refinamento 28
procedimento HeuristicaConstrutiva(f(·), s)
1 s ← ∅;
2 Inicialize o conjunto C de elementos candidatos
3 enquanto (C = ∅) faça
4 e ← escolha um elemento e do conjunto C
5 s ← s ∪ e;
6 Atualize o conjunto C de elementos candidatos
7 fim-enquanto;
8 Retorne s;
fim HeuristicaConstrutiva();
Figura 3.1: pseudocódigo de Heurística Construtiva.
Nas heurísticas clássicas, geralmente o s elementos da solução são ordenados por
uma função gulosa, que avalia a melhora trazida por cada elemento. Assim, a cada
iteração, o melhor elemento é escolhido.
Os elementos também podem ser escolhidos de forma aleatória, sendo este o tipo
mais simples de construção.
As construções g ulosas geralmente apresentam resultados muito melhores, quanto
à obtenção de valores próximo do ótimo da f unção, quando comparadas à construção
aleatória. No entanto, apresentam a desva ntagem de que uma decisão tomada na
inserção de um elemento não pode ser alterada. Se a decisão for ruim, não existe
a possibilidade de corrigí-la. Além disso, as soluções finais geradas por esse tipo de
heurísticas a presentam uma diversidade muito pequena, ainda que sejam utilizadas
regras para conduzir a procura. Essas desvantagens podem ser minimizadas com a
utilização de uma componente aleatória na construção.
Geralmente, a s heurísticas construtivas (gulosas e aleatórias), aplicadas de forma
isolada, não resultam em soluções de bo a qualidade, necessitando de métodos de
refinamento dos resultados o btidos. Esses métodos são discutidos a seguir.
3.3 Heurísticas de Refinamento
As heurísticas de r efinamento, ou técnicas de Busca Local, são métodos que
tentam melhorar uma solução, encontrada inicialmente a partir de métodos cons-
trutivos. Essas heurísticas são baseadas na noção de vizinhança.
Definição 3 Uma estrutura de vizinhanç a é uma função N : S → 2
S
, que define,
para todo ponto s ∈ S, um conjunto de vizinhos N (s) ⊆ S. O conjunto N (s) é
chamado d e vizinhança do ponto s.
Uma solução s
′
faz parte da vizinhança da solução s se, e somente se, s
′
é
resultado de uma modificação em s, causada por um determinado movimento m, de
tal maneira que continue a fazer parte do conjunto de soluções possíveis.
A seguir, são apresentados dois métodos clássicos de busca local.
3.4 Metaheurísticas 29
3.3.1 Método de Descida
O Método de Descida parte de uma solução inicial s qualquer e, a cada passo,
analisa todos os seus possíveis vizinhos (considerando uma vizinhança N (s) qual-
quer), movendo-se somente para aquele que apresentar uma melhora no valor atual
da função de avaliação. Assim, o método pára quando um ótimo local é encontrado.
A Fig. 3 .2 mostra o pseudocódigo do a lgoritmo.
procedimento Descida(f(·), N (·), s)
1 V = {s
′
∈ N (s) | f(s
′
) < f(s)};
2 enquanto (|V| > 0) faca
3 Selecione s
′
∈ V, sendo s
′
= arg min{f(s
′
) | s
′
∈ V};
4 s ← s
′
;
5 V = {s
′
∈ N (s) | f( s
′
) < f(s)};
6 fim-enquanto;
7 Retorne s;
fim Descida;
Figura 3.2: Pseudocódigo do método de descida.
3.3.2 Método de Descida Randômico
O Método de Descida Randômico é uma va riação do Método de Descida. Este
método parte de uma solução inicial qualquer e, a cada iteração , escolhe aleato ria-
mente uma estrutura de vizinhança, que é aplicada à solução corr ente. Em seguida,
analisa um vizinho qualquer, movendo-se somente para o vizinho que representar
uma melhora estrita no valor atual da função de avaliação. O método é interrom-
pido após um número fixo de iterações sem melhora no valor da melhor solução
obtida até então.
A Fig. 3 .3 apresenta o pseudocódigo do método de descida randômico.
3.4 Metaheurísticas
Como visto na seção anterior, as heurísticas de construção e de refinamento, em
geral, ficam presos em um ótimo local. Aí reside a inovação das metaheurísticas,
pois estas têm a capacidade de escapar de ótimos locais. Isso é feito através de
estratégias que permitem uma melhor exploração do espaço de busca.
As metaheurísticas são definidas, de acordo com Osman e Laporte (1996), como
um processo de geração iterativo, que guia uma heurística subordinada, combinando
inteligentemente diferentes conceitos para explorar o espaço de busca.
As metaheurísticas podem ser classificadas, segundo o princípio que utilizam
para explorar o espaço de busca, em metaheurísticas baseadas em busca local e
metaheurísticas baseadas em busca populacional.
Nas metaheurísticas baseadas em busca local, a exploração é realizada através da
aplicação de moviment os à solução corrente, que levam o algoritmo a uma solução
3.4 Metaheurísticas 30
procedimento DescidaRandomica(f(·), N (·), s, iterMax)
1 iter = 0; contador de iterações sem melho ra
2 enquanto (iter < iterMax faça
3 iter = iter + 1;
4 selecione aleatóriamente s
′
∈ N (s);
5 Se (f(s
′
) < f(s)) faça
6 iter = 0;
7 s ← s
′
;
8 fim-se;
9 fim-enquanto;
10 Retorne s;
fim DescidaRandomica();
Figura 3.3: pseudocódigo do Método de Descida Randômico.
promissora de sua vizinhança. Pertencem a essa categoria as metaheurísticas Busca
Tabu, GRASP, Iterated Local Search e Simulated Annealing (SA).
As metaheurísticas baseadas em busca populacional se inspiram nos mecanismos
encontrados na natureza. Consistem em manter um conjunto de boas soluções e
combiná-las, de forma a tentar produzir soluções ainda melhores. Se enquadram
nessa catego r ia as metaheurísticas Algoritmos Genéticos (AG), Algoritmos Memé-
ticos ( AM), Ant Colony System ( ACS) e Particle Swarm Optimization (PSO).
Neste trabalho, para solucionar o PCDA, são utilizados métodos evolutivo s com-
binados com métodos de busca local, resultando, assim, em métodos híbridos. Para
resolver o PCEB, é usado um algoritmo baseado em um algo r itmo evolutivo multi-
objetivo descrito na literatura . Estes métodos serão abordados nas seções a seguir.
3.4.1 Metahe urí s ticas baseadas em Busca Local
Os algoritmos baseados em busca local descritos a seguir foram utilizados na reso-
lução dos problemas de corte tr atados nesta dissertação.
3.4.1.1 Iterated Local Search
A metaheurística Iterated Local Search - ILS (Lourenço et al., 2002) é baseada
na idéia de que se pode melhorar um procedimento de busca local com a geração de
novas soluções de partida, obtidas com a a plicação de perturbações sobre a solução
ótima. É um método que não explora o espaço completo das soluções, mas um
pequeno subespaço composto por soluções que são ótimos locais, ou ainda, soluções
que sofreram uma busca local, mas sem a garantia de o t imalidade de determinados
procedimentos de otimização.
O algoritmo ILS inicia-se com a geração de uma solução aleatória, que, em se-
guida, sofre uma busca local. A seguir, é aplicada uma perturbação nessa solução.
Tais perturbações são divididas em níveis. Neste tra balho, o primeiro nível de per-
turbação consiste em aplicar uma vez um determinado movimento sobre a solução.
3.4 Metaheurísticas 31
No segundo nível, esse movimento é aplicado duas vezes sobre a solução, e assim
sucessivamente. Após a perturbação, a solução passa p or uma busca local, sendo
avaliada em seguida. Se esta solução for pior que a anterior, o movimento é desfeito
e o nível de perturbação cresce. Caso contrário, a solução encontrada pa ssa a ser a
solução corr ente, e o nível de perturbação atual é aplicado. A solução corrente é a
melhor solução encontrada até então. O procedimento pára após um certo número
de iterações.
Como se pode perceber, a perturbação deve ser forte o suficiente para garantir a
exploração de diferentes soluções e fraca o bastante para que não ocorra um reinício
aleatório. A eficiência do ILS é baseada no conjunto de amostragem de ótimos locais
e na escolha do método de busca local, das perturbações e do critério de aceitação.
O pseudocódigo do método é apresentado na Fig. 3.4.
procedimento ILS(·)
1 s
0
← GeraSoluçãoInicial();
2 s ← BuscaLocal(s
0
);
3 enquanto (os critérios de parada não estiverem satisfeitos) faça
4 s
′
← Perturbação(s, historico);
5 s
′′
← BuscaLocal(s
′
);
6 s ← CriterioAceitação(s, s
′′
);
7 fim-enquanto;
8 Retorne s;
fim ILS();
Figura 3.4: Pseudocódigo da Metaheurística ILS.
Observa-se, no pseudocódigo da Fig. 3.4, que a metaheurística ILS possui cinco
pontos importantes para seu funcionamento:
(a) Procedimento de geração da solução inicial: a solução inicial pode ser gerada
aleatoriamente ou utilizando-se uma heurística ou metaheurística. O impor-
tant e é que a solução inicial não deve ser muito cara computacionalmente e
deve ser, de preferência, de boa qualidade, ou seja, estar em um subespaço de
busca promisor.
(b) Procedimento de busca local: responsável por pesquisar, no subespaço g erado
pelas estruturas de vizinhança, uma solução ótima local. Novamente, existe a
liberdade de escolher qualquer método de busca local, ou, até mesmo, utilizar
uma metaheurística.
(c) Procedimento de perturbação: responsável por gerar uma nova solução, mo-
dificando a solução corrente.
(d) Critérios de parada: vários critérios podem ser empregados, como, por exem-
plo, número fixo de iterações; parar após a passagem de um certo tempo
computacional; parar após um certo número de iterações sem melhora no va-
lor da função objetivo; parar quando a melhora no valor da função objetivo se
tornar insignificante.
3.4 Algoritmos evolutivos 32
Figura 3.5: Esquema do método ILS, para o caso de funções contínuas.
(e) Critérios de aceitação: o critério de aceitação mais comum é de acordo com o
valor da função objetivo. Porém, outros critérios podem ser empregados.
A Fig. 3.5 ilustra, através de um esquema hipotético, o compor t amento do
método.
3.4.1.2 Método Multi-Start
Em 1973, Lin e Kernighan (1973) propuseram a heurística Multi-Start, que con-
siste em fazer amostragens do espaço de busca, seguidas de refinamento. Um dos
métodos mais conhecidos, baseados em Multi-Start, é o Greedy Random Adaptive
Search Procedure (GRASP), introduzido por Feo e Resende (1995 ) .
O Multi-Start é uma metaheurística iterativa, comp osta por duas fases, conforme
apresentado na 3.6. Na primeira fase, se constrói uma solução, aleatoriamente ou
utilizando uma heurística. Na segunda fase, é aplicada uma busca local sobre a
solução obtida na construção. A metaheurística é executada até que um critério
de parada seja atingido (número de iterações, tempo de processamento, número de
iterações sem melhora (MS
max
), etc). O método retorna a melhor das soluções
refinadas. O pseudocódigo do método é mostrado na Fig. 3.6.
Os detalhes da implementação de cada um dos métodos, para o problema de
corte objeto de interesse, pode ser vista nos Capítulos 4 e 5.
3.4.2 Algo ri tmos evol utivos
A computação evolutiva surgiu nos ano 50, e tem, como idéia básica, a aplicação
do processo de evolução natural como um modelo de solução de problemas, a partir
de sua implementação em computador.
Segundo Von-Zuben (2000), a principal vantagem da computação evolutiva está
na possibilidade de resolver problemas pela simples descrição matemática do que
se espera de uma solução, não havendo necessidade de se indicar explicitamente os
passos até o resultado, que certamente seriam específicos para cada caso. É lógico
que os algoritmos evolutivos correspondem a uma seqüência de passos até a solução,
3.4 Algoritmos evolutivos 33
procedimento Multi-Start (·)
1 f
∗
← ∞;
2 iter ← 0;
3 enquanto (iter < MS
max
) faça
4 s ← ConstroiSolução();
5 s
′
← BuscaLocal(s);
6 Se (f(s
′
) < f
∗
) faça
7 s
∗
← s
′
;
8 f
∗
← f(s
′
);
9 fim-se;
10 iter ← iter + 1;
11 fim-enquanto;
12 Retorne s
∗
;
fim Multi-Start();
Figura 3.6: pseudocódigo do Método Multi-Start.
mas estes passos são os mesmos para uma ampla gama de problemas, fornecendo
robustez e flexibilidade.
Apesar de não garant ir a otimalidade da solução, essas t écnicas são capazes de
solucionar problemas intratáveis por outros métodos. Uma descrição das pesquisas
em computação evolutiva pode ser encontrada em Bäck et al. (200 0a) e Bäck et al.
(2000b).
Os métodos evolutivo s operam sobre uma população de candidatos em paralelo.
Assim, eles podem fazer a busca em diferentes áreas do espaço de solução, através
da colocação de um número de pontos adequado para a busca em várias regiões.
Um do s primeiros algoritmos evolutivos desenvolvidos foram os Algoritmos G e-
néticos (AG), propostos inicialmente por Holla nd (1 975) e popularizados por um
dos seus alunos, David G oldberg (G oldberg, 1989). Os AG se mostraram ba stante
eficientes para encontrar soluções ótimas ou aproximadamente ótimas.
O método se baseia nos conceitos da evolução genética, segundo a qual quanto
melhor um indivíduo se adaptar a o seu meio, maior será sua chance de sobreviver
e gerar descendentes. É um processo composto por diversos passos, que podem
apresentar grandes va riações. Daí a razão pela qual estes algoritmos são chamados
de “um Alg oritmo Genético”, em vez de “ o Algoritmo Genético”. Os detalhes deste
método são apresentados a seguir.
3.4.2.1 Algoritmos Genéticos
Algoritmos Genéticos (AG) são algoritmos de otimização baseados nos princípios
da seleção natural e da genética. Segundo a teoria da seleção natural, dada uma
população, os indivíduos com características genéticas mais favo r áveis têm maior es
chances de sobreviver e gerar descendentes cada vez mais aptos, enquanto indivíduos
menos aptos tendem a serem extintos.
3.4 Algoritmos evolutivos 34
Os AG utilizam uma estratégia de busca paralela e aleatória, com a busca voltada
para pontos de alta aptidão (pontos nos quais a função a ser minimizada (maximi-
zada) assumem valores relativamente baixos (altos)).
Apesar de serem compostos por procedimentos a leató r ios, os AG não são um
mecanismo de busca aleatório não-direcionado, pois exploram infor mações históricas
para encontrar novos e promissores pontos no espaço de busca. O processo de busca
é iterativo, no qual cada iteração é chamada de g eração.
Nos AG, cada indivíduo da po pulação representa uma solução do problema. Em
cada geração, os mecanismos de seleção e reprodução são aplicados a uma população
de candidatos (que varia com a complexidade do problema).
Através da seleção, determinam-se quais indivíduos conseguirão se reproduzir,
gerando um determinado número de descendentes para a próxima geração. A pro-
babilidade de um indivíduo ser selecionado é proporcional ao seu nível de aptidão.
A Fig. 3 .7 mostra o pseudocódigo de um AG simples.
procedimento Algoritmo Genético
1 t ← 0;
2 Gerar a população inicial P (t);
3 Avaliar P (t);
4 enquanto(os critérios de para da não estiverem
satisfeitos) faça
5 t ← t + 1;
6 Gerar P (t) a partir de P (t − 1);
7 Avaliar P (t);
8 Definir a população sobrevivente;
9 fim-enquanto;
fim AlgoritmoGenetico;
Figura 3.7: pseudocódigo de um AG simples.
A seguir são apresentados os principais elementos de um AG.
Representação da solução
Para que possam ser aplicados os operadores genéticos, é necessário que os indivíduos
estejam codificados em cromossomos. Cada cromossomo representa uma variável do
problema. No caso de apenas uma variável, o indivíduo e o cromossomo têm o
mesmo significado.
A codificação mais usada é a binária, em função da facilidade de implementação
do algo ritmo. Nela, os indivíduos são r epresentados por vetores binários, no s quais
cada elemento denota a presença (1) ou ausência (0) de uma determinada caracte-
rística. Entretanto, se for necessário trabalhar com maior precisão em problemas
com parâmetros contínuos, provavelmente serão utilizados longos cromossomos para
representar as soluções, necessitando de uma grande quantidade de memória. Além
disso, não existe uniformidade nos operadores. Por exemplo, mutação nos primeiros
bits do gene afeta mais a aptidão que mutação nos últimos bits do gene.
3.4 Algoritmos evolutivos 35
Outra codificação bastante difundida é a representação do cromossomo usando
valores reais. Essa representação apresenta a vantagem de ser naturalmente com-
preendida pelo ser humano e requer menos memória que aquela usando uma cadeia
de bits (Micha lewicz, 1992). Outra vantagem da representação real é a possibilidade
de criar novos operadores e variações dos operadores existentes.
Função de aptidão
A avaliação dos indivíduos é feita através de uma função que representa o problema
e tem, por objetivo, fornecer uma medida de aptidão de cada indivíduo na popu-
lação corrente. Nem sempre a função de a ptidão corresponde à função objetivo do
problema (função a ser otimizada).
A função objetivo e a f unção de aptidão não são as mesmas, por exemplo, quando
o objetivo do problema é a minimização da uma função. Isso porque os AG são de-
finidos para problemas de maximização, ou seja, buscam indivíduos com as maiores
aptidões. Nesse caso, por exemplo, pode-se tomar a função de aptidão como o in-
verso da função objetivo. Assim, quanto menor o valor da função objetivo, maior o
valor da função de aptidão. Essa conversão, no entanto, pode, em alguns casos, fazer
com que a função de aptidão assuma valores muitos próximos (tornando a seleção
aleatória). É o que ocorre no exemplo a seguir, no qual são dados os valores da
função objetivos de dois indivíduos de um problema de minimização:
f
objetivo
(s
1
) = 500
f
objetivo
(s
2
) = 600
Invertendo-se o valor da função objetivo, obtém-se os seguintes valores para a função
de aptidão:
f
aptidão
(s
1
) = 0, 0020
f
aptidão
(s
2
) = 0, 0017
Como pode ser visto, soluções com uma diferença importante na função objetivo
tornam-se soluções muito próximas se for feita apenas a inversão dos valores. Uma
alternativa para se obter a função de aptidão sem tais distorções é a utilização de
um método de escalamento linear. Neste método, a aptidão do indivíduo é obtida
através de uma equação linear. Este método, utilizado neste trabalho, é descrito no
Capítulo 4.
Seleção dos indivíduos
A seleção corresponde à seleção natural que ocorre entre os seres vivos, que escolhe
os indivíduos mais aptos para sobreviver e gerar descendentes. No caso do AG, são
selecionados os indivíduos com maior valor na função de aptidão para gerar filhos
através dos operadores de recombinação e mutação.
Existem diversos métodos de seleção, mas em todos eles os melhores indivíduos
terão uma probabilidade maior de sobrevivência e reprodução.
Na estrutura do AG, proposto por Holland, a população se mantém fixa durante
todas as gerações. Por isso, a cada geração devem ser selecionados quais indivíduos
irão se reproduzir e quais vão desaparecer da população. Após a seleção, seguida
3.4 Algoritmos evolutivos 36
pela reprodução, todos os indivíduos estão sujeitos aos operadores de recombinação
e mutação.
O método apresentado por Holland (1975) para seleção é conhecido como método
da roleta. Neste método, cada indivíduo tem uma probabilidade (aptidão relativa)
de ser escolhido de a cordo com a sua aptidão f
apt
.
A Tab ela 3.1 ilustra um exemplo da aplicação deste método de seleção. O pro-
cesso se inicia com a soma de todas as funções de aptidão dos indivíduos da popula-
ção corrente. Em seguida, calcula-se a porcentagem de cada indivíduo com relação
a essa soma. Após esse cálculo, é feita uma lista com a s porcentagens acumuladas.
O próximo passo é o sorteio de um número a leató r io r (retirado de uma distri-
buição uniforme) no intervalo [0, soma], conforme mostra a Tabela 3.2. Por fim, o
indivíduo selecionado é o primeiro que possuir uma aptidão acumulada maior que
r. O processo é repetido até que toda a população seja preenchida. A Fig. 3.8
apresenta o processo.
Tabela 3.1: Método da Roleta: análise de aptidão.
Indivíduo i 1 2 3 4 5 6 7 8 9 10
Aptidão f
apt
(i) 8 2 17 7 2 12 11 7 3 7
Apt. Relativa % 10,5 2,6 22,4 9,2 2,6 15,8 14,5 9,2 3,9 9,2
Apt. Rel. Acumulada % 10,5 13,1 35,5 44 ,7 47,3 63,1 77,6 8 6,8 90 ,7 99,9
Tabela 3.2: Método da Roleta: seleção.
n
o
aleatório r 23 49 76 30 1 38 57
Indivíduo selecionado 3 7 10 4 1 6 7
4
9
2
7
1
3
10
6
5
8
Figura 3.8: Representação da Roleta - Seleção do primeiro indivíduo.
Como se pode observar, no método da roleta, apesar dos indivíduos mais aptos
possuírem maior probabilidade de sobreviverem, todo s indivíduos, inclusive os menos
aptos, têm chances de sobrevivência.
3.4 Algoritmos evolutivos 37
A cada dois indivíduos escolhidos desta maneira são gerados dois novos indiví-
duos (idênticos aos selecionados). O processo de seleção termina quando é selecio-
nado um número de indivíduos igual ao tamanho da população anterior. Quando
isso ocorre, a população antiga é substituída por essa nova população.
Reprodução
Os operadores genéticos de recombinação e mutação são utilizados para garantir que
a próxima geração se renove, mas que mantenha, de certa forma, as características
adquiridas pelas gerações anteriores. Estes operadores são os principais mecanismos
de busca dos AG par a explorar regiões desconhecidas do espaço de soluções.
Recombinação O operador de recombinação é aplicado a um par de indivíduos
retirados da população selecionada pela roleta (população intermediária), gerando
dois indivíduos filhos.
Um exemplo simples de recombinação, para um AG com representação binária,
é a recombinação de um ponto. Nele, cada um dos cromossomos pais tem sua cadeia
de bits cortada em uma posição aleatória, produzindo duas partes. Essas partes são
trocadas, gerando dois novos cromossomos.
Quando se utiliza a representação real, é possível a utilização de diversos ope-
radores de recombinação. Neste trabalho, as soluções para os dois problemas de
corte originam indivíduos representados por número inteiros. Por isso, no alg oritmo
desenvo lvido para a solução do PCDA, foi utilizado um operador conhecido como
Order recombinação - OX, específico para o tipo de representação (descrito no Capí-
tulo 4). No algoritmo evolutivo para o PCEB, utilizou-se o recombinação uniforme,
descrito no Capítulo 5.
O operador de recombinação é aplicado com uma dada probabilidade a cada par
de cromossomos selecionados, sendo que, na prática, essa probabilidade varia entre
60% e 90% (como na natureza, nem todos os casais têm filhos). Caso não ocorra
a recombinação, os filhos serão iguais a os pais, permitindo, assim, que algumas
soluções sejam preservadas.
Mutação Após a recombinação, o operador de mutação é aplicado, com dada
probabilidade, em cada elemento dos dois filhos. Quando se usa o código binário,
a mutação consiste em simplesmente inverter os valores de bits, ou seja, mudar o
valor de um dado bit de 1 para 0 ou de 0 para 1.
A mutação tem o objetivo de introduzir e manter a diversidade dos indivíduos
na população. Por outro lado, po de destruir informações contidas nos indivíduos.
Por isto, a probabilidade de mutação deve ser p equena (geralmente entre 0,1% a
5%), mas suficiente para assegurar a diversidade.
Para prevenir que os melhores indivíduos não desapareçam da população pela
manipulação dos operadores genéticos, eles podem ser automaticamente colocados
na próxima geração. Esta operação é conhecida como elitismo.
3.5 Otimização Combinatória Multiobjetivo 38
Critério de Convergência
Como os algo r itmos estocásticos nã o são capazes de indicar se foi encontrado o ótimo
global, é necessário determinar critérios de convergência para que se limite o tempo
de execução do algoritmo.
O critério utilizado neste trabalho é encerrar o algoritmo a pós um número má-
ximo de gerações. Assim, quando o AG alcança uma determinada geração, é fina-
lizado, e a solução é o melhor indivíduo obtido até então. Para obter o número
máximo de gerações, geralmente são realizadas análises de convergência par a várias
simulações.
3.4.3 Algo ri tmos Genéticos Híbridos
Os AG, em sua forma original, são eficientes para solucionar diversos problemas de
otimização. No entanto, para problemas de grande complexidade, seu desempenho,
seguindo a formulação orig inal, não t em se mostrado satisfatório.
Entretanto, devido à facilidade, apresentada pelos AG, de combinação com ou-
tros métodos, em esp ecial com métodos de busca local, diversos pesquisadores têm
proposto modificações na estrutura básica do algoritmo, nas quais são incorporadas,
aos AG, técnicas de busca local, ou, de outro modo, são incluídos conceitos de ou-
tras metaheurísticas, como, por exemplo, Simulated Annea l i ng, Tabu Search (busca
tabu) ou I terated Local Search. São obtidas, assim, versões conhecidas como Algorit-
mos Genéticos Híbridos, Algoritmos Meméticos ( Moscato, 1989) ou, simplesmente,
Algoritmos Evolutivos (AE).
A aplicação de busca local nos indivíduos está relacionada com a combinação de
aprendizado e evolução (Whitley, 1992). O aprendizado seria uma busca local pela
solução mais próxima, e a incorporação das modificações ocorridas pelo indivíduo.
O que ocorre, portanto, é a conservação das características evolutivas dos AG associ-
adas a utilização de heurísticas que provocam melhorias individuais nos indivíduos.
O algor itmo evolutivo resultante, por t anto, possui as características básicas dos AG,
mas são mais especializados para determinadas aplicações.
Neste trabalho é desenvolvido um algoritmo evolutivo híbrido, que combina um
AG em sua formulação clássica com as metaheurísticas ILS e Multi-Start, para a
resolução do Problema de Corte com Dimensão Aberta. Os detalhes do método são
descritos no Capítulo 4.
O Problema de Corte de Estoque Bidimensional t ambém foi solucionado por
um método evolutivo desenvolvido para resolução de pro blemas multiobjetivos. A
descrição do método é apresentada no Capítulo 5.
Em ambos os casos, optou-se pela utilização de métodos evolutivos devido à sua
flexibilidade e simplicidade de implementação, além do sucesso que apresentaram
quando aplicados à diversos problemas de difícil r esolução.
3.5 Otimização Combinatória Multiobjetivo
Um problema de otimização multiobjetivo (POMO) consiste em minimizar (ou
maximizar) simultaneamente um conjunto de critérios (objetivos) satisfazendo um
conjunto de restrições. Em otimização multiobjetivo, nã o existe uma única solução
3.5 Otimização Combinatória Multiobjetivo 39
que otimize cada um dos objetivos, mas sim um conjunto de soluções eficientes, ou
soluções Pareto-ótimas, no qual nenhuma solução é melhor que outra solução para
todos o s o bjetivos. Assim, o decisor é o responsável pela escolha de uma solução
eficiente particular que satisfaça os objetivos globais do problema.
Um problema geral de otimização multiobjetivo consiste em encont r ar um vetor
de soluções que satisfaça restrições e otimize uma função vetorial cujos element os
representam as funções objetivos. Os objetivos considerados, geralmente, são con-
flitantes entre si. Neste contexto, portanto, o termo “otimizar” significa encontrar
soluções nas quais os valores de todos objetivos não podem ser melhorados simulta-
neamente.
Um enunciado geral para um POMO é o seguinte:
max / min {f
1
(x) = z
1
, . . . , f
n
(x) = z
n
} (3.1)
sujeito a x ∈ X (3.2)
em que a solução x é um vetor de variáveis de decisão e X é o conjunto de soluções
factíveis presentes no espaço de decisões.
A imagem da solução x no espaço objetivo factível, denotado por Z, é um ponto
z
x
= [z
x
1
, z
x
2
, . . . , z
x
n
] = f (x), t al que z
x
j
= f
j
(x), j = 1, . . . , n.
Na otimização mono-obj etivo, o espaço dos objetivos é inteirament e ordenado,
ou seja, dados dois elementos x e y ∈ X, existem apenas duas possibilidades: ou
f(x) ≥ f(y) ou f (x) ≤ f (y).
Na otimização multiobjetivo, no entanto, não existe uma solução que seja ótima
para todos os objetivos. Pode ocorrer, por exemplo, que a minimização de um
determinado objetivo provoque um aumento nos outros objetivos.
Apesar do espaço obj etivo não ser, em geral, completamente ordenado, é possível
ordená-lo parcialmente (Pareto, 1896). Essa ordenação parcial permite diferenciar
as soluções de um problema de otimização multiobjetivo. Em um conjunto parcial-
mente ordenado, dadas duas soluções x e y ∈ X, existem três possibilidades:
• f(x) ≤ f(y)
• f(y) ≤ f(x)
• (f(x) f(y) e f(y) f(x)
em que () é o operador de não-dominância. Assim, pode-se dizer que uma solução
x, domina uma solução y, se:
(a) A solução x não é pior que a solução y em nenhum dos objetivos, ou seja, f
j
(x)
≤ f
j
(y), para j = 1, . . . , n, onde n é número de objetivos.
(b) A solução x é estritamente melhor que a solução y em pelo menos um objetivo,
ou seja, f
j
(x) < f
j
(y) para algum j ∈ {1, . . . , n}.
Assim, uma solução eficiente, ou Pareto-ótima, é uma solução não-dominada por
nenhuma outra solução factível. O conjunto de to das as soluções não-dominadas,
dentre as soluções factíveis, é chamado de Conjunto Pareto-ó timo. Os pontos no
espaço das funções-objetivo que corr espondem ao conjunto Pareto-ótimo for mam a
Fronteira de Pareto.
3.5 Otimização Combinatória Multiobjetivo 40
Caso não exista diferença na relevância relativa entre os objetivos a serem aten-
didos, todos os pontos na Fronteira de Pareto são qualitativamente equivalentes, sob
a perspectiva de otimização.
As Fronteiras de Pareto podem apresentar diversas conformações, incluindo des-
continuidade. Além disso, durante o processo de busca, o fato de uma solução
ser não-dominada frente às propostas de solução já investigadas não implica que
a mesma pertença à Fronteira de Pareto. Assim sendo, o processo de busca terá
sempre dois objetivos principais:
(i) Convergir para a fronteira de Pareto;
(ii) Manter uma distribuição tão uniforme quanto possível das soluções não-domi-
nadas.
O segundo objetivo é o principal motivo pelo qual as heurísticas populacionais
são reconhecidas como as mais a dequadas para a busca de solução de problemas de
otimização multiobjetivo de elevada dimensão.
A resolução de problemas multiobjetivo é dividida, ba sicamente, em duas etapas:
• Etapa de determinação das soluções eficientes;
• Etapa de decisão.
A primeira etapa consiste na busca de soluções Pareto-ótimas dentro do espaço
factível. A segunda etapa, consiste em selecionar a solução que representa um com-
promisso final dentre aquelas soluções de Pareto. Nessa fase, o decisor faz uma
escolha externa ao processo de otimização. Dependendo de como e quando o pro-
cesso de otimização e a etapa de decisão são combinados, os métodos de resolução
podem ser classificados em três categorias:
(a) Decisão antes do processo de busca (a priori): o decisor opta pelo compromisso
que ele quer obter antes de iniciar o método de resolução. Basicamente, o que
se faz é t r ansformar um problema multiobjetivo em uma aproximação mono-
objetivo. Após está transformação, pode-se aplicar qualquer técnica mono-
objetivo para a resolução do problema. Entretanto, a a dequação dos pesos
atribuídos a cada objetivo não é trivial, principalmente quando os objetivos
são extremamente conflitantes.
(b) Decisão durante o processo de busca (progressivo): é o procediment o de decidir
durante o processo de obtenção das soluções não-dominadas. A escolha do
decisor é utilizada na busca de novas soluções eficientes. Esta abordagem
exige certa experiência do decisor, já que as escolhas deverão ser tomadas de
modo a orientar o processo de otimização no sentido de formar a fronteira
Pareto-ótima.
(c) Decisão a pós o processo de busca (a posteriori): é considerada a opção mais ló-
gica, pois as escolhas serão feitas de acordo com os resultados encontrados. Ou
seja, com o conjunto Pareto-ótimo definido, torna-se possível conhecer o com-
portamento do problema em relação aos objetivos em questão. Conhecendo-se
as relações de dependência entre eles, a escolha torna-se mais fácil.
3.6 Otimização Multiobjetivo Evolutiva 41
A qualificação das metodologias de busca de soluções eficientes depende do co-
nhecimento de dificuldades de solução usualmente encontradas nos problemas mul-
tiobjetivo. Assim como na otimização mono-obj etivo, as dificuldades de resolução
de problemas multiobjetivo se devem à presença de restrições e do comportamento
das funções objetivo.
As principais dificuldades encontradas na otimização de problemas multiobjetivo
são:
• não-convexidade;
• descontinuidades; e
• multimodalidade ou existência de múltiplos ótimos locais ou globais.
Além destas dificuldades, pode-se citar a não uniformidade das soluções no espaço
dos o bjetivos. Certos métodos de resolução podem apresentar características que
concentram as soluções em determinadas áreas. Se estas regiões não forem próximas
às soluções Pareto ou se elas contemplarem apenas uma parte da fronteira ótima, a
caracterização de todo o conjunto Pareto-ótimo po de ser comprometida.
O o bjetivo deste trabalho é desenvolver um método de ot imização multiobjetivo
à posteriori, baseado em algoritmos evolutivos aplicados ao Problema de Corte e
Empacotamento Bidimensional. Os métodos evolutivos para otimização multiobje-
tivo são detalhados na seção a seguir.
3.6 Otimização Multiobjetivo Evolutiva
Os métodos evolutivos, ou métodos de busca po r populações, trabalham com
um conjunto de soluções corrente simultaneamente. Além disso, a população sub-
seqüente é baseada nas informações obtidas em mais de um ponto no espaço de
soluções. Essas info r mações dizem respeito aos valores das funções objetivo, as
quais permitem determinar quais soluções são melhores. Os métodos de busca por
populações são, portanto, os que mais se aproximam do conceito de algoritmos de
otimização para problemas genéricos (multimodais, com restrições, convexos e não
convexos, etc.).
Os métodos de busca por populações, no entanto, têm suas limitações. Dentre
elas, está a dependência do método com relação à distribuição da população inicial.
Dificilmente o método convergirá se o ótimo global estiver afastado da região onde
se concentra a população inicial. Assim, fica claro que a eficiência desses métodos
depende de uma população inicial que explore bem todo o espaço de busca. Outra
desvantagem é a velocidade de convergência. Comparando com o utros métodos, eles
podem ser mais lentos, por necessitar de maior número de avaliações do problema.
O esforço computacional desses métodos pode ser maior para atingir os mesmos
resultados (quando os outro s métodos obtém um resultado).
Os aspectos apresentados, nesta seção, somados às características do problema
multiobjetivo aqui tr atado, mostram que o grupo mais adequado para sua resolução
é o de busca por população.
3.6 Algoritmos Multiobjetivos baseados em AG’s 42
3.6.1 Algo ri tmos Multiobjetivos basea dos em Algoritmos Gé-
neticos
O surgimento dos Algoritmos Genéticos Multiobjetivos é recente. O primeiro
trabalho foi propo sto por Schaffer (1984). Após este trabalho nenhum estudo rele-
vante foi a presentado por quase uma década, com exceção de um esboço apresentado
no livro de Goldberg (1989), de um novo procedimento de ordenamento de soluções
não-dominadas. Este livro tornou-se um marco dos algoritmos evolutivos e alavan-
cou o tratamento de problemas de otimização multiobjetivo. Baseados nas idéias
conceituais apresentadas por Goldberg, diversos pesquisadores passaram a desenvol-
ver diferentes versões de algoritmos de otimização multiobjetivos.
Desde G oldberg, o número de publicações nesta área tem crescido muito (estão
disponíveis atualmente em Coello (1999) mais de 2500 referências). Coello (1999)
apresenta uma revisão, que classifica e avalia inúmeras técnicas de otimização mul-
tiobjetivos. Esse trabalho ainda mostra que a maioria dos métodos utilizados é
baseado nos AG mono-objetivo.
A principal diferença entre os AG mono-objetivo e multiobjetivo está, basica-
mente, na maneira como a seleção beneficia as soluções não-dominadas e as soluções
mais dispersas (situadas em regiões menos p ovoadas). De acordo com autores já
citados, os principais métodos propostos e suas estratégias para a seleção são:
• Vector Evaluated Genetic Algorithm − VEGA (Schaffer, 1984) : o operador
genético de seleção é modificado de forma a criar populações separadas para
cada objetivo. Com isso, são geradas especializações, ou seja, cada população
tende ao ponto ótimo para aquele objetivo e não para a fronteira Pareto-ótima
associada ao problema;
• Multiobjective Genetic Algorithm − MOGA (Fonseca e Fleming, 1993): a idéia
do MOGA é estabelecer uma ordem entre os indivíduos: os não-do minados
têm classificação igual, já os dominados são penalizados de acordo com sua
dominância. A dificuldade está em encontrar uma forma de intercalar estes
dois grupos, de modo a permitir uma boa disposição da fronteira Pareto-ótima;
• Nondominated Sorting Genetic Algorithm − NSGA I (Srinivas e Deb, 1993),
NSGA II (Deb et al., 2002): neste método, somente as soluções não-dominadas
são selecionadas. Por todas serem eficientes, terão a mesma probabilidade para
se reproduzir. Nesta metodologia, a desvantagem é a dificuldade em conseguir
manter a diversidade da população. A falta de diversidade pode gerar uma
fronteira incompleta, o u seja, a concentração de soluções em algumas regiões;
• Niched Pareto Genetic Algorithm − NPGA (Horn e Nafpliotis, 1993): uma
das técnicas de seleção para AG mono-objetivo é o torneio entre os indivíduos
(Goldberg, 1989). Os autores implementaram um tor neio no qual a regra
de comp etição é a idéia de dominância por Pareto. Neste método, existe a
dificuldade de determinar quais e quantos indivíduos participarão do torneio;
• Método das Populações Intermediárias (Viennet e Marc, 1996): o método
segue três passos básicos: a determinação dos pontos mínimos de cada objetivo;
a procura de uma po pulação intermediária (baseada na escolha de n indivíduos
3.6 Algoritmos Multiobjetivos baseados em AG’s 43
para cada objetivo) e, a partir desta população, a definição da fronteira Pareto-
ótima. A principal restrição desta metodologia é que em cada objetivo deve
haver um único ótimo no espaço de estudo (função unimodal);
• Strength Pareto Evolutionary Algorithm − SPEA I (Zitzler e Thiele, 1998 ) ,
SPEA II (Zitzler, 1999) e (Zitzler et al., 2001): um escalar indicando uma
medida de força para cada indivíduo é criado para o processo de seleção. Os
indivíduos não-dominados devem possuir maior for ça.
Diversos trabalhos apresentam comparações feitas entre os vários algoritmos de-
senvolvidos: Zitzler (1 999), Dias (19 99) e Régnier (2003). De acordo com estes
trabalhos, os algoritmos SPEA−II e NSGA−II parecem ser os métodos mais sóli-
dos.
Entretanto, para escolher ou desenvolver um algoritmo evolutivo, é necessário
conhecer seus mecanismos básicos e sua interação com a busca multiobjetivo. Em
geral, um algoritmo evolutivo é caracterizado por um conjunto de soluções candi-
datas que, após serem submetidas a um processo de seleção, são manipuladas po r
operadores genéticos, com o intuito de melhorar o conjunto.
Em razão de seu par alelismo, os métodos baseados em AG’s têm o potencial de
encontrar múltiplas soluções em uma única iteração. No entanto, nem sempre é
possível encontrar soluções ótimas, sendo menos provável ainda encontrar o Pareto-
ótimo completo. Em conseqüencia disso, as metas para a otimização multiobjetivo
passam a ser:
(i) Minimizar a distância entre a fronteira não-dominada obtida e a fronteira
Pareto-ótima;
(ii) Manter uma boa distribuição das soluções encontradas.
Além dos aspectos apresentados acima, existem duas questões importantes na
resolução de um problema de otimização multiobjetivo através de métodos baseados
em AG:
(i) Como atribuir a função de aptidão às soluções, sendo esta a principal diferença
entre um AG multiobjetivo e um AG mono-objetivo. Devido à indiferença en-
tre as soluções dominantes de um problema multiobjetivo, é necessário definir
algumas estratégias para calcular a função de aptidão e para selecionar as
soluções com maior probabilidade de reprodução.
(ii) Como manter a diversidade da população, evitando uma convergência prema-
tura, e g arantindo a obtenção de uma fronteira bem distribuída.
Neste trabalho, foi utilizado um algoritmo evolutivo multiobjetivo baseado no
NSGA-II, descrito a seguir.
3.6 Algoritmos Multiobjetivos baseados em AG’s 44
3.6.1.1 Nondominated Sorting Genetic Algorithm - NSGA-II
O algoritmo NSGA, proposto por Srinivas e Deb (1995) é uma das diversas
implementações baseadas nas sugestõ es de Goldberg (1989). Nesse algoritmo, é
utilizado um procediment o de seleção por or denamento, que prioriza as soluções não-
dominadas corrent es, a lém de um método voltado para a manutenção da diversidade
da população.
A única diferença desta implementação em relação a um algoritmo genético sim-
ples está na maneira como o operador de seleção é empregado. Tanto o operador de
recombinação quanto o operador de mutação são os usuais da t é cnica.
O NSGA foi um dos primeiros algoritmos evolutivos multiobjetivo desenvolvido.
No entanto, ao longo dos anos, esse algoritmo recebeu críticas no que se referia a:
(i) Alta complexidade computacional, o que torna o método computacionalmente
caro para populações grandes;
(ii) Ausência de uma estratégia de elitismo: Rudolph (1999) e Zitzler et al. (2000).
mostraram que o elitismo é capaz de melhorar significativament e o desempenho
de um algoritmo genético, além de prevenir a perda de boas soluções;
(iii) Dificuldade em especificar o parâ metro de compartilhamento σ
share
, utilizado
na função de compartilhamento, que mant ém a diversidade da população. Este
parâmetro está relacionado com a distância métrica escolhida para calcular a
medida da proximidade de dois membros da população.
Em vista dessas limitações, os autores do NSGA propuseram, em (Deb et al.,
2002), uma versão melhorada, chamada de NSGA-II . Nos resultados encontrados
para diversos problemas difíceis, em termos de encontrar um conjunto diversificado
de soluções e convergir para soluções próximas do verdadeiro Pareto- ótimo, o NSGA-
II superou os resultados de dois algo r itmos multiobjetivos contemporâneos: o PAES
(Knowles e Corne, 1999) e o SPEA (Zitzler, 1999).
Nas próximas seções, são descritos o algoritmo de ordenação de soluções não-
dominadas, que cria as fro nteiras de soluções no algoritmo, e o algoritmo c rowding
distance, responsável por manter a diversidade no NSGA-II.
Fast Non-Dominated Sort
O procedimento Fast Non D ominated Sort atribui um valor de aptidão às soluções
da po pulação de acordo com o seu nível de não-dominância. Inicialment e, o Fast
Non Dominated Sort encontra, para cada solução p:
(i) O contador de dominância n
p
, que mostra o número de soluções que dominam
a solução p.
(ii) O conjunto S
p
, formado pelas soluções dominadas por p.
To das as soluções da primeira fronteira não-dominada (soluções da população que
dominam todas as outras) têm o contador de dominância n
p
igual a zero. Para cada
solução p com n
p
= 0, são visitadas as q soluções pertencente ao conjunto S
p
, e
o contador de dominância n
q
é decrementado em uma unidade. As soluções q que
3.6 Algoritmos Multiobjetivos baseados em AG’s 45
tiverem seu contador de dominância n
q
reduzido a zero são, então, separadas em
uma lista Q. Estas soluções for mam a segunda f ronteira. O procedimento acima é
repetido para cada membro de Q, sendo identificada assim a terceira fronteira. O
processo continua até que todas as fronteiras sejam identificadas.
Ao fim do procediment o Fast Non Dominated Sort, as soluções estão agrupadas
em diferentes fronteiras, conforme a Fig. 3.9, e p ossuem um atributo, chamado
de nondomination rank, que corresponde ao número da fronteira a qual pertencem.
O pseudocódigo do procedimento Fast Non Dominated Sort é apresentado na Fig.
3.10.
f
2
F
3
F
2
f
1
F
1
Figura 3.9: Fronteiras geradas pelo método Fast-non-dominated-sort.
Crowding Distance
As soluções que pertencem a uma mesma fronteira, identificada com o procedimento
Fast Non Dominated Sort, possuem, obviamente, o mesmo nível de dominância, ou
seja, são indiferentes. Portanto, par a classificá-las, tor na-se necessário um outro
parâmetro. No NSGA-II, é utilizada a proximidade das soluções indiferentes. Nesse
caso, as soluções que estão mais distantes de suas soluções vizinhas são favorecidas.
Para isso, é calculada, para cada solução, uma estimativa do número de soluções
que a rodeiam no espaço objetivo.
Inicialmente as soluções são or denadas em f orma crescente do primeiro objetivo,
ou seja, z
1
, . . . , z
n
, em que n é o número de soluções na fronteira considerada. Para
cada ponto z
i
, calcula-se a distância:
d
j
(f
i
) = f
j
(z
i+1
) − f
j
(z
i−1
) (3.3)
Este procedimento é repetido para j = 1, . . . , m, considerando-se que existam m
objetivos a serem satisfeitos.
A estimativa das soluções em volta de uma determinada solução é, então, dada
por:
cd(z
i
) =
m
j=1
d
j
(3.4)
3.6 Algoritmos Multiobjetivos baseados em AG’s 46
Procedimento Fast Non Dominated Sort
1 Para Cada p ∈ P
2 S
p
= ∅
3 n
p
= 0
4 Para Cada q ∈ P
5 Se (p ≺ q) faça (Se p domina q)
6 S
p
= S
p
∪ {q} (Adicione q ao conjunto de soluções dominadas por p)
7 Senão se (q ≺ p) faça
8 n
p
= n
p
+ 1
9 Se (n
p
= 0) faça (p pertence à pri meira fron teira)
10 p
rank
= 1
11 F
1
= F
1
∪ {p}
12 i = 1 (Inicializa o contador de fronteiras)
13 Enquanto F
i
= ∅
14 Q = ∅ ( Armazena os membros da próxi ma fronteira)
15 Para Cada p ∈ F
i
16 Para Cada q ∈ S
p
17 n
q
= n
q
− 1
18 Se (n
q
= 0) faça ( q pertence à p róxima fronteira)
19 q
rank
= i + 1
20 Q= Q ∪ {q}
21 i = i + 1
22 F
i
= Q
fim Fast Non Dominated Sort;
Figura 3.10: pseudocódigo do procedimento Fast Non Domi nated Sort.
Esta medida é conhecida como Crowding distance, também citada na literatura
com o nome de distância de agrupamento, e indica o valor do perímetro do
cubóide criado a partir de uma solução e tendo, como vértices, suas soluções vi-
zinhas. Às soluções extremas z
1
e z
n
são atribuídos valores de Crowding distance
arbitrariamente g r andes (e, portant o, sempre são priorizadas no método elitista).
Após atribuir um valor de Crowding dis tan ce a cada uma das soluções de uma
determinada fronteira, torna-se possível comparar duas soluções através de suas
medidas de proximidade com as demais soluções. A Fig. 3.11 ilustra a crowd i ng
distance para dois objetivos.
A solução com menor valor dessa medida de distância tem, portanto, mais so-
luções em sua volta, quando comparada às outras soluções. Essa é a medida usada
pelo operador de comparação Crowded-Comparison Operator, descrito a seguir.
O algoritmo para cálculo da crowding distance das n soluções de uma fronteira
S
front
é mostrado na Fig. 3.12 .
3.6 Algoritmos Multiobjetivos baseados em AG’s 47
f
2
f
1
i
i+1
i-1
Cubóide
Figura 3.11: Crowding distance.
Algoritmo Crowding di stance
1 para cada ponto z
i
∈ f(S
front
) faça
2 dist(z
i
) = 0
3 para cada objetivo j faça
4 Ordene os pontos em S
front
de acordo com o objetivo j
obtendo z
1
, ..., z
n
;
5 dist(z
1
)= α
6 dist(z
n
) = α (α é um valor suficientemente grande)
7 para i = 2 at é (n − 1) faça
8 dist(z
i
) = dist(z
i
) + (f
j
(z
i
+ 1) − f
j
(z
i
− 1))
(f
j
(z
i
) é o valor da j-ésima função objetivo em z
i
)
9 fim-para
10 fim-para
11 fim-para
Figura 3.12: Pseudocódigo do procedimento crowding distance.
Crowded-Comparison Operator
O c rowded-comparison o perator (≺
n
) guia o processo de seleção nos diferentes está-
gios do algoritmo, em direção a uma fronteira Pareto-ótima uniformemente distri-
buída.
Assim, assumindo que todo indivíduo i da população tem dois atributos:
(i) nondomination rank (i
rank
);
(ii) c rowding distance (i
dist
);
pode-se definir a seguinte ordem parcial (≺
n
):
i ≺
n
j se {(i
rank
< j
rank
) ou ((i
rank
= j
rank
)e(i
dist
> j
dist
))}
3.6 Algoritmos Multiobjetivos baseados em AG’s 48
Isso quer dizer que, entre duas soluções com ranks diferentes, tem a preferência
aquela com menor rank. Por outro lado, se duas soluções estão na mesma fronteira
(mesmo rank), prefere-se aquela que está em uma região menos povoada.
A apresentação dos procedimentos acima permite a descrição do a lgoritmo NSGA-
II, feita a seguir.
Algoritmo NSGA-II
O algoritmo inicia-se com a geração aleatória de uma população inicial, P
0
, de
tamanho N. Esta população é or denada de acordo o critério de não-do minâ ncia.
Em função do seu nível de não-dominância, cada solução recebe um rank, cor-
respondente ao índice da fro nteira à qual a solução pertence (1 é melhor nível, 2 é
o segundo melhor nível, e assim por diante).
Após a classificação das soluções, é gerada uma nova população Q
0
, de tamanho
N, através dos mecanismos de seleção, recombinação e mutação. Como o elitismo
é introduzido pela comparação da população corrente com a população anterior, o
procedimento é diferente após a geração inicial. A seguir, o algoritmo é descrito
para a t−ésima geração. O pseudocódigo do algoritmo, para a t−ésima geração, é
apresentado na Fig.
Procedimento NSGA-II
1 R
t
= P
t
Q
t
2 F = fast-nondomina ted- s ort(R
t
)
3 P
t+1
= 0
4 i = 1
5 Enquanto |P
t+1
|+|F
i
|≤ N
6 crowding-distance(F
i
)
7 P
t+1
= P
t+1
F
i
8 i = i + 1
9 Ordene(F
i
,≺
n
)
10 P
t+1
= P
t+1
F
i
[1 : (N − |P
t+1
|)]
11 Q
t+1
= crie − nova − populao(P
t+1
)
12 t = t + 1
Figura 3.13: Pseudocódigo do procedimento NSGA-II.
Inicialmente, com a combinação das populações P
t
e Q
t
, é formada a população
R
t
, de tamanho 2N. A população R
t
é então ordenada por não-dominância. Como
todas as populações (anteriores e corrente) estão incluídas em R
t
, é garantido o
elitismo do algoritmo.
As soluções pertencentes a F
1
são as melhores soluções na população combinada.
Se o tamanho de F
1
é menor que N, todas as soluções de F
1
são escolhidas para
a nova população, P
t+1
. Para completar P
t+1
, são escolhidos os indivíduos das
fronteiras subseqüentes. Deste modo, as próximas soluções a serem escolhidas são
3.6 Algoritmos Multiobjetivos baseados em AG’s 49
aquelas pertencentes à F
2
, seguidas pelas soluções de F
3
, e assim por diante. Este
procedimento continua, até que não seja mais possível acomodar inteiramente uma
fronteira. A última fronteira além da qual não podem mais ser adicionadas novas
fronteiras será chamada de F
L
.
Geralmente, a soma da s soluções de todas as fronteiras entre F
1
e F
L
são mai-
ores que o tamanho da população. Para que sejam escolhidos, ent ão, não mais que
N indivíduos, as soluções da fronteira F
L
são ordenadas de acordo com o crowded-
comparison operator≺
n
, em ordem decrescente. Em seguida, para finalizar o preen-
chimento da nova população, são escolhidas as soluções com m aior valor de crowding
distance, seguindo a lista ordenada obtida acima. Um esquema do comportamento
do NSGA-II é mostrado na Fig. 3.14.
P
t
Q
t
R
t
F
1
F
2
F
3
P
t+1
Rejeitadas
Crowding
Distance
Non-dominated
Sorting
Figura 3.14: Compor t amento do NSGA−II.
A nova população P
t+1
, de tamanho N, passa agora pelos processos de seleção,
crossover e mutação, dando origem a uma nova população Q
t+1
, de tamanho N.
Neste trabalho, o método NSGA-II foi adaptado para sua aplicação ao Problema
de Corte de Estoque Multiobjetivo. As principais adaptações estão nos operadores
de seleção, recombinação e mutação. Além disso, foi necessária a utilização de o utras
heurísticas e metaheurísticas para a obtenção de soluções que pudessem constituir a
população inicial do NSGA-II. O Capítulo 5 apresenta os detalhes da implementação
Algoritmo Evolutivo Multiobjetivo (AEMO) aplicado ao PCEB.
Capítulo 4
Algoritmos Evolutivos aplicados ao
PCDA
Nesta dissertação, para solucionar o Problema de Corte com Dimensão Aberta
(PCDA), caracterizado na seção 2.3, propõe-se um Algoritmo Evolutivo Híbrido
(AEH). Tal escolha se deve às diversas vantagens apresent adas pelos algo r itmos evo-
lutivos na resolução de problemas intratáveis por métodos convencionais. Optou- se,
ainda, por um algoritmo evolutivo híbrido, já que diversas combinações de algo rit-
mos, especialmente combinações entre AG e outras heurísticas ou metaheurísticas,
têm apresentado resultados promissores e muito superiores à queles obtidos pelo AG
convencional. O AEH desenvolvido neste trabalho apresenta a s seguintes particula-
ridades em relação a um AG convencional:
(a) No AG, a população inicial é gerada de maneira aleatória. No AEH, os indiví-
duos são gerados por duas metaheurísticas: Multi-Start (MS) e Iterated Local
Search (ILS). Assim, são originadas, para fins de comparação, duas versões do
AEH, designadas por AEH-MS e AEH-ILS.
(b) Em vez do operador de recombinação tradicional (uniforme ou n p ontos),
utilizou-se o operador Order Crossover (OX).
(c) Um operador de busca local é a plicado nos melhores indivíduos da população
a cada geração, realizando, assim, uma busca intensiva na vizinhança das
melhores soluções encontr adas pelo AEH, com o objetivo de atingir um número
maior de soluções com nível de aptidão mais alto.
A seguir, o algoritmo evolutivo proposto é descrito, bem como resultados computa-
cionais de sua a plicação são apresentados.
4.1 Representação de uma solução
Neste problema, um indivíduo representa a seqüência em que os itens serão
inseridos no objeto, ou seja, é um vetor de n valores inteiros, sendo n o número
de itens da solução. Assim, cada gene representa um item, e sua posição no vetor
indica a seqüência utilizada pelos algoritmos de encaixe de itens, descritos a seguir.
50
4.1 Representação de uma solução 51
Foram utilizados dois algoritmos aproximados t radicionalmente usados para a
resolução de problemas de corte bidimensional: First-Fit e Best-Fit. Estes algorit-
mos são capazes de gerar apenas padrões guilhotinados (um padrão de corte é a
forma como os itens são dispostos em um objeto).
Dada uma solução qualquer, o s dois algoritmos se iniciam com o encaixe dos
itens na ordem em que aparecem, até que a largura do objeto se torne insuficiente
para encaixar o próximo item. Neste momento, está formada a primeira faixa, cuja
altura corresponde ao item de maior altura presente nela.
A partir da segunda faixa, o s algoritmos encaixam os itens das seguintes f ormas:
- No algoritmo First-Fit, antes de um item ser inserido, são pesquisadas as
larguras disponíveis de cada faixa já formada, para avalia r a possibilidade de
encaixá-lo. Caso não seja possível sua inserção em nenhuma faixa já formada,
é criada uma nova faixa. Assim, os itens são alocados na primeira faixa em
que couberem, sem ultra pa ssar o comprimento L do objeto. Portanto, uma
nova faixa somente é formada quando não é possível encaixar o item em uma
faixa já existente.
- No algoritmo Best-Fit, ant es de um item ser inserido, são verificadas, além
da largura, a área restante de cada faixa já formada ( essa área é dada pela
diferença entre a área da faixa e a soma das áreas dos itens). O item será
encaixado na faixa onde o espaço for mais bem utilizado, ou seja, onde a
área restante após sua inserção seja menor. Se não for possível encaixá-lo, é
formada uma nova faixa.
O encaixe de itens utilizando os algoritmos First-Fit e Best-F i t descritos acima
é mostrado na Fig. 4.1.
2
5
6
8
3
7
1
R10
4
2
5
6
8
3
7
1
R10
4
2
5
6
8
3
7
1
R10
4
First-fit Best-fit
Figura 4.1: Ação dos algoritmos aproximados Fi rs t-Fit e Best-Fit.
Os pseudocódigos dos algoritmos são apresentados na F ig. 4.2, para o caso do
algoritmo First Fit, e na Fig. 4.3, par a caso do algoritmo Best Fit.
Os dois algoritmos são utilizados, portanto, como parte do método evolutivo
proposto. Na seção de resultados, além de listados os resultados obtidos pelo AEH
4.2 Representação de uma solução 52
procedimento First-fit()
1 L ← comprimento do o bjeto;
2 h
i
← altura do item i, i = 1, . . . , n;
3 l
i
← comprimento do item i, i = 1, . . . , n;
4 ldf
j
← L {comprimento disponível na faixa j, j = 1, . . . , n};
5 j ← 1;
6 para i = 1 até i = n faça
7 enquanto (l
i
> ldf
j
) faça
8 j ← j + 1
9 fim-enquanto
10 ldf
j
← ldf
j
− l
i
{insere o item i na fa ixa j}
11 fim-para;
fim First-fit();
Figura 4.2: pseudocódigo do a lg oritmo First-Fit.
procedimento Best-fit()
1 L ← comprimento do objeto;
2 h
i
← altura do item i, i = 1, . . . , n;
3 l
i
← comprimento do item i, i = 1, . . . , n;
4 hf
j
← 0 {altura da faixa j, j = 1, . . . , n};
5 ldf
j
← L {comprimento disponível na f aixa j, j = 1, . . . , n};
6 j ← 1;
7 para i = 1 até i = n faça
8 melhor
Rel
← ∞
9 A
i
← h
i
∗ l
i
; {área do item i}
10 para j = 1 até j = n faça
11 Adf
j
← hf
j
∗ ldf
j
; {área disp onível na faixa j}
12 Rel ← Adf
j
/A
i
; {relação da s áreas}
13 se (l
i
≤ ldf
j
) e (hi ≤ hf
j
) e (Rel < melhor
Rel
) então
14 melhor
Rel
← Rel
15 k ← j {armazena a faixa que contém a melhor relação}
16 fim-se
17 fim-para
18 ldf
k
← ldf
k
− l
i
{insere o item i na faixa k}
19 fim-para;
fim Best-fit();
Figura 4.3: pseudocódigo do a lg oritmo Best-Fit.
com a utilização de cada um dos algoritmos de encaixe, os desempenhos de ambos
são comparados.
4.2 Operadores genéticos 53
4.2 Operadores genéticos
4.2.1 Operadores de Recombinação
O cruzamento é o principal mecanismo do AG para explorar o espaço de busca,
através da criação de novo s pontos, obtidos pela troca de informação genética entre
os indivíduos.
Neste trabalho, deve-se evitar que uma operação provoque a repetição de uma
var iável em um mesmo individuo. Por isso, par a realizar o cruzamento (crossover),
foi utilizado o op eradorOrder Crossover (OX), aplicado com uma dada probabili-
dade. Este operador g era filhos a partir da escolha de uma seqüência parcial dos
genes de um dos pais, preservando a ordem relativa dos g enes do outro pai, conforme
descrito a seguir.
São escolhidos aleatoriamente dois indivíduos p
1
e p
2
(pais). Os pais são divididos
em três partes, por dois pontos de corte escolhidos a leato ri amente. Os filhos f
1
e
f
2
herdam a parte do meio de seus respectivos pais, p
1
e p
2
. Em seguida, partindo
do segundo corte de um pai (por exemplo, p
2
), copiam-se, em f
1
, os elementos de
p
2
, na ordem em que aparecem, sendo removidos os elementos contidos entre os dois
cortes do outro pai (no caso, p
1
), conforme a Fig. 4.4 .
p
1
= (1 6 8 | 3 2 5 | 4 7) p
2
= (6 2 7 | 1 4 3 | 5 8)
f
1
= (7 1 4 | 3 2 5 | 8 6) f
2
= (8 2 5 | 1 4 3 | 7 6)
Figura 4.4: Operador de Recombinação.
4.2.2 Operadores de Mutação
A mutação é um operador genético que tem a função de introduzir caracterís-
ticas na população, ou mesmo recuperar aquelas que se perderam em operações,
como, por exemplo, o operador de recombinação. Além disso, a mutação é usada
para prevenir a convergência prematura para ótimos locais, através da amostragem
de novos pontos no espaço de busca. Este operador é aplicado, numa dada pro-
babilidade, a cada descendente individualmente, após a aplicação do operador de
recombinação. Neste trabalho, foram aplicados dois operadores de mutação, esco-
lhidos aleatoriamente, em indivíduos também selecionados de forma aleatória. São
eles:
- Operador troca: consiste em trocar a ordem de encaixe de dois itens, escolhidos
aleatoriamente, conforme ilustrado na Fig. 4.5. Nesse operador, dado um
conjunto de n itens, existem n(n − 1)/ 2 indivíduos mutantes possíveis.
- Operador realocação: consiste em realocar um item da posição i para a posição
j, sendo i e j escolhidos aleatoriamente. Nesse operador, dado um conjunto de
n itens, existem (n − 1)
2
indivíduos mutantes possíveis. Po r exemplo, sendo
4.3 Operadores de Mutação 54
s = (1 6 8 3 2 5 4 7)
s’ = (1 6 5 3 2 8 4 7)
Figura 4.5: Operador de mutação: tr oca.
i = 2 e j = 6 (realocar o item da segunda posição para a sexta posição),
obtém-se, a partir do individuo s, o indivíduo mutante s
′
mostrado na Fig.
4.6. Nessa estrutura, são permitidos movimentos para posições sucessoras
(como no exemplo acima) ou antecessoras à posição em que o item se encontra
na seqüência do vetor.
s = (1 6 8 3 2 5 4 7)
s’ = (1 8 3 2 5 6 4 7)
Figura 4.6: Operador de mutação: realocação.
- Operador realoca gr upo: consiste em realocar um grupo composto por x itens
que ocupam posições seqüenciais dentro do vetor de solução, ou seja, de j até
j + x. O t amanho (x) deste grupo de itens, obtido experimentalmente, var ia
entre 2 e 6 itens. A nova posição k do primeiro item do grupo é escolhida
de f orma aleatória. O grupo de itens de tamanho x será então realocado nas
posições k até k + x , desde que k = j e k ≤ n − x, em que n representa o
número de itens da solução.
- Operador troca altura: consiste em realocar um item, escolhido aleatoria-
mente, que ocupa a po sição j do vetor de solução, para uma nova posição k,
escolhida da seguinte maneira: inicialmente, calcula-se o módulo da diferença
(dif) entre as altura s h do item da posição j e do item da posição j + 1,
ou seja dif =| h
j
− h
j+1
| . Em seguida, é pesquisada uma posição k tal
que | h
j
− h
k
|< dif. Para evitar uma busca exaustiva pela posição k, são
executados 0, 1
∗
n pesquisas, sendo n o número de itens da solução. Se não
for encontr ada uma p osição que ob edeça à condição acima, o item não será
realocado.
4.3 Função de custo e função de aptidão dos indiví-
duos
Função de custo dos indivíduos
A função de custo é a altura utilizada do objeto em determinada solução, obtida após
a execução de um procedimento de encaixe dos itens, o u seja, a solução é avaliada
4.5 Seleção dos indivíduos para a próxima geração 55
pela própria função objetivo, dada pela expressão (2.1) do modelo de Programação
Linear Inteira apresentado no seção 2.3.
Função de aptidão de um indivíduo
A função de aptidão avalia a possibilidade de sobrevivência de cada indivíduo gerado
pelo AG. A partir desta avaliação, é possível descobrir o grau de adaptação dos
indivíduos e eliminar aqueles menos adaptados. Devido à utilização do mecanismo
da roleta para selecionar os indivíduos da próxima geração, não foi possível usar a
função de custo como função de aptidão, pois este trabalho trata de um problema
de minimização. Além disso, o método da roleta depende muito da escala da função
de aptidão. Por exemplo, considerando-se uma população com 10 indivíduos com
os seguint es valores de função de aptidão: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, a probabilidade
de seleção do melhor indivíduo (com aptidão igual a 10) é de 16, 6% e a do pior
1, 5 %. Se, aos valores de função de aptidão de todos os indivíduos, forem somadas
100 unidades, as probabilidades de escolha do melhor e pior indivíduo passam a ser
de 10, 4% e 9, 5%, respectivamente. Como pode ser observado, as probabilidades
tornaram-se muito próximas. Esta é uma cara cterística indesejável, que provocou o
surgimento de vários métodos de escalonamento. O método utilizado neste trabalho
foi o escalonamento linear.
No procedimento de escalonamento, para converter o valor da função objetivo em
função de a ptidão , é utilizada uma função linear. Neste trabalho, a função utilizada
é dada por uma equação que corresponde à equação da reta, que passa pelos pontos
(f
min
, a) e (f
max
, β). Considerando β = 0, tem-se:,
f
aptidao
(s) =
a (f
max
− fo(s))
(f
max
− f
min
)
para:
• fo(s) = valor da função objetivo da solução s;
• f
aptidao
(s) = valor da função de aptidão da solução s;
• f
max
= valor máximo de função objetivo encontrado na po pulação;
• f
min
= valor mínimo de função objetivo encontrado na população;
• a = valor da função de aptidão atribuída ao indivíduo com f
min
;
• β = valor da função de aptidão atribuída a o indivíduo com f
max
.
4.4 Seleção dos indivíduos para a próx ima geração
O mecanismo de seleção para as próximas gerações utilizado foi o método da
roleta, descrito na seção 3.4.2. Como este método po de fa zer com que o melhor
indivíduo da população seja perdido, optou-se por uma seleção elitista, que mantém
(após um refinamento) na nova população, as duas melhores soluções da população.
4.6 Geração da população inicial 56
4.5 Geração da população inicial
Para gerar uma população inicial, são utilizados vários procedimentos, que po-
dem ser aleatórios ou heurísticos. Gerar soluções aleatórias diversifica o espaço de
soluções, mas, geralmente, cria soluções de baixa qualidade, que exigem um temp o de
processamento muito elevado para ser melhorada. Por outro lado, soluções gulosas,
apesar de serem de boa qualidade, apresentam baixa diversidade. Como alternativa
aos métodos totalmente aleatórios ou totalmente gulosos, vários autores sugerem a
utilização de heurísticas para gerar a população inicial.
Neste trabalho foram implementadas e testadas as metaheurísticas ILS e Multi-
Start, conforme descrito em Andrade et al. (2008a) e Andrade et al. (2008 b), para a
geração da população inicial do AEH. A aplicação das metaheurísticas ao problema
é detalhada a seguir.
4.5.1 Geração da po pulação i nicial - ILS
Os seguintes procedimentos são utilizados neste trabalho nas etapas que com-
põem o ILS:
(a) Geração da solução inicial: solução inicial gerada aleatoriamente;
(b) Busca Local: Método Randômico de Descida, utilizando, como estrutura de
vizinhança, os movimentos descritos na seção 4.2, usados originalmente como
operadores de muta ção ;
(c) Perturbação: em cada nível, são escolhidos aleatoriamente e aplicados à solu-
ção os movimentos descritos na seção 4.2, por (nível + 1);
(d) Critério de aceitação: valor da função de avaliação.
O pseudocódigo da implementação desenvolvida neste trabalho é apresentada na
Fig. 4.7.
4.5.2 Geração da po pulação i nicial - Multi-Start
Na primeira fase de construção do algoritmo Multi-Start, uma solução é constru-
ída aleatoriamente. Na segunda fase, a busca local aplicada sobre a solução obtida
na construção é o Método Randômico de Descida, utilizando a mesma estrutura
de vizinhança descrita acima. O critério de parada do algoritmo é o número de
iterações sem melhora (MS
max
).
Os resultados obtidos com os métodos apresentados, assim como os parâmetros
utilizados, são descritos na seção de experimentos computacionais a seguir.
4.6 Experimentos Computacionais
O Algo ritmo Evolutivo Híbrido proposto (AEH) foi implementado na linguagem C, e
compilado em C++ Builder 5.0; enquanto a formulação de programação matemática
do PCDA apresenta da na seção 2.4.3 foi resolvida no otimizador CPLEX, versão 11.
4.6 Problemas teste para o PCDA 57
procedimento ILS(·)
1 s
0
← ConstroiSoluçaoAleatoria(·);
2 s ← DescidaRandomica(s
0
);
3 nivel = 1; iter = 1;
4 enquanto (nivel < n
niveis
) faça
5 enquanto (iter < ILS
max
) faça
6 s
′
← Perturbação(s, nivel);
7 s
′′
← DescidaRandomica(s
′
);
8 se (f(s”) < f(s)) então
9 s ← s";
10 nivel ← 1;
11 iter ← 0;
12 senão
13 iter ← iter + 1;
14 fim-enquanto
15 nivel ← nível + 1;
16 iter ← 0;
17 fim-enquanto
18 Retorne s;
19 fim-enquanto;
8 Retorne s;
fim ILS();
Figura 4.7: Pseudocódigo da Metaheurística ILS para geração de solução inicial para
o PCDA.
Os testes computacionais foram feitos em um PC Intel Core 2 Quad (Q6600) 2.40
GHz, com 8 GB de RAM, tendo, como sistema operacional, o ambiente Windows
Vista Ultimate.
4.6.1 Proble mas teste para o PCDA
Para avaliar o AEH proposto, foram utilizados os problemas-teste de Hopper e
Turton (2001b), disponíveis na OR-Library Beasley (1990). Estes problemas-teste
foram construídos para um problema de corte/empacotamento bidimensional com
as seguintes características:
• Um conjunto de itens, que podem conter itens idênticos;
• Um único objeto com comprimento fixo e altura infinita;
• Todas as peças são retangulares.
Ressalta-se que, apesar de ser possível a existência de itens com dimensõ es idên-
ticas em um problema-teste, os tipos de itens são muito diversificados, ou seja, cada
4.6 Problemas teste para o PCDA 58
problema-teste apresenta um elevado número de tipos diferentes de itens. Essa di-
versificação dos itens se mostrou bastante adequada ao modelo implementado neste
trabalho (Lodi et a l., 2004), para validação dos métodos aqui propostos, pois o
mesmo trata de um problema irrestrito. Assim, apesar de existirem poucos itens
idênticos em um mesmo problema-teste, quando isto ocorre, estes dois (ou mais
itens) são considerados itens diferentes, cada um com uma demanda associada ig ua l
a um.
Os problemas-teste de Hopper e Turton (2001b) foram construídos de forma a
não apresentarem perda quando solucionados de maneira não-guilhotinada e com
a rotação ortogonal dos itens permitida. Eles estão divididos em sete categorias,
sendo que cada categoria contém três problemas. Cada categoria dos problemas-
teste apresenta o número de itens, o comprimento do objeto (L
obj
) e a altura ótima
(H
∗
), conforme a Tabela 4.1. Para cada problema são dados o comprimento e altura
dos itens.
Tabela 4.1: Problemas-teste de Hopper e Turton (2001)
Categoria N
o
de itens L
obj
H
∗
P1 P2 P3
C1 16 17 16 20 20
C2 25 25 25 40 15
C3 28 29 28 60 30
C4 49 49 49 60 60
C5 73 73 73 60 90
C6 97 97 97 80 120
C7 196 197 196 160 240
A seguir, são apresentados o s resultados obtidos, a partir dos dados dos pro-
blemas-teste, par a o PCDA guilhotinado, nos termos tratados no presente trabalho,
aplicando-se o otimizador CPLEX, versão 11.0, e o AEH proposto. São apresentados
e comparados os resultados das duas versões do AEH, utilizando as metaheurísticas
ILS e Multi-Start, pa r a geração da população inicial. As versões do método serão
chamadas, a partir deste momento, de AEH
MS
e AEH
ILS
.
Também é feita a comparação dos métodos de encaixe (Fi rs-Fit e Best-Fit). Por-
tant o, para cada versão do AEH, serão apresentado s e discutidos os resultados envol-
vendo cada um dos algo ritmos de encaixe (AEH
MS(F F )
, AEH
MS(BF )
, AEH
ILS(F F )
e AEH
ILS(BF )
).
Neste ponto, é importante ressaltar que estes r esultados, na medida em que tra-
tam do PCDA guilhotinado e sem a rotação dos itens, têm soluções com alturas
maiores que as alturas ótimas encontradas nos problemas-teste, solucionados, se-
gundo sua formulação orig inal, de fo rma não-guilhotinada e com a rotação dos itens
permitida.
Para testar todas as versões do AEH, for am resolvidos problemas-teste com 16
a 196 itens, tot alizando 21 problemas. Cada problema foi resolvido 10 vezes pelos
métodos propostos. Os parâmetros dos AEH’s, obtidos experimenta lmente, são
apresentados na Tabela 4.2.
4.6 Resultados do AEH-MS 59
Tabela 4.2: Parâmetros dos méto do s AEH
MS
e AEH
ILS
, sendo n o número de itens
do problema-teste.
Parâmetros Valores
Categoria do Problema-teste C1, C2, C3, C4 N
o
de indivíduos n
C5, C6, C7 n/2
C1,C2,C3,C4,C5,C6 N
o
de gerações n
C7 n/2
Parâ metro α da função de escalamento linear 100
Probabilidade de recombinação ( p
c
) 0,85
Probabilidade de mutação (p
m
) 0,05
Número máximo de iterações sem melhora do Multi-Start (MS
max
) 50
Número máximo de iterações sem melhora do ILS (ILS
max
) 20
Número máximo de iterações sem melhora do MRD (MRD
max
) n
4.6.2 Resultados do AEH-MS
A Tabela 4.3 apresenta os resultados dos experimentos computacionais. A pri-
meira coluna apresenta o problema-teste e a segunda, o número de itens correspon-
dente. A terceira coluna a presenta os r esultados obtidos pela resolução do modelo
matemático apresentado na seção 2.3, pelo software de otimização CPLEX, versão
11.0, limitado a uma hora de processamento.
Nas colunas “Melhor Solução” e “Solução Média” são apresentados, para cada
problema-teste e para cada versão do AEH, o valo r da melhor solução obtida em
dez execuções do algoritmo e o valor médio, respectivamente. As últimas três colunas
apresentam o tempo de processamento do CPLEX e das duas versões do AEH. O
erro relativo, apresentado nas oitava e nona colunas, é calculado pela expressão:
gap =
(r
medio
− r
melhor
)
r
melhor
× 100
em que r
medio
é o resultado médio obtido pela aplicação do AEH e r
melhor
é o resul-
tado obtido pelo otimizador CPLEX para cada problema-teste.
Como pode ser observado pela Tabela 4 .3 , o CPLEX obteve a solução ótima para
todos os problemas-teste com até 49 itens, e também para um problema com 73 itens.
Para o restante dos problemas, este otimizador não foi capaz de provar a otimalidade
das soluções obtidas em uma hora de execução. O desvio da solução média produzida
pelo método AEH
MS(F F )
chegou a 18,63%, e, para o AEH
MS(BF )
, não ultrapassou
10,87%. Os tempos de processamento variaram, para o AEH
MS(F F )
, de 0,07 a 26,38
segundos e, para o AEH
MS(BF )
, de 0 ,21 a 487,40 segundos, em média. Observa-se
que o AEH
MS(F F )
alcançou o resultado ótimo conhecido para os problemas-teste
com até 29 itens e para um problema com 49 itens. O AEH
MS(BF )
alcançou o
resultado ótimo para todos os problemas com até 4 9 itens e para um problema com
73 itens. Com relação aos tempos de pro cessamento , nota-se que par a problemas
com mais de 49 itens os tempos gastos pelos algoritmos propostos foram, geralment e,
inferiores àqueles demandados pelo otimizador aplicado ao modelo de PLI.
4.6 Resultados do AEH-MS 60
Tabela 4.3: Resutados do AEH
MS
aplicado ao PCDA.
Problema n Melhor solução Solução média Gap(%) Tempo Médio (s)
Exato AE
F F
AE
BF
AE
F F
AE
BF
AE
F F
AE
BF
Exato AE
F F
AE
BF
C1P1 16 27* 27* 27* 27* 27* 0 0 0,10 0,07 0,23
C1P2 17 29* 29* 29* 29* 29* 0 0 0,12 0,08 0,25
C1P3 16 23* 23* 23* 23* 23* 0 0 0,05 0,07 0,22
C2P1 25 20* 20* 20* 20* 20* 0 0 0,06 0,07 0,21
C2P2 25 34* 34* 34* 34* 34* 0 0 0,18 0,17 0,69
C2P3 25 23* 23* 23* 23* 23* 0 0 0,06 0,07 0,22
C3P1 28 40* 40* 40* 40,90 40* 2,25 0 0,12 0,15 0,58
C3P2 29 42* 42* 42* 42,10 42* 0,24 0 0,09 0,18 0,63
C3P3 28 43* 43* 43* 44,50 43* 3,49 0 0,13 0,17 0,61
C4P1 49 74* 74* 74* 76,90 75 3,92 1,35 15,74 2,15 13,39
C4P2 49 74* 77 74* 78,40 75,40 5,95 1,89 1,02 2,15 13,31
C4P3 49 80* 81 80* 82,70 80,50 3,38 0,63 0,80 2,00 13,03
C5P1 73 101 102 101 105,30 102,30 4,26 1,29 3600** 7,32 92,73
C5P2 73 106* 106* 106* 108,70 106,50 2,55 0,47 27,25 8,54 93,57
C5P3 73 106 109 106 113,10 107,30 6,70 1,23 3600** 8,14 89,82
C6P1 97 136 144 137 150,10 140,24 10,37 3,12 3600* * 11,13 136,63
C6P2 97 145 152 145 154,40 146,90 6,48 1,31 3600** 11,12 148,02
C6P3 97 139 145 141 148,90 142,80 7,12 2,73 3600** 11,17 148,91
C7P1 196 263 310 282 312,00 291,60 18,63 10,87 3600* * 23,79 458,97
C7P2 197 283 309 292 319,10 299,20 12,76 5,72 3600** 26,38 487,40
C7P3 196 283 319 299 329,60 302,20 16,47 6,78 3600** 24,95 457,56
* Solução ótima * * Limite de tempo de execução
4.6.3 Resultados do AEH-ILS
A Tabela 4.4 apresenta os resultados do algoritmo evolutivo no qual a população
inicial é gerada pela metaheurística ILS. Pode-se observar que as duas versões do
4.7 Conclusões 61
método encontraram o ótimo conhecido para todos os problemas com a t é 29 itens,
sendo que o AEH
ILS(BF )
encontrou a solução ótima para todos os problemas com
49 itens e para um problema com 73 itens. Além disso, o desvio da solução média
chegou a 19,6% no AEH
ILS(F F )
e, no método AEH
ILS(BF )
, não ultrapassou 9,5%.
4.7 Conclusões
Nos experimentos computacionais realizados mostrou-se a imp ortância do uso de
uma heurística que gere soluções de boa qualidade para inicializar um AG e ta mbém
a necessidade de incorporar, ao AG, um mecanismo eficiente de busca local. Foi
observado que o trabalho computacional adicional exigido pela busca local pode ser
compensado pela redução do número de indivíduos e do número de iterações do
algoritmo.
O algoritmo heurístico proposto foi aplicado nos problemas-teste de Hopp er e
Turton (2001b), que tratam o PCDA de forma não-guilhotinada. Mostrou-se nos
experimentos que o AEH
MS
e o AEH
ILS
propostos alcançaram as soluções ót imas
dos pro blemas com até 49 itens. Em um pro blema-teste, com 73 itens, o AEH
MS
,
em suas duas versões (First-Fit e Best-Fit) e o AEH
ILS(BF )
encontraram a solução
ótima conhecida.
Em termos de valor da função de avaliação, as versões do método que utilizaram
o First-Fit apresentaram, para problemas com mais de 49 itens, resultados bastante
inferiores àqueles obtidos pelas versões com o Best-F i t. É demonstrada, assim, a
sup erioridade do algoritmo aproximado Best-Fit em relação ao First-Fit, quando os
problemas-testes usados têm um número gra nde de itens.
O método AEH
ILS
encontrou, em t ermos de função de avaliação, para pro blemas
com mais de 49 itens, resultados ra zoavelmente melhores que os encontrados pelo
AEH
MS
. Isso mostra a eficiência do ILS para esse tipo de problema.
O tempo de processamento das quatro versões do algoritmo, para problemas
com mais de 49 itens, foi pequeno se comparado ao tempo gasto pelo método exato,
nos problemas com mais de 4 9 itens. Ressalta-se que a grande diferença observada
entre os tempos médios das versões com o First-Fit e o Best-Fit se deve ao modo
como são encaixados os itens. O Best-F i t sempre pesquisa todas as fa ixas formadas
antes de alocar um item, ao passo que o First-Fit p esquisa as faixas somente até
encontrar a primeira faixa onde é p ossível encaixar o item. O primeiro algoritmo
exige, portanto, um esforço computacional maior.
Os resultados obtidos e descritos acima mostram o potencial da técnica proposta
e a possibilidade da utilização desta em situações práticas.
4.7 Conclusões 62
Tabela 4.4: Resutados do AEH
ILS
aplicado ao PCDA.
Problema n Melhor solução Solução média Gap (%) Tempo Médio (s)
Exato AE
F F
AE
BF
AE
F F
AE
BF
AE
F F
AE
BF
Exato AE
F F
AE
BF
C1P1 16 27* 27* 27* 27* 27* 0 0 0,10 0,05 0,12
C1P2 17 29* 29* 29* 29* 29* 0 0 0,12 0,05 0,14
C1P3 16 23* 23* 23* 23* 23* 0 0 0,05 0,05 0,12
C2P1 25 20* 20* 20* 20* 20* 0 0 0,06 0,07 0,22
C2P2 25 34* 34* 34* 34* 34* 0 0 0,18 0,20 0,70
C2P3 25 23* 23* 23* 23* 23* 0 0 0,06 0,07 0,21
C3P1 28 40* 40* 40* 40,9 40* 2,25 0 0,12 0,20 0,65
C3P2 29 42* 42* 42* 42,1 42* 0,24 0 0,09 0,22 0,70
C3P3 28 43* 43* 43* 44,5 43* 3,49 0 0,13 0,21 0,69
C4P1 49 74* 75 74* 77,4 75 4,59 1,08 1 5,74 1,75 9,23
C4P2 49 74* 76 74* 79,2 75,2 7,03 1,62 1,02 1,88 9,90
C4P3 49 80* 83 80* 84,3 80,7 5,38 0,88 0,80 1,72 9,01
C5P1 73 101 106 101 109 102,4 7,92 1,39 3600** 3 ,76 45,75
C5P2 73 106* 110 106* 112,4 106,4 6,04 0,38 27,25 4,24 51,27
C5P3 73 106 113 106 116,7 107,3 10,09 1,23 3600* * 3,76 47,6 0
C6P1 97 136 145 137 150,7 138,3 10,81 1,69 3600* * 18,48 235,56
C6P2 97 145 154 145 155,8 146,8 7,45 1,24 3600** 19,14 245,60
C6P3 97 139 148 141 151 142,6 8,63 2,59 3600** 18,35 239,76
C7P1 196 263 306 280 314,5 288,1 19,58 9,54 3600** 90,30 1533,75
C7P2 197 283 309 292 320,5 295,7 13,25 4,49 3600** 101,39 1712,1 0
C7P3 196 283 313 292 323,9 297,1 14,45 4,98 3600** 97,06 1661,57
* Solução ótima * * Limite de tempo de execução
Capítulo 5
Algoritmo Evolutivo Multiobjetivo
aplicado ao PCEB
O objetivo deste Capítulo é apresentar a aplicação de um Algoritmo Evolutivo Mul-
tiobjetivo (AEMO) ao Problema de Corte de Estoque Bidimensional Multiobjetivo.
Na seção a seguir, é descrita a estratégia desenvolvida para a construção das so-
luções. A seção 5.2 mostra os detalhes da implementação do AEMO aplicado ao
PCEB. Na seção 5.3, são propostos os problemas-teste utilizados para avaliar o mé-
todo, assim como testes computacionais realizados, além dos resultados obtidos e
sua análise.
5.1 Geração de Padrões
No capítulo 2 é visto que uma das etapas da modelagem mat emática do Problema
de Corte de Estoque é a definição de todos os possíveis padrões de corte. Trata-
se de um problema combinatório no qual, para algumas dezenas de tipos de itens,
podem ser encontrados milhões ou bilhões de padrões distintos. Entretanto, a etapa
de geração dos padrões não precisa ser realizada completamente, ou seja, é possível
encontrar boas soluções a part ir de um número finito de padrões.
Neste trabalho, optou-se por gerar um tipo de padrão de corte conhecido na
literatura como padrão de corte guilhotinado bidimensional em 2-estágios não-exato.
Considera-se que o padrão é não-exato quando ao menos um item necessitar de
ajuste, o que ocorre quando os tipos de itens requeridos não são cortados em sua
totalidade na guilhotina. Além disso, o problema de corte aqui tratado é irrestrito,
ou seja, não há limitações para o número de vezes em que um mesmo tipo de item
pode aparecer no padrão.
Para gerar os padrões (guilhotinados bidimensionais em 2-estágios não-exatos),
foi utilizado um método exato de duas fases, baseado nos trabalhos de Hifi e Hallah
(2006) e Morabito e Garcia (1998). O uso de modelos de duas fases é comum na
literatura, devido ao êxito obtido pelo modelo proposto em Gilmore e Gomory (1 965)
para o corte de chapas retangulares.
Morabito e Garcia (1998) apresentam uma abor da gem para o problema de corte
numa fábrica brasileira de chapas de fibra de madeira reconstituída, na qual estão
envolvidas restrições pouco usuais, como limitações para a diferença entre o maior
63
5.1 Etapa de Geração das Faixas 64
e menor comprimento dos tipos presentes no padrão. O problema é modelado em
duas fases, cada uma por meio de um problema de otimização inteira, e resolvido
utilizando-se um método baseado em enumeração implícita. Em seu trabalho, Hifi e
Hallah (2006) também utiliza um método de duas fases para solucionar um problema
de corte restrito.
O método de duas fases, com base nos autores citados, é utilizado neste tra-
balho na geração dos padrões de corte. Com respeito aos dados do problema, são
considerados:
- objetos com comprimento L e altura H;
- um conjunto de itens I = 1, . . . , n, tendo cada item i ∈ I comprimento l
i
e
altura h
i
.
Além disso, considera-se que os itens estão or denados de forma crescente com relação
à a ltura , ou seja, h
1
≤ h
2
≤ . . . ≤ h
n
.
As duas fases da modelagem do pro blema de geração de padrões são as seguintes:
(i) Escolha dos itens que serão arranjado s ao longo de faixas de comprimento
L e alturas variáveis, especificadas a seguir. Com esse processo são obtidas,
portanto, a s faixas que integrarão o padrão.
(ii) Escolha das faixas que serão arranjadas ao longo da altur a H do obj eto de
dimensões (L, H).
As duas etapas do método são descritas nas seções a seguir.
5.1.1 Etapa de Geração das Faixas
Para geração das faixas, foram utilizadas três abordagens, detalhadas a seguir.
Abordagem 1
Nesta abordagem, são geradas faixas uniformes, ou seja, faixas com comprimento
L que possuem itens com a mesma altura. Para ta nto, inicialmente, os itens são
ordenados de for ma crescente com relação à altura. Em seguida, os itens (i ∈ I)
são agrupados em função de sua altura em r grupos, que formam o conjunto J =
{1, ..., r}, no qual cada item i do grupo j ∈ J possui altura h
i
=
¯
h
j
.
Para cada grup o j ∈ J, deseja-se encontrar a melhor combinação de itens do
tipo i, para cada uma das r faixas (L, h
j
). Deve-se o bservar, ainda, que uma faixa
uniforme só será construída para grupos j ∈ J que tenham ao menos um item i tal
que h
j
= h
i
, j = i, ou seja, são formadas faixas uniformes com dois ou mais itens
de mesma altura, mas de comprimentos distintos. Sejam:
• F
1
h
j
: valor da melhor combinação de itens na faixa (L, h
j
).
• x
ij
: número de vezes que o item i aparece na faixa j.
• S
¯
h
j
= {i ∈ I, h
i
=
¯
h
j
}: conjunto dos itens com a mesma altura.
5.1 Etapa de Geração das Faixas 65
Cada valor F
1
h
j
pode ser obtido com a solução do seguinte Problema da Mochila
Irrestrito P MI
1
:
P MI
1
max F
1
h
j
=
i∈S
¯
h
j
l
i
h
i
x
ij
(5.1)
sujeito a
i∈S
¯
h
j
l
i
x
ij
≤ L (5.2)
x
ij
≥ 0 e inteiro (5.3)
Após a resolução do problema acima, caso o modelo não t enha utilizado todo o
comprimento da faixa, o comprimento restante L
rest
é completado, resolvendo-se o
(P MI
2
) com os próximos itens i tal que {i ∈ Q
¯
h
j
= {i ∈ I, h
i
<
¯
h
j
}}.
P MI
2
max F
2
h
j
=
i∈Q
¯
h
j
l
i
h
i
x
′
ij
(5.4)
sujeito a
i∈Q
¯
h
j
l
i
x
′
ij
≤ L
rest
(5.5)
x
′
ij
≥ 0 e inteiro (5.6)
Verificou-se, experimentalment e, que a tentativa de utilizar o comprimento res-
tante da faixa gera resultados melhores do que aqueles obtidos apenas com o primeiro
modelo.
Os itens que compõem as faixas, assim como sua freqüência, são dados pelo valor
obtido para as variáveis x
ij
e x
′
ij
. Portanto, o cálculo da perda de cada faixa, em
área, é dado por:
P erda = L
¯
h
j
− (F
1
h
j
+ F
2
h
j
)
Para exemplificar a abordagem, considere a formação de faixas unifor mes em um
problema de corte com as seguintes cara cterísticas: objetos com dimensões (100, 1 00)
e 4 tipos de itens, com as dimensões (l
i
, h
i
) constantes na F ig. 5.1.
No exemplo, tem-se I = 1, 2, 3 , 4 e J = 1, com h
1
= h
2
(existe, porta nto, apenas
um gr upo de dois itens distintos que têm a mesma altura) . Considerando os itens
1 e 2, é, então, solucionado o P MI
1
, que resulta na faixa mostrada na Fig. 5.2. A
solução para o P MI
1
é x
11
= 2, x
12
= 2, com F
1
h
1
= 3000 e P erda = 0. Como a
faixa é completamente utilizada, nã o é solucionado o P MI
2
.
O pseudocódigo do procedimento é apresentado na Fig. 5.3.
Abordagem 2
Esta abordagem se inicia com a construção de n f aixas, que contém, cada uma,
apenas um item i, i ∈ I. Em seguida, o compriment o restante da faixa (L −
l
i
) é completado, resolvendo-se um Problema da Mochila Irrestrito com os itens
k, k = i + 1, . . . , n, tal que h
k
≤ h
i
. Esse processo garante que todos os itens
5.1 Etapa de Geração das Faixas 66
100
100
1
30
30
2
30
20
3
20
40
4
Objeto
Itens ( )l ,h
i i
15
10
Figura 5.1: Exemplo da Abordagem 1.
11
2
2
Figura 5.2: Faixa formada pela Abordagem 1.
Procedimento 1
1 Para j = 1 até r faça
2 S
¯
h
j
= {i ∈ I, h
i
=
¯
h
j
};
3 (F
1
h
j
, x
ij
) ←Resolva (P MI
1
);
4 L
rest
= L −
i∈S
¯
h
j
l
i
x
ij
;
5 Se (L
rest
> 0) faça
6 Q
¯
h
j
= {i ∈ I, h
i
<
¯
h
j
};
7 (F
2
h
j
, x
′
ij
) ←Resolva (P MI
2
);
8 fim-se;
9 Crie a faixa j usando x
ij
e x
′
ij
;
10 P erda =
¯
h
j
L − (F
1
h
j
+ F
2
h
j
)
11 fim-para;
fim Procedimento 1;
Figura 5.3: Pseudocódigo da Abordagem 1 para a geração de faixas.
estarão presentes no conjunto de faixas. O Problema da Mochila Irrestrito (P MI
3
)
é apresentado a seguir.
5.1 Etapa de Geração das Faixas 67
P MI
3
max F
3
=
n
k=i+1
l
k
hkx
ki
(5.7)
sujeito a
n
k=1+1
l
k
x
ki
≤ L − l
i
(5.8)
x
ki
≥ 0 e inteiro (5.9)
Neste problema, x
ki
representa o número de vezes que o item k aparece na faixa
iniciada por i e n é o número de itens.
Os itens que pertencem à faixa, assim como sua freqüência, são dados, portanto,
pela valor da variável x
ki
, além de uma unidade do item i. A perda em cada faixa
é dada por:
P erda = Lh
i
− (l
i
h
i
+ F
3
)
O pseudocódigo do procedimento é apresentado na Fig. 5.4.
Procedimento 2
1 Para i = 1 até n faça
2 Para k = i + 1 até n faça (Percorre o restante dos itens)
3 (F
3
, x
ki
) ← Resolva (P MI
3
);
4 fim-para;
5 Crie a faixa i usando 1 unidade do item i e x
ki
;
6 P erda = Lh
i
− (l
i
h
i
+ F
3
)
7 fim-para;
fim Procedimento 2;
Figura 5.4: Pseudocódigo da Abordagem 2 para a geração de faixas.
Considerando o exemplo dado na Abordagem 1, com a aplicação da Abordagem
2 tem-se a formação das faixas mostradas na Fig. 5.5.
A solução do P MI
3
para o exemplo é a seguinte:
- Primeira faixa: x
21
= 3, x
41
= 3, F
3
= 1950, P erda = 5%;
- Segunda faixa: x
32
= 2, F
3
= 1600, P erda = 26, 66%;
- Terceira faixa: x
43
= 6, F
3
= 900, P erda = 15%;
Abordagem 3
Na terceira abordag em do procedimento de for mação das f aixas, para cada item
i, i ∈ I, é construida uma faixa homogênea (i.e. faixa que contém apenas um
tipo de item). Em seguida, é verificado o comprimento restante da faixa (L
rest
=
L − (⌊L/l
i
⌋l
i
)). Caso seja possível (se L
rest
for maior que o comprimento do item
de menor l
i
), o compriment o restante é completado resolvendo-se o P MI
4
com os
5.1 Etapa de Geração das Faixas 68
2
3
3
3
4
4 4
4 4
4
1 22
4
2
Figura 5.5: Faixas formadas pela Aborda gem 2.
próximos itens (itens k, k = i + 1, . . . , n, t al que h
k
≤ h
i
). O Problema da Mochila
Irrestrito ( P MI
4
) é apresentado a seguir.
P MI
4
max F
4
=
n
k=i+1
l
k
h
k
x
ki
(5.10)
sujeito a
n
k=i+1
l
k
x
ki
≤ L − ⌊L/l
i
⌋l
i
(5.11)
x
ki
≥ 0 e inteiro (5.12)
Neste problema, x
ki
representa o número de vezes que o item k aparece na faixa
homogênea de itens i. A perda de cada faixa é dada por:
P erda = Lh
i
− (⌊L/l
i
⌋l
i
h
i
+ F
4
)
O pseudocódigo do procedimento é apresentado na Fig. 5.6.
Procedimento 3
1 Para i = 1 até n faça
2 Para k = i + 1 até n faça (Percorre o restante dos itens)
3 (F
4
, x
ki
) ← Resolva (P MI
4
);
4 fim-para;
5 Crie uma faixa i usando ⌊L/l
i
⌋ itens i e x
ki
;
6 P erda = Lh
i
− (⌊L/l
i
⌋l
i
h
i
+ F
4
)
7 fim-para;
fim Procedimento 3;
Figura 5.6: Pseudocódigo da Abordagem 3 para a geração de faixas.
Considerando o exemplo referente à Abordagem 1, com a aplicação da presente
abordagem formam-se as faixas mostradas na Fig. 5.7 .
A solução do P MI
4
para o exemplo é a seguinte:
5.2 Etapa de Geração dos Padrões 69
4
3
3
4
4
4
4 4
4
4
4
4
4
4
4
11 1
2
2
2
2
2
Figura 5.7: Faixas formadas pela Aborda gem 3.
- Primeira faixa: x
41
= 1, F
4
= 150, P erda = 5%;
- Segunda faixa: faixa homogênea (item 2);
- Terceira faixa: x
43
= 2, F
4
= 300, P erda = 5%;
- Quarta faixa: faixa homogênea (item 4);
5.1.2 Etapa de Geração dos Padrões
A partir do conjunto de faixas obtidas pelos procedimentos descritos acima, são
gerados os padrões de cort e através dos mesmos tr ês procedimentos, sendo que agora
nos PMI’s serão considerados como itens as fa ixas geradas anteriormente. As faixas
serão, entã o, combinadas ao longo da altura H do objeto. Tomando o exemplo dado
na formação das faixas, os padrões gerados pela primeira abor dagem são a queles
mostrados na Fig. 5.8.
11 2
2
4
3
3
4
4
3
3
4
4
33
4
4
3
3
4
4
3
3
4
11 2
2
11 22
Figura 5.8: Padrões formados pela abordagem 1.
5.2 Algoritmo Evolutivo Multiobjetivo aplicado ao PCEB 70
5.2 Algoritmo Evolutivo Multiobjetivo aplicado ao
Problema de Corte Bidimensional
Com os padrõ es obtidos na seção anterior, são construídas as soluções do pro-
blema, que formarão o espaço de busca. Ressalta-se que este algoritmo é baseado
no algoritmo NSGA-II, principalmente no que se refere às estratégias de:
• Classificação da população: a função de aptidão de cada solução é calculada
de acordo com a não dominância das soluções.
• Elitismo: é mantido um subconjunto de soluções dominantes encontra da s até
o momento.
• Preservação de diversidade na população: as soluções de uma mesma fronteira
têm sua função de aptidão expressa também em termos de sua cro wding-
distance.
A seguir são descritas as etapas do AEMO.
5.2.1 Representação da solução
A solução do PCEB deve mostrar quais padrões são utilizados, a ssim como a
freqüência de cada padrão . Uma representação bastante utilizada é feita através de
um vetor, com dimensão correspondente ao número de padrões, no qual a posição
indica o padrão utilizado e o elemento indica sua freqüência.
Neste trabalho, entretanto, observou-se que, nesse tipo de representação, poucos
tipos distintos de padrões eram utilizados, quando comparados ao número to t al de
padrões (n
padroes
). Assim, conclui-se, experimentalmente, que um vetor de tamanho
n
padroes
exigia um esforço computacional adicional desnecessário. Por isso, opto u-se
por r epresentar a solução por meio de uma matriz, de dimensão 2 × n
p
, sendo n
p
o número de padrões utilizados na solução. A primeira linha desta matriz indica os
índices dos padrões utilizados, e a segunda linha sua respectiva freqüência, conforme
o exemplo de solução mostrado a seguir:
s =
10 5 3 8 2
8 2 8 6 9
(5.13)
Neste caso, o padrão 10 está sendo utilizado 8 vezes; o padrão 5 está sendo
utilizado 2 vezes e assim por diante.
5.2.2 Geração da População Inicial
Cada indivíduo da população inicial é construído confo rme o procedimento des-
crito a seguir.
5.2 Geração da População Inicial 71
Construção das soluções
A construção da solução se inicia com a definição do número de padrões distintos,
ou seja, o número de colunas da matriz solução. Os padrões são escolhidos aleato-
riamente, dentro do intervalo [1, n
padroes
]. Em seguida, essa primeira linha do vetor
solução é preenchida com n
p
padrões, escolhidos aleatoriamente.
Com os tipos de padrões distintos definidos, a próxima etapa do procedimento
é a verificação da viabilidade da solução, ou seja, a confirmação de que a solução
é capaz de gerar todos os tipos de itens demandados. Para tanto, são somadas as
freqüências de cada tipo de itens nos padrões escolhidos. Se essa soma for igual a
zero, a solução é inviável, e o processo de escolha aleatório de padrões é reiniciado,
até que se encontre um padrão viável.
Uma das formas de se obter a segunda linha, seria gerar a freqüência de cada
padrão aleatoriamente. Entretanto, as soluções geradas dessa maneira apresentam,
no caso médio, um excesso ou uma falta de itens, com relação à demanda, muito
elevado.
Então, para obter, a s soluções iniciais, adotou-se um procedimento parcialmente
guloso, no qual, a cada iteração escolhe-se, aleatoriamente, um padrão. Em seguida,
calcula-se um limite superior para a freqüência do padrão, de modo que os itens
gerados pela solução não ultrapassem a demanda, de acordo com a equação (5.14):
F
j
= min
⌊
d
i
f
ij
⌋|f
ij
> 0
(5.14)
em que F
j
representa a freqüência do padrão j, d
i
a demanda do item i e f
ij
a
freqüência do item i no padrão j.
Com esse procedimento esp era-se que a solucão a presente um número baixo de
falta de itens. Posteriormente, pa ra corrigir essa falta de itens que ainda ocorre,
utiliza-se a metaheuristica ILS.
Para exemplificar o procedimento, será considerada a seguinte solução:
s =
10 5 3 8 2
A Tabela 5.1 mostra os itens que compõem o s padrões dessa solução, bem como
a demanda de cada item:
Tabela 5.1: Exemplo de solução.
Padrão Itens
1 2 3 4 5
2 0 1 0 2 3
3 2 4 3 0 0
5 1 0 2 0 1
8 0 3 0 0 4
10 2 3 0 1 2
Demanda 10 20 18 16 27
Inicialmente, escolhe-se aleatoriamente um padrão, e, em seguida, calcula-se o
limite superior. Supondo que o padrão 2 foi escolhido, tem-se:
5.2 Geração da População Inicial 72
F
2
= min{20/1, 1 6 /2, 27 /3} = 8 vezes;
Este resultado representa, portanto, a freqüência do padrão 2 na solução. Como
o padrão 2 é utilizado, por 8 vezes, deve-se atualizar a demanda. A Tabela abaixo
mostra, na primeira linha, os tipos de itens e, na segunda linha, a demanda atu-
alizada (em negrito). Por exemplo, tomando-se o item 5, que aparece 3 vezes no
padrão 2. Como o padrão 2 é utilizado por 8 vezes, são produzidos 24 itens do tipo
5. Deve- se, po r t anto, diminuir a demanda de 27 para 3 itens do tipo 5.
Item 1 2 3 4 5
Demanda 10 12 18 0 3
A partir de então, o processo se repete, para cada um dos padrões da solução,
conforme mostrado a seguir (supondo que a seqüência de padrões escolhidos aleato-
riamente foi 2, 5 , 10, 3 e 8).
F
5
= min{10/1, 1 8 /2, 3/ 1} = 3 vezes;
Item 1 2 3 4 5
Demanda 7 12 12 0 0
F
10
= min{7/2, 12/3, 0/ 1, 0/2 } = 0 vezes;
Item 1 2 3 4 5
Demanda 7 12 12 0 0
F
3
= min{7/2, 12/4, 12 /3} = 3 vezes;
Item 1 2 3 4 5
Demanda 1 0 3 0 0
F
8
= min{0/3, 0/4} = 0 vezes.
Item 1 2 3 4 5
Demanda 1 0 3 0 0
Finalmente, obtém-se uma solução representada pela seguinte matriz:
s =
10 5 3 8 2
0 3 3 3 8
Como pode ser visto pelo exemplo anterior, após o procedimento ainda são ge-
radas soluções que apresentam falta de itens. Conforme dito anteriormente, após o
procedimento acima, utiliza-se a metaheurística ILS com o objetivo de minimizar a
perda, o excesso e a falta de itens.
5.2 Avalia ção das soluções e Função de Aptidão 73
Aplicação da metaheurística ILS ao PCEB
As etapas do algoritmo ILS estão po stas na Fig. 3.4 da seção 3.4.1.1. A aplicação
desta metaheurística para o Problema em tela exige decisões de implementação,
descritas a seguir:
• Busca Local: Método Randômico de Descida, utilizando como estrutura de
vizinhança os seguintes movimentos:
– Moviment o 1: neste movimento, a freqüência de um padrão da matriz
solução, escolhido aleatoriamente, é aumentada em 1 a 6 unidades (valores
obtidos experimentalmente).
– Moviment o 2: neste movimento, são subtraídas da freqüência de um pa-
drão escolhido aleatoriamente de 1 a 6 unidades.
– Moviment o 3: inicialmente, são escolhidos dois padrões da matriz solução.
Em seguida, à freqüência do primeiro padrão é somada 1 unidade, e à
freqüência do segundo padrão subtraída 1 unidade.
• Perturbação: em cada nível, são escolhidos aleatoriamente e a plicados à solu-
ção os movimentos descritos a cima, por (nível + 1 ) vezes;
• Critério de aceitação: valor da função objetivo perda.
5.2.3 Avaliação das soluçõe s e Função de Aptidão
A função que avalia a solução quanto à perda, além de calcular a perda interna
(área) em cada objeto, também considera o excesso na produção de itens, assim como
a falta, em relação à demanda. As soluções que apresentem um g rande excesso de
itens, ou falta deles, são penalizadas ao receber um alto valor de função de avaliação,
sendo assim excluídas do processo evolutivo. A falta de itens é mais fortemente
penalizada, em vista da necessidade do atendimento da demanda. O excesso na
produção é comum em situações reais, e nem sempre é considerado perda, devido à
possibilidade de seu uso posterior. Por esse motivo, o excesso é menos penalizado.
A função de avaliação da perda de uma solução s é apresentada a seguir. Sejam:
- x
j
: número de vezes que o padrão de corte j é utilizado;
- n
p
: número de padrões de corte da solução;
- n: número de tipos de itens;
- a
ij
: número de itens do tipo i no padrão de corte j;
- d
i
: número demandado de itens do tipo i;
- g
i
: número de itens i gerados na solução;
- α: penalidade atribuída à falta de itens ;
- β: penalidade atribuída ao excesso de itens.
5.2 Avalia ção das soluções e Função de Aptidão 74
A função de avaliação da perda é, então, dada por:
f
1
(s) =
n
p
j=1
c
j
x
j
n
p
j=1
x
j
+ αc
falta
+ βc
excesso
(5.15)
em que:
c
j
= LH −
n
i=1
l
i
h
i
a
ij
(5.16)
c
falta
=
n
i=1
|min{0, g
i
− d
i
}|
n
i=1
d
i
(5.17)
c
excesso
=
n
i=1
max{0, g
i
− d
i
}
n
i=1
d
i
(5.18)
A equação (5.16) calcula a perda interna, ou seja, a diferença entr e a área do
objeto e a soma da área dos itens utilizados. Na equação (5.17), a falta de itens é
calculada pela diferença entre a quantidade de itens i gerados (dada por g
i
) e sua
demanda (d
i
). A equação (5.18), de forma semelhante, calcula o excesso de cada
tipo de item.
A função que avalia o número de padrões das soluções, é dada po r :
f
2
(s) =
n
p
j=1
δ(x
j
) (5.19)
em que:
δ(x
j
) =
1, se x
j
> 0;
0, se x
j
= 0.
A função de aptidão de uma solução depende da f r onteira à qual ela pertence e
da sua crowding-dis tance, as quais são calculadas utilizando-se os valores das funções
de avaliação de cada solução. As soluções na fronteira F
j
sempre possuirão maior
probabilidade de reprodução que qualquer solução em F
j+1
. É importante notar que,
para problemas de maximização e minimização, a função de aptidão é maximizada,
isto é, altos valores de aptidão correspondem a altas probabilidades de reprodução.
Seleção
A estratégia usada para selecionar as soluções pa r a a reprodução é o método da
roleta, descrito na seção 3.4.2.1.
5.2 Avalia ção das soluções e Função de Aptidão 75
5.2.4 Operadores Genéticos
Esta seção concentra-se em descrever os operadores genéticos implementados
para a solução do PCEB, além de demais caracterísitcas da implementação compu-
tacional realizada.
Operadores de Recombinação
Nesse o perador, são selecionadas duas soluções da população de pa is. A partir destas
duas soluções pais, são geradas duas soluções filhos, que herdam características de
ambos pais. Para o PCEB foi utilizado um operador conhecido como crossover
uniforme.
No crossover uniforme, são escolhidos, aleatoria mente, dois indivíduos da popu-
lação e, em seguida, é determinada a porcentagem de genes que vão ser trocados. O
cruzamento acont ece então da forma descrita a seguir.
Dados dos pais p
1
e p
2
, para gerar o descendente f
1
, é criado aleatoriamente um
vetor de bits do mesmo comprimento de p
1
. Em seguida, f
1
é preenchido, copiando-
se os elementos da coluna de p
1
nas posições em que o vetor é igual a 1. Nas posições
do vetor onde aparece zero, são copiados os elementos da coluna de p
2
. A Fig. 5.9
mostra um exemplo deste operador em duas soluções do PCEB.
[ ]
[ ]
ú
ú
û
ù
ê
ê
ë
é
¯¯¯
ú
ú
û
ù
ê
ê
ë
é
6284513
5317264
18251 0
96828
28351 0
01011
2
1
1
p a i
f i l h o
p a i
Figura 5.9: Cros sover uniforme.
Após a recombinação, obtém-se uma po pulação de tamanho 2N. Dessa popu-
lação, são mantidos apenas os N melhores indivíduos. Dentre eles, estão aqueles
que sofrerão mutação. Além disso, arbitrou-se que três melhores indivíduos dessa
população são mantidos a salvo de sofrerem mutação.
No operador de recombinação, como os padrões usados são modificados, é ne-
cessário corrigir a sua freqüência, já que o novo indivíduo pode apresentar grande
excesso ou falta de itens, ou ainda ser indivíduo inviável. Para isso, é utilizada a
metaheurística ILS, com o objetivo de minimizar a perda (que inclui a perda intrín-
seca dos padrões, o excesso e a falta de itens). Assim, o indivíduo, caso inviável,
tem a possibilidade de se tornar viável.
5.3 Avalia ção das soluções e Função de Aptidão 76
Operadores de Mutação
Os seguintes operadores de mutação são aplicados, a uma dada probabilidade:
- Operador de mutação 1: consiste em inserir no indivíduo um novo padrão,
escolhido aleatoriamente.
- Operador de mutação 2: consiste em eliminar um padrão do indivíduo, esco-
lhido aleatoriamente (a matriz de dimensão 2×n
p
, que representa o indivíduo,
passa a ter dimensão 2 × (n
p
− 1).
Critério de Parada
O critério de pa rada escolhido para esta implementação é o número máximo de
gerações.
Determinação de Parâmetros
Um conjunt o de parâmetros foi testado para o NSG A-II aplicado ao PCEB. Na
Tabela 5.2, é mostrada a combinação de parâmetros com a qual se obteve melhores
resultados.
Tabela 5.2: Parâmetros do algoritmo.
Parâmetros Valores
Número de indivíduos 50
Número de gerações 30
Probabilidade de crossover (p
c
) 0,85
Probabilidade de mutação (p
m
) 0,05
Penalidade falta (α) 100
Penalidade excesso (β) 10
ILS
max
20
5.3 Experimentos Computacionais
O algoritmo baseado no NSGA-II foi implement ado na linguagem C e compilado
em C++ Builder 5.0. Os testes computacionais fora m feitos em um computador
AMD Atlon XP 64 Bits 4000+ (aproximadament e 2.11 GHz), com 1 GB de memória
RAM, sob plataforma Windows XP.
Os modelos matemáticos apresentados na seção 5.1 foram resolvidos pelo software
de otimização CPLEX, versão 10 da ILOG. A solução gerada pelo CPLEX para
estes modelos fornece os padrões de corte necessários para se iniciar a utilização do
algoritmo evolutivo proposto.
Foi encontrada certa dificuldade para analisar o desempenho do alg oritmo pro-
posto, devido à falta de métodos exatos e de exemplos resolvidos otimamente na
literatura para comparação. Em vista dessas limitações, foram utilizados os seguin-
tes problemas-teste:
5.3 Avalia ção das soluções e Função de Aptidão 77
• Dois problemas apresentados em Figueiredo (2006), em que é apresentado
um estudo de caso em uma indústria de móveis. Em seu trabalho, o autor
analisou os padrões de corte adotados p or uma indústria de móveis, e, a partir
das cara cterísticas levantadas, propôs uma heurística para a geração de um
conjunto de pool de padrões tabuleiros compostos (uma composição de padrões
do tipo tabuleiro, nos quais os itens podem ser obtidos com um corte no
primeiro estágio, que origina faixas que serão cortadas simultaneamente no
segundo estágio). Com estes padrões, são solucionados problemas que utilizam
os dados da fábrica. Ressalta-se que o objetivo tratado no trabalho é apenas a
minimização da perda de material, ou seja, a parte não utilizada do conjunto
de objetos da solução, sendo que os itens gerados em excesso (sobra) não são
considerados perda. Ap esar dos resultados para a perda, considerada como
o único objetivo, não ser necessariamente um resultado de referência para
o problema combinado (com os objetivos de minimizar a perda e o número
de padrões), esses problemas foram escolhidos devido a características como,
por exemplo, o fato do corte ser feito em dois estágios e dos padrões serem
guilhotinados. Vale ainda destacar que foram testados apenas os problemas
de Figueiredo (2006) com maior número de itens.
• Problemas gerados aleatoria mente, com o intuito de testar a capacidade do
algoritmo de solucionar problemas com maior número de itens e com uma
var iação na dimensão dos itens.
5.3.1 Proble mas-teste de um indústria de móveis
Os problemas teste descritos em Figueiredo (2006) consideram a produção de
lotes do s produtos assim distribuídos:
• 1 lote de criados (300 unidades);
• 1 lote de armários de 5 portas (40 unidades);
• 1 lote de cômoda s (160 unidades).
Nesta dissertação, f oram solucionados apenas os problemas da produção de um
lote de armários de 5 portas (formado por 7 itens com esp essura de 15 mm) e de um
lote de cômodas (6 itens com espessura de 12 mm), por estes problemas apresentarem
um maior número de itens.
Os dados para estes problemas podem ser vistos nas Tabelas 5.3 e 5.4. São
apresentados o comprimento l
i
e a altura h
i
de cada item i, tendo como unidade
de medida milímetros (mm); a quantidade de cada item requerida por unidade
do produto Qtde; além da demanda d
i
de cada item. Os objetos utilizados têm
dimensões L × H de 2750 × 1830, para a produção das cômodas, e dimensões de
2750 × 18 50 para a produção dos armários.
Os resultados da aplicação do algoritmo evolutivo proposto são mostrados nas
Fig.s 5.10 e 5.11. São apresentadas as fronteiras obtidas na primeira e na última
geração de uma rodada típica do algoritmo. Como pode ser observado, os resultados
obtidos para os dois problemas demonstram que o AEMO é capaz de otimizar o s
5.3 Avalia ção das soluções e Função de Aptidão 78
Tabela 5.3: Problemas-teste de Figueiredo (2006)- Armário de 5 portas (15 mm).
Item l
i
h
i
Qtde d
i
1 1050 535 2 80
2 535 500 2 80
3 1049 452 5 200
4 499 452 5 200
5 535 430 2 80
6 452 429 2 80
7 700 212 4 160
Tabela 5.4: Problemas-teste de Figueiredo (2006) - Cômoda (12 mm).
Item l
i
h
i
Qtde d
i
1 635 180 3 480
2 454 180 6 960
3 635 135 2 320
4 454 135 4 640
5 440 65 2 320
6 635 50 1 160
4
4,5
5
5,5
6
6,5
7
7,5
8
2 4 6 8 10 12
Número de Padrões
Perda (%)
30ª Geração 1ª Geração
Figura 5.10: Fronteiras no problema dos armário s de 5 portas.
dois objetivos simultaneamente, gerando um conjunto de soluções que mostram a
ação de um o bjetivo em relação ao outro.
Claramente se observa que um menor número de padrões implica na ocorrência
de uma maior perda de material, em ambos os casos. As soluções obtidas para a
perda de material (não inclui as sobras, i.e. excedente de produção) e para o número
de padrões são apresentados nas Tabelas 5.5 e 5.6. Ressalta-se que Figueiredo (2006)
5.3 Avalia ção das soluções e Função de Aptidão 79
0
0,5
1
1,5
2
2,5
3
3,5
4
5 6 7 8 9 10
Número de Padrões
Perda (%)
30ª Geração 1ª Geração
Figura 5.11: Fronteiras no problema das cômodas.
trata apenas do objetivo de minimizar a perda.
Pela Tabela 5.5, observa-se que o AEMO, em termos de p erda, apresenta resulta-
dos bastante próximos daqueles encontrados por F igueiredo (2006), com a vantagem
de apresenta r outras soluções que mostram ao decisor o compromisso entre a perda
e número de padrões. Considerando isoladamente o número de padrões, pode-se
verificar que todas as soluções fornecidas pelo AEMO apresentar am um menor nú-
mero de padrões. Com relação ao tempo de execução, o AEMO se mostrou bastante
razoável, mesmo não sendo apropriado comparar os tempos de execução de métodos
de otimização mono e multiobjetivo.
A Tabela 5.6 mostra, da mesma for ma, que foram obtidas perdas muito próximas
daquelas de Figueiredo (2006). Considerando o número de padrões, observa-se que
o AEMO forneceu duas soluções com um número menor de padrões, e uma solução
com o mesmo número de padrões. Essa solução, e a solução de Fig ueiredo (2006),
mostram, praticamente, a mesma perda. Isso demonstra a capacidade do AEMO
em encontrar soluções de qualidade para ambos os objetivos. O tempo de execução
AEMO se mostrou, nova mente, bastante razoável.
Tabela 5.5: Resultados - Armário de 5 porta s ( 15 mm).
Armário de 5 p ortas Figueiredo (2006) AEMO
Número de Padrões 9 3 4 6 7
Perda ( %) 4 5,7 5,4 4,9 4,7
Tempo (seg) 66,2 150,8
5.3 Avalia ção das soluções e Função de Aptidão 80
Tabela 5.6: Resultados - Cômoda (12 mm).
Cômoda Figueiredo (2006) AEMO
Número de Padrões 8 6 7 8
Perda ( %) 0,7 1,22 0,81 0,73
Tempo (seg) 36,2 123,6
Ressalta-se que não foram obtidas as soluções correspondentes aos mínimos indi-
viduais das duas f unções objetivo, fato que impediu que as fro nteiras apresentassem
soluções com uma perda menor do que aquela encontrada por Figueiredo (2006).
5.3.2 Experimentos com exemplos aleatórios
Na realização dos experimentos com exemplos a leatórios, observou-se que, além
da quantidade de itens, a diversidade na dimensão dos itens afetava consideravel-
mente a qualidade das soluções (Figueiredo, 2006). Por isso, optou-se por agrupar os
exemplos em classes, que diferem entre si pelo número de itens n e pela diversidade
na dimensão do s itens.
Nos experimentos analisados, considerou-se L = 100 e H = 100, com a de-
manda dos itens gerada aleatoriamente no intervalo [200, 800]. O comprimento dos
itens l
i
foi gerado aleatoriamente nos intervalos [0, 10 L; 0, 50L] (tamanhos diver-
sos) e [0, 05L; 0, 30L] (tamanhos pequenos). Da mesma forma, a altura dos itens
h
i
foi gerada aleatoriamente nos intervalos [0, 10H; 0, 50H] (tamanhos diversos) e
[0, 05 H; 0, 30H] (tamanhos pequenos). Estes experimentos foram divididos em seis
classes, mostradas na Tabela 5.7.
Tabela 5.7: Problemas gerados aleatoriamente
.
Classes n l
i
h
i
1 10 0, 05L; 0, 30L 0, 05H; 0, 30H
2 10 0, 10L; 0, 50L 0, 10H; 0, 50H
3 20 0, 05L; 0, 30L 0, 05H; 0, 30H
4 20 0, 10L; 0, 50L 0, 10H; 0, 50H
5 30 0, 05L; 0, 30L 0, 05H; 0, 30H
6 30 0, 10L; 0, 50L 0, 10H; 0, 50H
Em cada classe, foram gerados 10 exemplos aleatórios. A Tabela 5.8 mostra os
resultados médios obtidos. A primeira coluna da Tabela indica a classe do problema,
a segunda mostra a perda média (%), a terceira o número médio de padrõ es e a
quarta o tempo de execução do algoritmo. A perda representa a soma da perda
intrínseca de cada padrão (não inclui os itens produzidos em excesso).
5.4 Avalia ção das soluções e Função de Aptidão 81
Tabela 5.8: Resultados Médios para os 10 exemplos de cada classe.
Classe Perda (%) N úmero de padrões Tempo
1 2,70 11,03 277,50
2 3,35 10 281,10
3 3,90 18,8 1472,71
4 6,65 15,92 2533,26
5 4,12 35,14 3258,98
6 6,88 28,83 5810,71
Conforme se p ode observar pela Tabela 5.8, os resultados do AEMO for am sa-
tisfatórios, em termos de perda, para todas as classes de problemas, mostrando um
melhor desempenho para as classes com menor número de itens e com dimensões
menos heterogêneas.
Nas Fig .s 5.12 a 5.17 são apresentados as fronteiras, ou curvas de trade-off,
obtidas pelo AEMO aplicado a um exemplo (escolhido arbitra riamente) de cada
uma das seis classes de problemas. São mostradas, respectivamente, a fronteira
obtida na primeira geração e a fronteira obtida na última geração (30
a
geração).
Pode-se observar, na maioria das classes, que existem poucas soluções viáveis na
população inicial, devido à penalização das soluções pelo grande excesso ou falta.
Entretanto, pode-se verificar que este fato não compromete a resolução do pro-
blema, já que tais soluções viáveis são encontradas natura lmente durante o processo
evolutivo, possibilitando assim a convergência das populações para regiões mais pro-
missoras.
Como pode ser observado, os resultados obtidos para esse conjunto de proble-
mas confirma a eficiência do algoritmo desenvolvido em encontrar fronteiras que
melhoram ao longo das gerações. Comparando- se as classes com o mesmo número
de itens, observou-se que as classes com maior dispersão nas dimensões dos itens
(classes 2, 3 e 6) apresentara m uma elevação no índice de perda, além de tempo de
processamento maior.
5.4 Conclusões
Este trabalho apresentou um Algoritmo Evolutivo Multiobjetivo para a resolução
do Problema de Corte de Estoque Bidimensional, considerando a minimização de
dois objetivos: perda de material e número de padrões distintos. Nos testes com-
putacionais realizados, o algoritmo mostrou-se capaz de produzir um conjunto de
soluções que mostram o compromisso entre os dois objetivos, a part ir do qual o de-
cisor pode selecionar uma solução de acordo com a sua aplicação particular. Além
disso, verificou-se que a fronteira de soluções melhora ao longo do tempo.
O AEMO proposto foi aplicado a dois problemas-teste de Figueiredo ( 2006), que
trata do problema de corte em uma fábrica de móveis. Mostrou-se nos experimentos
que o AEMO alcançou resultados bastante próximos daqueles obtidos por Figueiredo
(2006), em termos do número de padrões. Com relação à perda de material, t ambém
foram encontrados resultados bastante próximos aos resultados médios de Figueiredo
(2006).
5.4 Avalia ção das soluções e Função de Aptidão 82
1
2
3
4
5
5 7 9 11 13 15 17 19 21
Número de Padrões
Perda (%)
30ª Geração 1ª Geração
Figura 5 .1 2: Curva de trade-off ent re a perda e o número de padrões distintos no
exemplo da classe 1.
0
2
4
6
8
10
12
14
7 9 11 13 15 17
Número de Padrões
Perda (%)
30ª Geração 1ª Geração
Figura 5 .1 3: Curva de trade-off ent re a perda e o número de padrões distintos no
exemplo da classe 2.
Além disso, foram gerados seis conjuntos de testes aleatórios, com o intuito de
testar o algoritmo com um maior número de itens, além de verificar a influência da
dispersão na dimensão dos itens na qualidade da solução. Os conjuntos com itens
de dimensões mais homogêneas, como era de se esperar, apresentaram melhores
resultados em termos de perda (e, conseqüentemente, piores resultados quanto ao
número de padrões).
Estes resultados iniciais mostram o potencial da técnica proposta e a possibili-
dade da utilização desta em situações práticas. Deve-se observar, ainda, que não
5.4 Avalia ção das soluções e Função de Aptidão 83
0
1
2
3
4
5
6
7
8
9
10 15 20 25 30 35 40
Número de Padrões
Perda (%)
30ª Geração 1ª Geração
Figura 5 .1 4: Curva de trade-off ent re a perda e o número de padrões distintos no
exemplo da classe 3.
3
5
7
9
11
13
15
17
8 10 12 14 16 18 20 22 24 26 28 30 32
Número de Padrões
Perda (%)
30ª Geração 1ª Geração
Figura 5 .1 5: Curva de trade-off ent re a perda e o número de padrões distintos no
exemplo da classe 4.
foram encontrados, na literatura analisada, outros trabalhos que relatassem tentati-
vas de obtenção de soluções que apresentassem um compromisso entre os o bjetivos
aqui tratados para o problema de corte de estoque bidimensional.
5.4 Avalia ção das soluções e Função de Aptidão 84
3
4
5
6
7
8
24 29 34 39 44 49
Número de Padrões
Perda (%)
30ª Geração 1ª Geração
Figura 5 .1 6: Curva de trade-off ent re a perda e o número de padrões distintos no
exemplo da classe 5.
4
5
6
7
8
9
10
11
12
20 24 28 32 36 40 44 48 52
Número de Padrões
Perda (%)
30ª Geração 1ª Geração
Figura 5 .1 7: Curva de trade-off ent re a perda e o número de padrões distintos no
exemplo da classe 6.
Capítulo 6
Conclusões Gerais e Trabalhos
Futuros
6.1 Conclusões Gerais
O presente trabalho abordou dois problemas de corte bidimensional bastante
usuais em situações práticas: o problema de corte com dimensão aberta guilhoti-
nado (PCDA) e o problema de corte de estoque guilhotinado ( PCEB). No primeiro
problema, considerou-se apenas um critério de otimização, que foi a minimização da
perda de material. No segundo problema, foram considerados dois critérios de otimi-
zação: a minimização da perda de material e a minimização do número de padrões
distintos (troca de padrões), tratando-se, portanto, de um problema multiobjetivo.
Para a resolução do PCDA, foram estudadas, implementadas e testadas as se-
guintes abordagens, já existentes, para a etapa de encaixe dos itens: First-Fit e
Best-Fit. Os testes com os dois métodos mostram que, para problemas com poucos
itens (até 49 itens), tanto a técnica First-Fit quanto a t écnica Best-Fit atingem
a solução ótima, sendo que a primeira apresentou um t empo de execução menor.
Entretanto, a observação mais importante foi a de que, quanto se eleva o número de
itens (de 73 a 197 itens), o algoritmo Best-Fit obtém resultados bastante superiores
ao First-Fit. Para solucionar o problema de corte com dimensão aberta guilhotinado
em estudo, desenvolveu-se uma proposta baseada nos algoritmos evolutivos híbridos.
Mais especificamente, fo r am implementadas as seguintes combinações de algoritmos:
Algoritmo Genético com a população inicial gerada pela metaheurística Iterated
Local Search e algor itmo genético com a população gerada pela metaheurística Multi-
Start.
No início do desenvolvimento deste trabalho, f oi implementado um algo r itmo
evolutivo, baseado em um AG simples, que contava apenas com a incorpor ação de
operadores de busca local, sendo que tal estudo, assim como seus resultados, fo r am
publicados em Andrade et al. (2008f). Em seguida, foi testada o efeito do uso
de metaheurísticas para a geração da po pulação inicial do AG com operado res de
busca local. A primeira metaheurística a ser testada foi a Multi-Start, sendo que este
estudo é apresentado Andrade et al. (2008d) e Andrade et al. (2008c). Testou-se,
ainda, a utilização da metaheurística Iterated Local Sea rc h (ILS), para a geração
da população inicial do algoritmo evolutivo. Este último estudo é mostrado em
Andrade et al. (2008e).
85
6.2 Trabalhos Futuros 86
Verificou-se, no desenvolvimentos dos trabalhos citados acima, que os algoritmos
propostos apresentar am um bom desempenho, tendo em vista a dificuldade de reso-
lução problema. Em termos de valor da função de avaliação, os melhores resultados
foram obtidos com a utilização do algoritmo evolutivo cuja população inicial foi ge-
rada pelo ILS (AE
ILS
). Com relação ao tempo computacional, observou-se que os
tempos encontrados pelos métodos propostos fo r am, em média, inferiores àqueles
requeridos pelo método exato.
Os estudos iniciais acerca do problema de corte são apresentados em Andrade
et al. (2 007). Neste trabalho, o PCEB foi solucionado por um AG simples. Ao longo
deste trabalho, surgiu o interesse pelo estudo do PCEB através de uma abordagem
multiobjetivo , que considerasse, além do objetivo de minimizar a perda, a minimiza-
ção do número de padrões distintos (setup). Desenvolveu-se, então, uma formulação
matemática multiobjetivo para o problema, baseada na formulação para problemas
unidimensionais, que t r atam dos mesmos objetivos, apresentada em (Golfeto et al.,
2007).
Para a geração dos padrões de corte, foi utilizado um método d e duas fases,
baseado nos trabalhos de Morabito e Garcia ( 1998) e Hifi e Hallah (2006). O PCEB
multiobjetivo foi solucionado por um algoritmo evolutivo multiobjetivo (AEMO) ba-
seado no método NSGA-II ( Deb et al., 2002). Os resultados obtidos para problemas-
teste reais de uma indústria de móveis, retirados do tra balho de Figueiredo (2006)
(mostrados em Andrade et al. (2009)), e para problemas gerados aleatoriamente,
mostraram que o AEMO é capaz de encontrar soluções que apresentam um com-
promisso entre os dois objetivos. Não foram encontra do s trabalhos que tratassem
do PCEB envolvendo os objetivos aqui tratados. Em razão disso, não houve como
comparar os resultados obtidos. Observou-se, entretanto, que os índices de perda
obtidos foram baixos, em todo s os problemas. Além disso, mostra-se que o AEMO
é capaz de produzir fronteiras não dominadas cada vez melhores, no decorrer das
gerações.
Considera-se que a principal contribuição deste trabalho está no fato deste ser
uma das primeiras abordagens do problema de corte de estoque bidimensional mul-
tiobjetivo que envo lve a redução do número de padrões distintos.
As evidências empíricas obtidas neste trabalho indicam que os algoritmos pro-
postos são adequados para solucionar problemas associados a situações reais.
6.2 Trabalhos Futuros
Com respeito ao a lgoritmo evolutivo desenvolvido para o PCDA, poderiam ser
testados os desempenhos de outras heurísticas para geração da população inicial.
Por se t r atar de uma abo r da gem inicial, há muito a ser feito em termos de estudos
e testes para o PCEB multiobjetivo. Algumas sugestões são:
• Ap erfeiçoar o método de geração de padrões;
• Testar outros métodos evolutivos multiobjetivos;
• Estudar a possibilidade da utilização de busca local multiobjetivo;
• Desenvolver mecanismos para aumentar diversidade das fronteiras;
6.2 Trabalhos Futuros 87
• Verificar a qualidade das fronteiras não-dominadas obtidas pelos algoritmos.
Por se tratar de uma abordagem inicial do problema de corte bidimensional mul-
tiobjetivo, muitas melhorias podem ser realizadas no método, como a implementação
de novas estratégias para aumentar o número de soluções não-dominadas.
Referências Bibliográficas
Andrade, M. S. F.; Souza, S. R.; Souza, M. J. e Temponi, E. C. C. (2008)a. Um
algoritmo evolutivo híbrido aplicado à solução do problema de corte bidimensional
guilhotinado. Anais do XL Simpósio Bras i l eiro de Pesquisa Operacional - SBPO,
João Pessoa, PA.
Andrade, M. S. F.; Souza, S. R.; Souza, M. J. e Temponi, E. C. C. (2008)b. Um
algoritmo evolutivo híbrido aplicado à solução do problema de corte bidimensional
guilhotinado. Anais do XXVIII ENEGEP - Encontro Naciona l de Engenharia de
Produção, R io de Janeiro, RJ.
Andrade, M. S. F.; Souza, S. R. e Souza, M.J. (2 008)c. Um algoritmo evolutivo hí-
brido aplicado à solução do problema de corte bidimensional guilhotinado. Anais do
XXVIII ENEGEP - Encontro Nacional de Enge nharia de Produção, Rio de Janeiro.
Andrade, M. S. F.; Souza, S. R.; Souza, M.J. e Temponi, E. C. C. (2008)d. Algo-
ritmos evolutivos aplicados à resolução do problema de corte bidimensional. Anais
do XXXIX CILAMCE - Congresso Ibero Latino Americano de Métodos Com puta-
cionais em Engenharia, Maceió.
Andrade, M. S. F.; Souza, S. R. e Temponi, E. C. C. (2007). Problema de corte
bidimensional com padrões de corte: abordagem via metaheurísticas populacionais.
Anais do X EMC - Encontro de Modelagem Computacional, Nova Friburgo.
Andrade, M. S. F.; Souza, S. R. e Temponi, E. C. C. (20 08)e. Um algoritmo evolutivo
híbrido aplicado à solução do problema de corte bidimensional guilhotinado. Anais
do XL SBPO - Simpós i o Brasileiro de Pesquisa Operaciona l, João Pessoa.
Andrade, M. S. F.; Souza, S. R. e Temponi, E. C. C. (2008)f. Um alg oritmo memético
aplicado à solução do problema de corte bidimensional guilhotinado. Anais do XI
SPOLM - Simpósio de Pesquisa Operacional e Logística da Marinha, Rio de Janeiro,
RJ.
Andrade, M. S. F.; Souza, S. R. e Temponi, E. C. C. (2009). Um algoritmo evo -
lutivo híbrido a plicado à solução do problema multiobjetivo de corte bidimensional
guilhotinado. Anai s do XLI SBPO - Simpósio Brasi l eiro de Pesquisa Opera c ional,
Porto Seguro.
Arenales, M.; Morabito, R. e Yanasse, H. (1999). Special issue: Cutting and pa cking
problems. Pes quisa Ope racional, v. 19, n. 2, p. 107–299.
88
Referências Bibliográficas 89
Bäck, T.; Fogel, D.B e Michalewicz, Z . (200 0)a. Evolutionary computation 1: Basic
algorithms and operators. Institute of Physics Publishing, v. .
Bäck, T.; Fog el, D.B e Michalewicz, Z. (2000)b. Evolutionary computation 2: Basic
algorithms and operators. Institute of Physics Publishing, v. .
Beasley, J. E. (1985). Algorithms for unscontrained two-dimensional guilhotine
cutting. Journal of the Operational Research Society, v. 36, n. 4 , p. 297–306.
Beasley, J. E. (1990). Or-library: distributing test problems by electronic mail.
Journal of the Operational Research Society, v. 41, n. 11, p. 1069–1072 .
Bischoff, E. E. e Wäscher, G. (1995). Cutting and packing. Europea n Journal of
Operational Research, v. 84, p. 503–505.
Blum, C. e Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview
and conceptual comparison. ACM Computing Surveys, v. 35, n. 3, p. 268–308.
Christofides, N. e Whitlock, C. (1977). An algorithm for two dimensional cutting
problems. O perations Research, v. 25, n. 1, p. 30–44.
Coello, C. A. (1999). A Comprehensive Survey of Evolutionary-Based Multiobjective
Optimization Techniq ues. Laboratorio Nacional de Informatica Avanzada, Mexico.
Deb, K.; Agrawal, S.; Pratab, A. e Meyarivan, T. Apr.(2002). A fast and elitist
multi-o bjective genetic algorithm: Nsga-ii. IEEE - Transac tions on Evolutionary
Computation, volume 6, p. 182–197, Apr.(2002).
Dias, A. H. F. (1999). Algoritmos genéticos a plicados a problemas com múlti-
plos objetivos. Master’s thesis, UFMG, Belo Horizonte. Dissertação (Mestrado em
Engenharia Elétrica).
Diegel, A.; Chetty, M.; Schalkwyck, S. VAn e Naidoo, S. (1993). Setup combining
in trim loss problem 3 to 2 and 2 to 2. Working paper, v. Business Administration,
n. University of Natal, p. Durban.
Dowsland, K. A. e Dowsland, W. B. (199 2). Packing problems. European Journal
of Operational Research, v. 56, p. 02–14.
Dyckhoff, H. (1990). A topology of cutting and packing problems. European Journal
of Operational Research, v. 44, p. 145–159.
Dyckhoff, H.; Scheithauer, G. e Terno, J. (1997). Cutting and packing. In M.
Amico, F. Maffio l i , F., S . Martello (eds.). Annotated bibliographies in combinatorial
optimisation. John Wiley and Sons, New York, NY, p. 393–414.
Feo, T. A. e Resende, M. G. C. (1995). Greedy randomized adaptive search proce-
dures. Journal of Global Optimi zation, v. 6, p. 109– 133.
Figueiredo, A. G. Análise de produtividade de padrões de corte na indústria de
móveis. Dissertação de Mestrado, Universidade Estadual Paulista, Instituto de Bi-
ociências, Letras e Ciências Exatas, São Jo sé do Rio Preto, (2006).
Referências Bibliográficas 90
Foerster, H. e Wäscher, G. (2000) . Pattern reduction in one-dimensional cutting
stock problem. International Journal o f Production Research, v. 38, p. 1657–76.
Fogliatto, F . S. e Fagundes, P. R. M. (2003 ). Troca rápida de ferramentas: proposta
metodológica e estudo de caso. Revis ta Gestão & Produção, v. 10.
Fonseca, C. M. e Fleming, P. J. Aug.(19 93). Genetic algorithm for multiobjective
optimization: Formulation, discussion and generalization. In: 5th Conference on
Genetic Algorithm, p. 416 –423, San Mateo, California.
Gilmore, P. e Gomory, R. (1961). A linear pro gramming approach to the cutting
stock problem. Operational Research, v. 9, p. 849–8 59.
Gilmore, P. e Gomory, R. (1963). A linear pro gramming approach to the cutting
stock problem - part ii. O perational Research, v. 11, p. 863–888.
Gilmore, P. e Gomory, R. (1965). Multistage cutting stock problems of two and
more dimensions. Operational Research , v. 13, p. 94–1 20.
Goldberg, D. E. (1989). Genetic algorithms in search, o ptimization, and machine
learning. Addison-Wesley, v. .
Golfeto, R. R.; Moretti, A. C. e Neto, L. L. Sales. novembro(2007). Algoritmo
genético simbiót ico co-evolucionário aplicado ao problema de corte multi-objetivo.
X Encontro de Modelagem Computacional, Nova Friburgo, RJ. Anais do EMC 2007,
CD-ROM.
Gramani, M. C. N. Problema de corte bidimensional guilhotinado e r estrito em 2-
estágios. Dissertação de Mestrado, Instituto de Ciências Mat emáticas de São Carlos
- Universidade de São Paulo, São Carlos, (1 996).
Haessler, R. W. (1975). Controlling cutting patt ern changes in one-dimensional trim
problems. O perations Research, v. 23, n. 3, p. 483–493 .
Helmberg, C. (1995). Cutting aluminum coils with high length variables. Annals of
Operations Research, volume 57, p. 175–789, (1995).
Hifi, M. (1998). Exact algorithms for the guillotine strip cutting/packing problem.
Computers and Operations Re s earch, v. 25, p. 925 –940.
Hifi, M. ( 2002). Special issue on cutting and packing. Studia Informatica Universalis,
v. 2, p. 1–161.
Hifi, M. e Hallah, R. (2006). Strip generation algorithms for constrained two -
dimensional two -staged cutting pro blems. European Journal of Operational Res e-
arch, v. 1 72, n. 2 , p. 515–527.
Hochbaum, D. S. e Wolfgang, M. (1985). Approximation schemes fo r covering
and packing problems in image processing and vlsi. Journal of the Association for
Computing Machinery, v. 32, p. 130–136.
Holland, J. H. (1975 ). Adaptation in natural and artificial systems. MIT Press, v. .
Referências Bibliográficas 91
Hopper, E. e Turton, B.C. (2001)a. An empirical investigation of meta-heuristic
and heuristic algorithms for a 2d packing problem. European Journal of Operational
Research, v. 1, p. 3 4–57.
Hopper, E. e Turton, B.C. (2001)b. A review of the application of meta-heuristic
algorithm to 2d strip packing problems. Artificial Intelligence Rev i ew, v. 16 , p.
257–300.
Horn, J. e Nafpliotis, N. (19 93). Multiobjective optimization using the niched pareto
genetic algorithm. Relató rio técnico, Illinois.
Jakobs, S. (1996). On genetic algorithms for the packing of polygons. European
Journal of Operational Research, v. 88, p. 165–181.
Kantorovich, L. V. (1960). Mathematical methods of organizing and planning pro-
duction ( t r adução de um tra balho em russo datado de 1939). Management Sc i ence,
v. 6, p. 366–422.
Katsurayama, D. M. Estudo sobre o efeito da utilização de padrões tabuleiros
na produtividade do equipamento de cortes. Dissertação de Mestrado, Instituto
Nacional de Pesquisas Espaciais, São José dos Campos, (2002).
Knowles, J. e Corne, D. (1999). The pareto archived evolution strategy: A new
baseline algorithm for multiobjective optimization. Press, IEEE, editor, Proceedings
of the 1999 Congress on Evolutionary Computation, p. 98–105, Piscataway, NJ.
Kolen, A. W. e Spieksma, F. C. R. (2000). Solving a bi-criterion cutting stock
problem with open-ended demand: a case study. Journal of the Operational Research
Society, v. 51, p. 1238–1247.
Kroger, B. (1995). Guillotineable binpacking: A genetic approach. European Journal
of Operational Research, v. 84, p. 645–661.
Lesh, N.; Maks, J.; McMahon, A. e Mitzenmacher, M. (2004). Exhaustive approa-
ches to 2d rectangular perfect pa ckings. Information Processing Letters, v. 90, p.
7–14.
Leung, J.; Tam, T.; Wong, C.S.; Young, G. e Chin, F. (1 990). Packing squares into
square. Journal of Pa rallel and Distributed Com puting, v. 10, p. 271–2 75.
Limeira, M. S. Redução do número de pad rões em proble mas de corte de estoque.
Tese de Doutorado, Instituto Nacional de Pesquisas Espaciais - INPE, São José dos
Campos, Brasil, (2003).
Lin, S. e Kernighan, B. W. (1 973). An effective heuristic algor ithm for the travelling-
salesman problem. Opera tions Research, v. , n. 11, p. 498–516.
Liu, D. e Teng, H. (1999) . An improved bl-algorithm for genetic algorithm of the
orthogonal packing of rectangles. European Journal of Operational Research, v. 112,
p. 413–420.
Referências Bibliográficas 92
Lodi, A.; Martello, S. e Monaci, M. (200 2). Two-dimensional packing problems: a
survey. Euro pean Journal of Operational Research, v. 141, p. 241–252.
Lodi, A.; Martelo, S. e Vigo, D. (2004). Models and bounds for two-dimensional
level pa cking problems. Journal of C ombinatorial Optim i zation, v. 8, p. 363–379.
Lourenço, H. R.; Martin, O. e Stuetzle, T. (2002). Iterated local search. Handbook
of Metaheuristics, p. 321–353, Norwell, MA. Kluwer Academic Publishers.
Maculan, N. (1988). Problemas de otimização relacionados ao corte de bobinas de
papel. ANAIS - COLÓ QUIO BRASILEIRO DE MATEMÁTICA, volume 16, p.
159–182, Rio de Janeiro, RJ.
Martello, S.; Monaci, M. e Vigo, D. (2003). An exact approach to strip-packing
problem. INFORMS Journal on Computing, v. 15, p. 310– 319.
McDiarmid, C. (1999) . Pattern minimisation in cutting stock problems. Discrete
Applied Mathem atics, v. 98, p. 121– 130.
Michalewicz, Z. (1992). Genetic algorithms + data structures = evolution progra ms.
Springer-Verlag, v. .
Morabito, R. e Arenales, M. (1992). Um exame dos problemas de corte e empaco-
tamento. Pesquisa Ope racional, v. 12, n. 1, p. 1–20.
Morabito, R. e Arenales, M. (2000). Optimizing the cutting of stock plates in a
furniture company. I nternational Journal of Production Research, v. 38, n. 12, p.
2725–42.
Morabito, R. e Arenales, M. N. (1996). Staged and constrained two-dimensional
guilhotine cutting pro blems: an and/or-graph approach. European Journal of Ope-
rational Res earch, v. 94 , n. 3, p. 548–560.
Morabito, R. e Garcia, V. (1998). Uma abordagem para o problema de cortes de
chapas de fibra de madeira reconstituída. Pesquisa Operaci onal, v. 18, n. 1, p.
37–57.
Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and
martial arts: Towards memetic algorithms. Relatório técnico, California Institute
of Technology, Pasadena, California, USA.
Osman, I. H. e Laporte, G. (199 6). Metaheuristics: A bibliography. Operational
Research, v. 63, p. 513–623.
P., Le François e Gascon, A. (1995). Solving a one-dimensional cutting-stock problem
in a small manufacturing firm: a case study. IIE Transactions, v. 27, p. 483–496.
Pareto, V. ( 1896). Cours D’Economi e Politique. F. Rouge.
Pileggi, G. C. F.; Morabito, R. e Arenales, M. N. (2006). Abordagens para otimiza-
ção integrada dos problemas de geração e sequênciamento de p adrões de corte: caso
unidimensional. Pesquisa Operacional, v. 25, n. 3, p. 417–447.
Referências Bibliográficas 93
Pinto, M. J. O problema de corte de estoque inteiro. Dissertação de Mestrado, Ins-
tituto de Ciências Matemáticas e de Computação - ICMC-USP, São Carlos, (1999).
Régnier, J. Conception de Systèmes Hétérogènes en Génie Electrique par Optimi-
sation Evo l utionn aire Multicritère. PhD thesis, Institut National Polytechnique de
Toulouse, Toulouse, (2003 ). Tese (Docteur de l’INPT).
Richter, K. (1992). Solving sequential interval cutting problems via dynamic pro-
gramming. European Journal of Operations Research, v. 57, p. 332–338.
Rudolph, G. (1999). Evolutionary search under pa rt ially ordered sets. Relatório
técnico, Dortmund, Germany.
Schaffer, J. D. (1984 ). Some Experiments in Machine Learning using Vector Eva-
luated Genetic Algorithms. Thesis (Doctor of Philosophy) - Vanderbilt University,
Vanderbilt University,Nashville.
Srinivas, N. e Deb, K. (1993). Multiobjective optimization using nondominated
sorting in genetic algorithms. Relató r io técnico, Kanput, India.
Srinivas, N. e Deb, K. (1995). Multiobj ective function optimization using nondomi-
nated sorting genetic algorithms. Evol. Com put., volume 2, p. 221–248 , (1995).
Sweeney, P. e Parternoster, E. (1992). Cutting and packing problems: A categorized.
Application - Oriented Research Bibliograph y, v. , n. 43, p. 691–706.
Umetami, S.; Yagiura, M. e Ibaraki, T. (2003). One-dimensional cutting stock
problem to minimize the number of different patterns. O perations Research, v. 146,
p. 388–402.
Vanderbeck, F. (2000). Oexact algorithm for minimizing the number of setups in the
one dimensional cutting stock problem. European Journal of Operational Research,
v. 48, n. 6, p. 91 5–926.
Viennet, C. F. e Marc, I. (1996). Multicriteria optimization using a genetic alg orithm
for determining a pareto set. International Journal of Systems Sci ence, v. 27, n. 2,
p. 255–260.
Von-Zuben, F. J. (2000). Computação evolutiva: Uma abordagem pragmática.
Anais da I Jornada de Es tudos em Computação de Piracicaba e Regiã o, v. 1, p.
24–45.
Wang, P. Y. (1983). Two algorithms for constrained two-dimensional cutting stock
problems. O perations Research, v. 31, n. 3, p. 573–586 .
Wang, P. Y. e Waescher, G. (2002). Two algorithms for constrained two-dimensional
cutting stock problems. European Journal o f Operational Research, v. 141, p. 239–
469.
Wäscher, G.; Haußner, H. e Schumann, H. (2006). An improved typology of cutting
and packing problems. European Journal of Operational Research , v. 4, p. 44–45 4.
Referências Bibliográficas 94
Whitley, D.L. (1992). A genetic algorithm tutorial. Relatório Técnico CS93103,
Colorado Sta te University.
Yanasse, H. H. e Limeira, M. S. (2006). A hybrid heuristic to reduce the number of
different patterns in cutting stock problems. Computers and Operations Research,
v. 33, n. 9, p. 27 44–2756.
Yanasse, H. H.; Zinober, A. S. I. e Harris, R.G. (19 91). Two-dimensional cutting
stock with multiple stock sizes. Journal of the Operational Research Soci e ty, v. 42,
n. 8, p. 673–683.
Yeung, L.H.W. e Tang, W.K.S. (2004). Strip-packing using hybrid genetic approach.
Engineering Applications o f Articial Intelligence, v. 17, p. 169– 177.
Zitzler, E. Evolutionary Algorithms for Multi-objective Optimization: Methods and
Applications. PhD t hesis, Swiss Federal Institute of Technology Zurich, (1999).
Thesis (Doctor of Technical Sciences).
Zitzler, E.; Deb, K. e Thiele, L. (200 0). Comparison of multiobjective evolutionary
algorithms: Empirical results. Evol. Com put., v. 8, n. 2, p. 173–195.
Zitzler, E.; Laumanns, M. e Thiele, L. Sept.(2001). Spea2: Improving the strength
pareto evolutionary algorithm. In: EUROGEN 2001, Evolutionary Methods for
Design, Optimization and Control with Appli cations to Industrial Problems, p. 12–
21, Athens.
Zitzler, E. e Thiele, L. (19 98). An evolutionary algorithm for multi-objective opti-
mization: The strength pareto approach. Relatório técnico, Zurich.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
