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

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

СИРАЗЕТДИНОВА Татьяна Юрьевн

----- хи5

КОНСТРУИРОВАНИЕ ПРЯМОУГОЛЬНОГО РАСКРОЯ В СИСТЕМАХ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ С УЧЕТОМ ДЕФЕКТНЫХ ОБЛАСТЕЙ МАТЕРИАЛА

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

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

Уфа 2007

003056105

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

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

Ведущая организация

канд.техн.наук, доц. Валеева Аида Фаритовна

д-р техн. наук, проф. Мартынов Виталий Владимирович канд. техн. наук, доц. Григорчук Татьяна Ивановна

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

Защита состсмтсяыт&'с-р&б^ 2007 г. в (О часов на заседании диссертационного совета Д-212.288.03 при Уфимском государственном авиационном техническом университете по адресу: 450000, Уфа- центр, ул. К. Маркса 12, УГАТУ.

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

Автореферат разослан^ 2 2007 г.

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

В.В. Миронов

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

1. Декодер «вставки», разработанный для реализации технологических ограничений и обхода дефектных областей раскраиваемого материала.

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

3. Программная реализация разработанных методов в составе системы прямоугольного раскроя 2Б11-СиТ.

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

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

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

2 Предложен метод «холодного» отжига, основанный на принципах метаэвристики «имитация отжига», который в отличие от последней:

- работает с постоянным параметром температуры;

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

- использует новые способы расчета элементов вектора достижимости.

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

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

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

Разработанное программное обеспечение, реализующее методы и алгоритмы расчета прямоугольного раскроя листового и рулонного материала с учетом технологических ограничений, в качестве подсистемы для решения задач прямоугольного раскроя интегрировано в известную систему автоматизированного проектирования «Сириус», внедренную на следующих предприятиях. ООО «Центр автоматизации проектирования и высоких технологий» (г. Екатеринбург), ЗАО «Курганстальмост» (г. Курган), ОАО «Мечел» (г. Челябинск). Применение разработанного программного обеспечения позволило повысить эффективность использования материала на 5-8%.

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

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

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

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

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

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

• Международной уфимской зимней школе-конференции по математике (Уфа, 2005);

• III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2006);

• Зимней школе для аспирантов и молодых ученых (Уфа, 2006, 2007);

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

По теме диссертации опубликовано 7 работ, в том числе 1 в рецензируемом журнале из списка ВАК.

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

СТРУКТУРА РАБОТЫ

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

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

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

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

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

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

3. Подсистема постпроцессорной обработки информации о размещенных геометрических объектах.

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

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

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

параллельные кромкам материала) и негильотинного раскроя, которые, в свою очередь, разделяются на задачи раскроя полосы и задачи раскроя листов.

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

наборами следующего вида: для задачи раскроя полосы - <Ш; п; I; у;

для задачи раскроя листов - <(¥, I, п; и>, /, у, г,,В>), где IV- ширина полосы или

листа; Ь - длина листа; п - количество прямоугольников; ы = (ы/, и^,...,и>„....м^,

IV, - ширина прямоугольника; I - (I,, I, - длина прямоугольника /',

1 = I, я; у - признак гильотинности; е - признак возможности поворота

прямоугольников. Вводится прямоугольная система координат: оси Ох и Оу

совпадают со сторонами полосы (листа). Решение задачи представляется в виде

набора элементов <Х, У>, гдеX = (х/, х2, ..., х„), У = {у,,у2, ...,у„) - векторы

координат прямоугольников. Положение /'-го прямоугольника зададим

координатами нижней левой точки прямоугольника (х,\у,). Пусть

В=(й,42, -4т, ...4) - список дефектных областей, т = 1,г. Дефектные области йт

аппроксимируются наборами прямоугольников 77, на этапе подготовки исходной к

информации, ¿„=иЯ(1 положение П1 определяется набором <х'р у'р 1'р

/=I

(если решается задача раскроя полосы) и набором <х), у), Гр ы'р п)> (если решается задача раскроя листов), где х'р у) - координаты нижнего левого угла дефектной области, I), - длина и ширина дефектной области, п) - номер листа, который содержит дефектную область.

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

