Дробное планирование работы

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

Варианты

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

В вариантах с вытеснением разные части задания должны обрабатываться в разное время. В трехполевой записи они обозначаются pmtn. Впервые их изучил Макнотон. ^{[ 1 ]}
В вариантах разделения разные части задания могут обрабатываться одновременно на разных машинах. Они обозначаются расколом и были введены Сином и Чжаном. ^{[ 2 ]}

Планирование заданий с упреждением

Были изучены различные проблемы планирования работы с упреждением. Одним из них является обобщенное многопроцессорное планирование (GMS). У него есть два варианта.

В первом варианте общее количество прерываний ограничено некоторым фиксированным целым числом.
Во втором варианте каждое задание $j$ имеет связанный параметр, который ограничивает количество раз $j$ может быть вытеснено в течение возможного графика.

В обоих вариантах цель состоит в том, чтобы найти расписание, которое минимизирует время обработки с учетом ограничений вытеснения.

За одинаковые машины , Щепин и Вахания ^{[ 3 ]} докажите, что не более чем $n-2$ тотальные вытеснения, проблема NP-трудна , тогда как Макнотон ^{[ 1 ]} показывает алгоритм линейного времени с $n-1$ упреждения.

Для однородных машин полиномиальный алгоритм Гонсалеса и Сахни ^{[ 4 ]} дает максимум $2n-2$ упреждения. Шахнай, Тамир и Вегингер ^{[ 5 ]} доказана NP-трудность для случая, когда число вытеснений строго меньше $2n-2$ . Они также представили PTAS для GMS с глобальным ограничением приоритета и еще один PTAS для GMS с ограничением приоритета по заданиям, когда количество машин является фиксированной константой.

Сопер и Струсевич ^{[ 6 ]} изучите особый случай, когда допускается не более одного прерывания. Они показывают, что минимизация периода обработки является полиномиальной для двух машин.

Во многих работах изучаются другие варианты упреждающего планирования. Например, Лю и Ченг ^{[ 7 ]} рассмотрите планирование для одной машины с датами выпуска заданий и доставки, где нет жесткого ограничения на количество приоритетов, но каждый приоритет требует затрат времени на «настройку задания».

Некоторые работы, такие как Блажевич и др. ^{[ 8 ]} или Дэнг и др. ^{[ 9 ]} изучить упреждающее планирование для заданий с параллелизмом, когда задания должны обрабатываться одновременно на нескольких процессорах.

Планирование заданий с разделением

Были изучены различные цели. Существует множество вариантов, включая разное время установки. При планировании работы машины «время настройки» означает время, необходимое для подготовки машины к конкретной работе или задаче. Время настройки, зависящее от последовательности, — это ситуация, когда время настройки, необходимое для задания, зависит от задания, которое было до него, а не является постоянным для всех заданий (время независимой настройки задания).

Серафим ^{[ 10 ]} предполагает неограниченные разделения и прерывания и дает алгоритмы с полиномиальным временем, которые минимизируют максимальное и максимальное взвешенное опоздание для однородных и несвязанных машин.

Син и Чжан ^{[ 2 ]} разрешить неограниченное разбиение и предоставить полиномиальные алгоритмы для многих критериев оптимальности (таких как время выполнения, задержка, опоздание и т. д.) с идентичными, однородными и несвязанными машинами. Для случая с независимым временем настройки задания они дают $7/4$ алгоритм аппроксимации .

Сон и др. ^{[ 11 ]} изучить минимизацию продолжительности выполнения работ на одной машине с ограничением доступности машины с нижней границей длины каждой части разделяемого задания.

Для одинаковых машин Шим и Ким ^{[ 12 ]} предложить алгоритм ветвей и границ с целью минимизировать общее опоздание за счет независимого времени настройки задания. Ялауи и Чу ^{[ 13 ]} предложить эвристику для решения той же проблемы с целью минимизировать время выполнения. Ким и др. ^{[ 14 ]} предложить двухфазный эвристический алгоритм с целью минимизировать общее опоздание. С целью минимизировать время обработки Ким ^{[ 15 ]} изучает другой вариант с временем наладки семейства, в котором наладка не требуется, когда детали из одного и того же задания производятся последовательно. И Ван и др. ^{[ 16 ]} включить свойство обучения, которое улучшает время обработки задания в соответствии с эффектом обучения. Обучение необходимо перезапустить, если одно задание разделено и обработано на другом компьютере.

