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

i	j	lj	d	cj(s0)
5	65	42	370	219
5	70	46	370	265
5	75	50	370	315
5	80	52	370	367
5	85	54	370	421
5	90	56	370	477
5	95	58	370	535
5	100	61	370	596
5	105	65	370	661
5	110	71	370	732
5	115	72	370	804
5	120	76	370	880
5	125	80	370	960
5	130	84	370	1044
5	135	89	370	1133
5	140	95	370	1228
5	145	96	370	1324
5	150	100	370	1424

Для исследования алгоритмов использовалась система моделирования, написанная на языке C# в среде разработки Microsoft Visual Studio 2010. Расписания генерировались случайным образом с равномерным распределением параметров, длительности заданий выбирались из интервала от 1 до 200, директивный срок рассчитывался как 0,7P/m, где P – суммарная длительность всех заданий. Проводилось 2000 испытаний для каждой пары (n, m).

Для задачи МСЗП были получены следующие результаты. Исследования, приведенные ниже, проводились на процессоре Pentium Core 2 Duo с тактовой частотой 3,0 ГГц при объеме оперативной памяти 2 Гбайт.

В табл. 3.7 и 3.8 показано среднее (за 100 испытаний) время решения задачи МСЗП полиномиальной вычислительной схемами А1 и А2 (приведенными в параграфе 3.3) от количества заданий n и количества приборов m.

Таблица 3.7 – Среднее время решения задачи МСЗП полиномиальной вычислительной схемой А1 в зависимости от размерности задачи, мс

m n	5	10	15	20	30
3000	1,87	3,15	3,29	3,12	3,6
5000	25,79	21,84	11,41	11,41	21,25
10000	89,04	123,38	119,19	89,85	67,54
20000	491,07	572,23	500,19	480,65	313,55
40000	1855,95	2028,41	2361,71	2229,28	1349,66

Таблица 3.8 – Среднее время решения задачи МСЗП полиномиальной вычислительной схемой А2 в зависимости от размерности задачи, мс

m n	5	10	15	20	30
3000	2,21	2,35	2,33	2,49	2,18
5000	3,6	3,57	3,66	3,41	3,74
10000	7,04	7,82	7,05	7,81	7,97
20000	15,32	17	15,61	16,28	16,58
40000	32,8	34,68	33,59	34,7	34,37

В табл. 3.9 и 3.10 приведена частота получения оптимального решения в процентах за 2000 испытаний для алгоритмов А1 и А2 в зависимости от размерности задачи.