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

Ключевые слова и синонимы

Последовательность из n заданий должна быть назначена m идентичным машинам. Каждое задание должно быть назначено одной из машин. С каждым заданием связан размер, который можно рассматривать как время обработки или нагрузку. Нагрузка машины представляет собой сумму размеров присвоенных ей заданий. Цель заключается в минимизации максимальной нагрузки любой машины, также называемую продолжительностью работы. Эта задача носит название планирования заданий (JOB SCHEDULING).

Теорема 1. Коэффициент конкурентоспособности алгоритма LS составляет 2 — m1.

(1) (2)

OPT > L :

Неравенство (1) вытекает из того факта, что {OPT} необходимо выполнить работу I и, таким образом, по крайней мере одна машина имеет нагрузку как минимум L. Первое неравенство в выражении (2) обусловлено тем, что по крайней мере одна машина получает по крайней мере часть m1 от совокупного размера заданий. Второе неравенство в (2) вытекает из приведенных выше соображений относительно нагрузки каждой машины.

Это доказывает, что продолжительность работы алгоритма, X + L, может быть ограничена следующим образом.

1X + L < OPT + -—L < OPT + -—OPT (3)

Чтобы показать, что анализ является строгим, рассмотрим m(m - 1) заданий размера 1, за которыми следует одно задание размера m. После поступления меньших заданий LS получает сбалансированное расписание, в котором каждая машина имеет нагрузку m - 1. Следующее, большое задание увеличивает продолжительность работы до 2 m - 1. Однако оптимальным решением в автономном режиме было бы назначить задания меньшего размера m - 1 машине, а оставшееся задание – оставшейся машину, в результате чего мы получим нагрузку m.

Естественным образом возникает вопрос, является ли эта граница наилучшей. В одной из последующих работ Грэм [ ] показал, что применение алгоритма LS к отсортированной последовательности заданий (в порядке невозрастания размеров) на самом деле дает улучшенную верхнюю границу коэффициента аппроксимации, равную 4 - j^. Схему аппроксимации с полиномиальным временем выполнения предложили Хохбаум и Шмойс в работе [10]. Это лучший оффлайновый результат, на который можно было бы надеяться, поскольку, как известно, задача является NP-трудной в сильном смысле.

Что касается онлайновой задачи, то в статье [ ] было показано, что ни у одного (детерминированного) алгоритма коэффициент конкурентоспособности не может быть меньше 2 – 1, что верно для случаев m = 2 и m = 3. С другой стороны, в серии работ было показано, что алгоритм с меньшим коэффициентом конкурентоспособности можно найти для любого значения m > 4, и даже были разработаны алгоритмы с коэффициентом конкурентоспособности, не приближающимся к 2 для больших m.

Наилучший такой результат получили Флейшер и Валь [6], разработавшие 1,9201-конкурентный алгоритм. В [1, 7] были представлены нижние границы коэффициента конкурентоспособности для любого онлайнового алгоритма, равные 1,852 и 1,85358. Рудин [13] также улучшил нижнюю границу – до 1,88.

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

В этой задаче размеры заданий рассматриваются как нагрузки. Время представляет собой отдельную ось. Входными данными является последовательность событий, в которой каждое событие представляет собой поступление или уход задания. Множество активных заданий в момент времени t – это набор заданий, которые уже поступили к этому моменту и еще не завершены. Стоимостью алгоритма в момент времени t является продолжительность его работы на данный момент. Стоимость алгоритма равняется его максимальной стоимости по всем значениям времени. Оказывается, вышеприведенный анализ можно легко адаптировать и для этой модели. Любопытно отметить, что в данном случае, как показано в работе [2], лучше всего подойдет граница 2 - m1.

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

Верхняя граница 2 - m1 коэффициента конкурентоспособности может быть доказана при помощи отношения между стоимостью оптимального графика и количеством времени, в течение которого хотя бы одна машина простаивает (подробнее об этом см. в [ ]).

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

Самая сложная нерешенная задачи заключается в поиске наилучшего возможного коэффициента конкурентоспособности для этой базовой онлайновой задачи планирования. Разрыв между верхней и нижней границами невелик, но нахождение точной границы представляется очень трудным. Возможно, проще было бы найти наилучший возможный коэффициент конкурентоспособности для m = 4. Нижняя граница p3 ^ 1,732 была показана в работе [ ], а известная на данный момент верхняя граница – 1,733 – в [ ]. Таким образом, возможно, эта граница окажется равной p3.