Применение систем автоматизированного проектирования карт раскроя в судостроении

УДК 004.023

ПРИМЕНЕНИЕ СИСТЕМ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ КАРТ

РАСКРОЯ В СУДОСТРОЕНИИ

Ю.И. Валиахметова, С.В. Телицкий

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

Ключевые слова: раскрой, оптимизация, послойные алгоритмы

Введение. Традиционно судостроительная отрасль обеспечивает интересы обороны и безопасности, морского и речного транспорта и других сфер экономики. Ее доля в общем объеме производства оборонно-промышленного комплекса (ОПК) более 1/4, в экспорте военно-технической продукции - до 20-30%.

Судостроение является материалоемкой отраслью промышленности. Важным фактором снижения материалоемкости и рационального использования материальных ресурсов является совершенствование системы технологической подготовки раскроя промышленных материалов. Большие отходы конструктивных материалов (до 30% в материалоемких производствах) требуют коренной перестройки технологии проектирования процесса раскроя, его автоматизации. Создание и широкое внедрение САПР технологической подготовки раскроя, представляющих собой новые ресурсосберегающие технологии, обеспечивает снижение расхода материала, трудоемкости технологической подготовки и сроков проектирования.

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

Однако здесь наблюдается некая несогласованность между практикой и научной мыслью, которая заключается в том что:

- с одной стороны - в САПР раскроя почти везде отсутствует оптимизационное ядро;

- с другой стороны, многие ученые заняты разработкой точных и приближенных методов расчета раскроя и размещения деталей без учета ка-

Валиахметова Юлия Ильясовна - БГАУ, канд. техн. наук, доцент, e-mail: julikas@inbox.ru

Телицкий Станислав Владиславович - УГАТУ, аспирант, e-mail: stasion@mail.ru

Работа, выполнена при поддержке российского фонда фундаментальных исследований, проект 12-07-00631-а

ких-либо ограничений на производственные факторы.

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

Производственный процесс, связанный с металлом вообще и с раскроем в частности выглядит так.

1. Прием материала на склад от поставщика. Материал двух видов: прямоугольные листы (разного размера) и профиля.

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

2. Раскрой.

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

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

Классификация задачи раскроя, возникающая в процессе производства:

1. Изготовление заключается в сборке изделия из геометрических объектов произвольной формы, которые вырезаются из стандартных листов исходного материала. Для возможности использования прямоугольных методов расчета раскройных планов, что объекты произвольной формы аппроксимируются заготовками прямоугольный формы.

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

3. Особенности производства требуют предусмотреть как возможность строгой ориентации заготовки на листе, так и возможность их разворота.

4. Заготовки прямоугольной формы вырезаются из стандартных листов исходного металла с использованием станков термической резки, на которых выполняются резы произвольной длины, что говорит о прямоугольном нерегулярном раскрое. Исходя из особенностей единичного производства, оптимальным вариантом следует признать полностью автоматический подход к формированию раскройных карт и управляющих программ для станков с ЧПУ, только в этом случае будет достигнута производительность, удовлетворяющая условиям единичного производства.

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

6. В рассматриваемом производстве особенно необходим учет технологических параметров, таких как ширина реза; установка направления первоначального распила листов; раскрой произвольного количества изделий; наличие склада стандартных листов и материалов.

Для данного производства наиболее подходящей является задача прямоугольного нерегулярного раскроя/упаковки листов в условиях единичного и мелкосерийного производства с учетом разворотов заготовок. Данная задача по международной классификации задач раскроя/упаковки относится к задаче 2 Dimensional Bin Packing Problem (2DBPP).

Математическая модель задачи. По сути, в задаче двумерной упаковки/раскроя 2DBPP необходимо расположить элементы известной формы и размеров в прямоугольных областях заданных характеристик (рис. 1). Учитывая специфику предметной области, задача получает ряд дополнительных ограничений, усложняющих её решение [1].

