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

Примечательно, что хорошо известный алгоритм Грэма [15], LIST SCHEDULING, который определен для идентичных машин, пригоден как для временных, так и для постоянных задач. Этот алгоритм жадным образом назначает новое задание наименее загруженной машине. Коэффициент конкурентоспособности этого алгоритма составляет 2 - 1/м, что является наилучшим возможным значением (см. [ ]). Отметим, что коэффициент конкурентоспособности здесь тот же, что и для постоянных задач, однако для постоянных задач можно достичь коэффициента конкурентоспособности, который не стремится к 2 для больших m – см., например, [11].

Для равномерно связанных машин ситуация не слишком отличается. В этом случае алгоритмы Аспнеса и др. [3], а также Бермана и др. [ ] не могут применяться в исходном виде и требуют определенных модификаций. Алгоритм Азара и др. [7] имеет коэффициент конкурентоспособности не выше 20; он основан на общем методе, предложенном в [ ]. Алгоритм в работе [3] сохраняет предполагаемое значение Я, которое является оценкой стоимости оптимального оффлайнового алгоритма OPT. Инвариантом, который необходимо сохранить, является Я < 2OPT. На каждом шаге процедура применяется для некоторого значения Я (которое может быть инициализировано как загрузка первого задания на самой быстрой машине). Процедура для заданного значения Я применяется до тех пор, пока она не завершится неудачей, т.е. некоторое задание не может быть назначено, несмотря на выполнение всех условий. Процедура спроектирована таким образом, что в случае, когда она завершается неудачей, а это должно быть при ОПТ > Я, значение Я удваивается, и процедура повторяется для нового значения, игнорируя все назначения, выполненные для малых значений Я. Этот подход называется методом удвоения, в результате чего получается алгоритм с коэффициентом конкурентоспособности, который не более чем четыре раза превышает коэффициент конкурентоспособности, достигнутый процедурой. Процедура для заданного Я действует следующим образом. Пусть будет целевым коэффициентом конкурентоспособности для процедуры будет c. Машины сортируются по их скорости. Каждое задание назначается первой машине согласно порядку сортировки, такой, что задание может быть ей назначено. Задание j, поступающее в момент времени t, может быть назначено машине i, если pj/si < Я and l)~l + pj/si < cX. В работе [ ] было показано, что c = 5 позволяет алгоритму успешно назначать все задания (т. е. иметь хотя бы одну допускающую назначение машину для каждого задания), до тех пор, пока OPT < Я. Заметим, что константа c для постоянных задач, используемая в [ ], равна 2. Что касается нижних границ, то в [ ] было показано, что коэффициент конкурентоспособности R любого алгоритма удовлетворяет условию R > 3 - o(1). Верхнюю границу до значения 6 + 2 p5 улучшили Бар-Ной и др. [9].