Лоулер потратил много лет своей жизни, размышляя над тем, как эффективно выполнять последовательность задач, а вот его карьерный путь любопытным образом петлял. Он изучал математику в Университете Флориды, затем приступил к написанию дипломной работы в Гарварде в 1954 году, хотя и покинул его до получения степени. После учебы в юридической школе, прохождения военной службы и работы на заводе он в 1958 году вернулся в Гарвард, защитил диплом и получил работу в Мичиганском университете. Приехав в Беркли в 1969 году во время своего академического отпуска, он был арестован во время акции протеста против войны во Вьетнаме. Лоулер стал преподавателем одного из факультетов Университета Беркли на следующий год и завоевал репутацию «общественного сознания» отделения компьютерной науки. После его смерти в 1994 году Ассоциация вычислительной техники США учредила премию имени Лоулера для тех, кто в своих работах демонстрирует гуманитарный потенциал компьютерной науки.

В своем первом исследовании в области управления очередностью Лоулер предположил, что с этим явлением можно легко справиться. Например, возьмем алгоритм скорейшей даты исполнения, который минимизирует максимальную задержку при выполнении набора задач. Если ваши задачи связаны между собой отношениями предшествования, то все усложняется: вы не можете просто пробираться через список дел, исходя только из их дедлайнов, если к некоторым делам нельзя приступить до выполнения других. Однако в 1968 году Лоулер доказал, что это не такая уж и беда, если вы можете построить список дел «задом наперед»: просто выберите те задачи, от выполнения которых не зависят другие дела, и поместите одну из них с наиболее «отдаленным» дедлайном в самый конец списка. Затем просто повторяйте этот процесс, каждый раз учитывая только те задачи, которые не являются необходимым условием для выполнения других (пока еще не запланированных) задач.

Но проницательный взгляд Лоулера позволил выявить кое-что любопытное. Алгоритм наименьшего времени обслуживания, как мы видели, представляет собой оптимальное решение, если наша цель – вычеркнуть как можно больше задач из списка дел как можно быстрее. Но если некоторые из ваших задач связаны между собой отношениями предшествования, не существует простого или очевидного способа адаптировать алгоритм наименьшего времени обслуживания для этой ситуации. Несмотря на то что задача кажется элементарной, ни Лоулеру, ни другим исследователям оказалось не под силу найти для нее эффективное решение.

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

Как мы имели возможность наблюдать в рамках сценария «утроить выигрыш или потерять все», на который не распространяется мудрость оптимальной остановки, не каждая четко сформулированная задача имеет решение. В планировании очевидно, что каждый набор задач и ограничений предполагает наличие какого-либо наилучшего порядка выполнения, поэтому задачи планирования, в сущности, имеют решение, но возможны случаи, для которых просто не существует однозначного алгоритма, могущего подобрать оптимальное расписание выполнения работ в разумные сроки.

Это обстоятельство привело исследователей вроде Лоулера и Ленстра к неизбежному вопросу. Так все же какова доля труднорешаемых задач планирования? Через 20 лет после того, как Селмер Джонсон с помощью своей работы о переплетном деле дал толчок развитию теории планирования, поиск отдельных решений стал самой грандиозной и амбициозной задачей – своеобразным квестом по нанесению на карту всего рельефа теории планирования.

Исследователи пришли к выводу, что даже самое малозаметное изменение условий задачи планирования зачастую способно перенести ее в категорию труднорешаемых. Например, алгоритм Мура минимизирует количество не сделанных вовремя дел (или испорченных продуктов) в случае, когда все дела имеют одинаковую важность, но, если одно из дел более значимо, задача переходит в разряд труднорешаемых и ни один алгоритм не в силах предложить оптимальное расписание. Аналогично, если вам приходится ждать наступления определенного момента, чтобы приступить к делам, то почти все задачи по планированию, которые мы можем легко и эффективно решить без такого условия, становятся труднорешаемыми. Запрет на вынос мусорного ведра на улицу до того момента, когда приедет мусоровоз, мог бы стать разумной мерой организации порядка в городе, но при этом вы полностью потеряете контроль над вашим графиком.

Обозначение границ теории планирования продолжается по сей день. Недавнее исследование показало, что около 7 % всех задач все еще неизвестны. Это неизведанная сторона планирования. Из 93 % известных нам задач только 9 % имеют эффективное решение, а остальные 84 % считаются труднорешаемыми. Другими словами, для большинства задач по планированию типовые решения не подходят.

Если эффективная организация вашего графика кажется вам непосильным делом, возможно, это так и есть. Тем не менее алгоритмы, которые мы обсудили, могут стать отправной точкой для решения таких непростых задач: если решение и не будет идеальным, по крайней мере, оно будет грамотным.