Теория расписаний – это научная дисциплина, посвящённая методам оптимизации календарного планирования.

Задачи теории расписаний состоят в определении оптимальной очереди выполнения работ, распределения работ по рабочим местам.

Задачи теории расписаний постоянно возникают как при планировании производственных процессов, так и в повседневной жизни. Например, студент в течение дня планирует сделать несколько дел: посетить занятия (с 10.15 до 15.00), отремонтировать телефон (мастерская работает с 9.00 до 19.00), посетить зубного врача (прием с 9.00 до 17.00), купить продукты в супермаркете (с 9.00 до 21.00).

Естественно, чтобы успеть всё это сделать, нужно составить план действий:

1) На 9.00 зайти в приёмную врача и взять талон на удобное время, например, на 15.30 или 16.00.
2) Сдать телефон в ремонт, выяснить, на который час будет готов заказ.
3) Успеть на занятия к 10.15.
4) Посетить врача (время посещения врача было спланировано заранее, а у мастера по ремонту появляется дополнительное время).
5) Забрать телефон из ремонта.
6) Купить продукты (это делается в последнюю очередь, чтобы меньше носить тяжёлую сумку, и супермаркет закрывается позднее остальных нужных заведений).

Типичной задачей теории расписаний является составление расписания занятий. Это довольно сложная задача, поскольку в данном случае должны быть воедино сведены четыре категории – время проведения, учебная группа, преподаватель и аудитория.

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

В настоящий момент такие задачи всё чаще поручаются компьютерам, вернее, специально сделанным для этого программам.

У истоков создания теории расписаний стоял выдающийся американский инженер Генри Лоуренс Гантт (Henry Laurence Gantt, 1861–1919). 

Гантт впервые применил аналитические методы для исследования последовательности выполнения производственных операций и разработал методы их планирования.

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

Продвигая идею временных (с ударением на последнем слоге) диаграмм, Гантт приводил такие аргументы:

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

Диаграмма Гантта оказалась таким мощным аналитическим инструментом, что в течение почти ста лет не претерпевала изменений.

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

Это явление американский учёный Ричард Беллман назвал «проклятием размерности» (более подробно о научном наследии Беллмана см. в статье «Динамическое программирование», №8, 2018).

Например, 30 работ можно упорядочить 30! способами. Это число имеет порядок 10³². С перебором такого количества вариантов не справится никакой компьютер. Поэтому применяются приближённые методы дискретной оптимизации, которые находят оптимальное расписание с некоторой приемлемой ошибкой.

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

Задача красильщика

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

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

Обозначим время покраски i-й детали через t(i) а время подсушки – через b(i). Пусть расписание задаётся некоторой перестановкой номеров деталей. Например, перестановка (5, 3, 1, 4, 2) означает, что вначале красится деталь номер 5, затем 3, затем 4, 1, и наконец 2.

Назовём временем готовности детали z(i) момент времени, к которому она подсыхает после покраски. Эта величина рассчитывается просто – время покраски детали плюс время её подсушки плюс сумма времён покраски всех деталей, стоящих перед ней. А время готовности заказа равно максимуму из времён готовности всех деталей.

Покажем это на простом примере. Пусть есть три детали. t(1)=5, b(1)=4, t(2)=3, b(2)=7, t(3)=1, b(3)=5. Внесём исходные данные в таблицу и вычислим по ним величины z(i):

Пусть детали красятся в порядке (1, 2, 3). Тогда времена их готовности равны: z(1)=5+4=9, z(2)=5+3+7=15, z(3)=5+3+1+5=14, а время выполнения заказа равно max(9,15,14)=15.

Рассмотрим некоторое расписание, в котором есть две соседние работы i и j, стоящая непосредственно после i, и при этом b(j)>b(i).

Пусть суммарное время покраски деталей, стоящих перед i, равно T. Тогда i будет готова к моменту T+t(i)+b(i), а j – к моменту T+t(i)+t(j)+b(j). Рассмотрим альтернативное расписание, в котором лишь изменим порядок покраски i и j (теперь i будет краситься после j), а порядок покраски остальных деталей останется неизменным. Тогда i будет готова к моменту T+t(i)+t(j)+b(i), а j – к моменту T+t(j)+b(j).

Покажем, что при такой перестановке деталей i и j максимальное время готовности деталей i и j не увеличится (а если времена покраски деталей строго больше нуля, то уменьшится). Действительно, в первом случае искомая величина равна

max(T+t(i)+b(i), T+t(i)+t(j)+b(j)) = T+t(i)+t(j)+b(j), а во втором –

max(T+t(i)+t(j)+b(i), T+t(j)+b(j)). Заметим, что величина T+t(i)+t(j)+b(j), с одной стороны, больше, чем T+t(i)+t(j)+b(i), с другой стороны, больше, чем T+t(j)+b(j), отсюда

max(T+t(i)+b(i), T+t(i)+t(j)+b(j)) > max(T+t(i)+t(j)+b(i), T+t(j)+b(j)).

Заметим также, что время готовности остальных деталей (как тех, что стоят перед парой i и j, так и стоящих после неё) не изменилось. Таким образом, время выполнения заказа при переходе к альтернативному расписанию не увеличилось.

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

Заметим, что полученный результат может применяться не только к планированию порядка покраски деталей. К тому же, «задача красильщика» – это просто условное название класса задач теории расписаний, который объединяет ситуации, в которых каждая работа состоит из двух этапов, причём первый этап всех работ выполняется одним и тем же человеком, а второй этап начинает выполняться сам по себе, как только закончен первый.

Например, пусть некто хочет совершить поездку за границу, для чего ему нужно получить визы в посольствах А и В.

Пусть подготовка документов в А занимает 3 дня, а после подачи документов нужно ждать 8 дней, а для посольства В эти величины составляют 4 и 6 дней соответственно.

В данном случае, поскольку b(A) = 8, b(B) = 6, b(A) > b(B), то правильным порядком подготовки документов будет А, В. В этом случае документы из А будут получены через 3+8 = 11 дней, а документы из В – через 3+4+6 = 13 дней. Таким образом, время готовности всего пакета документов составит max(11,13) = 13. При порядке подготовки В, А документы из В будут получены через 4+6 = 10 дней, а документы из А – через 4+3+8 = 15 дней, таким образом, время готовности всего пакета документов составит max(10,15) = 15.

Другой пример – приготовление обеда.

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

Картошка чистится 15 мин. и варится 20 мин.

Курица моется и фаршируется 10 мин., затем запекается 40 мин.

Компоненты для супа готовятся 30 мин, затем суп варится 60 мин.

Здесь есть три работы, каждая из которых состоит из двух стадий, причём первая стадия выполняется при участии хозяйки, вторая – без неё.

Занесём исходные данные в таблицу:

Расположим блюда в порядке убывания времени «подсушки» (варки) – сначала суп, затем курица, затем картошка.

Результаты расчёта приведены в следующей таблице, где

t_i – время подготовки, T_i – время готовности к варке,

b_i – время варки, T_i + b_i – время готовности блюда.

Обед будет готов, когда будут готовы все блюда.

Диагамма Гантта готовки обеда при расписании (суп, курица, картошка) имеет вид:

Поскольку в данном случае есть три работы, то количество возможных расписаний равно 3!=6. Время готовности блюд и всего обеда для всех возможных расписаний приведено в таблице.

Читателю предлагается самостоятельно построить диаграмму Гантта для какого-либо из неоптимальных расписаний.

С.И. Доценко, кандидат физико-математических наук, старший научный сотрудник факультета компьютерных наук и кибернетики, КНУ имени Тараса Шевченко