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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Ссылки

  1. ^ ab Horowitz, Ellis; Sahni, Sartaj (1976-04-01). «Точные и приближенные алгоритмы планирования неидентичных процессоров». Журнал ACM . 23 (2): 317– 327. doi : 10.1145/321941.321951 . ISSN  0004-5411. S2CID  18693114.
  2. ^ abc Sahni, Sartaj K. (1976-01-01). "Алгоритмы планирования независимых задач". Журнал ACM . 23 (1): 116– 127. doi : 10.1145/321921.321934 . ISSN  0004-5411. S2CID  10956951.
  3. ^ Грэм, Рон Л. (1966). «Границы для некоторых аномалий многопроцессорной обработки». Bell System Technical Journal . 45 (9): 1563– 1581. doi :10.1002/j.1538-7305.1966.tb01709.x. ISSN  1538-7305.
  4. ^ Грэм, Рон Л. (1969-03-01). «Границы аномалий многопроцессорной синхронизации». Журнал SIAM по прикладной математике . 17 (2): 416– 429. doi :10.1137/0117039. ISSN  0036-1399.
  5. ^ Хуан, Синь; Лу, Пиньян (2021-07-18). «Алгоритмическая структура для аппроксимации распределения максиминной доли работы». Труды 22 - й конференции ACM по экономике и вычислениям . EC '21. Будапешт, Венгрия: Ассоциация вычислительной техники. стр.  630–631 . arXiv : 1907.04505 . doi :10.1145/3465456.3467555. ISBN 978-1-4503-8554-1. S2CID  195874333.
  6. ^ Хохбаум, Дорит С.; Шмойс, Дэвид Б. (1987-01-01). «Использование алгоритмов двойного приближения для решения задач планирования: теоретические и практические результаты». Журнал ACM . 34 (1): 144– 162. doi : 10.1145/7531.7535 . ISSN  0004-5411. S2CID  9739129.
  7. ^ Leung, Joseph YT. (1989-05-08). «Упаковка в контейнеры с ограниченными размерами деталей». Information Processing Letters . 31 (3): 145– 149. doi :10.1016/0020-0190(89)90223-8. ISSN  0020-0190.
  8. ^ Фризен, Д.К.; Дойермейер, Б.Л. (1981-02-01). «Анализ жадных решений для задачи последовательности замены деталей». Математика исследования операций . 6 (1): 74– 87. doi :10.1287/moor.6.1.74. ISSN  0364-765X.
  9. ^ Woeginger, Gerhard J. (1997-05-01). «Схема аппроксимации полиномиального времени для максимизации минимального времени завершения работы машины». Operations Research Letters . 20 (4): 149– 154. doi :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.
  • Резюме проблем параллельной машины без приоритета


Взято с "https://en.wikipedia.org/w/index.php?title=Планирование_идентичных_машин&oldid=1190183531"