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,[1]​ y, en general, se utilizan como máximo 2 − 2/W veces tantos niveles como sea necesario.[2]​[3]​

Declaración de problemas y aplicaciones

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 J₁, J₂, ..., J_n, junto con un sistema de restricciones de precedencia J_i < J_j que implican que el trabajo J_i se complete antes de que comience el trabajo J_j. 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]​

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.

El algoritmo

El algoritmo de Coffman-Graham realiza los siguientes pasos:[6]​

1. Representar el orden parcial por su reducción transitiva o relación de cobertura, un gráfico acíclico dirigido G que tiene un borde desde x a y siempre que x < y y no exista ningún tercer elemento z del orden parcial para el cual x < z < y . En las aplicaciones de dibujo gráfico del algoritmo Coffman-Graham, el gráfico acíclico dirigido resultante puede no ser el mismo que el gráfico dibujado, y en las aplicaciones de programación puede no tener una ventaja para cada restricción de precedencia de la entrada: en ambos casos, la reducción transitiva elimina los bordes redundantes que no son necesarios para definir el orden parcial.
2. Construye un Ordenamiento topológico de G en el que los vértices son ordenados lexicográficamente por el conjunto de posiciones de sus vecinos entrantes. Para hacerlo, agrega los vértices uno por uno al orden, en cada paso elige un vértice v para agregar de modo que los vecinos entrantes de v sean todos ya parte del ordenamiento parcial, y de tal manera que el vecino entrante agregado más recientemente v es anterior al vecino entrante agregado más recientemente de cualquier otro vértice que podría agregarse en lugar de v. Si dos vértices tienen el mismo vecino entrante agregado más recientemente, el algoritmo rompe el empate a favor de aquel cuyo segundo vecino entrante agregado más recientemente es anterior, etc.
3. Asígnesen los vértices de G a niveles en el reverso del orden topológico construido en el paso anterior. Para cada vértice v, agréguese v a un nivel que sea al menos un paso más alto que el nivel más alto de cualquier vecino saliente de v, que aún no tenga elementos W asignados, y que sea lo más bajo posible sujeto a estas dos restricciones

Análisis

Como Coffman y Graham (1972) probó originalmente, su algoritmo calcula una asignación óptima para W = 2; es decir, para programar problemas con trabajos de longitud unitaria en dos procesadores, o para problemas de dibujo de gráficos en capas con un máximo de dos vértices por capa.[1]​ Un algoritmo estrechamente relacionado también encuentra la solución óptima para programar trabajos con longitudes variables, lo que permite la aceleración de trabajos programados, en dos procesadores.[9]​ Para W > 2, el algoritmo de Coffman-Graham usa una cantidad de niveles (o calcula un programa con un intervalo de trabajo) que está dentro de un factor de 2 − 2/W del óptimo.[2]​[3]​ Por ejemplo, para W = 3, esto significa que utiliza a lo sumo 4/3 veces tantos niveles como sea óptimo. Cuando el orden parcial de las restricciones de precedencia es un orden de intervalos, 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 ancho de banda.[10]​

Además de encontrar horarios con intervalos de trabajo pequeños, el algoritmo de Coffman-Graham (modificado a partir de la aquí mostrada para que ordene topológicamente el grafo inverso de G y coloque los vértices lo más pronto posible en lugar de lo más tarde posible) minimiza el flujo de tiempo total de dos programas de procesador y la suma de los tiempos de finalización de los trabajos individuales. Se puede usar un algoritmo relacionado para minimizar el tiempo de flujo total para una versión del problema en la que se permite alterar la precedencia de los trabajos.[11]​

Coffman y Graham (1972) y Lenstra y Rinnooy Kan (1978)[12]​ indican que la complejidad de tiempo del algoritmo de Coffman-Graham, en un orden parcial de elementos n, 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, basado 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 para conjuntos disjuntos. En particular, con una versión de esta estructura publicada posteriormente por Gabow y Tarjan (1985), esta etapa también requiere tiempo lineal.[14]​

Referencias

1. Coffman, E. G., Jr.; Graham, R. L. (1972), «Optimal scheduling for two-processor systems», Acta Informatica 1: 200-213, MR 0334913, doi:10.1007/bf00288685 ..
2. Lam, Shui; Sethi, Ravi (1977), «Worst case analysis of two scheduling algorithms», SIAM Journal on Computing 6 (3): 518-536, MR 0496614, doi:10.1137/0206037 ..
3. Braschi, Bertrand; Trystram, Denis (1994), «A new insight into the Coffman–Graham algorithm», SIAM Journal on Computing 23 (3): 662-669, MR 1274650, doi:10.1137/S0097539790181889 ..
4. Leung, Joseph Y.-T. (2004), «Some basic scheduling algorithms», Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, ISBN 978-1-58488-397-5 ..
5. Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), «Methods for visual understanding of hierarchical system structures», IEEE Transactions on Systems, Man, and Cybernetics, SMC-11 (2): 109-125, MR 0611436, doi:10.1109/TSMC.1981.4308636 ..
6. di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1999), «Chapter 9: Layered drawings of digraphs», Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 265-302 ..
7. Bastert, Oliver; Matuszewski, Christian (2001), «Layered drawings of digraphs», en Kaufmann, Michael; Wagner, Dorothea, eds., Drawing Graphs: Methods and Models, Lecture Notes in Computer Science 2025, Springer-Verlag, pp. 87-120, doi:10.1007/3-540-44969-8_5 .. Bastert and Matuszewski also include a description of the Coffman–Graham algorithm; however, they omit the transitive reduction stage of the algorithm.
8. Healy, Patrick; Nikolov, Nikola S. (2002), «How to layer a directed acyclic graph», Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001, Revised Papers, Lecture Notes in Computer Science 2265, Springer-Verlag, pp. 16-30, MR 1962416, doi:10.1007/3-540-45848-4_2 ..
9. Muntz, R. R.; Coffman, E. G. (1969), «Optimal preemptive scheduling on two-processor systems», IEEE Transactions on Computers 18: 1014-1020, doi:10.1109/T-C.1969.222573 ..
10. Chardon, Marc; Moukrim, Aziz (2005), «The Coffman-Graham algorithm optimally solves UET task systems with overinterval orders», SIAM Journal on Discrete Mathematics 19 (1): 109-121, MR 2178187, doi:10.1137/S0895480101394999 ..
11. Coffman, E. G., Jr.; Sethuraman, J.; Timkovsky, V. G. (2003), «Ideal preemptive schedules on two processors», Acta Informatica 39 (8): 597-612, MR 1996238, doi:10.1007/s00236-003-0119-6 ..
12. Lenstra, J. K.; Rinnooy Kan, A. H. G. (1978), «Complexity of scheduling under precedence constraints», Operations Research 26 (1): 22-35, JSTOR 169889, MR 0462553, doi:10.1287/opre.26.1.22 ..
13. Sethi, Ravi (1976), «Scheduling graphs on two processors», SIAM Journal on Computing 5 (1): 73-82, MR 0398156, doi:10.1137/0205005 ..
14. Gabow, Harold N.; Tarjan, Robert Endre (1985), «A linear-time algorithm for a special case of disjoint set union», Journal of Computer and System Sciences 30 (2): 209-221, MR 801823, doi:10.1016/0022-0000(85)90014-5 ..

• Datos: Q5141033