В зада-

1 2

3

4

Рис. 1. Негильотинная упаковка

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

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

Заданы габариты раскраиваемого материала: C - ширина листа, D - длина листа, и размеры получаемых из него заготовок c, dh bi, где c = (ch c2,...,ci,...,cm), Ci - ширина заготовки, d = (dj, d2,...,di,...,dm), di - длина заготовки, b = (bj, b2,...,b,..,bm), bi - количество заготовок типа i,

i = 1, m .Требуется составить наиболее экономичный план раскроя, т.е. минимизировать общее количество раскраиваемых листов.

Каждому раскрою r сопоставим вектор a(r )= («1 (r), a2 (г),..., ai (r),..., am (r)), компоненты

ai(r) которого соответствуют количеству деталей i-го вида, получаемых при реализации раскроя. [1, 2]

Раскрой будем называть реализуемым, если выдержаны размеры и технологические параметры для всех получаемых заготовок. Реализуемый раскрой назовем допустимым в задаче целочисленного раскроя, если для него выполняется условие а(r V 61 = 1 ,2,....m}. Рассматриваемая задача

раскроя сводится к следующей целочисленной модели.

Задача 2DCSP. При заданных исходных данных для рассматриваемой задачи требуется найти совокупность раскроев rj r2, ...,rj, ...,rn, и неотрицательный вектор х = (*1,*2,...,хп) с целочисленными компонентами x, j = 1,...,n, удовлетворяющими

условиям ^ ai (ri ) Xj = bi,i є 1 j=1

и минимизи-

рующими функцию x) = ^

j

j=1

Подход к решению задачи. Разработка автоматизированных методов проектирования рационального раскроя особо остро стоит для единичного производства. Данная задача относится к классу МР-полных, поэтому точные методы для ее решения не применимы. Предлагается решать рассматриваемую задачу в два этапа:

Рис. 2. Условие гильотинности раскроя листового материала

1. Решается задача генерирования гильотинного раскроя. Г енерирование гильотинного раскроя

является частным случаем задачи 2DBPP и относится к задаче 2DCSP (Two-Dimensional Cutting Stock Problem, 2DCSP), является NP-трудной задачей комбинаторной оптимизации и может быть описана следующим образом.

Для любого прямоугольника P с R^ (рис. 2) с размерами (c, d): с Ф ct v d Ф dt, выполнено условие разделения на два прямоугольника P'(c', d') и P”(c”, d''):

