Введение
1. Основные задачи двумерного раскроя-упаковки и методы их решения .! 1
1.1. Задачи раскроя и упаковки и их классификация 11
1.2. Методы математического программирования 15
1.3. Точные методы комбинаторной оптимизации 16
1.4. Приближенные и эвристические методы 18
1.5. Вероятностные методы локального поиска оптимума 20
] .5.1. Генетические алгоритмы 21
1.5.2. Поиск с запретами 22
1.53. Имитация отжига 24
1.5.4. Муравьиная колония 24
1.6. Использование декодеров 25
1.7. Численные эксперименты 28
1.8. Выводы 29
2, Математические модели задач двумерного прямоугольного раскроя. Процедуры кодирования и декодирования 31
2.1. Исходная информация задач двумерного прямоугольного раскроя 31
2.2. Модель прямоугольной упаковки и условия допустимости 32
2.3. Постановка задач прямоугольного раскроя и упаковки 35
2.4. Процедуры декодирования в решении задач двумерного прямоугольного раскроя и упаковки 37
2.4.1. Рекурсивный декодер 38
2.4.2. Декодер поиска пустых корїин 41
2.4.3. Декодер «Нижний левый» 42
2.4.4. Блочный декодер 44
2.5. Декодер последовательного конструирования для прямоугольной упаковки 46
2.6. Выводы по второй главе 51
3. Метод поиска с запретами с переменными окрестностями и вторичными оценками для решения задач двумерного прямоугольного раскроя 52
3.1. Методика поиска с запретами для решения задач дискретной оптимизации 52
3.2. Алгоритм поиска с запретами с переменными окрестностями и вторичными оценками для решения задач двумерного прямоугольного раскроя 57
3.3. Реализация метода поиска с запретами Й составе автоматизированной системы проектирования карг двумерного прямоугольного раскроя CETAMI-CUT 66
3.4. Выводы по третьей тлаве 71
4. Численные эксперименты 72
4.1. Выбор числа шагов до смены вторичной оценки , 72
4.2. Эксперимент на случайно сгенерированных примерах 73
4.2.1. Примеры с количеством предметов 40 74
4.2.2. Примеры с количеством предметов 400 77
4.3. Сравнение декодера последовательного конструирования и блочного декодера 78
4.4. Эксперимент на безотходных, примерах Евы Хоппер 80
4.5. Выводы по четвертой главе 82
Заключение 83
Литература
