Планирование несвязанных машин

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Расширения

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

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

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

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

Ссылки

^ Jump up to: ^а ^б Горовиц, Эллис; Сахни, Сартадж (1 апреля 1976 г.). «Точные и приближенные алгоритмы планирования неидентичных процессоров» . Журнал АКМ . 23 (2): 317–327. дои : 10.1145/321941.321951 . ISSN 0004-5411 . S2CID 18693114 .
^ Ленстра, Ян Карел; Шмойс, Дэвид Б.; Тардос, Ева (1 января 1990 г.). «Аппроксимационные алгоритмы планирования несвязанных параллельных машин» . Математическое программирование . 46 (1): 259–271. дои : 10.1007/BF01585745 . ISSN 1436-4646 . S2CID 52867171 .
^ Вершае, Хосе; Визе, Андреас (10 ноября 2013 г.). "О конфигурации-LP для планирования на несвязанных машинах" . Журнал планирования . 17 (4): 371–383. arXiv : 1011.4957 . дои : 10.1007/s10951-013-0359-4 . ISSN 1094-6136 . S2CID 254694965 .
^ Гласс, Калифорния; Поттс, Китай; Шейд, П. (1 июля 1994 г.). «Планирование несвязанных параллельных машин с использованием локального поиска». Математическое и компьютерное моделирование . 20 (2): 41–52. дои : 10.1016/0895-7177(94)90205-4 . ISSN 0895-7177 .
^ Бруно, Дж.; Коффман, Э.Г.; Сети, Р. (1 июля 1974 г.). «Планирование независимых задач для сокращения среднего времени завершения» . Коммуникации АКМ . 17 (7): 382–387. дои : 10.1145/361011.361064 . ISSN 0001-0782 . S2CID 2507557 .
^ Сахни, Сартадж К. (1 января 1976 г.). «Алгоритмы планирования независимых задач» . Журнал АКМ . 23 (1): 116–127. дои : 10.1145/321921.321934 . ISSN 0004-5411 . S2CID 10956951 .
^ Шульц, Андреас С.; Скутелла, Мартин (1 января 2002 г.). «Планирование несвязанных машин путем случайного округления» . SIAM Journal по дискретной математике . 15 (4): 450–469. дои : 10.1137/S0895480199357078 . ISSN 0895-4801 .
^ Бар-Ной, Амоц; Бар-Иегуда, Реувен; Фройнд, Ари; (Сеффи) Наор, Джозеф; Шибер, Барух (1 сентября 2001 г.). «Единый подход к распределению ресурсов и планированию» . Журнал АКМ . 48 (5): 1069–1090. дои : 10.1145/502102.502107 . ISSN 0004-5411 . S2CID 12329294 .
^ Jump up to: ^а ^б Ленстра, Ян Карел; Шмойс, Дэвид Б.; Тардос, Ева (1 января 1990 г.). «Аппроксимационные алгоритмы планирования несвязанных параллельных машин» . Математическое программирование . 46 (1): 259–271. дои : 10.1007/BF01585745 . ISSN 1436-4646 . S2CID 206799898 .
^ Линь, Исюнь; Ли, Вэньхуа (1 июля 2004 г.). «Параллельное машинное планирование машинозависимых работ с единичной длиной» . Европейский журнал операционных исследований . Премия ЕВРО за выдающиеся достижения в практике 2001 г. 156 (1): 261–266. дои : 10.1016/S0377-2217(02)00914-1 . ISSN 0377-2217 .
^ Ким, Донг-Вон; Ким, Кён Хи; Чан, Усон; Фрэнк Чен, Ф. (1 июня 2002 г.). «Несвязанное параллельное планирование работы машины с учетом времени наладки с использованием имитации отжига» . Робототехника и компьютерно-интегрированное производство . 18 (3–4): 223–231. дои : 10.1016/S0736-5845(02)00013-3 . ISSN 0736-5845 .
^ Валлада, Ева; Руис, Рубен (16 июня 2011 г.). «Генетический алгоритм для несвязанной задачи планирования параллельных машин с временем настройки, зависящим от последовательности» . Европейский журнал операционных исследований . 211 (3): 612–622. дои : 10.1016/j.ejor.2011.01.011 . hdl : 10251/35412 . ISSN 0377-2217 .
^ Нисан, Ноам; Ронен, Амир (2001). «Проектирование алгоритмических механизмов». Игры и экономическое поведение . 35 (1–2): 166–196. CiteSeerX 10.1.1.16.7473 . дои : 10.1006/game.1999.0790 .

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

