Планирование работы не связанных между собой машин

Задача оптимизации в информатике и исследовании операций

Планирование на не связанных машинах — это задача оптимизации в информатике и исследовании операций . Это вариант оптимального планирования заданий . Нам нужно запланировать n заданий J ₁ , J ₂ , ..., J _n на m различных машинах таким образом, чтобы была оптимизирована определенная целевая функция (обычно, время выполнения должно быть минимизировано). Время, необходимое машине i для обработки задания j, обозначается как p _i,j . Термин «не связанный» подчеркивает, что нет никакой связи между значениями p _i,j для разных i и j . Это контрастирует с двумя особыми случаями этой задачи: планирование на однородных машинах — при котором p _i,j = p _i / s _j (где s _j — скорость машины j ), и планирование на идентичных машинах — при котором p _i,j = p _i (одинаковое время выполнения на всех машинах).

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

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

В третьем варианте целью является максимизация минимального времени завершения, " R|| " . Этот вариант соответствует проблеме эгалитарного распределения предметов . ${\displaystyle C_{\min }}$

Алгоритмы

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

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

Горовиц и Сахни ^[1] представили:

• Точные динамические алгоритмы программирования для минимизации максимального времени завершения как на однородных, так и на несвязанных машинах. Эти алгоритмы работают за экспоненциальное время (напомним, что все эти задачи NP-трудные).
• Схемы полиномиального времени аппроксимации , которые для любого ε >0 достигают максимум (1+ε)OPT. Для минимизации максимального времени завершения на двух однородных машинах их алгоритм работает за время , где — наименьшее целое число, для которого . Следовательно, время выполнения составляет , поэтому это FPTAS . Для минимизации максимального времени завершения на двух несвязанных машинах время выполнения равно = . Они утверждают, что их алгоритмы можно легко расширить для любого количества однородных машин, но не анализируют время выполнения в этом случае. ${\displaystyle O(10^{2l}n)}$ ${\displaystyle l}$ ${\displaystyle \epsilon \geq 2\cdot 10^{-l}}$ ${\displaystyle O(n/\epsilon ^{2})}$ ${\displaystyle O(10^{l}n^{2})}$ ${\displaystyle O(n^{2}/\epsilon )}$

Ленстра, Шмойс и Тардос ^[2] представили поливременной алгоритм аппроксимации 2-фактора и доказали, что поливременной алгоритм с аппроксимационным фактором меньше 3/2 невозможен, если только P=NP. Сокращение разрыва между 2 и 3/2 является давней открытой проблемой.

Верша и Визе ^[3] представили другой алгоритм двухфакторной аппроксимации.

Glass, Potts и Shade ^[4] сравнивают различные методы локального поиска для минимизации времени выполнения на не связанных машинах. Используя компьютерное моделирование, они обнаруживают, что поиск с запретами и имитация отжига работают намного лучше, чем генетические алгоритмы .

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

Бруно, Коффман и Сети ^[5] представляют алгоритм, работающий во времени , для минимизации среднего времени завершения работы на несвязанных машинах, R|| (среднее по всем работам время, необходимое для завершения работ). ${\displaystyle O(\max(mn^{2},n^{3}))}$ ${\displaystyle \sum C_{j}}$

Минимизация средневзвешенного времени завершения, R|| (где w _j — вес задания j ), является NP-трудной задачей даже на идентичных машинах, по сокращению из задачи о рюкзаке . ^[1] Это NP-трудная задача, даже если количество машин фиксировано и не менее 2, по сокращению из задачи о разбиении . ^[6] ${\displaystyle \sum w_{j}C_{j}}$

Шульц и Скутелла ^[7] представляют алгоритм (3/2+ε)-приближения с использованием рандомизированного округления . Их алгоритм представляет собой (2+ε)-приближение для задачи со временем выпуска заданий, R| | ${\displaystyle r_{j}}$ . ${\displaystyle \sum w_{j}C_{j}}$

