Por favor, use este identificador para citar o enlazar este ítem:
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 |
| Fecha de publicación : | 2021-05-01 |
| Editorial : | Tecnológico Nacional de México |
| metadata.dc.publisher.tecnm: | Instituto Tecnológico de Ciudad Madero |
| Descripción : | 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 en las colecciones: | Maestría en Ciencias de la Computación |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| G13070673_donacion_tesis_bib.pdf | 1.9 MB | Adobe PDF | Visualizar/Abrir | |
| G13070673_donacion_tesis_licencia.pdf Until 2050-01-01 | 119.09 kB | Adobe PDF | Visualizar/Abrir Request a copy |
Este ítem está protegido por copyright original |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons
