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

На правах рукописи

ФАЙЗРАХМАНОВ Ришат Илшатович

ОПТИМИЗАЦИЯ ПРОЦЕССА РАСКРОЯ ПРОМЫШЛЕННЫХ МАТЕРИАЛОВ ПО КРИТЕРИЮ МИНИМУМА МАТЕРИАЛЬНЫХ ПОТЕРЬ ПРИ НАЛИЧИИ ТЕХНОЛОГИЧЕСКИХ ОГРАНИЧЕНИЙ

Специальность 05.13.01 Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Уфа-2011

7 ДПР 2011

4842224

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

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

д-р техн. наук, доц. Асанов Асхат Замилович проф. каф. прикладной математики и информатики филиала ФГАОУ ВПО «Казанский (Приволжский) Федеральный университет» в г. Набережные Челны

канд. техн. наук

Сиразетдипов Тимур Маратович

гл. специалист ООО «РН-УфаНИПИнефть»

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

Защита диссертации состоится 29 апреля 2011 г. в 10 часов на заседании диссертационного совета Д-212.288.03 при Уфимском государственном авиационном техническом университете по адресу. 450000, Уфа-центр, ул. К. Маркса, 12

С диссертацией можно ознакомиться в научной библиотеке университета

Автореферат разослан «25» марта 2011 г.

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

Научный руководитель Официальные оппопеиты

8 с

В. В. Миронов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна результатов диссертационного исследования:

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

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

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

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

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

b) принцип «элитного муравья» для сохранения лучшего решения.

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

Практическую значимость имеют следующие результаты.

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

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

Апробирование результатов в виде методики повышения эффективности управления раскроем листового промышленного материала при производстве заготовок и рабочего прототипа программного обеспечения для оптимизации процесса раскроя на этапе технологической подготовки производства осуществлено на предприятии ХТЦ УАИ, Уфа. Применение разработанного программного обеспечения позволяет повысить эффективность использования материала на 6-8 %.

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

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

Работа выполнялась при частичной поддержке грантов Российского фонда фундаментальных исследований (РФФИ), проекты 09-07-09254-моб_з и 10-07-9 ИЗО-НШО-а, ИФ ВК 03 10 ХК.

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

Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах.

1. IV Республиканская студенческая научно-практическая конференция «Научное и экологическое обеспечение современных технологий», УГАЭС, Уфа, 2007;

2. Международной конференции "Компьютерные науки и информационные технологии" (CSIT), Уфа, 2007-2010;

3. Зимней школе для аспирантов и молодых ученых (Уфа, 2008— 2010);

4. I Всероссийской молодежной научной конференции "Молодежь и наука на севере", Сыктывкар, 2008;

5. IV Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009;

6. Российская конференция ""Дискретная оптимизация и исследование операций'" (DOOR-2010), Республика Алтай, 2010;

7. Международная конференция «Инновационные информационные технологии: Теория и Практика», Дрезден, 2010.

Публикации. По теме диссертации опубликовано 13 работ выполненных по теме диссертации при непосредственном участии автора: 9 статей, в том числе 2 в рецензируемом журнале ВАК и 7 статей в сборниках трудов конференции, 4 тезиса в сборниках конференций.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 139 страницах машинописного текста, кроме того содержит 61 рисунка и 13 таблиц. Библиографический список включает 112 наименования и занимает 9 страниц.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

(для фиксации материала), учет дефектных областей материала, учет направления волокон материала.

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

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

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

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

Приведен обзор задач раскроя промышленных материалов и методов их решения, которые представлены в работах отечественных и зарубежных авторов (JI. В. Канторович, В. А. Залгаллер, Э. А. Мухачева, И. В. Романовский, В. В. Мартынов, А. А. Петунин, В. М. Верхотуров, А. Ф. Валеева, Ю. А. Кочетов, G. Sheithauer, H. Dykhoff, S. Martello, P. Gilmore, R. Gomory, G. Washer, M. Garry, D. Johnson и другие.)

В результате анализа существующих методов решения задач раскроя и выявлении их недостатков была выбрана конструктивная метаэвристика «муравьиная колония» в связи с тем, что:

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

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

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

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

Исходная информация задач раскроя может быть задана наборами следующего вида - <W; L; пс; nr; Rc; Wr; Lr; D; A; a; <p; ô>, где

W, L - ширина и длина листового/рулонного материала (в случае рулонного материала L = оо);

пс, пг - количество круглых и прямоугольных предметов, соответственно;

Rc =(rie,r2c,...,ric,...,rn e) - вектор радиусов круглых заготовок, г,- - радиус г-ой круглой заготовки, i е 1с = (1,2,...,ис);

fVr =(wb.,w2l.,...,wjr.....w„rl.), Lr=(llr,l2r,...,ljn...,lnrr) - вектора ширин и

длин прямоугольных заготовок, w¡г, lir - ширина и длина j-й прямоугольной

