Problemas de corte e empacotamento na indústria de móveis: um estudo de caso

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Estudo dos problemas de corte e empacotamento

Pós-graduação em Engenharia Elétrica - FEIS

O problema de corte de placas defeituosas

O problema tratado neste trabalho consiste em cortar uma placa retangular em peças menores retangulares, de modo que a perda seja minimizada. A placa, entretanto, contém defeitos bem localizados. Propomos uma abordagem em grafo E/OU para representação das soluções possíveis e um método de enumeração implícita para determinar a solução ótima. Resultados computacionais demonstram a efetividade da abordagem.

Aplicação de técnicas de decomposição em problemas de corte de estoque

Pós-graduação em Matemática - IBILCE

Problemas de corte : métodos exactos y aproximados para formulaciones mono y multi-objetivo

Los problemas de corte y empaquetado son una familia de problemas de optimización combinatoria que han sido ampliamente estudiados en numerosas áreas de la industria y la investigación, debido a su relevancia en una enorme variedad de aplicaciones reales. Son problemas que surgen en muchas industrias de producción donde se debe realizar la subdivisión de un material o espacio disponible en partes más pequeñas. Existe una gran variedad de métodos para resolver este tipo de problemas de optimización. A la hora de proponer un método de resolución para un problema de optimización, es recomendable tener en cuenta el enfoque y las necesidades que se tienen en relación al problema y su solución. Las aproximaciones exactas encuentran la solución óptima, pero sólo es viable aplicarlas a instancias del problema muy pequeñas. Las heurísticas manejan conocimiento específico del problema para obtener soluciones de alta calidad sin necesitar un excesivo esfuerzo computacional. Por otra parte, las metaheurísticas van un paso más allá, ya que son capaces de resolver una clase muy general de problemas computacionales. Finalmente, las hiperheurísticas tratan de automatizar, normalmente incorporando técnicas de aprendizaje, el proceso de selección, combinación, generación o adaptación de heurísticas más simples para resolver eficientemente problemas de optimización. Para obtener lo mejor de estos métodos se requiere conocer, además del tipo de optimización (mono o multi-objetivo) y el tamaño del problema, los medios computacionales de los que se dispone, puesto que el uso de máquinas e implementaciones paralelas puede reducir considerablemente los tiempos para obtener una solución. En las aplicaciones reales de los problemas de corte y empaquetado en la industria, la diferencia entre usar una solución obtenida rápidamente y usar propuestas más sofisticadas para encontrar la solución óptima puede determinar la supervivencia de la empresa. Sin embargo, el desarrollo de propuestas más sofisticadas y efectivas normalmente involucra un gran esfuerzo computacional, que en las aplicaciones reales puede provocar una reducción de la velocidad del proceso de producción. Por lo tanto, el diseño de propuestas efectivas y, al mismo tiempo, eficientes es fundamental. Por esta razón, el principal objetivo de este trabajo consiste en el diseño e implementación de métodos efectivos y eficientes para resolver distintos problemas de corte y empaquetado. Además, si estos métodos se definen como esquemas lo más generales posible, se podrán aplicar a diferentes problemas de corte y empaquetado sin realizar demasiados cambios para adaptarlos a cada uno. Así, teniendo en cuenta el amplio rango de metodologías de resolución de problemas de optimización y las técnicas disponibles para incrementar su eficiencia, se han diseñado e implementado diversos métodos para resolver varios problemas de corte y empaquetado, tratando de mejorar las propuestas existentes en la literatura. Los problemas que se han abordado han sido: el Two-Dimensional Cutting Stock Problem, el Two-Dimensional Strip Packing Problem, y el Container Loading Problem. Para cada uno de estos problemas se ha realizado una amplia y minuciosa revisión bibliográfica, y se ha obtenido la solución de las distintas variantes escogidas aplicando diferentes métodos de resolución: métodos exactos mono-objetivo y paralelizaciones de los mismos, y métodos aproximados multi-objetivo y paralelizaciones de los mismos. Los métodos exactos mono-objetivo aplicados se han basado en técnicas de búsqueda en árbol. Por otra parte, como métodos aproximados multi-objetivo se han seleccionado unas metaheurísticas multi-objetivo, los MOEAs. Además, para la representación de los individuos utilizados por estos métodos se han empleado codificaciones directas mediante una notación postfija, y codificaciones que usan heurísticas de colocación e hiperheurísticas. Algunas de estas metodologías se han mejorado utilizando esquemas paralelos haciendo uso de las herramientas de programación OpenMP y MPI.

