Хаос дедлайнов: как планировать дела, чтобы все успевать

Книги по тайм-менеджменту часто противоречат друг другу: где-то рекомендуют немедленно выполнять любую мелкую задачу, кто-то считает, что начинать надо с самого сложного, а кто-то, наоборот, что нужно сознательно откладывать дела на потом. Журналист Брайан Кристиан и ученый-когнитивист Том Гриффитс уверены: чтобы все успевать, людям надо пользоваться алгоритмами, по которым работают компьютеры, — с их помощью давно можно найти оптимальный вариант с учетом всех заданных условий. В издательстве «Альпина Паблишер» вышла их книга «Алгоритмы для жизни: Простые способы принимать верные решения», в которой авторы объясняют, как применять сложные математические формулы для решения повседневных задач. T&P публикуют фрагмент.

Наука о времяпрепровождении

«Алгоритмы для жизни: Простые способы принимать верные решения»

Хотя проблема тайм-менеджмента и стара, как само время, наука о планировании родилась в механических цехах индустриальной революции. В 1874 году Фредерик Тейлор, сын зажиточного юриста, отказался от учебы в Гарварде, чтобы стать помощником инженера на заводе гидрооборудования в Филадельфии. Четыре года спустя он закончил обучение и начал работать на Мидвэльском сталелитейном заводе — сначала токарем, затем бригадиром механического цеха и в конце концов стал главным инженером. За это время он пришел к выводу, что время работы техники (и людей) использовалось не очень-то эффективно. Этот вывод и лег в основу разработанной им дисциплины, которую он назвал «научный менеджмент».

Тейлор создал производственно-диспетчерский отдел, ключевым элементом которого стал информационный стенд, на который вывешивалось расписание работы в цехе. В расписании было указано, какую задачу в данный момент выполняет каждая из машин и какие задачи стоят на очереди. Такая практика также ляжет в основу работ коллеги Тейлора Генри Ганта. Во втором десятилетии ХХ века он создаст свою знаменитую диаграмму, которая впоследствии поможет реализовать несколько наиболее амбициозных проектов столетия в сфере строительства — от дамбы Гувера до системы межштатных магистралей США. Век спустя диаграммы Ганта все еще украшают стены кабинетов и экраны ноутбуков руководителей проектов в таких компаниях, как Amazon, IKEA и SpaceX.

Тейлор и Гант сделали планирование объектом своих исследований и дали ему визуальную и концептуальную форму. Однако они не разрешили фундаментальный вопрос: какая же система планирования лучше? Первый намек на то, что на этот вопрос в принципе можно ответить, появился только спустя несколько десятилетий — в 1954 году в научной работе, опубликованной математиком-исследователем Селмером Джонсоном из корпорации RAND.

Джонсон исследовал сценарий переплетного дела: сначала книгу нужно напечатать на одном станке, а потом переплести, используя другой. Но наиболее распространенным примером спаренной работы двух устройств из нашей жизни служит прачечная. Когда вы стираете вещи, в первую очередь они проходят через стиральную машину, а потом отправляются в сушилку. Количество времени, которое займет каждый процесс, напрямую зависит от того, что вы загружаете. Если одежда сильно запачкана, то времени на стирку потребуется больше, при этом время на сушку не будет отличаться от обычного. Большее количество вещей будет дольше сушиться, но стирка займет то же время, что и в случае меньшей загрузки. И здесь Джонсон задал вопрос: «Если за один подход вам необходимо постирать и посушить несколько условных комплектов вещей, как это лучше организовать?»

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

Интуитивно понятно: алгоритм Джонсона работает потому, что вне зависимости от выбранной последовательности загрузки белья в самом начале будет работать только стиральная машина, при этом сушилка будет простаивать (а в самом конце, когда останется только посушить выстиранные вещи, — наоборот). Если в самом начале стирать вещи на коротких программах, а в конце сушить наименьшее количество вещей, то мы увеличим период, когда и стиральная машина, и сушильная работают одновременно. Таким образом, у нас получится свести к минимуму время, проведенное в прачечной. Анализ Джонсона лег в основу первого оптимального алгоритма планирования: начните с недолгой стирки и закончите полупустой сушилкой. […]

