Введение
Глава 1. Основные понятия и формальная постановка задачи 11
1.1. Модель
1.2. Оценка погреишости и времени составления расписания 12
1.3. Задачи большой размерности 14
Глава 2, Характеристика задачи я существующие методы ее решения 15
2.1. Результаты для задач минимизации длины расписания 15
2.2. Характеристик алгоритмов составления расписаний 16
2.3. Анализ существующих точных и приближенных алгоритмов 18
2.4. Анализ существующих параллельных стратегий 29
Глава 3. Алгоритмы составления расписания без прерываний 38
31- Алгоритм «Прщессор с ранним окончанием первым» 38
3.2. Вероятностный алгоритм 39
3.3. Лсевдополиномиальные алгоритмы 42
3.3.1. Различные интерпретации псевдополиномиальных алгоритмов 42
3.3.2. Псевдопопиномиальный алгоритме поиском в ширину 44
3.3.3. Псевдополиномиальный алгоритм с поиском в глубину 46
3.4. Метод агрегирования 41
3.4.1. Формальное описание 48
3.4.2. Задача составления расписания п работ на m идентичных процессорах 50
3.4.3. Вспомогательные алгоритмы 52
3.4.4. Агрегирующие алгоритмы 54
3.5. Анализ возможности совместного использования методики агрегирования с другими алгоритмами 55
Глава 4. Алгоритмы с гарантированной точностью 59
4. L Псевдополиномиальный алгоритм с поиском в глубину 59
4.2. Вероятностный алгоритм 62
4.3. Алгоритм «Процессор с ранним окончанием первым» „ 63
4.4. Алгоритм «Самая длинная работа первой» 65
Глава 5. Результаты для некоторых частных случаев 66
5.1 Длительности работ, заданные арифметической прогрессией 66
5.2. Длительности работ, близкие к арифметической прогрессии 68
53. Фиксированное число процессоров 68
Глава 6. Параллельное выполнение вычислений 70
6.1. Комбинированный псевдополиномиальныи алгоритм 70
6.2. Параллельное построение дерет решения 71
Глава 7. Результаты экспериментов 78
7. /. Экспериментальная система 78
7.2. Таблиг(ы и графики 79
Заключение 95
Список использованных источников
