Metadata
Mostrar registro completo
UM ALGORITMO PSEUDO-POLINOMIAL PARA O PROBLEMA DE GERAÇÃO DE PADRÕES DE CORTES GUILHOTINADOS EM PLACAS
Grafos and-or
Programação dinâmica
Algoritmo computacional
Processo industrial
Pseudo-polinomial
Perazzini, Leonardo da Rocha | Postado em:
2018
Resumo
Em um processo de produção de peças a partir de uma placa retangular P, o problema de geração de padrões de cortes guilhotinados consiste em determinar uma sequência de cortes a serem feitos por uma guilhotina em P (padrão de corte) de modo a: gerar um subconjunto de peças; minimizando o desperdício de material; e consequentemente maximizando o lucro da produção. Motivado pela relevância deste problema na indústria, este trabalho tem como objetivo combinar os conceitos de grafos And-Or e programação dinâmica para desenvolver um algoritmo capaz de resolver tal problema em tempo pseudo-polinomial. A utilização de percursos em grafos And-OR para produção de um algoritmo pseudo-polinomial, além de ser uma abordagem que ainda não havia sido utilizada na literatura, produz um algoritmo cuja complexidade de pior caso coincide com o estado da arte para o problema
[Texto sem Formatação]
[Texto sem Formatação]
Tipo de documento
Trabalho de conclusão de cursoAssunto(s)
Corte bidimensional guilhotinado em placasGrafos and-or
Programação dinâmica
Algoritmo computacional
Processo industrial
Pseudo-polinomial