заготовки соответственно, je.Jr = (1,2,...,иг);

£> - список дефектных (запретных для размещения заготовок) областей; А - необходимый суммарный припуск между заготовками; а - необходимый суммарный припуск между верхним/нижним сторонами промышленного материла и заготовкой;

(р - необходимый суммарный припуск между боковыми сторонами промышленного материала и заготовкой.

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

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

<ХС1УаКс> и <ХпУг,Кг>,

где Хс=(х1с,х2с,...,х^,...,хпсс), Уе=(у11!,у2с,...,у^,...,упсс) - векторы координат

круглых заготовок, (х1ау^) — координаты центра г-й круглой заготовки соответственно по оси Xи У; Хг=(х1г,х2г,...,хуг.....хЛгГ), Уг=(уъ,у2г,...,у;г,...,у„гг)

- векторы координат прямоугольных заготовок, (х^у^) - координаты верхнего левого угла _/-й прямоугольной заготовки по оси Хи У.

к,сеКс = {кхе,кгс,...,ки.,...,к„сс), к^еКг =(А|гД2Г,...ДУГ,...Д„ГГ) - номер листа

на котором размещена 1-я круглая и _/'-я прямоугольная заготовка, соответственно.

Пусть В = Ог \№с, где Вг = (¿¡г,¿1г.....- список дефектных областей, аппроксимируемых наборами прямоугольников ¡1тг, т = 1,?; Вс = (с1]с,с12с,-^!с,...,с1ес) - список дефектных областей, аппроксимируемых наборами кругов с15с, 5 = 1,^. Положение определяется набором <х^г,у1г,1*г,^гУтг >. где (х^., У^)- координаты верхнего левого угла дефектной области, мг- длина и ширина дефектной области, плтг- номер листа, который содержит дефектную область. Положение (15С определяется набором >> гДе У*с) ~ координаты центра дефектной области, - радиус дефектной области, п^с- номер листа, который содержит дефектную область.

Наборы элементов <Хс,УаКс> и <ХпУпКг>, называются допустимым раскроем, если выполнены следующие условия:

1) стороны прямоугольных заготовок параллельны сторонам листового или рулонного материала (условие ортогональности);

2) прямоугольные заготовки_/) не перекрывают друг друга и не выходят за границы раскраиваемого материала;

3) круглые заготовки / е 1С не перекрывают друг друга и не выходят за границы раскраиваемого материала;

4) круглые lelc и прямоугольные заготовки jeJr не перекрывают друг друга (формула (1));

[((*« + '/с + Л) ^ xjr) U (LxJr + lJr + Д) < (xk - ric)) U (Oy + v>jr + Д) <

<Jic - rk )) U (Cfc + ric + Д) < УJr)] U Kr(e < Xjr ) П Cfc < УJr ) n

n«xfc-Xjr)2 + -yjr)2 +A)2)]U[(^ + /,Г))П flöfc Sj>)n((*fc-J> -'/г)2 + (Лс-^г)2 ^fe + A)2)]U[(xfc <хуг)П (1) n>0>/r +"»n((*fc+ (Лс-WJr)2 ;>(rfc + Д)2)]и U[(*fc *{xJr +lJr))V\{yic z(yJr+wJr))n «Ä - xjr-ljr)2 + (yic - yJr -wJr)2 > {rlc + Д)2)]

5) круглые заготовки i e Ic и прямоугольные заготовки j e Jr не пересекаются с дефектными областями аппроксимированные кругами s е Dc и прямоугольниками meDr.

Требуется найти совокупность раскроев листов, минимизирующих их суммарное количество N.

Для размещения прямоугольных и круглых предметов разработан метод ABLP+, являющийся модификацией метода ABLP (М. Hifi, R. M'Hallah), создающего конечное множество позиций для размещения круглых предметов. Идея метода ABLP+ состоит в следующем: пусть имеется множество кругов Icel'c{jrc и множество прямоугольников Irel'r(jrr, где Гс - множество неразмещенных кругов, Гс - множество размещенных кругов, Гг -множество неразмещенных прямоугольников, Гг - множество размещенных прямоугольников. Первый компонент из множества Ic U/r в верхний левый угол области (пример для размещения круга приведен на рисунке 1, а; далее формируется список П допустимых позиций для размещения следующего компонента из множества /'СШ'Г и удаление из него тех позиций, которые не обеспечивают допустимое размещение; из сформированного списка позиций П выбирается самая верхняя левая позиция для добавления следующего предмета.

В методе ABLP+ формирование списка допустимых позиций происходит следующим образом:

1. Каждый круг Pi радиусом ric и координатами размещения (xic,yic), описывается кругом радиусом г-,с+А, который очерчивается горизонтальными и вертикальными линиями, позволяющими определить по четыре позиции для размещения следующего круга или прямоугольника. Пример формирования четырех позиций (xl.yl), (xl,yl), (xl,yl), (4г,у1) кругом Р, для размещения следующего прямоугольника Rk приведен на рисунке 1, Ъ.

2. Каждый размещенный прямоугольник Rk шириной w^ и длиной 4г, описывается прямоугольником шириной w^ + 2 х Д и длиной + 2 х Д, который очерчивается горизонтальными и вертикальными линиями, позволяющими определить по четыре позиции для размещения следующего круга

или прямоугольника. Пример формирования четырех позиций (,х)с,у)с), (*/с>У/с)> (х)с>у)с) прямоугольником Кк для размещения следующего круга Р;- приведен на рисунке 2.