[2] Ленстра, Ян Карел; Шмойс, Дэвид Б.; Тардос, Ева (1 января 1990 г.). «Аппроксимационные алгоритмы планирования несвязанных параллельных машин» . Математическое программирование . 46 (1): 259–271. дои : 10.1007/BF01585745 . ISSN 1436-4646 . S2CID 52867171 .

[3] Вершае, Хосе; Визе, Андреас (10 ноября 2013 г.). "О конфигурации-LP для планирования на несвязанных машинах" . Журнал планирования . 17 (4): 371–383. arXiv : 1011.4957 . дои : 10.1007/s10951-013-0359-4 . ISSN 1094-6136 . S2CID 254694965 .

[4] Гласс, Калифорния; Поттс, Китай; Шейд, П. (1 июля 1994 г.). «Планирование несвязанных параллельных машин с использованием локального поиска». Математическое и компьютерное моделирование . 20 (2): 41–52. дои : 10.1016/0895-7177(94)90205-4 . ISSN 0895-7177 .

[5] Бруно, Дж.; Коффман, Э.Г.; Сети, Р. (1 июля 1974 г.). «Планирование независимых задач для сокращения среднего времени завершения» . Коммуникации АКМ . 17 (7): 382–387. дои : 10.1145/361011.361064 . ISSN 0001-0782 . S2CID 2507557 .

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

[7] Шульц, Андреас С.; Скутелла, Мартин (1 января 2002 г.). «Планирование несвязанных машин путем случайного округления» . SIAM Journal по дискретной математике . 15 (4): 450–469. дои : 10.1137/S0895480199357078 . ISSN 0895-4801 .

[8] Бар-Ной, Амоц; Бар-Иегуда, Реувен; Фройнд, Ари; (Сеффи) Наор, Джозеф; Шибер, Барух (1 сентября 2001 г.). «Единый подход к распределению ресурсов и планированию» . Журнал АКМ . 48 (5): 1069–1090. дои : 10.1145/502102.502107 . ISSN 0004-5411 . S2CID 12329294 .

[:2-9] Jump up to: ^а ^б Ленстра, Ян Карел; Шмойс, Дэвид Б.; Тардос, Ева (1 января 1990 г.). «Аппроксимационные алгоритмы планирования несвязанных параллельных машин» . Математическое программирование . 46 (1): 259–271. дои : 10.1007/BF01585745 . ISSN 1436-4646 . S2CID 206799898 .

[10] Линь, Исюнь; Ли, Вэньхуа (1 июля 2004 г.). «Параллельное машинное планирование машинозависимых работ с единичной длиной» . Европейский журнал операционных исследований . Премия ЕВРО за выдающиеся достижения в практике 2001 г. 156 (1): 261–266. дои : 10.1016/S0377-2217(02)00914-1 . ISSN 0377-2217 .

[11] Ким, Донг-Вон; Ким, Кён Хи; Чан, Усон; Фрэнк Чен, Ф. (1 июня 2002 г.). «Несвязанное параллельное планирование работы машины с учетом времени наладки с использованием имитации отжига» . Робототехника и компьютерно-интегрированное производство . 18 (3–4): 223–231. дои : 10.1016/S0736-5845(02)00013-3 . ISSN 0736-5845 .

[12] Валлада, Ева; Руис, Рубен (16 июня 2011 г.). «Генетический алгоритм для несвязанной задачи планирования параллельных машин с временем настройки, зависящим от последовательности» . Европейский журнал операционных исследований . 211 (3): 612–622. дои : 10.1016/j.ejor.2011.01.011 . hdl : 10251/35412 . ISSN 0377-2217 .

[NisanRonen01-13] Нисан, Ноам; Ронен, Амир (2001). «Проектирование алгоритмических механизмов». Игры и экономическое поведение . 35 (1–2): 166–196. CiteSeerX 10.1.1.16.7473 . дои : 10.1006/game.1999.0790 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

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