Максимизация прибыли

Бар-Ной, Бар-Йехуда, Фройнд, Наор и Шибер ^[8] рассматривают ситуацию, в которой для каждой работы и машины есть прибыль от выполнения этой работы на этой машине. Они представляют приближение 1/2 для дискретного ввода и приближение (1- ε )/2 для непрерывного ввода.

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

Предположим, что вместо «работ» у нас есть ценные предметы, а вместо «машин» — люди. Человек i оценивает предмет j в p _i,j . Мы хотели бы распределить предметы среди людей так, чтобы наименее счастливый человек был максимально счастлив. Эта проблема эквивалентна планированию с не связанными между собой машинами, в котором цель состоит в максимизации минимального времени завершения. Это более известно под названием эгалитарное или распределение предметов по принципу максимума и минимума .

Формулировка линейного программирования

Естественный способ сформулировать задачу как линейную программу называется линейной программой Ленстры–Шмойса–Тардоса ^[9] (LST LP) . Для каждой машины i и задания _j определите переменную , которая равна 1, если машина i обрабатывает задание j , и 0 в противном случае. Тогда ограничения LP будут следующими: ${\displaystyle z_{i,j}}$

• ${\displaystyle \sum _{i=1}^{m}z_{i,j}=1}$для каждой работы j в 1,..., n;
• ${\displaystyle \sum _{j=1}^{n}z_{i,j}\cdot p_{i,j}\leq T}$для каждой машины i в 1,..., m;
• ${\displaystyle z_{i,j}\in \{0,1\}}$для каждого i , j .

Ослабление целочисленных ограничений дает линейную программу с размером полинома на входе. Решение ослабленной задачи может быть округлено для получения 2-приближения к задаче. ^[9]

Другая формулировка LP — это конфигурационная линейная программа . Для каждой машины i существует конечное число подмножеств заданий, которые могут быть обработаны машиной i за время не более T. Каждое такое подмножество называется конфигурацией для машины i . Обозначим через C _i ( T ) множество всех конфигураций для машины i . Для каждой машины i и конфигурации c в C _i ( T ) определите переменную , которая равна 1, если фактическая конфигурация, используемая в машине i, равна c , и 0 в противном случае. Тогда ограничения LP таковы: ${\displaystyle x_{i,c}}$

• ${\displaystyle \sum _{c\in C_{i}(T)}x_{i,c}=1}$для каждой машины i в 1,..., m;
• ${\displaystyle \sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1}$для каждой работы j в 1,..., n;
• ${\displaystyle x_{i,j}\in \{0,1\}}$для каждого i , j .

Обратите внимание, что число конфигураций обычно экспоненциально зависит от размера задачи, поэтому размер конфигурации LP экспоненциален. Однако в некоторых случаях можно ограничить число возможных конфигураций и, следовательно, найти приближенное решение за полиномиальное время.

Особые случаи

Существует особый случай, в котором p _i,j равно либо 1, либо бесконечности. Другими словами, каждое задание может быть обработано на подмножестве разрешенных машин , и его время выполнения на каждой из этих машин равно 1. Этот вариант иногда обозначается как " P|p _j =1,M _j | ". Его можно решить за полиномиальное время. ^[10] ${\displaystyle C_{\max }}$

Расширения

Ким, Ким, Джанг и Чен ^[11] расширяют проблему, позволяя каждому заданию иметь время настройки, которое зависит от задания, но не от машины. Они представляют решение с использованием имитации отжига . Валлада и Руиз ^[12] представляют решение с использованием генетического алгоритма .

Нисан и Ронен в своей статье 1999 года о проектировании алгоритмических механизмов ^[13] расширяют проблему по-другому, предполагая, что задания принадлежат эгоистичным агентам (см. Истинное планирование заданий ).

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

• Резюме проблем параллельной машины без приоритета

Ссылки

