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

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

­

Алгоритм А2 построен на основе исследований эффективности алгоритма А1. Определены наиболее часто выполняющиеся перестановки при реализации полиномиальной составляющей алгоритма. Разработан более эффективный алгоритм построения начального расписания. Это позволило существенно уменьшить трудоемкость алгоритма.

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

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

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

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

4. Назначаем задание j на прибор i с минимальным временем освобождения Ti.

5. Полагаем Ti = Ti + lj.

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

Алгоритм A2

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

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

2. Определяем WS(s0). Если WS(s0) = 0, то расписание s0 оптимально, конец алгоритма. В противном случае переходим к пункту 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¢. Переходим к п. 6, в случае отсутствия перестановки переходим к п. 7.

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

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

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

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

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

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

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

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

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

Трудоемкость алгоритма А2 определяется полиномом О(mn log n).

Пример 2 (к алгоритму А2). На пяти приборах необходимо выполнить множество заданий J. Исходные данные представлены в табл. 3.4 (d = 370); начальное расписание – в таблице 3.5.

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

j	1	2	3	4	5	6	7	8	9	10
lj	1	1	1	1	2	3	4	4	4	5
j	11	12	13	14	15	16	17	18	19	20
lj	5	5	5	6	6	7	7	8	8	8
j	21	22	23	24	25	26	27	28	29	30
lj	8	8	8	9	9	10	10	11	11	12
j	31	32	33	34	35	36	37	38	39	40
lj	12	13	13	14	14	14	14	15	16	20
j	41	42	43	44	45	46	47	48	49	50
lj	21	22	22	24	24	25	25	26	27	27
j	51	52	53	54	55	56	57	58	59	60
lj	28	29	29	31	31	32	34	38	38	39
j	61	62	63	64	65	66	67	68	69	70
lj	39	40	40	41	42	42	43	43	46	46
j	71	72	73	74	75	76	77	78	79	80
lj	46	47	48	48	50	51	52	52	52	52
j	81	82	83	84	85	86	87	88	89	90
lj	52	52	53	54	54	55	55	55	55	56
j	91	92	93	94	95	96	97	98	99	100
lj	56	57	57	58	58	58	59	59	60	61
j	101	102	103	104	105	106	107	108	109	110
lj	62	62	63	64	65	67	68	68	71	71
j	111	112	113	114	115	116	117	118	119	120
lj	71	72	72	72	72	73	73	73	74	76
j	121	122	123	124	125	126	127	128	129	130
lj	77	78	78	80	80	81	81	82	84	84
j	131	132	133	134	135	136	137	138	139	140
lj	85	85	86	86	89	89	90	91	93	95
j	141	142	143	144	145	146	147	148	149	150
lj	95	95	96	96	96	97	97	99	100	100

Расписание s0 (таблица 3.5) имеет следующие характеристики. ∆S(s0) = ∆4(s0) + ∆5(s0) = 6 + 17 = 23. RS(s0) = R1(s0) + R2(s0) + R3(s0) = 26 + 16 + 7 = 49. W(s0) = 23. C(s0) = 34341.