Zaloamati
Permanent URI for this communityhttps://hdl.handle.net/11191/38
Browse
2 results
Search Results
- Modelos combinatorios en ensamblamiento genético(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2018-01) Garcia Garcia, Lidia AngelicaLa presente tesis se estructura como sigue. En el capítulo 2, se revisan los conceptos matemáticos fundamentales empleados a lo largo de este trabajo. Las secciones 2.3 y 2.4 presentan respectivamente las definiciones de matroide binario y matroide. En la sección 3.1 del capítulo 3 se da una introducción al problema del reordenamiento cromosómico. La subsección 3.1.3 describe la estructura de ciertos organismos unicelulares llamados ciliados que son empleados como modelo en la genómica comparativa. Recientes investigaciones en teoría de inversiones han propuesto la aplicación de las tres operaciones irreversibles con las que estos organismos ordenan su ADN (definidas en la subsección 3.1.4) en la deducción de potenciales relaciones evolutivas relativas al fenómeno del reordenamiento cromósomico [61, 63]. En la sección 3.2 se presentan las definiciones de inversión, distancia de inversión, inversiones orientadas e inversiones no orientadas en términos de la permutación signada con la que se representa el orden y la orientación de los genes en un cromosoma lineal. La gráfica de punto de rompimiento asociada a dicha permutación es definida en la sección 3.3. La subsección 3.3.2 describe un modelo de programación lineal entera para el problema de la distancia de inversión. El concepto de gráfica de intersección está dado en la sección 3.4. La matriz de adyacencia de esta gráfica se presenta en la subsección 3.4.3. En la subsección 3.4.4 se define la inversión de corte de las subsecciones 3.2.5 y 3.3.4 en términos de la operación sobre matrices antisimétricas conocida como complemento local modificado. Los paseos Eulerianos en la multigráfica 4-regular conexa asociada a una permutación signada se estudian en la sección 3.5. En la subsección 3.5.3 se da la definición de la multigráfica codificada (G,Ƭ ) asociada a un sistema de isotropía S con gráfica fundamental H2. Las transformaciones aplicables sobre un paseo Euleriano en una multigráfica 4-regular, descritas por Kotzig y posteriormente extendidas por Bouchet, se definen en la sección 3.6. El concepto de gráficas fundamentales es presentado en la sección 3.7. La sección 3.8 define el sistema de isotropía con gráfica fundamental descrita en la subsección 3.7.1 y su relación con los matroides. El capítulo 4 presenta la aplicación de los conceptos expuestos en los contextos del ordenamiento por inversiones y del ensamblamiento genético enciliados. En la sección 4.1 las inversiones en un cromosoma lineal son descritas en términos del matroide binario normal. La definición de la distancia de inversión en el caso en que sea una permutación signada sin obstáculos se muestra en la ecuación (52) de esta sección. La relación entre el complemento local modificado y las transformaciones sobre paseos Eulerianos en multigráficas 4 regulares es presentada en la sección 4.2 mientras que la fórmula exacta para la distancia de inversión está dada por la ecuación (53) de la sección 4.3. Finalmente, la descripción de como el modelo aplicado se generaliza para genes y cromosomas circulares se da en la sección 4.4.
- Estudio del problema de programación de la producción en un ambiente multi-propósito flexible con división de lotes(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2018) Fernandez Romero, Miguel AngelEl problema de programación de tareas conocido como programación de la producción en un ambiente multi-propósito flexible con división de lotes es una variante del problema de tipo programación de la producción, en la cual los lotes pueden dividirse en sublotes de diferentes tamaños y asignarse a diferentes máquinas, de tal forma que se disminuyen los tiempos muertos y el tiempo total de procesamiento. El objetivo consiste en minimizar la amplitud de proceso, es decir, la fecha de terminación de la última operación en la última máquina. Debido a la complejidad computacional de este problema, normalmente se recurre a técnicas heurísticas para poder resolverlo. En este trabajo, se propone un algoritmo que combina estrategias de Búsqueda Tabú, con vecindades y técnicas de división de lotes basados en la ruta crítica de cada solución generada. Para determinar la eficiencia del algoritmo propuesto, se adaptaron las instancias edata, rdata y vdata de Hurink. Debido a que este problema casi no se ha reportado en la literatura, no fue posible encontrar soluciones, que sirvieran como punto de comparación, para las instancias antes mencionadas. Por lo tanto, se emplearon dos estrategias para poder evaluar el desempeño del algoritmo propuesto. Primero, se resolvieron las instancias propuestas hasta donde fue posible, con el solver Gurobi. Segundo, se emplearon los mejores resultados reportados, sin división de lotes, para este mismo conjunto de instancias. Los experimentos realizados muestran que el algoritmo propuesto es capaz de generar buenas soluciones en tiempos de cómputo aceptables. Por otro lado, se evidencian los beneficios de la estrategia combinando flexibilidad y división de lotes, introducida en este trabajo.