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

Петунин, Александр Александрович

Системы автоматизации проектирования (по отраслям)

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

доктора технических наук: Петунин, Александр Александрович
город: Екатеринбург
год: 2009
специальность ВАК РФ: 05.13.12

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

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

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

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

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

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

. 1 АПР 2010

Уфа-2010

004600451

Работа выполнена

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

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

Фроловский Владимир Дмитриевич зав. кафедрой АСУ Новосибирского государственного технического университета

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

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

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

д-р техн. наук, проф. Юрьев Виктор Леонидович

генеральный директор ОАО «Институт технологии и организации производства»

Ведущая организация Институт машиноведения

Уральского отделения РАН

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

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

Автореферат разослан "_18_"_марта_2010 г.

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

/3.

В. В. Миронов

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

Актуальность темы. В машиностроении и других отраслях промышленности существенная часть продукции изготавливается из заготовок, получаемых из листовых материалов на различном технологическом оборудовании. К такому оборудованию относятся, в частности, машины с числовым программным управлением (ЧПУ) для лазерной, плазменной, газовой (кислородной), электроэрозионной и гидроабразивной резки материала. В условиях снижения серийности производства, которые в настоящее время оказались характерными для большинства промышленных предприятий не только в России, именно машины с ЧПУ становятся основным видом станков, удовлетворяющих требованию максимальной простоты адаптации к постоянным изменениям номенклатуры получаемых заготовок. Как известно, использование систем автоматизированного проектирования (САПР) управляющих программ (УП) для станков с ЧПУ {Computer-Aided Manufacturing, САМ-систем) обеспечивает значительное сокращение времени подготовки программ в сравнении с «ручным» проектированием. Разработка УП для технологического оборудования резки предполагает предварительное геометрическое моделирование заготовок и получение раскройной карты листового материала, что порождает задачи оптимизации раскроя материала, которые заключаются в минимизации расхода материала при получении из пего заготовок известных форм и размеров. Программное обеспечение, автоматизирующее процесс описания геометрии заготовок и проектирования раскроя, принято относить к CAD (Computer-Aided Design) системам.

Начиная с середины 80-х годов прошлого века, во многих странах Европы и в США разрабатывалось математическое и программное обеспечение систем автоматизированного проектирования для решения задач оптимизация раскроя промышленных материалов и автоматизированной подготовки управляющих программ для машин резки с ЧПУ. Созданные на основе этих разработок CAD/CAM — системы отличаются, помимо применяемых математических моделей, методов и алгоритмов, также и различной степенью универсальности, которая касается как широты охватываемых задач раскроя материала, так и спектра технологического оборудования, поддерживаемого системой. Если говорить о зарубежных САПР, то на российском рынке сейчас, в основном, превалируют узкоспециализированные CAD/CAM системы, приобретаемые предприятиями вместе с конкретной машиной с ЧПУ. Такие системы, как правило, имеют эффективный СЛМ-модуль, разработанный специально для данного типа машин, и позволяют решать определенный (хотя и весьма ограниченный) круг задач проектирования раскроя листового материала. Вместе с тем, применение этих САПР вне рамок их специализации чаще всего бывает нецелесообразно, либо невозможно. Универсальные зарубежные CAD/CAM системы помимо высокой стоимости также имеют и недостаточно универсальные подсистемы проектирования раскроя и, как правило, САМ- модули, ориентированные, в первую очередь, только на автоматизацию процесса подготовки управляющих программ. При этом остаются нерешенными вопросы оптимизации разработки УП с точки зрения стоимости и

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

Российские разработчики, работающие в этой предметной области, имеют серьезные успехи в теоретических исследованиях вопросов оптимизации для многообразных задач раскроя-упаковки (Cutting & Packing, С&Р), к которым относятся и задачи раскроя. Огромный вклад в разработку алгоритмов оптимизации раскроя материала, начало которой положили известные работы JI. В. Канторовича и В. А. Залгаллера, внесла самая крупная отечественная научная школа раскроя-упаковки Э. А. Мухачевой (Э. А. Мухачева, М. А. Верхотуров, В. В. Мартынов, В. М. Картак, А. С. Филиппова, А. Ф. Ва-леева и др.). Среди зарубежных ученых, работающих в области создания методов оптимизации раскроя, следует отметить харьковскую научную школу Ю. Г. Стояна. Активно ведутся исследования задач С&Р в Германии, США, Италии, Японии, Китае, Израиле и др. странах.

Общие вопросы создания САПР описаны в работах ведущего российского ученого в области автоматизации проектирования И. П. Норенкова. Гораздо более скромны достижения российской науки в теории и практике разработки САПР раскроя листовых материалов и автоматизации подготовки управляющих программ для технологического оборудования резки с ЧПУ. В этой области в настоящее время работают, в частности, В. Д. Фроловский, М. А. Верхотуров и многие специалисты-практики.

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

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

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

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

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

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

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

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

•разработка концепции и методологии создания универсальных интегрированных CAD/CAM систем, ориентированных на автоматизацию раскройно-заготовительного производства на базе машин с ЧПУ в единичном и мелкосерийном производстве с целью описания структуры, функций и способов программной реализации эффективной САПР фигурного раскроя, адекватной потребностям современного производства;

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

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

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

Основные научные результаты, полученные автором и выносимые на защиту

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

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

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

А.Концепция и методология создания универсальных интегрированных САЛ/САМ систем раскроя, их структура и функции, ориентированные на автоматизацию раскройно-заготовительного производства на базе машин с ЧПУ термической и гидроабразивной резки в единичном и мелкосерийном производстве.

Программное обеспечение универсальной интегрированной САПР раскроя листового материала.

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

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

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

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

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

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

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

Обоснованность и достоверность результатов диссертации. Обоснованность результатов, полученных в диссертационной работе, базируется на использовании апробированных научных положений и методов исследования, корректном применении теоретических выводов теории систем автоматизированного проектирования и опыта разработки CAD/CAM систем раскроя материала, использовании адекватного математического аппарата, согласованности новых результатов с известными теоретическими положениями в исследуемых предметных областях.

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

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

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

■ алгоритмического и программного обеспечения САПР «Сириус», предназначенной для автоматизации проектирования раскроя материала и автоматизированной подготовки управляющих программ для газовой (кислородной), плазменной, лазерной и гидроабразивной резки материала на машинах с ЧПУ.

Апробация работы. Основные научные и практические результаты диссертации докладывались и обсуждались на международных, всероссийских, всесоюзных и региональных конференциях и семинарах, в том числе: Всесоюзном научном семинаре «Математическое обеспечение расчетов линейного и прямоугольного раскроя», Уфа, 1980; Всесоюзном совещании «Проектирование на ЭВМ технологических процессов и оснастки», Ростов-на-Дону, 1980; Всесоюзном семинаре «Применение ЭВМ в инженерных расчетах и автоматизация проектирования в химическом и нефтяном машиностроении», Москва, 1982; Всесоюзной научной конференции «Математическое обеспечение рационального раскроя в системах автоматизированного проектирования», Уфа, 1987; Всероссийском семинаре «Автоматизация раскройно-заготовительного производства на базе машин с ЧПУ», Екатеринбург, 1993,1995; Международной выставке «Информатика-2000», Екатеринбург, 2000; Первой Всероссийской научно-практической конференции по вопросам решения оптимизационных задач в промышленности «Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования», С-Петербург, 2001; Региональном научно-практическом семинаре «Автоматизация конструкторско-техноло-гической подготовки производства на базе программных продуктов T-FLEX», Екатеринбург, 2002,2005; 1-м Международном Евроазиатском машиностроительном форуме, Екатеринбург,2003; Научно-практическом семинаре «Передовые российские технологии для автоматизации проектирования и подготовки производства», Екатеринбург, 2008; Международной конференции «Компьютерные науки и информационные технологии» (CSIT2008), Анталия, Турция, 2008; Международной конференции «Компьютерные науки и информационные технологии» (CSIT2009), Ретимно, Греция, 2009.

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

Публикации. По теме диссертационной работы опубликовано 50 работ, в том числе: 36 статей (из них 9 статей в изданиях из перечня ВАК), 10 тезисов докладов международных, российских, всесоюзных и региональных конференций и семинаров, 4 информационных материала.

Структура и объем работы. Диссертация состоит из введения, пяти глав основного материала, библиографического списка, трех приложений и содержит 347 с. (в том числе 268 с. основного текста). Библиографический список включает 379 наименований литературы. В приложениях приведены акты внедрения результатов диссертационной работы на ряде российских

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

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

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

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

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

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

2. Сроки проектирования технологических процессов раскроя и резки материала.

3. Время резки на машинах с числовым программным управлением;

4. Стоимость резки.

5. Качество проектных решений с точки зрения соблюдения технологических требований резки.

Задача минимизации расхода материала рассматривается в работе в следующей общей постановке. Пусть АиА2>—,Ап - двумерные геометрические объекты (точечные множества), представляющие собой односвязные или многосвязные области, ограниченные одной или несколькими замкнутыми кривыми (граничными контурами). Данные объекты являются геометрическими моделями заготовок. Будем считать, что граничные контуры заданы полилиниями, состоящими из отрезков прямых и дуг окружностей (это связано с тем, что движение инструмента большей части технологического оборудования для раскроя материала возможно только по траектории такого типа). Пусть также заданы В1,В2,...,Вт - области размещения объектов (в общем случае, различные и многосвязные). Местоположение каждой заготовки А -, в области размещения определяется тремя параметрами х,.у,а, где х,у - абсцисса и ордината фиксированной точки (полюса) в некоторой системе координат, а - параметр, задающий ориентацию (угол поворота) объекта на плоскости. Если допустить зеркальное отражение заготовки, то появляется четвертый параметр р (признак зеркального отражения). Таким образом, необходимо определить 4п параметров размещения заготовок, при которых некоторая функция цели (функция качества раскроя) Г = Г(х1,уиа1,рих2,у2,а2,р2,...,хп,уп,ап,р„) достигает своего экстремума и выполняются условия взаимного не пересечения объектов, условия размещения объектов внутри одной из областей размещения В1,В2,...,Вт , а также ряд

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

fa(Xi,yi,ai,Pi,Xj,yj,aj,pj)Z0 i+j, i,j4,2,...,n (2)

rfiW.q.pfeO i—1, 2,...,n (3)

/1(х\,У1,Ч>Р\>хг>У2>аг>Р1>-">хг1>Уп>ап>Рп)^ (4)

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

называемому коэффициенту использования материала (КИМ), п

КИМ - (2 ) / Р , где Si - площадь i -го объекта, Р - суммарная площадь занятой часта областей размещения (использованного материала).

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

■ разработка новых высокоэффективных алгоритмов фигурного раскроя, адекватных потребностям современного производства;

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

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

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

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

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

■ разработка методов автоматического и полуавтоматического формирования маршрута инструмента для резки материала на машине с ЧПУ, учитывающих технологические требования термической резки и направленных на сокращение временных и стоимостных характеристик резки;

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

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

Пусть имеется п заготовок и N внешних и внутренних контуров (И>п), описывающих геометрию заготовок и их местоположение в области размещения. Пусть также Р,- - точки врезки для каждого контура заготовки (¡=1,2, Ро — начальная точка положения инструмента, а Ьу — расстояние между точками Р, и Р]- (ц=0,1,2,...,1V). Необходимо определить такой порядок вырезки контуров I = ¿р^...,/^, который минимизирует функцию

= ^ + (5)

При этом действует следующее ограничение: если в перестановке / контур ц - внешний, то все соответствующие внутренние контуры должны предшествовать контуру 4 в перестановке В силу того, что

значение функции цели (5) однозначно определяется последовательностью вырезки (перестановкой Г), задачу можно рассматривать, в общем виде, как задачу минимизации некоторого функционала Г] — Р](1), заданного на множестве перестановок Ду из N символов. Если точки врезки интерпретировать как вершины плоского графа, то эта задача также сводится к задаче поиска гамильтонова цикла минимальной длины. Из постановки задачи следует, что точка врезки в контур и точка выключения инструмента после вырезки кон-

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

