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

Планирование идентичных машин — это проблема оптимизации в информатике и исследовании операций . Нам даны n заданий J ₁ , J ₂ , ..., J _n с различным временем обработки, которые необходимо запланировать на m одинаковых машинах так, чтобы оптимизировалась определенная целевая функция, например, период обработки минимизировался .

Идентичное планирование машин — это частный случай единообразного планирования машин , которое само по себе является частным случаем оптимального планирования работ . В общем случае время обработки каждого задания на разных машинах может быть разным; в случае идентичного планирования машин время обработки каждого задания одинаково на каждой машине. Таким образом, идентичное машинное планирование эквивалентно многостороннему разделению чисел . Особым случаем идентичного планирования машин является планирование одной машины .

В стандартной записи с тремя полями для задач оптимального планирования заданий вариант с идентичными машинами обозначается буквой P в первом поле. Например, « П|| $C_{\max }$ « — это идентичная задача машинного планирования без ограничений, цель которой — минимизировать максимальное время завершения.

В некоторых вариантах задачи вместо минимизации максимального времени выполнения желательно минимизировать среднее время выполнения (усредненное по всем n заданиям); он обозначается P|| $\sum C_{i}$ . В более общем плане, когда некоторые задания более важны, чем другие, может оказаться желательным минимизировать средневзвешенное время завершения, при котором каждое задание имеет разный вес. Это обозначается P|| $\sum w_{i}C_{i}$ .

Алгоритмы

Минимизация среднего и средневзвешенного времени завершения

Минимизация среднего времени завершения ( P|| $\sum C_{i}$ ) можно выполнить за полиномиальное время. Алгоритм SPT (сначала самое короткое время обработки) сортирует задания по их длине, сначала самые короткие, а затем назначает их процессору с самым ранним временем окончания. Он выполняется за время O( n log n ) и минимизирует среднее время завершения на идентичных машинах. ^[1] П|| $\sum C_{i}$ .

Расписаний SPT может быть много; найти расписание SPT с наименьшим временем окончания (также называемое OMFT — оптимальное среднее время окончания ) NP-сложно.

Минимизация средневзвешенного времени выполнения является NP-трудной задачей даже на идентичных машинах за счет исключения задачи о рюкзаке . ^[1] Это NP-сложно, даже если количество машин фиксировано и не менее двух, за счет уменьшения проблемы с разделами . ^[2]

Сахни ^[2] представляет алгоритм экспоненциального времени и схему аппроксимации полиномиального времени для решения обеих этих NP-трудных задач на идентичных машинах:

Оптимальное среднее время завершения;
Средневзвешенное время завершения.

Минимизация максимального времени завершения (промежутка времени)

Минимизация максимального времени завершения ( P|| $C_{\max }$ ) является NP-сложным даже для идентичных машин, за счет исключения проблемы разделов . Известно множество точных и аппроксимирующих алгоритмов.

Грэм доказал, что:

Любой алгоритм планирования списка (алгоритм, который обрабатывает задания в произвольном фиксированном порядке и распределяет каждое задание на первую доступную машину) является $2-1/m$ аппроксимация для одинаковых машин. ^[3] Граница точная для любого m . Этот алгоритм работает за время O( n ).
Специальный алгоритм планирования списков, называемый Longest Processing Time First (LPT), который сортирует задания по убыванию длины, представляет собой $4/3-1/3m$ аппроксимация для одинаковых машин. ^[4]^{: сек.5} Это также называется жадным числовым разделением .

Коффман, Гэри и Джонсон представили другой алгоритм, называемый алгоритмом мультиподбора , использующий методы упаковки контейнеров , который имеет коэффициент аппроксимации 13/11≈1,182.

Хуан и Лу ^[5] представил простой алгоритм с полиномиальным временем, который достигает аппроксимации 11/9≈1,222 за время O( m log m + n ) посредством более общей проблемы максимин-долевого распределения рутинных работ .

Сахни ^[2] представил PTAS, который достигает (1+ε)OPT во времени $O(n\cdot (n^{2}/\epsilon )^{m-1})$ . Это FPTAS, если m фиксировано. Для m=2 время выполнения улучшается до $O(n^{2}/\epsilon )$ . Алгоритм использует технику, называемую интервальным разделением .

Хохбаум и Шмойс ^[6] представил несколько алгоритмов аппроксимации для любого количества одинаковых машин (даже если количество машин не фиксировано):