(0,0)

■Я»

С*'*/*)

д,

(-Л^Л.) А

а) + Ь)

Рисунок 1 —Метод АВЬР*\ а — размещение круга в верхний левый угол области; Ъ — четыре позиции, образованные кругом Р, для размещения прямоугольника Л*

3. Углы области размещения образуют дополнительные позиции для размещения следующего предмета.

Рисунок 2 — Четыре позиции, образованные прямоугольником для размещения круга Р,

4. Два смежных круга Р, и Р: генерируют по две дополнительные позиции для размещения следующего круга Р) или прямоугольника Щ. Пример формирования двух позиций у}у) и (х2^,уг}г) для прямоугольника Щ приведен на рисунке 3, а.

5. Пара (Р, , Я^, где Р, - круг, Кк - прямоугольник, генерирует по две дополнительные позиции для размещения следующего круга Р, или прямо-

угольника Rj. Пример формирования двух позиций (х)с,у)с)и (xjc,y2jc) для размещения следующего круга Pj приведен на рисунке 3 ,Ъ

В третьей главе рассматриваются алгоритмы муравьиной колонии, их достоинства и недостатки. Для решения задачи оптимизации процесса раскроя промышленных материалов по критерию минимума материальных потерь при наличии технологических ограничений разработан алгоритм ACOGA, основанный на алгоритме муравьиной колонии с процедурами генетического алгоритма Р-АСО для решения задачи коммивояжера (М. Guntssch, М. Middendorf).

(0,0)_(0,0) Л'

a) b)

Рисунок 3 — Позиции, генерируемые парами размещенных предметов: а — позиции, генерируемые парой кругов для размещения прямоугольника R/, b — позиции, генерируемые парой круг и прямоугольник для размещения

прямоугольника Rj

Алгоритм ACOGA для решения задачи оптимизации процесса раскроя промышленных материалов при наличии дефектных областей

Вход'. W - ширина полосы; пс - количество кругов; пг - количество прямоугольников; w„ /,■ - ширина и длина j-го прямоугольника соответственно, г,-радиус /-го круга, i=l,2,,..,nr; j=l,2,...,nc, D=(d:,d2, ...,dj - список дефектных областей, одна из стратегий обновления популяции: Age (удаление самого старого решения из популяции), Quality (удаления решения с наихудшей целевой функцией) или Probability (удаление решения из популяции с некоторой вероятностью).

Выход: лучшее найденное решение (карта раскроя)

1. Инициализация параметров алгоритма: к - размерность популяции; т - количество агентов; а — коэффициент влияния феромона; /? - коэффициент

влияния эвристической информации; t-mit - начальное значение феромона (iферомон - численная характеристика предмета, показывающая насколько часто данный предмет входил в лучшие решения на предыдущих итерациях

алгоритма); rmax - максимальное значение феромона; р - коэффициент испарения феромона; размещение дефектных областей D=(d,,d2, —.dj.

2. Повторять, пока не выполнен критерий остановки:

2.1. Выбрать предмет из множества lc U1Г с некоторой вероятностью по формуле (2) и поместить его в верхний левый угол области при помощи метода ABLP*.

2.2. Дня каждого из m агентов, не завершивших построение решений, выполнить:

2.2.1.Выбрать следующий предмет из множества Îc{JJr с некоторой вероятностью, определяемой формулой (2).

2.2.2.Добавить выбранный компонент к частично построенному решению:

2.2.2.1. С помощью метода ABLP+ построить список позиций,

удовлетворяющий условиям допустимости 1) - 5);

2.2.2.2.Поместить компонент в лучшую позицию - верхнюю левую найденную позицию.

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

2.4. Если \Р\ = к, то удалить из популяции решение согласно выбранной стратегии обновления популяции:

2.4.1. Выполнить обновление феромона.

2.5. Добавить лучшее решение в популяцию Р:

2.5.1. Выполнить обновление феромона.

3. Выдать результат - лучшее найденное решение.

Параметры алгоритма а, Д Tinit, rmax - вещественные положительные числа.

= ^ р, (2)

где Ту - феромон, численная характеристика показывающая насколько часто фрагмент_/ размещался после фрагмента /;

7?; = {мр х /уг) х у + {я х Г]С) х (1 - у) - численная характеристика полезности предмета] для построения решения; если предмет ] е Jr;

