Введение
1 Компактное суммирование векторов 19
1.1 Предварительные сведения 19
1.2 Формулировки результатов 23
1.3 Алгоритмы Лі.2, Ai.z 27
1.3.1 Необходимые обозначения 27
1.3.2 Описание алгоритма Л\.2 28
1.3.3 Описание алгоритма Ai.z 29
1.4 Доказательство теоремы 33
1.4.1 Процедура выравнивания 33
1.4.2 Суммирование больших векторов 35
1.4.3 Оценка радиуса суммирования 38
1.4.4 Асимптотическая оптимальность 40
1.4.5 Вспомогательные доказательства 49
1.5 Приложения для стохастических задач теории расписаний 60
1.5.1 Задача Open Shop 60
1.5.2 Задача Flow Shop 62
1.5.3 Задача о сборочной линии 63
1.5.4 Задача Job Shop 64
1.6 Заключительные замечания к главе 1 65
2 Достаточные условия полиномиальной разрешимости за дачи Open Shop 69
2.1 Предварительные сведения 69
2.2 Описание алгоритма Лг.і 70
2.3 Формулировки результатов 73
2.4 Доказательства 76
2.5 Заключительные замечания к главе 2 78
3 Произвольные перестановочные расписания в задачах о сборочной линии и Flow Shop 80
3.1 Предварительные сведения 80
3.2 Формулировки результатов 82
3.3 Доказательства 84
3.4 Заключительные замечания к главе 3 87
Приложение 89
Литература 91
