Browsing by Subject "Genetic algorithm"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Diseño de un método de solución para el flexible job shop con tiempos de alistamiento dependientes de la secuencia
    (Pontificia Universidad Javeriana Cali, 2020) Arciniegas Cortés, Valentina; Duque Otabo, Jhoan Arley; Londoño Barreto, Sara Lucía; Marín Carvajal, Juan Esteban; Morillo Torres, Daniel
    El Flexible Job Shop con Tiempos de Alistamiento Dependientes de la Secuencia (SDST-FJSP) es, al igual que el Job Shop Scheduling Problem (JSP), un problema de programación de trabajos. Sin embargo, el SDST-FJSP tiene en cuenta supuestos adicionales, tales como los tiempos de alistamiento dependientes de la secuencia y la multifuncionalidad de las máquinas, que permiten darle mayor cercanía a la realidad. Este problema ha sido catalogado como NP-hard, lo que ha despertado gran interés entre los investigadores, pues su alta complejidad hace que un método de solución exacta no sea una propuesta viable debido a la gran magnitud de los tiempos computacionales. Así pues, en este trabajo se proponen dos métodos para abordar el SDST-FJSP. El primero es un modelo matemático empleando MILP (Mixed-integer Linear Programming); si bien este es un método exacto, permite una comprensión más profunda del problema. El segundo es un algoritmo genético (AG) en el cual se empleó el método Tournament para el operador de cruce y el método Swap Mutation para el operador de mutación. Posteriormente, se realiza una comparación del desempeño obtenido por cada uno de los métodos, encontrando, como era de esperarse, mejores resultados en el AG para un mismo tiempo de ejecución.
  • Thumbnail Image
    Item
    Diseño de una metaheurística basada en el algoritmo genético para la solución del problema de intercambio de riñones en Estados Unidos
    (Pontificia Universidad Javeriana Cali, 2021) Ortega Bedoya, Juan Felipe; Otero Villamarín, Juan Felipe; Patiño Espinosa, Alejandro; Solano Ossa, José David; Morillo Torres, Daniel
    En los Estados Unidos, las complicaciones renales ocupan la octava posición como causa de muerte más frecuente, generando listas de espera que se acercan a las 100,000 personas, con solo alrededor de 25,000 accediendo a trasplantes renales. Ante la dificultad de suplir la demanda total de riñones necesarios, han surgido programas de intercambio renal que involucran donantes, receptores y altruistas, buscando establecer intercambios con cadenas o ciclos de longitud reducida por consideraciones logísticas. Frente al aumento de estos intercambios y programas tanto en Estados Unidos como en Europa, se ha desarrollado una metaheurística basada en el algoritmo genético. Esta estrategia ha sido concebida para abordar casos de prueba de mayor envergadura, superando las limitaciones de los modelos matemáticos convencionales. La aplicación de esta metaheurística proporciona una solución eficaz y escalable, mejorando la asignación de riñones en un contexto de alta demanda y limitaciones logísticas, ofreciendo respuestas a desafíos previamente considerados inabordables.
  • Thumbnail Image
    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, Daniel
    En 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.