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

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

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

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

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

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

Ответ 1

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

Здесь один, который нет.

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

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

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

Ответ 6

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

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

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

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

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