у-

[0, если предмет j е 1С.

Обновление феромона происходит лишь для решений популяции: если решение добавляется в популяцию, к значению феромона добавляется величина в\ если решение удаляется из популяции, значение феромона уменьшается на величину 0. Величина в определяется по формуле (3):

где/faj - значение целевой функции лучшего найденного решения; Q - некоторая постоянная величина.

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

Численный эксперимент основан на сравнительном анализе полученных результатов с нижними и верхними границами, с известными рекордными решениями, полученными другими эвристическими алгоритмам. Он проведен на различных наборах тестовых примеров из международных библиотек OR-library и OR-Benchmark (http://www.laria.u-picardie.fr/hifi/OR-Benchmark/).

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

Эксперимент 1. Определение влияние параметров алгоритма на качество решений.

Работа алгоритма ACOGA проводилась на каждом примере при следующих параметрах: коэффиценты я и /? изменялись на интервале от 0,4 до 2-х с шагом 0,1; количество агентов т=12; размер популяции /с=10; начальное значение феромона г1га, =0,05.

Для задач размещения прямоугольников в полубесконечную область рассмотрены тестовые примеры из международной библиотеки OR-library. На рисунке 4, а приведены значения целевых функций при некоторых значениях коэффициентов a vi Рва. тестовых данных класса N1, содержащего пять примеров N11, N12, N13, N14, N15, в каждом из которых содержится по 17 прямоугольников.

Для задачи размещения кругов в полубесконечную область рассмотрены тестовые примеры, в которых радиусы кругов были случайно сгенерированы в интервале ric е [ОД х W,...,0,5 х IV], где ric - радиус i-го круга. На рисунке 4, b приведены значения целевых функций при некоторых значениях коэффициентов a и /? на тестовых данных класса С1, содержащего три примера С11, С12, С13, в каждом из которых содержится по 100 кругов.

Эксперимент 2. Решалась задача размещения кругов.

Эксперимент проводился на известных классах примеров SY1-SY6 (Е. Hopper). Для сравнения были также представлены решения задачи размещения кругов, полученные генетическим алгоритмом CAGA (М. Hifi, R. M'Hallah), методом ветвей и границ S. Y. (Y. G. Stoyan, G. N. Yaskov), жадной эвристической процедурой В1.5 (W. Q. Huang, Н. Akeb, Y. Li, С. М. Li),

алгоритмом вероятностного поиска с запретами TABU SEARCH (TS) (Ю. А. Кочетов, А. С. Руднев) и решениями, найденными с помощью коммерческого пакета GAMS (http://www.gams.com/)- В качестве оценки применялась нижняя граница оптимальной длины полубесконечной области LB,

is>

lb = —— (S¡ - площадь г-го круга, W - ширина полубесконечной облас-w

ти). В качестве критерия оценки выступает длина занятой части полубесконечной области L (рисунок 4).

■ о=1.8; &=0,6

■ 0=1,8;

■ 0=1,4; р=1

■ а=1.э; 'У .2

а) Ъ)

Рисунок 3 — Определение влияния параметров на качество решений: а — Класс N1; Ь — Класс С1

■ LB

В CAGA

■ S.Y. э В1.5

■ те

a GAMS

■ ACOGA

■ 0=1,6; fl=G.fc

;ао=1,2:р=1А |и о=о,7: p=i,e: ¡■0=2; ;

Рисунок 4 — Сравнение алгоритма ACOGA с алгоритмама CAGA, SY, В 1.5, TS

и пакетом GAMS

Эксперимент №3. Решалась задача одновременного размещения кругов и прямоугольников.

В эксперименте проводилось сравнение работы алгоритмов TS, ACOGA и коммерческого пакета GAMS (рисунок 5). ¿^-нижняя и L'5-верхняя оценки (А.С. Руднев); для алгоритмов TS, ACOGA приведены результаты работы ал-

горитмов.

При решении задач одновременного размещения кругов и прямоугольников в полубесконечную область алгоритму ACOGA удалось найти новые рекордные решения на классах задач: CR3P02\ CR5P01; CR5P02; CR5P03; CR6P03 (A.C. Руднев).

В результате проведения экспериментов на рассмотренных примерах было выявлено, что разработанные методы и алгоритмы позволяют повысить эффективность использования материала на 6-8% по сравнение с известными.

Рисунок 5 — Сравнение эффективности алгоритмов на задаче одновременного размещения кругов и прямоугольников

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

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

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

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

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

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

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

5. Разработан рабочий вариант программного обеспечения на основе предложенных методов, алгоритмов и математического обеспечения оптимизации процесса раскроя промышленных материалов по критерию минимума материальных потерь при наличии технологических ограничений. Анализ результатов численных экспериментов показал их эффективность. На его основе было выявлено, что разработанные методы и алгоритмы позволяют повысить эффективность использования материала на 6-8%. Для пяти примеров задачи размещения круглых и прямоугольных предметов в полубесконечную область получены новые улучшенные значения целевой функции.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ОПУБЛИКОВАНЫ В РАБОТАХ

В рецензируемых журналах из списка ВАК

1. Конструктивный вероятностный алгоритм для размещения кругов и прямоугольников / Р. И. Файзрахманов // Вестник УГАТУ: науч. журн. Уфимск. гос. авиац. техн. ун-та. 2010. Т. 14, № 4 (39). С. 132-138.

2. Применение конструктивной метаэвристики «Муравьиная колония» к задаче гильотинного прямоугольного раскроя / А. Ф.Валеева, А. А. Петунии, Р. И. Файзрахманов // Вестник БГУ: науч. журн. Башкирск. гос. ун-та. 2007. Т. 12, №3. С. 12-15.

В других изданиях

3. Применения алгоритма муравьиной колонии в задаче выбора пунктов измерения уровня загрязнения окружающей среды / А. Ф.Валеева, Р. И. Файзрахманов // Научное и экологическое обеспечение современных технологий: мат. IV Респ. студ. науч.-практ. конф. Уфа: УГАЭС, 2007. С. 5659.

4. Задача гильотинного прямоугольного раскроя на базе метаэвристики муравьиная колония / А. Ф. Валеева, Р. И. Файзрахманов // Компьютерные науки и информационные технологии С81Т'2007: 9-я Междунар. конф. Уфа: УГАТУ, 2007. Т. 2. С. 234-236. (Статья на англ. яз.).

5. Применение метаэвристики муравьиной колонии к задаче двумерной упаковки / А. Ф. Валеева, Р. И. Файзрахманов // Актуальные проблемы науки и техники: мат. 3-й Всерос. зимн. шк.-сем. аспирантов и молодых ученых. Уфа: УГАТУ, 2008. С. 98-104.

6. Применение метаэвристики муравьиная колония к задачам раскроя / Р. И. Файзрахманов // Компьютерные науки и информационные технологии С81Т'2008: 10-я Междунар. конф. Уфа: УГАТУ, 2008. Т. 3. С. 79-80 (Статья на англ. яз.).

7. Решение задачи прямоугольного раскроя на базе алгоритма муравьиной колонии / Р. И. Файзрахманов // Молодежь и наука на севере: матер. I Всерос. молодежи, науч. конф. Сыктывкар: Изд. Коми науч. центра УрО РАН, 2008. Т. I. С. 67-68.

8. Решение задачи упаковки прямоугольников и кругов на базе алгоритма муравьиной колонии / А. Ф. Валеева, Р. И. Файзрахманов // Проблемы оптимизации и экономические приложения: матер. IV Всерос. конф. Омск: Полиграфический центр КАН, 2009. С. 115.

9. Применение метаэвристики «Муравьиная колония» к задаче упаковки / А. Ф. Валеева, Р. И. Файзрахманов // Актуальные проблемы науки и техники: матер. 4-й Всерос. зимн. шк.-сем. аспирантов и молодых ученых. Уфа: УГАТУ, 2009. Т. 1. Информатика, управление и компьютерные науки. С. 456-459.

10. Применение конструктивного алгоритма муравьиной колонии к задаче упаковки кругов и прямоугольников в полосу / Р.И. Файзрахманов // Компьютерные науки и информационные технологии С81Т'2009: 11-я междунар. конф. Уфа: УГАТУ, 2009. Т. 2. С. 67-69. (Статья на англ. яз.).

11. Вероятностный алгоритм муравьиной колонии для задачи упаковки кругов и прямоугольников / А. Ф. Валеева, Р. И. Файзрахманов // Применение информационных технологий и математических методов в экономике: матер, междунар. конф. Уфа: УГАТУ, 2010. С. 121-129. (Статья на английском языке).

12. Конструктивный вероятностный алгоритм муравьиной колонии для задачи упаковки кругов и прямоугольников / Р. И. Файзрахманов // Компьютерные науки и информационные технологии С81Т'2010: 12-я междунар. конф. Уфа: УГАТУ, 2010. Т. 3. С. 90-92. (Статья на англ. яз.).

13. Решение задачи упаковки кругов и прямоугольников на базе алгоритма муравьиной колонии / А. Ф. Валеева, Р. И. Файзрахманов // Инновационные технологии - теория и практика: матер, междунар. конф. Германия, Дрезден, 2010. С. 41-45. (Статья на англ. яз.).

Диссертант

Р. И. Файзрахманов

ФАЙЗРАХМЛНОВ Ришат Илшатович

ОПТИМИЗАЦИЯ ПРОЦЕССА РАСКРОЯ ПРОМЫШЛЕННЫХ МАТЕРИАЛОВ ПО КРИТЕРИЮ МИНИМУМА МАТЕРИАЛЬНЫХ ПОТЕРЬ ПРИ НАЛИЧИИ ТЕХНОЛОГИЧЕСКИХ ОГРАНИЧЕНИЙ

Специальность 05.13.01 Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

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

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

Оглавление.

Введение.

1 Анализ проблемы процесса раскроя промышленного материала по критерию минимизации потерь с учетом технологических ограничений.

1.1 Актуальность исследуемой проблемы.

1.2 Анализ существующих технологий раскройно-заготовительных работ

1.3 Классификация и анализ методов решения задач раскроя.

1.4 Цель и задачи исследования.

Выводы по первой главе.

2 Модели и методы решения задач раскроя промышленного материала при наличии технологических ограничений и методы ее решения.

2.1 Математические модели задач раскроя.

2.2 Методы решения задач раскроя промышленных материалов с учетом технологических ограничений.

2.3 Пример работы процедуры размещения.

Выводы по второй главе.

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

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

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

3.3 Пример работы алгоритма муравьиной колонии, основанной на популяции

Выводы по третьей главе.

Глава 4. Оценка эффективности алгоритмов и методов оптимизации процесса раскроя при наличии технологических ограничений на базе численных экспериментов.

4.1 Программное обеспечение для задачи оптимизации процесса раскроя промышленных материалов.

4.2. Определение влияния параметров алгоритма на качество решений.

4.3 Исследование эффективности предложенных методов и алгоритмов.

Выводы по четвертой главе.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна результатов диссертационного исследования:

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

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

3. Модифицированный алгоритм муравьиной колонии, основанный на процедурах генетического алгоритма и осуществляющий обмен информацией о построенных картах раскроя, для решения задачи раскроя листового и рулонного материалов на заготовки различных геометрических форм при наличии технологических ограничений характерных для реального производства, который использует: a) интервальное ограничение для параметра, показывающего частоту выбора фрагмента решения во избежания ранней стагнации; b) принцип «элитного муравья» для сохранения лучшего решения.

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