Сформулируем более общую задачу минимизации холостого хода, которая реально возникает на практике при использовании техники резки по контуру. Будем полагать, что для каждого контура определено конечное число точек врезки и, соответственно, такое же количество точек выключения инструмента. Определим вид целевой функции, учитывающей множественность точек врезки для каждого контура. Пусть к1- число возможных точек врезки в контуре /", Д*"*,/) расстояние между точкой выключения инструмента с номером л для контура / и точкой врезки с номером Г для контура] (5=7,..., к'; /=),..., У). Тогда критерием оптимальности маршрута ^(ц,^...,^) может служить функция вида

р= 0

Здесь индекс р=0 и р=И+1 соответствует точке начального положения инструмента. Оптимальным решением задачи будет являться вектор Л, состоящий из 2Ыэлементов: где s¡ - номер точки врезки для контура / (1 < я,- < ), и оптимизирующий функцию (6). При этом знак числа 5; (+/-) определяет направление обхода контура (по или против часовой стрелки). Множество (? допустимых решений задачи (значений вектора К) должно определяться с учетом информации о вложенности контуров и технологических требований термической резки.

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

7^3=• Со# + Ьоп ■ Соп + ТУр/ ■ Ср1 -> тт, (7)

где Ьод— длина переходов с выключенным режущим инструментом (холостой ход); С0д- стоимость единицы пути с выключенным режущим инструментом; ¿о« - длина реза с включенным режущим инструментом; С0„ - стоимость единицы пути с включенным режущим инструментом; Ыр, - количество точек врезки; Ср, - стоимость одной точки врезки.

При этом С0„, СР1 - величины, зависящие от типа резки (газовая, плазменная, лазерная, гидроабразивная), толщины материала и типа материала (конструкционные, нержавеющие, цветные металлы и пр.). Функциональная зависимость Сш и Ср, от перечисленных параметров на практике определяется либо табличными функциями, либо аналитически, что позволяет оценить по формуле (7) стоимость резки, выполняемой по любой УП, в том числе, полученной в интерактивном режиме без оптимизации.

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

рования УП рассматривают задачу уменьшения стоимости резки за счет использования «цепной резки»(сокращения количество точек врезки Л^,) и минимизации длины холостого хода . При решении задачи (7), также как и при решении задачи (5), применяются современные алгоритмы дискретной оптимизации, и также за рамками исследований остается вопрос технологичности получаемых решений. Оптимизация стоимости резки может быть достигнута, в частности, для маршрута инструмента, приводящего к значительному увеличению тепловых деформаций материала и превышению допустимых геометрических искажений размеров заготовок. Разработка методов оптимизации резки листового материала на машинах с ЧПУ, учитывающих технологические требования термической резки, проведена в главе 3.

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

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

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

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

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

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

На основе анализа всех аспектов проблем в диссертационной работе предлагается:

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

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

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

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

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

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

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

образом, задача (1}-(4) сводится, как и задача (5), к задаче оптимизации функции F(I), заданной на множестве перестановок Пп.

Отметим, что множество решений, сформированное по методу ПОР может не содержать оптимального. Метод, в частности, при определении местоположения заготовки не учитывает геометрии заготовок, следующих за размещаемой в выбранной последовательности размещения В то же время возможно при определении параметров размещения очередной заготовки осуществлять «прогнозирование» раскройного плана (производить вычисление частичной функции цели) в пределах некоторого числа заготовок, непосредственно следующих за данной. Излагаемые ниже два алгоритма построения допустимых раскройных планов, однозначно определяемых последовательностью заданных заготовок, основываются на таком прогнозировании. Применительно к решению общей задачи «нестинга» (1)—(4) предлагаемые алгоритмы формирования множества допустимых решений можно сформулировать следующим образом.

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

области размещения. Обозначим через zi = {xi,yi,ai,pi) вектор параметров размещения заготовки с номером /, (через 2,- - найденное и зафиксированное значение вектораz^). Пусть также выбрана некоторая частичная функция цели Fv, определяющая качество раскроя после укладки на материале v заготовок и задано целое положительное число к <п.

Всю совокупность заготовок согласно заданной последовательности разобьем на группы по k элементов в каждой, за исключением, может быть, последней: .....ik ,/t+1,...,/2i,i2l+„...,/„

i г

Ясно, что число таких групп будет равно, если и кратно к, и [п/к] +1, если это не так. Укладку очередной заготовки в каждой группе будем осуществлять таким образом, чтобы после укладки последней к-ой заготовки в группе величина функции цели была минимальной. Такой принцип построения вариантов раскройных планов в соответствии с очередностью номеров заготовок называется алгоритмом групповой оптимизации к-го порядка. Итерационную формулу процедуры, реализующий этот принцип, можно представить в следующем виде:

ЫЧ,■■■,%)= min Fk(zi zt) (8)

1 * ■ zjeGi

Fj+k{zk,...,2i.J= min Fj+k{z\,^z] щ■ zt) (9)

гдеj=k,2k,—,p-K гдеp=k[n/k], Gs - область возможных значений вектора при условии, что векторы z. зафиксированы. В том случае, если п не

кратно к, формулы (8) и (9) должны быть дополнены формулой: F„(z*,...,z*) = min Fn(z\,..jip,zi zQ

z)n äGn •

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

В диссертационной работе при реализации этих алгоритмов (при к=2 и к=3) и метода ПОР для прямоугольных заготовок использован прием «упрощения» границы занятой части области размещения, который позволяет сделать линейной зависимость времени проектирования упаковки от числа прямоугольников. Таким образом, время Т работы программы-декодера прямо пропорционально числу размещаемых прямоугольников п. Для декодера ПОР Т » tMn, где М- некоторая константа, зависящая от размеров прямоугольников и области размещения, at- константа, зависящая от производительности компьютера. Например, время проектирования 100000 (!) вариантов прямоугольного раскроя для 100 прямоугольников на компьютере Genuine Intel® CPU 2140 @ 1,6GHz (1ГБ - ОЗУ) по методу ПОР обычно не превышает 10 сек. Время Т генерации одного раскройного плана по методам групповой оптимизации и паллиативной цели составит Г & tM*[n/k] иГ» thf{n-k) соответственно. С использованием известного набора тестов для задачи упаковки прямоугольников в полосу (Strip Packing Problem, 2DSPP) проведено исследование разработанных декодеров прямоугольной упаковки, которое показало оправданность упрощения границы при проектировании множества допустимых решений G.

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

В диссертации предложены и реализованы несколько приближенных гибридных эволюционных алгоритмов поиска оптимальной последовательности, которые основываются на введении функции расстояния (метрики) на множестве перестановок П„ . Метризация множества перестановок, которая порождает механизм определения «близости» элементов множества, позволяет, с одной стороны, разрабатывать алгоритмы эволюционного типа, а с другой стороны, применять классические алгоритмы локальной оптимизации, базирующиеся на понятии окрестности точки в дискретном множестве П„ (окрестностью радиуса г перестановки ¡о называется множество O/Iq) аП„ такое, что V/ е Or(I0) р (I.Iq) < г, где р- некоторая функция расстояния, заданная на парах элементов множества П„). Система окрестностей на множестве П„ определялась транспозиционной метрикой р' и модифицированной разностной метрикой pd (плавающей квазиметрикои): расстоянием между перестановками I и 10 в транспозиционной метрике р (I,Iq) называется наименьшее возможное число транспозиций, которое необходимо выполнить в перестановке I, чтобы получить перестановку 1о. Расстояние между перестановками / и Yb плавающей квазиметрике pd задается по формуле:

pá(I,y) = YJc¡ ■[//" где if,if - порядковые номера элемента i в перестановках Y и /соответственно, с, - некоторые весовые коэффициенты.

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

Во второй главе также исследуется вопрос целесообразности применения аппроксимационного подхода на основе аппроксимации прямоугольниками объектов сложной формы для решения задач «нестинга». Был проведен вычислительный эксперимент сравнения эффективности двух алгоритмов, предназначенных для решения задач раскроя-упаковки: алгоритма упаковки прямоугольных объектов и алгоритма упаковки объектов, границы которых состоят из отрезков прямых и дуг окружностей. Оба эти алгоритма входят в состав библиотеки Nest Class Library(NCL) (разработка УГТУ-УПИ). Для описания эксперимента введем два понятия:

Коэффициентом прялюугольности Crect двумерного объекта назовем величину, равную отношению площади объекта к площади прямоугольника минимальной площади, содержащего данный объект (crecl=S/P, где S -площадь объекта, Р — площадь содержащего объект прямоугольника).

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

Crect= X c'rect i=1

Было сгенерировано 1000 тестовых заданий на раскрой со значениями коэффициента прямоугольности от 0,2 до 1. Результаты данного эксперимента приведены на рис. 1.

0,9 0.8 0,7 0,6 0,5 0.4 0,3 0.2 0,1 о

КИМ

■■ Прямоугольный раскрой

0 0,2 0.4 0.6 0,8 1

Коэффициент прямоугольности

Рисунок 1. Зависимость КИМ от коэффициента прямоугольности Сге(Л

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

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

пользуемого на практике приема: объединения фигурных объектов (заготовок) в группы или «блоки» (bit). Ясно, что прием формирования блоков вместе с повышением коэффициента прямоугольности задания также расширяет и класс заданий на раскрой, для которых целесообразно применять оптимизационные алгоритмы прямоугольного раскроя-упаковки. На рис. 2 приведен результат раскроя, полученный методом прямоугольного раскроя-упаковки с предварительным формированием блоков заготовок.

Рисунок 2. Пример использования оптимизационного алгоритма прямоугольного раскроя-упаковки Исследована эффективность применения приема формирования групп при проектировании допустимых вариантов раскроя по методу ПОР. На примере ряда тестовых заданий было проведено исследование, направленное на определение целесообразности предварительного формирования bit на основании значения введенного понятия: коэффициента «блочности» задания на раскрой Сыг пы/п> гДе пЫг количество заготовок, входящих в прямоугольные «блоки»; п - общее количество заготовок в задании на раскрой. На рис. 3 показан график зависимости КИМ от коэффициента «блочности» задания на раскрой для раскройных планов, спроектированных с предварительным формированием групп заготовок и без их формирования.

0,9 0,8 0,7

КИМ 0J6

0,5 0,4 0,3 0,2 0,1

------

с формированием блоков _ без формирования блоков -

О 0,2 0,4 0,6 0,8 1

Коэффициент «блочности»

Рисунок 3. Зависимость КИМ от коэффициента Сьи

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

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

логическим (растровым) описанием, которое позволяет заменить трудоемкие арифметические операции для вычисления параметров размещения геометрических объектов быстрыми логическими операциями процессора: AND, OR, NOT, XOR. Разработанные алгоритмы проектирования раскройных планов на базе растрового представления реализуют метод ПОР с различными оптимизационными критериями функции цели. Как и алгоритмы прямоугольного раскроя, они являются быстродействующими и обеспечивают возможность их применения в САПР фигурного раскроя в условиях единичного и мелкосерийного производства. В диссертационной работе приведен результат решения тестовой задачи, которая является демонстрационным примером CAD/CAM системы AccuFab (США). На трех прямоугольных листах размером 96x48 единиц необходимо разместить 207 заготовок сложной формы с фиксированным припуском на рез. Время проектирования составило 37 е., аналогичное времени работы системы AccuFab. КИМ увеличен на 3% по сравнению с результатом раскроя, полученным в самой системе AccuFab. Для построения допустимых вариантов размещения использовался декодер, реализующий метод ПОР для задач с изотропными свойствами материала. Заданный шаг позиционирования растрового объекта - 0,02 единицы.

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

Таблица 1. КЛАССИФИКАЦИЯ ЗАДАЧ ФИГУРНОГО РАСКРОЯ

Критерий классификации Наименование классов и подклассов

Изотропность материала изотропный; анизотропный; полуизотропный

Тип припуска на рез фиксированный; переменный

Регулярность раскроя регулярный; нерегулярный; квазирегулярный

Тип областей запрета без областей запрета; с безусловными областями запрета; с условными областями запрета

Признак зеркального отражения без зеркального отражения заготовок; с зеркальным отражением заготовок; с зеркальным отражением для части заготовок в задании

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

Тип резки гильотинная; произвольная (термическая резка; резка без деформаций материала)

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

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

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

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

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

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

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

Для реализации сформулированного подхода было произведено разбиение всех заданий фигурного раскроя по трем признакам: серийности производства, «прямоугольности» задания и преобладанию «крупных» заготовок над «мелкими». Сформулированы формальные числовые правила разделения заданий на 12 групп по указанным признакам (таблица 2). При этом все задания в группах удовлетворяли следующим свойствам: изотропный материал, фиксированный припуск на рез, нерегулярный раскрой без областей запрета и без зеркального отражения контуров заготовок, описанных полилиниями с дугами окружностей, с произвольной резкой без термических деформаций. В качестве тестируемых алгоритмов были выбраны 2 алгоритма фигурного раскроя (NCL и Штабель), входящие в состав САПР «СИРИУС» и алгоритм Nesting Factory, разработанный компанией Algomate (Израиль). В таблице 3

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

Таблица 2. КЛАССИФИКАЦИЯ ЗАДАНИЙ ФИГУРНОГО РАСКРОЯ

дляп ЕСТИРОВАНИЯ АЛГОРИТМОВ

Тип производства Тип заготовок в задании

Непрямоугольные прямоугольные

Крупные Мелкие крупные мелкие

Единичное 1 2 3 4

Мелкосерийное 5 6 7 8

Крупносерийное 9 10 11 12

Таблица 3. СХЕМА АВТОМАТИЧЕСКОГО ВЫБОРА АЛГОРИТМА

задания

1 2 3 4 5 6 7 8 9 10 11 12

Алгоритм раскроя ~~~~—^

Nesting Factory

NCL

Штабель

Аналогичный вычислительный эксперимент на предмет определения схемы выбора алгоритма раскроя был проведен для класса прямоугольных заготовок: все тестируемые задания для прямоугольного раскроя были разбиты на четыре группы по двум признакам: серийности производства и преобладанию «крупных» заготовок над «мелкими».

В качестве тестируемых методов были выбраны 5 методов прямоугольного раскроя, входящие в состав систем СЕТАМ-СЦТ (разработка УГАТУ) и N0,: рекурсивный метод (ЛСАР1ш), метод эмуляции отжига (БА),метод поиска с запретами (ТБ), метод выбора корзин (УВ8Р1ш), гибридный эволюционный алгоритм КАР11АЬ (ЫСЬ-К). В таблице 4 приведены результаты тестирования.

Таблица 4. РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ МЕТОДОВ ПРЯМОУГОЛЬНОГО РАСКРОЯ

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

оптимизации единичное Мелкосерийное

мелкие крупные мелкие Крупные

RCAplus 89,51 89,57 92,75 88,22

SA 85,61 85,61 89,00 88,43

TS 85,48 85,48 88,85 87,98

VBSPlus 89,19 89,19 91,03 89,01

NCL-K 92,41 90,18 90,44 88,17

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

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

В третьей главе исследуются вопросы автоматизации подготовки управляющих программ для машин резки листового материала с ЧПУ. Разработаны способы уменьшения термических деформаций материала при резке на машинах с ЧПУ и методы минимизации стоимости резки, реализованные как в виде автоматических процедур, так и в виде полуавтоматических функций. Как мы отмечали, задача оптимизации стоимости резки заключается в минимизации функции F3=Loff ■ Coff+Lon • Con+Npt ■ Cpt

Если не применяется специальная техника резки («совмещенный рез», «мосты» или «перемычки»), то оптимизационная задача может быть сведена к задаче поиска оптимального BCKropa.Q=(il,i2,...,iN,s„s2,...,sN,py,p2,...,pff). Здесь параметры имеют тот же смысл, что и в постановке задачи минимизации холостого хода инструмента (6), а рк - признак включения/выключения инструмента {0,1} при переходе в точку врезки sj? При этом QeG , где G - множество технологически допустимых вариантов маршрута резки. Допустимость варианта маршрута предполагает не пересечение контуров заготовок при переходах между контурами с включенным инструментом и соблюдением требований технологичности с точки зрения термических воздействий на заготовки.

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

1) общие изменения геометрических размеров заготовок (уменьшение) вследствие ее вырезания из нагретой части материала;

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

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

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

технологически корректного выбора порядка резки заготовок, точек врезки и направления резки контуров (по/против часовой стрелки). Для этого вводятся понятия правил «жесткости материала» и «жесткости заготовки».

Правило «жесткости материала» определяет допустимый порядок (последовательность) /д, резки контуров заготовок на материале. Фактически оно включает в себя несколько эвристических правил. Рис. 4 иллюстрирует четыре правила выбора стороны материала, с которой следует начинать процесс термической резки.

ничп.'ю |?С-*КП

а»

Я)

в)

•Й-

* - и --. -л. Ея$Я

г)

Рисунок 4. Правила выбора начальной стороны материала

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

