Введение
1 Введение 4
1.1 Задачи раскроя, упаковки и теории расписаний 4
1.1.1 Классификация задач раскроя 6
1.1.2 Классификация задач упаковки 7.
1.1.3 Задачи ортогональной упаковки 8
1.1.4 Задачи планирования при ограниченных ресурсах . 10
1.2 Размещения и графы 11
1.2.1 Граф размещения на плоскости 11
1.2.2 Граф многомерного размещения 13
1.3 Модели вычислений 14
1.4 Структура работы 17
2 Разделение размещения прямоугольников посредством угловых разрезов 19
2.1 Размещения, содержащие вырожденные прямоугольники . 21
2.2 Существование разделяющей последовательности разрезов 24
2.3 Нижняя оценка сложности 25
2.4 Построение разделяющей последовательности разрезов . 26
2.5 Обобщение для гофров 27
2.6 Трехмерный случай 29
3 Построение графа размещения 32
3.1 Плоский случай 32
3.1.1 Алгоритм построения графа размещения 32
3.1.2 Доказательство оптимальности 34
3.1.3 Обобщение для гофров 36
3.2 Случай с?-мерного пространства 37
3.2.1 Задача регионального поиска 37
3.2.2 Два метода построения графа размещения 38
4 Наклонная нумерация для размещений прямоугольников 41
4.1 Существование 42
4.2 Построение 44
4.2.1 Нижняя оценка сложности 45
4.2.2 Оптимальный алгоритм 45
4.2.3 Обоснование корректности 48
4.2.4 Обработка вырожденных случаев 51
4.3 Минимальный и максимальный номер прямоугольника . 52
4.4 Взаимнооднозначные соответствия 54
4.5 Обобщение для гофров 57
4.6 Обобіцение для пространств высших размерностей 58
4.6.1 Нумерация без повторений 58
4.6.2 Нумерация с повторениями 60
4.7 Задача об упаковке полосы 63
5 Заключение 66