Практическую значимость имеют следующие результаты.

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

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

Апробирование результатов в виде методики повышения эффективности управления раскроем листового промышленного материала при производстве заготовок и рабочего прототипа программного обеспечения для оптимизации процесса раскроя на этапе технологической подготовки производства осуществлено на предприятии ХТЦ УАИ, Уфа. Применение разработанного программного обеспечения позволяет повысить эффективность использования материала на 6-8%.

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

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

Работа выполнялась при частичной поддержке грантов Российского фонда фундаментальных исследований (РФФИ), проекты 09-07-09254-мобз и 10-07-91 ЗЗО-ННиО-а, ИФ ВК 03 10 ХК.

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

Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах.

1. IV Республиканская студенческая научно-практическая конференция «Научное и экологическое обеспечение современных технологий», УГАЭС, Уфа, 2007;

2. Международная конференция "Компьютерные науки и информационные технологии" (С81Т), Уфа, 2007-2010;

3. Зимняя школа для аспирантов и молодых ученых, Уфа, 2008-2010;

4. I Всероссийская молодежная научная конференция "Молодежь и наука на севере", Сыктывкар, 2008;

5. IV Всероссийская конференция "Проблемы оптимизации и экономические приложения", Омск, 2009;

6. Российская конференция "Дискретная оптимизация и исследование операций"' (00011-2010), Республика Алтай, 2010;

