Algoritmos para los problemas de corte de guillotina
Páginas: 5 (1066 palabras)
Publicado: 30 de noviembre de 2010
ALGORITMOS PARA LOS PROBLEMAS DE CORTE BIDIMENSIONAL DE GUILLOTINA
El problema de corte en dos dimensiones (TDC) consiste en cortar con máximo beneficio un tablero rectangular en un conjunto finito de pequeñas piezas rectangulares, Este problema tiene un extenso campo de aplicaciones en la industria y comercio. Aparece en el corte de madera, cartón, cristal, plástico, laminas metálicas, etc.El problema (TDC) se puede considerar como un subproblema o versión sencilla de un problema de corte más general en el cual se debe satisfacer toda la demanda de piezas a partir de un conjunto de tableros de distintos tamaños. En este trabajo imponemos a los patrones de corte las siguientes restricciones: Las piezas tienen orientación fija, los cortes son de tipo guillotina y se realizan sin límitede etapas.
Para resolver el problema (TDC) utilizamos los siguientes algoritmos heurísticos: Constructivo, GRASP, Tabu Search, Evolutivo Paralelo Adaptativo y Path Relinking.
Los resultados computacionales muestran que estos procedimientos meta heurísticos son muy eficientes.
Algoritmo GRASP para corte de guillotina en 2D
La meta heurística GRASP se caracteriza por ser un procedimientoiterativo que combina una fase constructiva y una fase de mejoría. En la fase constructiva una solución es construida paso a paso adicionando elementos a una solución parcial. En vez de escoger el elemento a ser adicionado, presenta una función golosa, la cual es dinámicamente adaptada como la solución parcial para luego ser construida. Sin embargo, la selección de un elemento no es determinístico,pero está sujeto a un proceso aleatorio. En ese sentido, cuando repetimos el proceso podemos obtener diferentes soluciones. Después de cada fase constructiva, la fase de mejor´ que usualmente consiste en una búsqueda local simple, trata de sustituir algunos elementos de la solución, los cuales son resultado de una aleatoriedad, produciendo mejores soluciones globales.
El método GRASP presenta dosprincipales fases. La primera fase se refiere a la construcción goloso - aleatorio de una solución y la segunda fase a la mejora de la solución construida. En cada iteración GRASP se va registrando la mejor solución encontrada. El algoritmo termina cuando alguna condición de parada es verificada. La calidad de la solución depende tanto del parámetro de relajación α y de la condición de parada. Estasafirmaciones serán observadas al momento que realizamos la corrida de los casos de prueba para el algoritmo.
Para el propósito del presente trabajo hemos realizado un algoritmo GRASP con 2 parámetros de relajación α y β. La fase constructiva está basada en un procedimiento F F DConstruccionGRASP el cual construye una solución formando patrones de corte, para luego replicarlos de acuerdo a lacantidad de demandas que atienden esos patrones.
Algoritmo EVOLUTIVO PARALELO ADAPTATIVO para corte de guillotina en 2D
Heurística Fans se define como un método de búsqueda por entornos, adaptativo y borroso. Es un método de búsqueda por entornos porque el algoritmo realiza transiciones desde una solución de referencia a otra de su entorno, produciendo trayectorias o caminos. Es adaptativo porquesu comportamiento varía en función del estado de la búsqueda y finalmente es considerado borroso porque las soluciones son evaluadas, además de la función objetivo, mediante una valoración borrosa que representa algún concepto subjetivo o abstracto.
Fans está basado en cuatro componentes principales: uno o varios operadores para construir soluciones; una valoración borrosa para cuantificarlas;un administrador de operación para adaptar el comportamiento o características del operador; y un administrador de vecindario para generar y seleccionar una nueva solución.
Una solución para el problema de corte con guillotina bidimensional se hace mediante un algoritmo evolutivo paralelo adaptativo, en el que cada población evolucionará siguiendo el esquema de búsqueda de soluciones Fans. La...
El problema de corte en dos dimensiones (TDC) consiste en cortar con máximo beneficio un tablero rectangular en un conjunto finito de pequeñas piezas rectangulares, Este problema tiene un extenso campo de aplicaciones en la industria y comercio. Aparece en el corte de madera, cartón, cristal, plástico, laminas metálicas, etc.El problema (TDC) se puede considerar como un subproblema o versión sencilla de un problema de corte más general en el cual se debe satisfacer toda la demanda de piezas a partir de un conjunto de tableros de distintos tamaños. En este trabajo imponemos a los patrones de corte las siguientes restricciones: Las piezas tienen orientación fija, los cortes son de tipo guillotina y se realizan sin límitede etapas.
Para resolver el problema (TDC) utilizamos los siguientes algoritmos heurísticos: Constructivo, GRASP, Tabu Search, Evolutivo Paralelo Adaptativo y Path Relinking.
Los resultados computacionales muestran que estos procedimientos meta heurísticos son muy eficientes.
Algoritmo GRASP para corte de guillotina en 2D
La meta heurística GRASP se caracteriza por ser un procedimientoiterativo que combina una fase constructiva y una fase de mejoría. En la fase constructiva una solución es construida paso a paso adicionando elementos a una solución parcial. En vez de escoger el elemento a ser adicionado, presenta una función golosa, la cual es dinámicamente adaptada como la solución parcial para luego ser construida. Sin embargo, la selección de un elemento no es determinístico,pero está sujeto a un proceso aleatorio. En ese sentido, cuando repetimos el proceso podemos obtener diferentes soluciones. Después de cada fase constructiva, la fase de mejor´ que usualmente consiste en una búsqueda local simple, trata de sustituir algunos elementos de la solución, los cuales son resultado de una aleatoriedad, produciendo mejores soluciones globales.
El método GRASP presenta dosprincipales fases. La primera fase se refiere a la construcción goloso - aleatorio de una solución y la segunda fase a la mejora de la solución construida. En cada iteración GRASP se va registrando la mejor solución encontrada. El algoritmo termina cuando alguna condición de parada es verificada. La calidad de la solución depende tanto del parámetro de relajación α y de la condición de parada. Estasafirmaciones serán observadas al momento que realizamos la corrida de los casos de prueba para el algoritmo.
Para el propósito del presente trabajo hemos realizado un algoritmo GRASP con 2 parámetros de relajación α y β. La fase constructiva está basada en un procedimiento F F DConstruccionGRASP el cual construye una solución formando patrones de corte, para luego replicarlos de acuerdo a lacantidad de demandas que atienden esos patrones.
Algoritmo EVOLUTIVO PARALELO ADAPTATIVO para corte de guillotina en 2D
Heurística Fans se define como un método de búsqueda por entornos, adaptativo y borroso. Es un método de búsqueda por entornos porque el algoritmo realiza transiciones desde una solución de referencia a otra de su entorno, produciendo trayectorias o caminos. Es adaptativo porquesu comportamiento varía en función del estado de la búsqueda y finalmente es considerado borroso porque las soluciones son evaluadas, además de la función objetivo, mediante una valoración borrosa que representa algún concepto subjetivo o abstracto.
Fans está basado en cuatro componentes principales: uno o varios operadores para construir soluciones; una valoración borrosa para cuantificarlas;un administrador de operación para adaptar el comportamiento o características del operador; y un administrador de vecindario para generar y seleccionar una nueva solución.
Una solución para el problema de corte con guillotina bidimensional se hace mediante un algoritmo evolutivo paralelo adaptativo, en el que cada población evolucionará siguiendo el esquema de búsqueda de soluciones Fans. La...
Leer documento completo
Regístrate para leer el documento completo.