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

Перестановка 1P-1S-W1. Меняем местами задания j ¢ Î Pr(s), r Î IR(s) и j ² ΠSh(s), h Î I∆(s). Задания j ¢ и j ² удовлетворяют следующим условиям:

lj² £ lj¢ + Rr(s) и lj¢ < Rh(s).

В результате этой перестановки получаем расписание s¢ такое, что

I∆(s¢) = I∆(s) | h;

F(s¢) = F(s) – (lj² – Rh(s)).

W(s¢) = W(s) – (lj² – Rh(s));

Перестановка 1P-1S-W2. Меняются местами задания j ¢ Î Pr(s), r Î IR(s) и j ² ΠSh(s), h Î I∆(s) такие, что

lj² £ lj¢ + Rr(s) и lj¢ > Rh(s).

В результате этой перестановки получаем расписание s¢ такое, что

I∆(s¢) = I∆(s);

F(s¢) = F(s) – (lj² – lj¢).

W(s¢) = W(s) – (lj² – lj¢));

Перестановка 1P-1S-W3. Меняются местами задания j ¢ Î Pr(s), r Î IR(s) и j ² ΠSh(s), h Î I∆(s) такие, что lj² > lj¢ + Rr(s) и lj¢ < Rh(s). После перестановки имеем расписание s¢, для которого выполняется

I∆(s¢) = I∆(s);

F(s¢) = F(s) – (lj¢ + Rr(s) – Rh(s));

W(s¢) = W(s) – (lj¢ + Rr(s) – Rh(s)).

Указанные типы перестановок в процессе реализации алгоритма могут выполняться как для отдельных заданий, так и для групп заданий j ΠJi, i = . При этом при проверке условий выполнения перестановок учитывается суммарная длительность перемещаемых заданий j ΠJi, i = . В этом случае реализуется экспоненциальная составляющая алгоритма, заключающаяся в переборе всех возможных вариантов расстановок заданий по приборам.

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

В соответствии с приведенной выше вычислительной схемой построены ПДС-алгоритмы решения задачи А1 и А2, которые применяются в зависимости от параметров исходных данных.

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

Алгоритм А10. Построение начального расписания s0 Î YP

1. Перенумеруем задания множества J по неубыванию длительностей выполнения.

2. Полагаем времена освобождения приборов Ti = 0, i = .

3. Полагаем j = 1, i = 1.

4. Если lj + Tj > d, то идем на выполнение п. 6. В противном случае назначаем задание j на прибор i. Полагаем

Ti = Ti + lj. 

5. Переходим к следующему заданию: j = j + 1. Если j > n, конец алгоритма. В противном случае переходим к п. 4.

6. Переходим к следующему прибору: i = i + 1. Если i £ m, то идем на выполнение п. 4. В противном случае полагаем Q (s0) = {j, j + 1, …, n} и выполняем алгоритм AQ. Конец алгоритма А10.

Алгоритм AQ

1. Определяем резервы приборов Ri(s0) = d –lj; i = .

2. Перенумеруем приборы таким образом, чтобы выполнялась система неравенств

R1(s0) ³ R2(s0) ³ ... ³ Rm(s0).

3. Полагаем i = 1.

4. назначаем задание j на прибор i.

5. Полагаем j = j + 1. Если j > n, то конец алгоритма АQ – получили расписание s0. В противном случае выполняем следующий пункт.

6. Полагаем i = i + 1, если i < m, и i = 1, если i = m. Идем на выполнение п. 4.

Алгоритм А1

Этап I. Построение начального расписания s0 Î YP.

1. По алгоритму А10 строим начальное расписание s0 Î YP.

2. Определяем WS(s0). Если WS(s0) = 0, то расписание оптимально, конец алгоритма. В противном случае переходим к пункту 3.

3. Если RS(s) ³ DS(s), выполняем пункт 4. Иначе полагаем s = s0, переходим к п. 9.

Этап II. Построение равномерного расписания s Î Y(sP) с числом запаздывающих заданий на каждом приборе i, равном L(s) = L(s0) – 1.

4. Полагаем s = s0, h = 1, f = f(s), где f – количество приборов с большим числом запаздывающих заданий.

5. Если для прибора h возможна перестановка 1P-0P-∆, то выполняем ее. Получаем расписание s¢. Переходим к п. 7, в противном случае переходим к п. 6.

6. Если для прибора h возможна перестановка 1P-1P-∆, то выполняем ее и переходим к п. 7. В случае отсутствия указанной перестановки идем на следующий пункт.

