Algoritmo para transformar un DAG de flujo de trabajo en una asignación de recursos paralela?

Question

Supongo que tengo un gráfico donde los nodos son cargas de trabajo de varios tipos y los bordes son dependencias entre las cargas de trabajo. (Esto es un DAG ya que las dependencias cíclicas no deben existir.)

También tengo un conjunto de agentes múltiples que pueden realizar el trabajo.

Algunas variedades de carga de trabajo se pueden dar a cualquier agente, otras se deben administrar a un agente específico y otras se deben administrar a un agente de un grupo particular de agentes.

¿Cómo puedo asignar cargas de trabajo de tal manera que:

• Sin carga de trabajo se le da a un agente hasta que se completen todas sus cargas de trabajo de bloqueo

• el menor tiempo posible se requiere para completar la gráfica carga total de trabajo . (Tenga en cuenta que minimizar el tiempo de inactividad del agente generalmente es bueno, pero no un requisito fundamental; puede haber escenarios en los que un agente en particular permanezca inactivo por más tiempo, pero el tiempo total para completar todos los trabajos en todos los agentes es mínimo).

Las cargas de trabajo tienen estimaciones de duración, pero asuma por simplicidad que cada carga de trabajo tarda el mismo tiempo en computarse. (Simplemente descomponga cada carga de trabajo en múltiples cargas de trabajo dependientes en serie hasta que cada carga de trabajo sea efectivamente una operación de tiempo constante.)

Conozco la clasificación topológica de DAG, pero eso produce un ordenamiento de nodos único y en serie. Tengo varios agentes operando en paralelo, y las relaciones son tales que se pueden realizar optimizaciones de tiempo potencialmente grandes mediante el reordenamiento no obvio de las tareas.

El resultado de esto se representaría mejor como un diagrama de Gantt con una duración total mínima. De hecho, si piensas en el problema como la asignación de tickets de errores en un hito a los ingenieros de un equipo, con el objetivo de lograr el hito lo antes posible, entonces entiendes la idea. (No ... no me digas que importe mi gráfico en MS Project y luego lo exportes :) - ¡Me interesa el algoritmo que lo respalda!)

Punteros a algoritmos bien conocidos, bibliotecas de software o cuestiones generales y principios son muy apreciados!

Answer 1

A menos que tenga un número infinito de agentes para que un agente compatible esté disponible tan pronto como se realicen todos los predecesores de una tarea, este es un problema NP-difícil.

< enchufe descarado>

Un problema muy similar hay en mi libro "Algorithms For Interviews"

</enchufe descarado>

Aquí es el problema y la solución del libro:

Tenemos que programar N conferencias en M clases. Algunas de esas conferencias son prerrequisitos para otros. ¿Cómo elegirías cuándo y dónde celebrar las conferencias para finalizar todas las conferencias lo antes posible?

Solución: Se nos da un conjunto de N conferencias y aulas de duración de la unidad M. Las conferencias se pueden llevar a cabo simultáneamente, siempre y cuando no haya dos clases en el mismo aula al mismo tiempo y se cumplan todas las restricciones de precedencia. Se sabe que el problema de programar estas clases para minimizar el tiempo necesario para finalizar es NP-completo. Este problema se modela naturalmente mediante gráficos. Modelamos conferencias como vértices, con un borde desde el vértice u hasta el vértice v si u es un requisito previo para v. Claramente, el gráfico debe ser acíclico para que se cumplan las restricciones de precedencia. Si solo hay una sala de conferencias, podemos simplemente mantener las conferencias en orden topológico y completar las N clases en N tiempo (suponiendo que cada clase sea de duración unitaria). Podemos desarrollar heurística observando lo siguiente: en cualquier momento, hay un conjunto de conferencias cuyas restricciones de precedencia han sido satisfechas. Si este conjunto es menor que M, podemos programarlos todos; de lo contrario, necesitamos seleccionar un subconjunto para programar. El subconjunto de selección se puede basar en varias métricas:

• conferencias orden de clasificación en base a la longitud de la cadena más larga de dependencia que están en el inicio de.
• Clasifique las conferencias de orden en función del número de conferencias para las que son requisitos previos inmediatos.
• conferencias orden de clasificación basado en el número total de clases que son requisitos previos directas o indirectas para.

También podemos usar combinaciones de estos criterios para ordenar las conferencias que actualmente se pueden programar. Por ejemplo, para cada vértice, definimos su criticidad como la longitud de una ruta más larga desde ella hasta un sumidero. Programamos conferencias procesando vértices en orden topológico. En cualquier punto de nuestro algoritmo, tenemos un conjunto de conferencias de candidatos: estas son las conferencias cuyos prerrequisitos ya han sido programados. Si el conjunto candidato es menor que el tamaño M, programamos todas las conferencias; de lo contrario, elegimos las M lecciones más críticas y las programamos; la idea es que se programen antes, ya que están al inicio de cadenas de dependencia más largas. El criterio es heurístico y puede no conducir a horarios óptimos; esto es de esperar ya que el problema es NP completo. Se pueden emplear otras heurísticas, por ejemplo, podemos usar el número de clases que dependen de la clase L como la criticidad de la clase L o alguna combinación del criterio.

Answer 2

El artículo de Wikipedia en PERT puede ser un buen lugar para comenzar.