Списочное планирование

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

Планирование в режиме онлайн на идентичных машинах

Постановка задачи

Статья Рональда Грэма [8] была опубликована в шестидесятых. На протяжении многих лет она служила типичным примером онлайновых алгоритмов (хотя исходный алгоритм был разработан как простая эвристика аппроксимации). В ней рассматривалась следующая базовая формулировка задачи.

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

Если задания подаются одно за другим, и каждое задание по очереди должно быть назначено машине без какого-либо представления о будущих заданиях, такая задача называется онлайновой. Онлайновые алгоритмы обычно оцениваются с использованием (абсолютного) коэффициента конкурентоспособности, который аналогичен коэффициенту аппроксимации одноименных алгоритмов. Для алгоритма [math]\displaystyle{ \mathcal{A} }[/math] мы обозначаем его стоимость также как [math]\displaystyle{ \mathcal{A} }[/math]. Стоимость оптимального оффлайнового алгоритма, который знает всю последовательность заданий, обозначается как OPT. Коэффициентом конкурентоспособности алгоритма [math]\displaystyle{ \mathcal{A} }[/math] является инфимум [math]\displaystyle{ \mathcal{R} \ge 1 }[/math], такой, что для любых входных данных [math]\displaystyle{ \mathcal{A} \le \mathcal{R} \cdot OPT }[/math].

Основные результаты

В статье [8] Грэм определяет алгоритм под названием LIST SCHEDULING (LS). Алгоритм получает задания одно за другим. Каждое задание поочередно присваивается машине с минимальной текущей нагрузкой. Зависимости можно разрывать произвольным образом. Получаем следующий основной результат.

Теорема 1. Коэффициент конкурентоспособности алгоритма LS составляет [math]\displaystyle{ 2 - \frac{1}{m} }[/math].

Доказательство. Рассмотрим расписание, созданное для заданной последовательности. Обозначим за [math]\displaystyle{ \ell }[/math] задание, определяющее продолжительность работы (т. е. последнее задание, назначенное машине i, имеющей максимальную нагрузку). Пусть L обозначает его размер, а X – общий размер всех остальных заданий, назначенных i. В момент, когда задание L было назначено i, это была машина с минимальной нагрузкой. Таким образом, нагрузка каждой машины составляет не менее X. Продолжительность работы оптимального расписания (т. е. расписания, которое минимизирует продолжительность этого периода) равна стоимости оптимального оффлайнового алгоритма и, таким образом, обозначается как OPT. Обозначим за P сумму всех размеров заданий в последовательности.

Можно получить две следующие простые нижние границы для OPT.

(1) [math]\displaystyle{ OPT \ge L }[/math]

(2) [math]\displaystyle{ OPT \ge \frac{P}{m} \ge \frac{m \cdot X + L}{m} = X + \frac{L}{m} }[/math]

Неравенство (1) вытекает из того факта, что {OPT} необходимо выполнить работу [math]\displaystyle{ \ell }[/math] и, таким образом, по крайней мере одна машина имеет нагрузку как минимум L. Первое неравенство в выражении (2) обусловлено тем, что по крайней мере одна машина получает по крайней мере часть [math]\displaystyle{ \frac{1}{m} }[/math] от совокупного размера заданий. Второе неравенство в (2) вытекает из приведенных выше соображений относительно нагрузки каждой машины.

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

(3) [math]\displaystyle{ 1X + L \le OPT + \frac{m - 1}{m} L \le OPT + \frac{m - 1}{m} OPT = (2 -\frac{1}{m}) OPT }[/math]

Первое неравенство в (3) следует из выражения (2), а второе – из выражения (1).

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

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

Что касается онлайновой задачи, то в статье [5] было показано, что ни у одного (детерминированного) алгоритма коэффициент конкурентоспособности не может быть меньше [math]\displaystyle{ 2 - \frac{1}{m} }[/math] для случаев m = 2 и m = 3. С другой стороны, в серии работ было показано, что алгоритм с меньшим коэффициентом конкурентоспособности можно найти для любого значения [math]\displaystyle{ m \ge 4 }[/math], и даже были разработаны алгоритмы с коэффициентом конкурентоспособности, не приближающимся к 2 для больших m.

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

Применение

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

Балансировка нагрузки для временных задач

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

Планирование с учетом времени выпуска и отношений предшествования

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

Верхняя граница [math]\displaystyle{ 2 - \frac{1}{m} }[/math] коэффициента конкурентоспособности может быть доказана при помощи отношения между стоимостью оптимального графика и количеством времени, в течение которого хотя бы одна машина простаивает (подробнее об этом см. в [14]).

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

Открытые вопросы

Самая сложная нерешенная задача заключается в поиске наилучшего возможного коэффициента конкурентоспособности для этой базовой онлайновой задачи планирования. Разрыв между верхней и нижней границами невелик, но нахождение точной границы представляется очень трудным. Возможно, проще было бы найти наилучший возможный коэффициент конкурентоспособности для m = 4. Нижняя граница [math]\displaystyle{ \sqrt{3} \approx 1,732 }[/math] была показана в работе [12], а известная на данный момент верхняя граница – 1,733 – в [3]. Таким образом, возможно, эта граница окажется равной [math]\displaystyle{ \sqrt{3} }[/math].

Литература

1. Albers, S.: Better bounds for online scheduling. SIAM J. Comput. 29(2), 459^73 (1999)

2. Azar, Y., Epstein, L.: On-line load balancing of temporary tasks on identical machines. SIAM J. Discret. Math. 18(2), 347-352 (2004)

3. Chen, B., van Vliet, A., Woeginger, G.J.: New lower and upper bounds for on-line scheduling. Oper. Res. Lett. 16, 221-230 (1994)

4. Epstein, L.: A note on on-line scheduling with precedence constraints on identical machines. Inf. Process. Lett. 76, 149-153 (2000)

5. Faigle, U., Kern, W., Turan, G.: On the performane of online algorithms for partition problems. Acta Cybern. 9, 107-119 (1989)

6. Fleischer, R., Wahl, M.: On-line scheduling revisited. J. Sched. 3, 343-353 (2000)

7. Gormley, T., Reingold, N., Torng, E., Westbrook, J.: Generating adversaries for request-answer games. In: Proc. of the 11th Symposium on Discrete Algorithms. (SODA2000), pp. 564-565 (2000)

8. Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst.Techn.J. 45,1563-1581 (1966)

9. Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 263-269 (1969)

10. Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J.ACM 34(1), 144-162 (1987)

11. Noga, J., Seiden, S.S.: An optimal online algorithm for scheduling two machines with release times. Theor. Comput. Sci. 268(1),133-143(2001)

12. Rudin III,J.F., Chandrasekaran, R.: Improved bounds for the online scheduling problem. SIAM J. Comput. 32,717-735 (2003)

13. Rudin III, J.F.: Improved bounds for the online scheduling problem. Ph. D. thesis, The University of Texas at Dallas (2001)

14. Sgall, J.: On-line scheduling. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms: The State of the Art, pp. 196-231. Springer (1998)

15. Shmoys, D.B., Wein, J., Williamson, D.P.: Scheduling parallel machines on-line. SIAM J. Comput. 24,1313-1331 (1995)