Существенная для нас проблема планирования действительно касается только одного устройства — нас самих.

Справляемся с дедлайнами

Планируя работу одного устройства, вы сразу же сталкиваетесь с проблемой. Исследования Джонсона на примере переплетного дела основывались на максимальном сокращении временных затрат, необходимых для выполнения работы двумя машинами. В случае управления одним устройством, если мы будем выполнять все поставленные задачи, любое расписание потребует одинаковое количество времени и определение порядка задач будет лишено смысла.

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

Таким образом, мы получаем первый урок в планировании работы одного устройства еще до того, как мы приступили к обсуждению, а именно: точно определите ваши цели. Мы не сможем объявить победителя среди способов планирования, пока не поймем, как вести счет. Этот вопрос также относится к компьютерной науке: прежде чем у вас появится план, вы должны определить набор критериев. Оказывается, от выбора критериев напрямую зависит, какой же подход в планировании станет лучшим.

Первые научные работы о планировании задач для одного устройства последовали сразу же за исследованием Джонсона и предложили ряд веских критериев. Под каждый критерий была разработана простая оптимальная стратегия.

Мы привыкли к тому, что, например, для каждой задачи существует срок исполнения и допустимая величина просрочки. Таким образом, мы можем ввести термин «максимальное опоздание выполнения набора задач» — наибольший среди этих задач срыв установленного срока исполнения (именно это будет учтено вашим работодателем при оценке вашей деятельности). Для розничных покупателей или заказчиков услуг, например, максимальная задержка выполнения задачи соответствует самому долгому времени ожидания для клиента.

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

Возможно, вы уже используете стратегию скорой даты исполнения, чтобы справляться с рабочей нагрузкой, тогда вам не нужно прислушиваться к советам программистов при выборе стратегии. Но, скорее всего, вы не в курсе, что это оптимальная стратегия. Более точным будет сказать, что для вас важен только один конкретный показатель — сокращение времени вашего максимального опоздания. Если вы не преследуете такую цель, то вам может больше подойти другая стратегия.

Например, возьмем холодильник. […] У каждого продукта разный срок хранения, поэтому употребление их по принципу очередности истечения срока хранения кажется самой разумной идеей. Однако это еще не конец истории. Алгоритм скорой даты исполнения, или в нашем случае даты порчи продукта, оптимален для сокращения времени максимального опоздания, что означает минимизацию степени испорченности одного наиболее испорченного продукта, который вам предстоит съесть. Наверное, это не самый аппетитный критерий.

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

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

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

Как разобраться с делами

Иногда соблюдение сроков — не самая большая наша забота. Мы просто хотим переделать все дела: чем больше дел, тем быстрее нам хочется с ними разобраться. Оказывается, что перевести это на первый взгляд элементарное желание в плоскость критериев планирования очень непросто.

Первый подход — подумать отвлеченно. Мы ранее отметили, что при планировании работы одного устройства мы не можем повлиять на общее время выполнения всех задач, но, если, например, каждая отдельная задача — это ожидающий клиент, есть способ максимально уменьшить время коллективного ожидания всех клиентов.

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

Максимальное уменьшение суммы времен выполнения ведет нас к очень простому оптимальному алгоритму — алгоритму наименьшего времени обслуживания: сначала делай то, что можешь сделать быстрее всего.

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

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

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

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

В деловом мире вес можно оценить в денежном эквиваленте: сколько денег вам принесет выполнение той или иной задачи. Разделив вознаграждение на время выполнения, мы получим почасовую ставку для каждого задания. (Если вы фрилансер, для вас это может быть особенно эффективно: просто разделите стоимость каждого вашего проекта на его объем и работайте над проектами в порядке уменьшения почасовой ставки.) Что любопытно, весовая стратегия также появляется и в исследованиях, посвященных добыванию пищи у животных: там доллары и центы превращаются в орехи и ягоды. Животные, стремясь получить максимум энергии от пищи, ищут пропитание, исходя из соотношения калорийности и временных затрат на поиски и съедение. […]

