Введение
1. Модели и методы решения задач упаковки S
1.1. Задача одномерного раскроя 12
1.2. Задача прямоугольной упаковки в полубесконечную полосу 13
1.3. Задача прямоугольной упаковки в листы 15
1.4. Задача гильотинного раскроя 15
1.5. Обзор методов решения задач одно и двухмерного раскроя-упаковки 16
1.5.1. Использование методов математического программирования 18
1.5.2. Применение методов комбинаторной оптимизации 19
1.5.3. Приближенные и эвристические методы 20
1.5.4. Вероятностные методы локального поиска оптимума 26
1.6. Выводы 32
2. Способы кодирования упаковок 33
2.1. Прямой способ кодирования 34
2.2. Кодирование приоритетным списком 34
2.3. Схема парных последовательностей 35
2.4. Блочная технология кодирования-декодирования упаковок 36
2.4.1. Блок структуры упаковок и их свойства 36
2.4.2. Преимущества блочной технологии кодирования упаковок. 41
2.4.3. Алгоритмы построения упаковки - декодеры. Декодер замещения Sub (NF), следующий подходящий 42
2.4.4. Декодер замещения Sub (FF), первый подходящий 45
2.4.5. Декодер жадного замещения Greedy Sub 49
2.4.6. Декодер «пара списков» Dual Local Search (DLS) 54
2.5. Выводы 57
3. Эволюционные методы решения задач упаковки 58
3.1. Наивный эволюционный метод {Naive Search, NS) 58
3.2. Эволюционный алгоритм (1+1) 58
3.3. Метод последовательного уточнения оценок (Sequentative Value Correction, SVC) 60
3.4. Генетические методы решения задачи упаковки. Общая характеристика генетических методов 64
3.5. Схема «жадного» генетического алгоритма 67
3.6. Гибридный генетический алгоритм на базе SVC и Greedy Sub 68
3.7. Модификация методов для решения задачи упаковки на прямоугольные листы 69
3.8. Оценка эффективности алгоритмов. Нижние границы 70
3.8. Выводы 73
4. Вычислительный эксперимент 74
4.1. Программная реализация алгоритмов 74
4.2. Решение задач размещения на полосу на примерах Bortfeld 79
4.3. Исследование эффективности способов кодирования упаковки и алгоритмов декодеров при использовании генетических алгоритмов 81
4.4. Исследование эффективности генетического гибридного алгоритма Genetic Greedy Sub. Сравнительный эксперимент с метаэвристическими алгоритмами 83
4.5. Решение задач размещения на листы на примерах S.P Fekete и J. Schepers 84
4.6. Выводы 88
Заключение 89
Список литературы