Для любого r >0 алгоритм с коэффициентом аппроксимации не более (6/5+2 ^{− р} ) во времени $O(n(r+\log {n}))$ .
Для любого r >0 алгоритм с коэффициентом аппроксимации не более (7/6+2 ^{− р} ) во времени $O(n(rm^{4}+\log {n}))$ .
Для любого ε >0 алгоритм со степенью аппроксимации не более (1+ε) за время $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ . Это ПТАС . Обратите внимание: когда количество машин является частью входных данных, задача является строго NP-сложной , поэтому FPTAS невозможен.

Люнг ^[7] улучшилось время выполнения этого алгоритма, чтобы $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ .

Максимизация минимального времени завершения

Максимизация минимального времени завершения ( P|| $C_{\min }$ ) применимо, когда «работы» на самом деле являются запасными частями, необходимыми для поддержания работы машин, и имеют разный срок службы. Цель состоит в том, чтобы машины работали как можно дольше. ^[8] Алгоритм LPT достигает как минимум ${\frac {3m-1}{4m-2}}$ оптимума.

Вегингер ^[9] представил PTAS, который достигает коэффициента аппроксимации $1-{\varepsilon }$ вовремя $O(c_{\varepsilon }n\log {k})$ , где $c_{\varepsilon }$ огромная константа, экспоненциальная относительно требуемого коэффициента аппроксимации ε. Алгоритм использует алгоритм Ленстры для целочисленного линейного программирования .

Общие целевые функции

Алон, Азар, Вегингер и Ядид ^[10] рассмотрим более общую целевую функцию. Учитывая положительную действительную функцию f , которая зависит только от времени завершения C _i , они рассматривают цели минимизации $\sum _{i=1}^{m}f(C_{i})$ , минимизация $\max _{i=1}^{m}f(C_{i})$ , максимизация $\sum _{i=1}^{m}f(C_{i})$ и максимизация $\min _{i=1}^{m}f(C_{i})$ . Они доказывают, что если f неотрицательна, выпукла и удовлетворяет сильному предположению непрерывности, которое они называют «F *», то обе задачи минимизации имеют PTAS. Аналогично, если f неотрицательна, вогнута и удовлетворяет F*, то обе задачи максимизации имеют PTAS. В обоих случаях время работы PTAS равно O( n ), но с константами, экспоненциальными по отношению к 1/ ε.

См. также

метод Фернандеса

Ссылки

^ Перейти обратно: ^а ^б Горовиц, Эллис; Сахни, Сартадж (1 апреля 1976 г.). «Точные и приближенные алгоритмы планирования неидентичных процессоров» . Журнал АКМ . 23 (2): 317–327. дои : 10.1145/321941.321951 . ISSN 0004-5411 . S2CID 18693114 .
^ Перейти обратно: ^а ^б ^с Сахни, Сартадж К. (1 января 1976 г.). «Алгоритмы планирования независимых задач» . Журнал АКМ . 23 (1): 116–127. дои : 10.1145/321921.321934 . ISSN 0004-5411 . S2CID 10956951 .
^ Грэм, Рон Л. (1966). «Границы некоторых аномалий многопроцессорной обработки» . Технический журнал Bell System . 45 (9): 1563–1581. дои : 10.1002/j.1538-7305.1966.tb01709.x . ISSN 1538-7305 .
^ Грэм, Рон Л. (1 марта 1969 г.). «Границы аномалий синхронизации многопроцессорной обработки» . SIAM Journal по прикладной математике . 17 (2): 416–429. дои : 10.1137/0117039 . ISSN 0036-1399 .
^ Хуан, Синь; Лу, Пиньян (18 июля 2021 г.). «Алгоритмическая основа для приближенного распределения долей по дому» . Материалы 22-й конференции ACM по экономике и вычислениям . ЭК '21. Будапешт, Венгрия: Ассоциация вычислительной техники. стр. 630–631. arXiv : 1907.04505 . дои : 10.1145/3465456.3467555 . ISBN 978-1-4503-8554-1 . S2CID 195874333 .
^ Хохбаум, Дорит С.; Шмойс, Дэвид Б. (1 января 1987 г.). «Использование алгоритмов двойного приближения для задач планирования теоретических и практических результатов» . Журнал АКМ . 34 (1): 144–162. дои : 10.1145/7531.7535 . ISSN 0004-5411 . S2CID 9739129 .
^ Люнг, Джозеф Ю.Т. (08 мая 1989 г.). «Контейнерная упаковка с ограниченным размером штук» . Письма об обработке информации . 31 (3): 145–149. дои : 10.1016/0020-0190(89)90223-8 . ISSN 0020-0190 .
^ Фризен, ДК; Дойермейер, БЛ (1 февраля 1981 г.). «Анализ жадных решений проблемы последовательности замены деталей» . Математика исследования операций . 6 (1): 74–87. дои : 10.1287/moor.6.1.74 . ISSN 0364-765X .
^ Вегингер, Герхард Дж. (1 мая 1997 г.). «Схема аппроксимации полиномиального времени для максимизации минимального времени завершения работы машины» . Письма об исследованиях операций . 20 (4): 149–154. дои : 10.1016/S0167-6377(96)00055-7 . ISSN 0167-6377 .
^ Алон, Нога; Азар, Йоси; Вегингер, Герхард Дж.; Ядид, Таль (1998). «Аппроксимационные схемы планирования на параллельных машинах» . Журнал планирования . 1 (1): 55–66. doi : 10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J . ISSN 1099-1425 .

