Я хочу найти критический путь для взвешенной группы доступности базы данных (путь с наибольшим весом), но с указанным количеством процессоров. Я знаю, как решить это с бесконечными процессорами.
Как вычислить критическую траекторию направленного ациклического графа?
Расчет критического пути графика
Очевидно, есть много разных способов, но обычно популярным методом является отслеживание максимальной стоимости или минимального времени запуска, а затем итеративное обновление стоимости путем добавления затрат на родительские узлы и т. Д.
Если бы у меня было только p процессоров, как бы я изменил этот алгоритм? Мой метод состоит в том, чтобы отслеживать «готовые» узлы и «работающие в данный момент» узлы, а затем выскакивать на максимум p узлов за раз.
Я не уверен, как это сделать эффективно, хотя ... Я просто хочу найти вес критического пути, а не сам путь!
Я понимаю на бумаге, когда я вытягиваю процессоры и планирую их вручную, но так как я не знаю, сколько у меня процессоров (это просто «р» процессоры), я не уверен, как имитировать это в код.