Введение
1. Задачи теории расписаний и сложность их решения 8
1.1. Формулировки задач 8
1.2. Алгоритмическая сложность решения задач 17
2. Построение циклических расписаний для производственной линии 26
2.1. Слоишость и свойства задач с различными критериями 27
2.2. Задача минимизации времени цикла с ограничением 34
2.3. Алгоритм для задачи минимизации времени цикла с ограничением 37
3. Аппроксимационные схемы решения задач . 53
3.1. Основные определения 53
3.2. Аппроксимационная схема для задачи минимизации времени цикла с ограничением 55
3.3. Аппроксимационная схема для задачи о поставках продукции с одним потребителем 57
4. Задача построения расписания для производственной системы открытого типа 72
4.1. Исследование структуры оптимальных решений 72
4.2. Модель целочисленного программирования и ее свойства 95
Заключение 103
Список использованной литературы 105
