Dos enfoques metaheurísticos para resolver el problema de impresión de etiquetas

En el presente trabajo de investigación de tesis se aborda el problema de impresión de etiquetas que se presenta en una imprenta, es un problema de optimización combinatoria y pertenece a la clase de complejidad NP-duro. Dada la dificultad práctica para resolver de forma exacta toda una serie de importantes problemas combinatorios, para los cuales es necesario ofrecer alguna solución debido a su interés práctico, se comenzaron a desarrollar algoritmos que proporcionen soluciones factibles, los cuales no garantizan encontrar el óptimo, pero si encuentran soluciones de buena calidad en un tiempo de cálculo aceptable. De acuerdo con la literatura, los algoritmos que se han utilizado para resolver este tipo de problema y que han dado buenos resultados son: Recocido Simulado, GRASP, Algoritmos Basados en Inmunidad y Búsqueda Tabú. En la presente tesis de maestría, se presentan dos enfoques metaheurísticos, los cuales son Aceptación por Umbral y Búsqueda Tabú, para resolver el problema de impresión de etiquetas. Los resultados obtenidos al implementar los algoritmos de Aceptación por Umbral y Búsqueda Tabú, muestran que se puede resolver el problema de impresión, obteniendo soluciones que mejoran a los trabajos reportados en el estado del arte en la mayoría de las instancias, en tiempos razonables.