(с' = с" = с) л (d '+d" = d) v (c'+c" = с) л (d' = d " = d), если (ci, di) 6 P', то (ci, di) g P", если (ci, di) 6 P", то (ci, di) g P'.

2. На втором этапе снимается условие гильо-тинности и заготовки уплотняются на листах.

Анализ существующих методов решения. Анализ моделей и методов решения задач раскроя 2DCSP [1, 2, 3, 6], а также литературы и современного состояния процесса проектирования карт гильотинного раскроя позволяет выделить основные группы методов решения задач гильотинного раскроя:

1. Методы, основанные на линейном целочисленном программировании и полного перебора с отсечением неперспективных вариантов, которые объединены под общим названием «метода ветвей и границ», и позволяют получать решения задачи только при малых размерностях (до 10 - 20).

2. Простые эвристические алгоритмы. В среде эвристических алгоритмов в основном выделяются: уровневые эвристические алгоритмы и эвристические алгоритмы, включающие в себя послойную стратегию.

За основу уровневых алгоритмов принимается принцип последовательной укладки элементов в прямоугольную область, расположенную в пределах листа, с выравниванием по левому и нижнему краю.[2, 3, 6]

Укладка элементов по стратегии Next Fit Decreasing (NFD) представляет собой последовательное заполнение прямоугольных областей листа. По алгоритму следующий элемент списка укладывается в текущую прямоугольную область. В случае, когда размер элемента больше размера свободной части текущей области, выделяется новая прямоугольная область в свободной части листа и элемент укладывается в нее (рис. 3 а).

По стратегии First Fit Decreasing (FFD) следующий элемент списка укладывается в текущую прямоугольную область. В случае, когда размер элемента больше размера свободной части текущей области, рассматривается следующий элемент. Новая область создается, когда ни один элемент не может быть уложен (рис. 3 b).

По стратегии Best Fit Decreasing (BFD) в прямоугольную область укладывается элемент наиболее подходящего размера. Новая область выделяется, когда ни один элемент не может быть уложен (рис. 3с).

Уровневые алгоритмы позволяют решать задачи с большими размерами относительно разме-

ров листа, но малым количеством деталей одного типоразмера, при изменении этих условий эффективность уровневых алгоритмов резко снижается. Сложность уровневых алгоритмов O(n log n), где n - общее количество элементов.

Послойная технология была предложена M.Adamowich & A.Albano в 70-е годы [5]. За основу послойных алгоритмов принимается принцип размещения элементов группами, составляющими полосы (слои). Алгоритм состоит в последовательном выполнении идентичных шагов, каждый из которых выполняется для выделенного на предыдущем шаге прямоугольника (c';d'). [4]

В модификации послойного алгоритма, предложенной Э.А. Мухачевой и Л.Ф. Розановой [6], на каждой итерации укладки деталей вычисляется

f\ 1

7 4

2 5

1

Рис. 3. Пример работы уровневых алгоритмов: а - стратегия Ь - стратегия FFD; с - стратегия BFD

оценка для каждого типоразмера. На основе вычисленных оценок определяется укладываемый на очередной итерации типоразмер деталей и необходимость поворота деталей на 90°. На рисунке 6 представлен пример карты раскроя, полученный послойным алгоритмом.

1 3 4

1

3

2

Рис. 4. Пример работы послойного алгоритма

Послойные алгоритмы строят «хорошие» планы раскроя и в плане высокого КРА, и в плане высокой технологичности без дальнейшего улучшения. На рис. 4 представлен пример карты раскроя, полученный послойным алгоритмом.

Сложность алгоритма O(n m2 log m), где m -количество типоразмеров деталей, n - общее количество деталей.

3. Метаэвристики: «поиск с запретами»,

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

4 fi 1

7

2 5

1

менение в процессе оперативной подготовки производства [2, 4, 5].

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

Разработка метода решения задачи. Алгоритм состоит в последовательном выполнении идентичных шагов, каждый из которых выполняется для выделенного на предыдущем шаге прямоугольника (с; й). На очередном шаге процесса выполняют ряд основных процедур. На первой процедуре заготовки разбиваются по текущему способу декомпозиции на приоритетные группы. Затем по некоторому правилу вычисляют оценки заготовок и выбирают заготовки с максимальной оценкой у,. Для найденных заготовок фиксируют признак

о, = 1,4 наиболее подходящего из возможных четырех размещений в листе (с; й). На следующей процедуре прямоугольник (с; й) разделяют на пару прямоугольников, полосу (с'; й '), и остаток от нее (с" ; й" ), который подлежит раскрою на последующем шаге. При этом способ выделения полосы определяется в зависимости от признака о,. На четвертой процедуре раскраивается полоса (с"; й "). Для раскроя полосы (с"; й ") применяется любой метод генерирования линейного раскроя. На пятой процедуре проверяют прямоугольник (с" ; й") на предмет его дальнейшего использования. Затем восстанавливается раскрой с максимально занятой площадью.

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

1. Сортировка.

Множество заготовок М разбивается на два непересекающихся подмножества М\ и М2. Имеем несколько критериев разбиения:

1. По длине каждой заготовки:

а) все заготовки принадлежат множеству

Мь

б) Для М\. с, > 0,3*С; для М2: с, < 0,3*С;

