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

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

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