Dado un conjunto de requerimientos lineales y un número ilimitado de barras de metal (u otro material) de tamaño estándar, con dimensión mayor a la de los requerimientos. El Problema de Cortes consiste en realizar cortes sobre las barras de tamaño estándar, de tal manera que se obtengan todos los requerimientos con el menor número de barras de tamaño estándar y el menor desperdicio posible. El problema es NP-Difícil, y presenta diversas aplicaciones en los diversos sectores de la industria, tales como la maderera, metal, plástico, etc. La presente Tesis, muestra un Procedimiento de Búsqueda Aleatoria, Adaptativa y Golosa (GRASP), para la resolución del problema de cortes. Experimentos numéricos realizados del algoritmo propuesto sobre 100 problemas-test, reportan una eficiencia, promedio del 95.4% para un parámetro de relajación de 0.5 y 2000 iteraciones. El software implementado consta de 4 módulos importantes: ingreso de datos necesarios para la realización de los cortes, Algoritmos Golosos FFD (First Fit Decreasing) y BFD (Best Fit Decreasing), GRASP y Reportes. / Given a group of lineal requirements and a limitless number of metal bars (or another material) of standard size, with more dimension to that of the requirements. The Cutting Stock Problem consists on carrying out courts on the bars of standard size, in such a way that all the requirements are obtained with the smallest number of bars of standard size and the minor waste possible. The problem is NP-hard, and it presents several applications in the different sectors of the industry, such as the lumberman, metal, plastic, etc. The present Thesis shows a Procedure of Random Search, Adaptive and Greedy to solve the Cutting Stock Problem. Carried out numeric experiments of the algorithm proposed on 100 problem-tests, they report efficiency, average of 95.4% for a parameter of relaxation of 0.5 and 2000 iterations. The implemented software consists of 4 important modules: entrance of necessary data for the realization of the cuts, Greedy Algorithms FFD (First Fit Decreasing) and BFD (Best Fit Decreasing), GRASP and Reports.

Los problemas de corte de piezas se presentan en diversos sectores productivos y han sido ampliamente estudiados en la literatura. En algunos casos, son problemas simples de especificar; pero en todos los casos son extremadamente difíciles de resolver; aquí se considera un caso de esa familia de problemas denominado el problema de corte de piezas irregulares. El objetivo principal de este trabajo es implementar un algoritmo que permita resolver el problema de corte de piezas irregulares el cual consiste básicamente en minimizar el número de superficies que alojen a una determinada cantidad de piezas irregulares en demanda, posicionar las piezas en las respectivas superficies, permitien- do minimizar la perdida de material. La solución a este problema se entrega a través de un programa computacional basado en la metaheurística GRASP y la Simulación Dinámica, donde el algoritmo implementado selecciona las piezas irregulares a posicionar en cada superficie, para luego aplicarles parámetros físicos necesarios para la simulación dinámica. Una vez que las piezas se compacten dentro de cada contenedor se tiene la configuración final, donde se analiza el desperdicio resultante. Se midió el rendimiento del algoritmo basándose en un conjunto de instancias de prueba; los experimentos numéricos sobre 10 instancias numéricas muestran un bajo costo computacional y un grado de eficiencia respecto a la calidad de la solución en 100 %.

Dado un conjunto de requerimientos lineales y un número ilimitado de barras de metal (u otro material) de tamaño estándar, con dimensión mayor a la de los requerimientos. El Problema de Cortes consiste en realizar cortes sobre las barras de tamaño estándar, de tal manera que se obtengan todos los requerimientos con el menor número de barras de tamaño estándar y el menor desperdicio posible. El problema es NP-Difícil, y presenta diversas aplicaciones en los diversos sectores de la industria, tales como la maderera, metal, plástico, etc. La presente Tesis, muestra un Procedimiento de Búsqueda Aleatoria, Adaptativa y Golosa (GRASP), para la resolución del problema de cortes. Experimentos numéricos realizados del algoritmo propuesto sobre 100 problemas-test, reportan una eficiencia, promedio del 95.4% para un parámetro de relajación de 0.5 y 2000 iteraciones. El software implementado consta de 4 módulos importantes: ingreso de datos necesarios para la realización de los cortes, Algoritmos Golosos FFD (First Fit Decreasing) y BFD (Best Fit Decreasing), GRASP y Reportes. / Given a group of lineal requirements and a limitless number of metal bars (or another material) of standard size, with more dimension to that of the requirements. The Cutting Stock Problem consists on carrying out courts on the bars of standard size, in such a way that all the requirements are obtained with the smallest number of bars of standard size and the minor waste possible. The problem is NP-hard, and it presents several applications in the different sectors of the industry, such as the lumberman, metal, plastic, etc. The present Thesis shows a Procedure of Random Search, Adaptive and Greedy to solve the Cutting Stock Problem. Carried out numeric experiments of the algorithm proposed on 100 problem-tests, they report efficiency, average of 95.4% for a parameter of relaxation of 0.5 and 2000 iterations. The implemented software consists of 4 important modules: entrance of necessary data for the realization of the cuts, Greedy Algorithms FFD (First Fit Decreasing) and BFD (Best Fit Decreasing), GRASP and Reports.

