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

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

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

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

Алгоритмы

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

Минимизацию среднего времени завершения можно выполнить за полиномиальное время:

Алгоритм SPT (сначала самое короткое время обработки) сортирует задания по их длине, сначала самые короткие, а затем назначает их процессору с самым ранним временем окончания. Он выполняется за время O( n log n ) и минимизирует среднее время завершения на идентичных машинах. ^[1] П|| $\sum C_{i}$ .
Горовиц и Сахни ^[1] представить точный алгоритм со временем выполнения O( n log mn ) для минимизации среднего времени завершения на однородных машинах, Q|| $\sum C_{i}$ .
Бруно, Коффман и Сетхи ^[2] представить алгоритм, работающий во времени $O(\max(mn^{2},n^{3}))$ , для минимизации среднего времени выполнения на несвязанных машинах R|| $\sum C_{i}$ .

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

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

Сахни ^[3] представляет алгоритм экспоненциального времени и алгоритм аппроксимации полиномиального времени для идентичных машин.

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

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

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

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

Аппроксимация с постоянным коэффициентом достигается с помощью алгоритма наибольшего времени обработки (LPT).

Горовиц и Сахни ^[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 )$ . Они утверждают, что их алгоритмы можно легко расширить на любое количество однородных машин, но не анализируют время выполнения в этом случае.

Хохбаум и Шмойс ^[4] представил несколько алгоритмов аппроксимации для любого количества одинаковых машин . Позже, ^[5] они разработали ПТАС для унифицированных машин.

Эпштейн и Скалл ^[6] обобщил PTAS для унифицированных машин для обработки более общих целевых функций. Пусть C _i (для i от 1 до m ) — период работы машины i в заданном расписании. Вместо минимизации целевой функции max( C _i ) можно минимизировать целевую функцию max( f ( C _i )), где f — любая фиксированная функция. Аналогичным образом можно минимизировать сумму целевой функции ( f ( C _i )).

Монотонность и правдивость

В некоторых случаях скорость машины является частной информацией машины, и мы хотим стимулировать машины раскрывать свою истинную скорость, то есть нам нужен правдивый механизм . Важным фактором достижения правдивости является монотонность . ^[7] Это означает, что если машина сообщает о более высокой скорости, а все остальные входные данные остаются прежними, то общее время обработки, выделенное машине, незначительно увеличивается. Для этой проблемы:

Аулетта, Де Приско, Пенна и Персиано ^[8] представил монотонный алгоритм с 4 приближениями, который работает за политайм при фиксированном количестве машин.
Амбросио и Аулетта ^[9] доказал, что алгоритм наибольшего времени обработки является монотонным, когда скорости машины являются степенями некоторого c ≥ 2, но не когда c ≤ 1,78. Напротив, планирование списков не является монотонным для c > 2.
Андельман, Азар и Сорани ^[10] представил монотонный алгоритм с 5 приближениями, который работает в политайме, даже когда количество машин варьируется.
Ковач ^[11] представил 3-приближенный монотонный алгоритм.

Расширения

Зависимые задания : в некоторых случаях задания могут быть зависимыми. Например, возьмем случай чтения учетных данных пользователя с консоли, затем использования их для аутентификации, а затем, если аутентификация прошла успешно, отобразите некоторые данные на консоли. Очевидно, что одна задача зависит от другой. некоторый порядок Это явный случай того, что между задачами существует . На самом деле ясно, что его можно смоделировать с частичным упорядочением . Тогда по определению набор задач представляет собой решетчатую структуру . Это еще больше усложняет задачу многопроцессорного планирования.

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