Отбираем задачи

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

Это позволяет нам радикально переосмыслить проблему прокрастинации — классической патологии тайм-менеджмента. Мы привыкли думать, что это ошибочный алгоритм. А что, если все совсем наоборот? Что если это и есть оптимальное решение неправильной задачи?

В одном из эпизодов «Секретных материалов» главный герой Малдер, прикованный к постели (в буквальном смысле), вот-вот должен был пасть жертвой вампира-невротика. Чтобы спастись, он опрокинул на пол пакет с семечками. Вампир, бессильный перед своей психической болезнью, стал нагибаться, чтобы подобрать их, семечко за семечком. Тем временем наступил рассвет — раньше, чем Малдер стал добычей монстра. Программисты назвали бы такой метод атакой пингования или сетевой атакой типа «отказ в обслуживании»: если заставить систему выполнять бесконечное количество банальных задач, самые важные вещи будут утеряны в хаосе.

Обычно мы ассоциируем прокрастинацию с ленью и так называемым поведением избегания, но симптомы прокрастинации могут так же легко появиться и у людей (или компьютеров, или даже вампиров), которые искренне и с энтузиазмом стремятся сделать все дела как можно быстрее.

В ходе исследования, проведенного в 2014 году Дэвидом Розенбаумом из Пенсильванского университета, участников попросили отнести одно или два тяжелых ведра на противоположный конец коридора. Одно из ведер находилось рядом с участником исследования, второе — дальше по коридору. К удивлению экспериментаторов, люди сразу же хватали ведро, стоящее рядом с ними, и тащили его по коридору, при этом проходя мимо второго ведра, которое могли бы тащить всего часть дистанции. Как было отмечено исследователями, «этот на первый взгляд иррациональный выбор отражает предрасположенность к прокрастинации. Этот термин мы вводим, чтобы дать определение явлению, когда мы спешим выполнить какую-либо промежуточную задачу даже ценой дополнительных физических усилий». Откладывание решения большой задачи в пользу решения множества простых вопросов может быть аналогичным образом расценено как приближение осуществления промежуточной цели, что, другими словами, означает, что прокрастинаторы действуют (оптимально!) так, чтобы максимально быстро сократить количество нерешенных задач в их мыслях. Это не значит, что их стратегия неэффективна для выполнения задач. У них отличная стратегия, но для неверного критерия.

Работа с компьютером представляет определенную опасность, когда нам нужно осознанно и четко выбрать критерий планирования: пользовательский интерфейс может ненавязчиво (или навязчиво) заставить нас использовать его критерии. Современный пользователь смартфона, в частности, привыкает видеть на иконках приложений значки, сигнализирующие о том количестве задач, которое мы должны выполнить в каждом из них. Если почтовый ящик извещает нас об определенном количестве непрочитанных писем, то получается, что все сообщения по умолчанию имеют одинаковую значимость. В таком случае можно ли порицать нас за то, что мы выбираем невесовую модель алгоритма наименьшего времени обслуживания в решении этой задачи (в первую очередь разбирайся с самыми простыми письмами и оттягивай работу с самыми сложными до последнего), чтобы быстро уменьшить количество непрочтенных писем?

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

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

Смена приоритетов и управление очередностью

Стояло лето 1997 года, и у человечества было много поводов для радости. Например, впервые вездеход исследовал поверхность Марса. «Марсопроходец» стоимостью $150 млн развил скорость до 16 000 миль в час, пересек 309 млн миль пустого пространства и приземлился с помощью воздушных амортизаторов на красную скалистую поверхность Марса.

И тут он забуксовал.

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

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

