§ 3. Задача теории расписаний для случая двух машин (алгоритм Джонсона)

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

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

3.2. Опишем известный алгоритм Джонсона (см. [98], гл. 2) для получения оптимального расписания. Идея его состоит в стремлении максимально сократить простои второй машины.

Шаг 1. Среди чисел находим наименьшее (если таких чисел несколько, берем произвольное из них). Если то полагаем т. е. помещаем деталь на первое место в расписании. Если же то полагаем т. е. помещаем деталь на последнее место в расписании.

Затем вычеркиваем деталь (т. е. числа ) из списка и переходим ко второму шагу.

Шаг Среди чисел еще не вычеркнутых на предыдущих шагах, находим наименьшее (если таких чисел несколько, то берется произвольное). Если то помещаем деталь в расписании на первое из мест, еще не занятых на предыдущих шагах; если же то помещаем деталь в расписании на последнее из незанятых мест.

Затем вычеркиваем деталь (т. е. числа и из списка и переходим к шагу.

Шаг Единственную оставшуюся в списке деталь помещаем на единственное оставшееся в расписании место.

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

(см. скан)

Таким образом, оптимальное расписание есть

Напомним, что прямой перебор потребовал бы сравнения перестановок.

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

Обозначим через

суммарное время обработки при заданном «опережении» и расписании Заметим, что функция монотонно возрастает по

Задачу с заданным и деталями будем обозначать через

Для функции имеет место следующая формула:

Действительно, через время 2 на первой машине закончится обработка деталей и начнется обработка деталей через время закончится обработка деталей на второй машине, и эта машина освободится для обработки деталей Отсюда и следует формула (3.1). 3.5. В обосновании алгоритма Джонсона основную роль играет Лемма 3.1. Алгоритм Джонсона дает оптимальное расписание (при любом ) для задачи с двумя деталями

Прежде чем доказывать лемму, покажем, как выводится из нее Теорема 3.1. Алгоритм Джонсона дает оптимальное расписание (при любом ) для задачи с произвольным количеством деталей

Доказательство проведем индукцией по числу деталей. При теорема совпадает с леммой.

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

I случай.

В формуле (3.1) положим и получим

Из (3.2) следует, что расписание является оптимальным расписанием для задачи где .

Согласно индукционному предположению расписание задачи полученное по алгоритму Джонсона, также будет оптимальным, и следовательно,

Из (3.3) следует, что расписание также будет оптимальным для задачи Так как расписание может быть получено по алгоритму Джонсона, то теорема для этого случая доказана.

II случай.

В формуле (3.1) положим и получим

Из отмеченной выше монотонности функции по следует, что если оптимальное расписание для задачи то оптимальное расписание для задачи Возьмем в качестве оптимальное расписание задачи найденное по алгоритму Джонсона. Тогда и расписание » О может быть получено по алгоритму Джонсона, и теорема доказана.

III случай.

Рассуждая так же, как и в случае I, получим, что существует такое оптимальное расписание задачи что расписание задачи может быть получено по алгоритму Джонсона. В частности, можно считать, что

Теперь из формулы (3.1) (положим сначала а затем ), получим

и

Из леммы и формулы (3.5) следует, что

следовательно,

и (с учетом (3.6) и (3.7))

Из (3.8) и из оптимальности расписания что расписание также является оптимальным. Но в силу (3.5) мы получили случай I, для которого теорема уже доказана.

IV случай.

Рассуждая так же, как и в случае II, получим, что существует такое оптимальное расписание задачи что расписание является оптимальным расписанием для задачи построенным по алгоритму Джонсона, причем Теперь из формулы (3.1) получаем

Из леммы следует, что

Из (3.10), (3.11), (3.12) и из монотонности по получаем

Из (3.13) и из оптимальности расписания

следует, что расписание также является оптимальным. Но в силу (3.9) получается случай II, рассмотренный выше.

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

3.6. Переходим к доказательству леммы. Достаточно доказать следующие два утверждения:

а) Если то расписание оптимальное, т. е. .

б) Если то расписание оптимальное, т. е.

Сначала выведем выражение для Согласно (3.1)

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

Из (3.15) и (3.14) получаем

Из (3.16) получаем

При доказательстве леммы рассмотрим отдельно два случая:

Каждый из этих случаев разобъем на четыре подслучая:

Случай

Из (3.19) следует, что

следовательно,

и расписание является оптимальным.

Случай

Из (3.24) получаем

откуда (с учетом следует, что

Из (3.31) и (3.24) получаем далее

откуда следует, что

и (с учетом

Из (3.29) — (3.32) получаем

Расписание оптимальное. Случай

Имеем

Очевидно,

Из (3.19) следует, что

Из (3.33) - (3.35) получаем

Расписание оптимальное.

Случай

Из (3.28) следует, что

Из (3.38) и (3.19) получаем

Из (3.39), (3.36), (3.37) и (3.19) вытекает неравенство

Расписание оптимальное.

Случай

Допустим, что

т. е. что

Отсюда получим

и

Из (3.20) следует, что

Складывая (3.41) и (3.42), имеем

что противоречит (3.22). Следовательно, (3.40) не выполняется и

Расписание оптимальное.

Случай

Допустим, что

т. е. что

Из (3.44) и (3.24) получаем

т. е.

и

Из (3.45) и (3.44) получаем

что противоречит (3.20). Следовательно, (3.43) не выполняется. Расписание оптимальное.

Случай

Допустим, что

т. е.

Из (3.47) и (3.25) получаем

т. е.

что противоречит (3.20). Следовательно, (3.46) не выполняется. Расписание оптимальное.

Случай

Отсюда и из (3.20) получаем

Расписание оптимальное.

Все случаи разобраны. Лемма доказана. Алгоритм Джонсона обоснован.

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