División de Ciencias Básicas e Ingeniería
Permanent URI for this communityhttps://hdl.handle.net/11191/1
Browse
3 results
Search Results
- Programación de trabajos en el área de capitoneado en una empresa de colchones(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2021-05-11) Arzate Flores, DanielEn este trabajo, se presenta una variación de problema de flujo en taller, el cual se presenta en una fábrica de colchones, específicamente en un área conocida como capitoneado. El principal objetivo es programar los diferentes tipos de trabajos a las diferentes máquinas de acuerdo a las características inherentes del producto y su variación en los tiempos de producción, para así satisfacer la demanda diaria que tiene la empresa. Para darle solución a este problema se comienza diseñando un modelo matemático que satisfaga las diferentes restricciones del sistema de producción de la empresa y sus necesidades. Una vez diseñado el modelo matemático, se procede a realizar su implementación mediante el software de gurobi, el cual nos da una solución exacta del problema (BB). Además, se implementan 3 heurísticas, las cuales son el Algoritmo Genético (GA), Algoritmo cultural (CA) y Recocido Simulado (SA). Para medir la eficiencia de las técnicas utilizadas (BB-GA-CA-SA), se comparan con 10 instancias. Cada instancia representa la programación de un día de trabajo en la empresa de colchones que el supervisor asignó de acuerdo a su conocimiento y estrategias internas. De igual manera, una vez obtenidas las soluciones en GA-CA-SA se procedido a comparar con la solución exacta para medir qué tan buenas son y el tiempo utilizado. Este trabajo se divide en 5 capítulos, los cuales son: Introducción, conceptos básicos, descripción del problema, resultados, y conclusiones y trabajo futuro. Por último, se encuentran la bibliografía con la cual este trabajo se apoyó.
- Tres heurísticas basadas en inteligencia de partículas adaptadas al problema de asignación generalizada(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2018) Torres Cockrell, Gilberto SinuheEl presente trabajo desarrolla la adaptación de tres técnicas heurísticas pertenecientes a la rama de las metaheurísticas denominada inteligencia de partículas (IP) para su adaptación al problema de asignación generalizada (PAG). Las heurísticas adaptadas al problema de asignación generalizada son las siguientes: Algoritmo de luciérnagas (AL); Búsqueda Gravitacional (ABG) Método de composición musical (MCM) Se propone una codificación para representar una solución, que permita visualizar de una manera fácil las características de la misma. A diferencia de los algoritmos originales que comienzan con soluciones aleatorias, aquí se plantea una estrategia para generar soluciones de buena calidad aprovechando las características del problema lo cual genera una adaptación en los métodos antes mencionados, ya que se agregan dos parámetros los cuales permitirán generar soluciones por tres estrategias diferentes los cuales serán representados de la siguiente manera: Pg (% soluciones realizadas por un algoritmo glotón) y Pa (% de soluciones realizadas de manera aleatoria ) el restante de la población será generada por una relajación del problema con fijación de variables y generación aleatoria. Para la estrategia AL se realizaron las siguientes adaptaciones: la función objetivo no solo es representada por el valor del individuo, sino que en base a su aptitud a través de las reglas de manejo de restricciones de Coello 2002 [14]. La distancia entre dos individuos no es determinada solamente por la distancia euclidiana, sino que también contempla la distancia de Hamming la cual permite encontrar soluciones de buena calidad; se generaron seis versiones del algoritmo de luciérnagas las cuales se basan en 4 vecindarios diferentes. Para la estrategia ABG se realizaron las siguientes adaptaciones: la masa de inercia es calculada por las reglas de manejo de restricciones de Coello 2002 la cual genera una función de pesos; la función de distancia propuesta contempla al igual que en el AL la distancia euclidiana y la distancia de Hamming, para este algoritmo tanto la mejor como la peor solución el movimiento lo realiza con una búsqueda local; para el resto de las soluciones el movimiento lo realiza con base a las características de la estrategia orinal. Para la estrategia MCM se realizaron las siguientes adaptaciones: la función objetivo utiliza las reglas de manejo de restricciones de Coello 2002 para determinar la aptitud de la solución; la función de distancia propuesta contempla al igual que en las estrategias AL y ABG la distancia euclidiana y la distancia de Hamming. Se tomaron instancias de prueba utilizadas en Chu y Beasley 1997[13], las cuales se encuentran disponibles en Or-Library. Se realizó una calibración de parámetros para las estrategias adaptadas al PAG con la estrategia de búsqueda armónica (BA) para cien mil llamadas a la función objetivo. Se llevó a cabo una serie de experimentos y una comparación con base en algunas de las estrategias del estado del arte del problema. Los resultados obtenidos permiten afirmar que se obtienen soluciones de buena calidad.
- Problema de ruteo del autobús escolar con recolección mixta(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2015-04) Rojas Silva, EduardoEn este trabajo se presenta una variante del "Problema de ruteo del autobús escolar" (SBRP) clásico, en el cual se trata de minimizar la distancia que se recorre en cada ruta. Concretamente el problema propuesto es una variante del problema de ruteo del autobús escolar para estudiantes con necesidades especiales, en el cual se considera la existencia de dos tipos de de estudiantes, con atributos diferentes al momento de decidir en donde se van a recoger, a diferencia de otras variantes existentes en la literatura, se considera la parte de asignación de los estudiantes como parte del problema ya que se considera que este parámetro influye al momento en que se crean las rutas, aun cuando la complejidad del problema se vea incrementada. La idea principal de este trabajo consiste en explorar tanto los métodos heurísticos como los exactos, para poder obtener una solución a la variante propuesta, ya sea de forma exacta o aproximada. De tal manera que se pueda identificar en qué casos conviene usar uno de estos métodos. El problema se modela como un programa lineal entero mixto, el cual posteriormente se resuelve mediate el software glpk y se encuentran soluciones para instancias pequeñas, que se toman como base para compararlas con las encontradas con el método heurístico utilizado. Para la parte heurística se optó por utilizar una de las técnicas clásicas: Un algoritmo glotón aleatorizado y adaptativo (GRASP, del inglés Greedy Randomized Adaptive Search Procedures), dado que se parte de la formulación matemática previamente obtenida para la parte exacta, fácilmente se puede adaptar para la elaboración del GRASP. La técnica GRASP es una meta-heurística muy rápida que genera soluciones de alta calidad, la cual se divide en dos fases: una de construcción de soluciones, que utiliza para ello un algoritmo glotón aleatorizado una fase de mejora, la cual realiza una búsqueda local. Este proceso se repite varias veces y la mejor solución encontrada se toma como el resultado, lo que al final nos proporciona una solución que, si bien no garantiza que sea la óptima, sí es de buena calidad y se puede obtener en un tiempo mucho menor en comparación con el tiempo que tarda encontrar la solución con un método exacto, cuando éste es capaz de encontrar una. Finalmente nos enfocamos en la versión más simple y general del problema para dar un algoritmo de aproximación, el cual se basa en un algoritmo que originalmente se diseñó para resolver una variante del problema de ruteo vehícular.