ПДС-АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ МИНИМИЗАЦИИ СУММАРНОГО ЗАПАЗДЫВАНИЯ ПРИ ВЫПОЛНЕНИИ ПАРАЛЛЕЛЬНЫМИ ПРИБОРАМИ ЗАДАНИЙ С ОБЩИМ ДИРЕКТИВНЫМ СРОКОМ



ПАВЛОВ А.А., Мисюра Е.Б. Кратко изложены основные теоретические свойства задачи и описан ПДС-алгоритм ее решения.

The basic theoretical properties of the problem aregiven in brief and the PDC-algorithm of its solution is described.

Введение

Рассматривается задача построения расписания для параллельных идентичных приборов выполнения заданий, минимизирующего суммарное запаздывание выполнения заданий относительно общего директивного срока (МСЗПО).Для фиксированного одинакового момента запуска приборов задача является _NP-_трудной. Эффективный алгоритм решения этой задачи(МСЗП) приведен в [1]. Мы обобщаем решение задачи МСЗП на общий случай, когда моменты времени за­пуска приборов являются фиксированными в произвольные моменты времени.

Постановка задачи МСЗПО

Задано множество заданийJ = {1, 2,..., n}, m приборов равной производительности, для каждого задания $j\in J$ известна длительность выполнения ${{l}_{i}}$. Все задания имеют общий директивный срок d. Моменты запуска приборов на выполнение работ ${{r}_{i}}$, $i=\overline{1,m}$, различны. Простои приборов при выполнении заданий запрещены.

Необходимо построить расписание $\sigma $ выполнения заданий $j\in J$ на m приборах такое, чтобы достигался минимум функционала:

\[F(\sigma )~=~\sum\limits_{j\in{J}}{\max [0;\ {{C}_{j}}\left( \sigma \right)-d]},\]

где ${{C}_{j}}\left(\sigma \right)$ – момент завершения выполнения задания j в последовательности $\sigma $.

Сформулированная задача относится к классу NP-трудных [2]. Мы развиваем результаты, изложенные в [1], и предлагаем ПДС-алго­ритм решения задачи, обладающий такими свойствами: на основе теоретических свойств за­дачи МСЗП находятся логико-аналитические ус­ловия (p-усло­вия), выполнение которых в процессе реализации заданной полиномиальной вычислительной схемой приводит к получению оп­тимального решения. Выполнение этих условий также служит критерием останова вычислений экпоненциальной составляющей ПДС-ал­го­рит­ма.

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

В [4] исследованы теоретические свойства задачи МСЗПО. Получены признаки оптимальности полиномиальной составляющей ПДС-ал­горитма и оценка отклонения от оптимального решения для экспоненциальной составляющей.

ПДС-алгоритм решения задачи МСЗП [1], входящий в состав ПДС-алгоритма для задачи МСЗПО, состоит из двух этапов: этап 1 (Ал­горитм А0) – построение начального расписания ${{\sigma}^{уп}}$, этап 2(Алгоритм А) – приближенный алгоритм построения расписания с оценкой отклонения от оптимального, основанный на направленных улучшающих перестановках. Трудоемкость алгорит­ма А определяется полиномом О(mn logn).

Исследование свойств задачи МСЗПО

Лемма 1[3]. Пусть обслуживание заданий L-м прибором не может быть начато раньше момента времени ${{r}_{L}}\ge 0$, L = 1,m. Расписанию $\sigma $, при котором каждое очередное задание k = 1, 2, …, n назначается на обслуживание на тот прибор, который раньше других оказывается свободным, соответствует наименьшее значение суммы времен завершения обслуживания всех заданий.

Теорема 1. В расписании ${{\sigma }^{уп}}$ не существует перестановок заданий, выполняемых между приборами $i\in {{\sigma }^{1}}$ и $i\in{{\sigma }^{2}}$, приводящих к умень­шению значения функционала.

Доказательство [4] основано на утверждениях 1–3 и 11 из [4], лемме 1 и теореме[3], в соответствии с которой поиск оптимального расписания можно ограничить рассмотрением расписаний, при которых каждый прибор обслуживает задания в порядке возрастания их номеров.