если:

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

- прямоугольники не перекрывают друг друга;

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

- выполняется условие гильотинности (если решается задача гильотинного раскроя);

- прямоугольники не пересекаются с дефектными областями Уг'.у" л'=1,...,л, ] = \,.,к или {у, >/,+и>,) v(/y>y,+w,).

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

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

преобразующие полученную кодировку в карту раскроя. Был рассмотрен класс метаэвристических алгоритмов и выбран подкласс эволюционных алгоритмов, а именно: метод «имитация отжига» и наивный эволюционный алгоритм (1+1)-ЕА. Качество полученного решения зависит не только от выбранного метода расчета раскроя и схемы кодирования, но и от алгоритмов декодирования карт раскроя. В связи с этим возникает необходимость в разработке декодера, позволяющего учитывать технологические ограничения, возникающие в реальном производстве, а также условие непересечения прямоугольников с дефектными областями материала.

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

Разработан метод «холодного» отжига (Cold Annealing, СА) для решения задач раскроя полосы и листов на базе процедур известной метаэвристики «имитация отжига». Основное отличие предлагаемого алгоритма состоит в том, что вводится фиксированный параметр температуры. Приведем общую схему алгоритма С А:

1. Задать параметр щ (аналог температуры)

2. <7о Генерировать начальное состояние (решение)

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

3.1 Выбрать следующее текущее состояние q

3.2 Выбрать случайным образом тип окрестности N(<7)

3.2.1 Генерировать состояния окрестности N{g)

3.2.2 Для каждого состояния окрестности N(<?) повторять

3 2.2.1 Вычислить значения оценочной функции для каждого состояния окрестности N(<7)

3.2.2.2 Определить векторы генерации G, достижимости А, переходов Р

3.2.3 Выполнить переход в одно из состояний окрестности N(^) в зависимости от вектора перехода Р.

Для генерации начального состояния используется однопроходная эвристика. На каждом шаге алгоритма СА случайным образом осуществляется выбор текущего состояния q из окрестности N(g). Важную роль в задачах раскроя играет способ кодирования решений. В алгоритме СА для кодировки состояний

предлагается структура данных (код), представляющая собой вектор V = (vfl, v,.....

v,,./), элементы которого v, = <b„ r„ р,>, где Ь, - номер прямоугольника; г, - флаг поворота детали (0 - без поворота, 1 - с поворотом на 90°); р, - число, позволяющее выбрать координаты размещения прямоугольника на полосе или

листе. В алгоритмах локального поиска качество получаемого решения в значительной степени зависит от выбора окрестности. В алгоритме С А предлагается несколько типов окрестностей, которые различаются по типу и мощности. Для получения различных типов окрестности N(<7) используются следующие операции над кодом:

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

- перемещение элемента вектора У;

- изменение флага поворота г, в V;

- изменение числа р,.

По мощности окрестности разделяются на три типа: «малая» - количество модификаций в кодировке к = 1 Л0\ «средняя» - количество модификаций равно количеству прямоугольников и; «большая» - количество модификаций равно п. Существенное значение при расчете прямоугольного раскроя имеет декодер, который для каждого кодированного состояния позволяет восстановить карту раскроя и вычислить оценочную функцию Р(д). В отличие от известной схемы «имитация отжига» в алгоритме СА используются: оценочная функция

= где Б(д) - площадь использованного материала для состояния д\

вектор генерации О = (ОрС/.,,...^,), где I - это количество элементов в окрестности,

у, если е

О, иначе , где - окрестность состояния <7;

ненормированный вектор достижимости л, элементы которого ~е -

-е =(л(д)/5(д;)) 1 , где др д - состояния, лг0 - параметр алгоритма

(аналог температуры); ненормированный вектор переходов Р с элементами

р

которые нормируются по формуле Р] = — Элементы

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

В работе также реализован алгоритм решения задач раскроя на базе метаэвристики (1+1)-ЕА, являющейся аналогом алгоритма «имитация отжига» с нулевой температурой. Основная идея этого алгоритма состоит в том, что на каждой итерации строится окрестность, содержащая только одно состояние.

