Все планируют NP-трудные проблемы?
Я знаю, что существуют некоторые проблемы планирования там, которые являются NP-hard/NP-complete... однако, ни один из них не указан таким способом показать, что эта ситуация является также NP.
Если Вам ограничили ряд задач к startAfter, startBy, и продолжительности вся попытка использовать единственный ресурс... можно ли разрешить расписание или определить ли, что это не может быть разрешено без исчерпывающего поиска?
Если бы ответ "сожалеет приятель, но это полно NP", какова была бы лучшая эвристика (s?) для использования и там способы уменьшить время, которое требуется для a) разрешить расписание и b) определить неразрешимое расписание.
Я реализовал (в прологе) основную цель разрешения конфликтов через рекурсию, которая реализует "самое маленькое окно сначала" эвристика. Это на самом деле находит решения скорее быстро, но исключительно медленно при нахождении недопустимых расписаний. Существует ли способ преодолеть это?
Yay для составных вопросов!
4 ответа
Самая трудная часть большинства проблем планирования в реальной жизни - это получение достоверности и полного набора ограничений. Если взять пример создания университетского расписания:
- Профессор А не встает утром, он работает во многих комитетах, но никто не скажет бюро расписания о подобном ограничении
- Кафедра 1 нуждается в расписании к началу семестра, однако кафедра 2, которая использует те же самые кабинеты, не хочет принимать решение о курсах, которые будут проводиться до тех пор, пока все студенты не прибудут
- Etc
Тогда вам нужна система расписания, которая может справиться с изменениями, так что когда одно ограничение меняется в последнюю минуту, вам не нужно менять полное расписание.
Все вышесказанное обычно игнорируется в исследовательских работах о системах расписания. Что касается NP завершенности заданной проблемы планирования, то в реальной жизни вас не волнует , так как даже если она не является NP завершенной, вы вряд ли сможете даже определить, что является "лучшим решением", так что достаточно хорошего - достаточно хорошего.
Смотрите http://www.asap.cs.nott.ac.uk/watt/resources/university.html список документов, которые могут помочь вам начать; все еще есть много PHD, которые нужно иметь в программе планирования.
Вы можете использовать динамическое программирование для решения некоторых из этих вещей. Жадные алгоритмы также приходят на ум. Теория планирования - это как глубокие, так и красивые, но эти два, которых я нахожу, решит большинство проблем, которые я сталкивался. Возможно, мне повезло.
Что вы имеете в виду с startby?
с startable и если есть только один ресурс, то быстрое решение может быть использовано топологическую сортировку . Пример алгоритма проходит в линейное время, но не включает случай ошибки, если график содержит циклы.
Вот тот, которого нет.
Запланируйте набор заданий i = 1,2 ... n на одной машине, каждое из которых занимает время t (i), чтобы минимизировать среднее время ожидания.
Решение: отсортировать в порядке возрастания t (i). O (n log n)
Хороший список здесь