1. Horowitz, Ellis; Sahni, Sartaj (1976-04-01). «Точные и приближенные алгоритмы планирования неидентичных процессоров». Журнал ACM . 23 (2): 317–327. doi : 10.1145/321941.321951 . ISSN  0004-5411. S2CID  18693114.
2. Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). «Аппроксимационные алгоритмы для планирования не связанных параллельных машин». Математическое программирование . 46 (1): 259–271. doi :10.1007/BF01585745. ISSN  1436-4646. S2CID  52867171.
3. Verschae, José; Wiese, Andreas (2013-11-10). «О конфигурации-LP для планирования на несвязанных машинах». Journal of Scheduling . 17 (4): 371–383. arXiv : 1011.4957 . doi : 10.1007/s10951-013-0359-4. ISSN  1094-6136. S2CID  254694965.
4. Glass, CA; Potts, CN; Shade, P. (1994-07-01). «Планирование не связанных параллельных машин с использованием локального поиска». Математическое и компьютерное моделирование . 20 (2): 41–52. doi :10.1016/0895-7177(94)90205-4. ISSN  0895-7177.
5. Бруно, Дж.; Коффман, Э.Г.; Сети, Р. (1974-07-01). «Планирование независимых задач для сокращения среднего времени завершения». Сообщения ACM . 17 (7): 382–387. doi : 10.1145/361011.361064 . ISSN  0001-0782. S2CID  2507557.
6. Сахни, Сартадж К. (1976-01-01). «Алгоритмы планирования независимых задач». Журнал ACM . 23 (1): 116–127. doi : 10.1145/321921.321934 . ISSN  0004-5411. S2CID  10956951.
7. Шульц, Андреас С.; Скутелла, Мартин (2002-01-01). «Планирование не связанных машин с помощью рандомизированного округления». Журнал SIAM по дискретной математике . 15 (4): 450–469. doi :10.1137/S0895480199357078. ISSN  0895-4801.
8. Бар-Ной, Амоц; Бар-Йехуда, Реувен; Фройнд, Ари; (Сеффи) Наор, Джозеф; Шибер, Барух (2001-09-01). «Унифицированный подход к аппроксимации распределения ресурсов и планирования». Журнал ACM . 48 (5): 1069–1090. doi :10.1145/502102.502107. ISSN  0004-5411. S2CID  12329294.
9. Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). «Аппроксимационные алгоритмы для планирования не связанных параллельных машин». Математическое программирование . 46 (1): 259–271. doi :10.1007/BF01585745. ISSN  1436-4646. S2CID  206799898.
10. Линь, Исюнь; Ли, Вэньхуа (2004-07-01). «Параллельное машинное планирование машинно-зависимых заданий с единичной длиной». Европейский журнал операционных исследований . Премия EURO Excellence in Practice Award 2001. 156 (1): 261–266. doi :10.1016/S0377-2217(02)00914-1. ISSN  0377-2217.
11. Ким, Дон-Вон; Ким, Кён-Хи; Джанг, Усунг; Фрэнк Чен, Ф. (2002-06-01). «Несвязанное параллельное планирование машин с настройками времени с использованием имитации отжига». Робототехника и компьютерно-интегрированное производство . 18 (3–4): 223–231. doi :10.1016/S0736-5845(02)00013-3. ISSN  0736-5845.
12. Валлада, Ева; Руис, Рубен (2011-06-16). «Генетический алгоритм для задачи планирования несвязанных параллельных машин с зависимым от последовательности временем настройки». Европейский журнал операционных исследований . 211 (3): 612–622. doi : 10.1016/j.ejor.2011.01.011. hdl : 10251/35412 . ISSN  0377-2217.
13. Нисан, Ноам; Ронен, Амир (2001). «Проектирование алгоритмических механизмов». Игры и экономическое поведение . 35 (1–2): 166–196. CiteSeerX 10.1.1.16.7473 . doi :10.1006/game.1999.0790.