Все проблемы планирования 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 вечера, ну в этом случае, когда вы работаете через список, остановитесь, как только вы достигнете активности, которая заканчивается после этого времени.