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

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

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

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