РАЗРАБОТКА МОДЕЛИ ХРАНИЛИЩА ДАННЫХ ДЛЯ ФУНКЦИЙ ГИЛЬОТИННОГО РАЗМЕЩЕНИЯ И ЕЕ ПРИМЕНЕНИЕ ДЛЯ ПРИБЛИЖЕННОГО РЕШЕНИЯ ЗАДАЧИ ПОЛУЧЕНИЯ ГИЛЬОТИННОГО 2D-РАСКРОЯ

Введение 3
Функция гильотинного размещения и ее свойства 5
Разработка реляционного и нереляционного варианта модели хранилища функций гильотинного размещения 8
Модель реляционного хранилища ФГР 10
Агрегатная модель хранилища ФГР 11
Программная реализация 13
Анализ вычислительных экспериментов 14
Эвристический алгоритм получения гильотинного размещения набора деталей на полуполосе на основе применения анализа данных хранилища .. 16
Описание алгоритма 16
Структура данных 18
Программная реализация 19
Анализ вычислительных экспериментов 20
Заключение 21
Список литературы 22
Приложение 1 24

Отсутствует часть приложений
Купить

Задача о размещении прямоугольных объектов на плоскости известна достаточно давно [1] и находит широкое применение в различных сферах деятельности человека.
Существуют различные постановки задачи прямоугольной упаковки - на листе заданного размера или на бесконечной полуполосе заданной ширины, с возможностью поворота прямоугольников и без нее, с условием гильотинного и негильотинного размещения, с условием безотходной упаковки и без этого условия [1].
Прямоугольный раскрой может быть негильотинным (рис. 1) и гильотинным (рис. 2). Гильотинным называется раскрой, когда любая линия разреза параллельна или перпендикулярна краю полосы и проходит от края полосы до края.
В данной работе будет рассматриваться ортогональный прямоугольный гильотинный раскрой.
Практически все варианты задачи прямоугольного раскроя являются NP-трудными [2] и фактически сравнимы с полным перебором перестановок деталей на поверхности исходного материала во всех возможных вариантах размещения. В производстве применение таких трудоемких подходов крайне неэффективно, поскольку для этого необходимо обработать данные, размер которых пропорционален факториалу количества деталей.
Использование точных методов вычислений накладывает сильное ограничение на размерность задачи, поэтому для получения быстрого решения чаще используются эвристические и метаэвристические методы: алгоритмы муравьиной колонии, генетические алгоритмы, нейронные сети.
Были рассмотрены основные метаэвристические методы к решению данных задач:
1. Муравьиный алгоритм. В работе [3] предлагается алгоритм на базе конструктивной метаэвристики «муравьиная колония». В ней описана адаптация алгоритма муравьиной колонии к задаче прямоугольного раскроя.
2. Генетический алгоритм. Данный метод позволяет построить решение через комбинирование исходных параметров и последовательный подбор, путем использования механизмов, похожих на биологическую эволюцию [4].
Также были рассмотрены следующие точные методы:
3. Метод целочисленного программирования, приведенный в статье [5] дает точное решение, однако число вычислений довольно непредсказуемо. Для некоторых наборов прямоугольных деталей можно получить решение быстро, а уже незначительные изменение набора могут привести к достаточно долгим вычислениям, требующим больших вычислительных мощностей.
4. Функция гильотинного размещения (ФГР). В статье [6] представлен метод нахождения точного решения, который дает приемлемую оценку:
Мш(D)>2ттгт v|D|>3,
где количество операций сложения таблиц ФГР,
D — набор деталей,
|D| — количество деталей в наборе D,
klt... кт — число деталей каждого вида,
т —ко л ич е с т в о видов деталей в наборе.
Эвристические и метаэвристичекие методы решения задач размещения прямоугольных объектов на плоскости не утратят своей актуальности ввиду того, что позволяют решать задачи с большим количеством объектов нежели точные методы решения. Также есть необходимость в разработке новых методов решения.
Кроме того, важным является необходимость совершенствования имеющихся методов точного решения для задач с большим количеством размещаемых прямоугольных объектов.
Таким образом, целью данной работы является разработка хранилища данных для функций гильотинного размещения, а также разработка алгоритма его использования для приближенного решения задачи гильотинного 2Э-раскроя. Выбор модели должен быть обусловлен применением вычислительно простых процедур идентификации, поиска и пополнения хранилища. Для формулировки приближенного алгоритма получения гильотинного раскроя хранилище должно предоставлять наборы данных для проведения процедуры интеллектуального анализа на основе понятий похожести наборов деталей.

Купить