Heurística Surrogate para problema de carregamento de paletes dio produtor

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

A Aplicação de um modelo matemático na resolução de um problema de carregamento de paletes

Global competitiveness has been increased significantly in the last decade and, as consequence, companies are always looking for developing better processes in supply chain operations in order to maintain their competitive costs and keep themselves in the business. Logistics operations represent a large part of the product's final cost. Transportation can represent more than fifty percent of final cost sometimes. The solutions for cutting and packing problems consist in simple and low investment actions, as enhancing the arrangement of the transported load in order to decrease both material and room wastes. As per the presented reasons, the objective of this paper is to show and analyze a real application of a mathematical model to solve a manufacturer pallet-loading problem, comparing results from the model execution and the solution proposed by the company studied. This study will not only find the best arrangement to load pallets (which will optimize storage and transportation process), but also to check the effectiveness of existing modeling in the literature. For this study a computational package was used, which consists of a modeling language GAMS with the CPLEX optimization solver and two other existing software in the market, all of them indicating that an accurate mathematical model for solving this kind of problem in a two-dimensional approach is difficult to be found, in addition to a long execution time. However, the study and the software utilization indicate that the problem would be easily solved by heuristics in a shorter execution time

A Aplicação de um modelo matemático na resolução de um problema de carregamento de paletes

Global competitiveness has been increased significantly in the last decade and, as consequence, companies are always looking for developing better processes in supply chain operations in order to maintain their competitive costs and keep themselves in the business. Logistics operations represent a large part of the product's final cost. Transportation can represent more than fifty percent of final cost sometimes. The solutions for cutting and packing problems consist in simple and low investment actions, as enhancing the arrangement of the transported load in order to decrease both material and room wastes. As per the presented reasons, the objective of this paper is to show and analyze a real application of a mathematical model to solve a manufacturer pallet-loading problem, comparing results from the model execution and the solution proposed by the company studied. This study will not only find the best arrangement to load pallets (which will optimize storage and transportation process), but also to check the effectiveness of existing modeling in the literature. For this study a computational package was used, which consists of a modeling language GAMS with the CPLEX optimization solver and two other existing software in the market, all of them indicating that an accurate mathematical model for solving this kind of problem in a two-dimensional approach is difficult to be found, in addition to a long execution time. However, the study and the software utilization indicate that the problem would be easily solved by heuristics in a shorter execution time

Solução rasterizada para o problema de empacotamento de fita irregular utilizando a Montanha Voronoi.

O empacotamento irregular de fita é um grupo de problemas na área de corte e empacotamento, cuja aplicação é observada nas indústrias têxtil, moveleira e construção naval. O problema consiste em definir uma configuração de itens irregulares de modo que o comprimento do contêiner retangular que contém o leiaute seja minimizado. A solução deve ser válida, isto é, não deve haver sobreposição entre os itens, que não devem extrapolar as paredes do contêiner. Devido a aspectos práticos, são admitidas até quatro orientações para o item. O volume de material desperdiçado está diretamente relacionado à qualidade do leiaute obtido e, por este motivo, uma solução eficiente pressupõe uma vantagem econômica e resulta em um menor impacto ambiental. O objetivo deste trabalho consiste na geração automática de leiautes de modo a obter níveis de compactação e tempo de processamento compatíveis com outras soluções na literatura. A fim de atingir este objetivo, são realizadas duas propostas de solução. A primeira consiste no posicionamento sequencial dos itens de modo a maximizar a ocorrência de posições de encaixe, que estão relacionadas à restrição de movimento de um item no leiaute. Em linhas gerais, várias sequências de posicionamentos são exploradas com o objetivo de encontrar a solução mais compacta. Na segunda abordagem, que consiste na principal proposta deste trabalho, métodos rasterizados são aplicados para movimentar itens de acordo com uma grade de posicionamento, admitindo sobreposição. O método é baseado na estratégia de minimização de sobreposição, cujo objetivo é a eliminação da sobreposição em um contêiner fechado. Ambos os algoritmos foram testados utilizando o mesmo conjunto de problemas de referência da literatura. Foi verificado que a primeira estratégia não foi capaz de obter soluções satisfatórias, apesar de fornecer informações importantes sobre as propriedades das posições de encaixe. Por outro lado, a segunda abordagem obteve resultados competitivos. O desempenho do algoritmo também foi compatível com outras soluções, inclusive em casos nos quais o volume de dados era alto. Ademais, como trabalho futuro, o algoritmo pode ser estendido de modo a possibilitar a entrada de itens de geometria genérica, o que pode se tornar o grande diferencial da proposta.

