Несмотря на их преимущества, ресурсные ограничения приводят к усложнению задач планирования, поскольку в них вводятся дополнительные зависимости между действиями. К тому же составление расписания без ограничений с использованием метода критического пути является несложным, а задача поиска расписания с ресурсными ограничениями, характеризующегося самым ранним возможным временем завершения, является NP-трудной. Такая сложность часто наблюдается не только в теории, но и на практике. Одно из заданий, которое предложили исследователям для проверки их сил в 1963 году (найти оптимальное расписание для задачи, в которой рассматриваются только 10 машин и 10 работ по 100 действий каждая), не удавалось решить в течение 23 лет [900]. Для его решения было опробовано много подходов, включая метод ветвей и границ, алгоритм эмуляции отжига, поиск с запретами, метод удовлетворения ограничений и другие методы, описанные в части II этой книги. Одной из простых, но широко применяемых эвристик является алгоритм с минимальным резервом. В нем планирование действий осуществляется в режиме жадного поиска. Во время каждой итерации в этом алгоритме рассматриваются не введенные в расписание действия, для которых в расписании заданы все их преемники, и в расписание вводится то действие, которое имеет наименьший резерв для самого раннего возможного времени начала. После этого в алгоритме обновляются значения времени ES и LS для каждого затронутого действия и повторяется итерация. Эвристика основана на том же принципе, что и эвристика с "наиболее ограниченной переменной" в задачах удовлетворения ограничений. Этот алгоритм хорошо работает на практике, но применительно к рассматриваемой задаче сборки он привел к получению 130-минутного решения, а не 115-минутного решения, показанного на рис. 12.2.

Подход, принятый в этом разделе, состоит в том, что "вначале следует оставлять план, а затем расписание". Это означает, что общая задача подразделяется на этап планирования, в котором выбираются и частично упорядочиваются действия для достижения целей данной задачи, и на следующий за ним этап составления расписания, в котором в план вводится временная информация для обеспечения того, чтобы он соответствовал ограничениям по ресурсам и срокам. Такой подход широко применяется в организациях, занимающихся реальным планированием производства и поставок, в которых этап планирования часто выполняется экспертами-людьми. Однако, если существуют жесткие ограничения на ресурсы, могут возникать такие ситуации, что одни допустимые планы приводят к получению гораздо более лучших графиков, чем другие. В этом случае имеет смысл интегрировать этапы планирования и составления расписаний, принимая во внимание продолжительности и совпадения действий во времени на этапе создания плана с частичным упорядочением. Для учета такой информации могут быть дополнены некоторые алгоритмы планирования, описанные в главе 11. Например, планировщики с частичным упорядочением могут обнаруживать нарушения ресурсных ограничений во многом с помощью такого же способа, который в них используется для обнаружения конфликтов с помощью причинных связей. А эвристики могут быть модифицированы для оценки общего времени завершения плана, а не просто суммарной стоимости всей действий. В настоящее время в этой области исследований ведется активная работа.