Введение
1 Асимптотически точные алгоритмы для задач упаковки 10
1.1 Задача упаковки в контейнеры 10
1.1.1 Б-регулярные функции 10
1.1.2 Класс задач К\ 14
1.1.3 Условия асимптотической точности алгоритма 17
1.2 Задача упаковки в полосу 23
1.2.1 Класс задач К?п 24
1.2.2 Условия асимптотической точности алгоритма Ач . 25
1.2.3 Учет частичного порядка 32
1.2.4 Задача календарного планирования и упаковка в полосу 36
2 Метод ветвей и границ для задачи упаковки в контейнеры 40
2.1 Представление допустимых решений 41
2.1.1 Представление решений задач упаковки перестановками 42
2.1.2 Регулярные перестановки 45
2.1.3 Доминируемые решения и максимальные упаковки 47
2.2 Сравнение нижних оценок 48
2.2.1 Тривиальная оценка Ь\ 49
2.2.2 Оценка L2 49
2.2.3 Класс оценок ifl 50
2.2.4 Процедура лифтинга и класс оценок L . 53
2.2.5 Результаты вычислительных экспериментов 54
3 Задача календарного планирования со складируемыми ресурсами 56
3.1 Задача календарного планирования 56
3.2 Математическая модель 60
3.3 Некоторые сведения из теории сетевого планирования и T-гіоздние расписания 64
3.4 Задача PSa и формулировка основного результата 67
3.5 Обоснование алгоритма решения задачи PSa на основе Т-поздних расписаний 69
3.6 Алгоритм проверки допустимости Т-позднего расписания в задаче PSa 77
3.7 Завершение доказательства основной теоремы 87
3.8 Полиномиально разрешимый случай задачи MPS* 89
Заключение 92
Список публикаций автора по теме диссертации 94
Список литературы
