Проектирование нерегулярного раскроя листовых материалов на заготовки сложных форм с использованием дискретно-логического представления информации тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Логинов, Евгений Валерьевич

• Логинов, Евгений Валерьевич
• кандидат технических наук
• 2002

Оглавление диссертации кандидат технических наук Логинов, Евгений Валерьевич

Введение.

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

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

1.2 Многообразие задач раскроя - упаковки.

1.3 Классификация задач раскроя-упаковки.

1.4 Основные определения и постановка задачи размещения геометрических объектов.

1.4.1 Основные понятия и определения.

1.4.2 Общая постановка задачи оптимизации размещения плоских ГО

1.5 Основные определения и постановка задачи построения кратчайшего пути режущего инструмента.

1.6 Некоторые технологические ограничения, предъявляемые к САПР раскроя.

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

Глава 2. Методы и алгоритмы препроцессорного блока и блока оптимизации размещения САПР раскроя.

2.1 Препроцессорный блок.

2.2 Блок оптимизации размещения.

2.2.1 Методы и алгоритмы оптимизации процесса размещения плоских геометрических объектов.

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

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

Глава 3. Учет технологических ограничений и формирование пути режущего инструмента в рамках постпроцессорного блока САПР раскроя

3.1 Формирование технологических контуров для исходных контуров деталей.

3.2 Генерация пути режущего инструмента.

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

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

Глава 4. Разработка программного обеспечения системы автоматизации проектирования раскроя.

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

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

4.2.1 Препроцессорный блок САПР РУ.

4.2.2 Блок оптимизации размещения САПР РУ.

4.2.3 Постпроцессорный блок САПР РУ.

4.3 Система «ЫезЮАБ» - современная ресурсосберегающая технология размещения и раскроя.

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

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

Введение диссертации (часть автореферата) на тему «Проектирование нерегулярного раскроя листовых материалов на заготовки сложных форм с использованием дискретно-логического представления информации»

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

Среди множества задач, возникающих в проектировании, особое место занимают задачи, связанные с раскроем и упаковкой (Р-У) в заданных областях объектов различного вида и имеющих различную физическую природу. К таким задачам относятся:

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

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

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

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

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

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

Обе эти задачи: автоматизации проектирования и раскроя-упаковки тесно переплетаются в проблеме разработки систем автоматизации проектирования раскроя-упаковки (САПР Р-У) объектов разного вида в заданных областях на базе адекватных математических моделей и эффективных современных методов их решения.

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

Анализ отечественной и зарубежной литературы, информационных /Мегие^-источников позволяет сделать вывод, что исследованием и разработкой методов решения данного класса задач занимаются: Харьковская школа Р-У академика Стояна Ю.Г.; Институт алгоритмов и научных вычислений Германии (Ленгауэр Т.); Миленковик В., Даниэльс К. (США); Доусланд К., Доусланд В. (Великобритания); ряд российских ученых, среди которых: Вер-хотуров М.А., Мартынов В.В., Мухачева Э.А., Петунии A.A., Фроловский В.Д. Несмотря на это и на широкое распространение оборудования, позволяющего использовать эти методы на производстве: - до сих пор в большинстве случаев на карты Р-У проектируются вручную или примитивными интерактивными программными средствами. Это нарушает непрерывность процесса автоматизации и приводит к нерациональному использованию дорогостоящих материалов и высокопроизводительного оборудования для Р-У. Причиной такого состояния является отсутствие эффективного математического обеспечения для систем автоматизации проектирования раскроя-упаковки деталей сложных форм.

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

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

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

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

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

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

1. Разработать эффективные и надежные алгоритмы:

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

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

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

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

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

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

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

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

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

Результаты, выносимые на защиту:

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

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

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

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

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

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

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

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

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

Разработанные в диссертации методы и алгоритмы решения задач нерегулярного раскроя-упаковки деталей сложных форм, а также других задач, возникающих при создании САПР раскроя, дают возможность на единой основе создавать надежное и гибкое программное обеспечение, легко адаптируемое к любым производственным условиям и допускающее возможность широкого использования в различных отраслях промышленности. Кроме того, использованные алгоритмы оптимизации, на основе методов локального поиска, позволяют создать комплекс программных средств, быстро генерирующих высокоэкономичные карты раскроя - упаковки и программы для станков с ЧПУ. Все это дало возможность применить полученные результаты для разработки при создании автономного комплекса программных средств. На базе проведенных исследований, разработан работающий в среде Microsoft Windows 9х/2000/ХР программный продукт для решения задач САПР Р-У - "NestCAD", который на практике показал высокую эффективность за счет хорошей настраиваемое™ и быстрой адаптации к условиям работы производств различного вида в разнообразных отраслях промышленности, уменьшения времени проектирования карт Р-У (в 2-4 раза), экономии материала (до 5%) и энергии (до 6%).