7. Полагаем h = h + 1. Если h £ f, переходим к п. 5, иначе к п. 8.

8. Если WS(s) = 0, то реализовалась полиномиальная составляющая алгоритма, расписание s оптимально, конец алгоритма. Иначе переходим к п. 14.

Этап III. Построение равномерного расписания s Î Y(sP) с числом запаздывающих заданий на каждом приборе i, равном L(s) = L(s0).

9. Полагаем r = f(s) + 1.

10. Если для прибора r возможна перестановка 1P-0P-R∆, выполняем ее. Получаем расписание s¢, переходим к п. 12. В противном случае выполняем следующий пункт.

11. Если для прибора r возможна перестановка 1P-1P-R∆, выполняем ее. Получаем расписание s¢, переходим к п. 12. В противном случае переходим к следующему пункту.

12. Полагаем r = r + 1. Если r £ m, идем на п. 10, иначе на п. 13.

13. Если WS(s) = 0, то реализовалась полиномиальная составляющая алгоритма, расписание s оптимально, конец алгоритма, иначе переходим к п. 14.

Этап IV. Построение расписания s Î Y(sP), для которого WS(s) < WS(s0).

14. Полагаем r = f (s) + 1.

15. Если для прибора r возможна перестановка 1P-0P-R, выполняем ее. Получаем расписание s¢, переходим к п. 17. В противном случае выполняем следующий пункт.

16. Если для прибора r возможна перестановка 1P-1P-R, выполняем ее. Получаем расписание s¢, переходим к п. 17. Иначе переходим к следующему пункту.

17. Полагаем r = r + 1. Если r £ m, переходим к п. 15, иначе к п. 18.

18. Если WS(s) = 0, то реализовалась полиномиальная составляющая алгоритма, расписание s оптимально, конец алгоритма. Иначе переходим к п. 19.

Этап V. Построение расписания s Î YPS, для которого W(s) < W(s0).

19. Перераспределяем задания J \ P(s¢) по приборам, не изменяя нумерации приборов. Полагаем s = s¢.

20. Если для прибора h возможна перестановка 1P-1S-W1, выполняем ее, получаем расписание s¢. Переходим к п. 21.

21. Если для прибора h возможна перестановка 1P-1S-W2, выполняем ее, получаем расписание s¢. Переходим к п. 22.

22. Если для прибора h возможна перестановка 1P-1S-W3, выполняем ее, получаем расписание s¢. Переходим к п. 23.

23. Полагаем h = h + 1. Если h £ f, идем на. п. 20. В противном случае определяем значение функционала F(s¢) и верхнюю оценку отклонения полученного решения от оптимального W(s¢), конец алгоритма А1.

Оценим трудоемкость алгоритма А1.

На первом этапе выполняется алгоритм А10, трудоемкость которого определяется функцией О(mn log n).

Вычислительная сложность этапов III, IV, V не превышает вычислительную сложность этапа II.

Рассмотрим этап II. На этом этапе наиболее трудоемкой является перестановка 1P-1P-∆. Проверка возможности выполнения этой перестановки определяется функцией О(n2m).

Следовательно, трудоемкость алгоритма А1 ограничена полиномом О(n2m).

Пример 1 (к алгоритму А1). Обозначим через Fj(s0) запаздывание задания j в расписании s. На трех приборах необходимо выполнить множество заданий J, представленное в табл. 3.1, d = 15.

В табл. 3.2. представлено начальное расписание

∆S(s0) = ∆1(s0) = 1;

RS(s0) = R2(s0) + R3(s0) = 5; W(s0) = 1; F(s0) = 26.

Для n = 1, r = 2, j ¢ = 8, j ² = 6 производим перестановку 1P-1P-∆. В табл. 3.3 представлено расписание s0. Расписание s0 оптимально: F(s0) = 25.

Таблица 3.1 – исходные данные для примера 1

J	1	2	3	4	5	6	7	8	9	10	11	12
lj	2	2	3	3	4	5	6	8	8	9	10	10

Таблица 3.2 – начальное расписание для примера 1

i	j	lj	d	cj(s0)	Fj(s0)	Ri(s0)	∆i(s0)	Qi(s0)
1	8	8	15	8	0	7
	9	8	15	16	1		1
	12	10	15	26	11			2
2	6	5	15	5	0
	7	6	15	11	0	4
	10	9	15	20	5		5
3	1	2	15	2	0
	2	2	15	4	0
	3	3	15	7	0
	4	3	15	10	0
	5	4	15	14	0	1
	11	10	15	24	9		9	1

Таблица 3.3 – оптимальное расписание для примера 1