Рассмотрим расписание на приборах ${{i}_{r}}\in {{\sigma }^{1}}$ и ${{i}_{s}}\in{{\sigma }^{2}}$. Пусть задание ${{j}_{k}}$ выполняется на приборе ${{i}_{r}}$, а задание ${{j}_{p}}$ – на приборе ${{i}_{s}}$, причем задания ${{j}_{k}}$ и ${{j}_{p}}$ принадлежат одному уровню запаздывающих заданий. Для этих заданий выполняется: ${{l}_{{{j}_{k}}}}\le {{l}_{{{j}_{p}}}}$, в соответствии с алгоритмом построения последовательности ${{\sigma }^{}}$. Поменяем эти задания местами, т.е. задание ${{j}_{k}}$ будет выполняться на приборе ${{i}_{s}}$, а задание ${{j}_{p}}$ – на приборе ${{i}_{r}}$. В результате такой перестановки, в соответствии с утверждением 2,значение функционала увеличивается. Перестановки запаздывающих заданий, принадлежащих разным уровням запаздывания, в соответствии с леммой 1 [3],также приводят к увеличению значения функционала. В соответствии с утверждениями 1–3 [4], задания $j\in{{\sigma }^{2}}$ не могут быть перемещены в множества не запаздывающих заданий или запаздывающих заданий, для которых момент начала выполнения меньше их директивного срока. Сле­дова­тельно, в расписании ${{\sigma }^{уп}}$ не существует улучшающих перестановок между последовательностями ${{\sigma }^{1}}$ и ${{\sigma }^{2}}$. Теорема доказана.

Теорема 2. Значение функционала по задаче МСЗПО равно сумме значений функционала последовательностей ${{\sigma }^{1}}$ и ${{\sigma }^{2}}$.

ПДС-алгоритм решения задачи МСЗПО

$1.$ Построение начального расписания ${{\sigma }^{уп}}$ по Алгоритму А0 [1].

$3.$ Выполнение ПДС-алгоритма А [1] на последовательности ${{\sigma }^{1}}$.

$4.$ Анализ полученного решения. Если реализовалась полиномиальная составляющая алгоритма, расписание ${{\sigma }^{1}}$ оптимально,переход на п. 5. Иначе переход на п. 6.

$5$. Определение значения функционала для последовательности ${{\sigma }^{1}}$. Переход на п. 7.

$6.$ Определение значения функционала и оценки отклонения значения функционала от оптимального для последовательности ${{\sigma}^{1}}$.

$7.$ Определение значения функционала последовательности ${{\sigma }^{2}}$, оптимальной по построению.

$8.$ Определение значения функционала задачи МСЗПО в соответствии с теоремой 2. Конец.

Трудоемкость ПДС-алгоритма решения задачи МСЗПО определяется трудоемкостью ПДС-ал­горитма решения задачи МСЗП и равна О(mn logn). Для задачи МСЗП были проведены испытания на задачах с размерностью до 40 000 заданий с числом приборов до 30-ти. Среднее время решения задачи МСЗП при использовании алгоритма А не превысило 35 мс. Средняя частота получения оптимального решения составила 74,1%. Среднее отклонение от оптимального решения составило 0,00016.

Список литературы

$1.$ Згуровский М.З., Павлов А.А. Принятие решений в сетевыхсистемах с ограниченными ресурсами: Монография. – К.: Наукова думка. – 2010. –573 с.

$2.$ Гери М.Р., Джонсон Д.С. Вычислительные машины итруднорешаемые задачи. – М.: Мир, 1982. – 416 с.

$3.$ ТанаевВ.С., Шкурба В.В. Введение в теорию расписаний. – М.: Наука, 1975.–256 с.

$4.$ ПавловА.А., Мисюра Е.Б. Минимизация суммарного запаздывания при выполнении независимых заданий с общим директивным сроком идентичными параллельными приборами, моменты запуска которых произвольны //Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». –К.: “ВЕК+”, 2013. – №59 – С.28–34.

Jun 30, 2016