В настоящее время для решения задач прямоугольного раскроя/упаковки известны различные декодеры: в Европе популярен «усовершенствованный нижний левый» и его различные модификации, в школе под руководством Э.А. Мухачевой разработаны декодеры на базе блочных структур и послойной технологии, однопроходные эвристики; в Японии разработаны алгоритмы на базе

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

В работе предложен новый унифицированный декодер «вставки» (Priority Rotate Place, PRP), позволяющий, в отличие от перечисленных, восстановить карту раскроя при решении различных задач раскроя/упаковки с учетом технологических ограничений, а также осуществить обход дефектных областей материала. Декодер PRP позволяет получить BL-компактную карту раскроя (BL-компактная карта раскроя - это карта, в которой ни один прямоугольник не может быть сдвинут вниз или влево) и работает со свободными областями. Под свободной областью понимается прямоугольный участок полосы (или листа), который является максимальным при условии, что он не пересекается с уже уложенными прямоугольниками и границами материала, ограничен слева, сверху и снизу уложенными прямоугольниками или краями материала.

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

- получение списка точек М~{Мп (ха;уо,), Mt (ху ¡,),..., Mk.i (xL.hyk.h)}, куда прямоугольник Ъ, с учетом флага поворота г, может быть уложен (рис. 1). Для примера, изображенного на рис. 1 ,к - 4;

- выбор точки МлпаЩ и укладка прямоугольника Ь, без поворота, если г, --= 0, иначе с поворотом, в точку с координатами ( то[1|Д)|; уmod|M|).

Получение списка точек свободных областей

1. Вся полоса (лист) представляет собой свободную область. Область с координатами нижнего левого угла Мо(0;0) является единственной для укладки прямоугольника.

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

X

Рисунок 1 - Укладка прямоугольника декодером PRP

областей, то координаты ее нижнего левого угла добавляются в список точек М={Мп, М/, ... Мк.]}, в противном случае, данная область удаляется из списка свободных областей для укладки текущего прямоугольника (рис. 2, в).

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

Пример карты раскроя приведен на рис. 2, д.

ч ч / / _ _ - - ,

що.у,) 1

Ма(0;уд ЩхьУк 1

2

Рисунок 2 -Схема получения списка точек

а - размещение прямоугольника №1; 6 — размещение прямоугольника №2; в - размещение прямоугольника №3; г - размещение прямоугольника №4; д — пример карты раскроя

Схема работы декодера «вставки» РИР

1. Инициализация. Вся полоса (лист) - свободная область

2. Для всех элементов вектора V выполнять 2.1 - 2.4

2.1 Выбор первого элемента вектора К (прямоугольника)

2.2 Построение списка свободных областей, куда прямоугольник может быть уложен

2.2.1 Выбор первой свободной области из списка свободных областей

2.2.2 Пока список свободных областей не пуст, выполнять 2.2.2.12.2.2.3

2.2.2.1 Если элемент v, помещается в свободную область, то добавить координаты (х; у) нижнего левого угла свободной области в список точек М={Мо, М},..., М^}

2.2.2.2 Выбор следующей свободной области

2 2.2.3 Если решается задача раскроя на листы и свободных областей больше нет, то берется новый лист

2.3 Укладка элемента v, в область, определяемую точкойр,

2.4 Переход к следующему элементу вектора V

Пример работы декодера при наличии дефектных областей

Дана полоса ширины = 8, количество прямоугольников п - 4 с размерами IV = (2; 4, 4; 3), I = (б, 4; 1, 4). Вектор V = (<4,1,3>,<2,0,4>,<3,0,6>,<1,],5>). Построить карту раскроя.

1. Укладка области d| с дефектом (рис. 3, а).

М0

, _ L _

' J4

Mo

м.

Mo

2 3

м2

3 d 4 з| с 1

М,

I

Mo

Рисунок 3 - Пример получения карты раскроя а - размещение области с дефектом; б - выбор размещения прямоугольника № 1; в - размещение прямоугольника №2; г - размещение прямоугольника №3; д - размещение прямоуголькика№4; е - полученная карта раскроя