Основание для выполнения исследований.

Работы в данном направлении проводились автором в Уфимском государственном авиационном техническом университете в 1999-2002 годах в рамках хоздоговорных научно-исследовательских работ с ОАО «Уралхим-маш» г. Екатеринбург и ОДО «Лама» г. Бирск.

В 1999-2001 г.г. работа была поддержана РФФИ, проекты 01-99-00937 и 01-01-00510.

Внедрение результатов:

- в Акционерном обществе «Химмаш», г. Екатеринбург (алгоритмическое и программного обеспечения рационального раскроя плоских материалов на фигурные заготовки);

- в Обществе с дополнительной ответственностью «Лама», г. Бирск (система автоматизированного раскроя листового материала при производстве разверток в мебельной промышленности).

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

- Республиканская научно-техническая конференция «Интеллектуальное управление в сложных средах», Уфа, 1999 г.

- Международная научная конференция "Моделирование, вычисления, проектирование в условиях неопределенности, Уфа, 2000 г.

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

Публикации.

По теме диссертации опубликованы 10 работ, в том числе 5 статей, 4 доклада научно-технической конференции и 1 тезис докладов.

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

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

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Логинов, Евгений Валерьевич

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

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

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

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

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

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

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

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

Заключение

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

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

Список литературы диссертационного исследования кандидат технических наук Логинов, Евгений Валерьевич, 2002 год

1. Автоматизация ироектно-конструкторских работ и технологической подготовки производства в машиностроении, Т1, Т2 / под ред. О.И.Семенкова.- Минск: Вышэйшая школа, 1977. 312с.

2. Автоматизация технологической подготовки заготовительного производства / под общей ред. Г.П.Гырдымова. Ленинград: Машиностроение, 1990.- 350с.

3. Автоматизированная система технологической подготовки производства в машиностроении / под ред. Г.К.Горанского. М.: Машиностроение, 1976.-240с.

4. Артамонов Е.И. Проблемы разработки систем автоматизированного про-ектирования//Приборы и системы управления, 1981.-N2.-С. 12-23

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

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

7. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Воронеж: ВГТУ, 1995.-54с.

8. Белякова Л.Б. О развитии математического обеспечения оптимального раскроя фигурных заготовок // Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тез.докл. Всесоюз. конфер.-Уфа, 1987.-С. 16-17.

9. Белякова JI.Б., Рябина Н.О. Проектирование на ЭВМ оптимального раскроя заготовок при листовой штамповке сложных форм//Кузнечно-штамповочное производство, 1977.- N11. С.25-28.

10. Валеева А.Ф. Алгоритм построения прямоугольной упаковки и применение его к задаче фигурного раскроя//Труды междун. сибир. конф. по прикл. и индустр. математике, СО РАН, т.2, 1995.-С.47-57.

11. Верхотуров М.А. Математическое обеспечение автоматизированных систем нерегулярного размещения двух- и трехмерных геометрических объектов на базе дискретных моделей //Диссертация на соискание ученой степени доктора технических наук. Уфа 2000

12. Верхотуров М.А. Нерегулярная укладка геометрических объектов на базе дискретного представления информации в автоматизированных системах управления. Автореферат на соискание ученой степени канд. техн. наук. Уфа, 1992.-16с.

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

14. Верхотуров М.А., Верхотурова Г.Н. Метод псевдо-оценок в задачах трехмерной упаковки.//Проблемы оптимизации и экономические приложения (тезисы докладов).-Омск, 1997.-С.40.

15. Верхотуров М.А., Верхотурова Г.Н., Логинов Е.В. Применение метода "Поиск с запретами" (TS) для решения задач нерегулярного раскроя-упаковки // Принятие решений в условиях неопределенности: Межвуз. сб. науч. тр. Уфа: УГАТУ, 2000 С. 123-127.

