1. Repositorio Institucional del Tecnológico Nacional de México (RI - TecNM)
2. Tesis de Posgrado
3. Tamaulipas
4. Instituto Tecnológico de Ciudad Madero
5. Tesis
6. Tesis de Maestría
7. Maestría en Ciencias de la Computación

Titre:	UN ESTUDIO FORMAL DE HEURÍSTICAS PARA EL PROBLEMA DE EMPACADO DE OBJETOS DE UNA DIMENSIÓN
Auteur(s):	Gonzalez San Martin, Jessica Elena
Date de publication:	2021-05-01
Editeur:	Tecnológico Nacional de México
metadata.dc.publisher.tecnm:	Instituto Tecnológico de Ciudad Madero
Description:	El problema de Bin Packing de una dimensión (1D-BPP) es un problema clásico de optimización que es conocido por su aplicabilidad y complejidad, el cual pertenece a una clase especial de problemas denominada NP-duro. A través de los años el esfuerzo de muchos investigadores ha concretado en una variedad de algoritmos que han mostrado un desempeño satisfactorio, sin embargo, en la actualidad no existe un algoritmo heurístico capaz de encontrar la solución óptima para todas las posibles instancias de un problema de este tipo a pesar de los esfuerzos de la comunidad científica. En este trabajo se presenta un estudio de los algoritmos más relevantes y un análisis comparativo de los principales trabajos relacionados con 1D-BPP con el fin de identificar componentes y/o estrategias que muestran un impacto positivo en el desempeño de estos. Se propone una nueva versión de la metahuerística Grouping Genetic Algorithm with Controlled Gene-Transmission (GGA-CGT) la cuál denominamos GGA CGT/D. Para este algoritmo se diseñaron tres estrategias: un método de selección del límite inferior más adecuado al problema que se resuelve, un método de reducción del problema y un método de diversificación de soluciones los cuales ayudaron a mejorar el desempeño del algoritmo original. Los resultados obtenidos de un extenso estudio computacional confirman que GGA-CGT/D logra superar el desempeño de los mejores algoritmos del estado del arte. Como caso de estudio se seleccionó el conjunto de instancias más aceptado para comparar algoritmos competitivos. Este conjunto es parte de BPPLIB e incluye a la clase Hard28, que parece tener el mayor grado de dificultad para los algoritmos BPP. También se aborda un nuevo conjunto de instancias retadoras de grandes dimensiones llamado BPP𝑣𝑢_𝑐. El algoritmo propuesto puede resolver óptimamente todas las instancias seleccionadas de BBPLIB, y un gran número de BPP𝑣𝑢_𝑐, resolviendo en total 2309 instancias difíciles, abiertas hasta el momento, de las cuales 49 no habían sido resueltas por ninguno de los algoritmos seleccionados como caso de estudio.
metadata.dc.type:	info:eu-repo/semantics/masterThesis
Collection(s) :	Maestría en Ciencias de la Computación

Ce document est protégé par copyright Voir la licence

Ce document est autorisé sous une licence de type Licence Creative Commons