2. Укладка прямоугольника, характеризуемого элементом v0 = <4,1,3>. Это прямоугольник №4, который должен быть уложен с поворотом. Список точек М = (Щ0,3), Mi(2,0)}. Выбирается точка М3 mo<j |Mi, т.е. выбирается точка Мп, и прямоугольник укладывается с поворотом с координатами нижнего левого угла прямоугольника (0;3) (рис. 3,6).

3. Укладка прямоугольника, характеризуемого элементом v; = <2,0,4>. Это прямоугольник №2, который должен быть уложен без поворота. Список точек М= {Mo(0,4),Mi(5,0)}. Выбирается точка М4 mod щ, т.е. выбирается точка М0, и прямоугольник укладывается без поворота с координатами угла (0;4) (рис. 3,в)

4. Укладка прямоугольника, характеризуемого элементом V/ = <3,0,б>. Это прямоугольник №3, который должен быть уложен без поворота Список точек М = {М„(0,0), М,(5;0), М2(4;4)}. Выбирается точка Мь го0(| |д/|, т.е. выбирается точка Мп, и прямоугольник укладывается без поворота с координатами угла (0; 0) (рис. 3,г).

5. Укладка прямоугольника, характеризуемого элементом V; = <1,1,5>. Это прямоугольник №1, который должен быть уложен с поворотом. Список точек М={М/>(5,0) }. Выбирается точка М4 то<1 т.е. выбирается точка М0, и прямоугольник укладывается с поворотом с координатами угла (5; 0) (рис. 3,Э).

Полученная карта раскроя изображена на рисунке 3 ,е.

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

Рисунок 4 - Схема САПР раскроя-упаковки

Основные подсистемы САПР раскроя-упаковки представлены на рис. 4. Серым цветом выделена подсистема, включающая разработанное программное обеспечение. Оно может быть интегрировано в систему автоматизированного проектирования (CAD/CAM систему).

Разработанные алгоритмы расчета прямоугольного раскроя представлены в виде динамически подключаемых библиотек (DLL), но интеграция этих алгоритмов в CAD/CAM систему требует соответствия внутренних форматов данных. В связи с этим предусмотрен вариант с использованием исполняемого модуля, на вход которого подается текстовый файл задания, а на выходе формируется текстовый файл результата - карты раскроя (рис. 5). Этот исполняемый модуль использует расчетные алгоритмы в виде DLL, передавая задания на расчет карт раскроя и получая результат в виде списка координат размещения прямоугольных заготовок.

Рисунок 5 - Интеграция разработанного программного обеспечения в

САПР

Разработанное программное обеспечение для расчета прямоугольного раскроя листового и рулонного материала с учетом технологических ограничений интегрировано в систему автоматизированного проектирования «Сириус».

В четвертой главе описаны результаты численных экспериментов. В численном эксперименте рассматривались различные классы задач раскроя рулонного материала. Было рассмотрено четыре класса различных прямоугольников: «большие» В (/e[0,4fF;0,5^F], w е[0,4W]0,5W]); «малые» S ( / е [0,02W;0,W], w е [0,02W;0,IW]); «длинные» L (/e[0,(W;(W], w£[0,4w-0,5w)) и (/е[0,4Ж;0,5Ж], и>е[О,0Ж;0,1Ж]); «триплеты» Т (/ е [0,3W;0,35W], w e[0,3W;0,35W]). В работе проведена серия численных экспериментов. В качестве критерия получаемых решений использовался коэффициент раскроя (КРа), который вычисляется следующим образом:

2>,ч 2>,ч

КРа = - 100% для полосы и КРа = —--100% для листов, где L - длина

W V W-L-N

занятой части полосы, W — ширина полосы или листа, L - длина листа, N —

количество листов, w„ /, - размеры прямоугольников

Серия 1. Исследовалась зависимость коэффициента раскроя, получаемого методом «холодного» отжига от контрольного параметра. Решалась задача на полосу (рис. 5, а). Параметры алгоритма: и0= {1, 2, 5, 10, 15, 20, 25, 50, 100, 150, 200, 250, 500, 750, 1000, 1500, 2000, 2500, 3000, 5000}; время работы - 1 секунда,

10 секунд, 50 секунд, количество прямоугольников 80, раскрой гильотинный. При увеличении контрольного параметра п0 до 1500 эффективность алгоритма возрастает. Рекомендуемые значения параметра от 500 до 1500.

и

¡i в Классическая

В 100 S SOOL 401

si г *(

■ i S

- -J РЭвристш.* ! ,

60 L 60S 40 В 60 Т 20 В 100 L

KOj 1-вО flfMMOyrofliiHMitOB

:Iqca

jlB1«l ЁА'

20 $ го t sob sot

Kon-во ЛрЯ*"ЭуГОЛ4.НМ|!С>

1

атало j ; ots PRP | !

Рисунок 6 - Результаты численного эксперимента а - зависимость значении оценочной функции от контрольного параметра; 6 - зависимость КРа от вида оценочной функции; в - зависимость КРа от начального решения; <? - сравнение методов SA, С А и (} + 1}-ЕА;

д сравнение декодеров; е - сравнение алгоритмов SA, TS и NPE CJecode

Серия 2 Исследовалась зависимость коэффициента раскроя, получаемого методом «холодного» отжига, от вида оценочной функции F(q). Решалась задача на полосу (рис. 5, 6). Параметры алгоритма: пд= 500; время работы алгоритма - 50 секунд, количество прямоугольников - 40, 60, 100 и 200, раскрой гильотинный. Использовались следующие оценочные функции: F(q) = S(q), где S(q) - площадь использованного материала, и F(q) = 1п£(д). Использование логарифмической оценочной функции повышает качество решения задачи на 3-5%.

Серия 3. Исследовалась зависимость коэффициента раскроя, получаемого методом «холодного» отжига от начального решения, которое генерировалось случайным образом или с помощью эффективной однопроходной эвристики. Решалась задача на полосу (рис. 5, в). Параметры алгоритма: и<т= 50; время работы - 1 минута, количество прямоугольников - 20, 40, 60 и 100, раскрой гильотинный. При использовании однопроходной эвристики в качестве начального решения эффективность метода «холодного» отжига возрастает на 1-2%.

Серия 4 Сравнительный анализ методов «имитация отжига», «холодного» отжига, (1+1)-ЕА (повороты прямоугольных заготовок запрещены) (рис. 5, г). Параметры алгоритмов: время работы - 5 минут, количество прямоугольников -20 и 50, раскрой гильотинный. Метод «холодного» отжига показывает лучшие результаты на классах задач «триплеты», «длинные» и «малые» прямоугольниками по сравнению с методом «имитация отжига» на 2-3% и по сравнению с методом (1+1)-ЕА на 3-5%, а также при увеличении числа заготовок.

Серия 5. Целью эксперимента при решении задачи раскроя полосы являлось сравнение декодеров в составе метаэвристики «поиск с запретами» (Мухачева Э А., Ермаченко А.И.). Использовались декодеры: «последовательного конструирования», «блочный» и «вставки». Повороты прямоугольников разрешены (рис. 5, д). Параметры алгоритмов: время работы - 1 минута, количество прямоугольников - 20 и 50, раскрой негильотинный. Разработанный декодер «вставки» показал лучшие результаты в классе «длинные» прямоугольники, чем декодер «последовательного конструирования» и «блочный» на 1-2%.

Серия 6 Проводилось сравнение методов «поиск с запретами», «холодного» отжига с декодером «вставки» и NPE_Decode (Кочетов Ю.А., Руднев A.C., Новосибирский государственный университет). Повороты прямоугольников разрешены. Параметры алгоритмов: время работы - 1 минута, количество прямоугольников - 80, раскрой гильотинный, наличие дефектных областей материала. Тестовые данные: класс В - «большие» прямоугольники [0.4W..0.5W; 0AW..0.55W]. Решалась задача гильотинного раскроя на листы с дефектными областями (рис. 5, е). В 30% случаев алгоритмы «холодного» отжига и «поиск с запретами» с декодером «вставки» показали улучшение решения на один лист.

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

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

методов для решения задач прямоугольного раскроя с учетом дефектных областей. Разработан алгоритм «холодного» отжига, основанный на базе процедур метода «имитация отжига». На большинстве классов задач он показал лучшие результаты по сравнению с классическим методом «имитация отжига». Реализован алгоритм (1 + 1)-ЕА как частный случай алгоритма «имитация отжига» с нулевой температурой.

2. Разработан новый метод проектирования прямоугольного раскроя -декодер РЯР, учитывающий дефекты раскройного материала. Этот декодер используется в составе метаэвристик (1+1)-ЕА, «холодного» отжига и «поиска с запретами». Они включены в автоматизированную систему расчета прямоугольного раскроя 2ВИ-СШ. Использование нового декодера позволяет повысить качество решения по сравнению с известными декодерами на 3-5%.

3. Разработаны методы и алгоритмы, позволяющие учитывать ряд технологических ограничений: припуски на резы, окантовку рулона или листов, дефекты раскраиваемого материала, реализованные в виде программного обеспечения. Программное обеспечение в составе системы 2ВЯ-СиТ автоматизированного рабочего места технолога раскройно-заготовительного производства позволяет повысить коэффициент использования материала в среднем на 5-8% по сравнению с простыми эвристиками и значительно сократить время проектирования.

4. Разработано оптимизационное ядро САПР в виде программного комплекса проектирования прямоугольного раскроя листового и рулонного материала с учетом дефектных областей на базе модифицированных эволюционных методов в рамках системы САПР раскройно-заготовительного производства. Результаты диссертационной работы приняты к внедрению в виде алгоритмов и программного обеспечения на ООО «Центр автоматизации проектирования и высоких технологий» (г. Екатеринбург), на предприятии, производящем мебель.

5. Исследована эффективность предложенных методов на базе численного эксперимента с использованием системы двумерного прямоугольного раскроя 2011-СиТ. При раскрое полосы наблюдается заметное улучшение качества решения задачи раскроя на некоторых классах задач.

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

Публикации в изданиях, рекомендованных ВАК:

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

Другие публикации:

2. Применение метода «моделирования отжига» для решения задачи раскроя / Т.Ю. Жукова (Сиразетдинова) // Принятие решений в условиях неопределенности: сб. статей. Уфа: УГАТУ, 2003. С.45-51.

3. Применение метаэвристики «имитация отжига» для задач гильотинного прямоугольного раскроя / А.Ф. Валеева, Т.Ю. Сиразетдинова // Междунар. Уфимск. зимн. шк.-конф по математике и физике для студентов, аспирантов и молодых ученых : матер, конф. Уфа, 2005. С. 99.

4. Метод «имитация отжига» для решения задач двухмерного гильотинного раскроя / Т.Ю. Сиразетдинова // Интеллектуальные системы обработки информации и управления : сб. статей регион, зимн. шк.-сем. аспирантов и молодых ученых. Уфа : Технологии, 2006. С.165-173.

5. Задача прямоугольного гильотинного раскроя на базе метаэвристики «имитация отжига» / Т.Ю. Сиразетдинова, А.Ф. Валеева // Проблемы оптимизации и экономические приложения, III Всероссийская конф.: матер, конф. Омск, 2006. С 55-62.

6. Решение задачи прямоугольного гильотинного раскроя с применением процедур имитации отжига / А.Ф. Валеева, Т.Ю. Сиразетдинова // Социально-экономические и технические системы. [Электронный ресурс] Набережные Челны, №9 2006 ( http^/kampi-ru/setsV 7 с.

7. Система проектирования прямоугольного раскроя /А.И. Ермаченко, Т.Ю. Сиразетдинова и др. Свидетельство об официальной регистрации программы для ЭВМ № 2004611452 от 11. 06.2004. М.

Сиразетдинова Татьяна Юрьевна

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

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

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

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

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

Центр оперативной полиграфии 450000, Уфа-центр, ул. К. Маркса, 12

Оглавление.

Введение.

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

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

1.2. Классификация задач раскроя.

1.2.2. Постановка задачи прямоугольного раскроя.

1.1.1. Постановка задачи прямоугольного раскроя с дефектами материала

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

1.4. Обзор методов решения задачи раскроя.

1.4.1. Точные методы решения задач раскроя.

1.4.2. Приближенные и эвристические методы.

1.4.3. Вероятностные методы локального поиска оптимума.

1.4.4. Использование декодеров.

1.4.5. Применение методов решения задач раскроя-упаковки в автоматизированных системах раскроя-упаковки.

1.5. Выводы.

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

2.1. Метод имитации отжига.

2.2. Метод «холодного» отжига.

2.3. Декодер «вставки».

2.4. Применение метода (1+1)-ЕА к задаче прямоугольного раскроя.

2.5. Метод «поиск с запретами» с декодером «вставки».

2.6. Работа декодера «вставки» с учетом обхода дефектных областей материала.

2.7. Выводы.

3. Автоматизированная система двумерного прямоугольного раскроя 2БК-СиТ.

3.1. Современное состояние раскройно-заготовительного производства.

3.2. Структура САПР раскроя-упаковки.

3.3. Программа-оболочка 2БК-СиТ, ее взаимодействие с расчетными модулями.

3.4. Интеграция системы 2БК-С1Л в стороннюю систему автоматизированного проектирования.

3.5. Алгоритмы, реализованные в системе 2БК-СиТ.

3.6. Выводы.

4. Численный эксперимент.

4.1. Результаты численного эксперимента.

4.2. Выводы.

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

1. Декодер «вставки», разработанный для реализации технологических ограничений и обхода дефектных областей раскраиваемого материала.

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

3. Программная реализация разработанных методов в составе системы прямоугольного раскроя 2БК-СиТ.

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

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

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

2. Предложен метод «холодного» отжига, основанный на принципах метаэвристики «имитация отжига», который в отличие от последней:

- работает с постоянным параметром температуры;

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

- использует новые способы расчета элементов вектора достижимости.

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

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

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

Разработанное программное обеспечение, реализующее методы и алгоритмы расчета прямоугольного раскроя листового и рулонного материала с учетом технологических ограничений, в качестве подсистемы для решения задач прямоугольного раскроя интегрировано в известную систему автоматизированного проектирования «Сириус», внедренную на следующих предприятиях: ООО «Центр автоматизации проектирования и высоких технологий» (г. Екатеринбург), ЗАО «Курганстальмост» (г. Курган), ОАО «Мечел» (г. Челябинск). Применение разработанного программного обеспечения позволило повысить эффективность использования материала на 5-8%.

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

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

Апробация работы

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

1. Международной уфимской зимней школе-конференции по математике (Уфа, 2005);

2. III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2006);

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

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

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

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

Диссертация состоит из введения, четырех глав, выводов, списка литературы, и приложений. Работа изложена на 130 страницах машинописного текста, кроме того, содержит 37 рисунков. Библиографический список включает 123 наименования и занимает 13 страниц.

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

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

Реализован алгоритм (1+1)-ЕА как частный случай алгоритма «имитация отжига» с нулевой температурой.

2. Разработан новый метод проектирования прямоугольного раскроя -декодер РЦР, учитывающий дефекты раскройного материала. Этот декодер используется в составе метаэвристик (1+1)-ЕА, «холодного» отжига и «поиска с запретами». Они включены в автоматизированную систему расчета прямоугольного раскроя 20Я-Си1. Использование нового декодера позволяет повысить качество решения по сравнению с известными декодерами на 3-5%.

3. Разработаны методы и алгоритмы, позволяющие учитывать ряд технологических ограничений: припуски на резы, окантовку рулона или листов, дефекты раскраиваемого материала, реализованные в виде программного обеспечения. Программное обеспечение в составе системы 20Я-СиТ автоматизированного рабочего места технолога раскройно-заготовительного производства позволяет повысить коэффициент использования материала в среднем на 5-8% по сравнению с простыми эвристиками и значительно сократить время проектирования.

4. Разработано оптимизационное ядро САПР в виде программного комплекса проектирования прямоугольного раскроя листового и рулонного материала с учетом дефектных областей на базе модифицированных эволюционных методов в рамках системы САПР раскройно-заготовительного производства. Результаты диссертационной работы приняты к внедрению в виде алгоритмов и программного обеспечения на ООО «Центр автоматизации проектирования и высоких технологий» (г. Екатеринбург), на предприятии, производящем мебель.

5. Исследована эффективность предложенных методов на базе численного эксперимента с использованием системы двумерного прямоугольного раскроя 2Б11-СиТ. При раскрое полосы наблюдается заметное улучшение качества решения задачи раскроя на некоторых классах задач.

Заключение

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

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

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

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

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

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

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

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

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

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

7. Борисовский П.А. Исследование эволюционных алгоритмов решения некоторых задач дискретной оптимизации: диссертация кандидата физ.-мат. наук: 05.13.18. Омск, 2005.109 с.

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

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

10. Валеева А.Ф., Сиразетдинова Т.Ю. Задача прямоугольного гильотинного раскроя на базе метаэвристики «Имитация отжига» // Проблемы оптимизации и экономические приложения, III Всероссийская конф.: матер, конф. Омск, 2006. С. 55-62.

11. Валеева А.Ф., Сиразетдинова Т.Ю. Решение задачи прямоугольного гильотинного раскроя с применением процедур имитации отжига // Социально-экономические и технические системы. Электронный ресурс. Набережные Челны, №9 2006 (http://kampi.ru/sets). 7 с.

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

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

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

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

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

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

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

19. Ермаченко А.И., Сиразетдинов Т.М. Рекурсивный метод для решения задач гильотинного прямоугольного раскроя // Математическое моделирование в решении научных и технических задач. Уфа: Технология, 2001. С. 18-23.

20. Жукова (Сиразетдинова) Т.Ю. Применение метода «моделирования отжига» для решения задачи раскроя // Принятие решений в условиях неопределенности: сб. статей. Уфа: УГАТУ. 2003. С. 45-51.

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

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

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

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

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

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

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

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

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

30. Мухачева A.C., Чиглинцев A.B. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информационные технологии. 2001 №3. С. 27-32.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48. Руднев А.С. Задачи двумерной прямоугольной упаковки в контейнеры с запрещенными областями // Магистерская диссертация, 2006. 120с.

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

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

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

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

53. Aurts Е., Lenstra J., edit. Local Search in Combinatorial Optimization/ // John Wiley&Sons. 1996. P. 10-15.

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

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

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

57. Belov G., Scheithauer G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths // European Journal of Operational Research. 2002.141. P. 274-294.

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

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

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

61. Chen P., Chen Y., Goel M., Mang F. Approximation of Two-Dimensional Rectangle Packing // CS270 Project Report, Spring 1999. P.56-62.

62. Chung F.K.R., Garey M.R., Johnson D.S. On packing two-dimensional bins // SIAM J. Algebraic Discrete Meth. 3 (1982) P. 66-76.

63. 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. P. 89-94.

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

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

66. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation. 1997. Vol. 1. No. 1.

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

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

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

70. Faroe O., Pisinger D., Zachariasen M. Guided local search for the three-dimensional bin packing problem // Tech. Rep. 99/13, DIKU, University of Copenhagen, Denmark. Dept. of Computer Science, University of Copenhagen. P. 251-259.

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

72. Folkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing // Journal of Heuristics. 1998.2(1). P. 5-30.,

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

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

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

76. Gilmore P., Gomory R. Multistage cutting stock problem of two and more dimensions// Operat.Res. 1965.13(1). P.94-120.

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

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

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

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

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

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

83. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing. Science. v220 (1983), pp 671-680.

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

85. Lirov Y., edit. Special issue: Geometric Resource Allocation // Mathematical and Computer Modelling. 1995.16(1).

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

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

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

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

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

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

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

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

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

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

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

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

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

99. Sakanushi K., Kajitani Y. The Quarter-State (Q-sequence) to Represent the Floorplan and Applications to Layout optimization // IEEE Asia Pacific Conference on Circuits and systems. 2000. Pp.829-832.

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

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

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

103. 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. 261-270.

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

105. Takahashi T. A New Encoding Scheme for Rectangle Packing Problem // Graduate School of Science and Technology. Niigata University. IEEE. 2000. P.175-178.

106. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische Losung. Leipzig. 1987.215p.

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

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

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

110. Yanasse H., edit. Special issue: Cutting and Packing Problems// Pesquisa Operacional. 1999.19(2).