Планирование униформ-машин - Uniform-machines scheduling

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

Приближение постоянного множителя достигается с помощью алгоритма с наибольшим временем обработки (LPT).

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

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

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

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

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

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

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

Расширения

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

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

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

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

Сводка проблем параллельных машин без прерывания

использованная литература

^ Горовиц, Эллис; Сахни, Сартадж (1976-04-01). «Точные и приближенные алгоритмы планирования неидентичных процессоров» . Журнал ACM . 23 (2): 317–327. DOI : 10.1145 / 321941.321951 . ISSN 0004-5411 .
^ ^a ^b ^c ^d Горовиц, Эллис; Сахни, Сартадж (1 апреля 1976 г.). «Точные и приближенные алгоритмы планирования неидентичных процессоров» . Журнал ACM . 23 (2): 317–327. DOI : 10.1145 / 321941.321951 . ISSN 0004-5411 .
^ Бруно, Дж .; Коффман, EG; Сетхи, Р. (1974-07-01). «Планирование независимых задач для сокращения среднего времени завершения» . Коммуникации ACM . 17 (7): 382–387. DOI : 10.1145 / 361011.361064 . ISSN 0001-0782 .
^ ^a ^b Сахни, Сартадж К. (1 января 1976 г.). «Алгоритмы планирования независимых задач» . Журнал ACM . 23 (1): 116–127. DOI : 10.1145 / 321921.321934 . ISSN 0004-5411 .
^ Hochbaum, Dorit S .; Шмойс, Дэвид Б. (1987-01-01). «Использование алгоритмов двойного приближения для теоретических и практических результатов задач планирования» . Журнал ACM . 34 (1): 144–162. DOI : 10.1145 / 7531.7535 . ISSN 0004-5411 . S2CID 9739129 .
^ Hochbaum, Dorit S .; Шмойс, Дэвид Б. (1988-06-01). «Схема полиномиального приближения для планирования на унифицированных процессорах: использование подхода двойного приближения» . SIAM Journal on Computing . 17 (3): 539–551. DOI : 10.1137 / 0217033 . ISSN 0097-5397 .
^ Эпштейн, Лия; Сгалл, Иржи (2004-05-01). «Аппроксимационные схемы для составления расписаний на однородно связанных и идентичных параллельных машинах» . Алгоритмика . 39 (1): 43–57. DOI : 10.1007 / s00453-003-1077-7 . ISSN 1432-0541 .
^ Арчер, А .; Тардос, Э. (2001-10-01). «Правдивые механизмы для однопараметрических агентов» . Материалы 42-го симпозиума IEEE по основам информатики : 482–491. DOI : 10.1109 / SFCS.2001.959924 .
^ Аулетта, Винченцо; Де Приско, Роберто; Пенна, Паоло; Персиано, Джузеппе (2004). Дикерт, Фолькер; Хабиб, Мишель (ред.). «Детерминированные механизмы истинной аппроксимации для планирования связанных машин» . STACS 2004 . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 608–619. DOI : 10.1007 / 978-3-540-24749-4_53 . ISBN 978-3-540-24749-4.
^ Амбросио, Паскуале; Аулетта, Винченцо (2005). Персиано, Джузеппе; Солис-Оба, Роберто (ред.). «Детерминированные монотонные алгоритмы планирования на связанных машинах» . Аппроксимация и онлайн-алгоритмы . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 267–280. DOI : 10.1007 / 978-3-540-31833-0_22 . ISBN 978-3-540-31833-0.
^ Анделман, Нир; Азар, Йоси; Сорани, Мотти (2005). Дикерт, Фолькер; Дюран, Бруно (ред.). "Истинные механизмы приближения для планирования эгоистичных связанных машин" . STACS 2005 . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 69–82. DOI : 10.1007 / 978-3-540-31856-9_6 . ISBN 978-3-540-31856-9.
^ Ковач, Annamária (2005). Бродал, Герт Стёльтинг; Леонарди, Стефано (ред.). "Быстрый монотонный алгоритм 3-аппроксимации для планирования связанных машин" . Алгоритмы - ESA 2005 . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 616–627. DOI : 10.1007 / 11561071_55 . ISBN 978-3-540-31951-1.
^ Квок, Ю-Квонг; Ахмад, Ишфак (1999-12-01). «Алгоритмы статического планирования для распределения ориентированных графов задач на мультипроцессоры». ACM Computing Surveys . 31 (4): 406–471. CiteSeerX 10.1.1.322.2295 . DOI : 10.1145 / 344588.344618 . ISSN 0360-0300 .

[1] Горовиц, Эллис; Сахни, Сартадж (1976-04-01). «Точные и приближенные алгоритмы планирования неидентичных процессоров» . Журнал ACM . 23 (2): 317–327. DOI : 10.1145 / 321941.321951 . ISSN 0004-5411 .

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

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

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

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

[6] Hochbaum, Dorit S .; Шмойс, Дэвид Б. (1988-06-01). «Схема полиномиального приближения для планирования на унифицированных процессорах: использование подхода двойного приближения» . SIAM Journal on Computing . 17 (3): 539–551. DOI : 10.1137 / 0217033 . ISSN 0097-5397 .

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

[8] Арчер, А .; Тардос, Э. (2001-10-01). «Правдивые механизмы для однопараметрических агентов» . Материалы 42-го симпозиума IEEE по основам информатики : 482–491. DOI : 10.1109 / SFCS.2001.959924 .

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

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

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

[12] Ковач, Annamária (2005). Бродал, Герт Стёльтинг; Леонарди, Стефано (ред.). "Быстрый монотонный алгоритм 3-аппроксимации для планирования связанных машин" . Алгоритмы - ESA 2005 . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 616–627. DOI : 10.1007 / 11561071_55 . ISBN 978-3-540-31951-1.

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

Languages

In other projects