7. Международная конференция «Инновационные информационные технологии: Теория и Практика», Дрезден, 2010.

Публикации. По теме диссертации опубликовано 13 работ выполненных по теме диссертации при непосредственном участии автора: 9 статей, в том 8 числе 2 в рецензируемом журнале ВАК и 7 статей в сборниках трудов конференции, 4 тезиса в сборниках конференций.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 139 страницах машинописного текста, кроме того содержит 61 рисунок и 13 таблиц. Библиографический список включает 112 наименования и занимает 9 страниц.

Выводы по четвертой главе

1. Разработано программное обеспечение для решения задачи оптимизации процесса раскроя промышленных материалов по критерию минимума материальных потерь. В программном обеспечении реализованы: a) метод размещение круглых и прямоугольных предметов в заданную область АВЬР+\ b) предложенный алгоритм АСОЭА для решения поставленной задачи.

2. Проведенный численный эксперимент по оценке влияние параметров алгоритма на целевую функцию показал: a) не существует оптимальных параметров для всех классов задач. Выбор параметров зависит от размерности задачи, типа раскраиваемых заготовок и величины разброса размеров заготовок; b) для задач малой размерности и с большим разбросом размеров заготовок существенное влияние на качество получаемого решения оказывает коэффициент влияния эвристической информации. В этом случае рекомендуется принимать значение коэффициента влияния эвристической информации в 2 раза больше коэффициента влияния уровня феромона; I c) для задач большой размерности, в которых разброс размеров заготовок относительно мал, существенное влияние на качество получаемого решения оказывает коэффициент влияния уровня феромона. В этом случае рекомендуется принимать значение коэффициента влияния уровня феромона больше коэффициента влияния уровня эвристической информации.

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

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

