Если у меня есть Направленный ациклический граф, вершины которого представляют задачи, а ребро представляет зависимость, и каждая вершина может содержать «значение» в 24-часовом формате времени (например, 1600, 1700, 1130), это значение представляет самое раннее время в день, когда эта задача может начаться.
Например:
Task C depends on Task B1's completion
Task C also depends on Task B2' completion
Task B1 depends on A's completion
Task B2 depends on A's completion, B2 also has a value of 1600(4pm), which means it can only start at or after 1600
Task A depends on nothing, A also has a value of 1500 (3pm), which means it can only start at or after 1500.
Это будет график с четырьмя вершинами (задачами): A, B1, B2, C. Задание B1 или B2 может выполняться только при завершении A, а задание C может выполняться только при завершении BOTH B1 и B2.
Учитывая этот график, как я могу вывести правильный порядок последовательности задач, оптимизированный по времени. Например: в этом случае оба из них являются правильными последовательностями работы:
A->B1->B2->C
A->B2->B1->C
Но последовательность 1 более оптимизирована по времени, потому что в последовательности 2 мы должны ждать до 1600, чтобы запустить B2, удерживая все остальное. В последовательности 1 мы можем сначала запустить B1, а затем подождать до 1600. Хотя общее время завершения может не отличаться, оптимизированный означает «запускать каждое задание как можно раньше». Также для простоты давайте не будем рассматривать продолжительность работы: предположим, что каждая работа завершается мгновенно после ее запуска.
Итак, вопрос в том, какой разумный алгоритм использовать для вывода такой оптимизированной по времени последовательности? Я знаю, что без учета оптимизации времени это всего лишь топологическая сортировка, но как мне улучшить этот алгоритм для оптимизации времени?