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

Естественным образом возникает вопрос, является ли эта граница наилучшей. В одной из последующих работ Грэм [9] показал, что применение алгоритма LS к отсортированной последовательности заданий (в порядке невозрастания размеров) на самом деле дает улучшенную верхнюю границу коэффициента аппроксимации, равную <math>\frac{4}{3} - \frac{1}{3m}</math>. Аппроксимационную схему с полиномиальным временем выполнения предложили Хохбаум и Шмойс в работе [10]. Это лучший оффлайновый результат, на который можно было бы надеяться, поскольку, как известно, задача является NP-трудной в сильном смысле.

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

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

Самая сложная нерешенная задача заключается в поиске наилучшего возможного коэффициента конкурентоспособности для этой базовой онлайновой задачи планирования. Разрыв между верхней и нижней границами невелик, но нахождение точной границы представляется очень трудным. Возможно, проще было бы найти наилучший возможный коэффициент конкурентоспособности для m = 4. Нижняя граница <math>\sqrt{3} \approx 1,732</math> была показана в работе [12], а известная на данный момент верхняя граница – 1,733 – в [3]. Таким образом, возможно, эта граница окажется равной <math>\sqrt{3}</math>.