Для однородных машин Ким и Ли ^{[ 17 ]} изучите вариант с выделенными машинами (для каждой работы есть несколько выделенных машин), временем настройки, зависящим от последовательности, и ограниченными ресурсами настройки (для работ требуются ограниченные операторы настройки) с целью минимизировать время выполнения. Криста, Сандерс и Фёкинг ^{[ 18 ]} Изучите минимизацию рабочего времени, используя вариант с k-разделением, вариант, в котором каждое задание можно разделить на большинство $k$ разные машины. Они показывают, что этот вариант и другой, более общий вариант, где каждое задание имеет свой собственный параметр расщепляемости, являются NP-трудными. Они предлагают некоторые алгоритмы аппроксимации, но их основным результатом является алгоритм с полиномиальным временем для обеих задач для фиксированного числа машин. Они показывают, что разрешение ограниченного числа разбиений снижает сложность планирования.

Во всех этих работах не существует глобального ограничения на количество разделяемых заданий.

Ссылки

^ Перейти обратно: ^а ^б Макнотон, Роберт (октябрь 1959 г.). «Планирование со сроками и функциями потерь» . Наука управления . 6 (1): 1–12. дои : 10.1287/mnsc.6.1.1 . ISSN 0025-1909 .
^ Перейти обратно: ^а ^б Син, Вэньсюнь; Чжан, Цзявэй (15 июля 2000 г.). «Параллельное машинное планирование с разделением заданий» . Дискретная прикладная математика . 103 (1): 259–269. дои : 10.1016/S0166-218X(00)00176-1 . ISSN 0166-218X .
^ Щепин, Евгений и Нодари Вахания. « Новая жесткая NP-жесткость вытесняющего мультипроцессора и открытого планирования ». Материалы 2-й междисциплинарной международной конференции по планированию: теория и приложения МИСТА 2005 . 2005.
^ Гонсалес, Теофило; Сахни, Сартадж (1 января 1978 г.). «Упреждающее планирование унифицированных процессорных систем» . Журнал АКМ . 25 (1): 92–101. дои : 10.1145/322047.322055 . ISSN 0004-5411 .
^ Шахнай, Хадас; Тамир, Тами; Вегингер, Герхард Дж. (1 июля 2005 г.). «Минимизация затрат на ремонт и упреждение в системе унифицированных машин» . Алгоритмика . 42 (3): 309–334. дои : 10.1007/s00453-005-1171-0 . ISSN 1432-0541 . S2CID 14256666 .
^ Сопер, Алан Дж.; Струсевич, Виталий А. (31 мая 2019 г.). «Расписания с одинарным вытеснением на однородных параллельных машинах» . Дискретная прикладная математика . Встреча GO X, Риги Кальтбад (Швейцария), 10–14 июля 2016 г. 261 : 332–343. дои : 10.1016/j.dam.2018.03.007 . ISSN 0166-218X . S2CID 126307013 .
^ Лю, Чжаохуэй; Ченг, Т.К. Эдвин (30 апреля 2002 г.). «Планирование с указанием дат выпуска заданий, сроков поставки и штрафов за упреждение» . Письма об обработке информации . 82 (2): 107–111. дои : 10.1016/S0020-0190(01)00251-4 . HDL : 10397/32337 . ISSN 0020-0190 .
^ Блажевич; Драбовский; Вегларц (май 1986 г.). «Планирование многопроцессорных задач для минимизации длины расписания» . Транзакции IEEE на компьютерах . С-35 (5): 389–393. дои : 10.1109/TC.1986.1676781 . ISSN 1557-9956 . S2CID 18188390 .
^ Дэн, Сяоте; Гу, Нянь; Брехт, Тим; Лу, Кайчэн (2000). «Упреждающее планирование параллельных заданий на мультипроцессорах» . SIAM Journal по вычислительной технике . 30 (1): 145–160. дои : 10.1137/S0097539797315598 . ISSN 0097-5397 . S2CID 1717179 .
^ Серафини, Паоло (1996). «Планирование заданий на нескольких машинах со свойством разделения заданий» . Исследование операций . 44 (4): 617–628. дои : 10.1287/опре.44.4.617 . ISSN 0030-364X . JSTOR 172004 .
^ Сын, Транг Хонг; Ван Ланг, Тран; Хюинь-Туонг, Нгуен; Сукхал, Амер (01 января 2021 г.). «Решение проблемы планирования заданий с ограниченным разделением на одной машине в доступных временных окнах» . Журнал окружающего интеллекта и гуманизированных вычислений . 12 (1): 1179–1196. дои : 10.1007/s12652-020-02162-0 . ISSN 1868-5145 . S2CID 255752164 .
^ Шим, Санг-О; Ким, Ён Дэ (01 марта 2008 г.). «Алгоритм ветвей и границ для идентичной задачи планирования параллельных машин со свойством разделения заданий» . Компьютеры и исследования операций . Часть специального выпуска: Новые тенденции в геолокационном анализе. 35 (3): 863–875. дои : 10.1016/j.cor.2006.04.006 . ISSN 0305-0548 .
^ ЯЛАУИ, ФАРУК; ЧУ, ЧЕНГБИН (01 февраля 2003 г.). «Эффективный эвристический подход для планирования параллельных машин с разделением заданий и временем настройки в зависимости от последовательности» . Операции IIE . 35 (2): 183–190. дои : 10.1080/07408170304382 . ISSN 0740-817X . S2CID 62630299 .
^ Ким*, Ю.-Д.; Шим, С.-О.; Ким, С.-Б.; Цой, Ю.-К.; Юн, Его Величество (1 ноября 2004 г.). «Планирование параллельных машин с учетом свойства разделения заданий» . Международный журнал производственных исследований . 42 (21): 4531–4546. дои : 10.1080/00207540410001720745 . ISSN 0020-7543 . S2CID 60729549 .
^ Ким, Хён Чжон (01 февраля 2018 г.). «Границы параллельного планирования машин с предопределенными частями заданий и временем настройки» . Анналы исследования операций . 261 (1): 401–412. дои : 10.1007/s10479-017-2615-z . ISSN 1572-9338 . S2CID 254228092 .
^ Ван, Чэньцзе; Лю, Чанчунь; Чжан, Чжихай; Чжэн, Ли (01 июля 2016 г.). «Минимизация общего времени завершения параллельного машинного планирования с разделением задач и обучением» . Компьютеры и промышленная инженерия . 97 : 170–182. дои : 10.1016/j.cie.2016.05.001 . ISSN 0360-8352 .
^ Ким, Хён Чжон; Ли, Джун Хо (01 февраля 2021 г.). «Планирование единых параллельных выделенных машин с разделением заданий, временем установки в зависимости от последовательности и несколькими серверами» . Компьютеры и исследования операций . 126 : 105115. doi : 10.1016/j.cor.2020.105115 . ISSN 0305-0548 . S2CID 225115689 .
^ Криста, Петр; Сандерс, Питер; Фёкинг, Бертольд (2003). «Планирование и распределение трафика для задач с ограниченной разделяемостью» . В Роване, Бранислав; Войташ, Питер (ред.). Математические основы информатики 2003 . Конспекты лекций по информатике. Том. 2747. Берлин, Гейдельберг: Springer. стр. 500–510. дои : 10.1007/978-3-540-45138-9_44 . hdl : 11858/00-001M-0000-0014-6BD1-8 . ISBN 978-3-540-45138-9 .

