Heuristica de dos-etapas para el problema de corte de piezas con guillotinado bidimensional

Resumen

En un ambiente altamente competitivo, el problema de corte de guillotina bidimensional es un elemento clave en la reducción de costos. Este problema tiene una amplia gama de aplicaciones en industrias cuyos procesos de corte de materiales se realizan con máquinas que sólo permiten cortes de un extremo a otro. En este trabajo se presenta un algoritmo de dos etapas usando metaheurísticas para acomodar en una sola placa de ancho conocido y longitud infinita, un conjunto de ítems rectangulares fuertemente heterogéneos que pueden ser rotados 90°. El objetivo es minimizar la longitud requerida de la placa procurando la acumulación del desperdicio. En la primera etapa se aplica un algoritmo de búsqueda tabú para determinar el orden en que se acomodan los ítems. En la segunda, se busca determinar el mejor acomodo de los ítems en la placa mediante un algoritmo de recocido simulado. Se experimenta con un conjunto de instancias conocidas. Los resultados muestran que la rotación de piezas favorece la obtención de soluciones que igualan al menos las reportadas previamente en la literatura y que la concentración de los desperdicios incrementa su posibilidad de reutilización.

Into a highly competitive environment, two-dimensional guillotine’s cut problem is an elementary key to cost reduction. This problem has a wide variety of applications into factories related to processes material cut. Cuts are done by machines which cut from one edge to other. A two stage algorithm is shown to place a finite set of items in a single plate with a known width and infinite length, using metaheuristics. All items are rectangular, mostly are distinct itself and each one can only be rotated 90 degrees at once. Main objective is minimization of length required by plate and waste accumulation were compacted as much as possible. First stage determines the order from items placed by using a tabu search algorithm. Second stage tries improving the order previous, through a simulated annealing algorithm. Experiments were performed over a set instance already known. Results showed solutions at least, equal or better than solutions known, due to rotation. Also, certain amount of waste grouped was achieved, which means a possible material recycling.