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

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

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