все области размещения В1,В2,...,Втразбиваются на подобласти В =(] £2/, где I) - количество выбранных зон для области В}. При этом формирований и нумерация зон должны проводиться в соответствии со всеми правилами «жесткости материала» и таким образом, чтобы оставшаяся не вырезанная область по своей геометрической форме приближалась к квадратной области.

Правило «жесткости заготовки» заключается в том, что при резке контура г точка врезки 5, (1 < л,- <&') и направление резки контура выбираются таким образом, чтобы сначала вырезались участки контура, расположенные в непосредственной близости к границе материала, либо к границе вырезанной области, а завершение резки происходило по участку контура, граничащего с «жесткой» (не вырезанной) частью области.

На основе введенных понятий «жесткости» заготовок, «жесткости» материала и «зоны резки» разработана методика сокращения тепловых деформаций материала при проектировании УП для машин термической резки

(МТР), как в автоматическом, так и в интерактивном режиме. Методика включает в себя определение:

1) зон для каждой области размещения у,

2) порядка резки контуров г,,^,...,/^ ;

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

Тем самьм определена декомпозиционная модель формирования множества б* допустимых решений для задачи (6). Разработан эвристический вычислительный алгоритм автоматического проектирования УП для МТР в соответствии с данной моделью, что позволяет в автоматическом режиме формировать некоторые допустимые значения вектора /?=(11,/2,..,/^,51,5:2,...,5,дг). Для минимизации холостого хода инструмента, как и для поиска оптимальной последовательности прямоугольной упаковки, использованы гибридные алгоритмы, сочетающие эволюционную стратегию и поиск локальных экстремумов.

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

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

В главе 3 также описан разработанный в ходе диссертационного исследования набор специальных полуавтоматических функций (макропрограмм) САМ системы, обеспечивающий эффективное применение различных стратегий при проектировании УП для машин резки листового материала. Основное назначение разработанных макропрограмм - автоматизация проектирования маршрута резки с целью сокращения времени и стоимости резки, как за счет использования специальных возможностей технологического оборудования с ЧПУ (резка трехрезаковым блоком, резка несколькими суппортами и др.), так и за счет применения специальных способов резки. На рис. 5 показана схема движения режущего инструмента при применении одной специальной функции («змейка»), использующей технику резки нескольких заготовок без выключения резака. Учитывая, что длина реза с включенным режущим инструментом при применении этой техники (по сравнению с техникой резки по контуру) практически не увеличится, уменьшение стоимости резки при каждом использовании функции составит А = (П] -1)*Ср/, где щ - число контуров, вырезаемых «змейкой» без выключения инструмента.

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

1 Ч _ _,'' Точка врезки

Рисунок 5. Резка «змейкой» трех одинаковых заготовок

В диссертационной работе на основе реальных производственных примеров и с учетом технических характеристик конкретного технологического оборудования определено примерное соотношение времени холостого хода и общего времени резки листового металла толщиной 10-30 мм на машинах с ЧПУ, которое составляет от 0,1% (для гидроабразивной резки) до 3-4% (для плазменной резки). Показано, что задача соблюдения технологических требований термической резки при разработке УП для оборудования газовой и плазменной резки имеет приоритетный характер перед задачей (6) минимизации холостого хода инструмента. Алгоритмы оптимизации маршрута инструмента могут эффективно использоваться в САМ системах при резке тонколистового материала, для которого суммарное время рабочего хода инструмента и суммарное время холостого хода являются сравнимыми величинами.

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

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

• оцифровка 2D объектов любой сложности с помощью устройств типа «дигитайзер»;

• оцифровка 2D объектов на экране монитора по растровой «подложке»;

• делинеаризация геометрических контуров;

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

В четвертой главе рассматриваются вопросы, связанные с разработкой концепции и методологии автоматизации проектирования раскроя материала на базе машин с ЧПУ, описана структура универсальной интегрированной CAD/CAM системы проектирования технологических процессов раскроя лис-

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

Определены следующие основные концептуальные признаки САПР:

• универсальность (широкий охват задач раскроя и технологического оборудования с ЧПУ для термической и гидроабразивной резки материала);

• ориентация на условия единичного и мелкосерийного производства;

• применение геометрических моделей, использующих круговую и линейную интерполяцию;

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

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

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

• приоритет технологических требований термической резки;

• ориентация на оптимизацию стоимостных характеристик резки на машинах с ЧПУ.

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

1) Подсистема моделирования геометрической информации для двумерных объектов.

2) Модуль формирования задания на раскрой.

3) Подсистема проектирования раскроя.

4) Модуль проектирования УП.

5) Постпроцессор.

6) Модуль вывода управляющей программы на носитель для ввода в машину с ЧПУ.

7) Модуль верификации и редактирования УП.

8) База данных материала и заготовок.

9) Подсистема планирования раскроя,

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

■ модуль для связи с системой ERP (Enterprise Resource Planning), функционирующей на предприятии;

■ подсистема расчетов линейного и шльотинного раскроя;

■ модуль расчетов 3D раскроя-упаковки и пр.

На рис. 6 и 7 представлены структурная схема универсальной интегрированной САПР, предназначенной для проектирования технологических процессов раскройно-зашговительного производства, и функциональная модель ее подсистемы для проектирования раскроя материала. Сформулированы требования к программной реализации функций основных подсистем универсальной интегрированной CAD/CAM системы раскроя. Показана целесообразность наличия в универсальных интегрированных CAD/CAM системах фигурного раскроя модуля верификации УП и подсистемы гильотинного рас-

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

Подсистема описания геометрической информации

Модуль формирования задания на раскрой

Подсистема планирования раскроя

Подсистема фигурного раскроя

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

Подсистема вывода УП на носитель для ввода в машину с ЧПУ

Рисунок 6. Структура ПО универсальной CAD/CAM системы для проектирования технологических процессов раскройно-заготовительного производства

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

Рисунок 7. Функциональная модель подсистемы проектирования раскроя

Формализована оптимизационная задача минимизации времени резки на гильотинных ножницах. Отмечено, что в случае потребности у предприятия в решении задач одномерного и трехмерного раскроя-упаковки, универсальную САПР фигурного раскроя следует расширять соответствующими подсистемами на основе единых алгоритмов для расчетов ID, 2D и 3D раскроя, но различающихся способами обработки геометрической информации. Единство алгоритмов обеспечивается общей декомпозиционной моделью, используемой для решения всех задач раскроя в условиях единичного производства.

В главе 4 также разработан и обоснован подход к программной реализации подсистем САПР нерегулярного раскроя (рис. 8), заключающийся в том, что в качестве графического редактора САПР выступает универсальная CAD система, а специализированные модули разрабатываются с использованием API (Application Programming Interface) на основе технологии .NET. Проведена реализация предложенной схемы применительно к модулю проектирования фигурного раскроя и ^/универсальной системы T-Flex CAD.

Рисунок 8. Схема применения Open API T-Flex CAD при разработке САПР нерегулярного фигурного раскроя

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

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

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

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

•на раскройно-заготовительном этапе производства сократить расходы материала на 5-10%;

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

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

•повысить качество получаемой продукции.

Проведенные в ходе внедрения САПР «Сириус» исследования эффективности средств, предназначенных для автоматизации технологических процессов раскроя материала, позволяют сформулировать несколько направлений дальнейшего развития и совершенствования систем автоматизированного проектирования раскроя и программирования УП для машин с ЧПУ:

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

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

3. Разработка отечественной интегрированной САПР фигурного раскроя и программирования УП для всех типов технологического оборудования с ЧПУ (включая прессовое оборудование) на базе универсальной российской CAD системы типа T-Flex CAD.

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

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

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

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

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

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

4.Сформулированы концепция и методология создания высокоэффективных интегрированных САПР раскроя материала для условий единичного и мелкосерийного типа производств, отличающиеся ориентацией на сочетание специализированных подсистем и универсальных CAD систем и на использование полуавтоматических методов проектирования. Формализованы основные оптимизационные задачи автоматизации проектирования раскройно-заготовительного производства. Предложен и реализован подход к созданию эффективного программного обеспечения проектирования технологических процессов раскроя на основе сочетания специализированных подсистем и универсальной CAD системы T-Flex CAD с использованием автоматических и интерактивных методов проектирования. Описана структура и состав функций САПР фигурного раскроя материала, характеризующейся высокой степенью универсальности решаемых задач раскроя и широким охватом технологического оборудования с ЧПУ для газовой, плазменной, лазерной и гидроабразивной резки материала.

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

ского университета-УПИ результаты работы используются на механико-машиностроительном факультете при проведении лекционных и практических занятий по дисциплинам «Автоматизация конструкторского и технологического проектирования» и «Разработка САПР» со студентами специальности 230104 (220300) - Системы автоматизированного проектирования, а также в курсовом, дипломном проектировании и диссертационных исследованиях аспирантов кафедры «Информационные технологии и автоматизация проектирования».

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в рецензируемых журналах из перечня ВАК

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

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

3. Параллелепипедная упаковка: алгоритмы, численный эксперимент и практические расчеты / А. А. Петунин, А. Ф. Валеева // Информационные технологии. 2007. № 12. С. 43-50.

4. Метод прямоугольной аппроксимации для решения задач нерегулярного фигурного раскроя-упаковки / А. А. Петунин, Э. А. Мухачева, А. С. Филиппова // Там же. 2008. № 1. С. 28-31.

5. Задача размещения ортогональных многоугольников: модели и алгоритм покоординатной упаковки / В. М. Картак, Э. А. Мухачева, Л. И. Васильева, А. А. Петунин// Там же. 2008. № 3. С. 46-53.

6.0 применении API T-FLEX CAD при разработке подсистемы автоматизированного проектирования раскроя материала / А. А. Петунин, И. С. Галкин // САПР и Графика 2008. № 12. С. 86-88.

7.0 некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала / А. А. Петунин // Вестник УГАТУ. Серия: Управление, вычислительная техника и информатика. 2009. Т. 13, № 2 (35). С. 280-286.

8. Автоматизация нерегулярного фигурного раскроя: основные подходы к разработке систем проектирования раскроя и управляющих программ для машин резки листовых материалов / А. А. Петунин // Информационные технологии. 2009. № 10. С.29-34.

9. Об автоматическом выборе метода оптимизации прямоугольного раскроя / А. А. Петунин // Программные продукта и системы. 2009. № 4 (88). С. 143-145.

Статьи в рецензируемых журналах из перечня ВАК, опубликованные до 2001 г.

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

11. Централизация раскройно-заготовителыюго производства на базе автоматизированных технологических линий раскроя листового металлопроката / А. А.

Петунии, А. А. Беседин, В. Я. Гамберг, В. В. Геймур, В Н. Ковальков // Тяжелое машиностроение. 1993. №7. С.19-22.

12. САПР «Сириус» - оптимизация раскроя и резки листовых материалов / А. А. Петунин А. А., В. И. Кротов, С. С. Уколов, В. В. Видяпин // САПР и графика. 1999. №Ю. С.42-47.

13. Информационная система планирования для интегрированной САПР «Сириус» / А. В. Полевов, А. А. Петунин А. А // Вестник УГТУ-УПИ. Конструирование и технология изготовления машин: Сб. научн. трудов. Екатеринбург: ГОУ ВПО УГТУ-УПИ. 2000. №3(11). С. 62-65.

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

14. О плотном размещении плоских выпуклых геометрических фигур / А. И. Липовецкий, А. А. Петунин // Автоматизация проектирования в машиностроении. Минск: ИТК АН БССР, 1981. Вып. 3. С. 39-44.

15. Задачи размещения геометрических объектов в проектировании: препринт / В. Г. Ещенко, А. В. Шишов, В. С. Тимощук, И. В. Теткин, А.И. Липовецкий, А. А. Петунин, Л. С. Шевелев. Киев: Ж АН УССР, 1981.31 с. (АН УССР. Ин-т кибернетики; препринт 81-81).

16. Использование выпуклых оболочек плоских фигур для приближенного решения задачи раскроя / А. И. Липовецкий, А. А. Петунин // Информационный листок Свердловского ЦНТИ, № 580-81. Свердловск, 1981.4с.

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

18. Об изменении метрик на множестве перестановок и решении задач размещения геометрических объектов / А. А. Петунин, А. И. Липовецкий // Автоматизация проектирования технологических процессов. Минск: ИТК АН БССР, 1982. Вып. 1. С. 154-159.

19. О некоторых вопросах разработки системы автоматизированного проектирования управляющих программ для газорезательных машин с ЧПУ в ПО «Урал-маш» / Н. В. Быков, А. А Петунин, M А. Тришин // Автоматизация технологической подготовки производства: межвуз. сб. научн. трудов. Свердловск: УПИ, 1986. С.35-38.

20. Система автоматизированного проектирования раскроя материалов и автоматизация раскроя металлопроката на базе машин с ЧПУ для термической резки металла / А. А. Петунин, В. Я. Гамберг, В. И. Кротов Н Титан. М.: ВИЛС. 1993. №2. С.56-58.

21. Интегрированная САПР «Сириус» / А. А. Петунин // КомпьютерМэн. Екатеринбург: Комсомольская Правда - Урал. 1996. №6. С.9-12.

22. Интегрированная САПР рационального раскроя материала и подготовки управляющих программ для технологического оборудования резки металлопроката / А. А. Петунин, Р. А. Вайсбурд, Н. У. Тугушев // Принятие решений в условиях неопределенности (проблема раскроя-упаковки): междунар. научн. изд. Уфа: УГАТУ, 1997. С.329-348 (на англ. языке).

23. Промышленные системы автоматизированного проектирования / АЛ. Петунии // Методические материалы по изучению курса «Разработка САПР» для студентов специальности САПР. Екатеринбург: УХТУ, 1998.40с.

24. Интегрированная САПР «Сириус» для автоматизации раскройно-заготовительного производства. Концепция. Опыт разработки и внедрения / А. А. Петуния // Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования: сб. докл. 1-й Всерос. науч.-пракг. конф. по вопросам решения оптимизационных задач в промышленности. СПб: ЦНИИТС, 2001. С. 126-129.

25.0 некоторых методах решения задач двумерного раскроя-упаковки в единичном производстве / А. В. Полевов, А. А. Петунин // Там же. С.133-136.

26. Об одном алгоритме проектирования раскроя для условий мелкосерийного производства / А. С. Выогин, А. А. Петунин // Там же. С.69-73.

27. Разработка программного обеспечения интерактивного раскроя и проектирования управляющих программ для машин термической резки материала / В. И. Кротов, А. А. Петунин // Там же. С. 87-91.