[:0-1] Перейти обратно: ^а ^б Макнотон, Роберт (октябрь 1959 г.). «Планирование со сроками и функциями потерь» . Наука управления . 6 (1): 1–12. дои : 10.1287/mnsc.6.1.1 . ISSN 0025-1909 .

[:1-2] Перейти обратно: ^а ^б Син, Вэньсюнь; Чжан, Цзявэй (15 июля 2000 г.). «Параллельное машинное планирование с разделением заданий» . Дискретная прикладная математика . 103 (1): 259–269. дои : 10.1016/S0166-218X(00)00176-1 . ISSN 0166-218X .

[3] Щепин, Евгений и Нодари Вахания. « Новая жесткая NP-жесткость вытесняющего мультипроцессора и открытого планирования ». Материалы 2-й междисциплинарной международной конференции по планированию: теория и приложения МИСТА 2005 . 2005.

[4] Гонсалес, Теофило; Сахни, Сартадж (1 января 1978 г.). «Упреждающее планирование унифицированных процессорных систем» . Журнал АКМ . 25 (1): 92–101. дои : 10.1145/322047.322055 . ISSN 0004-5411 .

[5] Шахнай, Хадас; Тамир, Тами; Вегингер, Герхард Дж. (1 июля 2005 г.). «Минимизация затрат на ремонт и упреждение в системе унифицированных машин» . Алгоритмика . 42 (3): 309–334. дои : 10.1007/s00453-005-1171-0 . ISSN 1432-0541 . S2CID 14256666 .

[6] Сопер, Алан Дж.; Струсевич, Виталий А. (31 мая 2019 г.). «Расписания с одинарным вытеснением на однородных параллельных машинах» . Дискретная прикладная математика . Встреча GO X, Риги Кальтбад (Швейцария), 10–14 июля 2016 г. 261 : 332–343. дои : 10.1016/j.dam.2018.03.007 . ISSN 0166-218X . S2CID 126307013 .

