Diseño e implementación de un algoritmo heurístico para el problema en el corte de vidrio

I En este trabajo de investigación se resuelve el problema en el corte de vidrio de Saint-Gobain Glass que publica la Sociedad Francesa de Investigación Operativa y Apoyo a la Decisión (ROADEF, por sus siglas en francés), el cual se desprende del conocido problema de optimización Corte y Empaquetado (cutting and packing, en inglés), este engloba a una gran familia de problemas con diferentes variantes que son de gran ayuda a la industria maderera, textil, metalúrgica, de vidrio, etc. La familia pertenece a los problemas NP-duros. Lo interesante de este problema en específico es que contiene varias restricciones que en la literatura se tratan en diferentes variantes, debido a esto la forma de resolverlo se vuelve más compleja. Se han publicado trabajos donde los algoritmos glotones generan buenos resultados para problemas con un número menor de restricciones. En esta tesis de maestría se proponen tres algoritmos glotones y la hibridación de ellos para resolver el problema y dar soluciones factibles, se experimentó con cincuenta instancias que proporciona ROADEF, la hibridación de los algoritmos glotones demuestra que son mejores al trabajar en conjunto que si se hace de forma individual.

This master thesis solves the Cutting and Packing problem of Saint-Gobain Glass published by the French Society for Operational Research and Decision Support (ROADEF), which follows from the well-known problem of cutting and packing optimization, this encompasses a large family of problems with different variants that are of great help to the industry the wood, textile, metallurgical, glass, etc. This family problem belongs to the NP-hard problems. The interesting matter about this specific problem is that it contains several restrictions that in the literature are treated in different variants, because of this the way to solve it becomes more complex. Works have been published where greedy algorithms generate good results for problems with a smaller number of restrictions. In this master's thesis three greedy algorithms and hybridization of them are proposed to solve the problem and give feasible solutions, experimented with fifty instances provided by ROADEF, the hybridization of the greedy shows that they are better when working together than if individual way.