28. Nest Class Library / А. В. Полевов, А. А. Петунин А. А // Научн. труды VII отчетной конф. молодых ученых ГОУ ВПО УГТУ-УПИ: сб. статей в 3 ч. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005. Ч. 2. С. 212-214.

29. Создание и обработка параметрических моделей геометрических объектов / П. А. Копорушкин, А. А. Петунин И Там же. 4.3. С. 368-370.

30. Автоматизация проектирования и изготовления малых архитектурных форм типа «решетка» / А. А. Петунин II Архитектон: Известия вузов. 2006. №16. URL: http://archvuz.ru/ (дата обращения 21.11.091.

31. САПР и .NET / И. С. Галкин, А. А. Петунин II Научн. труды XI отчетной конф. молодых ученых ГОУ ВПО УГТУ-УПИ: сб. статей в 3 ч. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2007. Ч. 3. С. 287-289.

32. Структура САПР фигурного раскроя и подготовки управляющих программ для машин резки листового материала / А. А. Петунин // Компьютерные науки и информационные технологии. Междунар. научное изд.: матер. 10-той между-нар. конф. CSIT2008 (Ангалия, Турция, 15-17 сентября 2008 г.). Уфа, 2008. Том 3. С. 119-122 (на англ. языке).

33. Использование интерфейса прикладного программирования в универсальных САПР / И. С. Галкин, А. А. Петунин // Научн. труды XV отчетной конф. молодых ученых ГОУ ВПО УГТУ-УПИ: сб. статей в 3 ч. Екатеринбург: УГТУ-УПИ, 2009.4.2. С. 14-16.

34.0 классификации оптимизационных задач фигурного раскроя / А.А.Петунин // Инновационные информационные технологии: Теория и практика. Междунар. научн. изд.: матер. Междунар. сем. (Карлсруе - Уфа - Дрезден, 25-31 июля 2009 г.). 2009. С. 95-97 (на англ. языке).

35. Об одном подходе к разработке программного обеспечения для решения задачи фигурного раскроя материала / И. С. Галкин, А. А. Петунин // Мавлютовские чтения: матер, конф. молодых ученых. Уфа: УГАТУ, 2009. С. 276-278.

36. О некоторых функциях Computer-Aided Manufacturing (САМ) систем для программирования управляющих программ для машин термической резки / А. А. Петунин, В. И. Кротов II Компьютерные науки и информационные технологии. Междунар. научн. изд.: матер. 11-той междупар. конф. CSrT'2009 (Крит, Греция, 58 октября 2009 г.). Уфа, 2009. Том 1. С. 76-80 (на англ. языке).

Диссертант

А. А. Петунин

ПЕТУНИН Александр Александрович

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

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

Подписано к печати xx.xx.xx Формат 60x84 1/16.

Бумага офсетная. Печать плоская. Усл. печ. л.. Усл. кр.-отт. 2,0. Уч.-изд. л. 2,0. Тираж 100 экз. Заказ № 81

Ризография НИЧ УГТУ-УПИ 620002, г. Екатеринбург, ул. Мира, 19

Оглавление автор диссертации — доктора технических наук Петунин, Александр Александрович

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ РАСКРОЯ ЛИСТОВЫХ МАТЕРИАЛОВ.

1.1. Основные задачи автоматизации раскройно-заготовительного производства.

1.2. Анализ подходов к разработке CAD/CAM систем раскроя листового материала.

1.3. Анализ методов решения оптимизационных задач раскроя.

1.4. Задачи оптимизации маршрута движения режущего инструмента

1.5. Анализ программного обеспечения для автоматизации проектирования раскроя материала и автоматизированной подготовки УПдлямашинсЧПУ.

ВЫВОДЫ ПО ГЛАВЕ 1.

ГЛАВА 2. ОПТИМИЗАЦИЯ ПРОЕКТИРОВАНИЯ РАСКРОЯ ЛИСТОВОГО МАТЕРИАЛА В ЕДИНИЧНОМ И МЕЖОСЕРИЙНОМ ПРОИЗВОДСТВЕ.

2.1. Классификация задач оптимизации раскроя по технологическим и геометрическим признакам.

2.2. Исследование метода прямоугольной аппроксимацрш для решения задач нерегулярного фигурного раскроя.

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

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

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

ВЫВОДЫ ПО ГЛАВЕ 2.

ГЛАВА 3. АВТОМАТИЗАЦИЯ ПОДГОТОВКИ УПРАВЛЯЮЩИХ ПРОГРАММ ДЛЯ МАШИН РЕЗКИ ЛИСТОВОГО МАТЕРИАЛА С ЧПУ.

3.1. Сравнительный анализ технологий резки материала на технологическом оборудовании с ЧПУ.

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

3.3. Оптимизационные задачи проектирования УП и стратегии формирования маршрута инструмента.

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

3.5. Автоматизация проектирования и изготовления малых архитектурных форм типа «решетка».

ВЫВОДЫ ПО ГЛАВЕ

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

УНИВЕРСАЛЬНОЙ ИНТЕГРИРОВАННОЙ CAD/CAM СИСТЕМЫ ПРОЕКТИРОВАНИЯ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ РАСКРОЯ ЛИСТОВОГО МАТЕРИАЛА.

4.1. Концепция разработки универсальной интегрированной САПР технологических процессов раскроя листового материала. состав и структура программного обеспечения.

4.2. Требования к функциям основных подсистем универсальной

CAD/CAM системы раскроя в единичном и мелкосерийном производстве

4.3. Интеграция программного обеспечения расчетов линейного, прямоугольного, параллелепипедного раскроя-упаковки и универсальной CAD/CAM системы фигурного раскроя.

4.4. Применение API T-FLEX CAD для разработки САПР фигурного раскроя материала.

ВЫВОДЫ ПО ГЛАВЕ 4.

ГЛАВА 5. РАЗРАБОТКА И ВНЕДРЕНИЕ САПР «СИРИУС».

5.1. Состав и структура программного обеспечения САПР «СИРИУС»

5.2. Реализация подсистемы автоматизированного проектирования фигурного и прямоугольного раскроя в САПР «СИРИУС».

5.3. Применение САПР «Сириус» для оптимизации экономических характеристик термической резки листовых материалов.

5.4. Внедрение интегрированных CAD/CAM решений САПР «СИРИУС» на предприятиях с единичным и мелкосерийным типом производства.

ВЫВОДЫ ПО ГЛАВЕ 5.

Введение 2009 год, диссертация по информатике, вычислительной технике и управлению, Петунин, Александр Александрович

Актуальность исследования. В машиностроении и других отраслях промышленности существенная часть продукции изготавливается из заготовок, получаемых из листовых материалов на различном технологическом оборудовании. К такому оборудованию относятся, в частности, машины с числовым программным управлением (ЧПУ) для лазерной, плазменной, газовой (газокислородной), электроэрозионной и гидроабразивной резки материала, гильотинные ножницы, прессы для листовой штамповки и другое оборудование. В условиях снижения серийности производства, которые в настоящее время оказались характерными для большинства промышленных предприятий не только в России, именно машины с ЧПУ становятся основным видом станков, удовлетворяющих требованию максимальной простоты адаптации к постоянным изменениям номенклатуры получаемых заготовок. Следует отметить, что процесс «индивидуализации» производства никак не связан с сегодняшним глобальным финансовым кризисом, а является объективной особенностью развития мировой экономики на современном этапе. Как известно, использование систем автоматизированного проектирования управляющих программ (УП) для станков с ЧПУ (Computer-Aided Manufacturing, С4М-систем) обеспечивает значительное сокращение времени подготовки программ в сравнении с «ручным» проектированием. Разработка УП для технологического оборудования резки предполагает предварительное геометрическое моделирование заготовок и получение раскройной карты листового материала, что порождает задачи оптимизации раскроя материала, которые заключаются в минимизации расхода материала при получении из него заготовок известных форм и размеров. Программное обеспечение, автоматизирующее процесс описания геометрии заготовок и проектирования раскроя принято относить к CAD (Computer-Aided Design) системам.

Начиная с середины 80-х годов прошлого века, во многих странах Европы и в США разрабатывалось математическое и программное обеспечение САПР для решения задач оптимизация раскроя промышленных материалов и подготовки управляющих программ для станков с ЧГТУ. Созданные на основе этих разработок CAD/CAM — системы отличаются, помимо применяемых математических моделей, методов и алгоритмов, также и различной степенью универсальности, которая касается как широты охватываемых раскройных задач, так и спектра технологического оборудования, поддерживаемого системой. Если говорить о зарубежных САПР, то на российском рынке сейчас, в основном, превалируют узкоспециализированные CAD/CAM системы, приобретаемые предприятиями вместе с конкретной машиной с ЧПУ. Такие системы, как правило, имеют хороший СЛМ-модуль, разработанный специально для данного типа машин, и позволяют эффективно решать определенный (хотя и весьма ограниченный) круг задач раскроя. Вместе с тем, применение этих САПР вне рамок их специализации чаще всего бывает нецелесообразно, либо невозможно.

Российские разработчики, работающие в этой предметной области, могут похвастаться серьезными успехами в теоретических исследованиях вопросов оптимизации для многообразных задач раскроя-упаковки (Cutting & Packing, С&Р), к которым относятся и задачи раскроя. Общие вопросы создания САПР описаны в работах ведущего российского ученого в области теории автоматизации проектирования И.П.Норенкова. Гораздо более скромны достижения российской науки в теории и практике разработки САПР раскроя промышленных материалов и автоматизации подготовки управляющих программ для технологического оборудования с ЧПУ, предназначенного для резки листовых материалов.

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

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

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

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

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

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

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

• разработка концепции и методологии создания универсальных интегрированных CAD/CAM систем, ориентированных на автоматизацию раскройно-заготовительного производства на базе машин с ЧПУ в единичном и мелкосерийном производстве с целью описания структуры, функций и способов программной реализации эффективной САПР фигурного раскроя, адекватной потребностям современного производства;

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

• апробация системы на промышленных предприятиях России.

Основные научные результаты, полученные автором и выносимые на защиту

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

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

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

4. Концепция и методология создания универсальных интегрированных CAD/CAM систем раскроя, их структура и функции, ориентированные на автоматизацию раскройно-заготовительного производства на базе машин с ЧПУ термической и гидроабразивной резки в единичном и мелкосерийном производстве.

5. Программное обеспечение универсальной интегрированной САПР раскроя листового материала.

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

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

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

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

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

Обоснованность результатов, полученных в диссертационной работе, базируется на использовании апробированных научных положений и методов исследования, корректном применении теоретических выводов теории систем автоматизированного проектирования и опыта разработки CAD/CAM систем раскроя материала, использовании адекватного математического аппарата, согласованности новых результатов с известными теоретическими положениями в исследуемых предметных областях.

Практическая значимость результатов. Практическая ценность результатов, полученных в диссертации, заключается в разработке: методики создания САПР раскроя материала в единичном и мелкосерийном производстве, ориентированной на использование в различных отраслях промышленности и на широкий спектр технологического оборудования для производства заготовок из листовых материалов; алгоритмического и программного обеспечения САПР «Сириус», предназначенной для автоматизации проектирования раскроя материала и автоматизированной подготовки управляющих программ для газовой (кислородной), плазменной, лазерной и гидроабразивной резки материала на машинах с ЧПУ.

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

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

Всесоюзном научном семинаре «Математическое обеспечение расчетов линейного и прямоугольного раскроя», Уфа, 1980;

Всесоюзном совещании «Проектирование на ЭВМ технологических процессов и оснастки», Ростов-на-Дону, 1980;

Всесоюзном семинаре «Применение ЭВМ в инженерных расчетах и автоматизация проектирования в химическом и нефтяном машиностроении», Москва, 1982;

Всесоюзной научной конференции «Математическое обеспечение рационального раскроя в системах автоматизированного проектирования», Уфа, 1987;

Всероссийском семинаре «Автоматизация раскройно-заготовительного производства на базе машин с ЧПУ», Екатеринбург, 1993,1995;

Международной выставке «Информатика-2000», Екатеринбург, 2000;

Первой Всероссийской научно-практической конференции по вопросам решения оптимизационных задач в промышленности «Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования», С-Петербург, 2001;

Региональном научно-практическом семинаре «Автоматизация конструктор ско-технологической подготовки производства на базе программных продуктов Т-FLEX», Екатеринбург, 2002, 2005;

1-м Международном Евроазиатском машиностроительном форуме, Екатеринбург, 2003;

Научно-практическом семинаре «Передовые российские технологии для автоматизации проектирования и подготовки производства», Екатеринбург, 2008;

Международной конференции «Компьютерные науки и информационные технологии» (CS1T2008), Анталия, Турция, 2008;

Международной конференции «Компьютерные науки и информационные технологии» (CSIT2009), Ретимно, Греция, 2009.

Результаты диссертационной работы внедрены в виде универсальной интегрированной САПР «СИРИУС» и программном обеспечении для расчетов прямоугольного раскроя в ОАО «Уралхиммаш», ОАО «Уралэлектротяжмаш», ЗАО «Проммашсервис», ЗАО «Завод подъемно-транспортного оборудования», 000«Уралтехнопроект»(г.Екатеринбург), ЗАО «Березовский машиностроительный завод» (Свердловская обл.), ОАО «Мечел» (г.Челябинск), ОАО «Буммаш» (г.Ижевск), ОАО «Копейский машзавод», ОАО «Южноуральский арматурно-изоляторный завод» (Челябинская обл.), ЗАО «Улан-Удэстальмост» (г.Улан-Удэ), ОАО «Буммаш» (г.Ижевск), ЗАО «Курганстальмост» (г.Курган), ЗАО «Топ Системы» (г.Москва), ООО «Тюменьстальмост»(г.Тюмень) и многих других предприятиях России, а также в учебном процессе Уральского государственного технического университета -УПИ Результаты исследования используются также в учебном процессе Уральского государственного технического университета — УПИ и научных исследованиях аспирантов.

Заключение диссертация на тему "Методологические и теоретические основы автоматизации проектирования раскроя листовых материалов на машинах с числовым программным управлением"

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