5. Проведенные эксперименты на реальных данных показали, что разработанные методы и алгоритмы позволяют повысить эффективность использования материала на 6-8%.

Заключение

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

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

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

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

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

5. Разработан рабочий вариант программного обеспечения на основе предложенных методов, алгоритмов и математического обеспечения оптимизации процесса раскроя промышленных материалов по критерию минимума материальных потерь при наличии технологических ограничений. Анализ результатов численных экспериментов показал их эффективность. На его основе было выявлено, что разработанные методы и алгоритмы позволяют повысить эффективность использования материала на 6-8%. Для пяти примеров задачи размещения круглых и прямоугольных предметов в полубесконечную область получены новые улучшенные значения целевой функции.

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

2. Батищев Д.Ю. Генетические алгоритмы решения экстремальных задач II учебное пособие под ред. Я.Е.Львовича. Воронеж: Воронежский гос. техн. ун-т; Нижегородский ун-т. — 1995. - 96 с.

3. Валеева А.Ф., Аглиуллин М.Н. Алгоритм муравьиной колонии для задач двухмерной упаковки: результаты вычислительного эксперимента II Труды XIII Байкальской международной школы-семинара. Иркутск, Байкал. -2005. - Т.1. - С. 429-434.

4. Валеева А.Ф., Файзрахманов Р.И. Применение конструктивной метаэвристики «Муравьиная колония» к задаче гильотинного прямоугольногораскроя II Вестник Башкирского государственного университета. Уфа:Бгу -2007.-Т. 12, №3,-с. 12-15.

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

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

7. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи.- М.: Мир. 1982. - 416 с.

8. Ермаченко А.И., Сиразетдинов Т.М. Метод поиска с запретами для решения задач прямоугольного гильотинного раскроя. II Дискретный анализ и исследование операций: сб. трудов всерос. конф. Новосибирск: НГТУ. - 2002. -с. 230.

9. Канторович JI.B., Заллгаллер В.А. Расчет рационального раскроя материалов — С.-П.: Лениздат. — 1951.

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

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

12. Леванова Т.В., Лореш М.А. Алгоритмы муравьиной колонии и имитации отжига для задачи о р-медиане II Автоматика и телемеханика. № 3.-2004.-с. 80-88.

13. Лореш М.А. Алгоритмы муравьиной колонии для простейшей задачи размещения: Препринт. Омск: ОмГУ. - 2006. — 19 с.

14. Мухачева Э.А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки II Дискретный анализ и исследование операций': Материалы российской конференции. Новосибирск. -2002г.-с. 80-87.

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

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

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

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

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

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

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

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

23. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. И Информационные технологии. — 1999г. — №1, С. 27.

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

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

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

27. Руднев A.C. Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу II Дискретный анализ и исследование операций.-2009.-Т. 16 -No. 4.-е. 61 -86.

28. Руднев A.C. Задачи двумерной прямоугольной упаковки в контейнеры с запрещенными областями II Магистерская диссертация. — 2006. — 120с.

29. Скобцов Ю. А. К вопросу о применении метаэвристик в решении задач рационального раскроя и упаковки II Вюник Хмельницького нацюнального ушверситету. — 2008. — Т. 1, № 4. — с. 205—217.

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

31. Файзрахманов Р.И. Конструктивный вероятностный алгоритм для размещения кругов и прямоугольников II Вестник Уфимского государственного авиационного технического университета. Уфа: УГАТУ. — 2010. — Т. 14, №4 (39).-с. 132-138.

32. Adamovicn A., Albano A. Nesting two-dimensional shapes in rectangular Modules II Comput. Aeded Design. 1976. - 8(1). - P.27-33.

33. Aurts E., Lenstra J., edit. Local Search in Combinatorial Optimization. II John Wiley&Sons. 1996. - p. 10-15.

34. Baker B.S., Goffman Jr. E.G., Riverst R.L. Orthogonal packing in two dimensions II SIAM J. Comput. 9 - 1980 - P.846-855.

35. Belov G., Scheithauer G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths II European Journal of Operational Research. 2002. - 141. - p. 274-294.

36. Bischoff E., Wascher G., edit. Special issue: Cutting and Packing II European Journal of Operational Research. 1995. - p. 84.

37. Bonabeau E., Dorigo M., Theraulaz G. From Natural to Artificial Swarm Intelligence II Oxford University Press. 1999.

38. Boschetti M.A. The Two-Dimensional Finite Bin Packing Problem II Quaterly Journal of the Belgian, French and Italian Operations Research Societies 2002.-p. 45-51.

39. Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison II ACM Computing Surveys. 35(3) -2003 — p. 268-308.

40. Burke E., Kendall G. Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem. II Accepted for the 1999 International Conference on Artificial Intelligence, Monte Carlo resort. Las Vegas. Nevada. USA. 1999. - P. 34-35.

