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

Рассматриваемая задача является полиномиально разрешимой на единичном компьютере с допустимым вытеснением [9, 10]. Если вытеснение допускается, то оптимальным для одного компьютера является подход SRPT. На параллельных компьютерах наилучшая известная верхняя граница для случая с разрешенным вытеснением достигается алгоритмом SRPT, который является O(logmin n/m; P)-аппроксимируемым [6], где P – отношение между самым большим и самым малым временем обработки для данного экземпляра. Заметим, что алгоритм SRPT является онлайновым, так что предыдущий результат выполняется также и для онлайнового случая. Кроме того, в [6] было доказано, что в онлайновом случае эта нижняя граница является строгой. Для оффлайнового случая с разрешенным вытеснением не найдено неконстантной нижней границы.

В случае с отсутствием вытеснения ни один оффлайновый алгоритм не способен улучшить <math>\Omega (n^{1/3 - \epsilon})</math>-аппроксимацию, для любого <math>\epsilon > 0 \;</math>, а наилучшая верхняя граница составляет <math>O(\sqrt{n/m} \; log(n/m))</math> [6]. В случае с единственным компьютером верхняя и нижняя границы приобретают вид <math>O(\sqrt{n})</math> и <math>\Omega (n^{1/2 - \epsilon})</math> [5].

Для вышеописанных сценариев было предложено немало расширений, в частности, для онлайнового случая с разрешенным вытеснением. Большинство предположений касались мощности алгоритма или знания экземпляра входных данных. В первом случае представляет интерес вариант, в котором алгоритм выполняется на более быстрых компьютерах, нежели его оптимальный аналог. Этот аспект обсуждался в работе [4]. Ее авторы доказали, что даже небольшое повышение скорости приводит к тому, что некоторые простые эвристики могут продемонстрировать эффективность, близкую к оптимальной.

Что до знания алгоритмом экземпляра входных данных, любопытным вариантом онлайновой конфигурации, встречающимся во многих современных практических приложениях, является вышеупомянутый подход с отсутствием предвидения. Этот аспект рассматривался в [1, 3]. В частности, авторы [1] доказали, что рандомизированный вариант эвристики MLF, описанный выше, позволяет получить коэффициент конкурентоспособности, который в среднем отличается от оптимума не более чем на полилогарифмический коэффициент.