ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2017 г.)
2-летний импакт-фактор РИНЦ: 0,500
2-летний импакт-фактор РИНЦ без самоцитирования: 0,405
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,817
5-летний импакт-фактор РИНЦ: 0,319
5-летний импакт-фактор РИНЦ без самоцитирования: 0,264
Суммарное число цитирований журнала в РИНЦ: 6012
Пятилетний индекс Херфиндаля по цитирующим журналам: 404
Индекс Херфиндаля по организациям авторов: 338
Десятилетний индекс Хирша: 17
Место в общем рейтинге SCIENCE INDEX за 2017 год: 527
Место в рейтинге SCIENCE INDEX за 2017 год по тематике "Автоматика. Вычислительная техника": 16

Больше данных по публикационной активности нашего журнале за 2008-2017 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
16 Декабря 2018

Об автоматическом выборе метода оптимизации прямоугольного раскроя

Automatic choice of the optimization method for rectangular cutting
Статья опубликована в выпуске журнала № 4 за 2009 год.[ 16.12.2009 ]
Аннотация:В статье рассматриваются задачи прямоугольного раскроя для условий единичного производства. Предложена классификация задач с целью исследования эффективности существующих методов раскроя для задач разных классов. Проведено тестирование 5 оптимизационных методов прямоугольного раскроя. На основании полученных результатов определена схема автоматического выбора оптимизационного метода в зависимости от принадлежности задачи к определенному классу.
Abstract:In article the rectangular cutting problem is considered. Classification of the rectangular cutting tasks is offered. This typology intends on research objective of efficiency of the existing cutting methods for tasks of a certain class. The testing of 5 the optimising cutting methods is done. On the basis of the testing results the scheme of an automatic choice of the optimising algorithm depending on the offered tasks typology is described.
Авторы: Петунин А.А. (AAPetunin@gmail.ru) - Уральский государственный технический университет – УПИ им. первого Президента России Б.Н. Ельцина, г. Екатеринбург, ,
Ключевые слова: автоматический выбор, классификация задач, метод оптимизации, прямоугольный раскрой
Keywords: automatic choice, classification of tasks, optimising method, rectangular cutting
Всего комментариев: 1
Количество просмотров: 7567
Версия для печати
Выпуск в формате PDF (4.85Мб)

Размер шрифта:       Шрифт:

Среди задач оптимизации раскроя листовых материалов наиболее исследованными являются задачи прямоугольного раскроя. По существующей в настоящее время типологии они относятся к классу задач 2DBPP (Two-Dimensional Bin Packing Problem) [1], для которых неизвестны алгоритмы решения полиномиальной сложности (NP-трудные задачи). Задачу прямоугольного раскроя в общем виде можно сформулировать следующим образом.

Пусть A1, A2, …, An – двухмерные геометрические объекты (точечные множества), ограниченные прямоугольными контурами и заданные своими размерами li (длина) и hi (высота), i=1, …,n. Данные объекты являются геометрическими моделями заготовок, которые необходимо получить из листового материала. Пусть также заданы B1, B2, …, Bm  – области размещения объектов – прямоугольные листы (в общем случае различные) c размерами Wj и Dj, j=1,…,m. Местоположение каждой заготовки Ai  в области размещения определяется тремя параметрами, где xi, yi  – абсцисса и ордината фиксированной точки (полюса) в некоторой системе координат; pi – параметр, задающий признак поворота объекта на плоскости. В качестве полюса объекта обычно задается какая-либо угловая точка прямоугольника. Предполагается также, что среди всех вариантов раскроя рассматриваются только такие, при которых стороны прямоугольников параллельны сторонам прямоугольной области размещения (ортогональная упаковка). В этом случае параметр pi может принимать два значения: 0 – прямоугольник имеет исходную ориентацию, 1 – прямоугольник повернут на 90°. Задачи с анизотропным материалом предполагают фиксированную ориентацию объектов.

Таким образом, необходимо определить 3n параметров размещения заготовок, при которых некая целевая функция F=F(x1, y1, p1, x2, y2, p2, …, xn, yn, pn) достигает своего экстремума и выполняются условия взаимного непересечения объектов, условия размещения объектов внутри одной из областей размещения В1, В2, ..., Вm, а также ряд дополнительных условий, определяемых свойствами раскраиваемого материала и особенностями технологического оборудования, используемого для раскроя. Примером технологических условий может служить требование гильотинности раскроя, которое разрешает только сквозные резы (от одного края прямоугольного листа до другого). Отметим, что алгоритмы гильотинного раскроя пригодны для решения задач негильотинного раскроя (задачи упаковки), но не наоборот. Будем считать, что раскраиваемый материал Вj используется в соответствии с заданной последовательностью. На практике в качестве целевой функции F чаще всего используют функцию, значение которой равно так называемому коэффициенту раскроя  , где P – суммарная площадь занятой части областей размещения (использованного материала). Если для раскроя использован один прямоугольный лист, P=W1´L, где L – длина занятой части листа. Если для раскроя использовано r листов, 1<, где L – длина занятой части последнего листа, использованного для раскроя. Рассматриваемая в литературе постановка задачи, в которой необходимо просто минимизировать число используемых для раскроя прямоугольных листов [1], в условиях единичного производства уравнивает заведомо разные по качеству варианты раскроя, поэтому на практике целесообразно ее применение с описанной выше целевой функцией.

