Введение
Глава 1. Связи - полный граф. Отсутствие ограничений по памяти. Переключения без затрат 16
1.1 Точный алгоритм 16
1.2 Эвристические алгоритмы 25
1.2.1 Эвристика 1 26
1.2.2 Эвристика 2 29
1.3 Сравнительный анализ алгоритмов Эвристика 1 и Эвристика 2 33
Глава 2, Переключения с затратами. Связи - полный граф. Отсутствие ограничений по памяти 41
2.1 Алгоритм Эвристика Ш 47
2.2 Алгоритм Эвристика П2 51
2.3 Сравнительный анализ алгоритмов Эвристика Ш и Эвристика П2 55
2.3.1 Испытания алгоритмов в случае первой модели образования временных затрат па прерывания 57
2.3.2 Испытания алгоритмов в случае второй модели образования временных затрат на прерывания 59
2.3.3 Испытания алгоритмов в случае третьей модели образования временных затрат на прерывания 62
Глава 3. Ограничения по памяти и скорости загрузки. Связи - полный граф. Общий директивный интервал 65
3.1 Однопроцессорный случай 65
3.1.1 Постановка задачи и предварительные соображения 66
3.1.2 Построение оптимального порядка выполнения работ 68
3.1.3 Алгоритм построения однопроцессорного расписания 69
3.2 Многопроцессорный случай 75
3.2.1 Постановка задачи 75
3.2.2 NP-трудность 76
3.2.3 Эвристический алгоритм 80
3.2.4 Анализ предложенного алгоритма 84
Глава 4. Ограничения по памяти. Произвольный граф связей. Переключения с затратами» Время - дискретные такты 98
4 1 Постановка задачи 99
4.2 Построение сети 100
4.3 NP-трудность. 105
4.4 Необходимые и достаточные условия существования допустимого расписания 108
4.5 Алгоритм построения расписания 111
Глава 5. Задача синтеза 112
5.1 Отсутствие ограничений на память процессоров 112
5.1.1 Постановка задачи ИЗ
5.1.2 Построение области допустимых параметров процессоров 113
5.2 Учет ограничений на память процессоров 117
5.2.1 Постановка задачи 117
5.2.2 Построение области допустимых параметров процессоров 118
Заключение 124
Список использованных источников 128
