Максимизировать прибыль в планировании задач блока с зависимостями
проблема У меня есть n заданий для планирования в P секунд на неограниченном количестве машин с зависимостями между заданиями, т.е. для каждой работы есть набор работ, которые должны быть запланированы только после того, как эта работа закончена. Прибыль для планирования Iго работа в Jго второй на любой машине — это f (i, j), что положительно.
И моя цель состоит в том, чтобы максимизировать общую прибыль, планируя каждую работу точно один раз в самое большее P секунд.
Мы можем предположить, что все работы могут быть запланированы в P секунд всегда.
Все известно заранее, т.е. проблема офлайн.
Также 0 <= f (i, j) <= B для всех я, j.
и число зависимостей составляет O (n).
Легко ли решить эту проблему? [может быть из-за конечных ограничений]
Мой подход
Для простоты сначала предположим, что для работы ее прибыль не зависит от времени.
То есть f (i, j) не зависит от j для всех i и зависит только от i.
Тогда будет работать любой топологический порядок, который соответствует P секундам.
Если нет зависимости, то мы также выбираем время, которое дает наибольшую прибыль для каждой работы, и это тоже легко.
Но проблема в том, что прибыль за рабочие места меняется со временем от зависимостей, в этом случае я не могу придумать какой-либо общий алгоритм.
У меня возникают проблемы при работе с зависимостями между заданиями. Существуют ли какие-либо ресурсы для алгоритмов планирования задач зависимых подразделений в Интернете?
Пожалуйста, поделитесь любой идеей, которая может помочь …
Обновить Я добавил границы для различных параметров, так как они могут потребоваться для анализа проблемы.
Решение
Это проблема динамического программирования. Для простоты предположим, что все прибыли неотрицательны.
определять F(i, j) быть максимальной прибылью от планирования iи все вещи, которые зависят от нее (рекурсивно вниз) в или позже jили второй -1 если это невозможно.
затем F(i, j) является -1 если F(i_1, j+1) является -1 для любой зависимости i_1 из i, В противном случае это больше (f(i, j) плюс сумма F(i_1, j+1)) или же F(i, j+1),
И тогда ваш ответ является суммой F(i, 0) для всех работ i без каких-либо зависимостей.
(Без неограниченных машин эта проблема стала бы нп-хард …)
Вот пример того, как использовать вашу задачу для моделирования уравнений MAX-SAT, где в каждом предложении есть все неотрицательные члены или все отрицательные члены.
Предположим, у нас есть 4 логических переменных A, B, C, а также D, В качестве примера предположим, что мы хотим сделать максимальную выполнимость для уравнения (A && B) || (!A && !C) || (!B && !C && !D) || (C && D), (Куда ! значит нет, && означает и, и || значит или.)
Давайте использовать обозначение J1 > J2 для работы, где J1 должен бежать раньше J2, И распределить по скобкам так, чтобы J1 > (J2, J3) Значит это J1) is a dependency for bothJ2andJ3`.
Теперь, чтобы смоделировать логические значения, давайте создадим 12 заданий. A1 > A2 > A3, B1 > B2 > B3, C1 > C2 > C3, а также D1 > D2 > D3, Тогда рабочие места A2, B2, C2, D2 должно произойти во время 2 или же 3и логическое значение A это правда утверждения «A2 происходит в момент времени 2 «. И аналогично для других логических выражений.
Все эти рабочие места дают прибыль 1 независимо от того, во сколько они бегут. Мы ввели в 3 раза больше заданий, чем булевы, но пока это просто.
Теперь давайте добавим вакансии для предложений. Каждое из этих рабочих мест будет иметь прибыль 11 если это работает в секундах 2 или же 3, а также 1 иначе. Таким образом, ваша максимальная прибыль будет достигнута, когда вы найдете настройки для ваших логических значений, которые максимизируют количество истинных предложений.
(A2, B2) > J1 моделирует правду (A && B),
J2 > (A2, C2)) моделирует правду (!A && !C),
J3 > (B2, C2, D2) моделирует правду (!B && !C && !D),
(C2, D2) > J4 моделирует правду (C && D),
Это опять-таки простое преобразование, с количеством добавленных заданий, равным количеству предложений.
Итак, мы моделируем проблемы MAX-SAT с расписанием. Но мы не можем смоделировать их всех. В частности, мы не можем моделировать предложения со смешанным отрицанием, такие как (A && !B), Так что, хотя MAX-SAT является NP-hard, возможно, что эта ограниченная версия — нет. Однако другие ограниченные версии MAX-SAT, например MAX-2SAT, имеют тенденцию быть NP-сложными, и я считаю, что эта версия тоже будет.
Но для доказательства или опровержения этой интуиции, вы должны спросить на более подходящем форуме. подобно https://cs.stackexchange.com/.
Другие решения