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

Они также дали подходящую нижнюю границу коэффициента конкурентоспособности (с точностью до постоянных коэффициентов).

Заметим, что минимизация средней продолжительности потока эквивалентна минимизации общей его продолжительности. Предположим, что каждое задание выплачивает 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> раз хуже оптимального.

В своей работе Леонарди и Раз также рассмотрели оффлайновые алгоритмы для задачи без вытеснения.

Для доказательства этого результата авторы дали общую технику преобразования расписания с вытеснением в расписание без вытеснения с потерей <math>O(n^{1/2})</math> в коэффициенте аппроксимации. Они также показали почти совпадающую нижнюю границу. В частности,

С момента публикации этих результатов они были расширены по нескольким направлениям. Вспомним, что алгоритм SRPT является как вытесняющим, так и мигрирующим. Авербух, Азар, Леонарди и Регев [2] предложили онлайновый алгоритм планирования, который не является мигрирующим и при этом дает коэффициент конкурентоспособности O(min(log(n/m), log P)). Авраами и Азар [1] представили онлайн-алгоритм с еще более ограниченным коэффициентом конкурентоспособности O(min(log P, log(n/m))). Их алгоритм, помимо того, что не поддерживает миграцию, отправляет задание на машину сразу же по его поступлении. Недавно Гарг и Кумар [4,5] распространили эти результаты на ситуацию, когда машины имеют неодинаковую скорость. Также были исследованы другие связанные проблемы и условия, такие как минимизация растяжения (определяемого как продолжительность потока, деленная на размер задания), минимизация взвешенной продолжительности потока, а также условие без предвидения, когда размер задания не известен в момент его поступления. Более подробную информацию можно найти в обзоре Прухса, Сгалла и Торнга [9].