Все ли проблемы планирования NP-трудны?

Я знаю, что есть некоторые проблемы планирования, которые являются NP-жесткими/NP-полными ... однако ни один из них не заявлен таким образом, чтобы показать, что эта ситуация также NP.

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

Если ответ будет " Извини, приятель, но это NP-complete " что было бы лучшей эвристикой (s?) использовать и есть ли способы уменьшить время, необходимое для А) разрешения расписания и Б) определения неразрешимого расписания.

Я реализовал (в прологе) основную цель разрешения конфликтов с помощью рекурсии, которая реализует эвристику "наименьшее окно первым". Это на самом деле находит решения довольно быстро, но исключительно медленно при поиске недействительных расписаний. Есть ли способ преодолеть это?

Ура для соединения вопросы!

6 18
heuristics recursion scheduling np-complete

6 ответов:

Самая трудная часть большинства задач планирования вреальной жизни - это получение надежности и полного набора ограничений. Если взять пример создания университетского расписания:

  • профессор а не встанет утром, он состоит на многих комитетах, но никто не расскажет бюро расписания о такого рода ограничениях
    • Отдел 1 нуждается в расписании к началу семестра, однако отдел 2, который использует те же комнаты, не желает принимать решение. на курсах, которые будут проходить до тех пор, пока не прибудут все студенты
  • Etc

Тогда вам нужна система расписания, которая может справиться с изменениями, поэтому, когда одно ограничение изменяется в последнюю минуту, вам не нужно менять полное расписание.

Все вышеперечисленное обычно игнорируется в научных работах о системах планирования. Что касается NP полноты данной задачи планирования, то в реальной жизни вам все равно , так как даже если она не является NP полной, Вы вряд ли даже удастся определить, что такое "лучшее решение", поэтому достаточно хорошо.

См. http://www.asap.cs.nott.ac.uk/watt/resources/university.html для списка работ,которые могут помочь вам начать работу; есть еще много докторов наук, которые нужно иметь в программном обеспечении планирования.

16

Часто существуют хорошие алгоритмы аппроксимации для NP-жестких/полных задач оптимизации, таких как планирование. Вы можете пролистать заметки Ахмеда Абу Сафии о приближенных алгоритмахдля планирования или различныхработах .

В некотором смысле, вся криптография с открытым ключом выполняется с "менее трудными" задачами, такими как факторинг частично, потому что NP-трудные задачи предлагают слишком много простых случаев. Это та же самая NP-полнота, которая делает их "морально жесткими", что также дает им слишком много легких проблем, которые часто попадают в некоторые границы ошибки оптимального.

Существует более глубокая теория жесткости аппроксимации, которая обсуждает ограничения алгоритмов аппроксимации.

3

Для решения некоторых из этих задач можно использовать динамическое программирование. Жадные алгоритмы также приходят на ум. Теория планирования одновременно глубока и прекрасна, но эти две, которые я нахожу, решат большинство проблем, с которыми я столкнулся. Возможно, мне просто повезло.

2

Что ты имеешь в виду со стартби?

С startAfter и если есть только один ресурс, то быстрым решением может быть использование топологической сортировки . Пример алгоритма выполняется в линейном времени, но не включает случай ошибки, если график содержит циклы.

1

Вот один, которого нет.

Запланируйте набор заданий i= 1,2...n на одной машине, каждая из которых занимает время t(i) так, чтобы среднее время ожидания было сведено к минимуму.

Решение: сортировка в порядке возрастания t (i). O (n log n)

Хороший список здесь

1

Рассмотрим задачу планирования, которая находится в классе P:

Ввод: список действий, которые включают время начала и время окончания.

Сортировка по времени окончания.

Выберите первые N элементов этого отсортированного списка, чтобы найти максимальное количество мероприятий, которые вы можете запланировать в данный момент времени.

Вы можете добавить предостережения, такие как: все действия должны заканчиваться в 5 вечера, ну в этом случае, когда вы работаете через список, остановитесь, как только вы достигнете действия, которое заканчивается после этого времени.

0