El algoritmo de Coffman-Graham es un algoritmo para 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 de modo que cada nivel tenga un número de elementos que no exceda un ancho fijo límite W. Cuando W = 2 , utiliza el mínimo número posible de niveles distintos y, en general, utiliza como máximo 2 − 2/ W veces tantos niveles como sea necesario.
Lleva el nombre de Edward G. Coffman, Jr. y Ronald Graham , quienes lo publicaron en 1972 para una aplicación en la programación de talleres de trabajo . En esta aplicación, los elementos que se ordenarán son trabajos, el límite W es el número de trabajos que se pueden programar en cualquier momento y el orden parcial describe las relaciones de requisitos previos entre los trabajos. El objetivo es encontrar un cronograma que complete todos los trabajos en un tiempo total mínimo. Posteriormente, el mismo algoritmo también se ha utilizado en el dibujo de gráficos , como una forma de colocar los vértices de un gráfico dirigido en capas de anchos fijos de modo que la mayoría o todos los bordes se dirijan consistentemente hacia abajo.
Para un orden parcial dado por su reducción transitiva (relación de cobertura), el algoritmo de Coffman-Graham se puede implementar en tiempo lineal utilizando la estructura de datos de refinamiento de partición como subrutina. Si no se da la reducción transitiva, se necesita tiempo polinómico para construirla.
En la versión del problema de programación de talleres resuelto por el algoritmo de Coffman-Graham, se da un conjunto de n trabajos J 1 , J 2 , ..., J n , junto con un sistema de restricciones de precedencia Ji < J j Requiriendo que el trabajo Ji se complete antes de que comience el trabajo J j . Se supone que cada trabajo requiere una unidad de tiempo para completarse. La tarea de programación consiste en asignar cada uno de estos trabajos a intervalos de tiempo en un sistema de W procesadores idénticos, minimizando el tiempo de duración de la asignación (el tiempo desde el comienzo del primer trabajo hasta la finalización del trabajo final). De manera abstracta, las restricciones de precedencia definen un orden parcial en los trabajos, por lo que el problema puede reformularse como uno de asignación de los elementos de este orden parcial a niveles (intervalos 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] [2]
En el marco de dibujo de gráficos en capas descrito por Sugiyama, Tagawa y Toda (1981) [3] la entrada es un gráfico dirigido , y el dibujo de un gráfico se construye en varias etapas: [4] [5]
En este marco, la asignación de coordenadas y nuevamente implica agrupar elementos de un conjunto parcialmente ordenado (los vértices del gráfico, con el orden de accesibilidad 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. [4] Aunque existen enfoques alternativos al algoritmo de Coffman-Graham para el paso de capas, estas alternativas en general no pueden incorporar un límite en el ancho máximo de un nivel o dependen de procedimientos complejos de programación de enteros . [6]
De manera más abstracta, ambos problemas pueden formalizarse como un problema en el que la entrada consta de un conjunto parcialmente ordenado y un número entero W. El resultado deseado es una asignación de números de nivel entero 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 , de modo que como máximo a W elementos se les asigne el mismo número entre sí, y minimizando la diferencia entre los números asignados más pequeños y más grandes.
El algoritmo de Coffman-Graham realiza los siguientes pasos. [4]
Como demostraron originalmente Coffman y Graham (1972), su algoritmo calcula una asignación óptima para W = 2 ; es decir, para problemas de programación con trabajos de longitud unitaria en dos procesadores, o para problemas de dibujo de gráficos en capas con como máximo dos vértices por capa. [1] Un algoritmo estrechamente relacionado también encuentra la solución óptima para programar trabajos con diferentes duraciones, permitiendo adelantarse a los trabajos programados, en dos procesadores. [7] Para W > 2 , el algoritmo de Coffman-Graham utiliza una cantidad de niveles (o calcula un cronograma con un makepan) que está dentro de un factor de 2 − 2/ W del óptimo. [8] [9] Por ejemplo, para W = 3 , esto significa que utiliza como máximo 4/3 veces más niveles de los óptimos. Cuando el orden parcial de las restricciones de precedencia es un orden de intervalo , o pertenece a varias clases relacionadas de órdenes parciales, el algoritmo de Coffman-Graham encuentra una solución con el número mínimo de niveles independientemente de su límite de ancho. [10]
Además de encontrar programas con un makespan pequeño, el algoritmo de Coffman-Graham (modificado de la presentación aquí para que ordene topológicamente el gráfico inverso de G y coloque los vértices lo más temprano posible en lugar de lo más tarde posible) minimiza el tiempo total de flujo. de programas de dos procesadores, la suma de los tiempos de finalización de los trabajos individuales. Se puede utilizar un algoritmo relacionado para minimizar el tiempo total de flujo para una versión del problema en la que se permite la preferencia de trabajos. [11]
Coffman y Graham (1972) y Lenstra y Rinnooy Kan (1978) [12] establecen que la complejidad temporal del algoritmo de Coffman-Graham, en un orden parcial de n elementos, es O ( n 2 ) . Sin embargo, este análisis omite el tiempo para construir la reducción transitiva, que no se sabe que sea posible dentro de este límite. Sethi (1976) muestra cómo implementar la etapa de ordenamiento topológico del algoritmo en tiempo lineal , basándose en la idea de refinamiento de partición . [13] Sethi también muestra cómo implementar la etapa de asignación de niveles del algoritmo de manera eficiente mediante el uso de una estructura de datos de conjuntos separados . En particular, con una versión de esta estructura publicada posteriormente por Gabow y Tarjan (1985), esta etapa también requiere tiempo lineal. [14]