Orientador: Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-20T00:13:37Z (GMT). No. of bitstreams: 1 Rangel_MariadoSocorroNogueira_M.pdf: 1539388 bytes, checksum: 1b7cb5400a240ba143c6750c03f7c7ac (MD5) Previous issue date: 1990 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Matemática Aplicada

El problema de corte y empaquetado en dos dimensiones, es un problema NP- difícil perteneciente a la familia de problemas de la optimización combinatoria. El problema combinatorio estriba en la gran cantidad de patrones de corte que puede construirse a partir de un número determinado de requerimientos y un conjunto de objetos los cuales deben ser cortados para satisfacer estos. Este problema es muy importante debido a la gran cantidad de aplicaciones que tiene en la industria. En este trabajo presentamos un estudio de los diferentes métodos que resuelven el problema, clasificándolos por métodos exactos, heurísticas y meta heurísticas. También presentamos conceptos, modelos del problema y las relaciones con otros problemas combinatorios. / -- Two dimensional cutting and packing problems is NP-hard, it belong to the family of problems of the optimization combinatory. This problem is based in the great amount of cut patterns that can be constructed from a determined number of requirements and a set of objects which must be cut to satisfy these. This problem is very important because it presents enormous applicability in the industry. In this work we presented a study of the different methods that solve the problem, classifying them by exact methods, heuristic and meta heuristic. Also we presented concepts, models and the relations with other combinatory problems.

Se tiene un grupo de requerimientos de piezas con una cantidad ilimitada de barras de algún tipo de material de tamaño estándar y éste posee mayor dimensión que el grupo de requerimientos. El problema de cortes 1D describe la utilización de las barras de tamaño estándar realizando cortes sobre ellas, de manera que se satisfaga todos los requerimientos con el menor número de barras de tamaño estándar. El problema es catalogado como NP-Difícil [Garey+79], y es ampliamente aplicado en diversos sectores de la industria tales como la maderera, vidrio, papelera, siderúrgica, etc. La presente tesis propone dos algoritmos GRASP Reactivo para el problema de cortes 1D, basado en los algoritmos GRASP BFD y GRASP FFD propuestos por [Mauricio+02], además, desarrolla un sistema de optimización basado en los algoritmos propuesto. Se realizan experimentos numéricos del algoritmo propuesto sobre 100 instancias de pruebas, de donde se obtiene una eficiencia promedio de 97.04% y una eficiencia ponderada de 97,19% para el GRASP Reactivo BFD con proceso de mejoría, además se observa que el GRASP BFD con proceso de mejoría converge más rápido al encontrar una solución, donde realiza en promedio 1237 iteraciones. Los resultados numéricos muestran una mejora del GRASP Reactivo con respecto al GRASP básico implementado por Ganoza y Solano [Ganoza+02] que obtuvo una eficiencia promedio de 96.73%. Estas mejorías se pueden explicar porque el parámetro de relajación y se ajusta de manera automática y es guiada en la búsqueda de una mejor solución. / It has a set of requirements of parts with an unlimited number of bars of some kind of standard size and material and this has increased the group size requirements. The cutting stock problem 1D describes the use of standard-size bars of making cuts on them, so that it meets all requirements with the least number of standard size bars. The problem is listed as NP-Hard [Garey+79], and is widely used in various industry sectors such as wood, glass, paper, steel, and so on. This thesis proposes two algorithms Reactive GRASP to the cutting stock problem 1D, based on the algorithms GRASP BFD and GRASP FFD proposed by [Mauricio+02], also, developed an optimization system based on the proposed algorithms. Numerical experiments are conducted of the proposed algorithm on 100 instances of testing, where you get an average efficiency of 97.04% and a weighted efficiency of 97,04%, also be seen that the GRASP BFD with improvement converges faster to find a solution average of 1237 iterations. The numerical results show an improvement of reactive GRASP with respect to the basic GRASP implemented by Ganoza and Solano [Ganoza+02], who obtained an average efficiency of 96,73%. These improvements can be explained as the relaxation parameter and is set automatically and is guided in the search for a better solution.

A dissertação apresenta o problema de corte de estoque, que é um problema de otimização inteiro, difícil de ser resolvido computacionalmente. Resolvemos o problema relaxando a condição de integralidade pelo método simplex com geração de colunas, mas esta solução não é viável na prática. Estudamos várias heurísticas para a obtenção da solução inteira do problema.

