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

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

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

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

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

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

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

Бросьте все: приоритетное прерывание и неопределенность

Лучшее время, чтобы посадить дерево, было 20 лет назад. Следующее лучшее время – сегодня.

Пословица

До этого момента мы обсуждали факторы, которые усложняли планирование. Но есть и способ облегчить этот процесс, а именно возможность прекратить выполнение одной задачи и переключиться на другую. Это действие – «приоритетное прерывание» – способно кардинально изменить ход игры.

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

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

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

Сейчас при хорошем раскладе работники механического цеха могут четко знать все, что им предстоит делать в ближайшие несколько дней, но большинство из нас привыкли работать «вслепую», по крайней мере отчасти. Мы даже можем не догадываться, например, когда мы сможем приступить к определенному проекту (когда мы получим ту или иную информацию от того или иного человека). И в любой момент телефонный звонок или электронное письмо могут добавить новую задачу в наш график. Оказывается, что, даже если вы не знаете, когда сможете начать решать вопросы, схемы скорой даты исполнения и наименьшего времени обслуживания по-прежнему остаются оптимальными стратегиями, которые могут гарантировать вам (в среднем) лучший возможный результат в условиях неопределенности. Если новые задания появляются на вашем столе абсолютно непредсказуемо, то оптимальной стратегией для минимизации максимального времени опоздания как раз является схема скорой даты исполнения с возможностью приоритетной остановки – когда вы можете переключиться с текущего вопроса на новый, с более горящими сроками, или же игнорировать его. Похожим образом схема наименьшего времени обслуживания с возможностью приоритетного прерывания – когда требуется сравнить время, которое необходимо вам для завершения текущего дела и для выполнения нового, – остается оптимальной для минимизации суммы времен выполнения.