Введение
1. Задачи раскроя-упаковки: обзор методов решения 8
1.1. Задачи одно и двумерного раскроя-упаковки 10
1.1.1. Простейшая одномерная задача раскроя иупаковки 10
1.1.2. Задача прямоугольной упаковки в полубесконечную полосу 11
1.1.3. Задача прямоугольной упаковки в листы 12
1.1.4. Задача гильотинного раскроя 12
1.2. Обзор методов решения задач одно и двумерного раскроя-упаковки 13
1.2.1. Использование методов математического программирования 13
1.2.2. Применение методов комбинаторной оптимизации 14
1.2.3. Приближенные и эвристические методы 15
1.2.4. Вероятностные методы локального поиска оптимума 22
1.3. Основные задачи исследования 25
1.4. Выводы 25
2. Моделирование прямоугольных упаковок 27
2.1. Математические модели задач упаковки в полосу и на листы 27
2.2. Блочная модель упаковки 29
2.3. Способы кодирования упаковок 33
2.4. Алгоритмы декодеры. Блочный декодер 37
2.5. Свойство декодеров «реставрация» 43
2.6. Выводы 48
3. Генетические методы решения задачи упаковки 49
3.1. Общая характеристика генетических методов 49
3.2. Генетический блочный алгоритм 51
3.3. Оценка эффективности алгоритмов. Нижние границы 55
3.4. Выводы 58
4. Задача гильотинного раскроя 59
4.1. Математическая модель задачи раскроя полосы 59
4.2. Использование мультиметодной технологии. Гильотинный генетический алгоритм 60
4.3. Метод дискриминации простых эвристик 66
4.4. Выводы 67
5. Вычислительный эксперимент 68
5.1. Программная реализация алгоритмов 68
5.2. Исследование эффективности способов кодирования упаковки и алгоритмов декодеров при использовании генетических алгоритмов 70
5.3. Исследование декодеров. Проверка на наличие свойства «реставрации» 72
5.4. Исследование эффективности генетического блочного алгоритма. Сравнительный эксперимент с метаэвристическими алгоритмами 73
5.5. Исследование эффективности генетического гильотинного алгоритма с применением дискриминации эвристик 74
5.6. Выводы 77
Заключение 78
Список литературы 80
