Проблема планирования параллельных задач - Parallel task scheduling problem

В теоретической информатике проблема планирования параллельных задач является NP-жесткий проблема оптимизации. Данный набор ${ displaystyle n}$ параллельные задачи, также называемые заданиями, должны быть запланированы на ${ displaystyle m}$ идентичные машины, иногда называемые процессорами, что сводит к минимуму время последнего завершения. В Veltman et al.^[1] и Дроздовский^[2], эта проблема обозначается ${ displaystyle P | size_ {j} | C _ { max}}$ в трехпольная запись введено Graham et al. ^[3]. Истоки этой постановки проблемы восходят к 1960 г.^[4]. Для этой задачи не существует алгоритма полиномиальной аппроксимации времени с отношением меньше, чем ${ displaystyle 3/2}$ пока не ${ displaystyle P = NP}$.

Определение

В этой задаче нам дан набор ${ displaystyle { mathcal {J}}}$ из ${ displaystyle n}$ рабочие места, а также ${ displaystyle m}$ одинаковые машины. ${ displaystyle j in { mathcal {J}}}$ есть время обработки ${ displaystyle p_ {j} in mathbb {N}}$ и требует одновременного использования ${ displaystyle q_ {j} in mathbb {N}}$ машины во время его выполнения. Расписание назначает каждое задание ${ displaystyle j in { mathcal {J}}}$ ко времени начала ${ displaystyle s_ {j} in mathbb {N} _ {0}}$ и набор ${ displaystyle m_ {j} substeq {1, dots, m }}$ из ${ displaystyle | m_ {j} | = q_ {j}}$ Это возможно, если каждый процессор выполняет не более одного задания в любой момент времени. Цель проблемы, обозначенная ${ displaystyle P | size_ {j} | C _ { max}}$ найти расписание с минимальной длиной ${ displaystyle C _ { max} = max _ {j in { mathcal {J}}} (s_ {j} + p_ {j})}$, также называемый периодом изготовления расписания. Достаточным условием выполнимости расписания является следующее

