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

Приведенный ниже пример показывает, как 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].