Utilize este identificador para referenciar este registo: https://rinacional.tecnm.mx/jspui/handle/TecNM/3000
Título: UN ESTUDIO FORMAL DE HEURÍSTICAS PARA EL PROBLEMA DE EMPACADO DE OBJETOS DE UNA DIMENSIÓN
Autor: Gonzalez San Martin, Jessica Elena
Data: 2021-05-01
Editora: Tecnológico Nacional de México
metadata.dc.publisher.tecnm: Instituto Tecnológico de Ciudad Madero
Descrição: 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
Aparece nas colecções:Maestría en Ciencias de la Computación

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
G13070673_donacion_tesis_bib.pdf1.9 MBAdobe PDFVer/Abrir
G13070673_donacion_tesis_licencia.pdf
  Until 2050-01-01
119.09 kBAdobe PDFVer/Abrir Request a copy


Este registo está protegido por copyright original.



Este registo está protegido por Licença Creative Commons Creative Commons