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

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

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

Проектирование гильотинного раскроя

листового и рулонного материала с использованием послойных алгоритмов

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

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

Уфа -2004

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

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

заслуж. деятель науки РФ

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

Мухачева Элита Александровна

Официальные оппоненты

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

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

канд. техн. наук, доц. Ибатуллина София Мухаметовна

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

Уфимский государственный нефтяной технический университет

Зашита состоится_2004 г. в_часов

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

«ши

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- ООО «Евролайн» (Воронеж) - раскрой стекла, 2003;

- АСКОН-М (Москва) - САПР раскроя, 2002-2004;

- СОЗАиТ (Серафимовский, Башкортостан) - Раскрой металла, 2003;

- УГАТУ - учебный процесс по специальностям: системы автоматизации проектирования, программное обеспечение ВТ и АС, 2003-2004.

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

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

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

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

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

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

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

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

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

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

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

Рассматривается задача гильотинного раскроя на прямоугольные детали нескольких типов. Различаются задачи раскроя полубесконечной полосы (1.5 Dimensional Guillotines Cutting Problems, 1.5DCSP) и задачи раскроя листов, 2DCSP. Под гильотинным понимается раскрой, реализуемый последовательностью сквозных резов, параллельных кромкам материала (рис. 1). При этом направление детали либо фиксируется, либо ее можно поворачивать на

Исходная информация задач может быть задана кортежами следующего вида: 1.50СвР = <1У; т; и>; /; Ь; у 0,20С8Р = <1У; I; т; /; Ъ; у, е>,

а

Ь

Рис. 1 - Примеры прямоугольного двумерного раскроя: а - гильотинный раскрой; б- негильотинный раскрой

в которых:

Ж - ширина полосы или листа; Ь - длина листа; т - количество типов деталей; м» = (у>1, уу,- ширина детали |' = 1,ш; I = (¡¡, ¡¿.....¡¡.....¡т),

- длина детали - количество деталей типа

/=1,от; п = -£Ь, - общее количество деталей; 7- признак гильотинности; у = / ,

если раскрой гильотинный; у = 0 в противном случае; € - признак направления детали в полосе (листе); € = 1, если детали можно поворачивать на 90°; € = 0 в противном случае.

В случае 1.5DCSP требуется найти гильотинный раскрой рулона Я на прямоугольные детали, минимизирующий длину Л использованной части полосы. В случае 2DCSP требуется найти совокупность гильотинных раскроев листов, минимизирующих их суммарное количество N.

Решение задачи может быть записано в виде кортежей <П, Л > для 1.5БС8Р и <П¡,П2,...,Пр...,Пы> для 20С8Р, в которых П — последовательность сквозных резов рулона, - последовательность сквозных резов -го листа; Л -длина использованной части полосы; И- количество использованных листов. Математическая модель задачи гильотинного раскроя Задача 1.5DCSP. Набор К ~{ги...,г„...,г„} векторов г1~ (хь у), / = называется гильотинным раскроем при выполнении условий: 1* Взаимное непересечение деталей

(х, £ V (л:,>*,+/,) или (у, £ .У, + и-7) V (у1 > + 2* Непересечение деталей с гранями полосы V» = 1,..., п: (х, г 0) л 0-, £ 0) л {у, + IV, <; ¡V); 3* Условие гильотинности разделения

Г I"

/ = л

Рис. 2 - Условие гильотинности раскроя

Для любого прямоугольника Я С Я (рис.2) с размерами выполнено условие разделения на два прямоугольника

P'(w',l') и P"(w",l"): Ov-= w"= w) л (/'+/"= /)v(w'+w"=H') л (/'= /"=/), если eP\то (w,,/,)*F\если (и>.,/()eP'\то (и>„/,.)¿F.

Раскрой Л является оптимальным, если длина A = max(;rí+/í) достигает минимума.

Задача 2DCSP. Набор Q шаблонов Ri={rn,...,r,n,...,rniJ векторов г,к ~ (x¡b у,0, k—l,...,N называется планом гильотинного раскроя листов, если векторы Гд, / = 1,...,п для каждого листа к = 1,...,Nудовлетворяют условиям типа 1*, 2*, 3" (непересечения и гильотинности раскроев). Набор Q шаблонов R¡¡ является оптимальным, если число достигает минимума.

Приводятся основные методы решения задач гильотинного раскроя. Методы, основанные на линейном целочисленном программировании и полного перебора с отсечением неперспективных вариантов, позволяют получать решения задачи только при малых размерностях (до 10-20). Уровневые алгоритмы позволяют решать задачи с малым количеством деталей одного типоразмера. По сути, уровневые алгоритмы представляют собой упрощенную модификацию послойного метода. Однако при увеличении количества деталей их эффективность резко снижается. Многие эвристики включают послойную стратегию, начало которой заложено в работах.М. Adamowich& A.. Albano. Послойный подход использовался Э.А. Мухачевой и Л.Ф. Розановой для решения задач гильотинного раскроя. Графовый метод и/или для решения 2D и 1.5DBPP развивается в работах R.Morabito & М. Arenales. Послойные алгоритмы неэффективны при малых количествах деталей одного типоразмера. Достаточно широкое применение получил метод «последовательного уточнения оценок», SVC, который реализуется по модифицированной схеме первый подходящий, FFD с процедурами приоритета и повторения. Упорядочивание элементов основано на экономическом смысле двойственных переменных в линейном программировании. Метод можно назвать общим для решения задач раскроя-упаковки. Он применяется в случаях линейного и гильотинного раскроя, 2-х и 3-х мерной упаковки, а также и для решения задач фигурного раскроя. Для решения задач гильотинного раскроя также могут использоваться различные метаэвристики: «поиск с запретами», «имитация отжига», «муравьиная колония», «генетические алгоритмы». Из-за высокой сложности алгоритмов при увеличении количества деталей резко возрастает время, затрачиваемое на решение задачи, что затрудняет их применение в процессе подготовки производства.

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

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

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

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

III

Wk

в

fci-

'•SJ-R-

Ш

та Р¥л A

,'S,*: -

В

S?V?iiJSs'

]

ift.-»-*

J'f.'^

Ж A

abed Рис. 3 - Способы укладки детали в прямоугольную область

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

= тт(0"-и'сы,/.'-/ ), где а = тт(&е, — ) -

К]

которые могут быть уложены в один слой без поворота;

-

количество деталей,

количество деталей,

которые могут быть уложены в один слой с поворотом; - номер укладываемой детали;

L' и W4- размеры текущего прямоугольного участка.

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

Сложность алгоритма 0(4к - количество уровней

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

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

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

гильотинности все прямоугольные области, пересекающиеся с использованной областью, разделяются на несколько частей. Далее объединяются прямоугольные области, слияние которых не повлечет за собой потерю свойства гильотинности раскроя. При укладке деталей в область AFLR данная область удаляется из списка остатков, добавляются взаимно пересекающиеся остатки DHLR, BFLJ и ZGLI (рис. 4,а).

' ~ • 1 * ~-г 4 4. _ 5». }

ч * . •! -г , « Уу - 1-1 у

- Т.,- * ъ е-

Я

N

О

и

19-

к

в

м

\И

Рис. 4 - Изменение списка остатков при укладке деталей в прямоугольную область АБЬЯ: а - укладка деталей в остаток АИ-Я; б - разделение остатка, пересекающегося с использованной частью материала АВСБ

В списке сохраняются всевозможные остатки с максимально возможными размерами, с допущением пересечений, поэтому после каждой итерации укладки необходимо преобразовать те остатки, которые пересекаются с использованной на последней итерации частью материала. Удаляются все остатки, подобные NMPQ (рис. 4,6), вместо которых в список заносятся остатки NKBS, КМТВ, BTWC, CWPE, UCEQ.

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

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

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

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

Сложность алгоритма О(2 п т log m).

Сложность упрощенной модификации алгоритма О(п т log m).

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

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

Более подробно рассмотрена подсистема генерирования карт раскроя-упаковки, которая преобразует информацию об объектах согласно их размещению в области. Существует три способа получения карт раскроя:

1. Ручной, при котором карта раскроя полностью составляется человеком.

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

3. Автоматизированный, подразумевающий разумное разделение функций между человеком и машиной.

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

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

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

Важное место в работе занимает автоматизированный выбор алгоритма расчета раскроя, который основан на методе ближайшего соседа. Метод

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

В системе CETAMI-CUT используется семь характеристик для описания класса задач. Размеры деталей измеряются в долях от ширины полосы/листа. Используются следующие

показатели: п -^Ь/— общее количество деталей, -доля деталей малого

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

ж-количество типоразмеров деталей, к -коэффициент удлиненности

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

В системе ведется база данных, в которой хранится набор троек Т=< Х,А,Л >, где Х- набор характеристик решенной задачи, А - сведения об использовавшемся алгоритме решения, а также полученный результат , где - полученный коэффициент раскроя, - полученный коэффициент раскроя с учетом площади полезных остатков, /-время, затраченное на решение задачи. Процедура автоматизированного выбора метода решения определяет набор Х'=<п',8'1,8'а,8,1,,8'1,т\к'> для новой задачи и осуществляет поиск в базе данных троек Тс близким набором характеристик Xк набору характеристик X. Степень близости набора характеристик определяется оценкой, вычисляемой как взвешенная сумма квадратичных отклонений соответствующих характеристик. Весовые коэффициенты определяют значимость каждой характеристики при вычислении оценки близости наборов

5 = щ {п - п')2 + <о2{8, - 8\)г + со}{5, - б',)1 + <а4 {8Ь - 6\)2 +

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

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

и

С1{ показывает влияние количества типоразмеров деталей т\ и 7 показывает влияние удлиненности листов к. Результат решения оценивается следующим образом: г = Л1кра+Л1кра+Л}1, где - весовые коэффициенты,

определяющие направленность поиска.

Увеличение весового коэффициента \ влечет увеличение значимости КРа без учета полезных остатков, - КРа с учетом полезных остатков, X? -затрачиваемого на получение решения времени.

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

где величины Б' и г' соответствуют набору X, а величины и г, соответствуют Х,.В случае Q<0 за Л7принимается наборХ(.

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

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

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

Значения весовых коэффициентов Л,,^,-^,(01,б)1,...,0}7 и констант С„ С/ определяется эмпирическим путем и указываются в настройках системы. Диапазон значений для весовых коэффициентов и констант представлен числовым отрезком [0; 1].

Рекомендуемые значения весовых коэффициентов и констант:

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

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

Я, = I; ¿2 = 0,02; Л, = 0,01;

<о, =0,9; о>2 =0,2; соу = 0,1; <а4 =0,1; <у5 =0,05; ео6 = 0,8; й>7 =0,2; С, = 0,9; С, = 0,25.

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

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

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

100.00

п-300..1000. п «1000-4000. п * 1000.4000. n - 4000..20 000. п «4000.^0000, п « 4000..20 000, т»15..25 т*Ю..20 т«40..80 т« 10..25 т« 160..400 т« 600. .2000

_[ MBFD_MLA_CIRCA« _PRCA-_gVBS+_DVBS-

Рис. 6 - Сравнение коэффициентов раскроя полосы

Диаграмма сравнения коэффициентов раскроя полосы представлена на рисунке 6, диаграмма сравнения коэффициентов раскроя листов представлена на рисунке 7. В эксперименте участвовали уровневый алгоритм «лучший подходящий» (BFD), послойный метод (LA), рекурсивный метод (RCA+), упрощенная модификация рекурсивного метода (RCA-), метод поиска пустых корзин (VBS+) и его упрощенная модификация (VBS-).

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

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

100 00 95 00 90 00

*

я 85 00

О.

ас

во 00

75 00 7000

п» 100 300 п*300 1000 п-300 1000 п = 1000 4000 л »1000 4000 п = 1000 4000

т= 10 20 тв 15 25 т« 60 100 т»10 20 т*40 80 ,т»200 400

_I ЩВГР И LA PRCA* PRCA- nV8S+ gVBS-

Рис. 7 - Сравнение коэффициентов раскроя листов

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

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

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

1. Изучена послойная технология формирования карт двумерного прямоугольного гильотинного раскроя Рассмотрены простые реализации идеи укладки деталей группами. Выявлены недостатки известных послойных алгоритмов: уровневых с использованием простых эвристик и более сложных алгоритмов М. Адамовича, Э.А. Мухачевой и Л Ф. Розановой.

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

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

4. Исследована эффективность предложенных методов на базе численного эксперимента с использованием системы двумерного прямоугольного раскроя CETAMI-CUT. При раскрое полосы с разрешенными поворотами деталей рекурсивный метод получает лучшие результаты при большом количестве (свыше 50) типоразмеров деталей и при их удлиненной форме. В остальных случаях метод поиска пустых корзин показал лучшие результаты, особенно при больших размерах деталей и большом количестве однотипных деталей. При раскрое листов лучшие результаты обеспечивает рекурсивный метод независимо ни от размеров, ни от количества деталей.

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

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

1. Ермаченко А.И., Сиразетдннов Т.М., Усманова А.Р. Метод «поиска с запретами» для решения задачи гильотинного прямоугольного раскроя // Принятие решений в условиях неопределенности. Уфа: УГАТУ, 2000. С. 95-100.

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

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

4. Ермаченко А.И., Сиразетдинов ХТУЕ Пакет алгоритмов и программ для решения задач гильотинного раскроя // Труды 12-й Байкальской междунар. конф. Т.6. Иркутск: Байкал, 2001. С. 13-18.

5. Ермаченко А.И., Сиразетдинов Т.М., Усманова Л.Р. Пакет методов для решения задач прямоугольного гильотинного раскроя в условиях серийного и единичпого производства // Материалы конф. ОПТИМ-2001 СП ЦНИИ ТС. С. 79-82.

6. Ермаченко Л.Н. Сиразетдинов Т.М. Автоматизированная система расчета прямоугольного раскроя // Принятие решений в условиях неопределенности. Уфа: УГАТУ, 2002. С. 158-162.

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

8. Ермаченко А.И., Сиразетдинов Т.М. Автоматизированная система расчета прямоугольного раскроя // Информационные системы и технологии. Новосибирск: НГТУ, 2003. С. 36-39.

9. Сиразетдинов Т.М. Автоматизированная система расчета прямоугольного раскроя // Принятие решений в условиях неопределенности. Уфа: УГАТУ, 2003. С. 329-339.

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

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

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

АВТОРЕФЕРАТ

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

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

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

»13 929

Оглавление.

Введение.

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

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

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

1.3. Постановка задачи гильотинного раскроя.

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

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

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

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

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

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

1.6. Выводы.

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

2.1. Уровневые алгоритмы.

2.2. Послойная технология расчета гильотинного раскроя.

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

2.3.1. Рекурсивный метод.

2.3.2. Метод поиска пустых корзин.

2.4. Выводы.

3. Автоматизированная система двумерного прямоугольного раскроя CETAMI-CUT.

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

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

3.3. Применение разработанного программного обеспечения в САПР раскроя-упаковки.Error! Bookmark not defined.

3.4. Программа-оболочка CETAMI-CUT, ее взаимодействие с расчетными модулями.

3.5. Детерминированные эвристические алгоритмы решения задачи гильотинного раскроя, реализованные в системе CETAMI-CUT.

3.5.1. Рекурсивный алгоритм в рамках системы CETAMI-CUT.

3.5.2. Алгоритм поиска пустых корзин в рамках системы CETAMI-CUT.

3.6. Автоматизированный выбор метода расчета раскроя.

3.7. Выводы.

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

4.1. Независимое использование рекурсивного метода и метода поиска пустых корзин.

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

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

4.1.3. Сравнение разработанных эвристик с послойным алгоритмом и между собой.

4.2. Использование рекурсивного метода в составе метаэвристик.

4.3. Использование метода поиска пустых корзин в составе метаэвристик

4.4. Использование процедуры автоматизированного выбора метода решения задачи.

4.5. Выводы.

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Разработанное программное обеспечение позволяет быстро строить карты раскроя с высоким коэффициентом использования материала;

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

Работа выполнялась при поддержке грантов Российского Фонда Фундаментальных Исследований (РФФИ), проекты 99-01-000937 и 01-01000510; технического задания фирмы АСКОН-М (Москва).

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

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

1. Двенадцатая Байкальская международная конференция «Методы оптимизации и их приложения» (Иркутск, 2001 г);

2. Всероссийская научно-практическая конференция "Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования" ОПТИМ-2001 (Санкт-Петербург, 2001г.);

3. Всероссийская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002г.);

4. Международная научно-техническая конференция «Информационные системы и технологии» ИСТ-2003 (Новосибирск, 2003);

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

Результаты диссертационной работы непосредственно отражены в 14 публикациях, в том числе в монографии (2 п.л.), 9 статьях, 5 трудах конференций (3 докладов и 2 тезисов), выполненным по теме диссертации при непосредственном участии и руководстве автора.

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

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

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

1. Изучена послойная технология формирования карт двумерного прямоугольного гильотинного раскроя. Рассмотрены простые реализации идеи укладки деталей группами. Выявлены недостатки известных послойных алгоритмов: уровневых с использованием простых эвристик и более сложных алгоритмов М. Адамовича, Э.А. Мухачевой и Л.Ф. Розановой.

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

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

4. Исследована эффективность предложенных методов на базе численного эксперимента с использованием системы двумерного прямоугольного раскроя CETAMI-CUT. При раскрое полосы с разрешенными поворотами деталей рекурсивный метод получает лучшие результаты при большом количестве (свыше 50) типоразмеров деталей и при их удлиненной форме. В остальных случаях метод поиска пустых корзин показал лучшие результаты, особенно при больших размерах деталей и большом количестве однотипных деталей. При раскрое листов лучшие результаты обеспечивает рекурсивный метод независимо ни от размеров, ни от количества деталей.

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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