В диссертационной работе в результате проведенных исследований разработаны методологические и теоретические основы автоматизации проектирования раскроя листовых материалов на базе машин с ЧПУ, позволяющие создавать универсальные интегрированные САПР раскроя материала в единичном и мелкосерийном производстве. В диссертации изложены новые научно-обоснованные решения по разработке и исследованию моделей, алгоритмов и методов автоматизации проектирования технологических процессов раскроя, внедрение которых вносит значительный вклад в повышение эффективности раскройно-заготовительного производства. В ходе проведенных исследований получены следующие научные и практические результаты. l.Ha основе декомпозиционного и аппроксимационного подходов, комбинирования дискретно-логического и векторного представлений геометрической информации разработаны автоматические и интерактивные ' i I i i I J - ' > получать рациональные варианты раскройных карт за время, приемлемое для условий единичного производства. При этом учитываются технологические особенности резки материала. Проведена классификация задач фигурного раскроя листового материала по технологическим и геометрическим признакам, позволяющая разрабатывать алгоритмы оптимизации раскроя с учетов технологии резки, особенностей технологического оборудования для резки, свойств раскраиваемого материала, степени серийности производства и геометрических форм заготовок. Кроме того, предложенная типология позволяет проводить сравнительный анализ эффективности алгоритмов раскроя материала применительно к решению практических задач. На основе проведенных исследований выделен класс задач фигурного раскроя, для которого прямоугольная аппроксимация целесообразна.

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

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

6.Результаты диссертационной работы внедрены в виде универсальной интегрированной САПР «СИРИУС», которая используется для оптимизации расчетов фигурного и прямоугольного раскроя и подготовки управляющих программ машин резки листовых материалов в различных отраслях промышленности, в том числе, в машиностроении, в металлургии, на предприятиях по производству металлоконструкций в Екатеринбурге, Челябинске, Тюмени, Ижевске, Кургане, Свердловской, Челябинской, Пермской областях и других регионах России. В учебном процессе Уральского государственного технического университета-УПИ результаты работы используются на механико-машиностроительном факультете при проведении лекционных и практических занятий по дисциплинам «Автоматизация конструкторского и технологического проектирования» и «Разработка САПР» со студентами специальности 230104 — Системы автоматизированного проектирования, а также в курсовом, дипломном проектировании и диссертационных исследованиях аспирантов кафедры «Информационные технологии и автоматизация проектирования».

Библиография Петунин, Александр Александрович, диссертация по теме Системы автоматизации проектирования (по отраслям)

1. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987. —248с.

2. Астраков С.Н., Ерзин А.И., Залюбовский В.В. Сенсорные сети и покрытие плоскости кругами // Дискрета, анализ и исслед. опер., 16:3 (2009), 3-19.

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

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

5. Бабаев Ф.В. Эвристический метод для решения задачи раскроя // Приборы и системы управления, 1977, № 5, С. 8-10.

6. Белякова Л.Б. Вопросы оптимального расположения конгруэнтных фигур на плоскости: Автореф.дис.канд.физ.-мат.наук.-Горький:ГГУ,1970.-13с.

7. Белякова Л.Б. Об оптимальном раскрое листового материала // Автоматизация технологического проектирования при помощи ЭЦВМ. М.: Машиностроение, 1968.-С.21-32.

8. Белякова Л.Б., Рябина Н.О. Алгоритм построения множества возможных сдвигов фигуры по заданному направлению на плоскости с областями запрета для движения. // Вычислительная техника в машиностроении. Минск, ИТК АН БССР, 1974, вып. 4, с. 9-15.

9. Борисовский П.А., Еремеев A.B. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика, №3. М.: Наука, 2004. С.3-9.

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

11. Бухвалова В.В. Реализация метода зон Липовецкого для прямоугольного раскроя // Всесоюзная н.-т. конф. "Математическоеобеспечение рационального раскроя в САПР" (Уфа, 15-18 июня 1987 г.): Тезисы докладов. Уфа, 1987. - С. 24-25

12. Бухвалова В.В., Одинцова Т.В. Схема перебора для задачи прямоугольного раскроя // Математическое моделирование в технологии машиностроения: Сборник научных трудов. Свердловск: УрО АН СССР, 1989.-С. 100-107

13. Валеева А.Ф., Петунии A.A., Файзрахманов Р.И. Применение конструктивной метаэвристики "муравьиная колония" к задаче гильотинного прямоугольного раскроя // Вестник Башкирского университета. Раздел: Математика. Уфа, 2007г., Том 12, N3, стр 12-14.

14. Васильев В.И., Ильясов Б.Г. Интеллектуальные системы управления с использованием генетических алгоритмов. Учебное пособие. Уфа: УГАТУ, 1999. - 105 с.

15. Васильев В.И., Ильясов Б.Г., Валеев C.B., Жернаков C.B. Интеллектуальные системы управления с использованием нейронных сетей. Учебное пособие. Уфа: УГАТУ, 1997. - 92 с.

16. Вельтмандер П. В. Машинная графика. Учебное пособие в 3-х книгах. НГТУ. 2000.

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

18. Верхотуров М.А. Об устойчивых алгоритмах построения годографа // Принятие решений в условиях неопределенности: Межвузовский сборник. — Уфа: УГАТУ, 1998. С. 270-284.

19. Верхотуров М.А., Логинов Е.В., Лохматов О.В. Сравнительный анализ современных автоматизированных систем нерегулярного раскроя заготовок сложных форм // Принятие решений в условиях неопределенности: Межвузовский научный сборник. —Уфа: УГАТУ, 2005.

20. Верхотуров М.А., Петренко C.B. Об одном подходе к нахождению локального экстремума задачи размещения невыпуклых ориентированныхмногоугольников в полубесконечной полосе// Межвузовский сборник научных трудов, Уфа: УГАТУ, 2005, С. 7-18.

21. Верхотуров М.А., Сергеева О.Ю. Некоторые особенности реализации упаковки геометрических объектов на базе цепного кодирования// Принятие решений в условиях неопределенности / Межвузовский сборник научных трудов. -Уфа: 1996.

22. Верхотуров М.А., Тарасенко П.Ю. Математическое обеспечение задачи оптимизации пути режущего инструмента при плоском фигурном раскрое на основе цепной резки. // Вестник УГАТУ. Управление, ВТиИТ. Уфа: Изд-во УГАТУ, 2008, Т.10, №2 (27), с. 123-130.

23. Волков И. Vericut — производственный комплекс на рабочем столе // САПР и графика. 2003, N4.

24. Галкин И.С., Петунин A.A. Использование интерфейса прикладного программирования в универсальных САПР. Научные труды XV отчетной конференции молодых ученых ГОУ ВПО УГТУ-УПИ: сборник статей в 3 ч. Екатеринбург: УГТУ-УПИ, 2009г., 4.2, С. 14-15.

25. Галкин И.С., Петунин A.A. Об одном подходе к разработке программного обеспечения для решения задачи фигурного раскроя материала //

26. Материалы конференции молодых ученых «Мавлютовские чтения» Уфа: УГАТУ, 2009, С.276-278.

27. Гамберг В.Я., Липовецкий А.И., Петунин A.A., Шевелев Л.С. Автоматизация раскроя листового проката в индивидуальном производстве. — Экспресс-информация о производственно-техническом опыте. Серия ХМ-15 — М., ЦИНТИХимнефтемаш, 1982. 2с.

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

29. Ганелина Н.Д., Фроловский В.Д. Декомпозиционный метод оптимизации проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ. // Научный Вестник НГТУ. Новосибирск: Изд-во НГТУ, 2006, №2 (23), с. 9 19.

30. Ганелина Н.Д., Фроловский В.Д. Исследование методов построения кратчайшего пути обхода отрезков на плоскости // Сибирский журнал вычислительной математики. №3, т. 9, 2006, с. 201 — 212.

31. Гери М. П., Джонсон Д. С. Вычислительные машины и трудноразрешимые задачи. М.; Мир, 1982. — 416 с.

32. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.-509 с.

33. Гиль Н.И. Математическое моделирование нерегулярного размещения плоских геометрических объектов в системах автоматизации проектирования (теоретические основы, методы, приложения): Автореф.дис.докт.техн.наук.-Минск, 1990.-32с.

34. Гиль Н.И., Комяк В.М. Об одном подходе к построению годографа вектор функции плотного размещения плоских геометрических объектов, устойчивого к вычислительной погрешности.-Харьков, 1991.-23с.-(Препринт/АН УССР, Ин-т пробл. машиностроения:350).

35. Гузаиров М.Б., Тарасов А.Е. Автоматизация проектирования раскроя стекла: проблемно-ориентированные алгоритмы конструирования рациональных карт раскроя // Системы управления и информационные технологии. 2007. № 3(29). С. 53-57.

36. Данциг Д.Б. Линейное программирование, его применение и обобщение. -М.: Прогресс, 1966.-600с.

37. Емец O.A. Интервальная математическая модель комбинаторной задачи цветной упаковки прямоугольников. / Емец O.A., Евсеева Л.Г., Романова Н.Г. //Кибернетика и системный анализ, №3. 2001. С.131-138.

38. Задача двумерной контейнерной упаковки: нижние границы и численный эксперимент с алгоритмами локального поиска оптимума / Э.А. Мухачева, А.Ф. Валеева, A.C. Филиппова, С.Ю. Поляковский // Информационные технологии. 2006. № 4. С. 45-52.

39. Задачи размещения геометрических объектов в проектировании /В.Г. Ещенко, A.B. Шишов, B.C. Тимощук, И.В. Титкин, А.И. Липовецкий, A.A. Петунии, Л.С. Шевелев. Киев, ИК АН УССР, 1981. - 31с. - (АН УССР. Ин-т кибернетики; препринт 81-81)/.

40. Залюбовский В. В. Точные и асимптотически точные алгоритмы для задач упаковки и календарного планирования // Диссертация . кандидата физико-математических наук Новосибирск, 2006. - 105 с.

41. Иванов Г.А. Проектирование размещения плоских геометрических объектов методами нелинейного программирования: Автореф.дисс. канд.техн.наук. Йошкар-Ола: МарПИ, 1993.-16с.

42. KIT-комплект. Гидроабразивная резка, лазерная, газовая и плазменная резка Электронный ресурс. — Метод доступа: URL: http://www.kit-cut.ru/ (дата обращения 21.11.09)

43. Канторович Л.В. Математические методы в организации и планировании производства Л.:ЛГУ,1939.-60с.

44. Канторович Л.В. Методы рационального раскроя металла// Производственно техн. бюллетень. -М.-1942.-35с.

45. Канторович Л.В., Горстко А.Б. Математическое оптимальное программирование.-М:Экономика, 1968.-96с.

46. Канторович Л.В., Залгаллер В.А. Расчет рационального раскроя промышленных материалов.- Л.:Лениздат,1951.-257с.

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

48. Картак В. М., Мухачева Э. А., Васильева Л. И., Петунин А. А. Задача размещения ортогональных многоугольников: модели и алгоритм покоординатной упаковки. // Информационные технологии. Москва, 2008, N3, С. 46-53.

49. Картак В.М. Матричный алгоритм поиска оптимального решения для задачи упаковки прямоугольников в полубесконечную полосу // Информационные технологии. 2008, N2. С.24-30.

50. Каспншцкая М. Ф., Сергиенко И. В., Хильченко В. И. Об одном подходе к решению задач размещения. Кибернетика, 1974, № 5, С.51-60.

51. Кац Е., Вахатов Ю., Емелин А., Старостин Н. NC Manager: визуализация, контроль и редактирование программ ЧПУ. // САПР и графика. 2000, N9. С.54-57.

52. Компания "МТС Software" САМ Software for CNC Sheet and Plate Fabrication. Электронный ресурс. — Метод доступа: URL: http://www.mtc-software.com/ (дата обращения 21.11.09)

53. Компания "New-Laser" разработка и изготовление. Электронный ресурс. - Метод доступа: URL: http://www.new-laser.ru (дата обращения 21.11.09)

54. Компания "Rosinox-Laser" плазменная резка, лазерная резка металла. Электронный ресурс. — Метод доступа: URL: http://www.rosinox-laser.ru/ (дата обращения 21.11.09)

55. Компания "SigmaTEK Systems" CAD/CAM nesting software solution for all major profile cutting and punching machines. Электронный ресурс. http ://www. sigmanest. com/

56. Компания «Algomate» automatic nesting experts Электронный ресурс. - Метод доступа: URL: http://www.algomate.com/

57. Компания ООО "TRUMPF" CAD/CAM решения. Электронный ресурс. - Метод доступа: URL: http://www.ru.trumpf.com (дата обращения 21.11.09)

58. Компания АСКОН. Электронный ресурс. Метод доступа: URL: http://ascon.ru (дата обращения 21.11.09)

59. Компания БАЗИС. Электронный ресурс. — Метод доступа: URL: http://www.bazissoft.ru (дата обращения 21.11.09)

60. Компания ЗАО «Технолазер» — лазерная резка металла. Электронный ресурс. Метод доступа: URL: http://www.technolaser.ru (дата обращения 21.11.09)

61. Коновалов И. Раскрой-это очень просто! // САПР и графика. 2002, N11. С.36-39.

62. Копорушкин П.А., Петунии A.A. Создание и обработка параметрических моделей геометрических объектов. Научные труды VIII отчетной конференции молодых ученых ГОУ ВПО УГТУ-УПИ: сборник статей в 3 ч. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005г., Ч.З, С.368-370.

63. Кочетов Ю. А. Вычислительные возможности локального поиска в комбинаторной оптимизации // Журнал вычислительной математики и математической физики. 2008. т.48, № 5. С. 788-807.

64. Кривошеев И.А. Автоматизация системного проектирования авиационных двигателей. Автореферат докторской диссертации. Уфа, изд-во УГМИ, 2000.-32 с.

65. Кривошеев И.А., Яруллин Т.Р., Сапожников A.B. и др. Методы и средства для внедрения компонентов CALS-технологии в авиадвигателестроении // Информационные технологии. Приложение к журналу. 2004, N3. -32с.

66. Кузнецов В.Ю. Задачи покрытия ортогональных многоугольников с запретными участками. // Вестник УГАТУ. Серия: «Управление, вычислительная техника и информатика», Т. 10, №2(27). Уфа: УГАТУ. 2008. С. 177-182.

67. Куликов Г.Г., Брейкин Т.В., Арьков В.Ю. Интеллектуальные информационные систе-мы: Учеб. пособие. / Уфимск. гос. авиац. техн. ун-т. -Уфа, 1999. -129 с.

68. Левский M.B. Оптимизация траектории лазерного резака при автоматической резке листовых материалов. // Автоматизация и современные технологии. 2008, №11, с. 26 31.

69. Липовецкий А.И. Геометрический подход к вычислению оптимума в задаче прямоугольного раскроя // Труды Санкт-Петербургского математического общества. 2007, Т. 13, С. 121-142.

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

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

