algorithm - que - programador de tareas windows 8

¿Algoritmo optimizado para programar tareas con dependencia?

Question

Hay tareas que se leen de un archivo, se procesan y se escriben en un archivo. Estas tareas deben programarse en función de la dependencia. Las tareas también se pueden ejecutar en paralelo, por lo que el algoritmo debe optimizarse para ejecutar tareas dependientes en serie y tanto como sea posible en paralelo.

p.ej:

1. A -> B
2. A -> C
3. B -> D
4. E -> F

Entonces, una forma de ejecutar esto sería ejecutar 1, 2 y 4 en paralelo. Seguido por 3.

Otra forma podría ser ejecutar 1 y luego ejecutar 2, 3 y 4 en paralelo.

Otro podría ejecutarse 1 y 3 en serie, 2 y 4 en paralelo.

¿Algunas ideas?

Answer 1

Dada una asignación entre los elementos y los elementos de los que dependen, una ordenación topológica ordena los elementos para que ningún elemento preceda a un elemento del que depende.

Esta tarea de código de Rosetta tiene una solución en Python que puede indicarle qué elementos están disponibles para procesarse en paralelo.

Dada su entrada, el código se convierte en:

try:
    from functools import reduce
except:
    pass

data = { # From: http://stackoverflow.com/questions/18314250/optimized-algorithm-to-schedule-tasks-with-dependency
    # This   <-   This  (Reverse of how shown in question)
    ''B'':         set([''A'']),
    ''C'':         set([''A'']),
    ''D'':         set([''B'']),
    ''F'':         set([''E'']),
    }

def toposort2(data):
    for k, v in data.items():
        v.discard(k) # Ignore self dependencies
    extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
    data.update({item:set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item,dep in data.items() if not dep)
        if not ordered:
            break
        yield '' ''.join(sorted(ordered))
        data = {item: (dep - ordered) for item,dep in data.items()
                if item not in ordered}
    assert not data, "A cyclic dependency exists amongst %r" % data

print (''/n''.join( toposort2(data) ))

Que luego genera esta salida:

A E
B C F
D

Los artículos en una línea de la salida podrían procesarse en cualquier suborden o, de hecho, en paralelo; siempre y cuando todos los elementos de una línea superior se procesen antes de los elementos de las siguientes líneas para preservar las dependencias.

Answer 2

Deje que cada tarea (por ejemplo A,B,... ) sean nodos en un gráfico acíclico dirigido y defina los arcos entre los nodos en función de su 1,2,...

Luego puede ordenar topológicamente su gráfico (o usar un método basado en búsquedas como BFS ). En su ejemplo, C<-A->B->D y E->F , entonces, A y E tienen una profundidad de 0 y deben ejecutarse primero. Luego puedes ejecutar F , B y C en paralelo seguido de D

Además, echa un vistazo a PERT .

Actualizar:

¿Cómo sabes si B tiene una prioridad más alta que F ?

Esta es la intuición detrás del ordenamiento topológico utilizado para encontrar el orden.

Primero encuentra los nodos raíz (sin bordes entrantes) (ya que uno debe existir en un DAG). En tu caso, eso es A & E Esto resuelve la primera ronda de trabajos que deben completarse. A continuación, los hijos de los nodos raíz ( B , C y F ) necesitan ser terminados. Esto se obtiene fácilmente consultando tu gráfica. El proceso se repite hasta que no haya nodos (trabajos) que se encuentren (finalicen).

Answer 3

Primero genera un ordenamiento topológico de tus tareas. Compruebe los ciclos en esta etapa. a partir de entonces, puedes explotar el paralelismo observando máximos antichains. en términos generales, se trata de conjuntos de tareas sin dependencias entre sus elementos.

Para una perspectiva teórica, este artículo cubre el tema.

Answer 4

Sin considerar el aspecto serial / paralelo del problema, este código puede al menos determinar la solución serial general:

def order_tasks(num_tasks, task_pair_list):
    task_deps= []
    #initialize the list
    for i in range(0, num_tasks):
        task_deps[i] = {}

    #store the dependencies
    for pair in task_pair_list:
        task = pair.task
        dep = pair.dependency

        task_deps[task].update({dep:1})

    #loop through list to determine order
    while(len(task_pair_list) > 0):
        delete_task = None

        #find a task with no dependencies
        for task in task_deps:
            if len(task_deps[task]) == 0:
                delete_task = task
                print task
                task_deps.pop(task)
                break

        if delete_task == None:
            return -1

        #check each task''s hash of dependencies for delete_task
        for task in task_deps:
            if delete_key in task_deps[task]:
                del task_deps[task][delete_key]

    return 0

Si actualiza el bucle que comprueba las dependencias que han sido totalmente satisfechas para recorrer toda la lista y ejecute / elimine tareas que ya no tienen ninguna dependencia al mismo tiempo, eso también le permitirá aprovechar las tareas completadas en paralela.

Answer 5

Sus tareas son un gráfico orientado con (con suerte) sin ciclos.

Contiene sources y wells (los orígenes son tareas que no dependen (no tienen borde de entrada), los pozos son tareas que no se desbloquean (no hay borde de salida)).

Una solución simple sería dar prioridad a sus tareas en función de su utilidad (llamémosle U .

Típicamente, comenzando por los pozos, tienen una utilidad U = 1 , porque queremos que terminen.

Coloque todos los predecesores de los pozos en una lista L del nodo que se está evaluando actualmente.

Luego, tomando cada nodo en L , su valor U es la suma de los valores U de los nodos que dependen de él + 1. Ponga a todos los padres del nodo actual en la lista L

Repetir hasta que todos los nodos hayan sido tratados.

Luego, inicie la tarea que se puede iniciar y tenga el mayor valor de U , porque es el que desbloqueará la mayor cantidad de tareas.

En tu ejemplo,

U(C) = U(D) = U(F) = 1
U(B) = U(E) = 2
U(A) = 4

Lo que significa que iniciará A primero con E si es posible, luego B y C (si es posible), luego D y F