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

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

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

Все заранее известно т.е. проблема оффлайн.

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

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

Эта проблема проста? [может быть из-за конечных ограничений]

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

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

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

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

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


c++ optimization job-scheduling algorithm maximize
person v78    schedule 07.12.2014    source источник
comment
Работы выполняются за 1 секунду? То есть, если задание запланировано на время j, то любые зависимые задания могут выполняться во время j + 1? Учитывая, что мы все знаем заранее, всегда можно подобрать решение, но я предполагаю, что вы спрашиваете, существует ли что-то лучшее.   -  person dohashi    schedule 09.12.2014
comment
да, любое НЕМЕДЛЕННОЕ зависимое задание может быть запланировано на время j + 1 секунда. Наивная грубая сила очень неэффективна и экспоненциальна для этой проблемы   -  person v78    schedule 09.12.2014
comment
Возможно, вы сможете прочитать редакционную статью, когда она выйдет: codechef.com/DEC14/problems/RIN   -  person David Eisenstat    schedule 12.12.2014

Ответы (1)


arrow_upward
3
arrow_downward

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

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

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

person btilly    schedule 07.12.2014
comment
Нет, тут ошибка, с таким подходом разобрался раньше. Граф зависимости задач - это не дерево в целом, это DAG, если у задания более одного родителя, то такой подход дает неправильный ответ [он завышает требуемую прибыль]. Могу привести пример, если непонятно ?? - person v78; 08.12.2014
comment
Это серьезный поворот и неверное предположение с моей стороны. Извините. - person btilly; 08.12.2014
comment
Думаю, DP может быть неприменим в общем случае. Также эта проблема не является NP-полной, возможно, может быть применен сетевой поток. - person v78; 08.12.2014
comment
@ cc2 Я думал о случае, когда P=4, есть набор S заданий, которые могут произойти либо во 2-ю секунду, либо в 3-ю секунду, есть другие T работы, которые получают значительную прибыль, если они выполняются во 2-ю секунду, и подмножество S зависит от них, и еще больше T', которые получают значительную прибыль, если они происходят во второй 3-й секунде и зависят от подмножества S. Для каждого элемента S у вас есть логическое значение, это задание выполняется на второй секунде. Каждый элемент T и T' представляет собой логическое предложение. И вы смоделировали задачу MAX-SAT. Я не знаю, как это доказать ... - person btilly; 09.12.2014
comment
вы достаточно смоделировали MAX-SAT, чтобы ответить на ваш вопрос об этом типе работы на самом деле NP-Hard, но это действительно так. Я бы посоветовал спросить об этой разновидности csexchange, где вы привлечете людей более квалифицированных, чем я, для анализа вопроса. - person btilly; 09.12.2014
comment
не могли бы вы объяснить свое снижение до MAX-SAT своим примером со ЗНАЧЕНИЯМИ. Я не могу понять, как это можно уменьшить до MAX-SAT. - person v78; 09.12.2014
comment
@ cc2 Я обновил сообщение, чтобы проиллюстрировать, как я сокращаю определенный тип проблемы планирования, которую вы хотели бы решить, до определенного класса задач MAX-SAT. И пояснил, что еще нужно сделать, чтобы это превратилось в демонстрацию того, что я правильно подозреваю, что ваша проблема - NP-Hard. - person btilly; 09.12.2014
comment
@btilly Вы уверены, что хотите, чтобы ваша формула была ИЛИ ИЛИ, а не ИЛИ? Вопросы выполнимости обычно относятся к последнему. В противном случае все, что нам нужно сделать, это найти удовлетворительное задание для одного предложения, и все готово. - person mhum; 10.12.2014
comment
@mhum Если присмотреться внимательнее, ты прав. Тем не менее, конструкция, которая у меня есть, представляет собой серию двоичных вариантов с предложениями, которые являются и. Я все равно готов поспорить, что это NP-сложно, даже если это не та проблема, о которой я думал. - person btilly; 10.12.2014
comment
@ cc2: Я не понимаю, что вы, ребята, говорите о MAX-SAT, но я совершенно уверен, что каждый F(i, j) может быть вычислен за O(n*p) с помощью динамического программирования. - person Mooing Duck; 11.12.2014
comment
@MooingDuck Проблема в том, что задания могут иметь несколько зависимостей, и от них могут зависеть разные вещи. F(i, j), как описано, приписывает всю возможную дополнительную прибыль от более раннего планирования дочерних процессов к решению о том, когда должно выполняться родительское задание, а затем планирует сверху вниз. Но если дочерняя работа зависит от независимых родителей, то, когда один из родителей запланирован, влияет на то, что F(i,j) должно быть для другого, и наоборот. Так что все разваливается. - person btilly; 12.12.2014
comment
@btilly: Я написал половину объяснения, прежде чем полностью понял суть проблемы. Мое плохое, ты прав. - person Mooing Duck; 12.12.2014
comment
@btilly Хотя вполне возможно (вероятно?), что вы правы, не обязательно, что созданные вами виджеты будут подходить друг к другу требуемым образом. Например, ограничения приоритета очень удобны для моделирования отношений И, но не так хороши для ИЛИ; неограниченное количество идентичных процессоров немного усложняет моделирование отношений исключения; и т. д. Между тем, проблема SAT (с предложениями в CNF), когда все переменные в предложении либо все инвертированы, либо все неотрицательны, известна как MONOTONE SAT, и, как я полагаю, известна как NP-полная. - person mhum; 13.12.2014