Одноетапні задачі теорії розкладів у багаторівневій системі планування (стр. 4 )

Для того, щоб показати, які результати дають алгоритми А1 та А2 на задачах різної розмірності для комбінацій I, II, III параметрів T і R, зведені результати наведені в табл. 4. У колонці "Опт" показано час оптимального розв’язання задачі, отриманого алгоритмом гілок і границь.

Таблиця 4

Середній час розв’язання порівняно з точним алгоритмом (мс)

Параметри задачі		Параметри задачі
		Комбінація параметрів	Опт	А1	А2			Комбінація параметрів	Опт	А1	А2
2	3	I	9.2	2.2	4.7	3	3	I	158	24.3	51.2
2	3	II	9.7	2.4	5	3	3	II	149	18.9	39.9
2	3	III	9.1	2.1	4.3	3	3	III	121	18.5	39.1
2	4	I	46	3.2	6.7	3	4	I	3598	97.7	206.2
2	4	II	47	3.4	7.2	3	4	II	1584	45.8	96.7
2	4	III	43	2.4	5.1	3	4	III	3178	31.4	66.2
2	5	I	336	9.5	20.0	3	5	I	70683	198.9	420.0
2	5	II	354	7.4	15.6	3	5	II	46954	167.1	352.8
2	5	III	224	8.6	18.2	3	5	III	44783	72.9	154

Дані з табл. 4 показують, що алгоритми А1 і А2 дуже ефективні. У середньому на розв’язання треба було менше, ніж 0.42 секунди для будь-якого набору з 20 задач. Середня кількість часу, необхідного для оптимального розв’язання алгоритмом гілок і границь, становила менше 70.6 секунди. Однак час, необхідний для оптимального розв’язання, швидко збільшувався при зростанні розмірності. Це вказує на те, що використовувати алгоритм гілок і границь для розв’язання задач більших розмірностей недоцільно.

Порівняння результатів табл. 4 також показує, що у всіх випадках алгоритм А1 вимагає меншої кількості часу на розв’язання, ніж алгоритм А2. Це засвідчує, що розв’язання задачі алгоритмом А1 виконується відносно легко. Однак, з погляду обчислювальної складності, ця задача усе ще є NP-складною в звичайному сенсі.

Для того, щоб продемонструвати, які результати дають алгоритми А3 і А4 на задачах різної розмірності для комбінацій I, II, III параметрів T і R, отримані дані зведено в табл. 5. У колонці "Опт" показано час оптимального розв’язання задачі, отриманого алгоритмом гілок і границь.

Таблиця 5

Середній час розв’язання порівняно з точним алгоритмом (с)

Параметри задачі		Параметри задачі
n	Комбінація параметрів	Опт	А3	А4	n	Комбінація параметрів	Опт	А3	А4
10	I	3.2	0.077	1.461	20	I	40.5	0.156	4.811
10	II	3.3	0.063	0.291	20	II	38.2	0.128	0.862
10	III	3.1	0.026	1.092	20	III	31.0	0.053	3.118
15	I	15.9	0.116	2.702	25	I	115.9	0.195	5.665
15	II	16.2	0.095	0.526	25	II	119.1	0.160	1.154
15	III	14.8	0.039	2.018	25	III	77.2	0.066	4.370

Результати табл. 5 показують, що алгоритми А3 та А4 були дуже ефективні. У середньому для будь-якого набору з 20 задач на розв’язання алгоритмом А3 треба було менше, ніж 0.2 секунди; А4 – менше, ніж 5.7 секунди. Середня кількість часу, необхідного для оптимального розв’язання алгоритмом гілок і границь, становила не більше 2 хвилин. Однак час, необхідний для оптимального розв’язання, швидко збільшувався при зростанні розмірності. Це вказує на те, що використовувати алгоритм гілок і границь для розв’язання задач більших розмірностей недоцільно.