5, 6 e 7 de Agosto de 2010
ISSN 1984-9354
HEURÍSTICA PARA O PROBLEMA DE
SINTERIZAÇÃO DE LIGA METÁLICA E
DIAMANTE PARA A PRODUÇÃO DE
FERRAMENTAS DIAMANTADAS
Eglon Rhuan Salazer Quimaraes (Universidade Candido Mendes)
[email protected]
Ana Carolina de Almeida Sá (Universidade Candido Mendes)
[email protected]
Dalessandro Soares Vianna (Universidade Federal Fluminense)
[email protected]
Marcilene de Fátima Dianin Vianna (Universidade Estadual Norte
Fluminense)
[email protected]
Nas diferentes áreas de aplicação, a substituição de alguns tipos de
ferramentas por ferramentas diamantadas é crescente. Dentre as
áreas de aplicação mais afetadas se encontra o tratamento de
materiais rochosos como o mármore. Neste setorr as ferramentas
diamantadas são utilizadas desde o corte até o polimento das rochas.
Este trabalho tem como objetivo, propor técnicas para otimizar o
processo de criação das ferramentas de corte de mármore, otimizando
o processo de empacotamento das partículas que a compõem, visando
encontrar um maior fator de dureza e maior durabilidade. É proposta
para o problema uma heurística de busca local, da qual os resultados
foram considerados satisfatórios, segundo avaliação de um
especialista da área de síntese de diamantes.
Palavras-chaves: Heurística de busca local, otimização combinatória,
ferramentas diamantadas
VI CONGRESSO NACIONAL DE EXCELÊNCIA EM GESTÃO
Energia, Inovação, Tecnologia e Complexidade para a Gestão Sustentável
Niterói, RJ, Brasil, 5, 6 e 7 de agosto de 2010
1. Introdução
O processo de produção das ferramentas diamantadas utilizadas para o corte de mármore
que são abordadas neste trabalho consiste na sinterização de uma liga metálica juntamente
com o diamante. Esta sinterização gera uma matriz, que é soldada a uma base de aço
concluindo seu processo.
As matrizes geradas pela sinterização de diamante com liga metálica possuem 60% de
partículas de diamante e 40% de liga metálica. As partículas de diamante têm sua
granulometria fixada em 400 mm e não podem se tocar dentro do bloco. Enquanto o pó
metálico que constitui a liga pode variar entre 10 e 50 mm. Os modelos de Furnas e
Andreasen mostram claramente a influência da distribuição granulométrica das partículas no
fator de empacotamento, conforme apresentado; quando existem partículas de tamanhos
diferentes, o fator de empacotamento melhora consideravelmente. A Figura 1 mostra a
eficiência do posicionamento e da diversidade de tamanhos quanto ao empacotamento de
partículas.
Figura 1. Representação de empacotamento com dois tamanhos de partículas.
2
VI CONGRESSO NACIONAL DE EXCELÊNCIA EM GESTÃO
Energia, Inovação, Tecnologia e Complexidade para a Gestão Sustentável
Niterói, RJ, Brasil, 5, 6 e 7 de agosto de 2010
Quando todas as partículas apresentam o mesmo tamanho (monotamanho), o volume
intersticial mínimo é 26% do volume total e é independente do tamanho das partículas
(SILVA, SEGADAES & DEVEZAS, 2004). Contudo, os pós de diamante e liga metálica
apresentam distribuições granulométricas diferentes, podendo variar a proporção de diferença
visto que a granulometria do pó metálico pode variar. Neste caso, as partículas de menor
tamanho podem ocupar os interstícios deixados livres pelo empacotamento de partículas de
tamanho superior, o que eleva a densidade do sistema. Portanto, existe uma grande
possibilidade de otimizar a distribuição de tamanhos de partículas, para maximizar o
empacotamento e reduzir o volume intersticial.
No empacotamento com dois tamanhos diferentes de partículas em que cada um deve
ocupar uma porcentagem do espaço pré-determinado, podemos observar que partículas de
tamanho maior, preferencialmente, não devem estar muito próximas, pois deste modo não
torna a mistura homogênea havendo uma grande possibilidade das partículas ficarem
concentradas em uma determinada região.
Foram encontrados na literatura, alguns documentos que se referem a problemas de
empacotamento: Oliveira e Filgueira (2007) propõem algumas técnicas heurísticas para
carregamento de itens idênticos de base circular (tubos, rolos,...) em uma base retangular. A
resolução consiste em determinar o posicionamento padrão das bases circulares dos itens no
palete retangular, enquanto maximiza o número de itens. Silva, Segadães e Devezas (2004)
utilizam pós de alumina comercial (reativa e tabular) para a realização do empacotamento,
recorrendo a dois procedimentos distintos, usando a metodologia das superfícies de resposta e
técnicas de análise estatística afins (programa de cálculo Statistica). Em ambos os casos foi
obtida a distribuição granulométrica que maximiza a densidade de empacotamento. Os
resultados obtidos demonstram, assim, que o efeito prejudicial da não esfericidade das
partículas pode ser, na realidade, compensado pela otimização da distribuição granulométrica
global.
Neste trabalho é proposto uma heurística de busca local para a sinterização de diamante
com liga metálica, com o intuito de encontrar as melhores distribuições granulométricas e
homogeneidade das partículas, visando chegar a um melhor fator de dureza e maior
durabilidade do material resultante. Para a implementação da heurística proposta, o bloco
gerado pela sinterização foi representado por uma matriz, que devido à complexidade do
3
VI CONGRESSO NACIONAL DE EXCELÊNCIA EM GESTÃO
Energia, Inovação, Tecnologia e Complexidade para a Gestão Sustentável
Niterói, RJ, Brasil, 5, 6 e 7 de agosto de 2010
problema foi criada de forma bidimensional. Nesta matriz são inseridas as partículas de
diamante e de liga metálica. Após este processo é contabilizada a quantidade de espaços
vazios dentro da matriz, de forma a medir o fator de empacotamento obtido pela mesma.
O restante do trabalho está organizado da seguinte forma: a Seção 2 apresenta a heurística
proposta; os resultados são mostrados na Seção 3; as considerações finais são descritas na
Seção 4; e, por fim, são apresentadas as referências utilizadas.
2. Heurística proposta
Métodos baseados em busca local vêm demonstrando sucesso na solução de problemas de
otimização combinatória (ANDREATTA, CARVALHO & RIBEIRO, 2002; FESTA &
RESENDE, 2002; FESTA et al., 2006; GLOVER, 1996; GLOVER, FESTA & MARTÍ,
2000; MLADENOVIC & HANSEN, 1997; OCHI et al., 1998; VIANNA & COELHO, 2006;
VIANNA, OCHI & DRUMMOND, 1999). Neste trabalho é proposto um método de busca
local para o problema de sinterização de diamante com liga metálica. Na heurística proposta,
uma solução inicial é construída e depois refinada através de um método de busca local. A
Subseção 2.1 apresenta uma técnica de construção de uma solução inicial proposta neste
trabalho. Uma estratégia de refinamento proposta neste trabalho é descrita na Subseção 2.2.
2.1. Método construtivo
Como já citado anteriormente, o bloco produzido pela sinterização é representado através
de uma matriz bidimensional. Neste trabalho, esta matriz possui dimensões 10000x10000 e é
inicializada com o valor „0‟ (simbolizando uma matriz inicialmente vazia).
Para se alocar as partículas de diamante na matriz efetua-se uma seqüência de cálculos.
Primeiro, calcula-se a quantidade total de pontos da matriz, multiplicando-se a quantidade de
colunas pela quantidade de linhas. Sabendo que as partículas de diamante ocupam 60% do
4
VI CONGRESSO NACIONAL DE EXCELÊNCIA EM GESTÃO
Energia, Inovação, Tecnologia e Complexidade para a Gestão Sustentável
Niterói, RJ, Brasil, 5, 6 e 7 de agosto de 2010
espaço, é possível determinar que 60% da quantidade de pontos total da matriz serão
ocupados pelo diamante.
Após definida a quantidade de pontos que será preenchida por partículas de diamante,
calcula-se a quantidade de pontos que uma partícula de diamante possui. Este valor é obtido
com base nos dados contidos em um arquivo texto de entrada (extensão .txt), o qual contém as
dimensões (quantidade e distribuição dos pontos) do diamante. A quantidade de partículas de
diamante é calculada através da divisão da quantidade total de pontos que serão preenchidos
por diamante pela quantidade de pontos que um diamante possui. Sabendo a quantidade de
partículas de diamante que serão alocadas, o próximo passo consiste em identificar a
quantidade de diamantes em cada linha e em cada coluna. Para chegar a este resultado, é feita
a raiz quadrada da quantidade de partículas de diamante, este cálculo pode resultar em um
valor não inteiro, neste caso é criada mais uma linha para alocar as partículas restantes.
Após este passo é necessário saber a distância entre as partículas. A distância entre
partículas nas linhas é obtida dividindo a quantidade de pontos sem preenchimento da linha
pelo diâmetro da partícula e a distância entre diamantes na coluna é obtida através do mesmo
processo, porém com valores referentes à coluna. A última linha pode ter uma quantidade
diferente de diamantes, por isto este cálculo também é feito separadamente para a última
linha.
Após efetuar todos os cálculos de quantidade e distância entre os diamantes, os mesmos
são inseridos na matriz respeitando-se estes valores. Esta inserção é feita atribuindo o valor
„1‟ na matriz no espaço em que a partícula vai ocupar e para que se possa diferenciar uma
partícula de outra, o ponto do meio da mesma recebe o valor 5. Os valores de tamanho das
partículas de diamante e das partículas do pó metálico são obtidos através de um arquivo de
texto de entrada (extensão .txt) contido na pasta do aplicativo. A Figura 2 mostra uma parte da
matriz com algumas partículas de diamante de tamanho reduzido já inseridas.
5
VI CONGRESSO NACIONAL DE EXCELÊNCIA EM GESTÃO
Energia, Inovação, Tecnologia e Complexidade para a Gestão Sustentável
Niterói, RJ, Brasil, 5, 6 e 7 de agosto de 2010
Figura 2. Matriz com partículas de diamante de tamanho reduzido.
Depois de inseridas todas as partículas de diamante na matriz é efetuado um teste em cada
índice da matriz para que se possa avaliar a possibilidade de inserção de uma partícula de pó
metálico. Caso sua inserção não sobreponha nenhum índice com valor diferente de „0‟ nem
ultrapasse os limites da matriz, uma partícula é inserida e o teste continua a partir do próximo
ponto até que toda a matriz seja percorrida.
Este método de construção traz uma solução com boa homogeneidade de distribuição das
partículas de diamante, porém não é possível garantir uma ótima condição de empacotamento
devido ao posicionamento das partículas. Devido a este fator foi considerado necessário a
implementação de um método de busca local, o qual percorre toda a vizinhança da solução em
busca de uma solução melhor. Se esta solução vizinha for encontrada, torna-se a solução
corrente e a busca local reinicia seu processo.
6
VI CONGRESSO NACIONAL DE EXCELÊNCIA EM GESTÃO
Energia, Inovação, Tecnologia e Complexidade para a Gestão Sustentável
Niterói, RJ, Brasil, 5, 6 e 7 de agosto de 2010
2.2. Refinamento da solução
Devido a possibilidade do método construtivo não gerar resultados satisfatórios, foi
identificada a necessidade de se implementar um método de refinamento das soluções obtidas.
Contudo, o processo de criação de um método de busca local neste problema possui alguns
fatores que o dificultam. O primeiro fator consiste no tamanho da matriz que representa o
problema, o qual é muito elevado; isto acarreta demora na obtenção de resultados. Outro fator
se deve a grande quantidade de partículas que são alocadas na matriz, devido a isto qualquer
“movimento” que se deseje efetuar sobre uma partícula pode levar a uma necessidade de
“movimentos” com várias outras partículas dentro da matriz, levando a um esforço
computacional elevado.
Diante disto, o refinamento implementado neste trabalho se baseia em gerar novas
soluções a partir de perturbações nos posicionamentos definidos pelo método construtivo. O
método construtivo define a quantidade de partículas de diamante por linhas, colunas e a
distância entre elas. As quantidades de partículas por linha e por coluna seguem estas
definições, porém no momento de se alocar o diamante, a distância entre elas pode receber
uma perturbação ou não, a uma probabilidade definida em 5%.
Este processo é repetido até que a quantidade de iterações definida pelo usuário seja
atingida, gerando várias soluções e todas as soluções geradas ficam guardadas para que
possam ser comparadas posteriormente.
3. Resultados
Para a realização dos experimentos foi definido como 20 mm e 50 mm o tamanho do raio
das partículas de pó metálico e de diamante, respectivamente.
O algoritmo foi executado com 10 iterações e ficou em execução durante
aproximadamente 5 horas em um micro com processador sempron 2800 e 1 GB de memória
RAM.
Os resultados obtidos são apresentados na Figura 3, que apresenta o número de pontos
vazios nos resultados obtidos em cada iteração.
7
VI CONGRESSO NACIONAL DE EXCELÊNCIA EM GESTÃO
Energia, Inovação, Tecnologia e Complexidade para a Gestão Sustentável
Niterói, RJ, Brasil, 5, 6 e 7 de agosto de 2010
Figura 3. Resultados.
Os resultados foram analisados por um especialista da área de síntese de diamantes da
Universidade Estadual Norte Fluminense (UENF), o qual considerou os resultados obtidos
bem promissores.
4. Considerações Finais
A área de síntese de diamantes é uma área em ampla expansão em nosso país. No entanto,
é escasso o uso de técnicas de otimização combinatória em seus processos. Este trabalho tem
como objetivo resolver o problema de sinterização de uma liga metálica com diamante. Para
simular a situação real, algumas dificuldades foram encontradas, tais como: a representação
computacional do problema, tamanho elevado da matriz, dentre outros. Estes fatores levaram
a uma demora na execução do algoritmo.
Contudo, os resultados obtidos mostram que a estratégia de busca local implementada
levou a uma melhora, visto que o melhor resultado foi obtido na sétima iteração e apresentou
162570 pontos preenchidos a mais do que a primeira que representa o método construtivo.
8
VI CONGRESSO NACIONAL DE EXCELÊNCIA EM GESTÃO
Energia, Inovação, Tecnologia e Complexidade para a Gestão Sustentável
Niterói, RJ, Brasil, 5, 6 e 7 de agosto de 2010
Estes resultados, quando analisados por um especialista da área de síntese de diamantes,
foram considerados bem promissores.
Agradecimentos
Este trabalho foi financiado pelo Conselho Nacional de Desenvolvimento Científico e
Tecnológico (CNPq), pela Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro
(FAPERJ), pelo Parque de Alta Tecnologia do Norte Fluminense (TECNORTE) e pela
Fundação Estadual do Norte Fluminense (FENORTE).
Referências
Andreatta, A. A., Carvalho, S.E.R., Ribeiro, C.C. A framework for local search
heuristics for combinatorial optimization problems. Em S. Voss e D. Woodruff, editores,
Optimization Software Class Libraries, p. 59–79. Kluwer, 2002.
Festa, P., Pardalos, P.M., Pitsoulis, L.S., Resende, M.G.C. GRASP with pathrelinking
for the weighted MAXSAT problem. ACM Journal of Experimental Algorithmics, 11:1–16,
2006.
Festa, P., Resende, M.G.C. GRASP: An annotated bibliography. Em C.C. Ribeiro e P.
Hansen, editores, Essays and Surveys in Metaheuristics, p. 325–367. Kluwer, 2002.
Glover, F. Tabu search and adaptive memory programing – Advances, applications
and challenges. Em R.S. Barr, R.V. Helgason, e J.L. Kennington, editores, Interfaces in
Computer Science and Operations Research, p. 1–75. Kluwer, 1996.
Glover, F., Laguna, M., Martí, R. Fundamentals of scatter search and path relinking.
Control and Cybernetics, 39:653–684, 2000.
9
VI CONGRESSO NACIONAL DE EXCELÊNCIA EM GESTÃO
Energia, Inovação, Tecnologia e Complexidade para a Gestão Sustentável
Niterói, RJ, Brasil, 5, 6 e 7 de agosto de 2010
Mladenovic, N., Hansen, P. Variable Neighborhood Search. Computers and Operations
Research, 24, 1097-1100, 1997.
Ochi, L. S., Drummond, L. M. A., Victor, A. O., Vianna, D. S. A parallel evolutionary
algorithm for solving the vehicle routing problem with heterogeneous fleet. Future
Generation Computer Systems 14, 285-292, 1998.
Oliveira, L. J., Filqueira, M. Aplicação de Ligas Fe-Cu-SiC Como Matriz Ligante em
ferramentas Diamantadas. Revista Brasileira de Aplicações de Vácuo, v. 26, n. 1, p. 15-20,
2007.
Silva, A. P., Segadaes, A. M., Devezas, T. C. Aplicação de métodos estatísticos na
otimização da densidade de empacotamento de distribuições de pós de alumina.
Cerâmica [online], v. 50, n. 316, p. 345-354, 2004.
Vianna, D. S. ; Coelho, S. R. Otimização do Tempo de Espera das Embarcações no
Porto de Imbetiba - Petrobrás. Em: XXXVIII Simpósio Brasileiro de Pesquisa Operacional,
Goiânia, 1814-1824, 2006.
Vianna, D. S., Ochi, L. S., Drummond, L. M. A. A parallel hybrid evolutionary
metaheuristic for the period vehicle routing problem with heterogeneous fleet. Lecture
Notes in Computer Science 1388, 216-225, 1999.
10