А. Ф. Валеева Применение конструктивных эвристик в задачах раскроя-упаковки*

      Рассматриваются задачи одномерной, прямоугольной, параллелепипедной упаковки, являющиеся NP-трудными проблемами. Для их решения применяются конструктивные эвристики, основанные на методах решения задачи "0≈ 1 рюкзак" и метаэвристиках муравьиной колонии, поиска с запретами. Приведены результаты численного эксперимента, подтверждающие высокую эффективность предложенных алгоритмов.

Applying of the Constructive Heuristic Methods for Cutting-Packing Problems
      The paper is devoted to solving the linear, rectangular and parallelepiped cutting-packing problems. It is known, these problems referred to the class of NP-hard problems. The constructive heuristic methods based on 0≈ 1 Knapsack Problem and Ant Colony Optimization are developed for solving these problems. The numerical comparison efficiency of algorithms is conducted.

Введение
1. Постановки и математические модели основных задач С&Р
     1.1. Постановки и математические модели задач одномерной упаковки
     1.2. Постановки и математические модели негильотинных задач прямоугольной упаковки
     1.3. Задача негильотинной прямоугольной упаковки в прямоугольные листы (2DBP)
     1.4. Постановка и математическая модель задачи гильотинного прямоугольного раскро
     1.5. Постановка и математическая модель задачи параллелепипедной упаковки (3D Bin Packing, 3DBP)
2. Конструктивные эвристики, базирующиеся на методе динамического перебора, для решения задач рас кроя-упаковки
3. Применение метаэвристик для решения задач двухмерной упаковки
     3.1. Алгоритм "имитация отжига"
     3.2. Метод поиска с запретами
     3.3. Метаэвристика АСО
4. Численные эксперименты
Заключение