При решении задач прямоугольного раскроя используются в основном приближенные методы, описанные, например, в [2]. Среди них преобладают эвристики и метаэвристики. Алгоритмы, гарантирующие получение глобального и локальных экстремумов (точные методы), из-за NP-труд­ности задачи применимы в основном к задачам небольшой размерности n. Первый конструктивный алгоритм поиска глобального экстремума был описан в [3]. Эффективность методов автоматического проектирования прямоугольного раскроя существенно зависит от условий задачи: ассортимента заготовок, их количественных характеристик, размеров материала и пр., причем характер этой зависимости остается крайне малоисследованным. Это приводит к тому, что при решении практических задач пользователь системы прямоугольного раскроя вынужден экспериментировать с имеющимся у него программным продуктом, содержащим несколько различных вычислительных алгоритмов, с целью выбора наилучшего, что приводит к дополнительным временным затратам и, в конечном итоге, к получению неоптимальных вариантов раскроя. Вместе с тем представляется целесообразным в составе программного обеспечения для расчетов прямоугольного раскроя иметь модуль, определяющий для конкретной задачи наиболее перспективный метод решения на основе предварительного анализа задачи.

Предлагаемый подход можно реализовать следующим образом.

1. Вводим некоторую классификацию задач прямоугольного раскроя листового материала, то есть разбиение множества заданий на группы (классы) по определенным признакам.

2. Проводим тестирование имеющихся в распоряжении разработчика методов раскроя с целью выявления наиболее эффективного для каждого класса заданий.

3. В соответствии с результатами тестирования определяем схему автоматического выбора метода. Выбор метода оптимизации для конкретной задачи может определяться исходя из того, какой метод показал наилучшее среднее значение коэффициента раскроя по результатам тестирования для задач этого класса. Другой способ выбора оптимизационного метода для конкретного класса определяется числом тестов, для которых выбираемый метод дает максимальное значение коэффициента раскроя среди всех тестируемых методов.

4. Разрабатываем и включаем в состав программного обеспечения прямоугольного раскроя процедуру автоматического выбора метода.

5. При решении конкретной задачи раскроя проводим предварительный анализ задания на предмет его принадлежности к какой-либо группе и выбираем метод решения в соответствии с разработанной процедурой автоматического выбора.

Целесообразна реализация схемы автоматического выбора метода с функцией самообучения (то есть с возможностью продолжения тестирования всех методов и изменением алгоритма выбора на основании результатов тестирования) при условии наличия достаточного временного ресурса у пользователя. Сформулируем два основных утверждения, касающихся процедуры самообучения:

·     постоянное изменение схемы автоматического выбора в процессе самообучения свидетельствует о неточной классификации задач раскроя; в этом случае критерии классификации должны быть пересмотрены;

·     если при решении практических задач в режиме самообучения изменение схемы наблюдается только на начальном этапе эксплуатации программного продукта, значит, критерии были выбраны правильно, а использовались неадекватные тесты.

Существующие методы прямоугольного раскроя, как правило, содержат несколько числовых параметров, определяющих конкретный вычислительный алгоритм. Например, одна из реализаций эвристического метода эмуляции отжига [2] содержит 14 параметров, влияющих на алгоритм расчета. Это означает, что при проведении тес- тирования разработчик должен определить несколько наборов параметров для каждого метода и рассматривать каждый набор как отдельный метод. Важно также обеспечить равноправность методов по времени использования, предусмотрев при программной реализации каждого метода управляющий параметр, ограничивающий время расчета.

Для реализации сформулированного подхода все тестируемые задания для прямоугольного раскроя были разбиты на четыре класса по двум признакам: серийность производства и преобладание крупных заготовок над мелкими. Поясним эти понятия.

Существующая в настоящее время типология производства по степени его серийности подразумевает три типа производства: единичное, мелкосерийное, крупносерийное (массовое). В качестве формального разделения заданий по признаку серийности используем следующее правило: если число прямоугольников одинакового размера для каждого элемента списка прямоугольников в задании не превосходит шести, то задание будем относить к классу единичных. Остальные задания будем считать серийными. Отметим, что данное разделение заданий сделано для проведения тестирования и не может служить определением понятия серийности производства.