${ displaystyle sum _ {j in { mathcal {J}}, s_ {j} leq t$.

Если это свойство выполняется для всех моментов времени запуска, можно сгенерировать возможное расписание, назначив заданиям свободные машины в каждый момент времени, начиная с момента времени. ${ displaystyle t = 0}$.^[5][6]. Кроме того, количество машинных интервалов, используемых заданиями, и интервалов простоя на каждом временном шаге может быть ограничено ${ displaystyle | { mathcal {J}} | +1}$^[5]. Здесь машинный интервал - это набор следующих друг за другом машин максимальной мощности, так что все машины в этом наборе обрабатывают одно и то же задание. Машинный интервал полностью определяется индексом его первой и последней машины. Следовательно, можно получить компактный способ кодирования вывода с полиномиальным размером.

Твердость

Эта проблема NP-трудна даже для постоянного количества машин из-за того, что ${ displaystyle P2 || C _ { max}}$ соответствует проблема раздела. Кроме того, Ду и Люн^[7] показал, что эта проблема сильно NP-жесткий когда количество машин не менее ${ displaystyle m = 5}$, и что существует псевдополиномиальное время алгоритм, который решает проблему именно в том случае, если количество машин не превышает ${ displaystyle m = 3}$. Позже Хеннинг и др.^[8] показал, что проблема также является NP-трудной, когда количество машин ${ displaystyle m = 4}$. Если количество машин не ограничено константой, не может быть алгоритма аппроксимации с коэффициентом аппроксимации меньше, чем ${ displaystyle 3/2}$ пока не ${ displaystyle P = NP}$ потому что эта проблема содержит проблема с упаковкой бункера как подслучай, т.е. когда все задания имеют время обработки ${ displaystyle p_ {j} = 1}$.

Варианты

Изучено несколько вариантов этой проблемы.^[2]. Следующие варианты также рассматривались в сочетании друг с другом.

Смежные вакансии: В этом варианте машины имеют фиксированный заказ. ${ displaystyle (M_ {1}, dots, M_ {m})}$. Вместо того, чтобы назначать задания какому-либо подмножеству ${ displaystyle m_ {j} substeq {M_ {1}, dots, M_ {m} }}$, задания должны быть назначены интервалу машин. Эта задача соответствует постановке задачи проблема упаковки полосы.

Формовочные работы: В этом варианте каждая работа ${ displaystyle j in { mathcal {J}}}$ имеет набор возможных машинных номеров ${ Displaystyle D substeq {1, точки м }}$ и для каждого из этих чисел ${ displaystyle d in D}$ у него есть время обработки ${ displaystyle p_ {j, d}}$. Чтобы запланировать работу ${ displaystyle j in { mathcal {J}}}$, алгоритм должен выбрать номер машины ${ displaystyle d in D}$ и назначьте время начала ${ displaystyle s_ {j}}$ и чтобы ${ displaystyle d}$ машины за временной интервал ${ displaystyle [s_ {j}, s_ {j} + p_ {j, d}).}$ Обычное допущение для такого рода проблем состоит в том, что работа, которая определяется как ${ displaystyle d cdot p_ {j, d}}$ не увеличивается для увеличивающегося числа машин.

Несколько платформ: В этом варианте набор машин разбит на независимые платформы. Запланированное задание может использовать машины только одной платформы и не может охватывать несколько платформ при обработке.

Алгоритмы

Алгоритм составления списков Гэри и Грэхема^[9] имеет абсолютное соотношение ${ displaystyle 2}$, как указывает Турек и др.^[10] и Людвиг и Тивари^[11]. Фельдманн, Сгалл и Тенг^[12] заметил, что длина невытесняющего расписания, созданного алгоритмом планирования списка, на самом деле не превышает ${ displaystyle (2-1 / м)}$ раз оптимальное время вытеснения. Схема полиномиальной аппроксимации (PTAS) для случая, когда число ${ displaystyle m}$ процессоров постоянна, обозначается ${ displaystyle Pm | size_ {j} | C _ { max}}$, был представлен Amoura et al.^[13] и Jansen et al.^[14]Позже Янсен и Теле ^[6] нашел PTAS для случая, когда количество процессоров полиномиально ограничено по количеству рабочих мест. В этом алгоритме количество машин полиномиально зависит от временной сложности алгоритма. Поскольку, как правило, количество машин появляется только в логарифмическом масштабе в размере экземпляра, этот алгоритм также является схемой псевдополиномиального приближения по времени. А ${ Displaystyle (3/2 + varepsilon)}$- приближение дано Янсеном^[15], что закрывает пробел до нижней границы ${ displaystyle 3/2}$ за исключением сколь угодно малого ${ displaystyle varepsilon}$.

Различия между смежными и несмежными заданиями

Для случая задачи планирования параллельных задач оптимальная продолжительность выполнения может различаться в зависимости от ограничения на смежность машин. Если задания могут быть запланированы на несмежных машинах, оптимальная продолжительность выполнения может быть меньше, чем в случае, когда они должны быть запланированы на смежных. Разница между непрерывным и несмежным расписанием была впервые продемонстрирована в 1992 году.^[16] в случае с ${ displaystyle n = 8}$ задачи, ${ displaystyle m = 23}$ процессоры, ${ displaystyle C _ { max} ^ {nc} = 17}$, и ${ displaystyle C _ { max} ^ {c} = 18}$.Błdek et al. ^[17] изучили эти так называемые c / nc-разности и доказали следующие моменты:

• Для возникновения c / nc-разницы должно быть как минимум три задачи с ${ displaystyle q_ {j}> 1.}$
• Для возникновения c / nc-разницы должно быть как минимум три задачи с ${ displaystyle p_ {j}> 1.}$
• Чтобы возникла c / nc-разница, по крайней мере, ${ displaystyle m = 4}$ требуются процессоры (и существует экземпляр с разницей c / nc с ${ displaystyle m = 4}$).
• Для возникновения разницы c / nc длина несмежного расписания должна быть не менее ${ displaystyle C _ { max} ^ {nc} = 4.}$
• Максимальная разница c / nc ${ Displaystyle sup _ {I} C _ { max} ^ {c} (I) / C _ { max} ^ {nc} (I)}$ по крайней мере ${ displaystyle 5/4}$ и самое большее ${ displaystyle 2.}$
• Решить, есть ли разница c / nc в данном экземпляре, является NP-полным.

Кроме того, они предложили следующие две гипотезы, которые остались недоказанными:

• Чтобы возникла разница c / nc, по крайней мере, ${ displaystyle n = 7}$ задачи обязательны.
• ${ Displaystyle sup _ {I} C _ { max} ^ {c} (I) / C _ { max} ^ {nc} (I) = 5/4}$

Смотрите также

• Планирование работы магазина
• Планирование открытых магазинов

Рекомендации