Планирование списка

Планирование по спискам — это жадный алгоритм планирования идентичных машин . Входными данными для этого алгоритма является список заданий, которые должны быть выполнены на наборе из m машин. Список упорядочен в фиксированном порядке, который может определяться, например, приоритетом выполнения заданий или порядком их поступления. Алгоритм неоднократно выполняет следующие шаги, пока не будет получено допустимое расписание:

Возьмите первое задание в списке (тот, которое имеет наивысший приоритет).
Найдите машину, доступную для выполнения этой работы.
- Если машина найдена, запланируйте это задание на этой машине.
- В противном случае (подходящей машины нет) выберите следующее задание в списке.

Пример

Предположим, имеется пять заданий со временем обработки {4,5,6,7,8} и m =2 процессора. Тогда результирующее расписание будет {4,6,8}, {5,7}, а интервал выполнения будет max(18,12)=18; если m =3, то результирующее расписание равно {4,7}, {5,8}, {6}, а период выполнения равен max(11,13,6)=13.

Гарантия производительности

Алгоритм работает во времени $O(n)$ , где n — количество рабочих мест. Алгоритм всегда возвращает часть заданий, продолжительность выполнения которых не превышает $2-1/m$ раз оптимальная продолжительность цикла. ^[1] Это связано с тем, что и длина самой длинной работы, и средняя длина всех работ являются нижними границами оптимального периода изготовления. Алгоритм можно использовать как онлайн-алгоритм , когда порядок поступления товаров невозможно контролировать.

Стратегии заказа

Вместо использования произвольного порядка можно предварительно заказать задания, чтобы получить лучшие гарантии. Некоторые известные стратегии планирования списков: ^[2]

Первый алгоритм высшего уровня , или HLF;
Алгоритм наибольшего пути или LP;
Планирование с наибольшим временем обработки или LPT; этот вариант уменьшает коэффициент аппроксимации до ${\frac {4}{3}}-{\frac {1}{3k}}$ .
Метод критического пути .
Неоднородное время самого раннего окончания или HEFT. Для случая разнородных работников.

Аномалии

Алгоритм планирования списка имеет несколько аномалий. ^[1] Предположим, что имеется m =3 станков, а длина заданий равна:

3, 2, 2, 2, 4, 4, 4, 4, 9

Далее предположим, что все задания «4» должны быть выполнены после четвертого задания «2». Затем планирование списка возвращает следующее расписание:

3, 9
2, 2, 4, 4
2, [2 в режиме ожидания], 4, 4

и период действия равен 12.

Аномалия 1 . Если задания «4» больше не зависят от предыдущих заданий, то расписание списка будет таким:

3, 4, 9
2, 2, 4
2, 4, 4

и период обработки равен 16. Удаление зависимостей увеличило период обработки.

Аномалия 2 . Предположим, что длины заданий уменьшаются на 1, до 2, 1, 1, 1, 3, 3, 3, 3, 8 (с исходными зависимостями). Тогда расписание списка будет таким:

2, 3, 3
1, 1, 3, 8
1, [1 в режиме ожидания], 3

а период изготовления равен 13. Сокращение всех работ привело к увеличению периода изготовления.

Аномалия 3 . Предположим, есть еще одна машина (с исходными длинами, с зависимостями или без них). Тогда расписание списка будет таким:

3, 4
2, 4, 9
2, 4
2, 4

а период изготовления равен 15. Добавление машины увеличило срок изготовления.

Аномалии ограничены следующим образом. Предположим, что изначально у нас было m ₁ машин и период ремонта был t ₁ . Теперь у нас есть m ₂ машин, зависимости одинаковы или ослаблены, длина заданий такая же или короче, список тот же или другой, а период обработки равен t _2. Тогда: ^[1]^[3]

${\frac {t_{2}}{t_{1}}}\leq 1+{\frac {m_{1}-1}{m_{2}}}$ .

В частности, при одинаковом количестве машин соотношение $2-{\frac {1}{m}}$ . Особым случаем является случай, когда исходное расписание является оптимальным; это дает границу $2-{\frac {1}{m}}$ по коэффициенту аппроксимации.

Ссылки

^ Перейти обратно: ^а ^б ^с Грэм, Рон Л. (1 марта 1969 г.). «Границы аномалий синхронизации многопроцессорной обработки» . SIAM Journal по прикладной математике . 17 (2): 416–429. дои : 10.1137/0117039 . ISSN 0036-1399 .
^ Микели, Джованни Де (1994). Синтез и оптимизация цифровых схем . Нью-Йорк: МакГроу-Хилл. ISBN 978-0070163331 .
^ Грэм, Рон Л. (1966). «Границы некоторых аномалий многопроцессорной обработки» . Технический журнал Bell System . 45 (9): 1563–1581. дои : 10.1002/j.1538-7305.1966.tb01709.x . ISSN 1538-7305 .

[:1-1] Перейти обратно: ^а ^б ^с Грэм, Рон Л. (1 марта 1969 г.). «Границы аномалий синхронизации многопроцессорной обработки» . SIAM Journal по прикладной математике . 17 (2): 416–429. дои : 10.1137/0117039 . ISSN 0036-1399 .

[2] Микели, Джованни Де (1994). Синтез и оптимизация цифровых схем . Нью-Йорк: МакГроу-Хилл. ISBN 978-0070163331 .

[:2-3] Грэм, Рон Л. (1966). «Границы некоторых аномалий многопроцессорной обработки» . Технический журнал Bell System . 45 (9): 1563–1581. дои : 10.1002/j.1538-7305.1966.tb01709.x . ISSN 1538-7305 .

[1]

[2]

[3]