Maestría en Ingeniería
Permanent URI for this collection
Browse
Browsing Maestría en Ingeniería by Subject "Algoritmo genético"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Diseño de una mateheurística para resolver el Flexible Job Shop Problem with sequence-dependent setup times(Pontificia Universidad Javeriana Cali, 2026) Duque Otabo, Jhoan Arley; Morillo Torres, DanielEl Flexible Job Shop Scheduling Problem (FJSSP) es un referente clásico de la optimización combinatoria por su capacidad para modelar entornos industriales con máquinas o recursos polivalentes y complejidad en la secuenciación de las actividades operacionales. En este trabajo se aborda una variante del FJSSP que incorpora Sequence-Dependent Setup Times (SDST), una característica fundamental para representar de manera más realista los procesos productivos, pero que incrementa significativamente la complejidad computacional del problema. Para resolver esta variante, se propone una Mateheurística que integra un Algoritmo Genético (GA), encargado de la búsqueda global del espacio de soluciones, con un modelo de Programación Lineal Entera Mixta (MILP) incorporado como operador de diversidad. Este operador resuelve subproblemas de asignación y secuenciación mediante una estrategia de división en lotes de operaciones, permitiendo mejorar la calidad de las soluciones generadas por el GA. La eficacia del enfoque se evalúa mediante dos estrategias de integración GA--MILP. La primera incorpora un operador MILP independiente, en el que cada lote se optimiza de forma aislada. La segunda utiliza un operador MILP dependiente, que incorpora restricciones derivadas de los lotes previamente optimizados para orientar la búsqueda del GA hacia regiones más prometedoras del espacio de soluciones. Los resultados computacionales obtenidos sobre un conjunto de 276 instancias adaptadas muestran que la Mateheurística propuesta obtiene mejor desempeño dentro de las alternativas evaluadas y bajo las condiciones experimentales definidas al modelo MILP como al GA ejecutados de forma independiente, especialmente en instancias de mayor complejidad, caracterizadas por altos niveles de flexibilidad.Item Solución de un sistema open shop en un taller de mecánica automotriz mediante el diseño de un algoritmo genético(Pontificia Universidad Javeriana Cali, 2020) Delgado Moore, Luis Fernando; Morillo Torres, DanielEl área de programación de tareas (también conocida como scheduling) se encarga de planificar la mejor asignación de los recursos dentro de un sistema productivo que permita la consecución de un conjunto de tareas; logrando eficiencia y efectividad en tal asignación. El incentivo de estudiar problemas relacionados con el scheduling nace de la necesidad de obtener soluciones factibles de alta calidad de un grupo de tareas y recursos (como máquinas) que requieren ser secuenciados de forma que se optimicen los recursos productivos y obtener así un beneficio económico. El presente estudio buscar solucionar uno de los problemas más relevantes de esta área: el Open Shop, mediante el desarrollo de un algoritmo genético. Un problema Open Shop se define como un conjunto de m máquinas las cuales deben procesar un conjunto de n tareas que tienen un tiempo de procesamiento específico; cada tarea debe ser procesado por todas las máquinas (o un subconjunto de ellas). Adicionalmente, solo se puede ejecutar un solo tarea a la vez, y cada máquina solo puede procesar una tarea simultáneamente. Inicialmente, se desarrolló un Modelo Matemático que generó soluciones factibles obtenidas mediante el software de optimización AMPL, quien resultó eficiente solo para instancias inferiores a 5 máquinas y 5 tareas. Con el ánimo de mejorar amplitud en resultados y aplicaciones, se desarrolló un Algoritmo Genético el cual encontró soluciones para instancias de hasta 20 máquinas y 20 tareas, las que a su vez fueron evaluadas con las bases de datos más usadas en literatura: las instancias de Taillard (1993), Brucker (2007) y Guéret & Prins (1999) encontrando desviaciones promedio inferiores al 9% en tamaños de hasta 20 máquinas x 20 tareas. Finalmente, el algoritmo mencionado fue aplicado a un caso real de un taller de mecánica automotriz en el que se evidenció que asignando de una mejor manera las secuencias de operaciones y las máquinas, el tiempo de ejecución (makespan) mejoraría sustancialmente permitiendo incrementar la eficiencia de la operación cuantificada con los siguientes indicadores: Ejecución total de órdenes de trabajo diarias (100%), 14% de tiempo disponible y 86% de ocupación.Item Solución robusta al problema de programación de actividades con recursos restringidos y duraciones estocásticas(Pontificia Universidad Javeriana Cali, 2025) Gutiérrez Padilla, María Victoria; Morillo Torres, DanielEn esta investigación se aborda el Uncertain Resource-Constrained Project Scheduling Problem (URCPSP); su versión determinista (el RCPSP) es considerada como el problema NP-hard más importante del área de programación. El RCPSP tiene como objetivo secuenciar las actividades que conforman un proyecto, con el fin de minimizar su tiempo de ejecución, teniendo en cuenta las duraciones de las actividades, sus relaciones de precedencia y el uso de recursos escasos. El URCPSP considera un entorno más realista, donde las duraciones de las actividades pueden variar debido a improvistos. En la literatura se han definido diversos enfoques para su solución, entre ellos destaca la programación robusta, que consiste en encontrar una programación base que sea capaz de absorber posibles perturbaciones mediante una amortiguación temporal. Para conocer qué tan robusta es una solución se han desarrollado diferentes medidas de robustez. Sin embargo, la eficacia de estas medidas es limitada, y ninguna considera simultáneamente la estructura y el estado operativo del problema. Así, la contribución de este proyecto es triple: a) se define una nueva medida de robustez mediante la adaptación de este concepto en sistemas eléctricos, teniendo en cuenta una función lineal por partes para cada actividad que evalúa la importancia de las holguras, considerando el grado en el que se cumple la holgura esperada de cada actividad; b) se diseña una metodología general de solución para el URCPSP que considera el componente estocástico de las duraciones de las actividades y la nueva medida de robustez, e incluye la propuesta de una metaheurística evolutiva; y c) se adapta una librería estándar de casos de prueba incluyendo las duraciones estocásticas basados en perfiles realistas de actividades bajo riesgo. Los resultados obtenidos validan la eficiencia de la propuesta y muestran cómo la distribución inteligente de las holguras permite alcanzar una mayor robustez.