Organización del conocimiento y resolución de problemas en Física.

Explorar con una cierta base empírica, algunas de las relaciones existentes entre la organización del conocimiento en la memoria del estudiante y su efectividad en la resolución de problemas de Física. Estudio 1: 85 sujetos de COU de Ciencias del Instituto Cardenal Herrera Oria (Madrid), muestreo accidental. 2: 18 alumnos de COU de Ciencias del Instituto Español de París, clasificados según el rendimiento en Física a lo largo del primer trimestre 3: 8 alumnos de diferentes grupos de COU del Instituto Experimental-Piloto Cardenal Herrera Oria. Monografía organizada en dos partes, una base conceptual para enmarcar convenientemente, los estudios de carácter empírico, sus resultados, análisis y discusión y 3 estudios empíricos: Analizar la influencia de la organización del conocimiento conceptual en los alumnos, mediante la construcción de mapas conceptuales a modo de tratamiento sobre la efectividad en la resolución de problemas de Física; Se analiza la influencia del anterior tratamiento en la estructura cognitiva (asociativa) del sujeto, elucidada mediante las técnicas de tests de asociación de palabras; 3 se profundiza en la caracterización de la representación del conocimiento en los buenos resolventes frente a la de los malos y plantea la de los sujetos expertos. 1) Seis problemas de examen de Física nivel COU, Test Colectivo Geft de Witkiin y Col. 2) Test de Asociación de palabras. 3) Pretest-posttest. Tabulación cruzada, prueba de Chi cuadrado, análisis de varianza factorial 2x3, 'T' de Student, análisis cualitativo y cuantitativo. 1) La DIC influye significativamente en la resolución de problemas de Física aunque en diferente grado siendo mayor su influencia en los llamados problemas generales frente a los estándar. También influye en la resolución de problemas de Física que requieren el manejo gráfico o analítico, de una representación esquemática de la situación planteada en el enunciado. La construcción de los mapas no influye significativamente sobre la efectividad de la resolución de problemas de carácter cuantitativo. 2) No podemos sostener fundadamente que la elaboración de mapas conceptuales haya modificado suficientemente el aspecto de la estructura conceptual (asociativa) de los estudiantes, que miden los tests de asociación de palabras. 3) Más que patrones procedimentales de sujetos expertos y novatos, lo que se deriva de la investigación es la existencia de procedimientos eficaces e ineficaces en lo que respecta a la construcción de la representación y a la subsiguiente resolución de problemas de corte académico o escolar. Parece emerger un cuadro relativamente claro con consecuencias definidas en lo que a la Educación Científica respecta, que serán objeto de una investigación posterior ya iniciada.

Inferência fuzzy para o problema de corte de estoque com sobras aproveitáveis de material

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Geração de padrões de corte n-grupos para a indústria moveleira

Neste artigo são apresentadas propostas de soluções para o problema de geração de padrões de corte n-grupos para o corte da matéria-prima na indústria moveleira. Este problema NP-difícil aparece em diversos outros processos industriais que incluem o corte de painéis retangulares grandes de tamanho padrão em retângulos menores. O planejamento dos cortes é um aspecto importante do planejamento da produção nestas indústrias, pois efeitos negativos tais como o perda de matériaprima e tempo de preparo da máquina de corte podem ser minimizados, diminuindo assim os custos de produção. É estudada a eficiência de modelos lineares inteiros para resolver o problema do corte guilhotinado bidimensional propostos em [33,34], bem como o seu uso na geração de colunas para o problema de corte de estoque. São usados dados reais de uma fábrica de móveis de pequeno porte característica do pólo moveleiro de Votuporanga/SP. Os resultados obtidos indicam que as estratégias propostas geram perdas dentro dos requisitos exigidos pela fábrica. © SPM.

Solução do problema de corte bidimensional de peças retângulares tipo não-guilhotinado usando simulated annealing

Pós-graduação em Engenharia Elétrica - FEIS

Propostas de solução para o problema de corte de estoque bidimensional de uma fábrica de móveis de pequeno porte

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Modelos matemáticos para o problema integrado de dimensionamento de lotes e corte de estoque unidimensional

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)