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

'''Теорема 5. Для любого <math>p \ge 1</math> существует <math>\epsilon > 0</math>, такое, что даже при наличии в <math>(1 + \epsilon)</math> раз более быстрого процессора алгоритм RR не является оптимальным для минимизации <math>\ell_p</math>-норм продолжительности потока. В частности, для e < 1/2p алгоритм RR является <math>(1 + \epsilon)</math>-скоростным, ^(п^-^РЩ-конкурентным. Для <math>\ell_p</math>-норм растяжимости RR является Q(n)-конкурентным, как и фактически любой рандомизированный алгоритм без предвидения.'''

Приведенные выше результаты были расширены по нескольким направлениям. Бансал и Прус [ ] распространили эти результаты на взвешенные <math>\ell_p</math>-нормы продолжительности потока и растяжимости. Чекури, Ханна, Кумар и Гель [4] распространили их результаты на случай нескольких машин. Их алгоритмы особенно элегантны: каждое задание назначается некоторой машине случайным образом, и все задания на определенной машине обрабатываются с помощью алгоритма SRPT или SETF (в зависимости от применимости).