Algoritmo de Coffman-Graham
En programación de taller y trazado de grafos, el algoritmo Coffman-Graham es un proceso de cálculo, llamado así por Edward G. Coffman, Jr. y Ronald Graham, cuyo fin es organizar los elementos de un conjunto parcialmente ordenado en una secuencia de niveles. El algoritmo elige una disposición tal que un elemento que viene después de otro en el orden se asigna a un nivel inferior, y tal que cada nivel W contiene elementos que no superan una amplitud dada. Cuando W = 2 se utiliza la cantidad mínima posible de niveles distintos, y, en general, se utilizan como máximo 2 − 2/W veces tantos niveles como sea necesario.
From Wikipedia, the free encyclopedia
En programación de taller y trazado de grafos, el algoritmo Coffman-Graham es un proceso de cálculo, llamado así por Edward G. Coffman, Jr. y Ronald Graham, cuyo fin es organizar los elementos de un conjunto parcialmente ordenado en una secuencia de niveles. El algoritmo elige una disposición tal que un elemento que viene después de otro en el orden se asigna a un nivel inferior, y tal que cada nivel W contiene elementos que no superan una amplitud dada. Cuando W = 2 se utiliza la cantidad mínima posible de niveles distintos,[1] y, en general, se utilizan como máximo 2 − 2/W veces tantos niveles como sea necesario.[2][3]
En la versión del problema de programación de un taller de trabajo resuelto por el algoritmo Coffman-Graham, se asigna un conjunto de trabajos n J1, J2, ..., Jn, junto con un sistema de restricciones de precedencia Ji < Jj que implican que el trabajo Ji se complete antes de que comience el trabajo Jj. Se supone que cada tarea toma un tiempo unitario para completarse. La tarea de programación es asignar cada uno de estos trabajos a intervalos de tiempo en un sistema de procesadores idénticos W, minimizando el plazo total de la asignación (el tiempo desde el inicio del primer trabajo hasta la finalización del trabajo final). En abstracto, las restricciones de precedencia definen un orden parcial en los trabajos, por lo que el problema puede reformularse como uno de asignar los elementos de este orden parcial a niveles (franjas de tiempo) de tal manera que cada intervalo de tiempo tenga como máximo tantos trabajos como procesadores (como máximo W elementos por nivel), respetando las restricciones de precedencia. Esta aplicación fue la motivación original para que Coffman y Graham desarrollaran su algoritmo.[1][4]
En el marco del trazado de grafos por capas descrito por Sugiyama, Tagawa y Toda (1981),[5] la entrada es un grafo dirigido, y el dibujo de un gráfico se construye en varias etapas:[6][7]
- Se elige un conjunto de arcos retroalimentados y los bordes de este conjunto se invierten para convertir la entrada en un grafo acíclico dirigido.
- Los vértices del gráfico reciben coordenadas y enteras de tal manera que, para cada borde, el vértice inicial del contorno tiene una coordenada más alta que el vértice final, con como máximo W vértices que comparten la misma coordenada y.
- Se introducen dígitos arbitrarios auxiliares dentro de cada contorno para que los bordes subdivididos conecten pares de vértices que estén en niveles adyacentes del dibujo.
- Dentro de cada grupo de vértices con la misma coordenada y, los vértices son permutados para minimizar el número de cruces en el dibujo resultante, y los vértices tienen asignadas coordenadas x consistentemente con esta permutación.
- Los vértices y bordes del gráfico se dibujan con las coordenadas asignadas.
En este marco, la asignación de la coordenada y implica nuevamente agrupar elementos de un conjunto parcialmente ordenado (los vértices del gráfico, con el orden alcanzable en el conjunto de vértices) en capas (conjuntos de vértices con la misma coordenada y), que es el problema resuelto por el algoritmo de Coffman-Graham.[6] Aunque existen enfoques alternativos al algoritmo de Coffman-Graham para el paso de estratificación, estas alternativas en general no son capaces de incorporar un límite en el ancho máximo de un nivel o dependen de complejos Procedimientos programación en enteros.[8]
De manera más abstracta, ambos problemas pueden formalizarse como un problema en el que la entrada consiste en un conjunto parcialmente ordenado y un entero W. El resultado deseado es una asignación de números enteros a los elementos del conjunto parcialmente ordenado de modo que, si x < y es un par ordenado de elementos relacionados del orden parcial, el número asignado a x es menor que el número asignado a y, tal como que como mucho los W elementos tienen asignados el mismo número uno que otro, y minimizan la diferencia entre el número asignado más pequeño y el más grande.