Внешние ссылки

Краткое описание проблем с параллельными машинами без упреждения

[:0-1] Перейти обратно: ^а ^б Горовиц, Эллис; Сахни, Сартадж (1 апреля 1976 г.). «Точные и приближенные алгоритмы планирования неидентичных процессоров» . Журнал АКМ . 23 (2): 317–327. дои : 10.1145/321941.321951 . ISSN 0004-5411 . S2CID 18693114 .

[:3-2] Перейти обратно: ^а ^б ^с Сахни, Сартадж К. (1 января 1976 г.). «Алгоритмы планирования независимых задач» . Журнал АКМ . 23 (1): 116–127. дои : 10.1145/321921.321934 . ISSN 0004-5411 . S2CID 10956951 .

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

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

[5] Хуан, Синь; Лу, Пиньян (18 июля 2021 г.). «Алгоритмическая основа для приближенного распределения долей по дому» . Материалы 22-й конференции ACM по экономике и вычислениям . ЭК '21. Будапешт, Венгрия: Ассоциация вычислительной техники. стр. 630–631. arXiv : 1907.04505 . дои : 10.1145/3465456.3467555 . ISBN 978-1-4503-8554-1 . S2CID 195874333 .

[:02-6] Хохбаум, Дорит С.; Шмойс, Дэвид Б. (1 января 1987 г.). «Использование алгоритмов двойного приближения для задач планирования теоретических и практических результатов» . Журнал АКМ . 34 (1): 144–162. дои : 10.1145/7531.7535 . ISSN 0004-5411 . S2CID 9739129 .

[7] Люнг, Джозеф Ю.Т. (08 мая 1989 г.). «Контейнерная упаковка с ограниченным размером штук» . Письма об обработке информации . 31 (3): 145–149. дои : 10.1016/0020-0190(89)90223-8 . ISSN 0020-0190 .

[8] Фризен, ДК; Дойермейер, БЛ (1 февраля 1981 г.). «Анализ жадных решений проблемы последовательности замены деталей» . Математика исследования операций . 6 (1): 74–87. дои : 10.1287/moor.6.1.74 . ISSN 0364-765X .

[:22-9] Вегингер, Герхард Дж. (1 мая 1997 г.). «Схема аппроксимации полиномиального времени для максимизации минимального времени завершения работы машины» . Письма об исследованиях операций . 20 (4): 149–154. дои : 10.1016/S0167-6377(96)00055-7 . ISSN 0167-6377 .

[10] Алон, Нога; Азар, Йоси; Вегингер, Герхард Дж.; Ядид, Таль (1998). «Аппроксимационные схемы планирования на параллельных машинах» . Журнал планирования . 1 (1): 55–66. doi : 10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J . ISSN 1099-1425 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

v т и оптимального планирования работы Проблемы
Одноэтапные работы	Одна машина Идентичные машины Униформные машины Несвязанные машины
Многоэтапные работы	Параллельные задачи Открыть магазин Поточный цех Магазин вакансий
Цели оптимизации	Макеспан Ранность Опоздание Опоздание Пропускная способность
Другие требования	Интервальное планирование Правдивое планирование работы