В своем первом исследовании в области управления очередностью Лоулер предположил, что с этим явлением можно легко справиться. Например, возьмем алгоритм скорейшей даты исполнения, который минимизирует максимальную задержку при выполнении набора задач. Если ваши задачи связаны между собой отношениями предшествования, то все усложняется: вы не можете просто пробираться через список дел, исходя только из их дедлайнов, если к некоторым делам нельзя приступить до выполнения других. Однако в 1968 году Лоулер доказал, что это не такая уж и беда, если вы можете построить список дел «задом наперед»: просто выберите те задачи, от выполнения которых не зависят другие дела, и поместите одну из них с наиболее «отдаленным» дедлайном в самый конец списка. Затем просто повторяйте этот процесс, каждый раз учитывая только те задачи, которые не являются необходимым условием для выполнения других (пока еще не запланированных) задач.
Но проницательный взгляд Лоулера позволил выявить кое-что любопытное. Алгоритм наименьшего времени обслуживания, как мы видели, представляет собой оптимальное решение, если наша цель – вычеркнуть как можно больше задач из списка дел как можно быстрее. Но если некоторые из ваших задач связаны между собой отношениями предшествования, не существует простого или очевидного способа адаптировать алгоритм наименьшего времени обслуживания для этой ситуации. Несмотря на то что задача кажется элементарной, ни Лоулеру, ни другим исследователям оказалось не под силу найти для нее эффективное решение.
Более того, сам Лоулер скоро обнаружил, что эта ситуация принадлежит к той категории задач, которые, по мнению большинства программистов, не имеют эффективного решения. Специалисты называют их труднорешаемыми[19].
Как мы имели возможность наблюдать в рамках сценария «утроить выигрыш или потерять все», на который не распространяется мудрость оптимальной остановки, не каждая четко сформулированная задача имеет решение. В планировании очевидно, что каждый набор задач и ограничений предполагает наличие какого-либо наилучшего порядка выполнения, поэтому задачи планирования, в сущности, имеют решение, но возможны случаи, для которых просто не существует однозначного алгоритма, могущего подобрать оптимальное расписание выполнения работ в разумные сроки.
Это обстоятельство привело исследователей вроде Лоулера и Ленстра к неизбежному вопросу. Так все же какова доля труднорешаемых задач планирования? Через 20 лет после того, как Селмер Джонсон с помощью своей работы о переплетном деле дал толчок развитию теории планирования, поиск отдельных решений стал самой грандиозной и амбициозной задачей – своеобразным квестом по нанесению на карту всего рельефа теории планирования.