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

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

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

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