Минимальная продолжительность потока: различия между версиями

Для случая, когда вытеснение не разрешено, Келлерер, Таутенхан и Вёгингер [6] предложили аппроксимационный алгоритм с коэффициентом <math>O(n^{1/2})</math> для минимизации продолжительности потока на одной машине, а также показали, что ни один алгоритм с полиномиальным временем выполнения не может иметь коэффициента аппроксимации <math>n^{1/2 - \epsilon}</math> для любого <math>\epsilon > 0</math>, если только не выполняется соотношение P=NP.

Леонарди и Раз [8] представили первые нетривиальные результаты по минимизации средней продолжительности потока на нескольких машинах. Позже более простое представление этоих результатов было дано Леонарди в работе [7]. Основной результат [8] состоит в следующем.

'''Теорема 1 [8]. На нескольких машинах алгоритм SRPT является <math>O(min(log(n/m), \; log \; P))</math>-конкурентным для минимизации средней продолжительности потока, где P – отношение максимального размера задания к минимальному.'''

'''Теорема 2 [8]. Для задачи минимизации продолжительности потока на нескольких машинах любой онлайновый алгоритм имеет коэффициент конкурентоспособности <math>\Omega(min(log(n/m), \; log \; P))</math>, даже если разрешена рандомизация.'''

Заметим, что минимизация средней продолжительности потока эквивалентна минимизации общей его продолжительности. Предположим, что каждое задание выплачивает 1 доллар за каждую единицу времени, когда оно живо (т. е. не завершено), тогда сумма полученных платежей равна общей продолжительности потока. Суммируя оплату за каждый временной шаг, общую продолжительность потока можно выразить как сумму по количеству незавершенных заданий в каждую единицу времени. Поскольку SRPT работает с заданиями, которые могут быть завершены как можно скорее, интуитивно кажется, что в любой момент времени он должен наименьшее количество незавершенных заданий. Для одной машины это верно, однако для нескольких машин это не так (что показано в примере ниже). Основная идея работы [8] заключалась в том, чтобы показать, что в любой момент времени количество незавершенных работ в рамках SRPT «по сути» не более чем в O(min(log P)) раз больше, чем при любом другом алгоритме. Для этого авторы разработали технику группировки заданий в логарифмическое число классов в соответствии с их оставшимися размерами и рассуждений о суммарном объеме незавершенной работы в этих классах. С тех пор эта техника нашла широкое применение для получения других результатов. Чтобы получить гарантию, выраженную относительно n, требуются некоторые дополнительные идеи.

Приведенный ниже пример показывает, как SRPT может отклоняться от оптимума при наличии нескольких машин. Этот пример также является ключевым компонентом в построении нижней границы в Теореме 2. Предположим, у нас имеются две машины, и три задания размером 1, 1 и 2 поступают в момент времени t = 0. SRPT запланирует два задания размером 1 на момент времени t = 0, а затем будет работать над заданием размером 2 в момент времени t = 1. Таким образом, в момент t = 2 у него остается одна единица незавершенной работы. Однако оптимальный вариант может запланировать работу размера 2 на момент времени 0 и завершить все эти работы к моменту времени 2. Затем, в момент времени t = 2, поступают еще три задания с размерами 1/2, 1/2 и 1. Опять же, SRPT сначала будет работать над заданиями размера 1/2, и можно увидеть, что у него будет два незавершенных задания с оставшимся объемом работы 1/2 у каждого в момент t = 3, в то время как оптимальный алгоритм может закончить все эти задания к моменту 3. Эта схема продолжается, давая три задания размером 1/4, 1/4 и 1/2 при t = 3 и так далее. После k шагов у SRPT останется k заданий с размерами <math>1/2, 1/4, 1/8, ... , 1/2^{k - 2}, 1/2^{k - 1}; 1/2^{k - 1}</math>, тогда как у оптимального алгоритма не останется ни одного задания. Теперь соперник может давать 2 задания размером <math>1/2^k</math> каждые <math>1/2^k</math> единиц времени в течение длительного времени, что означает, что SRPT может быть в <math>\Omega(log \; P)</math> раз хуже оптимального.

'''Теорема 3 [8]. Существует полиномиальный по времени оффлайновый алгоритм, который достигает коэффициента аппроксимации <math>O(n^{1/2} \; log \; n/m)</math> при минимизации средней продолжительности потока на m машинах без вытеснения.'''