2.2.Параллельные машины.Полиномиально разрешимые задачи

Unrelated Machines

Задача R|prmp|Cmax как задача лин. прог.:

$Cmax Ñ min;

txu

операция Oij фрагмент Jj, выполняющ. на Mi

ppOijq xijpij длина операции (длина фрагм. Jj íà Mi)

операции могут прерываться: величины x

ij из решения определяют только общую долю фрагментов Jj íà Mi.

Очевидно, допустимым расписаниям этого примера соответствуют допустимые расписания для R|prmp|Cmax.

Позже убедимся, что задача O|prmp|Cmax P P и, кроме того, длина оптимального расписания совпадает с

Задачи P || °Cj è P |pj 1| °wjCj

Ранее рассматривали похожую задачу: 1|| ° wjCj. Äëÿ åå решения был предложен алгоритм W SP T : упорядочение работ по невозрастанию отношения wj{pj:

Оказывается, это правило определяет оптимальное решение наших задач.

Лемма 1

Пусть x; y P Nn, причем: x1 ¤ x2 ¤ ¤ xn, à P Sn. Рассмотрим следующую задачу:

n

fpx; y; q ¸ xiy i Ñ min :

i 1

t u

Решением является перестановка : y 1 ¥ y 2 ¥ ¥ y n .

Доказательство. Пусть в опт. пер. для некоторого i: y i y i 1 . Поменяем местами эти два элемента: получим пер. 1.

l1 l pl i; i 1q; i1 i 1; i1 1 i:

Вычислим значение функции на этой перестановке:

fpx; y; q fpx; y; 1q x i y i x i 1 y i 1 x i y i 1 x i 1 y i

px i x i 1 qpy i y i 1 q ¡ 0:

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

Algorithm 3 (Решения задач P || ° Cj è P |pj 1| ° wjCj)

1:Перенумеровать работы согласно W SP T (то есть, для пер-

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

2:Перебирая машины по порядку, назначать на каждую машину первую из еще не назначенных работ.

Теорема 3

Алгоритм 3 строит оптимальное решение задач P || ° Cj è P |pj 1| ° wjCj с трудоемкостью Opn ln nq.

Доказательство. Докажем для P || ° Cj (для второй задачи доказательство аналогично).

Добавим в J несколько работ длительности 0 так, чтобы n было кратно m. Очевидно, в опт. расп. эти работы назначаются в t 0, и значение критерия то же, что и в исходной задаче.

Пусть оптимальное расписание. Обозначим:

J i мн.-во работ, выполняющихся на Mi, ni |J i| количество работ на Mi,

pi1; pi2; : : : ; pini длит.-сти работ из J i в порядке вып. на

Mi.

Вклад работ из J i в целевую функцию равен:

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

loooooooooooooooooooomoooooooooooooooooooonпервые работы

Заметим, что значение критерия может быть уменьшено, если найдутся две машины Mi è Ml такие, что ni nl ¡ 1. Действительно, пусть нер.-во выполнено, преобразуем в 1:

работу, вып. первой на Mi, уберем с этой машины и назначим первой на Ml. Ïðè ýòîì,

Cjp q ¸ Cjp 1q nipi1;

Cjp q ¸ Cjp 1q pnl 1qpi1;

nn

Следовательно, в опт. расп. ni отличаются друг от друга не более, чем на 1. Так как n кратно m, то ni n1 äëÿ âñåõ i.

Применим Лемму 1, взяв в качестве x последовательность коэффициентов, а в качестве y последовательность длительностей работ:

x tt1um; t2um; : : : ; tn1umu ;

y tpin1 ui¤m; tpin1 1ui¤m; : : : ; tpi1ui¤m( :

По Лемме, значение критерия достигает минимума, если последовательность y не возрастает: первыми выполняются самые короткие работы, вторыми более длинные и т.д. То есть, работы упорядочены согласно W SP T .

Теорема 4

Алгоритм 3 строит приближенное решение задачи P || ° wjCj ñ

Доказательство. Не приводится. Основывается на наблюдении: наихудшую точность W SP T -упорядочение

демонстрирует в случае, когда величины wj{pj одинаковы для âñåõ j.

[Uwe Schwiegelshohn: An alternative proof of the Kawaguchi-Kyan bound for the Largest-Ratio-First rule. Oper. Res. Lett. 39(4): 255-259 (2011)]