Списочное планирование: различия между версиями

(3) <math>1X + L \le OPT + \frac{m - 1}{m} L \le OPT + \frac{m - 1}{m} OPT = (2 -\frac{1}{m} OPT)</math>

Чтобы показать, что анализ является строгим, рассмотрим m(m - 1) заданий размера 1, за которыми следует одно задание размера m. После поступления меньших заданий LS получает сбалансированное расписание, в котором каждая машина имеет нагрузку m - 1. Следующее, большое задание увеличивает продолжительность работы до 2 m - 1. Однако оптимальным решением в автономном режиме было бы назначить задания меньшего размера m - 1 машине, а оставшееся задание – оставшейся машину, в результате чего мы получим нагрузку m.

Естественным образом возникает вопрос, является ли эта граница наилучшей. В одной из последующих работ Грэм [ ] показал, что применение алгоритма LS к отсортированной последовательности заданий (в порядке невозрастания размеров) на самом деле дает улучшенную верхнюю границу коэффициента аппроксимации, равную 4 - j^. Схему аппроксимации с полиномиальным временем выполнения предложили Хохбаум и Шмойс в работе [10]. Это лучший оффлайновый результат, на который можно было бы надеяться, поскольку, как известно, задача является NP-трудной в сильном смысле.

Что касается онлайновой задачи, то в статье [ ] было показано, что ни у одного (детерминированного) алгоритма коэффициент конкурентоспособности не может быть меньше 2 – 1, что верно для случаев m = 2 и m = 3. С другой стороны, в серии работ было показано, что алгоритм с меньшим коэффициентом конкурентоспособности можно найти для любого значения m > 4, и даже были разработаны алгоритмы с коэффициентом конкурентоспособности, не приближающимся к 2 для больших m.

Наилучший такой результат получили Флейшер и Валь [6], разработавшие 1,9201-конкурентный алгоритм. В [1, 7] были представлены нижние границы коэффициента конкурентоспособности для любого онлайнового алгоритма, равные 1,852 и 1,85358. Рудин [13] также улучшил нижнюю границу – до 1,88.