72. Липовецкий А.И. Топологическая сортировка укладок одного класса фигур // Математическое моделирование в технологии машиностроения. УрО АН СССР, Институт машиностроения, Свердловск, 1988. — 48 с.

73. Липовецкий А.И., Петунии A.A. Использование выпуклых оболочек плоских фигур для приближенного решения задачи раскроя. Информационный листок Свердловского ЦНТИ, № 580-81. Свердловск, 1981. -4с.

74. Липовецкий А.И., Петунии A.A. Оптимизация раскроя листового материала на прямоугольные заготовки в индивидуальном производстве. -Информационный листок Свердл. ЦНТИ, №619-81. Свердловск, 1981. - 2с.

75. Липовецкий А.И.; Петунии A.A. О плотном размещении плоских выпуклых геометрических фигур. // Автоматизация проектирования в машиностроении. Минск, ИТК АН БССР, 1981, вып.З, с. 39-44.

76. Липовецкий А.И.; Петунии A.A. Проектирования раскройных карт для выпуклых плоских деталей в индивидуальном производстве. // Проектирование на ЭВМ технологических процессов и оснастки: Тез. докл. Всесоюзного совещания. Ростов-на-Дону, 1980, с. 44-46.

77. Мазурин А., Пирогов И., Пирогов В. Раскрой листового материала и ЧПУ-обработка на базе T-FLEX CAD // САПР и графика. 2000, N10. С.39-43.

78. Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Материалы конференции. -Уфа: изд. Уфимского авиационного института, 1988.- 159 с.

79. МПР инвест Электронный ресурс. Метод доступа: URL: http://www.mprs.ru/services/cutting/price/ (дата обращения 21.11.09)

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

81. Мухачева A.C. Простые эвристики для решения двумерной задачи максимального покрытия. // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Вып.2. 4.1. Уфа: УГАТУ. 2005. С.38-43.

82. Мухачева A.C. Технология блочных структур локального поиска оптимума в задачах прямоугольной упаковки // Информационные технологии. Приложение к журналу. 2004. № 5. С. 18-31.

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

84. Мухачева Э. А., Ермаченко А. И., Сиразетдинов Т. М., Усманова А. Р. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя. //Информационные технологии. -М.:2001, №6.

85. Мухачева Э.А. М.А. Верхотуров, В.В. Мартынов. Прикладные задачи исследования операций: раскрой и упаковка. // Полет. -М.: Машиностроение. 2002. С. 79-80.

86. Мухачева Э.А. Методы локального поиска оптимума в комбинаторных задачах прямоугольного раскроя-упаковки (Краткий обзор) // ОПТИМ-2001. Материалы конференции. С.-Петербург. ЦНИТС. 2001. С. 118123.

87. Мухачева Э.А. Несобственные задачи оптимального распределения двумерного ресурса: геометрические образы и генетические алгоритмы на базе их блочной структуры // Уфа: Вестник УГАТУ, 2001, №1(3). С. 111-120.

88. Мухачева Э.А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки // Дискретный анализ и исследование операций: материалы конференции. Институт математики СО РАН, Новосибирск. 2002. С. 80-87.

89. Мухачева Э.А. Проектирование прямоугольных упаковок с использованием декодеров блочной структуры. / Мухачева Э.А., Назаров Д.А., Филиппова A.C. //Автоматика и телемеханика, №6. 2006. С. 161-173.

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

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

92. Мухачева Э.А., Валеева А.Ф. Метод динамического перебора в задаче двумерной упаковки //Информационные технологии. 2000. №5. с. 30-37.

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

94. Мухачева Э.А., Валеева А.Ф., Тоцков И.Е. Методы решения задачи параллелепипедной упаковки на базе метода динамического перебора // Информационные технологии, 2001, № 1. С.21-29.

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

96. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. САПР раскроя: основные проблемы и опыт их решения. //М.: Машиностроение. Вестник компьютерных и информационных технологий. №2. 2004. -С.31-40

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

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

99. Мухачева Э.А., Зал галл ер В.А. Линейное программирование в задачах раскроя, Международный журнал программное обеспечение в инженерных знаниях. Т.З, N4, 1993, с. 463-476.

100. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя // Информационные технологии. Машиностроение. -М.: 2000, №9. -С. 15-21.

101. Мухачева Э.А., Картак В.М., Васильева Л.И. Задача планирования п-мерных упаковок графов // Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде: Сб. докладов к междунар. конференции, УРО РАН, Екатеринбург, 2000.

102. Мухачева Э.А., Мухачева A.C. Конструирование алгоритмов локального поиска оптимума прямоугольной упаковки на базе двойственных задач линейного раскроя // Информационные технологии. -М.: Новые технологии. № 6, 2002. -С. 25-30.

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

104. Мухачева Э.А., Мухачева A.C., Чиглинцев A.B. Генетический алгоритмы в задачах двумерного гильотинного раскроя // Принятие решений в условиях неопределенности : Межвуз. науч. сб. Уфа: УГАТУ, 2000.

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

106. НИП-ИНФОРМАТИКА. ТЕХТРАН. Электронный ресурс. Метод доступа: URL: http://vvww.nipinfor.ru/catalog.html?idcat=7 (дата обращения 21.11.09)

107. Новожилова М.В. Решение задачи поиска глобального экстремума линейной функции цели на структуре линейных неравенств // Препринт института проблем машиностроения. Харьков: АН УССР, 1988. 48с.

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

109. Норенков И.П. Основы автоматизированного проектирования: учебн.для студ. ВУЗов. М.: МГТУ им. Баумана, 2006. 448 с.

110. Норенков И.П., Кузьмик П.К. Информационная поддержка наукоемких изделий. CALS-технологии. М.: Изд-во МГТУ им. Н.Э.Баумана, 2002.-320 с.

111. Панюкова Т.А. Обходы с упорядоченным охватыванием в плоских графах // Дискретный анализ и исследование операций. 2006, т. 13, № 2, с. 3143.

112. Панюкова Т.А. Последовательности цепей с упорядоченным охватыванием. // Известия РАН. Теория и системы управления. 2007, N 1. С. 88-97.

113. Панюкова Т.А. Построение маршрутов с упорядоченным охватыванием в плоских графах // Труды 36-й Региональной молодежной конференции. Проблемы теоретической и прикладной математики. Екатеринбург: УрО РАН, 2005. С. 61-66.

114. Пападимитроу X. Комбинаторная оптимизация. Алгоритмы и сложность. Пер. с англ. / Пападимитроу X., СтайглицК. М.: Мир, 1985 -512с.

115. Петров A.A., Кобелев A.B. Кукушкин В.А., Виниченко В.Н., Острокопытов Д.А. Опыт использования AutoCAD на «Севмаше» // Судостроение 3'2002 (742) май-июнь.

116. Петунин А.А, Беседин A.A., Гамберг В.Я., Геймур В.В., Ковальков

117. B.Н. Централизация раскройно-заготовительного производства на базе автоматизированных технологических линий раскроя листового металлопроката // Тяжелое машиностроение. М.: Машиностроение, N7, 1993г.1. C. 19-22

118. Петунин A.A. Автоматизация нерегулярного фигурного раскроя: основные подходы к разработке систем проектирования раскроя и управляющих программ для машин резки листовых материалов // Информационные технологии. Москва, 2009, N10, С.29-34.

119. Петунии A.A. Алгоритмы и программы раскроя листового материала в индивидуальном производстве: Автореф. дисс. канд. техн. наук. — Свердловск: УПИ, 1982.

120. Петунии A.A. Интегрированная САПР «Сириус» // КомпьютерМэн. Екатеринбург: изд-во «Комсомольская Правда — Урал», N6,1996. С.9-12.

121. Петунии A.A. Методы укладки прямоугольников в заданной последовательности и их программная реализация. // Математическое обеспечение расчетов линейного и прямоугольного раскроя. Материалы Всесоюзного семинара. Уфа, 1981, с 142-145.

122. Петунии A.A. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестник УГАТУ. Уфа, 2009, Т. 13, № 2 (35). С. 280-286.

123. Петунии A.A. Об автоматическом выборе метода оптимизации прямоугольного раскроя // Программные продукты и системы. 2009. № 4 (88). С. 143-145.

124. Петунии A.A. Программные средства перевода символьной информации с ЕС ЭВМ на ЭВМ NORD-IOOCX и обратно,- Информационный листок Свердловского ЦНТИ, №639-87. Свердловск, 1987. - 4с.

125. Петунии A.A. Промышленные системы автоматизированного проектирования // Методические материалы по изучению курса «Разработка САПР» для студентов специальности САПР. Екатеринбург: УГТУ, 1998. 40с.

126. Петунин A.A., Валеева А.Ф. Параллелепипедная упаковка: алгоритмы, численный эксперимент и практические расчеты // Информационные технологии. Москва, 2007, N12, С. 43-50.

127. Петунин A.A., Галкин И.С О применении API T-FLEX CAD при разработке подсистемы автоматизированного проектирования раскроя материала // САПР и Графика Москва, 2008, N12, С.86-88.

128. Петунин A.A., Галкин И.С. САПР и .NET. Научные труды XI отчетной конференции молодых ученых ГОУ ВПО УГТУ-УПИ: сборник статей в 3 ч. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2007г., Ч.З, С. 287-289.

129. Петунин A.A., Гамберг В.Я., Кротов В.И. Система автоматизированного проектирования раскроя материалов и автоматизация раскроя металлопроката на базе машин с ЧПУ для термической резки металла // «Титан». М. ВИЛС, N2, 1993г. С.56-58.

130. Петунин A.A., Кротов В.И., Уколов С.С., Видяпин В.В. САПР «Сириус» оптимизация раскроя и резки листовых материалов // САПР и графика. Москва: изд-во «Компьютер Пресс», N10, 1999г. С.42-47.

131. Петунин A.A., Куреннов Д.В., Полевов A.B. Об одном подходе к решению задач раскроя-упаковки // Вестник УГТУ-УПИ. Конструирование и технология изготовления машин: Сборник научных трудов. Часть 2.Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005, N18(70), С.212-216.

132. Петунии A.A., Мухачева Э.А., Филиппова A.C. Метод прямоугольной аппроксимации для решения задач нерегулярного фигурного раскроя упаковки // Информационные технологии. — Москва, 2008, N1, С. 2831.

133. Петунин A.A., Полевов A.B., Куреннов Д.В. Об одном подходе к решению задач раскроя-упаковки // Конструирование и технология изготовления машин. Сборник научных трудов. 42. Вестник УГТУ-УПИ. -Екатеринбург: УГТУ-УПИ, 2005, N18(70), С.212-216.

134. Петунин A.A.; Липовецкий А.И. Об изменении метрик на множестве перестановок и решении задач размещения геометрических объектов. //Автоматизация проектирования технологических процессов. Минск, ИТК АН БССР, 1982, вып. 1, с. 154-159.

135. Полевов А. В. Алгоритмы автоматического раскроя листового материала в условиях единичного производства. // Диссертация на соисканиеученой степени кандидата технических наук. Уральский государственный технический университет. Екатеринбург, 2005, 127с.

136. Полевов A.B., Петунии A.A. Nest Class Library. Научные труды VII отчетной конференции молодых ученых ГОУ ВПО УГТУ-УПИ: сборник статей в 2 ч. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005г., 4.2, С.212-214.

137. Полевов A.B., Петунин A.A. Информационная система планирования для интегрированной САПР «Сириус» //Конструирование и технология изготовления машин. Сборник научных трудов. Екатеринбург. Вестник УГТУ-УПИ: изд-во УГТУ-УПИ, N3(11), 2000г. С.62-65.

138. Пономаренко JI. Д., Макмак П. М. Новые подходы к минимизации на перестановках при упаковке геометрических объектов. // Теория и методы автоматизации проектирования. Минск, ИТК АН БССР, 1980, вып. 4, с. 8-14.

139. Программирование для Windows 95; в 2-х томах. Чарльз Петзолд. пер. с англ. СПб.: BHV - Санкт-Петербург, 1997 - 752 е., ил.

140. Программы для профессионального производства мебели. Программа АСТРА Раскрой. Электронный ресурс. Метод доступа: http://www.astrapro.ru/astranest.asp (дата обращения 21.11.09)

141. Программы раскроя листовых материалов. Программа раскроя Astra S-Nesting. Электронный ресурс. Метод доступа: URL: http://nesting.astrapro.ru/astra-nesting.asp (дата обращения 21.11.09)

142. Пушкарёва Г.В. Генетическое программирование при автоматизированном проектировании управляющих программ для систем ЧПУ // Сборник научных трудов НГТУ. 2004. №1. - С. 67-72.

143. Пушкарёва Г.В. Применение гибридного генетического алгоритма для оптимизации маршрутов. // Автометрия, 2006, № 2, т. 42, с. 68-79.

144. Пшеничный Б. Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980. - 320с.

145. Рвачев В. JL, Стоян Ю. Г., Глушко А. Г. К вопросу о поиске абсолютного экстремума в одной задаче оптимального раскроя. //Алгоритмические языки и автоматизация программирования. Киев, 1966, вып. 2, с. 70-81.

146. Рвачев B.JI. Теория R-функций и некоторые ее приложения. -Киев: Наук. Думка, 1982.- 552 с.

147. Роджерс Дэвид Алгоритмические основы машинной графики, М.:«Мир», 1989. 504 с.

148. Романова Т.Е. Интервальное пространство 15п.ЗУ/Докл. HAH. Украина. 2000. №9. С. 36-41.

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

150. Савлов С.Ф. Построение нерегулярных укладок неориентированных многоугольников // Матем.обесп-е рацион-ого раскроя в системахавтоматизированного проектирования:Материалы Всесоюзной конференции. -Уфа, 1988. -С.118-120.

151. Саенко А. «ТЕХТРАН: современное средство оптимизации раскроя листового материала». Оборудование и инструмент для профессионалов. Серия «Металлообработка». 2008 г., N6, с.66-67.

152. САПР АССОЛЬ. Системы автоматизированного проектирования и управления производством. Электронный ресурс. — Метод доступа: URL: http://assol.mipt.ru/rus/center/news.shtml (дата обращения 21.11.09)

153. САПР ЧПУ ТИГРАС. Электронный ресурс. Метод доступа: URL: http://www.tigras.ru (дата обращения 21.11.09)

154. Стоян Ю. Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. Киев: Наук, думка, 1976. — 247с.