Лихорадочно работая, команда лаборатории в конце концов смогла воспроизвести и затем диагностировать такое поведение. Корнем зла оказалась классическая опасность планирования под названием «смена приоритетов». Происходит следующее: задача с низким приоритетом захватывает для работы системный ресурс (скажем, доступ к базе данных), но затем таймер прерывает работу задачи на середине, ставя ее на паузу, и активирует диспетчер системы. Диспетчер готов запустить задачу с высоким приоритетом, но не может, поскольку база данных занята. Таким образом, диспетчер опускается ниже по списку очередности задач, запуская различные незаблокированные задачи средней важности вместо того, чтобы запустить задачу с наивысшим приоритетом (которая заблокирована) или задачу с низким приоритетом, которая и блокирует работу (и которая оказалась в самом конце списка очередности после задач среднего приоритета). В таком кошмарном сценарии система может игнорировать задачу высшего приоритета очень долго*.

* Что примечательно, руководитель группы по управлению программным обеспечением «Марсопроходца» считал, что проблема заключается в «давлении дедлайнов» и в том, что во время разработки программного обеспечения устранение именно этой проблемы сочли низкоприоритетной задачей. Таким образом, коренная причина, по сути, стала отражением самой задачи.

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

Комик Митч Хедберг рассказывает такую историю: «Я был в казино, отдыхал, вдруг ко мне подошел парень и сказал: «Вы должны пересесть. Вы заблокировали пожарный выход». Можно подумать, что я не собирался бежать, если бы начался пожар». Аргумент сотрудника казино: это смена приоритетов. Контраргумент Хедберга: наследование приоритетов. Хедберг, развалившийся на стуле перед пытающейся спастись бегством толпой, мешкая, ставит свою низкоприоритетную задачу над высокоприоритетной задачей людей, намеренных спасти свою жизнь. Но все изменится, если он унаследует их приоритет (перед наступающей в панике толпой ее приоритет наследуется довольно быстро). Как говорит Хедберг, «если вы состоите из горючих материалов и у вас есть ноги, вы никогда не блокируете пожарный выход».

Мораль этой истории в том, что даже любви к решению задач иногда бывает недостаточно, чтобы избежать роковых ошибок в планировании. И даже любви к решению важных задач — тоже. Готовность крайне скрупулезно решать самый важный вопрос с привычной нам близорукостью может привести к тому, что весь мир называет прокрастинацией. Как в случае с застрявшим автомобилем: чем сильнее вы хотите выбраться, тем больше буксуете. По утверждению Гёте, «то, что значит больше, никогда не должно быть во власти того, что значит меньше». И хотя в этом есть определенная мудрость, иногда такое утверждение не совсем справедливо. Зачастую то, что значит для нас больше всего, не может быть сделано, пока не закончено самое незначительное дело. Поэтому единственный выход — это относиться к неважным вещам с той же важностью, как и к тем, выполнение которых они тормозят.

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

В 1978 году исследователь Ян Карель Ленстра смог использовать тот же принцип, помогая другу Джину с переездом в новый дом в Беркли. «Джин постоянно откладывал какое-нибудь дело, не закончив которое мы не могли приступить к срочным вопросам». Как вспоминает Ленстра, они должны были вернуть грузовик, но он был им нужен, чтобы вернуть некоторое оборудование, а оборудование было нужно, чтобы починить кое-что в квартире. Этот ремонт мог подождать (поэтому все и откладывалось), но вернуть грузовик нужно было срочно. По словам Ленстра, он объяснил другу, что задача, предшествующая самой срочной, является еще более срочной. Поскольку Ленстра известен как ключевая фигура в теории планирования и был более чем вправе дать такой совет, он не удержался от деликатной иронии. Эта ситуация стала кейсом, демонстрирующим смену приоритетов из-за управления очередностью. А пожалуй, самым выдающимся экспертом в области управления очередностью, считается как раз друг рассказчика — тот самый Джин, или Юджин Лоулер.

Ограничитель скорости

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

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

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

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

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

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

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

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

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

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

 

https://theoryandpractice.ru