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



На прав;р%£гЦ»писи

СМАГИН Михаил Анатольевич

АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ РАЦИОНАЛЬНОГО РАЗМЕЩЕНИЯ ПРЯМОУГОЛЬНЫХ ДЕТАЛЕЙ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО МЕТОДА НА МНОЖЕСТВЕ ЭВРИСТИК

Специальность

05.13.12 - Системы автоматизации проектирования

Автореферат диссертации на соискание ученой степени кандидата технических наук

Уфа 2005

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

Научный руководитель заслуж. деятель науки РФ

д-р техн. наук, проф. Мухачева Элита Александровна

Официальные оппоненты д-р техн. наук, проф.

Фроловский Владимир Дмитриевич

д-р техн. наук, проф.

Мартынов Виталий Владимирович

Ведущая организация Башкирский государственный университет

Защита состоится? 2005 г. в /Л часов

на заседании диссертационного совета Д - 212.288.03 Уфимского государственного авиационного технического университета по адресу: 450000, Уфа- центр, ул. К. Маркса 12, УГАТУ

С диссертацией можно ознакомиться в библиотеке университета Автореферат разослан «¿3 » Айнв^Ь 2005 г.

Ученый секретарь диссертационного совета д-р техн. наук, проф.

В.В. Миронов

НА НИХ

1

Актуальность темы исследования

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

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

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

Цель работы

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

Задачи исследования

Для достижения цели работы были поставлены следующие задачи:

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

задач;

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

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

4. Разработать автоматизированный комплекс проектирования рационального размещения прямоугольных деталей на рулонном, листовом материале и в открытых областях на основе разработанных алгоритмов;

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

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

Методы исследования

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

На защиту выносятся

1. Генетический алгоритм с мультиметодным представлением алгоритмов-декодеров, как основа автоматизации проектирования рациональных карт размещения деталей;

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

3. Модификация алгоритмов конструирования упаковки, ориентированной на размещении деталей в открытой области:

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

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

4. Автоматизированный комплекс построения рационального размещения деталей на рулонном, листовом материале и открытой области;

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

Научная новизна результатов

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

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

3. Разработаны методы и алгоритмы конструирования размещения деталей:

• вычислительная схема применения алгоритма замещения для размещения прямоугольных деталей на листы. Основана на учете дополнительного офаниче-ния по длине листа при укладке деталей;

• метод локальной перестройки в составе алгоритма замещения, новизна которого состоит в выработке принципов перестановки прямоугольников внутри блоков полосы, листа. Он позволяет повысить эффективность метода замещения без существенных затрат дополнительного времени;

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

Практическая значимость и внедрение результатов

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

2. Разработано математическое обеспечение двумерного прямоугольного размещения деталей в рамках автоматизированного комплекса. Его применение позволяет повысить коэффициент использования материала в среднем на 5-10% по сравнению с ручным способом или применением простых эвристик;

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

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

1. ООО «Научно-инженерное предприятие - Информатика», г. С.Петербург - внедрение в промышленную систему «Тенхтран-Раскрой», 2005.

2. УГАТУ - учебный процесс по специальностям: 080116 «Математические методы в экономике», 010503 «Математическое обеспечение и администрирование информационных систем», в рамках курсов «Методы оптимизации» и «Математические методы и модели исследования операций» и при выполнении курсовых и дипломных работ, 2004-2005.

Связь исследования с научными проблемами

Работа выполнялась при частичной поддержке грантов Российского фонда фундаментальных исследований (РФФИ), проекты 99-01-000937, 01-01-000510 и 03-01-07002.

Апробация работы и публикации

Первые результаты в виде генетического алгоритма с двумя известными алгоритмами конструирования размещения нашли свое место в дипломной работе «Генетический алгоритм на базе различных декодеров для решения задачи распределения двумерного ресурса», которая была отмечена медалью Министерства Образования РФ «За лучшую научную студенческую работу». Созданный программный комплекс отмечен дипломом за первое место в конкурсе на «Лучшую программу для ЭВМ, созданную при дипломном проектировании» Уфимского государственного авиационного технического университета.

Результаты работы, а также отдельные ее разделы докладывались, обсуждались и получили положительную оценку на конференциях: Республиканский конкурс научных работ (Уфа, 2000 (доклад отмечен дипломом), 2002 (работа отмечена грамотой дипломата конкурса научных работ)); Двенадцатая Байкальская международная конференция «Методы оптимизации и их приложения» (Иркутск, 2001); Международная конференция «Компьютерные науки и информационные технологии» С81Т (Уфа, 2001, 2002,2005); Всероссийская научно-практическая конференция "Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования" ОПТИМ-2001 (С.Петербург, 2001); Всероссийская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002, 2004); Всероссийская научно-техническая конференция с международным участием «Мехатроника, Автоматизация, Управление» (Уфа, 2005); семинары кафедры вычислительной математики и кибернетики Уфимскою государственного авиационного технического университета.

По теме диссертации опубликовано 17 работ. Правовая сторона программного комплекса защищена «Свидетельством об официальной регистрации программ для ЭВМ» № 2002610945.

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

Структура работы

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

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

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

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

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

Базовыми при подготовке диссертации явились теоретические разработки Э.А. Мухачевой в области САПР раскроя, разработки в области САПР размещения объектов сложной формы и гильотинного раскроя, подготовленные профессорами М.А. Верхотуровым, В.В. Мартыновым и Т.М. Сиразетдиновым.

Постановки задач двумерного размещения деталей

1. Размещение прямоугольных предметов в полубесконечную полосу (1.5DBPP). Имеется прямоугольная полоса заданной ширины W и неограниченной длины, и набор прямоугольных предметов с размерами (w, ; l„) i = 1,т. Введем прямоугольную систему координат: оси 0Х и 0У совпадают со сторонами полосы. Положение i-ro прямоугольника назовем горизонтальным, если его сторона длины 1, параллельна неограниченной грани полосы, а вторая сторона перпендикулярна ей. Горизонтальное положение каждого прямоугольника i зададим вектором (х,; у,), соответствующим левой нижней точке прямоугольника. Набор векторов (х,; у,) задает прямоугольное размещение (Rectangle packing, RP) деталей, если

