Desenvolvimento de algoritmo massivamente paralelo com GPGPU para criar a região obstrutiva montanhosa discreta

Resumo

Foram realizados dois projetos de pesquisa 2008/11132-7 e 2010/18913-4 em que a aplicabilidade da região livre de colisão para solucionar o empacotamento irregular bidimensional com contêineres abertos (uma dimensão variável). Nestes dois projetos, foi conseguido um conjunto de resultados internacionalmente competitivo em qualidade, conforme publicado em periódicos internacionais indexados. Entretanto, o tempo computacional se apresentou demasiadamente elevado. Neste projeto, o tempo computacional tentará ser drasticamente reduzido, pela pesquisa, proposição e desenvolvimento um novo algoritmo que determinará as posições favoráveis para o posicionamento de um item em um leiaute em representação discreta. Em uma etapa de pré-processamento, serão criados polígonos de obstrução montanhosos que indicam o grau de sobreposição associado a cada posicionamento. Os polígonos de obstrução montanhosos serão discretizados. A união dos polígonos de obstrução montanhosos internos ao polígono de posicionamento interno definem a região de obstrução montanhosa. A região de obstrução montanhosa indica o quanto cada polígono penetra no leiaute. Este processo será realizado em GPGPU permitindo um processamento massivamente paralelo. Uma versão preliminar do algoritmo para contêineres com dimensões fixas foi implementada em MatLab, demonstrando a sua aplicabilidade aos problemas Tangram e Fu. (AU)