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

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

Теорема 4 [8]. Ни один алгоритм с полиномиальным временем выполнения для минимизации общей продолжительности потока на нескольких машинах без вытеснения не может иметь коэффициент аппроксимации O(nll3~s) для любого " > 0, если только не выполняется P=NP.

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