16. Верхотуров М.А., Верхотурова Г.Н., Логинов Е.В. Структура решения задач нерегулярного раскроя-упаковки геометрических объектов // Моделирование, вычисления, проектирование в условиях неопределенности: Межвуз. сб. науч. тр. Уфа: УГАТУ, 2000 С.375-379.

17. Верхотуров М.А., Верхотурова Г.Н., Брусиловский Д.П. Методы и алгоритмы нерегулярной двумерной упаковки объектов сложных геометрических форм. Рукопись деп. в ВИНИТИ, №682-В97 от 05.03.97.

18. Верхотуров М.А., Драган Т.М. Подсистема первоначальной (входной) обработки информации в САПР технологической подготовки раскроя// Применение САПР в машиностроении: Тез. докл. Всесоюзной конференции. Свердловск:УПИ, 1989.-С. 12-13.

19. Верхотуров М.А., Кардакова О.В., Логинов Е.В., Нугуманов А.Ш. О применении метода "simulated annealing" для решения задач нерегулярной упаковки // Интеллектуальное управление в сложных системах: Тез. докл. респ. науч.-техн. конф. Уфа, 1999 С. 19.

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

21. Верхотуров М.А., Логинов Е.В., Лохматов О.В., Аллаяров И.Ф. Применение метода «моделирования отжига» для задач трехмерной упаковки //

22. Принятие решений в условиях неопределенности: Межвуз. сб. науч. тр. Уфа: УГАТУ, 2002 С. 181-189.

23. Верхотуров М.А., Мухачева Э.А. Интегрированная система рационального раскроя в условиях единичного и мелкосерийного производства// Куз-нечно-штамповочное производство"". №5.-М:1996.-С.24-27."

24. Верхотуров М.А., Мухачева Э.А. Интегрированная система рационального раскроя// Актуальные проблемы математического моделирования и автоматизированного проектирования в машиностроении: Тезисы международной н.-т. конференции.-Казань: 1995.-С.61-63.

25. Верхотуров М.А., Мухачева Э.А., Шабрина Л.И. Многообразие задач раскроя и упаковки. Деп.в ВИНИТИ, №3023-В94.-М:1994.-8с.

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

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

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

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

30. Грейди Буч, Джеймс Рамбо, Айвар Джекобсон UML Руководство пользователя.- Москва, ДМК, 2000 432 с.

31. Грибов А. Б. Алгоритмы решения задачи плоского раскроя. -Кибернетика, 1973, N6.

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

33. Джамп Д. AutoCAD. Программирование.-M.:Радио и связь,1992.- 336с.

34. Жак C.B. О методах решения задач, сочетающих эвристику и случайный выбор// Кибернетика, 1972.-N1 .-С. 119-121.

35. Иванов Г.А. Проектирование размещения плоских геометрических объектов методами нелинейного программирования. Автореферат диссертации на соискание ученой степени кандидата технических наук. Йошкар-Ола, 1992.-19с.

36. Ирэ Пол. Объектно-ориентированное программирование с использованием С++: Пер. с англ. Киев: НИИПФ ДиаСофт Лтд, 1995. 480с.

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

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

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

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

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

42. Карасик Е.Б. Новый подход к решению задачи фигурного раскроя. -Баку, 1988.-18с.-Рукопись деп. в АзНИИНТИ, 12.05.88,N1032-A3.

43. Кнут Д. Искусство программирования для ЭВМ.-М: Мир, 1976, т.1, 1977, т.2, 1978, т.З.

44. Компьютер и задачи выбора /Автор предисл. Ю.И. Журавлев.-М:Наука, 1989.-208с.(Серия "Кибернетика неограниченные возможности и возможные ограничения").

45. Логинов Е.В. Годограф-ориентированная адаптация алгоритма «tabu search» для задач нерегулярного размещения геометрических объектов // Математическое моделирование в решении научных и технических задач: Сб. статей. Вып. 2. Уфа: Технология, 2001 С.56-61.

46. Магас С. Л. Заполнение вырубок ориентированными многоугольниками // Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тез.докл. Всесоюзной конференции.-Уфа, 1987.- С.111-112.

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

48. Мухачева Э.А., Белякова Л.Б. Задачи планирования рационального раскроя и их комплексное решение// Принятие решений в условиях неопре-деленности.-Уфа:УАИ, 1990.- С.99-108.

