Введение
1 Графический метод точного решения 9
1.1 Сведения о методах решения задач комбинаторной оптимизации 10
1.2 Описание графического метода точного решения 12
1.3 Графический алгоритм решения задачи 1 (no-idle) \ max Tj 16
1.4 Графический алгоритм решения задачи l\dj = d\ WjTj 24
2 Графический метод приближенного решения 34
2.1 Описание модификации графического метода для поиска приближенного решения 35
2.2 Полная полиномиальная аппроксимацонная схема для задачи l\dj = d\ J WjTj 36
2.3 Дополнительные сведения о приближенном решении задач 40
3 Алгоритмы решения задач теории расписаний
3 3.1 Классические одноприборные задачи теории расписаний 45
3.2 Одноприборные задачи с обратными критериями оптимизации 49
3.3 Одноприборные задачи с одним невозобновимым ресурсом 65
3.4 Задача одноколейной железной дороги с двумя станциями 74
3.5 Графические алгоритмы решения одноприборных задач 92
3.6 Сравнение графических алгоритмов и классических алгоритмов динамического программирования 99
3.7 Результаты численных экспериментов 101
Графические алгоритмы решения задач типа Ранец 103
4.1 Графические алгоритмы решения задачи об инвестициях 103
4.2 Графические алгоритмы решения задачи о размере партии продукции 117
О сложности решения некоторых задач комбинаторной оптимизации 120
5.1 Задача минимизации времени выполнения работ проекта с учетом ограничения на ресурсы 120
5.2 Задача балансировки производственной линии 147
5.3 Задача о двух параллельных не взаимозаменяемых приборах 154
5.4 Алгоритм решения RCPSP в программном продукте 1С: Управление строительной организацией 162
5.5 Программные продукты для автоматизированного составле ния расписаний в учебных заведениях 163
Заключение 167
Список использованных источников 1
