Минимизация суммарного запаздывания выполнения заданий параллельными приборами (стр. 1 )

Глава 3 Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами

Труднорешаемая задача комбинаторной оптимизации «Минимизация суммарного запаздывания при выполнении независимых заданий с равными весами и общим директивным сроком параллельными приборами» (МСЗП) формулируется следующим образом.

Задано множество заданий J, число приборов m, для каждого j Î J известна длительность выполнения lj. Все задания имеют общий директивный срок d. Необходимо построить расписание s выполнения заданий j Î J на m приборах одинаковой производительности такое, чтобы достигался минимум функционала:

F(s) = max [0; Cj(s) – d],

где Cj(s) — момент завершения выполнения задания j в последовательности s.

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

Сформулированная задача относится к классу NP-трудных [8]. Она разрешима за псевдополиномиальное время при m = 2. Впервые эта задача рассматривалась нами в [38].

Указанная задача находит широкое применение при разработке систем планирования производства, управления проектами, управления строительством и в других областях. В частности, алгоритм решения задачи использован в иерархической модели планирования и управления сложными системами, имеющими сетевое представление технологических процессов и ограниченные ресурсы (глава 8).

В [76] получены следующие результаты. Пусть задания множества J = {1, 2,..., n} пронумерованы в порядке неубывания значений lj; Jk ΠJ – множество заданий, обслуживаемых k-м прибором. Jk= {Yk, Rk}; ji Î Yk, если Ci < d. В противном случае ji Î Rk.

Теорема 3.1 [76]. Существует оптимальное расписание, при котором

1) Ψ = {1, 2, …, |Ψ|},

2) если |Ψ| < n, то , и Rk содержит те и только те элементы R = {|Ψ|+1, …, n}, которые отличаются от |Ψ| + k на величину, кратную m, k = , где , а, если .

Пусть Q(m) – класс расписаний, удовлетворяющих условиям теоремы 3.1 и дополнительным условиям: |Ψ| = m, где m – натуральное число. Оптимальное расписание q* принадлежит хотя бы одному из классов Q(m) при некотором m = m*.

Теорема 3.2 [76]. Расписание qÎQ(m) является оптимальным в Q(m), если при этом расписании величина достигает наименьшего значения. Здесь: ; c(m) – число, равное остатку от деления (n – m) на m при n – m > 0 и равное m в противном случае.

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

Пронумеруем задания множества J = {1, 2,..., n} по неубыванию значений lj и разобьем на (необязательные непустые) подмножества J1, J2,..., Ji,..., Jm, попарно не имеющие общих элементов, где Ji – множество заданий, обслуживаемых i-м прибором i = .

Поиск оптимального расписания в соответствии с известной теоремой можно ограничить рассмотрением расписаний, при которых каждый прибор обслуживает задания в порядке возрастания их номеров [76].

Действительно, если в оптимальной последовательности si* = (j1*, j2*,..., jn*) для некоторых заданий jk, jk+1 выполняется ljk > ljk+1, то последовательности si, отличающейся от si* транспонированием элементов jk* и j*k+1, соответствует меньшее значение рассматриваемого функционала, что противоречит предположению об оптимальности si*.

Разобьем множество заданий Ji на подмножества Pi(s), Si(s), Qi(s) по следующему признаку:

Pi(s) – множество незапаздывающих заданий в расписании прибора i;

Si(s) – множество запаздывающих заданий в расписании прибора i, для которых выполняются условия:

Sjн < d, Cj > d, j Î Si(s),

где Sjн — момент начала выполнения задания j;

Qi(s) – множество запаздывающих заданий в расписании прибора i, для которых выполняются условия:

Sjн < d, "j ΠQi(s),

P = Pi; S = Si; Q = Qi;

Ri(s) – резерв времени прибора i в расписании s

Ri(s) = d – lj;

i(s) – запаздывание в выполнении задания j Î Si(s) относительно директивного срока:

i =lj – d.

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

Теорема 3.3. Существует оптимальное расписание, при котором выполняются условия:

1) P U S = {1, 2,..., | P U S |};

2) если P U S < n, то , и Qi \ Si содержит те и только те элементы, которые отличаются от | P U S | + i на величину, кратную m, i = .

Обозначим через YPS класс расписаний, удовлетворяющий условию теоремы 3.3, и через YPS(m) класс расписаний, удовлетворяющий условию | P(s) U S(s) | = m, m – натуральное число. Можно сказать, что YPS(m) Ì YPS. Оптимальное расписание s* принадлежит хотя бы одному из классов YPS(m) при некотором m=m*. Число различных непустых классов YPS(m) не превышает m. [76]

