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