Wii,j = \,m;iïj;(xl>xj+lJ vx, >*,+/,) >.у,vy, > j/,+vv,); (1) для i = \,m,xi >0 л j>, >0 Ayi+w, <W. (2)

Если длина L(RP) занятой части полосы достигает минимума, то RP называется оптимальным размещением.

В задаче 1.5DBPP требуется при выполнении условий (1) и (2) минимизировать занятую часть полосы.

2. Размещение прямоугольных предметов на листы (2DBPP). Имеется набор прямоугольных листов с размерами (W, ; L), г = Гй (W- ширина листа, L -длина листа), и набор прямоугольных предметов с размерами (w, ; lj,) j = Un. Введем прямоугольную систему координат для каждого из листов: оси 0Х и 0У совпадают со сторонами листа. Положение прямоугольника к в листе i зададим вектором (хь- ytj,, где {хк; ук) - левая нижняя точка прямоугольника. Набор векторов (хк; Уь), задает прямоугольное размещение деталей на листе i, i е Vn, если

для \/k,qel,m;k*q:(xt >хя +/? vx >х4 +lt)v(yt >yq >yt +wt);

(3) _

дляЛ = 1 ,m;xt > 0 л ук > 0 л х, + lt <, L, л yt + w, £ Wt. (4)

Если количество требуемых для размещения листов N(RP) достигает минимума, то RP называется оптимальным размещением.

В задаче 2DBPP требуется при выполнении условий (3) и (4) минимизировать количество необходимых для размещения предметов листов.

3. Размещение прямоугольных предметов в открытой области (2DAMP). Задан квадрант в плоскости и набор прямоугольных предметов с размерами (Wj ; lj.) j = l,m. Введем прямоугольную систему координат для открытой области: оси 0Х и Oy совпадают с его сторонами. Положение каждого прямоугольника i зададим вектором (х,; у,) с минимальными координатами. Набор векторов (х,; у,) называется прямоугольным размещением деталей в открытой области, если

для i,j = \,m;i*j;xl^xJ+lJ vx, >x,+l, v yt >_yy +wj >y, +w,; (5)

Если площадь S(RP) покрывающего занятую часть открытой области прямоугольника достигает минимума, то RP называется оптимальным размещением.

В задаче 2DAMP требуется при выполнении условия (5) минимизировать площадь покрывающего занятую часть открытой области прямоугольника.

В главе приводится обзор основных методов решения задачи двумерного размещения прямоугольных объектов. Методы, основанные на линейном целочисленном программировании и полного перебора с отсечением неперспективных вариантов, позволяют получать решения задачи только при малых размерностях (до 10-20) различных деталей. Здесь для получения за приемлемое время близкого к оптимальному решения используется метаэвристика генетический алгоритм с набором простых эвристик конструирования размещения. Среди них такие, как алгоритм «нижний левый» (Jakobs) и «улучшенный нижний левый», представленный D. Liu и Н. Teng, блочный алгоритм, разработанный A.C. Мухачевой, A.B. Чиг-линцевым под руководством Э.А. Мухачевой, алгоритм замещения и двойственный (A.C. Мухачева-Филиппова). В качестве алгоритма генерации приоритетных списков и их направленного перебора используется генетический алгоритм с процедурами скрещивания, мутации и селекции.

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

Для графического представления карты размещения применяются различные схемы кодирования. Среди них такие, как:

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

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

представляющая порядок их размещения: п (1[я], 2[я], Правила укладки

прямоугольников задаются отдельно внутри эвристики-декодера. Данное представление удобно для его использования в генетических алгоритмах, поскольку они как раз и работают с последовательностями (ген), кодирующими размещение деталей (особь).

3. Кодирование парой последовательностей. Мига1а и др. предложили схему кодирования названную парой последовательностей. Пример размещения, закодированного парой последовательностей, представлен на рисунке 1.

: в,3, 1,4,5,2

а- :1,2,3,4.в,6

Рисунок 1. Пара последовательностей

Основываясь на этом кодированном решении, относительные местоположения для каждой пары i и j прямоугольников строятся следующим образом: Если i располагается переду в обеих перестановках, мы должны разместить i левее j. Если i располагается перед / в а+ и после j в а_, то мы помещаем i выше j. Например, на рисунке 1, " 1 расположен перед 4 в обеих перестановках, и, следовательно, 1 левее, чем 4 ", "4 располагается перед 2 в о+ и после 2 в о , и, следовательно, 4 -выше, чем 2" и так далее.

4. Кодирование блок-структурой (Block Structure, BS). Пусть имеется прямоугольное размещение, RP. Проведем мысленно через правые стороны прямоугольников вертикальные резы. Эти линии разбивают RP на прямоугольные вертикальные блоки одной и той же ширины W и различной длины. Пусть длина рассматриваемой RP равна L. Фиксируя L, проведем мысленно через верхние стороны прямоугольников горизонтальные линии. Тогда RP разобьется на горизонтальные блоки одной и той же длины L и различной ширины. Таким образом, мы получаем две блок-структуры для RP, вертикальную и горизонтальную (UBS, HBS). Сопоставим блок-структурам списки S и S. Каждому блоку j соответствует в списке кортеж (запись номеров прямоугольников, пересекающих блок) и длина Xi вертикального (ширина г^ - горизонтального) блока. Тогда

s = (i(/),2(/), ■•• )х> s-(i(J), 2(7),..., /(7),- И» (О

где i(j) (i(7)) - номер прямоугольника, пересекающегоу'-й (7) блок, г -количество вертикальных, q - горизонтальных блоков.

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

в 5

3 4

1

2

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

Декодер "нижний левый" (Bottom Left, BL). Алгоритм "нижний-левый" в редакции Jakobs удобно представить в виде последовательности шагов:

Шаг 1: Поместить первый прямоугольник из я в левый нижний угол полосы.

Шаг i: Последовательно передвинуть прямоугольник i из я, i = ijn, начиная с верхнего правого угла упакованной площади полосы влево настолько, насколько это возможно, затем вниз, снова влево, вниз и т.д., до тех пор, пока он не сможет быть сдвинут влево или вниз.

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

Декодер "усовершенствованный нижний левый" (Improved Bottom Left, IBL). Алгоритм "усовершенствованный нижний левый", предложен Liu и Teng на основе алгоритма "нижний левый", отличается стратегией размещения очередного i-ro прямоугольника: при его размещении передвижение влево имеет преимущество (при горизонтальном расположении полосы).

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

Блочный декодер (Block decoder, BD). Разработан A.B. Чиглинцевым. Блочный декодер ориентирован на формирование блочной структуры. В качестве начального блока принимается полоса бесконечной длины. По мере размещения прямоугольников согласно л формируют и модифицируют блоки.

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

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

Двойственный декодер (Double decoder, DD). Декодер разработан A.C. Мухачевой-Филипповой и P.P. Шир газ иным.

Алгоритм основан на решении задачи линейного раскроя запаса материала и двойственной к ней задачи" (Cutting Stock Problems, 1DCSP). Имеется материал, поступающий в виде стержней (полос), длины Z. Путем его раскроя требуется получить набор из m различных предметов заданной длины Я,, i = l,m ив необходимом количестве ty каждого вида i = l,m . Нужно найти план раскроя с минимальным расходом материала. Искомый план представляет совокупность раскроев rv 5 V - 1,л, заданных списком кортежей (l(v),2(y),..)%v, J*(v) - номера получаемых предметов, Xv ~ интенсивность применения каждого раскроя v. Расход материа-

Термин двойственности применяется здесь не в связи с линейным программированием

л а характеризует величина N = £ х. • задача хорошо изучена, для ее решения

Х-1

известны точные и эвристические алгоритмы.

Вернемся к исходной задаче 1.5DBPP. Если положить Z=W; Я, = wt и

b,=l,, i-\,m то 1.5DBPP трансформируется в 1DCSP с (Z=W; m; Л = и>;

Ъ = 1). Если же положить Z=N; Я, = /,, b, = w,.) i = 1, т , то 1.5DBPP трансформируется в 1DCSP* с (Z=N; m; Л = I ; b = w).

Двойственный декодер основан на последовательном решении задач RCSP и RCSP*. Причем каждый из них решается методом следующий подходящий (Next Fit, NF). При этом формируются две блок-структуры (вертикальная и горизонтальная), по которым строится карта размещения прямоугольников.

Декодер применяется для размещения прямоугольных объектов в полосу и в открытой области. Во втором случае при использовании двойственного декодера возникает дополнительная задача определения размера стержней при решении задачи линейного раскроя запаса материала (1DCSP).

Декодер замещения для задачи 1.5DBPP (Substitution, Sub). Алгоритм замещения разработан A.C. Мухачевой-Филипповой и P.P. Ширгазиным для размещения прямоугольников в полубесконечной полосе.

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

Декодер замещения для задачи 2DBPP (SubS). На базе алгоритма Sub в диссертации разработан алгоритм замещения в листы. Итерация в данном алгоритме — процесс укладки одного кортежа блок-структуры. Для этого согласно перестановки п, соблюдая условия непересечения, укладываем прямоугольники в текущую блок-структуру. Далее формируем кортеж, генерируем текущую блок-структуру и переходим на следующую итерацию, до тех пор, пока не будут уложены все возможные прямоугольники из я- в заданный лист. Длину кортежа определяем как минимальную среди прямоугольников длину, занимаемую ими в текущей блок-структуре.

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

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

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

Здесь же рассмотрен алгоритм, основанный на кодировании парой последовательностей.

Пара последовательностей - пара перестановок а = (о+, о_) 1= {1,2, ..., /и}, где о+ (I) = / означает, что прямоугольник г - это 1-й прямоугольник в о+(а_). Пара последовательностей определяет раздвинутость прямоугольников по оси X или по оси У, то есть задает неперекрытие прямоугольников.

Пара последовательностей обладает следующими свойствами:

1. Размерность пространственного поиска (то есть, число всех возможных закодированных решений) конечна;

2. Каждое закодированное решение соответствует допустимому размещению;

3. Расшифровка размещения (то есть вычисление координат из закодированного решения) возможна за полиномиальное время;

4. Существует закодированное решение, которое соответствует оптимальному размещению.

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

На этапе скрещивания происходит формирование новых особей (перестановок прямоугольников) на основе уже существующих. При этом в новом особе-потомке находят свое отражение черты обоих родителей.

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

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

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

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

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

Основные подсистемы САПР размещения деталей приведены на рис. 2:

Рисунок 2. - Структура САПР размещения

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

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

3. Подсистема постпроцессорной обработки информации. Включает блок получения статистической информации о карте раскроя (КРА, количество листов и т.д.), блок отображения карты раскроя, блок сохранения полученных результатов.

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

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

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

1. Сравнение различных декодеров в рамках одного внешнего генетического алгоритма. Показана эффективность применения декодеров для классов задач (мелких, больших, длинных, коротких, с разбросом по размерам), даны рекомендации по их использованию. Так, для мелких и длинных заготовок предпочтительнее алгоритм замещения (коэффициент раскроя соответственно 95,6% и 96%), для больших - улучшенный блочный (93,5%). Для коротких заготовок и набором заготовок, с большим разбросом по размерам, оба алгоритма показывают достаточную эффективность (94-95%%).

2. На примерах Bortfeld. В результате эксперимента показана эффективность решения задачи размещения на примерах, предложенных Bortfeld, приведено сравнение с его результатами. Для 5 классов из 10 генетический алгоритм с декодером замещения показывает лучший результат

3. На примерах S.P. Fekete и J. Schepers. В результате эксперимента получены результаты решения задачи размещения на листы в сравнении с нижней границей и алгоритмами других авторов. Алгоритм замещения с генетикой показывает в среднем лучшие решения для всех классов задач (отклонение от нижней границы 5,64-7,75%%).

4. Сравнение декодеров для решения задачи размещения в открытой области на различных классах исходных данных. Показана эффективность разработанных в диссертации декодеров для данной задачи. Средний коэффициент раскроя решений, полученных на базе двойственного декодера, составляет 95,3%, на базе алгоритма пары последовательностей - 87,6%.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

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

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

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

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

Основные результаты диссертационной работы:

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

2. Рассмотрена возможность и разработана технология использования алгоритмов конструирования карты размещения деталей в совместной работе с внешней метаэвристикой (генетическим алгоритмом) для осуществления процесса локального поиска рационального размещения деталей.

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

4. В рамках системы САПР раскройно-заготовительного производства разработана подсистема размещения деталей в полубесконечной полосе, листах, в открытой области. Применена схема использования генетического алгоритма совместно с алгоритмами конструирования карт размещения, такими, как «нижний левый», «улучшенный нижний левый», блочный, замещения, двойственный и другими. Все это позволяет повысить коэффициент использования материала в среднем на 5—10% по сравнению с ручным способом или применением простых эвристик, значительно сократить время проектирования и упростить процедуру получения карты размещения деталей.

5. Разработана и программно реализована система учета технологических параметров, таких, как возможность поворота деталей на 90°, припуск на ширину реза, окантовку рулона или листов. Это позволяет расширить практические возможности и значимость разработанного автоматизированного комплекса.

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

Публикации по теме диссертации

1. A.C. Мухачева, A.B. Чиглинцев, М.А. Смагин, Э.А. Мухачева //Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения Информационные технологии. Приложение. М.: Машиностроение. 2001. №9. 24 с.

2. A.C. Мухачева, М.А. Смагин // Задача прямоугольной упаковки: гибридизация классического генетического алгоритма с процедурами последовательного уточнения оценок / Труды XII Байкальской междунар. конф. Иркутск : ОКИС ЦНИТ ИГУ. 2001. Т. 6. С. 33-38.

3. A.C. Мухачева, М.А. Смагин // Гибридные алгоритмы для задачи прямоугольной упаковки на базе генетического метода "нижний левый" и "последовательного уточнения оценок" / Математическое моделирование в решении научных и технических задач. Вып. 2. Уфа : Технология. 2001. С. 65-70.

4. A.C. Мухачева, A.B. Чиглинцев, М.А. Смагин, Д.И. Бунаков //Задача прямоугольной упаковки: гибридный алгоритм на базе генетических процедур // ОПТИМ - 2001. Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования: Матер, конф. СПб.: ЦНИИ технологии судостроения.-2001. С. 109-113.

5. Э.А. Мухачева, A.C. Мухачева, М.А. Смагин //. Задача прямоугольной упаковки: классический генетический метод с алгоритмами «Нижний левый» и «Последовательного уточнения оценок» / Принятие решений в условиях неопределенности. Межвуз. науч. сб. Уфа : УГАТУ. 2001. С. 78-87.

6. A.C. Мухачева, С.Х. Курелеиков, М.А. Смагин, P.P. Ширгазии

//Методы локального поиска оптимума прямоугольной упаковки с использованием двойственной схемы / Информационные технологии. М. : Машиностроение. 2002. №10. С. 26-31.

7. Э.А. Мухачева, М.А. Смагин // Решение задачи распределения двухмерного ресурса методами генетических алгоритмов / Принятие решений в условиях неопределенности. Межвуз. науч. сб. Уфа : УГАТУ. 2002. С. 138-144.

8. Э.А. Мухачева, A.C. Мухачева, М.А. Смагин // Методика тестирования и анализ результатов работы блочного и двойственного декодеров на базе генетического алгоритма / Принятие решений в условиях неопределенности: Научн. изд-е. Уфа: УГАТУ. 2003. С. 170-176.

9. A.C. Мухачева, A.B. Чиглинцев, М.А. Смагин, Н.М. Садретдинова //Процедуры расшифровки решений задачи двухмерной упаковки / Сб. тр. конф. по компьютерным наукам и информационным технологиям. Уфа : УГАТУ, 2003. Т. 2. С. 44-47. (статья на англ. яз.).

10. Э.А. Мухачева, A.C. Мухачева, A.B. Чиглинцев, М.А. Смагин, Л.А. Ильясова // Задача прямоугольной упаковки: численный эксперимент с

генетическими алгоритмами и различными декодерами / Принятие решений в условиях неопределенности. Уфа : УГАТУ. 2005. С. 63-70.

11. М.А. Месягутов, М.А. Смагин, A.C. Филиппова //Упаковка на листы декодером замещения на базе алгоритма локального поиска / Сборник трудов конференции по компьютерным наукам и информационным технологиям. Уфа : УГАТУ. 2005. Т. 2. С. 164-166. (статья на англ. яз.).

12. М.А. Смагии Автоматизированная система двумерной упаковки с использованием различных декодеров на базе генетического алгоритма агин // Мехатроника, автоматизация, управление: Вторая Всерос. науч.-техн. конф. с междунар. участием. Уфа: УГАТУ. 2005. С. 425-430.

Диссертант

М.А. Смагин

Смагин Михаил Анатольевич

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

Специальность 05.13.12 - Системы автоматизации проектирования

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 21.11.2005. Формат 60x84 1/16 Бумага офсетная. Печать плоская. Гарнитура Тайме. Усл. печ. л. 1,0. Усл. кр.-отт. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 519.

ГОУВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К. Маркса, 12

i i

\ш

У

!

1

Ш 23 4 ] ;

РНБ Русский фонд

2006-4 27696

Оглавление.

Введение.

1. Анализ современных моделей и методов проектирования двумерного размещения.

1.1. Автоматизация проектирования и технологической подготовки заготовительного производства.

1.2. Классификация задач размещения и место исследуемых задач в ней.

1.3. Общая постановка задач двумерного размещения.

1.4. Математические модели двумерного размещения.

1.5. Обзор методов решения задачи двумерного размещения.

1.5.1. Точные методы, их достоинства и недостатки.

1.5.2. Простые эвристики.

1.5.3. Методы локального поиска оптимума. Общая схема и метаэвристики.

1.6. Автоматизированные системы проектирования размещения деталей.

1.7. Выводы.

2. Эвристические методы размещения деталей на заданных объектах.

2.1. Схемы кодирования.

2.1.1. Прямая схема кодирования.

2.1.2. Кодирование приоритетным списком, перестановкой.

2.1.3. Кодирование парой последовательностей.

2.1.4. Кодирование блок-структурой.

2.2. Однопроходные эвристики проектирования размещения.

2.2.1. Декодер "нижний левый".

2.2.2. Декодер "усовершенствованный нижний левый".

2.2.3. Блочный декодер.

2.2.4. Двойственный декодер.

2.2.5. Метод размещения деталей в открытую область на базе двойственного алгоритма.

2.2.6. Декодер замещения.

2.2.7. Метод локальной перестройки.

2.2.8. Схема применения алгоритма замещения для размещения деталей на листы.

2.3. Выводы.

3. Генетический алгоритм решения задач прямоугольной упаковки.

3.1. Генетический алгоритм с позиций локального поиска экстремума.

3.2. Процедуры скрещивания и мутации.

3.3. Модификации генетического алгоритма.

3.4. Схема ограничения поиска решений в генетическом алгоритме.

3.5. Выводы.

4. Автоматизированный комплекс построения рационального размещения. Численные эксперименты.

4.1. Организация раскройно-заготовительного производства.

4.2. Структура САПР рационального размещения.

4.3. Описание автоматизированного комплекса построения рационального размещения.

4.3.1. Схема нахождения рационального размещения.

4.3.2. Выполнение задачи размещения автоматизированным комплексом.

4.3.3. Функциональные возможности автоматизированного комплекса

4.4. Постановка численных экспериментов и анализ их результатов.

4.4.1. Исследование работы генетического алгоритма с различными декодерами.

4.4.2. Решение задач размещения на полосу на примерах Bortfeld.

4.4.3. Решение задач размещения на листы на примерах S.P Fekete и J. Schepers.

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

4.5. Выводы.

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

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

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

В настоящее время используются системы автоматизированного проектирования размещения деталей (как отечественных, так и зарубежных разработок), отличающиеся структурой и объемом выполняемых работ, качеством конструирования решения и технологической подготовки производства. В первую очередь были разработаны автоматизированные системы «Нестинга» (размещение деталей сложных форм), особого внимания заслуживают разработки В.Д. Фроловского и A.A. Петунина. Система «Техтран-Раскрой» компании «НИП-Информатика», разработанная под руководством Фроловского В.Д., объединяет возможности CAM-системы с функциями организации производственного процесса [48]. Система «Сириус» (A.A. Петунин) предназначена для проектирования рационального раскроя, а также для подготовки управляющих программ резки [43]. Однако в различных системах проектирования долгое время вопросы экономии материальных ресурсов уходили на второй план. Внимание уделялось главным образом логическим, а не расчетным операциям. Расчеты и проектирование выполнялись быстро за счет использования простых однопроходных эвристик. Попытка объединить два критерия, затраты времени и экономия материала, была осуществлена в докторской диссертации ЭА. Мухачевой[34]. Она использовала в системах автоматизации линейное программирование. Это оказалось возможным в условиях массового производства.

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

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

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

Цель работы

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

Для достижения цели работы были поставлены следующие задачи:

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

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

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

4. Разработать автоматизированный комплекс проектирования рационального размещения прямоугольных деталей на рулонном, листовом материале и в открытых областях на основе разработанных алгоритмов;

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

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

Методы исследования

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

На защиту выносятся

1. Генетический алгоритм с мультиметодным представлением алгоритмов-декодеров, как основа автоматизации проектирования рациональных карт размещения деталей;

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

3. Модификация алгоритмов конструирования упаковки, ориентированной на размещении деталей в открытой области:

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

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

4. Автоматизированный комплекс построения рационального размещения деталей на рулонном, листовом материале и открытой области;

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

Научная новизна работы

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

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

3. Разработаны методы и алгоритмы конструирования размещения деталей:

• вычислительная схема применения алгоритма замещения для размещения прямоугольных деталей на листы. Основана на учете дополнительного ограничения по длине листа при укладке деталей;

• метод локальной перестройки в составе алгоритма замещения, новизна которого состоит в выработке принципов перестановки прямоугольников внутри блоков полосы, листа. Он позволяет повысить эффективность метода замещения без существенных затрат дополнительного времени;

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

Практическая значимость работы

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

2. Разработано математическое обеспечение двумерного прямоугольного размещения деталей в рамках автоматизированного комплекса. Его применение позволяет повысить коэффициент использования материала в среднем на 5-10% по сравнению с ручным способом или применением простых эвристик;

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

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

1. ООО «Научно-инженерное предприятие - Информатика», г. С.-Петербург -внедрение в промышленную систему «Тенхтран-Раскрой», 2005.

2. УГАТУ - учебный процесс по специальностям: 080116 «Математические методы в экономике», 010503 «Математическое обеспечение и администрирование информационных систем», в рамках курсов «Методы оптимизации» и «Математические методы и модели исследования операций» и при выполнении курсовых и дипломных работ, 2004-2005. Связь исследования с научными проблемами

Работа выполнялась при частичной поддержке грантов Российского Фонда Фундаментальных Исследований (РФФИ), проекты 99-01-000937, 01-01-000510 и 03-01-07002.

Апробация работы и публикации

Первые результаты в виде генетического алгоритма с двумя известными алгоритмами конструирования размещения нашли свое место в дипломной работе «Генетический алгоритм на базе различных декодеров для решения задачи распределения двумерного ресурса», которая была отмечена медалью

Министерства Образования РФ «За лучшую научную студенческую работу». Созданный программный комплекс отмечен дипломом за первое место в конкурсе на «Лучшую программу для ЭВМ, созданную при дипломном проектировании» Уфимского государственного авиационного технического университета.

Результаты работы, а также отдельные ее разделы докладывались, обсуждались и получили положительную оценку на конференциях: Республиканский конкурс научных работ (Уфа, 2000 (доклад отмечен дипломом), 2002 (работа отмечена грамотой дипломата конкурса научных работ)); Двенадцатая Байкальская международная конференция «Методы оптимизации и их приложения» (Иркутск, 2001); Международная конференция «Компьютерные науки и информационные технологии» СБГГ (Уфа, 2001, 2002, 2005); Всероссийская научно-практическая конференция "Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования" ОПТИМ-2001 (С.-Петербург, 2001); Всероссийская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002, 2004); Всероссийская научно-техническая конференция с международным участием «Мехатроника, Автоматизация, Управление» (Уфа, 2005); семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.

По теме диссертации опубликовано 17 работ. Правовая сторона автоматизированного комплекса защищена «Свидетельством об официальной регистрации программ для ЭВМ» № 2002610945.

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

Структура и объем работы

Диссертация состоит из введения, 4-х глав, выводов, списка литературы, и приложений, включающих табличные результаты численных экспериментов, блок-схему генетического алгоритма. Работа изложена на 115 страницах машинописного текста, кроме того, содержит 31 рисунок и 10 таблиц. Библиографический список включает 107 наименований и занимает 11 страниц.

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

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

2. Разработана технология использования множества алгоритмов конструирования карты размещения деталей в совместной работе с внешней метаэвристикой (генетическим алгоритмом) для осуществления процесса локального поиска рационального размещения деталей.

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

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

5. Разработана и программно реализована система учета технологических параметров, таких, как возможность поворота деталей на 90°, припуск на ширину реза, окантовку рулона или листов. Это позволяет расширить практические возможности и значимость разработанного автоматизированного комплекса.

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

Заключение

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

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

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

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

1. Аккуратов Г.В., Березнев В.А., Брежнева O.A. О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Уфа: УАИ. 1990. С. 145154.

2. Бабаев Ф.В. Оптимизация раскроя материалов: Обзор. М.: НИИМАШ, 1978.- С.72.

3. Бабаев Ф.В. Оптимальный раскрой материалов с помощью ЭВМ. -М.: Машиностроение. 1982.

4. Бабкова Е.В. Задача оценки сложности раскроя в условиях автоматизированного управления производством // Принятие решений в условиях неопределенности: Межвуз. науч. сб. -Уфа: УГАТУ, 2000. -С.136-141.

5. Бабкова Е.В. Модель сменной загрузки раскройного оборудования // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2002. - С. 184-190.

6. Батищев Д.И. Генетические алгоритмы решения экстремальных задач // под редакцией Я.Е. Львовича: Учеб. пособие. Воронежский гос. техн. ун-т; Нижегородский гос. ун-т. Воронеж, 1995. 69с.

7. Булавский В.А., Яковлева М.А. О решении задач оптимального раскроя линейных материалов на ЭВМ // Математические методы в технико-экономических расчетах: Материалы научного совещания, т. IV. М.: АН СССР. 1961. С. 83-87.

8. Бухвалова В.В. Задача прямоугольного раскроя: метод зон и другие алгоритмы // С.Петербург: Государственный университет. 2001.

9. И. Верхотуров М.А. Задача нерегулярного раскроя плоских геометрических объектов: моделирование и расчет рационального раскроя // Информационные технологии. 2000. №5. С.37-42.

10. Гамберг В.Я., Липовецкий А.И., Петунин A.A. Автоматизация проектирования раскройных карт в условиях индивидуального производства // Кузнечно-штамповочное производство, 1982.-N3 С.26-27.

11. Гери М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи // М. Мир. 416с.

12. Гимади Э.Х., Залюбовский В.В. Задача упаковки в контейнеры: асимптотически точный подход // Известия вузов. Математика. 1997. №12. С. 2533. Работа поддержана РФФИ: проекты 96-01-01591 и 97-01-00890.

13. Гончаров E.H., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения .// Дискретный анализ и исследование операций. 1999. Серия 2. 6. №1. С. 12-32. Работа поддержана РФФИ: проекты 99-01-00601, 98-07-90259.

14. Горанский Г.К., Бендерева Э.И. Технологическое проектирование в комплексных автоматизированных системах подготовки производства. -М.:Машиностроение, 1981.-455 с.

15. Долгопольский Б.С., Бритарев К.Ф. Арцишевский Ю.Ю. Система автоматизированного проектирования на ЭВМ процессов холодной листовой штамповки. -М.: Кузнечно-штамповочное производство. 1979. №6. С. 13-14.

16. Жукова Т.Ю. Применение метода "Моделирование отжига" для решения задачи раскроя // Уфа: Принятие решений в условиях неопределенности. 2003. С. 230-235. Работа поддержана РФФИ, проект 01-0100510.

17. Канторович JI.B., Залгаллер В.А. Рациональный раскрой промышленных материалов // Новосибирск: Наука СО. 1971. 299с.

18. Канторович JI.B., Заллгаллер В.А. Расчет рационального раскроя материалов // Лениздат. 1951.

19. Кацев C.B. Об одном классе дискретных минимаксных задач: Кибернетика, 1979, №5, с. 139-141.

20. Коробцева H.A. САПР одежды: исторический экскурс и обзор существующих систем // Текстильная промышленность. 2003. №5. С.61-62. №6. С. 63-65.

21. Кочетов Ю., Усманова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // Иркутск: XII Байкальская международная конференция. 2001. С.22-27. Работа поддержана РФФИ: проект 01-01-00510.

22. Липовецкий А.И. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении. Минск. 1985. С. 80-87.

23. Липовецкий А.И. Свойства прямоугольных укладок и алгоритмы оптимального раскроя // Управляющие системы. ИМ СОАН ССР. 1984., вып. 25. 34 с.

24. Макеев Б.А., Батозский В.И. и др. Автоматизация раскроя тонколистового проката. -М.: Кузнечно-штамповочное производство. 1978. №6. С. 30-33.

25. Мартынов В.В. Информационная система раскроя плоских геометрических объектов сложной формы: основные проблемы и подходы к их решению // Вестник УГАТУ. -Уфа, Изд.УГАТУ, 2001. С. 105-113.

26. Мухачева A.C., Куреленков С.Х., Смагин М.А., Ширгазин P.P. Методы локального поиска оптимума прямоугольной упаковки с использованием двойственной схемы // Информационные технологии. 2002. №10. С. 26-31. Работа поддержана РФФИ, проект 01-01-00510.

27. Мухачева Э.А. Валеева А.Ф. Метод динамического перебора в задаче двумерной упаковки // Информационные технологии. 2000. №5. С. 30-37. Работа поддержана РФФИ: проект 99-01 -00947.

28. Мухачева Э.А. Методы условной оптимизации в задаче рационального раскроя листового проката // Оптимизация: Сб. науч. трудов СО АН СССР. 1978. Вып. 22. С. 83-93.

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

30. Мухачева Э.А. Рациональный раскрой прямоугольных листов на прямоугольные заготовки // Оптимальное планирование: Сб. научных трудов СО АН СССР. 1966. Вып. 6. С. 43-115.

31. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов // Уфа. УГАТУ. 1998. 216 с.

32. Мухачева Э.А., Ермаченко А.И., Сиразетдинов Т.М., Усманова А.Р. Метод поиска минимума с запретами в задачах двумерного гильотинногораскроя II Информационные технологии. 2001. №6. С. 25-31. Работа поддержана РФФИ: проект 99-01-00947, 01-01-00510.

33. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя // Информационные технологии. 2000. №9. С. 15-22. Работа поддержана РФФИ: проект 99-01-00947.

34. Мухачева Э.А., Мухачева A.C. Метод перестройки для решения задачи прямоугольной упаковки // Информационные технологии. 2000 №4. С. 30-36. Работа поддержана РФФИ, проект 99-01-00947.

35. Мухачева Э.А., Мухачева A.C., Белов Г.Н. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя Информационные технологии. 2000 №2. С. 11-17. Работа поддержана РФФИ: проект 99-01-00947.

36. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование // Новосибирск. Наука СО. 1987. 272 с.

37. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. // Информационные технологии. 1999. №1. С. 2-7.

38. Петунин A.A. Интегрированная САПР "Сириус" для автоматизации раскройно-заготовительного производства // С.Петербург: ОПТИМ-2001. С. 123126.

39. Романовский И.В. Алгоритмы решения экстремальных задач // М.: Наука. 1977.

40. Романовский И.В. Решение задачи гильотинного раскроя методом переработки списка состояний // Кибернетика. 1969. №1. С. 102-104.

41. Романовский И.В., Христова Н.П. Решение дискретных минимаксных задач методом дихотомии // ЖВМ и МФ. 1973. 13(5). С. 1200-1209.

42. Усманова А. Вероятностные жадные эвристики для задачи упаковки в контейнеры // С.Петербург: ОПТИМ-2001. С. 141-146. Работа поддержана РФФИ: проекты 99-01-00947, 01-01-00510.

43. Фроловский В. Моделирование и оценка качества проектных решений в системах сквозного проектирования корпусных изделий из листового материала // Информационные технологии. 2000. №5. С. 18-25.

44. Петербург: ЦНИИТС. 2001. С.182-188.

45. Фроловский В.Д. Целочисленная аппроксимация и оптимальное группирование геометрических объектов в задачах размещения // Научный вестник НГТУ. № 1(8). 2000. С. 37-46.

46. Шпур Г., Краузе Ф.-Л. Автоматизированное проектирование в машиностроении. М.-.Машиностроение, 1988.-648с.

47. Aurts Е., Lenstra J., edit. Local Search in Combinatorial Optimization/ // John Wiley&Sons. 1996.

48. Adamovicn A., Albano A. Nesting two-dimensional shapes in rectangulark M, ,

49. Modules // Comput. Aeded Design. 1976. 8(1). P.27-33.

50. Baesley J.E. http://mscmga.ms.ic.ac.-uk/info.html.

51. Beasley. J.E. A population heuristic for constrained two-dimensional nonguillotine cutting. EJOR, 156, 2004, p.601-627.

52. Baker B.S., Coffman E.G. and Rivest R.L., Orthogonal packing in two dimentions. SIAM Journal of Computing 9. 1980. pp. 846-855.

53. Bischoff E., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1995. 84.

54. Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem // Annals of OR. 1993. 41(4). P.313-325.

55. Caprara A. and Toth P. Lower bounds and algorithms for the 2-dimentional vector packing problem. Discrete Applied Mathematics, 111. 2001. pp. 231-262.

56. Cavique L., Rego C. and Themido I., Case oriented paper Subgraph ejection chains and tabu search for the crew sheduling problem. 50. 1999. pp. 608-616.

57. Coffman E., Garey M., Jchonson D. Approximation algorithms for bin-packing-an updated survey // Algorithm Design for Computer System Design (Ausiello G., Lucertini M., Serafini P. eds) Berlin etal. 1984.

58. Coffman E.G., Garey M.R., Johnson D.S. and Tarjan R.E., "Perfomance bounds for level-oriented two-dimentional packing algorithms" S1AM Journal on Computing 9 (1980) P. 801-826.

59. Dorigo M., Di Caro G., Gambardella L.M. Ant Algorithms for Discrete Optimization // Artificial Life. 1999. Vol.5. No.3. pp. 137-172.

60. Dyckhoff H., Scheithauer G., Terno J. Cutting and Packing // Annotated Bibliographies in Combinatorial Optimization, edited by M.Dell'Amico, F.Maffioli and S.Martello. John Wiley&Sons. 1997. P.393-412.

61. Dykhoff H. A typology of cutting and packing problems // Evropean Journal of Operational research. 1990. Vol. 44. P. 145-159.

62. Dykhoff H., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1990. 44(2).

63. Folkenauer E. Tapping the full power of genetic algorithm through suitable representation and local optimization: Application to bin packing // Evolutionary Algorithms in Management Applications. Berlin. 1995. P. 167-182.

64. Folkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing // Journal of Heuristics. 1998. 2(1). P. 5-30.

65. Forster H., Wascher G. (1997) Simulated annealing for order spread minimization sequencing cutting patterns // European Journal of Operational Research. 1998. 110. P. 272-281.

66. Garey M.R., Johnson D.S. Computers and Intractability: A guide to the Theory of NP-Completeness // San-Francisco, Freemau. 1979.

67. Gehring H., Bortfeld A. A Genetic Algorithm for Solving the Container Loading Problem// International transactions in operational research. 1997, V.4, №5/6. P.401-418.

68. Gilmore P., Gomory R. Multistage cutting stock problem of two and more dimensions//OperatRes. 1965. 13(1). P.94-120.

69. Gilmore P., Gomory R. The theory and computation of knapsack functions. // Oper. Res. 1966. V.14. P.1045-1075.

70. Gilmore P.C. and Gomory R.E. A Linear Programming Approach to the Cutting-stock Problem, Operations Research 9(1961), pp. 849-859.

71. Glover F. Tabu search and adaptive memory programming advances, applications and challenges // Interfaces in Computer Science and Operations Research. 1996. P. 1-75.

72. Glover F. and Laguna M. Tabu search. Kluwer Academic Publishers.1997.

73. Hopper E., Turton B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. // EJOR 128. 2001. P. 34-57.

74. Holland J.H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, The University of Michigan Press (1975), and MIT Press (1992).

75. Jhonson D.S., Demers A., Ullman J.D., Garey M.R., Graham R.L. Worst-case performance bounds for simple one-dimensional packing algorithms // SIAM J. Comput. V. 3. N4. 1974. P.299-325.

76. Kochetov Yu., Usmanova A. Probabilistic Tabu Search with Exponential Neighborhood for Bin Packing Problem // Proceedings MIC'2001, Porto, 2001. P. 619-624. Работа поддержана РФФИ: проект 01-01-00510.

77. Lirov Y., edit. Special issue: Geometric Resource Allocation // Mathematical and Computer Modelling. 1995. 16(1).

78. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. // European Journal of Operation Research. 1999. 112. P. 413-420.

79. Lodi A., Martello S., Vigo D. Recent advances on two-dimensional bin packing problems. // Discrete Applied Mathematics 123. 2002. P. 379 -396.

80. Loris Faina. An application of simulated annealing to the cutting stock problem // European Journal of Operational Research. 1999. 114. P. 532-556.

81. Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part I: One Dimensional Knapsack Problem. // INFOR. 1994. 32(3).

82. Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part II: Multidimensional Knapsack and Cutting Stock Problems // INFOR. 1994. 32(4).

83. Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementations. //YOHN WILEY&SONS. Chichester. 1990.

84. Martynov V. Geometrical objects regular placement onto a stock sheet or strip // Pesquisa Operacional, Vol. 19, No.2. SP - BRAZIL, Instituto Nacional de Pesquisas Espaciais, dezembro de 1999. P.211-222.

85. Morabito M. Arenales M. Staged and constrained two-dimensional guillotine cutting problems: an and/or-graph approach. // European Journal of Operational Research. 1996. 94. P.548-560.

86. Morabito R., Arenales M. An AND/OR graph approach to the container loading problem // International Transactions in Operational Research 1 (1994) 59-73.

87. Mukhacheva E., edit. Special issue: Decasion Making under Conditions of Uncertainty (Cutting-Packing Problems)/ The International Scientific Collection. 1997. Ufa. Russia.

88. Mukhacheva E.A., Zalgaller V.A. Linear Programming Cutting Problems // International Journal of Software Engineering and Knowledge Engineering. 1993. V. 3.N4. P. 463-476.

89. Murata H., Fujiyoshi K., Nakatane S. and Kajitani Y. Rectangle-Packing-Based Module Placement // Proc. IEEE/ACM International Conf. on Computer-Aided Design. 1995. P.472-479.

90. Scheithauer G. and Terno J. About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem. Oper. Res. Proc. 1991, Springer-Verlag, Berlin Heidelberg, 439-444.

91. Scheithauer G., Terno Y. Muller A., Belov G. Solveng one-dimensional cutting stock problems exactly with a cutting plane algorithm. // Journal of the Operational Research Society. 2001. 52. H. 1390-1401.

92. Schwerin P., Wascher G. The Bin-Packing Problem: a Problem Generator and Some Numerical Experiments with FFD Packing and MTP // International Transactions in Operational Research. 1997. 4. P.337-389.

93. Sergeyeva O.Y., Scheithauer G. and Terno J. The value correction method for packing of irregular shapes // Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa 1997. P. 261270.

94. Stutzle T., Hoos H.H. MAX-MIN Ant System // Preprint submitted to Elsiever Science, 1999.

95. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische Losung. Leipzig. 1987.

96. Valeyeva A.F., Agliullin M.N. Ant Colony Algorithm for the 2-D Bin-Packing Problem: Numerical Study // Proceedings of the 5th International Workshop on Computer Science and Information Technologies, 2003. P. 110-114.

97. Verhoturov M.A., Sergeyeva O.Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // Pesquisa Operacional. 2000. V. 20. N2. P. 233-247. Работа поддержана РФФИ, проект 99-01-00947.

98. Wang P., Valenzeva L. Data set generation for rectangular placement problems // European Journal of Operational Research. 2001. 134(2). P.378-391.

99. Wang P., Wascher G., edit, {it Special issue: Cutting Packing Problems} Europen Journal of Operational research. 141 (2002).

100. Yanasse H., edit. Special issue: Cutting and Packing Problems// Pesquisa Operacional. 1999. 19(2).