Пусть () – наибольшее (наименьшее) значение m, при котором YPS ¹ Æ. Обозначим через c(s) число, равное остатку от деления n – | P(s) U S(s) | на m при n – | P(s) U S(s) | > 0, и равное m в противном случае. В теореме 3.4 приведены достаточные условия, при которых расписанию s Î YPS(m) соответствует наименьшее суммарное запаздывание среди всех расписаний, принадлежащих классу YPS(m), £ m £ . [76]

Теорема 3.4. Расписание s Î YPS(m) является оптимальным в YPS(m), если при этом величина Z(s) =  достигает наименьшего значения. [76]

Обозначим через s* оптимальное расписание выполнения множества заданий J.

Следующая теорема позволяет оценить отклонение произвольного расписания от оптимального.

Теорема 3.5. Если расписание s Î YPS, то F(s) – F(s*) £ z(s).[76]

Следствие. Если s Î YPS и z(s) = 0, то расписание s – оптимально.

В теореме 3.4 сформулированы условия локальной оптимальности, (т. е. оптимальности в классе YPS(m),  £ m £ ), поэтому для произвольных расписаний s¢ Î YPS(m¢) и s² Î YPS(m²), m¢ ¹ m², z(s¢) ¹ 0, z(s²) ¹ 0, из справедливости неравенства z(s¢) < z(s²) не следует справедливость неравенства F(s¢) < F(s²).

Приведем пример: задано: m = 4, d = 9 и значения j и lj:

j	1	2	3	4	5	6	7	8	9	10
lj	2	2	2	2	8	8	8	10	10	10

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

Расписание s¢: J1(s¢) = 2, 8, 10; J2(s¢) = 2, 8, 10; J3(s¢) = 2, 8; J4(s¢) = 2, 10; F(s¢) = 28.

Расписание s²: J1(s²) = 8, 10; J2(s²) = 8, 10; J3(s²) = 8, 10; J4(s²) = 2, 2, 2, 2;

z(s¢) = 2 < z(s²) = 27; F(s¢) = 28 > F(s²) = 27.

Выделим из класса YPS класс расписаний YP Î YPS, удовлетворяющий дополнительно следующим условиям:

1) P = {1, 2,..., | P |};

2) lj > Ri(s);

3) , если , " jk, jl Î S(s).

Пусть | P | < n. Обозначим: Pmin – минимальное количество заданий множества P, при котором YP ¹ Æ; Pmax – максимальное количество заданий множества P.

Утверждение 3.1. Для всех возможных расписаний s Î YP, построенных на множестве заданий J, справедливо:

Pmax – Pmin < m.

Доказательство. Для любого расписания s Î YP выполняется

= d · m – .

Следовательно, | P(s) | = Pmin (Pmax) справедливо для такого расписания s, в котором имеет максимально возможное (минимально возможное) значение среди всех расписаний класса YP. Но для каждого прибора i расписания s Î YP выполняется: Ri(s) < lj.

Следовательно,

Ri(s) < m ·lj £ l|P(s)|+i и Pmax – Pmin < m.

Утверждение 3.2. Максимальная разность количества запаздывающих заданий на приборах в расписаниях s Î YP не превышает единицы.

Справедливость этого утверждения очевидна и следует непосредственно из определения класса YP.

Определение 3.1. Расписание с одинаковым числом запаздывающих заданий на приборах назовем равномерным.

Теорема 3.6. Равномерное расписание s Î YP является оптимальным.

Доказательство. Пусть Li – количество запаздывающих заданий на приборе i. Рассмотрим следующие случаи:

а) Ri = 0; i = ; Ri > 0; i = ; Li = L; "i = .

Расписание s(а) оптимально, поскольку

z(s(а)) = Di =Di = 0;

б) Ri = 0; "i = ; Li = L; "i = .

Расписание s(б) оптимально, так как c(s(б)) = 0;

в) Ri > 0; i = ; Li = L; "i = .

Расписание s(в) оптимально, так как c(s(в)) = 0.

Теорема доказана.

Введем обозначения:

Lmax – максимальное число запаздывающих заданий на приборах;

Lmin – минимальное число запаздывающих заданий на приборах;

 – приборы с числом запаздывающих заданий Lmax;

| P(s) | = P – мощность множества P(s);

DS(s) = Di;

RS(s) = ; WS(s) = min{RS(s), DS(s)}.