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 tal que cada nivel tiene un número de elementos que no excede un límite de ancho fijo W . Cuando W = 2 , utiliza el número mínimo posible de niveles distintos y, en general, utiliza como máximo 2 − 2/ W veces más niveles que sean necesarios.
Recibe su nombre en honor a 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 deben ordenar 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 prerrequisitos entre los trabajos. El objetivo es encontrar una programación que complete todos los trabajos en el 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 de manera consistente hacia abajo.
Para un ordenamiento 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 un tiempo polinomial para construirla.
En la versión del problema de programación de talleres de trabajo resuelta por el algoritmo de Coffman–Graham, se proporciona un conjunto de n trabajos J 1 , J 2 , ..., J n , junto con un sistema de restricciones de precedencia J i < J j que requieren que el trabajo J i se complete antes de que comience el trabajo J j . Se supone que cada trabajo tarda una unidad de tiempo en completarse. La tarea de programación es asignar cada uno de estos trabajos a intervalos de tiempo en un sistema de W procesadores idénticos, minimizando el tiempo transcurrido 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 se puede reformular 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 de Coffman y Graham para desarrollar su algoritmo. [1] [2]
En el marco de dibujo de gráficos en capas delineado 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 la coordenada y implica nuevamente agrupar elementos de un conjunto parcialmente ordenado (los vértices del gráfico, con el orden de alcanzabilidad 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 son capaces de incorporar un límite en el ancho máximo de un nivel o dependen de procedimientos complejos de programación entera . [6]
De manera más abstracta, ambos problemas se pueden formalizar como un problema en el que la entrada consiste en un conjunto parcialmente ordenado y un entero W. La salida deseada es una asignación de números de nivel entero a los elementos del conjunto parcialmente ordenado de manera 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 manera que a lo sumo W elementos se les asigna el mismo número entre sí, y se minimiza la diferencia entre los números asignados más pequeños y más grandes.
El algoritmo Coffman-Graham realiza los siguientes pasos. [4]
Como Coffman y Graham (1972) demostraron originalmente, 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 la programación de trabajos con longitudes variables, lo que permite la prelación de trabajos programados, en dos procesadores. [7] Para W > 2 , el algoritmo de Coffman–Graham usa un número de niveles (o calcula una programación con un makespan) que está dentro de un factor de 2 − 2/ W del óptimo. [8] [9] Por ejemplo, para W = 3 , esto significa que usa como máximo 4/3 veces más niveles que 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 planificaciones con tiempos de ejecución pequeños, el algoritmo 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 planificaciones 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 preemisión de trabajos. [11]
Coffman & Graham (1972) y Lenstra & Rinnooy Kan (1978) [12] establecen que la complejidad temporal del algoritmo 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 nivel del algoritmo de manera eficiente mediante el uso de una estructura de datos de conjunto disjunto . En particular, con una versión de esta estructura publicada posteriormente por Gabow & Tarjan (1985), esta etapa también requiere tiempo lineal. [14]