Algoritmo grasp para cortes de guillotina
Páginas: 14 (3420 palabras)
Publicado: 23 de febrero de 2010
Algoritmo GRASP para cortes de guillotina
A grasp algorithm for guillotine cuts
--------------------------------------------------------------------------------
RESUMEN
El presente trabajo se enfoca en el corte recto de guillotina, el cual debido al alto costo computacional que ocasiona al obtener soluciones exactas, se plantea utilizar un Algoritmo GRASP que permitaencontrar buenas soluciones para cualquier instancia y en tiempos adecuados, teniendo como objetivo principal minimizar el residuo o de desperdicio de materiales que se generan en el proceso de corte. Esto permitirá el incremento de la productividad y reducción de costos haciéndolo atractivo para aplicarlo en el sector de la industria del papel, vidrio, metal y madera.
Palabras Clave: GRASP,heurística, parámetro de relajación, cortes en 2D.
--------------------------------------------------------------------------------
ABSTRACT
This work focus upon the first one, which, due to its high computational cost that causes us to obtain exact solutions, the use of a GRASP Algorithm for straight guillotine cuts, which allows to find good solutions for any instance in suitabletimes is thought to be used, having as the main goal to minimize the lost or waste of materials generated in the cutting process. This will allow us the enhancement of productivity and the reduction of costs making it attractive for applying it in the paper, glass, metal and wood industry sector.
Key words: GRASP, heuristics, relaxing parameter, 2D cuts.--------------------------------------------------------------------------------
INTRODUCCIÓN
El problema de corte en dos dimensiones consiste en determinar un conjunto de patrones de corte variables de tal forma que satisfagan los requerimientos de piezas de material solicitados utilizando el menor número de láminas disponibles. Los cortes en dos dimensiones se clasifican por el tipo de herramienta a utilizar como elcorte por guillotina y corte no guillotina, considerados cortes rectangulares aplicado en el sector de papel (CM 88) (HEIS 96), vidrio (DG 76), (Fa 83), (Ma 79), metal, madera (VM 92).
El principal objetivo de este problema es reducir la cantidad de residuo (desperdicio) de material que se origina al momento de realizar un determinado corte.
Los cortes de guillotina son rectos y de extremoa extremo de la lámina y siempre paralela a uno de los lados de la misma. En algunos casos se tendrá la necesidad de una rotación de 90° en determinados requerimientos para que sus lados siempre queden paralelos a los de la lámina donde se realizará el corte.
Dentro de este proceso de corte se considerarán las posibles combinaciones de los requerimientos; debido al alto grado de combinacionesque se obtiene, presenta un alto costo de procesamiento y consumo de memoria principal de la computadora. En este sentido el trabajo permitirá construir patrones o esquemas de orden de complejidad lineal, y para este tipo de problema se propone la utilización de un algoritmo metaheurístico GRASP (Greedy randomize adaptative search procedure).
El trabajo desarrolla un algoritmo meta heurísticopara la solución del problema de cortes en dos dimensiones. Debido al alto costo computacional que demanda el obtener soluciones exactas, este problema es considerado por la misma algorítmica como NP-difícil, por ello se justifica el desarrollo de la heurística.
FUNDAMENTACIÓN TEÓRICA
El problema de cortes ha sido ampliamente estudiado en las dos últimas décadas, debido a su granaplicabilidad en sectores productivos tales como la industria del papel, vidrio, metal y madera.Existen dos tipos de cortes rectos en dos dimensiones, los cuales son mostrados en la figura 1.
La dificultad inherente a este problema de corte en dos dimensiones, es el gran número de posibles patrones de corte que pueden ocurrir.
Se han reportado diferentes aplicaciones existentes para el...
A grasp algorithm for guillotine cuts
--------------------------------------------------------------------------------
RESUMEN
El presente trabajo se enfoca en el corte recto de guillotina, el cual debido al alto costo computacional que ocasiona al obtener soluciones exactas, se plantea utilizar un Algoritmo GRASP que permitaencontrar buenas soluciones para cualquier instancia y en tiempos adecuados, teniendo como objetivo principal minimizar el residuo o de desperdicio de materiales que se generan en el proceso de corte. Esto permitirá el incremento de la productividad y reducción de costos haciéndolo atractivo para aplicarlo en el sector de la industria del papel, vidrio, metal y madera.
Palabras Clave: GRASP,heurística, parámetro de relajación, cortes en 2D.
--------------------------------------------------------------------------------
ABSTRACT
This work focus upon the first one, which, due to its high computational cost that causes us to obtain exact solutions, the use of a GRASP Algorithm for straight guillotine cuts, which allows to find good solutions for any instance in suitabletimes is thought to be used, having as the main goal to minimize the lost or waste of materials generated in the cutting process. This will allow us the enhancement of productivity and the reduction of costs making it attractive for applying it in the paper, glass, metal and wood industry sector.
Key words: GRASP, heuristics, relaxing parameter, 2D cuts.--------------------------------------------------------------------------------
INTRODUCCIÓN
El problema de corte en dos dimensiones consiste en determinar un conjunto de patrones de corte variables de tal forma que satisfagan los requerimientos de piezas de material solicitados utilizando el menor número de láminas disponibles. Los cortes en dos dimensiones se clasifican por el tipo de herramienta a utilizar como elcorte por guillotina y corte no guillotina, considerados cortes rectangulares aplicado en el sector de papel (CM 88) (HEIS 96), vidrio (DG 76), (Fa 83), (Ma 79), metal, madera (VM 92).
El principal objetivo de este problema es reducir la cantidad de residuo (desperdicio) de material que se origina al momento de realizar un determinado corte.
Los cortes de guillotina son rectos y de extremoa extremo de la lámina y siempre paralela a uno de los lados de la misma. En algunos casos se tendrá la necesidad de una rotación de 90° en determinados requerimientos para que sus lados siempre queden paralelos a los de la lámina donde se realizará el corte.
Dentro de este proceso de corte se considerarán las posibles combinaciones de los requerimientos; debido al alto grado de combinacionesque se obtiene, presenta un alto costo de procesamiento y consumo de memoria principal de la computadora. En este sentido el trabajo permitirá construir patrones o esquemas de orden de complejidad lineal, y para este tipo de problema se propone la utilización de un algoritmo metaheurístico GRASP (Greedy randomize adaptative search procedure).
El trabajo desarrolla un algoritmo meta heurísticopara la solución del problema de cortes en dos dimensiones. Debido al alto costo computacional que demanda el obtener soluciones exactas, este problema es considerado por la misma algorítmica como NP-difícil, por ello se justifica el desarrollo de la heurística.
FUNDAMENTACIÓN TEÓRICA
El problema de cortes ha sido ampliamente estudiado en las dos últimas décadas, debido a su granaplicabilidad en sectores productivos tales como la industria del papel, vidrio, metal y madera.Existen dos tipos de cortes rectos en dos dimensiones, los cuales son mostrados en la figura 1.
La dificultad inherente a este problema de corte en dos dimensiones, es el gran número de posibles patrones de corte que pueden ocurrir.
Se han reportado diferentes aplicaciones existentes para el...
Leer documento completo
Regístrate para leer el documento completo.