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

Question

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

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

Если ответ «Извини, приятель, но это NP-полно» какую эвристику(ы?) лучше всего использовать и существуют ли способы сократить время, необходимое для а) разрешения расписания и б) выявления неразрешимого расписания.

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

Ура сложным вопросам!

Answer 1

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

• Профессор А не встанет утром, он входит в состав многих комитетов, но никто не сообщит в офис расписания о такого рода ограничениях.
• Кафедре 1 необходимо расписание к началу семестра, однако кафедра 2, которая использует те же аудитории, не желает принимать решение о курсах, которые будут проводиться до тех пор, пока не прибудут все студенты.
• И т. д

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

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

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

Answer 2

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

В каком-то смысле вся криптография с открытым ключом выполняется с помощью «менее сложных» задач, таких как частичный факторинг, потому что NP-сложные задачи предлагают слишком много простых случаев.Та же самая NP-полнота делает их «морально трудными», что также дает им слишком много простых задач, которые часто попадают в пределы некоторой погрешности от оптимальных.

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

Answer 3

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

Answer 4

Что вы имеете в виду под startBy?

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

Answer 5

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

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

Решение:Сортировка в порядке возрастания t(i).О (п журнал п)

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

Answer 6

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

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

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

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

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