Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

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

Далее мы рассмотрим только один крошечный класс такой литературы, где в отличие от переплетного дела или прачечной необходимо планировать работу одного устройства. Существенная для нас проблема планирования действительно касается только одного устройства – нас самих.

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

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

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

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

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

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

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

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

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

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

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

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

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

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