Un Algoritmo de búsqueda adaptativa aleatoria y golosa para la resolución del problema de cortes

Abstract

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.