Балансировка нагрузки: различия между версиями

Альтернативный алгоритм под названием ROBIN HOOD был предложен в работе [7]. Этот алгоритм сохраняет нижнюю границу на OPT, которая представляет собой максимум из двух следующих функций. Первой из них является максимальная средняя загрузка машины за прошедшее время работы алгоритма. Второй – максимальный размер задания среди всех, поступивших за это время. Обозначим эту нижнюю границу на время t (после того, как произошли t событий) за <math>B^t</math>. Машина i называется «богатой» в момент времени t, если <math>L^t_i \ge \sqrt{m B^t}</math>. В противном случае она называется «бедной». Временем «удачи» богатой машины i является такой момент времени t, что в момент времени t' - 1 она еще является бедной, а в моменты t', ..., t, – уже богатой; т. е. именно в этот момент машина i перешла в разряд богатых. Очевидно, что машины могут стать бедными из-за обновления <math>B^t</math> или убытия заданий. Стать богатой машина может в результате поступления заданий, назначенных ей.

Заметим, что для малых значений m <math>(m \le 5)</math> коэффициент конкурентоспособности жадного алгоритма все еще является наилучшим, как было показано в [1]. В данной работе было показано, что для эта граница равна (m + 3)/2 для m = 3, 4, 5. Нетрудно заметить, что для m = 2 лучшая граница равна 2.

Самая большая разница возникает в случае несвязанных машин. В отличие от случая постоянных задач, в котором может быть достигнута верхняя граница O(log m) [3], в [2] было показано, что любой алгоритм имеет коэффициент конкурентоспособности <math>\Omega(m / log \; m)</math>. Отметим, что у тривиального алгоритма, который назначает каждое задание машине, имеющей имеет минимальную нагрузку, коэффициент конкурентоспособности не превышает m [3].