Многоэтапные задания . В различных настройках каждое задание может содержать несколько операций, которые необходимо выполнять параллельно. Некоторые такие настройки обрабатываются планированием открытого цеха , планированием поточного цеха и планированием цеха .

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Горовиц, Эллис; Сахни, Сартадж (1 апреля 1976 г.). «Точные и приближенные алгоритмы планирования неидентичных процессоров» . Журнал АКМ . 23 (2): 317–327. дои : 10.1145/321941.321951 . ISSN 0004-5411 . S2CID 18693114 .
^ Бруно, Дж.; Коффман, Э.Г.; Сети, Р. (1 июля 1974 г.). «Планирование независимых задач для сокращения среднего времени завершения» . Коммуникации АКМ . 17 (7): 382–387. дои : 10.1145/361011.361064 . ISSN 0001-0782 .
^ Jump up to: ^а ^б Сахни, Сартадж К. (1 января 1976 г.). «Алгоритмы планирования независимых задач» . Журнал АКМ . 23 (1): 116–127. дои : 10.1145/321921.321934 . ISSN 0004-5411 .
^ Хохбаум, Дорит С.; Шмойс, Дэвид Б. (1 января 1987 г.). «Использование алгоритмов двойного приближения для задач планирования теоретических и практических результатов» . Журнал АКМ . 34 (1): 144–162. дои : 10.1145/7531.7535 . ISSN 0004-5411 . S2CID 9739129 .
^ Хохбаум, Дорит С.; Шмойс, Дэвид Б. (1 июня 1988 г.). «Схема полиномиальной аппроксимации для планирования на унифицированных процессорах: использование подхода двойного приближения» . SIAM Journal по вычислительной технике . 17 (3): 539–551. дои : 10.1137/0217033 . ISSN 0097-5397 .
^ Эпштейн, Лия; Сгалл, Иржи (1 мая 2004 г.). «Схемы аппроксимации для планирования равномерно связанных и одинаковых параллельных машин» . Алгоритмика . 39 (1): 43–57. дои : 10.1007/s00453-003-1077-7 . ISSN 1432-0541 . S2CID 12965369 .
^ Арчер, А.; Тардос, Э. (1 октября 2001 г.). «Правдивые механизмы для однопараметрических агентов» . Материалы 42-го симпозиума IEEE по основам информатики . стр. 482–491. дои : 10.1109/SFCS.2001.959924 . ISBN 0-7695-1390-5 . S2CID 11377808 .
^ Аулетта, Винченцо; Де Приско, Роберто; Пенна, Паоло; Персиано, Джузеппе (2004). «Механизмы детерминированной истинной аппроксимации для планирования связанных машин» . В Дикерте, Волкере; Хабиб, Мишель (ред.). Стакс 2004 . Конспекты лекций по информатике. Том. 2996. Берлин, Гейдельберг: Springer. стр. 608–619. дои : 10.1007/978-3-540-24749-4_53 . ISBN 978-3-540-24749-4 .
^ Амбросио, Паскуале; Аулетта, Винченцо (2005). «Детерминированные монотонные алгоритмы планирования на связанных машинах» . В Персиано, Джузеппе; Солис-Оба, Роберто (ред.). Приближение и онлайн-алгоритмы . Конспекты лекций по информатике. Том. 3351. Берлин, Гейдельберг: Springer. стр. 267–280. дои : 10.1007/978-3-540-31833-0_22 . ISBN 978-3-540-31833-0 .
^ Андельман, Нир; Азар, Йоси; Сорани, Мотти (2005). «Механизмы правдивой аппроксимации для планирования эгоистичных машин» . В Дикерте, Волкере; Дюран, Бруно (ред.). Стакс 2005 . Конспекты лекций по информатике. Том. 3404. Берлин, Гейдельберг: Springer. стр. 69–82. дои : 10.1007/978-3-540-31856-9_6 . ISBN 978-3-540-31856-9 .
^ Ковач, Аннамария (2005). «Быстрый монотонный алгоритм 3-приближения для планирования связанных машин» . В Бродале — Герт Столтинг; Леонарди, Стефано (ред.). Алгоритмы – ЕКА 2005 . Конспекты лекций по информатике. Том. 3669. Берлин, Гейдельберг: Springer. стр. 616–627. дои : 10.1007/11561071_55 . ISBN 978-3-540-31951-1 .
^ Квок, Ю-Квонг; Ахмад, Ишфак (1 декабря 1999 г.). «Алгоритмы статического планирования для распределения направленных графов задач мультипроцессорам». Обзоры вычислительной техники ACM . 31 (4): 406–471. CiteSeerX 10.1.1.322.2295 . дои : 10.1145/344588.344618 . ISSN 0360-0300 . S2CID 207614150 .

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

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

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

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

