Embed Size (px)
Citation preview
PROBLEMA DE CORTE
BIDIMENSIONAL GUILHOTINADO -
UMA ABORDAGEM ATRAVÉS DE
FERRAMENTAS CAD E HEURÍSTICAS
DE POSICIONAMENTO.
Cliceres Mack Da Bianco (UFSM)
Alexandre Dias da Silva (UFSM)
Os Problemas de Corte e Empacotamento tem tido grande
importância, devido sua abrangência e aplicabilidade nos mais
diversos ramos industriais. Outro fator é a crescente necessidade que
as indústrias tem de otimizar seus processos, pela maiior
competitividade impostas pelas transformações que têm afetado a
ordem econômica mundial. Neste trabalho é tratado o problema de
corte bidimensional classificado na literatura como Stock Cutting
Problem, que consiste em determinar a melhor forma de cortar objetos,
atendendo a demanda de itens de modo a maximizar o objeto utilizado
evitando o desperdício. Para resolução deste problema é proposta uma
abordagem utilizado heurísticas construtivas em conjunto com
ferramentas CAD. Os testes realizados demonstram que as ferramentas
CAD se ajustam a este problema e os recursos disponíveis em sua
estrutura minimizam as dificuldades de implementação.
Palavras-chaves: problema de corte e empacotamento, heurísticas
construtivas, ferramentas CAD
XXX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUÇÃO Maturidade e desafios da Engenharia de Produção: competitividade das empresas, condições de trabalho, meio ambiente.
São Carlos, SP, Brasil, 12 a15 de outubro de 2010.
2
1. Introdução
Inúmeras indústrias têm seus processos de produção ligados ao corte de matéria-prima em
geral esta matéria-prima se apresenta disponível em tamanhos grandes padronizados, que são
estocados para, posteriormente, serem cortados em itens menores, de tamanhos variados e não
padronizados, para atender à demanda interna e/ou externa.
As indústrias que apresentam esta característica são do ramo de: madeira, tecido, vidro, aço,
espuma e a construção civil, entre outras. Nessas indústrias o planejamento do corte da
matéria-prima é essencial a fim de minimizar o desperdício de material e melhorar a
competitividade das indústrias no seu setor de atividades.
Esta problemática é conhecida na litetatura como Problemas de Cortes e Empacotamentos
(PCE) ou Cutting and Packing Problems na versão inglesa. Segundo Temponi et al. (2007), a
principal característica dos PCE’s é a facilidade que são representados através de modelos
matemáticos, mas devido seus componentes geométricos são problemas difíceis de serem
solucionados.
Os PCE’s tratam-se de problemas combinatórios que do ponto de vista da sua resolução, são
classificados como Não-Polinomial-Difícil ou NP-difícil isso significa que não existe
algoritmo exato que resolva este problema em tempo polinomial. Esta inviabilidade é
atribuída á explosão combinatória de arranjos possíveis quando o objetivo é a determinação
de um arranjo ótimo, ou seja, as técnicas exatas de otimização requerem um longo tempo
computacional de processamento e não propiciam resultados práticos.
Em todo o mundo os pesquisadores, como o grupo europeu de interesse em problemas de
posicionamento EURO e o grupo com interesse em corte e empacotamento ESICUP,
dedicam-se a estudo sobre PCE e ao desenvolvimento de novas aplicações capazes de resolver
novas variantes ou de lidar com instâncias de maior dimensão.
A geração de padrões de corte é a principal etapa que antecede o corte da matéria prima.
Nessa fase são gerados os resultados levando em consideração a melhor forma de posicionar
os itens dentro de uma chapa sem que haja sobreposição, aproveitando da melhor maneira o
espaço e evitando sobras e desperdícios.
Na geração de padrões de corte pretendem-se efetuar o posicionamento de um conjunto de
itens, no interior de um objeto, designados por placas, de acordo com um determinado
objetivo. Em Oliveira (2002), este objetivo pode ser a minimização de uma determinada
função de custo, por exemplo: o desperdício ou a maximização de qualquer função de valor.
A resposta a problemas deste tipo implica a determinação de:
a) Qual critério de posicionamento utilizar;
b) Qual a técnica para que não haja sobreposição;
c) Como inserir todos os itens se a placa for limitada;
d) Qual a melhor disposição dos itens dentro de objetos.
Uma alternativa para resolver problemas da classe NP-Difícil é a utilização de métodos
heurísticos, que, não garantem a obtenção da solução ótima do problema, mas asseguram
soluções sub-ótimas com menor esforço computacional, quando comparado à utilização de
métodos exatos. (NORONHA, 2005).
3
De acordo com Oliveira (2001), é computacionalmente muito pesado garantir a
admissibilidade das soluções obtidas. Torna-se assim quase que obrigatória a utilização de
uma poderosa e eficiente biblioteca geométrica no desenvolvimento de soluções competitivas.
Neste contexto o uso de ferramentas CAD vem suprir a necessidade de bibliotecas
geométricas e permitem desenvolver soluções que apresentam comandos práticos facilitando
o desenvolvimento de aplicações.
2. Classificação dos PCE
Uma tipologia para PCE, foi introduzida por Dyckhoff (1990), na qual o autor propõe quatro
critérios de classificação: dimensionalidade, forma de utilização do objeto, classificação dos
objetos, classificação dos itens.
O número de trabalhos nessa área cresceu significativamente e esta tipologia tornou-se
inadequada. Wäscher et al. (2005), propuseram uma tipologia mais abrangente, baseada de
acordo com o objetivo do problema que pode ser maximização da saída ou minimização de
entrada.
Na primeira situação pretende-se maximizar a utilização de uma determinada matéria-prima
que será cortada, ou seja, maximizar a quantidade de itens que é possível produzir a partir de
determinada matéria-prima. Na segunda situação, o propósito é minimizar a quantidade de
matéria-prima utilizados na produção de um determinado conjunto de itens.
A característica dos itens é outro critério desta tipologia, são analisadas as seguintes situações:
Idênticos - situação onde os itens têm o mesmo formato e tamanho; Fracamente heterogêneo -
onde os itens itens apresentam pequenas variações quanto ao formato e tamanho e podem ser
agrupados em poucas classes de itens idênticos; Fortemente heterogêneo - os itens apresentam
formas e tamanhos diferentes, dificilmente são agrupados.
Quando o objetivo for maximização da saída ele pode ser classificado como:
Problema de Empacotamento: apresenta todos os itens idênticos.
Problema de Colocação: neste caso os itens são fracamente heterogêneos.
Problema de Mochila: os itens são fortemente heterogêneos.
Mas quando o objetivo for minimização de saída podem receber a seguintes classificações:
Problema de Dimensão Aberta (Open Dimensional Cutting Problem): apresenta itens com
dimensões variáveis.
Problema de Corte de Estoque (Cutting Stock Problem): itens fracamente heterogêneos.
Problema de Carregamento de Containers (Containers Packing Problem): itens fortemente
heterogêneos.
O tipo de corte também precisa ser definido. Para os PCE’s existem dois tipos: Guilhotinado e
não-guilhotinado. No tipo não-guilhotinado o corte acontece de acordo com a dimensão do
item sem haver descaracterização da chapa retangular como mostra Figura 1a. No tipo
guilhotinado o corte é efetuado até o final da placa, ou seja, corte é feito na placa de uma
ponta a outra gerando duas placas, este corte é apresentado na Figura 1b.
4
Figura 1 - a) Corte não-guilhotinado e b) corte guilhotinado
Conforme Fiqueiredo (2007), à medida que as peças vão sendo combinadas no objeto, entre
elas pode haver um espaço não aproveitado que chamamos de desperdício interno. Isso ocorre
em função das dimensões das peças serem diferentes. O desperdício externo ocorre quando o
espaço está além do conjunto de peças já projetadas, e nele não cabe mais nenhuma outra peça
no lado direito.
Neste trabalho trataremos do Cutting Stock Problem, onde o objetivo a ser satisfeito é cortar o
menor número de placas produzindo todos os itens demandados, com um número infinito de
objetos retangulares de dimensões (W, H), denominado placas, com itens de dimensões
variáveis (wi, hi) fracamente heterogêneo, no qual hi é o comprimento e wi é a largura das
peças. Quanto ao tipo de corte este trabalho empregou o corte guilhotina.
3. Ferramentas CAD
A velocidade, execução e implementação de um projeto são fundamentais para o sucesso das
indústrias Esta realidade tem obrigado o emprego de metodologias e ferramentas de gestão no
desenvolvimento de produtos que possibilitam atingir estes objetivos.
As indústrias que envolvem em seu processo produtivo o problema de corte precisam do
apoio de aplicações informáticas em três grandes áreas: concepção e desenho do produto,
determinação de padrões de corte e, por fim, na determinação do percurso de corte e no
controle automático da máquina de corte. (LECTRA, 2008)
Existem algumas aplicações informáticas isoladas e dedicadas à realização de apenas uma
determinada tarefa, mas a tendência é adicionar estas capacidades a sistemas de CAD/CAM,
através da integração de módulos adicionais para a realização de tarefas específicas. A área
menos desenvolvida, e também a de maior complexidade, é claramente a de determinação de
padrões de corte. (ÁLVARES & FERREIRA, 2006).
Os sistemas CAD - (Computer Aided Design), e CAM – (Computer Aided Manufacturing),
que em português corresponde a Projeto Auxiliado por Computador e Manufatura Auxiliada
por Computador, respectivamente, são ferramentas que desempenham um papel fundamental
para a viabilização de um projeto de produto em tempos reduzidos, oferecendo oportunidade
para simular e reduzir custos na fase de desenvolvimento e geração do produto.
O investimento na tecnologia CAD/CAM, adotada pelas empresas, permitem uma vez
modelados os produtos, escolher o processo de fabricação com o auxilio da ferramenta CAM,
selecionar a máquina, informar a seqüência de fabricação, escolher ferramentas e condições
de corte. A partir daí, o sistema calcula automaticamente a trajetória das ferramentas,
transferindo-as na forma de um programa CN, para uma máquina-ferramenta determinada
anteriormente. (CASTRO, 2007).
Uma das grandes vantagens das indústrias que fazem uso das ferramentas CAD é ter seus
processos de desenvolvimento e fabricação integrados, ou seja, após definir os padrões de
5
corte é possível enviar os resultados para equipamentos automatizados, como as guilhotinas
CNC (Command Numeric Computer), fazendo conexão entre os desenhos no sistema CAD e
a máquina de corte. (TEBIS, 2006)
Devido estas vantagens as indústrias utilizam ferramentas, para aperfeiçoar a geração de
padrões de corte, provindas de CAD, aliada com a facilidade de desenvolvimento de
aplicações e integração de ferramentas.
Outra facilidade das ferramentas CAD que podem ser adaptadas de acordo com as
necessidades específicas de cada indústria, possibilitando até mesmo o desenvolvimento de
aplicações, pois os recursos fundamentais como mover, rotacionar e verificar sobreposição
estão prontos, o que não acontece em outras ferramentas usadas para estes fins por exemplo:
as linguagens de programação, onde a implementação desses recursos se torna complexa.
Em uma aplicação desenvolvida para PCE é fundamental implementar uma rotina para
movimentar as peças, pois no decorrer da execução é preciso rearranjar as peças para melhor
aproveitar a placa. Através da ferramenta CAD Move, é necessário somente um simples
comando indicando a peça a ser movimentada, sua posição atual e o local a inserida.
Exemplo: (command "move" peça pto_inicial pto_final).
O recurso de rotacionar figuras geométricas nas aplicações para gerar padrões de corte,
otimiza a placa e evita desperdício, porém dependendo da linguagem de programação a
implementação de tal recurso se torna complexa e em alguns trabalhos não sendo empregada.
Segundo Gomes (2005), a consideração de rotações na geração de padrões de corte aumenta
consideravelmente a dificuldade dos problemas, ora relacionado ao nível da componente
combinatória, por aumento no número de combinações possíveis, ora relacionado componente
geométrica, pela existência de maior diversidade de formas geométricas.
Esta operação se torna trivial com o uso do comando CAD Rotate por exemplo: (command
"rotate" peça "" pto_inicial 90).
Em Costa (2007), a complexidade do problema é refletida na necessidade de garantir uma
precisão adequada na verificação da existência de sobreposição no posicionamento de dois
itens e devem ser implementadas de uma forma eficiente, uma vez que são recursos
elementares na resolução deste tipo de problema.
Assim, o emprego de recursos que evitem que duas peças ocupem o mesmo espaço é requisito
para gerar padrões de cortes factíveis, tanto em estudos com itens de formatos regulares tanto
para formatos irregulares.
Em estruturas CAD a verificação de sobreposição tem menor complexidade, pois a operação
Intersect consegue detectar quando duas figuras se sobrepõem.
4. Heurísticas
A utilização de heurísticas construtivas é muito freqüente na resolução de problemas NP
Difíceis, principalmente nas situações onde se pretende obter rapidamente uma solução de boa
qualidade.
Normalmente, as heurísticas construtivas baseiam-se em seqüência ordenadas e em regras
gulosas de construção. A seqüência ordenada é obtida pela ordenação inicial dos elementos,
com base num determinado critério. A solução é sucessivamente construída pela aplicação de
uma regra gulosa sobre o elemento seguinte da seqüência ordenada.
6
De acordo com Dal Bianco & Silva (2009), a maior parte dos pesquisadores opta inicialmente
por uma heurística construtiva, percebe-se uma preferência pela técnica Bottom-left, pois
otimiza os espaços na fase de posicionamento dos itens e encontra soluções em curto período
de tempo.
A construção dos padrões de corte é assegurada por heurísticas de posicionamento gulosas,
que se baseiam na avaliação do desperdício das soluções parciais, no comprimento do padrão
de corte ou nas coordenadas do ponto de posicionamento. (MORABITO, 2008)
As heurísticas construtivas apresentam regras de posicionamento que são responsáveis pela
determinação do ponto de posicionamento de uma determinada peça, sendo aplicada
sucessivamente a todas as outras peças de forma a obter-se o padrão de corte.
Na literatura podem ser encontrados alguns algoritmos para o encaixe das peças na chapa
retangular como: Next-Fit (NF), First Fit (FF), First Fit Decreasing (FFD), Next Fit
Decreasing (NFD), Bottom-Left (BL). Os algoritmos de encaixe empregados neste trabalho
foram Botton_left (BL) e First-left (FL).
4.1 Bottom-left
O Bottom-left toma uma lista com as peças a serem encaixadas e prossegue com o processo de
encaixe das peças colocando a primeira no canto inferior esquerdo e as demais peças são
encaixadas da seguinte forma: primeiramente tenta-se encaixar a peça o mais próximo da base
(eixo x), e depois ela deve ser movimentada mais a esquerda possível da chapa, sem sobrepor
nenhuma peça. (CORREA, et. al, 2005)
Após todas as peças serem encaixadas é possível determinar o desperdício, calculado através
da altura da solução obtida. A altura de uma solução corresponde ao canto superior da peça
que está em um nível mais alto. A melhor solução é aquela que apresenta a menor altura, ou
seja, que apresenta menor desperdício da placa. A largura está limitada pela dimensão da
placa.
4.2 First-fit
Outra heurística adotada na solução deste trabalho é a First-fit. Nesta técnica a lista de peças
para encaixe é processada da seguinte forma: Inserir a peça mais a esquerda possível, a partir
do ponto (0,0) preenchendo os espaços existentes mais próximos do eixo y, quando necessário
criar uma nova coluna. Segue-se a mesma regra de avaliação de desperdício.
Como o método prioriza preencher no eixo y primeiro e deste modo a altura fica limitada até
preenchimento dos espaços. Se mesmo assim houver peças a serem encaixadas, elas são
colocadas em cima, começando da esquerda, a fim de manter a largura fixa e se ter um ponto
de comparação entre os algoritmos implementados. A Figura 2a apresenta o comportamento
da heurística BL e 2b apresenta a heurística FF.
a) b)
7
Figura 2 - a) Representação do comportamento da heurística BL e b) FF
5. Heurísticas Construtivas em Ferramentas CAD
Este trabalho teve como critério de ordenação a dimensão, ou seja, a seqüência de
posicionamento segue a ordem decrescente de área. A primeira peça inserida no canto inferior
esquerdo gera uma faixa. A Figura 3 ilustra uma faixa que tem seu comprimento definido pela
dimensão da peça. Caso a heurística empregada seja BL as faixas criadas terão prioridade o
eixo X no caso sentido de posicionamento será vertical (Figura 3b) e o sentido da faixa será
horizontal priorizando o eixo Y se a heurística for FF (Figura 3c).
A cada iteração tenta-se mover a próxima peça da lista, respeitando o comprimento e a largura
da faixa. Caso a peça exceda o comprimento ou a largura da faixa o operador de rotação é
avaliado se retornar verdadeiro a peça é rotacionada e posicionada na faixa se for falso então a
peça é excluída da faixa. A Figura 4 apresenta esta situação, o operador rotação inverte a
largura e o comprimento da peça que esta sendo posicionada para que não exceda os limites
da faixa. Quando toda a faixa estiver preenchida uma nova faixa é criada. São formadas outras
faixas até que a demanda total de cada item seja satisfeita ou enquanto existir espaço na placa.
Figura 3- Exemplo de geração de faixas
Figura 4 - Exemplo de rotação de peças
5.1 Fases da heurística
Foi seguido um processo iterativo composto das seguintes fases:
1. Gerar uma lista com as peças em ordem decrescente de área (Ld);
2. Especificar a dimensão da nova placa (Pj);
3. Selecionar a primeira peça (maior altura) da lista (p1);
4. Definir a faixa de acordo com a altura da peça incluída (Fl e Fw);
5. Escolher as próximas peças de acordo com as dimensões da faixa;
8
6. Remover da Ld as peças inseridas na placa;
7. Caso não haja nenhuma peça que caiba na faixa, ir para o passo 4.
8. Caso não haja nenhuma peça que caiba na placa, ir para o passo 2.
A heurística BL e FF seguem as etapas mudando somente a ordem de posicionamento na
faixa.
A Figura 5 apresenta o pseudo-código da heurística propostas.
Figura 5 – Pseudo-código genérico da heurística
6. Resultados
Para avaliar a eficácia das ferramentas CAD, foi desenvolvida uma aplicação utilizando as
heurísticas construtivas BL e FF descritas neste trabalho.
Os testes com as heurísticas em ferramentas CAD forma realizados com um conjunto de seis
instâncias, disponível por Hopper e Turtton (2001).
Cada uma das seis instâncias possui os seguintes dados: comprimento (L) e largura (W) da
placa, o número de peças diferentes (m), o comprimento ótimo da placa (lo), e, para cada uma
das peças, o comprimento (li) e a largura (wi). Na Tabela 1, estão especificados os dados
principais referentes à dimensionalidade de cada uma das instâncias utilizadas.
Instâncias m lo L x W
I1 16 ou 17 20 20 x 20
I2 25 15 40 x 15
I3 28 ou 29 30 60 x 30
I4 49 60 60 x 60
I5 72 ou 73 90 60 x 90
I6 97 120 80 x 120
Tabela 1 - Instâncias utilizadas nos testes
As instâncias foram executadas duas vezes, uma com a heurística BL e a outra com a
heurística FF.
Os algoritmos foram desenvolvidos em linguagem AutoLisp e executados em um computador
Intel Celeron, 2 Gb de memória RAM e ambiente Windows Vista.
Além de avaliaram as ferramentas CAD, os testes realizados comparam a qualidade das
heurísticas. A Tabela 2 resume a distância relativa entre o comprimento ótimo e o
comprimento encontrado pelas heurísticas BL e FF comparadas com os resultados obtidos
com Hopper e Turton (2001).
1. Definir a lista C= (p1....,pn)
2. Ordenar Ld = (p1 > p2 >p4)
3.Se pi < Pj
Insere pi
4.Define Fl e Fw
5. Enquanto Fl e Fw > pi
Mover pi
6. Retonar passo 3.
9
Instância lo (cm) Hopper e
Turton (%)
BL (%) FL (%) T (s)
I1 20 25 30 25 -
I2 15 39 25 40 -
I3 30 33 30 35 -
I4 60 33 30 35 -
I5 90 31 31 33 -
I6 120 34 31 36 1
Tabela 2 - Distância Relativa entre comprimento ótimo as melhores resultados de BL e FL
Além de apresentar a distância relativa entre o comprimento ótima e o comprimento que
encontrado pelas heurísticas BL e FF a Tabela 2 apresenta o tempo de execução das
heurísticas BL e FF. Nas instâncias I1 ate I5 o tempo foi inferior á um segundo, portanto não
foi descrito.
Os resultados obtidos pela heurística FF foram melhor apenas à primeira instância, conforme
o tamanho da instância aumenta o desperdício tende a aumentar.
Para solução ótima deste problema as peças são arranjadas de forma não guilhotina, e o
problema proposto neste trabalho é guilhotina, apesar disto as heurísticas descritas
apresentaram bons resultados, em algumas instâncias supera os resultados obtidos por Hopper
e Turton.
O tempo de processamento de todas as instâncias foi inferior a um segundo (1s), isto
demonstra que as ferramentas CAD não tornam os algoritmos pesados computacionalmente,
tornando seu uso viável neste tipo de problema.
As Figuras 6, 7, 8 e 9, apresentam resultados obtidos pelas heurísticas BL e FL, porém deve-
se observar que estes resultados utilizam heurísticas construtivas e todos podem ser
melhorados, com aplicação outras técnicas como: as meta-heurística.
A Figura 9 é o resultado para instância I6 onde 9a apresenta o resultado obtido pela heurística
BL e 9b é o resultado obtido Hopper e Turton (2001), observa-se que a heurística BL
aproveitou melhor os espaço da placa resultando em um desperdício bem inferior quando
comparadas com a de Hopper e Turton.
10
Figura 6 - Instância I1 - a) Resultado obtido pela BL - b) resultado obtido pela FF
Figura 7 - Instância I2 - a) Resultado obtido pela BL - b) resultado obtido pela FF
Figura 8 - Instância I3 - a) Resultado obtido pela BL - b) resultado obtido pela FF
Figura 8 - Instância I3 - a) Resultado obtido pela BL - b) resultado obtido pela FF
11
Figura 10 – Instância I a) Resultado obtido pela BL - b) resultado obtido por Hopper e Turton (2001)
7. Conclusões
Neste artigo, estudou-se o Cutting Stock Problem guilhotinado, no qual os objetos possuem
forma retangular e têm duas dimensões relevantes. Por se tratar de um problema de natureza
NP - Difícil, foi proposta, para sua resolução, heurísticas Bottom-letf e Firt-fit.
Analisando-se os resultados obtidos, pode-se destacar que:
a técnica BL apresentou, nas seis instâncias testadas, bons resultados;
quanto maior a diversidade de peças de uma instância melhor será o aproveitamento do
espaço da placa;
a heurística BL obteve melhor aproveitamento de placa, esta técnica se enquadra nos
requisitos de corte guilhotinado;
as ferramentas CAD facilitam e agilizam o processo de desenvolvimento e implementação
dos algoritmos para corte e empacotamento, dispensando o uso de bibliotecas geométricas.
As evidências empíricas deste trabalho mostram que as ferramentas CAD, apesar de pouco
utilizadas, podem ser apropriadas para solucionar instâncias associadas a situações reais, nas
quais o objetivo seja cortar um objeto de forma a atender à demanda e minimizar o
desperdício de material envolvido no processo.
Referências
ÁLVARES, J. A. & FERREIRA J.C.E. Webmachining: uma metodologia para integração CAD/CAPP/CAM
voltada para manufatura remota de peças rotacionais via Web. Universidade Federal de Santa Catarina. 2006.
CASTRO, E. B. P. Automação da produção. Curso de Engenharia de Produção, Universidade Federal de Juiz
a)
b)
12
de Fora. Disponível em: <www.engprod.ufjf.br/ epd_automacao/EPD030_Introducao.pdf>. Acessado em: 09
nov. 2009.
CORREA M. D.; COTA G. R. & FALQUETO, S. T. Implementação de Algoritmo Genético para solução do
problema de corte industrial bidimensional não-guilhotinado. 2008.
COSTA, M.T. Novas abordagens ao posicionamento de figuras irregulares. Tese de doutorado. Universidade
do Porto, 2007.
DAL BIANCO, M. C. & SILVA, D. A. Ferramentas Geométricas e Técnicas Heurísticas para o Problema de
Corte e Empacotamento envolvendo formas irregulares. VI Simpósio De Excelência em Gestão e Tecnologia -
SEGeT- .2009.
DYCKHOFF, H. A typology of cutting and packing problems. European Journal of Operational Research,
44(2):145–159, 1990.
FIQUEIREDO, A. G. & RANGEL S. Aplicação de modelos de 2-estágios e 1-grupo na geração de padrões de
corte na indústria moveleira. S.J. do Rio Preto. 2007.
GOMES A. M. F. Abordagens Heurísticas ao Posicionamento de Formas Irregulares. Tese de do doutorado.
Universidade do Porto, 2005.
HOPPER E. & TURTON B.C.H. An empirical investigation of meta-heuristic and heuristic algorithms for a
2D packing problem. European Journal of Operational Research 128 34±57, 2001.
LECTRA. As três soluções CAD/CAM da Lectra Vocacionadas para materiais compósitos maximizam a
produtividade e fazem face aos exigentes requisitos de qualidade da empresa Corse Composites Aéronautiques.
Disponível em <http: //www.lectra.com/binaries/ Lectra_customersuccessstory
_CorseComposite_IndustrialFabric_pt_France_VectorDesignConcept_tcm31-136029.pdf >. Acessado em: 10
mar. 2010.
MORABITO, R. & PUREZA, V. Geração de padrões de corte bidimensionais guilhotinados e restritos via
programação dinâmica e busca em grafos-e/ou. Produção, 17(1), 33-51, 2007.
NORONHA, T. F.; SILVA, M. & ALOISE, J. D. Uma Abordagem sobre Estratégias Meta-heurísticas. 2005.
OLIVEIRA, J. F. & FERREIRA, J. S. Algorithms for nesting problems. European Journal of Operational
Research,v. 84 p. 506–521, 1993.
OLIVEIRA, J. F. Problemas de Posicionamento de Figuras Irregulares: uma perspectiva de otimização. Tese
de Doutoramento, Universidade do Porto,1995.
TEBIS. Solução CAD/CAM para produção com os padrões mais elevados Disponível em <http://www.tebis.
com/cms/fileadmin/broschueren/pt_Tebis_ProductRange_061030.pdf>. Acessado em: 20 mar. 2010., 2006
TEMPONI, C. C. E; SOUZA, R. S.; ANDRADE, M. S. & SANTOS, F. A. Open Dimensional Cutting
Problem: uma abordagem Híbrida via GRASP e ILS. VII Encontro de Engenharia de Produção, 2007.