в) Для М\. с, > 0,5*С; для М2: с,- < 0,5*С;

г) Для М\. с, > 0,8*С; для М2: с, < 0,8*С;

2. По отношению площади каждой заготовки к площади всех заготовок:

а) Для М\. отношение > 0,3; для М2: отношение < 0,3;

3. По отношению длины каждой заготовки к ее площади:

а) Для М\. отношение > 0,3; для М2: отношение < 0,3;

2. Определение размера и направления отрезаемой полосы.

2.1. Рассчитать для каждой заготовки с номером 1 = 1,...,т:

1 [тш([С/с, ],Ь,),еслий, < й

1 [О в противном случае

^2 [тш([С/й, ],Ь1),еслис1 < й

1 [0 в противном случае

[тш(Р / с, ], Ь ,), еслий, < с

1 [0 в противном случае

4 [тш(Р / Й , ], Ь ,), если с, < с

к = •

[0 в противном случае

2.2. Определить ожидаемые коэффициенты раскроя соответствующей полосы (ширина совпадает с одним из размеров заготовки, а длина - с размером раскраиваемого прямоугольника на заготовки I-го вида):

1 2

1 = кг с, . 2 = к г й I .

1 с ’ 1 с

3 _ кг сг . ,,4 _ к14й1

У, =

У, = -

й ‘ й

2.3. Определить заготовку с максимальной оценкой

у, = тах

{у/; у,2; у}; у, }= у]1 у = l,4

фиксируют пару (у,; V ,). и выбирают заготовку с максимальной оценкой У\х = тах у, .

2.4. Прямоугольник (с; й) делят на пару прямоугольников (с’;й’) и (с";й’) одним из следующих способов:

если V1 =1 , то с = с; Й' = й ,; с = с;

й " = й - Й

если V1 =2, то с = с; Й =с с = с;

й" = й — с,:

если V1 =3, то с' = Й; Й’ = й ,; с" = й ;

й" = с — й ,;

если V1 =4, то с' = Й; Й’ = с ; с" = й ;

й" = с-с .

3. Заполнение полосы.

Каждой прямоугольной заготовке

(с,; Й, ),/ = 1, т , ставим сначала в соответствие пару линейных заготовок (/2,-1 = с,; ^ = й,), для

которых:

3.1. Вычисление линейных оценок У* р*- = тш

* *

У2*-1 = йг р2г-1 / й

*

Р2,-1 = 0

*

Уц-1 = 0

если й, < й' и с, < с’ ,

в противном случае;

Р2, = тт([Й'/ с, \ ь,X **

У2, = с,Р 2, / Й

р 2, = 0,1

> в противном случае.

3.2. Определение максимальной оценки У* = тах(у2*-1;у2*),

/, = Ь-Ъ Р* = Р2г—1, если У* = У2*г-1,

/г*= /ц, Р,*= Р2,,если У* = У2* .

3.3. Построение приоритетного списка. Строится приоритетный список PS по не-

*

возрастанию оценок У, , т.е.

PS = {,1, ?2,..., ,к,.., ,т } такой, что

* * *

У, > У* > ... > У .

,1 ,2 т

3.4. Укладка заготовок в полосу.

Полагают

к = 1; я,.=1"т = 0; S = 0; с0 = с, и выполняют операции раскроя и анализ полученного остатка.

3.4.1. Раскрой

Укладываем очередную из РS заготовку (,= 1к) в максимально возможном количестве

ti = тт |_с0//, Л Ь,1 Р* ).

Находим использованную к данному моменту

*

площадь S = S + tiCidiРi .

Формируем остаток с0 = с0 - tiZi и кор-

* * ректируем а, = tipi , Ь, = Ь, - tipi .

3.4.2. Анализ

Если остаток допускает дальнейшее размещение,

то полагаем к=к+1 и переходим к

операции 3.4.1.

Если полоса заполнена до конца или к= т, то вычисляется оценка данного размеще-

S

ния равная----------

Если оценка = 1, то переходим к следующей процедуре

иначе запоминается вектор размещения a и делается шаг назад. Он заключается в том, что убирается одна из последних отрезанных заготовок и во вновь полученный остаток размещаются следующие из РS заготовки.

4. Заполнение боковых пустот.

В данной процедуре осуществляется раскрой боковых пустот. Заполнение происходит первыми

подходящими в данный момент заготовками из подмножества М2.

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

1) Длинные, ci (ширина прямоугольника) < 0,5*с (ширина листа) и

di (длинна прямоугольника) > 0,8*с

2) Широкие, с > 0,8*с и dj < 0,5*с

3) Большие, ci> 0,5*с и di> 0,5*с

4) Маленькие, с< 0,5*с и di< 0,5*с

В каждой сформированной задаче перечисленные виды прямоугольников брались в различных соотношениях и рассчитывались с помощью программы, разработанной на предприятии, и программы, разработанной в настоящей дипломной работе. Результаты сравнительного численного эксперимента представлены в таблице. Данные эксперимента показали, что в 86% случаев КРА IIII SVCuT лучше КРА ПП NesT .

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

Литература

1. Мухачева Э.А. Рациональный раскрой промышленных материалов: применение АСУ. - М: Машиностроение, 1984. - 176 с.

2. Мухачева Э.А. Прямоугольный раскрой в индивидуальном производстве // Математическое обеспечение расчетов линейного и прямоугольного раскроя: Материалы Всесоюзного семинара. Уфа, 1981г.

3. Залгаллер В.А., Круглов А.И. Рулонный принцип раскроя// Математическое обеспечение расчетов линейного и прямоугольного раскроя: Материалы Всесоюзного семинара. Уфа, 1981г.

4. Adamovicn A., Albano A. Nesting twodimensional shapes in rectangular Modules // Comput. Aeded Design. 1976. 8(1). P.27-33.

5. Мухачева Э.А., Мухачева А.С., Белов Г.Н. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя. Информационные технологии. 2000 №2. С. 11-17.

6. Мухачева А.С., Валеева А.Ф., Картак В.М. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума // М.: МАИ, 2000. 192 с.

если с, < d’ и d, < с’,

№ Тип прямоугольника, % от общего числа КРА NesT КРА SVCuT № Тип прямоугольника, % от общего числа КРА NesT КРА SVCuT

1 2 3 4 1 2 3 4

1 0 20 20 60 0,906 0,911 51 10 50 0 40 0,883 0,904

2 0 50 50 0 0,826 0,854 52 10 50 10 30 0,937 0,96

3 5 10 0 85 0,798 0,83 53 10 50 30 10 0,914 0,889

4 5 10 5 80 0,976 0,982 54 10 50 40 0 0,918 0,925

5 5 10 10 75 0,927 0,935 55 10 60 0 30 0,961 0,984

6 5 10 20 65 0,89 0,881 56 10 60 10 20 0,928 0,931

7 5 10 30 55 0,921 0,94 57 10 60 30 0 0,927 0,936

8 5 10 40 45 0,918 0,902 58 10 70 0 20 0,836 0,948

9 5 10 50 35 0,856 0,876 59 10 70 10 10 0,892 0,908

10 5 10 60 25 0,841 0,857 60 10 70 20 0 0,932 0,949

11 5 10 70 15 0,837 0,844 61 10 80 0 10 0,913 0,921

12 5 10 80 5 0,863 0,874 62 10 80 10 0 0,871 0,889

13 5 10 85 0 0,854 0,867 63 30 10 0 60 0,886 0,894

14 5 20 0 75 0,959 0,97 64 30 10 10 50 0,949 0,96

15 5 20 5 70 0,938 0,926 65 30 10 30 30 0,947 0,957

16 5 20 10 65 0,879 0,896 66 30 10 40 20 0,934 0,922

17 5 20 20 55 0,874 0,881 67 30 10 50 10 0,914 0,897

18 5 20 30 45 0,907 0,914 68 30 10 60 0 0,914 0,928

19 5 20 40 35 0,893 0,884 69 30 30 0 40 0,935 0,946

20 5 20 50 25 0,857 0,862 70 30 30 10 30 0,889 0,901

21 5 20 60 15 0,879 0,897 71 30 30 20 20 0,933 0,947

22 5 20 70 5 0,873 0,879 72 30 30 30 10 0,885 0,914

23 5 20 75 0 0,864 0,871 73 30 30 40 0 0,935 0,948

24 5 30 10 55 0,971 0,988 74 30 50 0 20 0,976 0,985

25 5 30 30 35 0,879 0,892 75 30 50 5 15 0,947 0,958

26 5 30 50 15 0,912 0,906 76 30 50 10 10 0,934 0,937

27 5 30 65 0 0,871 0,876 77 30 50 20 0 0,912 0,906

28 5 50 5 40 0,948 0,94 78 40 0 50 10 0,896 0,908

29 5 50 20 25 0,876 0,882 79 40 0 60 0 0,928 0,937

30 5 50 45 0 0,881 0,887 80 40 0 0 60 0,904 0,918

31 5 70 0 25 0,895 0,904 81 40 15 0 45 0,913 0,927

32 5 70 25 0 0,872 0,903 82 40 15 20 25 0,28 0,934

33 5 85 5 5 0,885 0,895 83 40 15 40 5 0,926 0,938

34 5 85 0 10 0,908 0,912 84 40 15 45 0 0,928 0,924

35 10 0 10 80 0,885 0,894 85 40 30 0 30 0,925 0,933

36 10 0 30 60 0,906 0,915 86 40 30 10 20 0,971 0,98

37 10 0 50 40 0,917 0,925 87 40 30 30 0 0,895 0,909

38 10 0 70 20 0,879 0,877 88 40 50 0 10 0,957 0,969

39 10 0 80 10 0,855 0,862 89 40 50 10 0 0,92 0,929

40 10 10 0 80 0,897 0,918 90 50 5 15 30 0,951 0,971

41 10 10 10 70 0,983 0,99 91 50 5 30 15 0,922 0,915

42 10 10 30 50 0,886 0,891 92 50 5 45 0 0,925 0,934

43 10 10 50 30 0,894 0,906 93 50 10 10 30 0,923 0,934

44 10 10 70 10 0,899 0,914 94 50 10 30 10 0,925 0,938

45 10 10 80 0 0,891 0,895 95 50 10 40 0 0,9 0,911

46 10 30 0 60 0,976 0,986 96 50 30 10 10 0,954 0,967

47 10 30 10 50 0,925 0,918 97 50 30 0 20 0,911 0,923

48 10 30 30 30 0,925 0,927 98 50 30 20 0 0,92 0,93

49 10 30 50 10 0,921 0,933 99 70 10 0 20 0,931 0,956

50 10 30 60 0 0,89 0,908 100 70 30 0 0 0,976 0,986

Башкирский государственный аграрный университет

Уфимский государственный авиационный технический университет

APPLICATION OF COMPUTER-AIDED OF CARDS OF CUTTING OUT DESIGNS IS IN

SHIPBUILDING

Ju.I. Valiakhmetova, S.V. Telitskiy

The 2-dimensional rectangular cutting and packing problem for shipbuilding industry is under consideration. The present solving methods are surveyed and analyzed in the paper. The authors pose the computer-aided design system from the optimization core of cutting card calculation, that takes into account the basic properties of shipbuilding industry and is based on a new algorithm of rectangular items lay-by-lay placing on the sheets. The numerical experiment results verify high potential of the optimization core of the computer-aided design system Key words: cutting, optimization, lay-by-lay algorithms