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

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

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