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

Abstract

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/).