[7] Лю, Чжаохуэй; Ченг, Т.К. Эдвин (30 апреля 2002 г.). «Планирование с указанием дат выпуска заданий, сроков поставки и штрафов за упреждение» . Письма об обработке информации . 82 (2): 107–111. дои : 10.1016/S0020-0190(01)00251-4 . HDL : 10397/32337 . ISSN 0020-0190 .

[8] Блажевич; Драбовский; Вегларц (май 1986 г.). «Планирование многопроцессорных задач для минимизации длины расписания» . Транзакции IEEE на компьютерах . С-35 (5): 389–393. дои : 10.1109/TC.1986.1676781 . ISSN 1557-9956 . S2CID 18188390 .

[9] Дэн, Сяоте; Гу, Нянь; Брехт, Тим; Лу, Кайчэн (2000). «Упреждающее планирование параллельных заданий на мультипроцессорах» . SIAM Journal по вычислительной технике . 30 (1): 145–160. дои : 10.1137/S0097539797315598 . ISSN 0097-5397 . S2CID 1717179 .

[10] Серафини, Паоло (1996). «Планирование заданий на нескольких машинах со свойством разделения заданий» . Исследование операций . 44 (4): 617–628. дои : 10.1287/опре.44.4.617 . ISSN 0030-364X . JSTOR 172004 .

[11] Сын, Транг Хонг; Ван Ланг, Тран; Хюинь-Туонг, Нгуен; Сукхал, Амер (01 января 2021 г.). «Решение проблемы планирования заданий с ограниченным разделением на одной машине в доступных временных окнах» . Журнал окружающего интеллекта и гуманизированных вычислений . 12 (1): 1179–1196. дои : 10.1007/s12652-020-02162-0 . ISSN 1868-5145 . S2CID 255752164 .

[12] Шим, Санг-О; Ким, Ён Дэ (01 марта 2008 г.). «Алгоритм ветвей и границ для идентичной задачи планирования параллельных машин со свойством разделения заданий» . Компьютеры и исследования операций . Часть специального выпуска: Новые тенденции в геолокационном анализе. 35 (3): 863–875. дои : 10.1016/j.cor.2006.04.006 . ISSN 0305-0548 .

[13] ЯЛАУИ, ФАРУК; ЧУ, ЧЕНГБИН (01 февраля 2003 г.). «Эффективный эвристический подход для планирования параллельных машин с разделением заданий и временем настройки в зависимости от последовательности» . Операции IIE . 35 (2): 183–190. дои : 10.1080/07408170304382 . ISSN 0740-817X . S2CID 62630299 .

[14] Ким*, Ю.-Д.; Шим, С.-О.; Ким, С.-Б.; Цой, Ю.-К.; Юн, Его Величество (1 ноября 2004 г.). «Планирование параллельных машин с учетом свойства разделения заданий» . Международный журнал производственных исследований . 42 (21): 4531–4546. дои : 10.1080/00207540410001720745 . ISSN 0020-7543 . S2CID 60729549 .

[15] Ким, Хён Чжон (01 февраля 2018 г.). «Границы параллельного планирования машин с предопределенными частями заданий и временем настройки» . Анналы исследования операций . 261 (1): 401–412. дои : 10.1007/s10479-017-2615-z . ISSN 1572-9338 . S2CID 254228092 .

[16] Ван, Чэньцзе; Лю, Чанчунь; Чжан, Чжихай; Чжэн, Ли (01 июля 2016 г.). «Минимизация общего времени завершения параллельного машинного планирования с разделением задач и обучением» . Компьютеры и промышленная инженерия . 97 : 170–182. дои : 10.1016/j.cie.2016.05.001 . ISSN 0360-8352 .

[17] Ким, Хён Чжон; Ли, Джун Хо (01 февраля 2021 г.). «Планирование единых параллельных выделенных машин с разделением заданий, временем установки в зависимости от последовательности и несколькими серверами» . Компьютеры и исследования операций . 126 : 105115. doi : 10.1016/j.cor.2020.105115 . ISSN 0305-0548 . S2CID 225115689 .

[18] Криста, Петр; Сандерс, Питер; Фёкинг, Бертольд (2003). «Планирование и распределение трафика для задач с ограниченной разделяемостью» . В Роване, Бранислав; Войташ, Питер (ред.). Математические основы информатики 2003 . Конспекты лекций по информатике. Том. 2747. Берлин, Гейдельберг: Springer. стр. 500–510. дои : 10.1007/978-3-540-45138-9_44 . hdl : 11858/00-001M-0000-0014-6BD1-8 . ISBN 978-3-540-45138-9 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]