Максимизировать прибыль при планировании единичных задач с зависимостями

Проблема У меня есть n заданий для планирования в P секунд на неограниченном количестве машин с зависимостями между заданиями i.e. для каждой работы есть набор заданий, которые должны быть запланированы только после завершения этой работы. Прибыль для планирования задания я ^th в j ^th вторая на любой машине равна f (i, j), что является положительным.
И моя цель - максимизировать общую прибыль, планируя каждое задание ровно один раз максимум через P секунд.

Мы можем предположить, что все задания могут быть запланированы в P секунд всегда.

Все известно заранее, то есть автономная проблема.

Также 0 <= f (i, j) <= B. для всех i, j.

а количество зависимостей - от O (n).

Легко ли эта проблема? [может быть обусловлено конечными ограничениями]

Мой подход
Для простоты сначала предположим, что для работы его прибыль не зависит от времени.
То есть f (i, j) не зависит от j для всех я и зависит только от i.
Тогда будет работать любое топологическое упорядочение, которое вписывается в P секунд.
Если нет зависимости, тогда мы также выбираем наивысшую прибыль, дающую время для каждой работы, и это также легко.

Но проблема в том, что прибыль за задание меняется со временем с зависимостями, в этом случае я не могу представить общий алгоритм.

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

Пожалуйста, поделитесь идеей, которая может помочь...

Обновление. Я добавил оценки для различных параметров, поскольку они могут потребоваться для анализа проблемы.

Ответ 1

Это проблема динамического программирования. Предположим для простоты, что все прибыли неотрицательны.

Определите F(i, j) как максимальную прибыль, которая должна быть сделана при планировании i 'th работы и всех вещей, которые зависят от нее (рекурсивно вниз), на или позже, чем j' th second, или -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 без зависимостей.

(Без неограниченных машин эта проблема станет np-hard...)

Вот пример того, как использовать вашу проблему для моделирования уравнений 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 both J2 and J3`.

Теперь, чтобы смоделировать булевы, задайте 12 заданий. A1 > A2 > A3, B1 > B2 > B3, C1 > C2 > C3 и D1 > D2 > D3. Тогда задание A2, B2, C2, D2 должно происходить в момент времени 2 или 3, а логическое A - это истина утверждения "A2 происходит во время 2". А также для других логических объектов.

Все эти задания получают прибыль 1 независимо от того, в какое время они работают. Мы ввели 3x столько заданий, как booleans, но пока это просто.

Теперь добавьте задания для предложений. Каждое из этих заданий будет иметь прибыль 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-жесткий, возможно, что эта ограниченная версия не является. Однако другие ограниченные версии MAX-SAT, например MAX-2SAT, имеют тенденцию быть NP-жесткими, и это моя интуиция, что это тоже будет.

Но для доказательства или опровержения этой интуиции вы должны спросить на более подходящем форуме. Как https://cs.stackexchange.com/.