49. Мухачева Э.А., Верхотуров М А., Ибатуллина С.М. О рациональном распределении ресурсов. Журн. Экономика и управление, 1994, N3, С.33-40.

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

51. Роджерс Д. Алгоритмические основы машинной графики /Пер.с англ,-М.:Мир,1989.-512с.

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

53. Стоян Ю.Г. Размещение геометрических объектов.- Киев: Наукова думка, 1975.-240 с.

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

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

56. Тарасова Т.Д., Розанова Л.Ф. Метод последовательного уточнения оценок для решения задач раскроя в условиях единичного и мелкосерийного производства//Принятие решений в условиях неопределенности.-Уфа: УАИ, 1990. С. 112-116.

57. Федоров Е.С. Симметрия и структура кристаллов.-М.:Изд-во АН СССР,1949.-411с.

58. Чебышев П.Л. О кройке одежды. -Журн. Успехи матем.наук,1946, 1Д.С.27.

59. Шехтман Л.И., Мухачева Э.А. Применение метода оценок для решения задачи трехмерной регулярной у паковки.//Принятие решений в условиях неопределенности.-Уфа, 1996.-С.82-84.

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

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

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

63. Adamowicz M., Allano A. Nesting Two-dimensional shapes in rectangular modules. Comput. Aided Des., 1976, 8,Nl,pp.27-33.

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

65. Cerny V. Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, J. Opt. Theory Appl., 45, 1985, pp.41-51.

66. Christofides, N. and Whitlock, C. An algorithm for the two dimensional cutting problems. Oper. Res., 25: pp.30 - 44.

67. Coffman E., Shor P. Packing in two dimensions: asymptotic average-case analysis of algorithms, Algorithmica, 9, 1993, pp.253-277.

68. Daniels K., Li Z., Milenkovic V.J. Automatic marker making, in: Proc. 3rd Canadian conf. On Computational geometry, ed. T.Shermer, August, 1991.pp. 1124.

69. Daniels K., Milenkovic V. J. Multiple Translational Containment: Approximate and Exact Algorithms /Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms.- San Francisco, CA, January 22-24, 1995, pp.205-214.

70. Daniels K., Milenkovic V.J. Multiple translational containment, part I: an approximation algorithm.- Algorithmica special issue on Computational geometry in manufacturing, 1994, 46p.

71. Dorigo M., Gambardella L.M. Ant colonies for the traveling salesman problem. BioSystems, 43, pp.73-81.

72. Dowsland K.A. Some experiments with simulated annealing techniques for packing problems, EJOR, 68, 1993, pp.389-399.

73. Dyckhoff, H. Scheithauer, J. Terno. Cutting and packing : An annotated bibliography. Technical Report MATH-NM-08-1996, TU Dresden, 1996.-35p.

74. Dycknoff H. A typology of cutting and packing problems. F.R.Germany., 1991, -41p.

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

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

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

78. Heistermann J., Lengauer T. The nesting problem in the leather manufacturing industry. European Journal of Operational Research, 57, 1995, pp.147-173.

79. J.F.Bard and N.F. Feo. Operations sequencing in discrete parts manufacturing. Management science, 35:249-255, 1989.

80. J.P.Hart and A.W.Shogan. Semi-greedy heuristica: An empirical study. Operation Research Letters, 6:107-114, 1987

81. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles // EJOR, 1999, 112, pp.413-420.

82. M. Daniels and V. J. Milenkovic. Multiple Translational Containment. Part I: An Approximation Algorithm. Submitted to the Algorithmica special issue on Computational Geometry in Manufacturing, June 1994. In press.

83. Milenkovic V.J. Rotational polygon overlap minimization.- Computational geometry: theory and application, 1997, 16p.

84. Milenkovic V.J., Daniels K. Translational polygon containment and minimal enclosure using mathematical programming.-ITOR special issue with papers from IFORS'96, 1996, 30p.

85. N.F. Feo and J.F.Bard. The cutting path and tool selection problem in computer-aided process planning. Journal of Manufacturing Systems, 8:17-26, 1989.

86. Rayward V.J., Osman I.h., ets al. (eda) Reactive search: toward self-tuning heuristics, Modern heuristic search methods, J.Wiley and sons ltd, 1996,61 p.

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