5.4. Сформулировать задачу Беллмана-Джонсона.
Предположим, что к условиям сформулированной задачи ТР добавлены еще два условия:
VI) технологический маршрут для всех заявок одинаков;
VII) последовательность запуска заявок в обслуживание на всех приборах одинакова.
Как и в предыдущей модели, задача состоит в том, чтобы для заданного технологического маршрута и соответствующих временах обслуживания заявок в условиях I) – VII) найти такие моменты начала обслуживания каждой заявки на любом приборе, при которых общее время обслуживания всех заявок будет минимальным.
Не уменьшая общности, условие VI) можно сформулировать в виде:
VI) Технологический маршрут для всех заявок одинаков и имеет вид
.
Условие
VII)
по существу означает, что очередность
обслуживания заявок будет определена,
если определятся моменты
,
начала обслуживания каждой заявки на
первом приборе при оговорке, что на
остальных приборах обслуживание будет
начинаться настолько рано, насколько
это позволяют условия обслуживания.
5.5. Описать множество допустимых решений в задаче Беллмана-Джонсона.
Можно
утверждать, что конкретные моменты
взаимно однозначно определяют перестановку
чисел
1,2, …,
,
причем каждый элемент
в такой перестановке является номером
заявки, которая будет обслуживаться в
расписании
-ой
по порядку. Известно, что имеется
возможных перестановок чисел 1,2, …,
.
Среди такого количества перестановок
в задаче Б-Д необходимо найти оптимальную.
5.6. Как найти общее время обслуживания заявок в задаче Беллмана-Джонсона при заданной очередности обслуживания?
Если
какая-то перестановка
задана, то анализ задачи Б-Д сводится
к анализу специального сетевого графика,
который имеет следующую структуру.
Вершины этого сетевого графика означают
операцию по обслуживанию на соответствующих
приборах. Если какая-то операция
выполняется для заявки
,
то после нее могут быть выполнены только
две из возможных операций: или будет
выполняться операция по обслуживанию
этой заявки на очередном приборе, или
на этом же приборе будет обслуживаться
очередная в расписании заявка. Эти
варианты переходов будем рисовать в
виде стрелок.
В итоге получим сетевой график следующего вида:
Как известно, для того, чтобы найти общее время обслуживания в комплексе работ, представленных в сетевом графике, достаточно найти длину критического пути из начальной в конечную вершину (в нашем случае это вершины A и В).
Любой
путь из вершины А
в
В
можно представить в виде вертикальных
и горизонтальных отрезков от номера 1
до номера
в первой колонке, от
до
во второй колонке, и так далее … от
до
в m-й
колонке:
При
длина такого пути будет равна:
.
Тогда
критическое время из
в
будет равно
.
5.7. Сформулировать теорему об оптимальном расписании в задаче Беллмана-Джонсона с двумя приборами.
Tеорема
3.1.1.
В
оптимальном расписании для задачи Б-Д
с двумя приборами заявка
обслуживается ранее заявки
,
если выполняется неравенство
.
(5.1.3)
Неравенство
(5.1.3) обладает свойством транзитивности,
т.е. если оно выполняется для пар
,
и
,
,
то оно будет выполняться и для пары
.
Алгоритм Джонсона.
Шаг
1.
Выписывается таблица времен обслуживания
заявок, состоящая из
строк и двух столбцов. Одновременно
готовится строка из
пустых позиций.
Шаг 2. В таблице ищется минимальный элемент. Если он принадлежит первому столбцу, то номер его строки записывается в первую слева свободную позицию подготовленной строки. Если этот минимум принадлежит второму столбцу, то номер его строки записывается в первую справа свободную позицию. В любом случае строка, где был минимум, вычеркивается из таблицы времени обслуживания. Шаг 2 повторяется, пока не заполнятся все пустые позиции подготовленной строки. Этим самым определится оптимальное расписание.
Если потребуется выбор из нескольких одинаковых минимумов, то можно выбирать любой из них. При выборе иного минимума может получиться иное оптимальное расписание.