41. Chung F.K.R., Garey M.R., Johnson D.S. On packing two-dimensional bins II SIAM J. Algebraic Discrete Meth. 3 (1982) - p. 66-76.134

42. Dorigo M. Optimization, Learning and Natural Algorithms // PhD thesis, Dipartimento di Electrónica, Politécnico di Milano, IT. 1992 (in Italian).

43. Dorigo M., Di Caro G., Gambardella L.M. Ant Algorithms for Discrete Optimization II Artificial Life, 1999. V.5(2). - P.137-172.

44. Dorigo M., Gambardella L.M. Ant Colonies for the traveling salesman problem. II IRIDIA, Technical Report 1996. P. 3.

45. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem II IEEE Transactions on Evolutionary Computation, 1(1). 1997. - p. 53-66.

46. Dorigo M., Maniezzo V., Colorny A. Ant System: An Autocatalytic Optimizing Process //Report1 TR-91-016. Milan: Politécnico di Milano, 1991.

47. Dorigo M., Maniezzo V., Colorny A. The Ant system: Optimization by a colony of cooperating agents II IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), 1996. P. 29-41.

48. Dorigo M., Stutzle T. Ant Colony Optimization //MIT Press. 2004.

49. Dykhoff H. A typology of cutting and packing problems I I Evropean Journal of Operational research. 1990. Vol. 44. - p. 145-159.

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

51. 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.

52. Folkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing II Journal of Heuristics. 1998. - 2(1). - p. 5-30.

53. 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.

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

55. Garey M.R., Johnson D.S. Computers and Intractability: A guide to the Theory of NP-Completeness II San-Francisco, Freemau. 1979. - p. 321-338.

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

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

58. Gilmore P.C., Gomory R.E. A Linear Programming Approach to the Cutting-stock Problem II Operations Research 9(1961). — p. 849-859.

59. Glover F. Tabu search and adaptive memory programming advances, applications and challenges. II Interfaces in Computer Science and Operations Research. 1996. - p. 1-75.

60. Hifi M., M'Hallah R. A dynamic adaptive local search algorithm for the circular packing problem II European Journal of Operational Research №183(2007) -p. 1280-1294.

61. Hifi M., M'Hallah R. Approximate algorithms for constrained circular cutting problems II Computers & Opertations Research- 31(2004) p. 675-694.

62. Hifi M., M'Hallah R. A hybrid algorithm for the two-dimensional layout problem: the cases of regular and irregular shapes. //International Transaction in Operational Research. 2003. - №10. - p. 195-216

63. Hopper E., Turtun B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem //EJOR. — 2001. — №128. P. 34-57.136

64. Huang W. Q., Li Y., Aked H., Li. C. M. Greedy algorithms for packing unequal circles into a rectangular container II European Journal of Operational Research. 2005. - №56. - P.539-548.

65. Imahori S., Yaguira M., Ibaraki T. Local Search Heuristics for the Rectangle Packing Problem With General Spatial Costs // MIC'2001 — 4th Metaheuristics International conference. — P. 471-476

66. Kallrath. Cutting circles and polygons from area-minimizing rectangles. //Journal of Global Optimization. 2009. - №43. - P. 299-328.

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

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

69. Lodi A., Martello S., Vigo D. Heuristic algorithms for the three-dimensional bin packing problem II European Journal of Operational Research. — 2002.- 141.-P. 410-420.

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

71. Lin S. Computer solutions of the traveling salesman problem II Bell System Journal. 1965. - V. 44 -P. 2245-2269.

72. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. II European Journal of Operation Research. — 1999. -112.-p. 413-420.

73. Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part I: One Dimensional Knapsack Problem. IIINFOR. 1994. - 32(3).

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

75. 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.

76. Morabito M., Arenales M. An AND/OR graph approach to the container loading problem II International Transactions in Operational Research 1 (1994) 5973.

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

78. Sakanushi К., Kajitani Y. The Quarter-State (Q-sequence) to Represent the Floorplan and Applications to Layout optimization // IEEE Asia Pasific Conference on Circuits and systems. 2000. - p. 829-832.

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

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

81. Sergeyeva O.Y., Scheithauer G. and Terno J. The value correction method for packing of irregular shapes II Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa- 1997. - p. 261-270.

82. Stoyan Y.G., Yaskov G.N. A mathematical model and solution for the problem of placing various-sized into a strip //European Journal of Operational Research. 2004. - №156. - P.590-600.

83. Stoyan Y.G., Yaskov G.N. Mathematical model and solution of optimization problem of placement of rectangles and circles taking into accountspecial constraints II International Transaction in Operational Research. 1998, №5(1). - p.45-57.

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

85. Terao J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische Losung. Leipzig. — 1987.

86. Yanasse H., edit. Special issue: Cutting and Packing Problems!I Pesquisa Operacional. 1999. - 19(2).

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