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

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

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

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

Эта граница является строгой в нескольких случаях. Для случая, когда есть ограничения по времени выпуска, нет ограничений на отношения предшествования, а время обработки (размеры) не известны по прибытии, Шмойс, Вейн и Уильямсон [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>.