Аноним

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

Материал из WEGA
м
Строка 78: Строка 78:


== Открытые вопросы ==
== Открытые вопросы ==
Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница £?(logn) была получена для конфигурации с одним компьютером [7], и есть причины предполагать, что она оказывается на логарифмический коэффициент ниже границы для параллельного случая.
Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница <math>\Omega(log \; n)</math> была получена для конфигурации с одним компьютером [7], и есть причины предполагать, что она оказывается на логарифмический коэффициент ниже границы для параллельного случая.


== См. также ==
== См. также ==
4551

правка