[5] Хохбаум, Дорит С.; Шмойс, Дэвид Б. (1 июня 1988 г.). «Схема полиномиальной аппроксимации для планирования на унифицированных процессорах: использование подхода двойного приближения» . SIAM Journal по вычислительной технике . 17 (3): 539–551. дои : 10.1137/0217033 . ISSN 0097-5397 .

[6] Эпштейн, Лия; Сгалл, Иржи (1 мая 2004 г.). «Схемы аппроксимации для планирования равномерно связанных и одинаковых параллельных машин» . Алгоритмика . 39 (1): 43–57. дои : 10.1007/s00453-003-1077-7 . ISSN 1432-0541 . S2CID 12965369 .

[7] Арчер, А.; Тардос, Э. (1 октября 2001 г.). «Правдивые механизмы для однопараметрических агентов» . Материалы 42-го симпозиума IEEE по основам информатики . стр. 482–491. дои : 10.1109/SFCS.2001.959924 . ISBN 0-7695-1390-5 . S2CID 11377808 .

[8] Аулетта, Винченцо; Де Приско, Роберто; Пенна, Паоло; Персиано, Джузеппе (2004). «Механизмы детерминированной истинной аппроксимации для планирования связанных машин» . В Дикерте, Волкере; Хабиб, Мишель (ред.). Стакс 2004 . Конспекты лекций по информатике. Том. 2996. Берлин, Гейдельберг: Springer. стр. 608–619. дои : 10.1007/978-3-540-24749-4_53 . ISBN 978-3-540-24749-4 .

[9] Амбросио, Паскуале; Аулетта, Винченцо (2005). «Детерминированные монотонные алгоритмы планирования на связанных машинах» . В Персиано, Джузеппе; Солис-Оба, Роберто (ред.). Приближение и онлайн-алгоритмы . Конспекты лекций по информатике. Том. 3351. Берлин, Гейдельберг: Springer. стр. 267–280. дои : 10.1007/978-3-540-31833-0_22 . ISBN 978-3-540-31833-0 .

[10] Андельман, Нир; Азар, Йоси; Сорани, Мотти (2005). «Механизмы правдивой аппроксимации для планирования эгоистичных машин» . В Дикерте, Волкере; Дюран, Бруно (ред.). Стакс 2005 . Конспекты лекций по информатике. Том. 3404. Берлин, Гейдельберг: Springer. стр. 69–82. дои : 10.1007/978-3-540-31856-9_6 . ISBN 978-3-540-31856-9 .

[11] Ковач, Аннамария (2005). «Быстрый монотонный алгоритм 3-приближения для планирования связанных машин» . В Бродале — Герт Столтинг; Леонарди, Стефано (ред.). Алгоритмы – ЕКА 2005 . Конспекты лекций по информатике. Том. 3669. Берлин, Гейдельберг: Springer. стр. 616–627. дои : 10.1007/11561071_55 . ISBN 978-3-540-31951-1 .

[12] Квок, Ю-Квонг; Ахмад, Ишфак (1 декабря 1999 г.). «Алгоритмы статического планирования для распределения направленных графов задач мультипроцессорам». Обзоры вычислительной техники ACM . 31 (4): 406–471. CiteSeerX 10.1.1.322.2295 . дои : 10.1145/344588.344618 . ISSN 0360-0300 . S2CID 207614150 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

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