По степени преобладания крупных заготовок все задания раскроя листового материала также разобьем на две группы. Задание считается состоящим из крупных заготовок, если их число составляет не менее 60 % от всех заготовок в задании. Крупной будем называть заготовку, один из габаритов которой составляет более половины ширины листа.

Для тестирования в качестве областей размещения использовались стандартные прямоугольные листы с размерами W=1500 мм, D=4000 мм. Диапазон размеров прямоугольников – от 200 до 1200 мм. Максимальное число одинаковых прямоугольников в серийном задании – 36. Числовые параметры методов фиксированные, время расчета для каждого теста – до 2 сек. Допускался поворот прямоугольников на 90°. Требование гильотинного раскроя не задавалось.

В качестве тестируемых методов были выбраны пять методов прямоугольного раскроя, входящих в состав систем CETAMI-CUT [4] и NCL [5]: рекурсивный метод (RCAPlus), метод эмуляции отжига (SA), метод поиска с запретами (TS), метод выбора корзин (VBSPlus), гибридный детерминированный метод KAPRAL (NCL-K). В таблице показаны результаты тестирования для 400 тестов (по 100 для каждого класса заданий).

Результаты тестирования методов прямоугольного раскроя

Метод оптимизации

Среднее значение коэффициента раскроя (в %) для каждого класса задания

единичное

cерийное

заготовки

мелкие

крупные

мелкие

крупные

RCAplus

89,51

89,57

92,75

88,22

SA

85,61

85,61

89,00

88,43

TS

85,48

85,48

88,85

87,98

VBSPlus

89,19

89,19

91,03

89,01

NCL-K

92,41

90,18

90,44

88,17

В таблице выделены лучшие результаты для каждого класса заданий, которые и определяют схему автоматического выбора метода расчета раскроя. Таким образом, при решении задачи прямоугольного раскроя в автоматическом режиме выбирается наиболее эффективный метод оптимизации, что сокращает время проектирования ра-

ционального варианта раскроя и повышает коэффициент раскроя. Можно сделать вывод, что при разработке универсальных систем автоматизации расчетов раскроя материала, ориентированных на решение широкого круга задач раскроя, описанный подход, основанный на автоматическом выборе метода оптимизации с использованием сравнительного анализа методов, является наиболее целесообразным способом интеграции существующих вычислительных алгоритмов. Попытки создать универсальный алгоритм прямоугольного раскроя, одинаково эффективный для всех классов задач, автор считает малоперспективными.

Литература

1.   Waesher G., Haussner H., Shumann H. An improved typology of cutting and packing problems // European Journal of Operational research. 2007, 183, pp. 1109–1130.

2.   Мухачева Э.А., Валеева А.Ф., Картак В.М., Мухачева А.С. Методы локального поиска оптимума в задачах ортогонального раскроя и упаковки: аналитический обзор и перспективы развития // Информационные технологии. 2004. № 5. C. 2–18.

3.   Липовецкий А.И. Свойства прямоугольных укладок: препринт. УрО АН ССР, Ин-т машиновед. Свердловск, 1988.

4.   Мухачева Э.А., Ермаченко А.И., Сиразетдинов Т.М., Жукова Т.Ю. Комплекс алгоритмов и программ расчета гильотинного раскроя // Информационные технологии. 2004. № 8. C. 18–25.

5.   Петунин А.А., Полевов А.В., Куреннов Д.В. Об одном подходе к решению задач раскроя-упаковки // Конструирование и технология изготовления машин: сб. науч. тр. Ч. 2. Вестник УГТУ-УПИ. Екатеринбург: УГТУ–УПИ. № 18 (70). 2005. C. 212–216.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=2398
Версия для печати
Выпуск в формате PDF (4.85Мб)
Статья опубликована в выпуске журнала № 4 за 2009 год. Версия для печати с комментариями

Назад, к списку статей

Comments

автор: Виктор [2011-05-18 23:47:22]
Это что такое? Вот это вот - научная статья? И ее автор - доктор? Цитата: "тестируемые задания для прямоугольного раскроя были разбиты на четыре класса по двум признакам: серийность производства и преобладание крупных заготовок над мелкими" (С) Петунин А.А. Задачи прямоугольного раскроя, во всем их многообразии, автору "удалось" описать 2-мя признаками. "Полнота" эксперимента "обеспечена" 4-мя "классами". И на основании этой "классификации" делаются выводы космического масштаба и "космической же глупости". В частности, он гарантированно потеряет до 10% материала, только потому, что пожалел 1-2 минуты вычислений. Поистине глобальный успех!!! Колоссальный вклад в "отечественную науку"!!! Это возможно только, если "4 класса" - это образование автора. Сохранил эту статью и обязательно распространю ее на англ. языке с подробными комментариями среди C&P community. Люди должны знать, с кем они имеют дело.
Оценка пользователя: 1 баллов