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

Question

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

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

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

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

Yay для сложных вопросов!

Answer 1

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

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

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

Answer 6

Рассмотрим проблему планирования в классе P:

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

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

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

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