Advanced search


Knowledge area




Filter by:

Publication type

Authors

Issue Years

Publishers

Origin repository

Access Level

Language

Subject

Select the topics of your interest and receive the hottest publications in your email

2 results, page 1 of 1

Resolución de problemas de sistemas de producción cíclica aplicando el índice cromático circular

José de Jesús Rodríguez Martínez (2016)

70 páginas. Maestría en Optimización.

En una gráfica G, el concepto de número cromático circular Xc(G) fue introducido por Vince en 1988. Este invariante es una generalización del número cromático X(G) de una gráfica y provee de una información más refinada de las características de la asignación de colores a los vértices de G. Este trabajo trata sobre la coloración de aristas de una gráfica, mediante el concepto de índice cromático circular X’c(G) como un refinamiento del índice cromático X’(G). Los invariantes Xc(G) y X’c(G) están relacionados, dado que cualquier coloración de las aristas de G es equivalente a colorear los vértices de la gráfica de líneas L(G). En el capítulo 1 se presenta información detallada sobre conceptos fundamentales de este trabajo. El índice cromático circular permite ayudar a resolver un tipo de problemas de asignación que se plantean en sistemas de producción cíclica. Estos problemas se pueden modelar en una gráfica bipartita donde el peso de la arista e = (u; v) corresponde al tiempo de ejecución de la tarea u realizada en la máquina v. En el capítulo 2 se presentan dos conceptos equivalentes: una r-coloración cromática circular y una (k; d)-coloración de las aristas de una gráfica. Ambos conceptos se refieren el índice cromático circular X’c(G). Asimismo, en este capítulo: (i) se comparan las cotas de X’c(G) con respecto a otros parámetros de la gráfica; (ii) se obtiene el X’c(G) para gráficas que tienen una función de peso asociada a sus aristas; y, (iii) finalmente, se enfatiza que es un problema NP-duro el cálculo del valor de X’c(G) para una gráfica dada G. En el capítulo 3 se presenta un resumen de familias de gráficas para las cuales se ha logrado determinar el valor de X’c(G). Este conjunto está constituido por: (i) gráficas de ruedas multieje Wp;q; (ii) gráficas Np; (iii) gráficas snarks, en donde destacan: Petersen, Descartes, Szekeres, Flores, Blanu²a, Blanu²a tipo 1 y Goldberg. Se extienden la últimas dos familias mediante el pegado de ciclos Cs+1 por trayectorias de longitud 1 y 2, dando lugar a nuevas familias, de las cuales se conoce su índice cromático circular. En el capítulo 4 se presenta una aplicación del concepto de coloración circular para modelar un sistema de producción cíclica conocido como open shop scheduling. En este tipo de problemas se tienen n trabajos que deben ser procesados en m máquinas. Cada trabajo consiste de un conjunto de tareas, las cuales tienen un tiempo de procesamiento en cada máquina en la que se puede realizar. El problema se modela mediante una gráfica bipartita (G), donde se tienen dos conjuntos de vértices, el conjunto de trabajos Ji y el conjunto de máquinas Mj . Una arista corresponde a una tarea asociada al trabajo i, que debe ser procesada en la máquina j, la cual se efectúa sin interrupciones. El peso asociado a la arista ij es el tiempo necesario para procesar la tarea ij. El objetivo es encontrar la mínima r-coloración circular por aristas de (G), dado que ésta es equivalente a encontrar la asignación tal que el tiempo necesario para procesar todas las tareas sea el mínimo. Asimismo, en este capítulo se presenta la implementación de tres algoritmos que aproximan el ciclo más pequeño para ejecutar todas las tareas, los cuales de describen a continuación: (i) el primero es una combinación de un problema de programación lineal con la heurística conocida como búsqueda en vecindades variables; y, (ii) los siguientes dos son una combinación de la resolución de un conjunto de problemas de programación lineal con algoritmos genéticos. Estas técnicas son algunas formas de resolver la asignación a sistemas de producción cíclica; las instancias que se utilizan en este trabajo son tomadas de E. Taillard (ver página http://mistic.heig-vd.ch/).

Master thesis

Graph coloring. Teoría de grafos. QA166.247 CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA MATEMÁTICAS CIENCIA DE LOS ORDENADORES TERMINALES, DISPOSITIVOS GRÁFICOS Y TRAZADORES

Anticoloraciones en gráficas

Luis Eduardo Urban Rivero (2018)

114 páginas. Doctorado en Optimización.

Uno de los problemas más conocidos y estudiados de la teoría de gráficas es el problema de coloración. Un caso especial del problema de coloración supuso una de las preguntas matemáticas más controvertidas de la humanidad, conocido ahora como el teorema de los cuatro colores. Controvertida por dos razones, la dificultad para encontrar su respuesta y porque en su demostración se emplearon por primera vez computadoras. En el mismo sentido de los problemas de coloración, Berge propuso en los 70’s un problema que 30 años después provocaría la creación de una teoría bajo el nombre del problema de anticoloración. El problema de Berge versa sobre lo siguiente. Dado un tablero de ajedrez de n_n, b reinas negras y w reinas blancas. ¿Es posible colocar las reinas negras y blancas en el tablero sin que se ataquen mutuamente? En las anticoloraciones se le pide a la coloración la condición opuesta a la coloración clásica, es decir si dos vértices son adyacentes estos deben tener el mismo color. Para que esto tenga sentido se deben agregar algunas condiciones al problema, como la existencia de vértices incoloros y que las cardinalidades de las clases de color sean fijas. En esta tesis se presenta la demostración de una conjetura que deriva del problema de Berge con caballos en lugar de reinas. Además de que se proponen modelos de programación lineal entera, no lineal entera y multiobjetivo para poder resolver problemas de anticoloración con dos colores por medio de algoritmos exactos. Además de lo anterior se presenta una mejora de las heurísticas parados colores y se propone una nueva heurística basada en algoritmos genéticos. Por último, se dan las extensiones necesarias para trabajar el problema de anticoloración con más de dos colores, tanto con algoritmos exactos como con métodos heurísticos.

Doctoral thesis

Graph coloring. Teoría de grafos. Optimización matemática. QA166.247 CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA MATEMÁTICAS INVESTIGACIÓN OPERATIVA PROGRAMACIÓN LINEAL