Os problemas de corte de estoque unidimensional consistem em cortar um conjunto de peças disponíveis em estoque para produzir um conjunto de itens em quantidades especificadas, em que apenas uma dimensão é relevante. Tais problemas têm inúmeras aplicações industriais e são bastante estudados na literatura. Tipicamente, esses problemas de corte apresentam uma característica comum - a minimização das perdas -entretanto, neste trabalho, consideramos que se uma perda é suficientemente grande para ser reaproveitada no futuro, não deve ser contabilizada como perda. Isto introduz uma postura diferente frente ao problema de corte: até que ponto a solução de perda mínima é a mais interessante, já que sobras podem ser reaproveitadas? Algumas características para considerar se uma solução é desejável são definidas e alterações em métodos heurísticos clássicos são propostas, de modo que os padrões de corte com perdas indesejáveis (nem tão grande, nem tão pequena) sejam alterados. As análises das soluções heurísticas são realizadas com base na resolução de um conjunto de classes de exemplos geradas aleatoriamente.

Se tiene un grupo de requerimientos de piezas con una cantidad ilimitada de barras de algún tipo de material de tamaño estándar y éste posee mayor dimensión que el grupo de requerimientos. El problema de cortes 1D describe la utilización de las barras de tamaño estándar realizando cortes sobre ellas, de manera que se satisfaga todos los requerimientos con el menor número de barras de tamaño estándar. El problema es catalogado como NP-Difícil [Garey+79], y es ampliamente aplicado en diversos sectores de la industria tales como la maderera, vidrio, papelera, siderúrgica, etc. La presente tesis propone dos algoritmos GRASP Reactivo para el problema de cortes 1D, basado en los algoritmos GRASP BFD y GRASP FFD propuestos por [Mauricio+02], además, desarrolla un sistema de optimización basado en los algoritmos propuesto. Se realizan experimentos numéricos del algoritmo propuesto sobre 100 instancias de pruebas, de donde se obtiene una eficiencia promedio de 97.04% y una eficiencia ponderada de 97,19% para el GRASP Reactivo BFD con proceso de mejoría, además se observa que el GRASP BFD con proceso de mejoría converge más rápido al encontrar una solución, donde realiza en promedio 1237 iteraciones. Los resultados numéricos muestran una mejora del GRASP Reactivo con respecto al GRASP básico implementado por Ganoza y Solano [Ganoza+02] que obtuvo una eficiencia promedio de 96.73%. Estas mejorías se pueden explicar porque el parámetro de relajación y se ajusta de manera automática y es guiada en la búsqueda de una mejor solución. Palabras clave: GRASP Reactivo, optimización combinatoria, meta heurísticas, problema de corte y empaquetado. / It has a set of requirements of parts with an unlimited number of bars of some kind of standard size and material and this has increased the group size requirements. The cutting stock problem 1D describes the use of standard-size bars of making cuts on them, so that it meets all requirements with the least number of standard size bars. The problem is listed as NP-Hard [Garey+79], and is widely used in various industry sectors such as wood, glass, paper, steel, and so on. This thesis proposes two algorithms Reactive GRASP to the cutting stock problem 1D, based on the algorithms GRASP BFD and GRASP FFD proposed by [Mauricio+02], also, developed an optimization system based on the proposed algorithms. Numerical experiments are conducted of the proposed algorithm on 100 instances of testing, where you get an average efficiency of 97.04% and a weighted efficiency of 97,04%, also be seen that the GRASP BFD with improvement converges faster to find a solution average of 1237 iterations. The numerical results show an improvement of reactive GRASP with respect to the basic GRASP implemented by Ganoza and Solano [Ganoza+02], who obtained an average efficiency of 96,73%. These improvements can be explained as the relaxation parameter and is set automatically and is guided in the search for a better solution. Keywords: Reactive GRASP, combinatorial optimization, metaheuristics, cutting stock problem.

Os problemas de corte de estoque unidimensional consistem em cortar um conjunto de peças disponíveis em estoque para produzir um conjunto de itens em quantidades especificadas, em que apenas uma dimensão é relevante. Tais problemas têm inúmeras aplicações industriais e são bastante estudados na literatura. Tipicamente, esses problemas de corte apresentam uma característica comum - a minimização das perdas -entretanto, neste trabalho, consideramos que se uma perda é suficientemente grande para ser reaproveitada no futuro, não deve ser contabilizada como perda. Isto introduz uma postura diferente frente ao problema de corte: até que ponto a solução de perda mínima é a mais interessante, já que sobras podem ser reaproveitadas? Algumas características para considerar se uma solução é desejável são definidas e alterações em métodos heurísticos clássicos são propostas, de modo que os padrões de corte com perdas indesejáveis (nem tão grande, nem tão pequena) sejam alterados. As análises das soluções heurísticas são realizadas com base na resolução de um conjunto de classes de exemplos geradas aleatoriamente.