Лекция 4. Задача Джонсона в теории расписаний

Задача Джонсона в теории расписаний. Случаи двух и трех машин.

Сформулируем классическую задачу теории расписаний - задачу Джон-сона:

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

В этой постановке задачи предполагается, что

1) в любой момент времени на одной машине выполняется не более одной работы;

2) в любой момент времени одна работа выполняется не более, чем на

одной машине.

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

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

Шаг 0. Записывается матрица времен выполнения данных работ.

Шаг 1. В матрице фиксируется минимальный элемент (любой); если он оказался в первом столбце (машина №1), то соответствующую работу назначают первой к исполнению; если он оказался во втором столбце (машина №2), то соответствующую работу назначают последней к исполнению.

Шаг 2. Исключают из дальнейшего рассмотрения время выполнения упорядоченной работы (т.е. вычеркивают из матрицы строку). Если после этого от матрицы ничего не остается, то задача решена; в противном случае переходим к Шагу 1.

Напомним, что описанный алгоритм минимизирует суммарное время простоя обеих машин.

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

пусть по-прежнему - множество работ, которые выполня-

ются на двух машинах (№1 и №2), пусть по-прежнему - - время выполнения i- ой работы на j- ой машине, но:

N ₁ - подмножество работ, которые выполняются только на первой маши-не;

N ₂ - подмножество работ, которые выполняются только на второй маши-не;

N _1,2 - подмножество работ, которые выполняются сначала на первой, а потом на второй машине;

N _2,1 - подмножество работ, которые выполняются сначала на второй, а потом - на первой машине.

Таким образом, .

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

1) в соответствии с алгоритмом Джонсона для последовательного

варианта задачи для двух машин упорядочим работы из множеств N _1,2 и N _2,1;

2) на первую машину запускаются сначала работы из N _1,2, затем - из

N ₁, а затем - из N _2,1;

3) на вторую машину запускаются сначала работы из N _2,1, затем - из

N ₂, а затем - из N _1,2.

Рассмотренный общий случай задачи Джонсона для двух машин часто называют смешанным вариантом задачи Джонсона.

Рассмотрим иллюстративный пример смешанного варианта задачи Джонсона для двух машин. Условие задается следующей таблицей:

N		N_1,2				N_2,1		N₁		N₂
М\Р	р₁	р₂	р₃	р₄	р₅	р₆	р₇	р₈	р₉	р₁₀	р₁₁
М₁
М₂

здесь р_j - имя работы, М_i - имя машины.

По алгоритму Джонсона:

оптимумы для N _1,2 и N _2,1, соответственно: (р₂,р₁,р₄,р₃) и (р₇,р₆,р₅);

оптимальные режимы работ.

Машина №1: (р₂,р₁,р₄,р₃,(р₈,р₉), р₇,р₆,р₅);

Машина №2: (р₇,р₆,р₅,(р₁₀,р₁₁), р₂,р₁,р₄,р₃).

Записи (р₈,р₉) и (р₁₀,р₁₁) означают, что порядок выполнения

этих работ - произвольный.

Перейдем к случаю трех машин.

Ограничимся здесь далеко не общей ситуацией; итак,

m =3 - число машин;

- множество работ;

- время выполнения i-ой работы на j-ой машине;

предполагается, что у все работ одна и та же последователь-

ность прохождения по машинам.

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

Утверждение №1. Пусть работы можно пронумеровать так, что окажутся выполненными одновременно следующие неравенства:

Тогда суммарный простой машин будет минимальным при следующем порядке запуска работ на исполнение: 1¾2¾...¾ n.

Утверждение №2. Пусть для матрицы выполнено хотя бы одно из двух следующих условий:

Построим новую матрицу , в которой i= 1,2,..., n, j= 1,2 и , и будем считать ее матрицей времен задачи Джонсона для двух машин в последовательном варианте и множества тех же работ . Тогда суммарное время простоя исходных трех ма-шин при выполнении исходных работ будет минимальным, если эти работы направлять на исполнение в том порядке, который является оптимальным в задаче с матрицей .