У меня есть граф задач, который является DAG (направленный ациклический граф).Каждый узел в графе является задачей, а ребра графа являются зависимостями / приоритетами.Это показано на прикрепленном изображении.Каждая задача (то есть 1, 2, 3, 4, 5) связана с конкретным типом ресурса.Существует 2 типа ресурсов - A, B. Количество этих ресурсов может варьироваться.Пока давайте предположим, что у нас есть 1 ресурс типа A и 1 ресурс типа B. Ресурс может выполнять только 1 задачу одновременно, и задачи не являются приоритетными.Ресурсы A и B могут выполняться параллельно.Время выполнения каждой задачи также указано на графике.Каков наилучший способ переупорядочить группу обеспечения доступности баз данных таким образом, чтобы задачи можно было выполнять параллельно (для получения минимального временного промежутка), не нарушая ограничения приоритета?Является ли проблема NP-полной?Существуют ли алгоритмы планирования / эвристические алгоритмы, доступные для таких сценариев?
DAG с приоритетом и ограничениями ресурсов