Введение «параллелизма» в задачу планирования задач

Question

Параллелизм в qoutes, поскольку я на самом деле не имею в виду параллельное программирование (Threads / Forking и т. задача, которая должна быть выполнена, и ребро от одной вершины v до другой вершины u означает, что v должно быть завершено до u может быть завершено. Для выполнения каждой задачи требуется определенное количество времени.

Пример: график зависимостей

(это всего лишь пример, программа должна быть в состоянии решитьдля любой группы доступности базы данных)

Используя топологическую сортировку, я обнаружил несколько заказов для выполнения всех задач, если за один раз выполняется одно задание. Но мне интересно представить идею, что несколько задач могут быть запущены и / или выполнены одновременно. Я предполагаю бесконечную «рабочую силу», означающую, что любое количество задач может быть выполнено одновременно. Я хочу найти способ выполнить все задачи в проекте в кратчайшие сроки.

В классе моей задачи (вершина) есть следующие переменные (Java):

class Task{
    int id, time;
    String name;
    List<Task> outEdges;
    List<Task> inEdges;
    boolean isFinished;
    Task(int id, String name, int time){
        this.id = id;
        this.name = name;
        this.time = time;
        isFinished = false;
        outEdges = new ArrayList<Task>();
        inEdges = new ArrayList<Task>();
//Tasks and edges between them are generated while reading from a file.
    }
      ...
}

(Кака также методы их получения / манипулирования) Сам график представлен массивом задач.

Какие виды концепций / алгоритмов я могу использовать, чтобы иметь возможность сделать это?

Answer 1

Предполагая, что вы имеете в виду, что если на вашем графике есть дуга от v до u, то v необходимо завершить, прежде чем можно будет запустить u.

Это просто поисксамое короткое время завершения проекта, когда вы думаете о графике как о графике приоритетности проекта. Для данного узла j (задачи) со временем активности dj >= 0 пусть sj обозначает его время начала.

Тогда следующая линейная программа решает вашу проблему

Minimize  sN [i.e., minimize the starting time of the last activity]
such that sj >= si + di , forall (i,j) in graph [i.e., ensure starting time of jth activity is after completion of ith activity if j follows i in the precedence graph]
such that all si's >= 0 [i.e., all starting times are nonnegative. Without these constraints, problem is unbounded.]

Здесь для удобства, 1 и N - фиктивные действия в начале и в конце проекта, соответственно, с 0 периодами активности. 1 предшествует всем остальным узлам на графике. N находится позади всех других узлов на графике.

Answer 2

Я предполагаю, что вам также указано число K «рабочих» (процессоров) для выполнения задач. То есть одновременно можно выполнить не более K задач. Ясно, что время, необходимое для выполнения всех задач, будет зависеть от K.

Эта проблема известна как приоритетное планирование.

Если число работников K больше или равно количеству задач N, то решение, предложенное Tryer, является правильным: вес самого тяжелого пути в вашей DAG-зависимости зависит от требуемого времени. (Самый тяжелый путь иногда называют критическим путем , и его можно вычислить за линейное время с использованием специального алгоритма кратчайшего пути.)

Если K = 1, как вы уже заметили, вы просто следуететопологический порядок и требуемое время будут суммой времени задач.

К сожалению, в интересном случае, когда 1 планирования списков . Идея составления списков очень проста. На каждом шаге алгоритма вы перебираете всех своих K рабочих. Для любого из них, который не используется, вы назначаете доступную неназначенную задачу и зависимости которой уже выполнены. Затем вы помечаете эту задачу как назначенную и продолжаете. После того, как все работники заняты или им не могут быть назначены другие задачи, вы ждете завершения некоторых задач и возобновляете алгоритм, как и раньше.

Строго можно доказать, что время T ', в которое алгоритм планирования списков завершит последнюю задачу, составляет самое большее T * + P, где T * - оптимальное время, а P - вес критического пути. ,Таким образом, алгоритм будет хорошо работать, если задачи на критическом пути составляют небольшую долю от общего числа.

Answer 3

Это, вероятно, будет зависеть от структуры конкретного графика.

Если требуемым результатом является достижение только одного конечного узла, такой алгоритм, как поиск в глубину , можно использовать для обеспечения последовательности событий. Как только он станет доступным, паралелизации не будет, поскольку существует строгая зависимость от последовательности.

Если необходимо прибыть в более чем один узел (и график можно пройти за разумное количество времени), алгоритмнапример, поиск в ширину может использоваться для предоставления требуемых последовательностей. Затем скажите, что вы хотите получить n различных вершин. Новый семантический граф (назовем его g2) может быть определен частями путей, которые являются общими для достижения требуемых вершин. Это означает, что каждое ребро в новом графе будет состоять из объединения общих частей в направлении достижения этих вершин. Для g2 все ребра могут запускаться параллельно.

Отказ от ответственности: Выше не жестко проверенный алгоритм, просто идея реализации.