Целочисленная линейная оптимизация для NP-сложных задач
В зависимости от ваших побочных ограничений, вы можете использовать метод критического пути или
(как предложено в предыдущем ответе) динамическое программирование . Но многие задачи планирования, как и у классического коммивояжера, труднодостижимы - точное решение имеет наихудший случай экспоненциального времени поиска, как вы описали в своей проблеме.
Важно знать, что хотя NP-сложные задачи все еще имеют очень плохое худшее время время решения, существует подход, который очень часто дает точные ответы с очень короткими вычислениями ( среднее значение *) 1014 * приемлемо, и вы часто не видите худшего случая).
Этот подход заключается в преобразовании вашей задачи в задачу линейной оптимизации с целочисленными переменными. Существуют пакеты свободных программ (например, lp-solve), которые могут эффективно решать такие проблемы.
Преимущество этого подхода в том, что он может дать вам точные ответы на NP-сложные задачи в приемлемое время. Я использовал этот подход в нескольких проектах.
Поскольку ваша формулировка проблемы не содержит более подробной информации о побочных ограничениях, я не могу более подробно рассказать о том, как применять метод.
Редактирование / добавление: пример реализации
Вот некоторые подробности о том, как реализовать этот метод в вашем случае (конечно, я делаю некоторые предположения, которые могут не относиться к вашей реальной проблеме - я знаю только детали из вашего вопроса):
Предположим, что у вас есть 50 команд cmd (i) (i = 1..50), которые должны быть запланированы на 10 или менее циклов цикла (t) (t = 1..10). Введем 500 двоичных переменных v (i, t) (i = 1.50; t = 1..10), которые указывают, выполняется инструкция cmd (i) в цикле (t) или нет. Эта базовая настройка дает следующие линейные ограничения:
v_it integer variables
0<=v_it; v_it<=1; # 1000 constraints: i=1..50; t=1..10
sum(v_it: t=1..10)==1 # 50 constraints: i=1..50
Теперь мы должны указать ваши побочные условия. Давайте предположим, что операции cmd (1) ... cmd (5) являются операциями умножения и что у вас есть ровно два умножителя - в любом цикле вы можете выполнять максимум две из этих операций параллельно:
sum(v_it: i=1..5)<=2 # 10 constraints: t=1..10
Для каждого из ваших ресурсов вам нужно добавить соответствующие ограничения.
Также давайте предположим, что операция cmd (7) зависит от операции cmd (2) и должна быть выполнена после нее. Чтобы сделать уравнение немного более интересным, давайте также потребуем разрыв между двумя циклами:
sum(t*v(2,t): t=1..10) + 3 <= sum(t*v(7,t): t=1..10) # one constraint
Примечание: сумма (t * v (2, t): t = 1..10) - это цикл t, где v (2, t) равно единице.
Наконец, мы хотим минимизировать количество циклов. Это несколько сложно, потому что вы получаете довольно большие цифры, как я предлагаю: мы присваиваем каждому v (i, t) цену, которая экспоненциально растет со временем: откладывание операций в будущее обходится гораздо дороже, чем их раннее выполнение:
сумма (6 ^ t * v (i, t): i = 1.50; t = 1..10) -> минимум. # одна целевая функция
Я выбираю 6 больше 5, чтобы гарантировать, что добавление одного цикла в систему делает его более дорогим, чем сжатие всего на меньшее количество циклов. Побочным эффектом является то, что программа постарается планировать операции как можно раньше. Вы можете избежать этого, выполнив двухэтапную оптимизацию: во-первых, используйте эту целевую функцию, чтобы найти минимальное количество необходимых циклов. Затем задайте ту же проблему еще раз с другой целевой функцией - ограничив число доступных циклов с самого начала и наложив более умеренный штраф за последующие операции. Вы должны поиграть с этим, надеюсь, у вас есть идея.
Надеюсь, вы можете выразить все ваши требования в виде линейных ограничений в ваших двоичных переменных. Конечно, у вас может быть много возможностей использовать ваше понимание конкретной проблемы с меньшими ограничениями или меньшими переменными.
Затем передайте вашу проблему в lp-solve или cplex и позвольте им найти лучшее решение!