Ganoza Sd


 
  
 


 

 


    
 

 


    
 

    ! "#
 $  "  !%& 
"  %

      !"# $% 


    
 

 %

 '(
(
!

 (



 )
&"$ "'"(#')*
 * + , -../

Agradecimientos

Al término de este trabajo que representa la culminación de nuestra tesis, queremos
agradecer a las personas que han ayudado a que esta tarea llegue a su fin.

En primer lugar a Dios, por habernos permitido llegar al final de esta etapa.

A nuestro asesor, Dr. David Mauricio, quien nos guió, apoyo y ayudó para llegar a la
culminación de este trabajo y noshizo ver la importancia de la tesis.

A nuestros amigos y personas especiales, quienes nos brindaron su apoyo, ayuda y
entusiasmo en todo momento.

Por último, pero no menos importante, queremos agradecer a nuestros padres, por su
incesante trabajo y esfuerzo por darnos una mejor educación.

A nuestros padres por ser nuestros ejemplo,
y esforzarse por nuestro futuro.
A nuestros maestros, quienes nosguían para
afrontar ese futuro

UN ALGORITMO DE BÚSQUEDA, ADAPTATIVA,
ALEATORIA Y GOLOSA PARA LA RESOLUCIÓN DEL
PROBLEMA DE CORTES
Dante Ganoza, Ursula Solano (1)
Facultad de Ingeniería de Sistemas e Informática, UNMSM
Av. Germán Amézaga s/n, Ciudad Universitaria, Lima, Perú
(1) e-mail: dantegs@hotmail.com, usolano_lazo@hotmail.com

Resumen
Dado un conjunto de requerimientos lineales y un númeroilimitado 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 aplicacionesen 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 y2000 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.

Palabras Claves: Problema de cortes, algoritmo Goloso, GRASP

AN ALGORITHM OF GREEDY RANDOMIZED ADAPTATIVE SEARCH
PROCEDURE TO SOLVE CUTTUNG STOCK PROBLEM
Dante Ganoza,Ursula Solano (1)
Ability of Engineering of Systems and Computer Science, UNMSM
Av. Germán Amézaga s/n, University City, Lima, Perú
(1) e-mail: dantegs@hotmail.com, usolano_lazo@hotmail.com

Abstract
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 consistson 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, Adaptiveand
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...