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

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

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

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

Уу за сложные вопросы!