Списочное планирование: различия между версиями

Эта граница является строгой в нескольких случаях. Для случая, когда учитывается время выпуска, нет ограничений на отношения предшествования, а время обработки (размеры) не известны по прибытии, Шмойс, Вейн и Уильямсон [15] доказали нижнюю границу, равную <math>2 - \frac{1}{m}</math>. Для случая, когда имеются только ограничения на отношения предшествования (время выпуска не учитывается, размеры заданий известны по прибытии), нижняя граница той же величины была приведена в [4]. Следует отметить, что в случае планирования с предвидением (в котором размеры заданий известны по прибытии) время выпуска и отношения предшествования не устанавливаются. Для m = 2 Нога и Сайден [11] показали, что жесткая граница равна <math>(5 - \sqrt{5})/2 \approx 1,38198</math>, а верхняя граница достигается при помощи алгоритма, который применяет ожидание с простаивающими машинами вместо того, чтобы планировать задания как можно быстрее, как это делает LS.