155. Стоян Ю.Г. Адаптация метода ветвей и границ для решения задачи размещения прямоугольников с учетом минимально и максимально допустимых расстояний. / Стоян Ю.Г., Аристова И.В., Яськов Г.Н. Харьков: HAH Украины. Ин-т пробл. Машиностроения, 1995.

156. Стоян Ю.Г. Выпуклые интервальные многоугольники // Доп. HAH Украины, №5. 2000. С.33-39.

157. Стоян Ю.Г. Комбинаторная оптимизационная задача размещения прямоугольников с учетом погрешностей в исходных данных. / Стоян Ю.Г., Романова Т.Е., Евсеева Л.Г. //Докл. HAH Украины, №7. 1997. С.56-60.

158. Стоян Ю.Г. Оптимизационная задача размещения правильных интервальных многоугольников. / Стоян Ю.Г., Романова Т.Е., Сысоева Ю.А. // Докл. HAH Украины, №9. 1998. С.114-120.

159. Стоян Ю.Г., Емец O.A. Теория и методы евклидовой комбинаторной оптимизации. Киев: Ин-т систем исследований образований. 1993. 188с.

160. Стоян Ю.Г., Новожилова М.В., Карташов A.B. Математическая2модель и оптимизация линейных Е (R ) задач размещения. - Харьков, 1991.к44с. (Препринт /АН УССР. Ин-т пробл. Машиностроения: №353).

161. Стоян Ю.Г., Соколовский В.З. Решение некоторых многоэкстремальных задач методом сужающихся окрестностей. Киев: Наук, думка, 1980. - 208с.

162. Стоян Ю.Г., Соколовский В.З., Пономаренко Л.Д. Метрики в пространстве перестановок и методы решения многоэкстремальных задач. -Харьков: Ин-т проблем машиностроения АН УССР, 1977, препринт № 69. 32с.

163. Стоян Ю.Г., Черепахин В.М. Об одном способе рационального размещения кругов в полосе. // Тез. докл. и сообщ. на Всесоюз. межвуз. симпоз. по прикл. математике и кибернетике. Горький, 1967, с. 176.

164. Стоян Ю.Г., Шайтхауер Г. и др. Класс поверхностей О-уровня Ф-функций точечных множеств с границей окружность или многоугольник// Проблемы машиностроения.-2000.-Т.З. №12, ч. С. 117-123.

165. Стоян Ю.Г., Яковлев C.B. Математические модели и оптимизационные методы геометрического проектирования. Киев. : Наук, думка, 1986. - 286с.

166. Топ Системы. Российский программный комплекс T-FLEX CAD/CAM/CAE/CAPP/PDM. Электронный ресурс. Метод доступа: URL: http://www.topsystems.ru (дата обращения 21.11.09)

167. Филиппова А. С. Кузнецов В.Ю. Задачи о минимальном покрытии ортогональных многоугольников с запретными участками // Информационные технологии, №9(145). 2008. С.60-65.

168. Филиппова A.C. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе технологии блочных структур // Информационные технологии. 2006, №6. 36 с.

169. Фроловский В. Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ // Информационные технологии в проектировании и производстве. № 4. М. 2005. С. 63-66.

170. Фроловский В. Д. Оптимальное группирование геометрических объектов при проектировании карт раскроя материалов // Программные продукты и системы. 2000, N3. С.47-48.

171. Фроловский В. Д. Моделирование и алгоритмизация процессов геометрического проектирования изделий из листового материала // Автореф.дис.докт.техн.наук -Новосибирск. 2001. -36с.

172. Фроловский В.Д. Исследование методов построения кратчайшего пути обхода отрезков на плоскости // Сибирский журнал вычислительной математики. Новосибирск, РАН, Сиб. отд-ние, 2006. -Т 9, № 3. -С. 201-212.

173. Юрьев В.Л. Автоматизация определения оптимальных параметров при нестационарных условиях резания. М: Отраслевая библиотека авиационной промышленности. 1992 . 144с.

174. Юрьев В.Л. Совершенствование технологических процессов нестационарной механической обработки сложнофасонных деталей газотурбинных двигателей. Уфа: Министерство образования и науки Российской Федерации. 2004,- 131с.

175. Юсупова Н.И. Миронов В.В. ХМЬ-технологии в базах данных. Введение. (С грифом УМО). Учебное пособие. Уфимский государственный технический университет Уфа: УГАТУ, 2004. -182 с. — (Серия Сотри!).

176. Aarts E., Lenstra J.K. (eds.) Local search in combinatorial optimization // John Wiley & Sons Ltd, 1997.-315p.

177. Aarts L., Van Laarhoven P. Statistical cooling: a general approach to combinatorial optimization problems // Philips J.Res 40, 1985, pp. 193-226.

178. Adobe Photoshop CS4 Электронный ресурс. Метод доступа: URL: http://www.adobe.com/products/photoshop/photoshop/ (дата обращения 21.11.09)

179. Akiyama J. Variations of the tiling problem. /Akiyama J., Nakamura G. // Oxford University Press. 2008.

180. Anil Kumar V.S., Ramesh H. Covering Rectilinear Polygons with Axis-Parallel Rectangles // Information and Control. 1999, V.63. N 3. P. 164-189.

181. Art R.C. An approach to the two dimensional irregular cutting stock problem // IBM Cambridge Scientific Centre, Report 36-Y08, 1966.

182. Autodesk Электронный ресурс. Метод доступа: URL: http ://www. autodesk.ru (дата обращения 21.11.09)

183. Beasley J. E. An exact two-dimensional non-quillotine cutting tree search procedure // Operation. Research 33 (1985), pp. 49-64.

184. Beasley J.E., 1985a. Bounds for two-dimensional cutting // Journal of the Operational Research Society 36, 71-74.

185. Beasley, J.E., 1985c. Algorithms for unconstrained two-dimensional guillotine cutting // Journal of the Operational Research Society 36, 297-306.

186. Beasley, J.E., 2004. A population heuristic for constrained two dimensional non-guillotine cutting // European Journal of Operational Research 156, 601-627.

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

188. Benell J. A., Dowsland K. A., Dowsland W. The irregular cutting-stock problem a new procedure for deriving the no-fit polygon // Computers ¿¿Operations Research 28 (2001), pp. 271-287

189. Benell, J.A., Dowsland, K.A., 2001. Hybridising tabu search with optimisation techniques for irregular stock cutting // Management Science 47, 11601172.

190. Berman P. Approximating rectilinear polygon cover problems / Berman P., DasguptaB. // Algorithmica. #17(4). 1997. P.331-356.

191. Birgin, E.G., Martinez, J.M., Ronconi, D.P., 2005. Optimizing the packing of cylinders into a rectangular container: A nonlinear approach // European Journal of Operational Research 160,19-33.

192. Bischoff, E.E., Janetz, F., Ratcliff, M.S.W., 1995. Loading pallets with non-identical items // European Journal of Operational Research 84, 681-692.

193. Bischoff, E.E., Marriott, M.D., 1990. A comparative evaluation of heuristics for container loading // European Journal of Operational Research 44, 267276.

194. Bischoff, E.E., Ratcliff, M.S.W., 1995. Loading multiple pallets // Journal of Operational Research Society 46, 1322-1336.

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

196. Bortfeldt, A., Gehring, H., 2001. A hybrid genetic algorithm for the container loading problem // European Journal of Operational Research 131, 143— 161.

197. Bortfeldt, A., Gehring, H., Mack, D., 2003. A parallel tabu search algorithm for solving the container loading problem // Parallel Computing 29, 641662.

198. Bresenham J. A linear algorithm for incremental digital display of circular arcs // Commun. ACM.- 1977.- Vol. 20, no. 2, 100-106.

199. Bronnimann H., Goodrich M. Almost optimal set covers in finite VC-dimension//Discrete comput. Geom., #14. 1995. P.263-279.

200. Carnieri, С., Mendoza, G.A., Gavinho, L.G., 1994. Solution procedures for cutting lumber into furniture parts // European Journal of Operational Research 73, 495-501.

201. Carravilla, M.A., Ribeiro, C., Oliveira, J.F., 2003. Solving nesting problems with non-convex polygons by constraint logic programming. // International Transactions in Operational Research 10, 651-664.

202. Chen, C.S., lee, S.M., Shen, Q.S., 1995. An analytical model for the container loading problem // European Journal of Operational Research 80, 68-76.

203. Cheng Y. A new method for image compression using irreducible covers of maximal rectangles. / Cheng Y., Iyegnar S.S., Kashyap R.L. // IEEE transactions on software engineering. V.14, #5. 1988. P.651-658.

204. Christofides, N., Hadjiconstantinou, E., 1995. An exact algorithm for general, orthogonal, two-dimensional knapsack problems // European Journal of Operational Research 83, 39-56.

205. Christofides, N., Whitlock, C., 1977. An algorithm for twodimensional cutting problems // Operations Research 25, 30-44.

206. Chu, C., La, R., 2001. Variable-sized bin packing: Tight absolute worst-case performance ratios for four approximation algorithms // SIAM Journal on Computing 30, 2069-2083.

207. Cohen M. F. Wang Tiles for image and texture generation / Cohen M. F., Shade J., Hiller S., Deussen O.// ACM Trans. Graphics, #22(3). 2003. P.287-294.

208. Consult+. Автоматизированные решения производства одежды. Электронный ресурс. — Метод доступа: URL: http://www.consultplus-bg.com/ru/ (дата обращения 21.11.09)

209. Corel Электронный ресурс. Метод доступа: URL: http://www.corel.ru (дата обращения 21.11.09).

210. Correia, М.Н., Oliveira, J.F., Ferreira, J.S., 2000. Cylinder packing by simulated annealing // Pesquisa Operacional 20, 269-286.

211. Correia, M.H., Oliveira, J.F., Ferreira, J.S., 2001. A new upper bound for the cylinder packing problem // International Transactions in Operational Research 8, 571-583.

212. Daniels K., Li Z., Milenkovic V.J. Automatic marker making // In: Proc.rd

213. Canadian conf. On Computational geometry, ed. T.Shermer, August, 1991.pp.ll-24.

214. Dowsland, K.A., 1987. An exact algorithm for the pallet loading problem // European Journal of Operational Research 31, 78-84.

215. Dyckhoff H. Cutting and packing in production and distribution. / Dyckjoff H., Finke U. // Berlin: Springer Verlag, 1992.

216. Dyckhoff H. Typology of cutting and packing problems // European journal of operational research, #44. 1990. P. 145-159.

217. Dyckhoff, H., 1981. A new linear programming approach to the cutting stock problem // Operations Research 29, 1092-1104.

218. EURO Special Interest Group on Cutting and Packing Электронный ресурс . —Режим доступа: http://paginas.fe.up.pt/~esicup/

219. Fekete S., Schepers J. A combinatorial characterization of higher dimensional orthogonal packing // Mathematics of Operations Research 2004 29. P. 353—368.

220. Folkenauer E. The grouping genetic algorithms for Bin-Packing // JORBEL-Belgian Journal of Operations Research, Statistics and Computer Science. 1995, vol 35, pp. 64-88.

221. ForsterH., Wascher G. Simulated annealing for order spread minimization sequencing cutting patterns. // European Journal of Operational Research. 1998. 110. P. 272-281.

222. Fortune S., Milencovic V. Numerical stability of algorithms for line arrangements, 7-th annual ACM SCG, 1991, pp.334-341.

223. Fowler R. J. Optimal packing and covering in the plane are NP-complete. / Fowler R.J., Paterson M.S., Tatimoto S.L. // Information Proc. Let., #12. 1981. P.133-137.

224. Freeman, H. and Shapira, R. Determining the minimum area encasing rectangle for an arbitrary closed curve. // Comm.ACM.18(7), pp.409 - 413 (1975).

225. Ganelina N.D., Frolovsky V.D. Ant Colony Approach to Defining Hamilton Cycle on Segments // KORUS 2005, Proceedings of the 9th Russian-Korean International Symposium on Science and Technology, 26 June 2 July 2005, NSTU, Russia, Vol.1, p.601 -603

226. Ganelina N.D., Frolovsky V.D. Colony Approach to Defining Hamilton Cycle on Segments // KORUS 2005, Proceedings of the 9th Russian-Korean International Symposium on Science and Technology, 26 June 2 July 2005, NSTU, Russia, Vol.1, p.601-603.

227. Ganelina N.D., Frolovsky V.D. Constructing tours on a set of plane geometric objects // Proceedings of the 9th International Workshop on Computer

