Un Algoritmo GRASP-Reactivo para resolver el problema de cortes 1D

Abstract

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.