00b4952459f6a57058000000 1

Un Algoritmo Evolutivo Paralelo Adaptativo para el problema del
Corte con Guillotina en 2D
J.I. Pelaez.1) D. La Red 2) A. Mesas.1) J.M. Doña. 1) ) J.Veintimilla 3)
1)

Dpto. de Lenguajes y Ciencias de la Computación
Universidad de Málaga. Málaga 29071. España
E-mail: jignacio@lcc.uma.es
2)

Dpto. de Informática
Universidad Nacional del Nordeste
Corrientes. Argentina
E-mail:lrmdavid@exa.unne.edu.ar
3)

Dpto. de Ingeniería Civil Materiales y Fabricación
Universidad de Málaga. Málaga 29071. España
E-mail: jveintimilla@uma.es

Resumen
El corte con guillotina en 2D es un problema
especialmente relevante en multitud de industrias
tales como papeleras, textiles, madereras,
metalúrgicas..., en las que se requiere cortar
láminas donde ubicar determinadas piezas, que
tienen asociadas unasdimensiones y un valor, de
manera que se maximice el beneficio. La
utilización de técnicas evolutivas paralelas,
heurísticas adaptativas y lógica borrosa, se han
mostrado adecuadas para resolver problemas de
optimización con excesivo costo computacional y
un espacio de soluciones grande. El propósito de
este trabajo es presentar un algoritmo evolutivo
paralelo, basado en una búsqueda adaptativa
borrosapor entornos para el problema del corte con
guillotina en 2D, y comparar sus resultados con
otros algoritmos evolutivos secuenciales y métodos
exactos.

una lámina en segmentos rectangulares donde se deben
ubicar piezas de tamaño y valor dado, de manera que se
maximice la suma de los valores de las piezas cortadas.
Una de las características del problema CG2D es que
utiliza un patrón de corte quesolo permite cortar
ininterrumpidamente desde un extremo a otro de la
lamina, lo que se conoce como cortes válidos. En la
figura 1 se muestra una secuencia de cortes válidos en la
que cada número indica el orden de corte. Mientras que
en la figura 2, se muestra una secuencia de cortes no
válidos.

Figura 1.Secuencia válida de corte con guillotina.

Palabras Clave: Problemas de Corte; Heurísticas;Algoritmos Evolutivas Paralelos; Lógica Borrosa;
Búsqueda Adaptativa; Optimización.

1 INTRODUCCIÓN
El problema del corte con guillotina en 2D, es un
problema especialmente relevante en multitud de
industria como metalúrgicas, papeleras, madereras,
textiles, etc. Diseñar algoritmos eficientes para este
problema es de gran importancia para estas industrias por
el aumento de rendimiento ycompetitividad que se
obtendría al maximizar el beneficio de los cortes
realizados. Básicamente el problema del corte con
guillotina en 2D (en adelante CG2D) consiste en dividir

Figura 2.Secuencia no válida de corte con guillotina.
De manera formal el CG2D se define como sigue:
Sea A0 = (α 0 , β 0 ) una lámina rectangular de largo α 0 y
ancho β 0 y, sea R un conjunto de m piezas rectangulares
más

pequeñasR1 , R2 ,..., Rm

con

dimensiones

(α1 , β1 ), (α 2 , β 2 ),..., (α m , β m ) , valor v1 , v2 ,..., vm

y máxima

cardinalidad b1 , b2 ,..., bm . El objetivo es construir un

patrón de corte válido para A0 que maximice la suma del
valor de las piezas cortadas usando no más de bi replicas
de cada rectángulo Ri en el patrón; y donde dicho patrón
de corte cumpla las siguientes restricciones:
1.
2.Todas las dimensiones (α i , β i ) para i = 1, 2,…,
m son enteros a lo largo del eje-x o el eje-y.
La orientación de las piezas se considera fija
(una pieza de longitud e y ancho f es distinta de
otra de longitud f y ancho e).

En adelante y con el propósito de distinguir entre las
piezas dadas en un conjunto R y los rectángulos
producidos por los cortes en A0 en cada etapa durante el
proceso decorte, nos referimos a las primeras como
“piezas” y a las segundas como “rectángulos”.
Desde los años 60 se han diseñado distintos tipos de
algoritmos para solucionar este problema. Para ello se
han utilizado desde técnicas tradicionales como
programación dinámica o lineal [7][8][9][10], métodos
heurísticos [3], y finalmente técnicas de inteligencia
artificial [5][11].
Dentro de las técnicas...