228. Science and Information Technologies (CSIT"2007), Ufa-Krasnousolsk. Russia. 2007. V 2. pp.216-221.

229. Gehring H. A genetic algorithm foe solving the container loading problem. / Gehring H., Bortfeld A. // International transactions in operational research, V.4, #5/6. 1997. P401-418.

230. George J. A. Multiple container packing: a case study of pipe packing // Journal of the Operational Research Society, #47. 1996. P. 1098-1109.

231. George J.A. Packing different-sized circles into a rectangular container /George J. A., George J.M., Lamar B.W. // European Journal of Operational Research, #84. 1995. P.693-712.

232. George, J.A., 1992. A method for solving container packing for a single size of box // Journal of the Operations Research Society 43, 307-312.

233. George, J.A., George, J.M., Lamar, B.W., 1995. Packing different-sized circles into a rectangular container // European Journal of Operational Research 84, 693-712.

234. George, J.A., Robinson, D.F., 1980. A heuristic for packing boxes into a container // Computers & Operations Research 7, 147-156.

235. Gilmore P. C., Gomory R. E. The theory and computation of knapsack functions // Oper. Res, 1966,14, pp. 145-17

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

237. Gilmore, P.C., Gomory, R.E., 1963. A linear programming approach to the cutting-stock problem-Part II // Operations Research 11, 864-888.

238. Gilmore, P.C., Gomory, R.E., 1965. Multistage cutting stock problems of two and more dimensions // Operations Research 13, 94-120.

239. Glover F. Tabu search and adaptive memory programming advances, applications and challenges. // Interfaces in computer science and operational research. 1996. P. 1-75.

240. Goldberg D. Genetic algorithms in search // Optimization and machine learning, Adision-Wesley publ., 1989. 99 p.

241. Gradis~ar, M., Kljajicr, M., Resinovicw, G., Jesenko, J., 1999. A sequential heuristic procedure for one-dimensional cutting // European Journal of Operational Research 114, 557-568.

242. Gudmundsson J. Close approximations of minimum rectangular coverings / Gudmundsson J., Levcopoulos C. //FST&TCS'96. LNCS,V.1180. 1996. P.135-146.

243. Gudmundsson J. Lower bounds for approximate polygon decomposition and minimum gap / Gudmundsson J., Levcopoulos C. // Information Processing Letters, V.81, Issue 3. 2002. P.137-141.

244. Heckmann R., Lengauer T. A simulated annealing approach to the nesting problem in the textile manufacturing industry. // Annals of OR, 57, pp. 103-133, 1995.

245. Heckmann R., Lengauer T. Computing closely matching upper and lower bounds on textile nesting problems. // European Journal of Operational Research, 108, 1998, pp. 473-489.

246. Hifi, M., 1998. Exact Algorithms for the Guillotine Strip Cutting/Packing Problem // Computers & Operations Research. Vol. 25, No 11, pp. 925-940.

247. Hifi, M., M'Hallah, R., 2004. Approximate algorithms for constrained circular cutting problems // Computers & Operations Research 31, 675-694.

248. Hifi, M., Ouafi, R., 1998.Abest-first branch-and-bound algorithm for orthogonal rectangular packing problems // International Transactions in Operational Research 5, 345-356.

249. Holland J. H. Adaptation in Natural and Artificial System. Ann Arbor: The University of Michigan Press, 1975. 96 p.

250. Home of Cutting. Электронный ресурс. Метод доступа: URL: http://www.cuttinghome.ru (дата обращения 21.11.09)

251. Imahori S. Local search algorithms for the rectangle packing problem with general spatial costs / Imahori S., Yagiura M., Ibaraki T. // Mathematical programming, #97. 2003. P.543-569.

252. Jacobs, S., 1996. On genetic algorithms for the packing of polygons. European Journal of Operational Research 88, 165-181.

253. JETCAM CADCAM nesting & material life management software for sheet metal and aerospace industries. Электронный ресурс. — Метод доступа: URL: http://www.jetcam.com (дата обращения 21.11.09)

254. Johnson D.S. Approximation algorithms for combinatorial problems // Journal of omputing and systems sciences, #9. 1974. P.256-278.

255. Kang, J., Park, S., 2003. Algorithms for the variable sized bin packing problem // European Journal of Operational Research 147, 365-372.

256. Kari J. Deterministic aperiodic tile sets / Kari J., Papasoglu P. // Geometric and functional analysis, #9. 1999. P.353-369.

257. Katagiri, H., Ishii, H., Sakawa, M., 2004. On fuzzy random linear knapsack problems. Central European Journal of Operations Research 12, 59-70.

258. Kaucher E. Interval Analysis in the Extended Interval Space IR // Сотр. Suppl., #2. 1980. P.33-49.

259. Kolountzakis M. The Steinhaus tiling problem and the range of certain quadratic forms / Kolountzakis M., Papadimitrakis M.N. // J. Math., #46. Illinois. 2002. P.947-951.

260. Labber, M., Laporte, G., Martello, S., 2003. Upper bounds and algorithms for the maximum cardinality bin packing problem // European Journal of Operational Research 149, 490-498.

261. Li, Z., Milenkovic, V., 1995. Compaction and separation algorithms for non-convex polygons and their applications // European Journal of Operational Research 84, 539-561.

262. Lieng J., Thulasiraman K. A Genetic Algorithm for Channel Routing in VLSI Circuits //Evolutionary Computation.- MIT, 1994, 1(4). P. 293-311

263. Lins, L., Lins, S., Morabito, R., 2002. An n-tet graph approach for nonguillotine packings of n-dimensional boxes into an n container. // European Journal of Operational Research 141, 421-439.

264. Lodi, A., Martello, S., Monaci, M., 2002a. Two-dimensional packing problems: A survey // European Journal of Operational Research 141, 241-252.

265. Lodi, A., Martello, S., Vigo, D., 2002b. Recent advances on twodimensional bin packing problems // Discrete Applied Mathematics 123, 379396.

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

267. Lodi, A., Martello, S., Vigo, D., 2004. Models and bounds for two-dimensional level packing problems // Journal of Combinatorial Optimization 8, 363379.

268. Lorie, J.H., Savage, L.J., 1955. Three problems in rationing capital // Journal of Business 28, 229-239.

269. Loris F. An application of simulated annealing to the cutting stock problem // European journal of operational research, #114. 1999. P.532-556.

270. Lovasz L. On the ratio of optimal integral and fractional covers // Journal of discrete mathematics, #13. 1975. P.383-390.

271. Marinescu D. An integer programming model for two-dimensional cutting stock problem with several support plates // Seminar of Optimization Theory, Cluj -Napoca 1985, Report No. 5, pp. 85 94.

272. Martello S., Vigo D. Exact solution of two-dimensional finite bin packing problem//Managment Science. 1997. Vol. 35. P. 64—68.

273. Martello, S., Monaci, M., Vigo, D., 2003. An exact approach to the strip-packing problem // INFORMS Journal on Computing 15, 310-319.

274. Martello, S., Pisinger, D., Toth, P., 2000. New trends in exact algorithms for the 0-1 knapsack problem // European Journal of Operational Research 123, 325332.

275. Martello, S., Vigo, D., 1998. Exact solution of the two-dimensional finite bin packing problem // Management Science 44, 388-399.

276. Masek W.J. Some NP-complete set covering problems // Manuscript. MIT, 1977.

277. Mauldin R.D. Comments about the Steinhaus tiling problem / Mauldin R.D., Yingst A. //Proc. Amer. Math. Soc., #131. 2003.

278. Milenkovic V, Daniels K, Li Z, Placement and compaction of non convex polygons for clothing manufacture // Fourth Canadian Conference on Computational Geometry, St John's, Newfoundland, 1992.

279. Milenkovic V. J., Daniels K. Translational polygon containment and minimal enclosure using mathematical programming //ITOR special issue with papers wrom rFOS'96, 1996, 30 p.

280. Milenkovic V.J. Multiple translational containment, part II: exact algorithms // Algorithmica special issue on Computational geometry in manufacturing, 1994, 40p.

281. Milenkovic, V.J., Daniels, K., 1999. Translational polygon containment and minimal enclosure using mathematical programming. // International Transactions in Operational Research 6, 525-554.

282. Miyazawa, F.K., Wakabayashi, Y., 1997. An algorithm for the three-dimensional packing problem with asymptotic performance analysis // Algorithmica 18, 122-144.

283. Miyazawa, F.K., Wakabayashi, Y., 2003. Cube packing // Theoretical Computer Science 297, 355-366.

284. Morabito, R., Arenales, M.N., 1996. Staged and constrained two-dimensional guillotine cutting problems: An AND/ORgraph approach // European Journal of Operational Research 94, 548-560.

285. Morabito, R., Morales, S., 1998. A simple and effective recursive procedure for the manufacturer's pallet loading problem // Journal of the Operational Research Society 49, 819-828.

286. Mukhacheva E.A., Kartack V.M. Exact Algorithms for Solving N-dimensional Bin-Packing Problems. San-Antonio, INFORMS-2000.

287. Mukhacheva E.A., V.Kartak., L.Vasilyeva Exact Algorithms for solving N-Dimentional bin-Packing Problems // 1NFOMS, Annual Meeting, San Antonio, Fall 2000.

288. Mukhacheva E.A., Valeeva A.F., Mukhacheva A.S. In Rectagular Bin-Packing Problem Based on Its Block Structura // Computer Science and Information Technologies. USATU, 2000.

289. Neville E.H. On the solution of numerical functional equations, illustrated by an account of a popular puzzle and of its solution // Proc. London Math. Soc., #14. 1915. P.308-326.

290. Oliveira, J.F., Ferreira, J.S., 1993. Algorithms for nesting problems // In: Vidal, R.V.V. (Ed.), Applied Simulated Annealing, Lecture Notes in Economics and Mathematical Systems, vol. 396. Springer, Berlin et al, pp. 255-273.

291. Oliveira, J.F., Gomes, A.M., Ferreira, J.S., 2000. TOPOS A new constructive algorithm for nesting problems. // OR Spektrum 22, 263-284.

292. OR-Library Электронный ресурс. — Режим доступа: http://people.brunel.ac.uk/~mastjjb/jeb/info.html.

293. O'Rourke J., Chien C.B., Olson Т., Naddor D. A new linear algorithm for intersecting convex polygons // Computer Graphics and Image Processing. 1982. V.19. P. 384-391.

294. Panyukova T.A. Routing problems for cutting processes // Proc. of 10th International Workshop on Computer Science and Information Technologies (CSIT'2008), Antalya, Turkey. Vol.2, USATU, Ufa, Russia, 2008, pp. 100-105.

295. Pisinger, D., 1999. An exact algorithm for large multiple knapsack problems // European Journal of Operational Research 114, 528-541.

296. Pisinger, D., 2002. Heuristics for the container loading problem // European Journal of Operational Research 141, 382-392.

297. Ratcliff, M.S.W., Bischoff, E.E., 1998. Allowing for weight considerations in container loading // OR Spektrum 20, 65-71.

298. Riehme, J., Scheithauer, G., Terno, J., 1996. The solution of twostage guillotine cutting stock problems having extremely varying order demands. European Journal of Operational Research 91, 543-552.

299. Scheithauer G., Wascher G. The Bin-Packing Problem: a Problem Generator and Some Numerical Experiments with FDD Packing and MTP // International Transactions in Operational Research. 1997, N 4. P.337-339.

300. Scheithauer, G., 1991. A three-dimensional bin packing algorithm // Journal of Information Processing and Cybernetics 27, 263-271.

301. Scheithauer, G., 1999. LP-based bounds for the container and multicontainer loading problem // International Transactions in Operational Research 6, 199-213.

302. Schilling, K.E., 1990. The growth of m-constraint random knapsacks. European Journal of Operational Research 46, 109-112.

303. SigmaTEK Systems CAD/CAM nesting software solution for all major profile cutting and punching machines. Электронный ресурс. - Метод доступа: URL: http://www.sigmanest.com (дата обращения 21.11.09)

304. SolidWorks Russia Электронный ресурс. Метод доступа: URL: http://www.solidworks.ru (дата обращения 21.11.09)

305. Stoyan Y.G., Yaskov G.N. A method of optimal lattice packing of congruent oriented polygons in the plane. // European Journal of Operational research. 2000, 124:204-216.

306. Stoyan YG, Ponomarenko LD, Minkowski sum and hodograph of the dense placement vector function. Report of the SSR Academy of Science, SER.A 10, 1977.

307. Stoyan Yu. Packing of various radii solid spheres into a parallelepiped / Stoyan Yu., Yaskov G., Scheithauer G. // Preprint MATH-NM-17-2001. Dresden: Technical University of Dresden, 2001.

308. Stoyan Yu.G. Analytical description of interactions of point sets // Journal of mechanical engineering, V.4, №1-2. 2001. P. 77-88.

309. Stoyan Yu.G. Construction of a Ф-fimction for two convex polytopes / Stoyan Yu.G., Terno J., Gil M., Romanova Т., Scheithauer G. // Applicationes Mathematical V. 2, №29. 2002. P.199-218.

310. Stoyan Yu.G. The extended interval space and elementary mappings // Proc of the IMACS-GAMM Intern. Symp. on Numerical Methods and Error Bounds. Oldenburg. 1995. P.270-279.

311. Stoyan Yu.G. Ф-function and its basic properties // Докл. HAH Украины. Сер. A, №8. 2001. P. 112-117.

312. Stoyan Yu.G. Ф-function for 2D primary objects / Stoyan Yu.G., Terno J., Scheithauer G., Gil N., Romanova T. // Studia Informatica, V.2,№1. Paris. 2002. P.l-32.

313. Stoyan Yu.G. Ф-function for complex 2D objects / Stoyan Yu.G., Scheithauer G., Gil M., Romanova T. // 40R Quarterly Journal of the Belhian, French and Italian Operations Research Societies, V. 2, #1. 2004. P.69-84.

314. Stoyan Yu.G. Ф-function for primary 3D objects / Stoyan Yu.G., Scheithauer G., Pridatko D., Romanova T. // Prepr. Dresden : Technische Univarsitat Dresden, 2002. P.27

315. Stoyan Yu.G., Novozhilova M.V., Kartashov A.V., Mathematical model and method of searching for a local extremum for non-convex oriented polygons allocation problem, European Journal of Operation Research 92 (1996), -pp. 193-210.

316. Stoyan, Y.G., Patsuk, V.N., 2000. A method of optimal lattice packing of congruent oriented polygons in the plane. European Journal of Operational Research 124, 204-216.

317. Stoyan, Y.G., Yaskov, G.N., 1998. Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints. International Transactions in Operational Research 5, 4557.

318. T. Odinzowa. Optimal packing of rectangles. Электронный ресурс. — Метод доступа: http://www.optipacker.de (дата обращения 21.11.09).

319. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische. Losung.-Leiprig, 1987, pp.207-217.

320. Terno J., Scheithauer G., Sommerwei U., Riehme J. An efficient approach for the multi-pallet loading problem // European Journal of Operational research. 2000, 123: 372-381.

321. Vanderbeck, F., 2001. A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem // Management Science 47, 864-879.

322. Waescher, G., 1990. An LP-based approach to cutting stock problems with multiple objectives I I European Journal of Operational Research 44, 175-184.

323. Waescher, G., Gau, T., 1996. Heuristics for the integer onedimensional cutting stock problem: A computational study // OR Spektrum 18, 131-144.

324. Waesher G., Haussner H., Shumann II. An improved typology of cutting and packing problems. // European Journal of Operational research. 2007, 183:11091130.

325. Yaodong Cui, Tianlong Gu, Wei Hu. Simplest optimal guillotine cutting patterns for strips of identical circles // Journal of Combinatorial Optimization. 2008, 15 (4): 357-367

326. Yaodong Cui, Xiaoxia Song. Applying parallelogrammic strips for cutting circles from stainless steel rolls // Journal of Materials Processing Technology. 2008, 205 (1-3): 138-145.

327. Yaodong Cui. Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors // European Journal of Operational Research. 2006, 169 (1): 30-40

328. Yaodong Cui. Qiang Wang. Exact and heuristic algorithms for the circle-cutting problem in the manufacturing industry of electric motors // Journal of Combinatorial Optimization. 2007, 14 (1): 35-44.

329. Yuen, B.J., 1995. Improved heuristics for sequencing cutting patterns // European Journal of Operational Research 87, 57- 64.

330. Yuen, B.J., Richardson, K.V., 1995. Establishing the optimality of sequencing heuristics for cutting stock problems // European Journal of Operational Research 84, 590-598.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00