Содержание к диссертации
Введение
1. Обзор моделей н методов решения задач раскрои 10
1.1 Автоматизация проектирования и технологической подготовки производства... 10
1.2. Классификация задач раскроя 13
1.3. Постановка задачи гильотинного раскроя 15
1.4 Математическая модель задачи гильотинного раскроя 17
1.5. Обзор методов решения задачи раскрой IS
1.5.1 Точные методы решения задач раскроя 21
1.5.2. Приближенные и эвристические методы 22
1.53. Вероятностные методи локального поиска оптимума 25
1.5.4. Применение методов решения задач раскроя-упаковки автоматизированных системах раскроя-у паковки 27
1.6. Выводы 32
2. Зврпстнчеекне методы решения задачи гильотинного раскроя 34
2.1. Уровневые алгоритмы 34
2.2. Послойная технология расчета гильотинного раскрои 35
2.3. Использование послойной технологии для разработки новых детерминированных, методов решения задачи гильотинного растфоя 36
2.3.1. Рекурсивный метод 36
2,3.2. Метод поиски пустых корзин 42
2.4. Выводы 49
3- Автоматизированная система двумерного прямоугольного раскроя CETAMI-CUT 51
3.1. Современное состояние раскройно-заготоиительного производства 51
3.2. Структура САПР раскроя-упаковки 54
3.3. Применение разработанного программного обеспечения в САПР раскроя-упаковки Error! Bookmark not defined .
3.4 Программа-оболочка CETAMI-CUT, ее взаимодействие с расчетными модулями 57
3.5. Детерминированные эвристические алгоритмы решения задачи гильотинного раскроя, реализованные в системе CETAMI-CUT 63
3.5.1. Рекурсивный алгоритм в рамках системы CETAMI-CUT 64
3.5.2. Алгоритм поиска пустых корзин в рамках системы CETAMI-CUT..66
3.6. Автоматизированный выбор метода расчета раскроя 69
4. Численные эксперименты 74
4.1. Независимое использование рекурсивного метода и метода поиска пустых корзин 74
4.1.1. Определение значений параметров рекурсивного метода для его эффективной работы 74
4.1.2. Определение значений параметров метода поиска пустых корзин для его эффективной работы 76
4.1.3. Сравнение разработанных эвристик с послойным алгоритмом и между собой 78
4.2. Использование рекурсивного метода в составе метаэвристшс 89
4.3. Использование метода поиска пустых корзин в составе метаэвристшс .92
4.4. Использование процедуры автоматизированного выбора метода решения задачи 94
4.5. Выводы 97
Заключение 99
Литература 101
Приложение 111
- Постановка задачи гильотинного раскроя
- Использование послойной технологии для разработки новых детерминированных, методов решения задачи гильотинного растфоя
- Применение разработанного программного обеспечения в САПР раскроя-упаковки Error! Bookmark not defined
- Использование рекурсивного метода в составе метаэвристшс
Введение к работе
Диссертационная работа посвящена разработке методов расчета и системы проектирования двумерного прямоугольного гильотинного раскроя рулонного и листового материала, созданию на этой базе программного обеспечения, входящего в состав автоматизированного рабочего места технолога раскройно-заготовительного производства.
Актуальность темы исследования. Определяющими факторами успеха
в промышленном производстве являются: уменьшение времени выхода
продукции на рынок, снижение стоимости и повышение качества. Темпы
морального старения промышленных изделий таковы, что поставленные на
конвейер новые образцы часто уже не соответствуют современным
требованиям. Только значительное сокращение цикла проектирования и
подготовки производства, подразумевающее внедрение систем автоматизации
проектирования (САПР), может способствовать созданию
конкурентоспособной продукции и своевременному выходу ее на рынок.
Задача гильотинного раскроя представляет собой важный раздел прикладных задач дискретной оптимизации и исследования операций. Ее решение является неотъемлемой частью процесса технологической подготовки производства.
Задача гильотинного раскроя относится к классу NP-трудных задач комбинаторной оптимизации. Это означает, что не существует алгоритма полиномиальной сложности для ее оптимального решения, и точный результат в общем случае может быть получено только за экспоненциальное время.
Поскольку на практике большинство задач гильотинного раскроя имеют большую размерность, то из-за больших затрат вычислительного времени и необходимостью учета технологических ограничений, для решения задач размещения в САПР применяют эвристические методы. Эти методы позволяют получать рациональные решения за приемлемое время.
Все вышесказанное определяет актуальность решаемой в данной работе задачи расчета гильотинного раскроя в системах автоматизированного проектирования.
Цель работы
Разработать высокопроизводительные методы решения задачи проектирования гильотинного раскроя листового и рулонного материала; создать на этой базе программную систему и включить ее в состав автоматизированного рабочего места технолога раскройно-заготовитеяьного производства.
Для достижения цели работы были поставлены следующие задачи:
Изучить и опробовать известные послойные алгоритма формирования карт двумерного прямоугольного гильотинного раскроя, наметить пути их совершенствования;
Разработать на базе послойной технологии высокопроизводительные эвристические алгоритмы для решения задач гильотинного раскроя рулонного и листового материала;
Разработать программное обеспечение на основе созданных методов в составе системы двумерного прямоугольного раскроя для автоматизированного рабочего места технолога раскройно-заготовительного производства, позволяющей учитывать ряд технологических ограничений: припуски на резы, окантовку рулона или листов, ограничение длины хода режущего инструмента;
Исследовать эффективность предложенных методов на базе численного эксперимента с использованием системы двумерного прямоугольного раскроя;
Разработать технологию автоматизированного выбора метода решения задачи раскроя на основе ее исходных данных и реализовать соответствующее программное обеспечение.
Методы исследования
Результаты исследований, выполненных в работе, базируются на методах исследования операций, теории и практике автоматизации проектирования, принципах модульного и структурного программирования. Для анализа эффективности методов применялись численные эксперименты и методы их обработки.
На защиту выносятся
1. Метод рекурсивный;, разработанный на базе послойной технологии,
предназначенный для получения гильотинного раскроя листового и рулонного
материала;
Метод поиска пустых корзин, разработанный на базе послойной технологии, предназначенный для получения гильотинного раскроя листового и рулонного материала;
Особенности реализации разработанных методов, связанные с технологическими ограничениями производства;
Задача автоматизированного выбора алгоритма расчета гильотинного раскроя и метод ее решения на базе правила ближайшего соседа;
Результаты численных экспериментов и рекомендации по использованию предлагаемых алгоритмов.
Научная новизна работы
Разработан метод гильотинного раскроя листового материала, новизна которого состоит в использовании рекурсивной процедуры раскроя прямоугольного участка с частичным перебором вариантов укладки деталей;
Разработан метод гильотинного раскроя рулонного материала, новизна которого состоит в поиске пустых корзин, позволяющий ограничивать перебор без потери качества раскроя;
Разработанные методы позволяют использовать их автономно для решения поставленных задач и в качестве процедуры, строящей карту раскроя в вероятностных алгоритмах локального поиска оптимума;
Разработанная мера близости для использования правила ближайшего соседа в применении к задаче автоматизированного выбора метода решения задачи раскроя на основе ее входных данных позволила улучшить качество выбора. Реализованный алгоритм показал адекватность методов исследуемым информационным областям.
Практическая значимость работы
Разработаны структура и функции автоматизированной подсистемы гильотинного раскроя, позволяющие осуществлять автоматизированный выбор метода расчета раскроя в зависимости от поступающей на вход информации и требований заказчика;
Разработанное математическое обеспечение двумерного прямоугольного раскроя в составе автоматизированного рабочего места технолога раскройно-заготовительного производства позволяет повысить коэффициент использования материала на 7-18% и значительно сократить время проектирования по сравнению с традиционным проектированием;
Разработанное программное обеспечение позволяет быстро строить карты раскроя с высоким коэффициентом использования материала;
Разработанные методы решения задачи являются инвариантными и могут быть легко адаптированы под конкретное производство, предъявляющее некоторые дополнительные технологические ограничения.
Работа выполнялась при поддержке грантов Российского Фонда Фундаментальных Исследований (РФФИ), проекты 99-01-000937 и 01-01-000510; технического задания фирмы АСКОН-М (Москва).
Апробация работы
Результаты работы, а также отдельные ее разделы докладывались и обсуждались на конференциях:
Двенадцатая Байкальская международная конференция «Методы оптимизации и их приложения» (Иркутск, 2001г);
Всероссийская научно-практическая конференция "Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования" ОПТИМ-2001 (Санкт-Петербург, 2001г.);
Всероссийская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002г.);
Международная научно-техническая конференция «Информационные системы и технологии» ИСТ-2003 (Новосибирск, 2003);
Семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.
Результаты диссертационной работы непосредственно отражены в 14 публикациях, в том числе в монографии (2 п.л.), 9 статьях, 5 трудах конференций (3 докладов и 2 тезисов), выполненным по теме диссертации при непосредственном участии и руководстве автора.
Структура и объем работы
Диссертация состоит из введения, 4 глав, выводов, списка литературы, и приложений, включающих табличные результаты численных экспериментов, функциональную и информационную модели, акты внедрения результатов работы. Работа изложена на 139 страницах машинописного текста, кроме того, содержит 25 рисунков и 24 таблиц. Библиографический список включает 98 наименования и занимает 10 страниц.
1. Обзор моделей и методов решения задач раскроя
В рамках диссертационной работы рассматриваются вопросы автоматизации подсистемы генерирования карт раскроя технологической подготовки производства САПР раскроя. Приводится обзор классов задач раскроя, постановка и математическая модель задачи лиьотинного раскроя, обзор методов решения задач раскроя.
1.1 Автоматизация проектирования и технологической подготовки
производства
Целью технологической подготовки производства является достижение в процессе изготовления продукции оптимального соотношения между затратами и получаемыми результатами. Увеличение доли мелкосерийного производства требует создания автоматизированных систем технологической подготовки, так как именно при данном характере производства преимущества использования автоматизированных систем проявляются в наибольшей степени [50].
Разработки в области автоматизации технологической подготовки производства (ТІ ill) создали условия для широкого внедрения автоматизированных систем ТПП и автоматизированного программирования систем ЧПУ. Объектами ТПП являются заготовки, основное и вспомогательное оборудование. Заготовка - это объект, подвергаемый в процессе ТПП непосредственному воздействию режущего инструмента. Множество заготовок может дать обоснование выбору технологического процесса. Речь идет о единичном, мелко-серийном и средне-серийном, а также массовом производстве. Вид материала - это еще одна из характеристик объекта ТПП, так как сведения о материале детали являются одним из критериев проектирования технологического процесса наряду с требованиями к инструменту и станкам.
Процесс производства деталей принято делить на заготовительный этап и этап механической обработки. Трудоемкости обоих этапов связаны между собой, т.е. уменьшение ее на одном из этапов может привести к увеличению трудоемкости на другом. Необходимо подчеркнуть, что создание систем автоматизированной технологической подготовки заготовительного производства наиболее актуально в настоящее время [15].
Раскройно-заготовительные работы являются одной из начальных стадий ТПП и закладывают основы рационального функционирования всех последующих производственных звеньев. Именно на этом этапе определяются оптимальные размеры заготовок, находится оптимальный способ их размещения на заданном материале, по сгенерированным планам раскроя рассчитываются нормы расхода как на каждую деталь, так и заказ материала на плановый период в целом. Процесс составления планов раксроя является сложным и трудоемким, особенно в условиях единичного и мелкосерийного производства, которые отличаются большой номенклатурой деталей и типоразмеров используемого материала, частой сменяемостью заказов. Поэтому технолог без использования средств автоматизации не в состоянии спроектировать планы раскроя, состоящие из большого количества разногабаритных деталей с минимальными отходами и с учетом технологических ограничений в сжатые сроки
Под системой автоматизированного проектирования раскроя-упаковки понимается совокупность математических, программных, технических и организационных средств, предназначенных для расчета и внедрения рационального плана раскроя-упаковки. Структура САПР раскроя-упаковки содержит три основные подсистемы (рис. 1).
Подсистема
препроцессорной подготовки информации
БД объектов
БД крат раскроя
Подсистема генерирования карт упаковки
Заявка на
проектирование упаковки
Подсистема
постпроцессорной обработки
Нормативно-справочная информация
Карты упаковки,
управляющие программы
для станков с ЧПУ,
комплект документации
Рис. 1 - Структура САПР раскроя-упаковки
Подсистема препроцессорной обработки исходной информации об объектах и областях размещения; она предназначена для подготовки, хранения и редактирования данных о геометрии объектов для решения конкретной задачи.
Подсистема генерирования карт раскроя, основной целью которой является формирование рационального размещения геометрических объектов в автоматическом режиме.
Подсистема постпроцессорной обработки информации о размещенных геометрических объектах (подсистема разработки технологического процесса раскроя-упаковки). Она формирует управляющие программы для станков с ЧПУ на основе карт раскроя и нормативно-справочной информации (НСИ).
Подготовка таких программ требует выполнения трудоемких математических расчетов и разработки алгоритмов формирования пути инструмента при выполнении раскроя объектов сложных форм, что само по себе является сложной задачей и в данной работе не рассматривалась.
Автоматизированное рабочего места технолога планово-заготовительного производства включает в себя подсистему препроцессорной обработки информации и подсистему генерирования карт раскроя, которое предназначено для решения задач раскроя-упаковки.
Только оптимальное проектирование на всех этапах разработки технологического процесса позволяет добиться качества проектирования и эффективности процесса производства в целом.
В данной работе рассматривается автоматизация ТИП единичного, мелко-серийного и средне-серийного производства.
1.2. Классификация задач раскроя
Под задачами раскроя понимается широкий класс моделей, объединенных общей логической структурой. К ним можно отнести следующие задачи:
задача раскроя запаса материала;
задача плотного размещения геометрических объектов в заданной области;
задача загрузки рюкзака;
задача упаковки контейнеров;
задача загрузки транспорта;
задача выбора ассортимента;
задача планировки помещений;
задача распределения памяти вычислительной машины;
-- задача составления расписания многопроцессорных систем.
Приведенный перечень можно продолжить, и каждая задача, в ср.ою очередь, может быть различным образом конкретизирована. Задачи могут отличаться геометрией материала и получаемых из него .ззготозо-с, размерностью, ассортиментом материала и запгкшок, уе-дойиямй реализации раскроя и другими дополнительными факторами.
/ Ассортимент объектов /
' шщт тшїїрші&т.
й№ШЇ$Ш$$ШЯ*
/ Вид назначения , / Суш планирования) /
Размерность
і -.- -
t
|||||Щ||ш||;йл ;||І|Ш;ЇІШШІІІШ:;
-^WWTC»yW
Одномерный
(ЛИНйЙНЫЙ)
V*>W'>»-*'*'*>»-
Трехмерный (пространственный)
,...J.
Ассортимент ('ПЛІ /
моделей) /
Геометрия
KtTlpepbiBfJSiJ МОДУЛЬ
;|||||щ||ір||
Фигурный
тимшация
/ Оїітиг*
ьид реализации
! Многопарамет» j ричеекая опти-
! МШЙДИЯ
ШІШШІШЕ;
Унаковка
Рис. 2 - Классификация моделей задач гзаскроя-упаковки
Приведенные проблемы рассматриваются далее под одним названием -їадача раскроя. Критерием, по которое какая-либо задача может быть
отнесена к данному классу задач, обычно является наличие двух групп объектов. К первой группе относятся объекты с большим значением некоторой характеристики (длина, вес, время в т.п.), ко второй группе - объекты с мешаными значеннями этой характеристики. Требуется установить соответствие и порядок назначений между -элементами этих групп.
Фактор-классификац~ия основных моделей задач раскроя-упаковки приведена па рисунке 2. Серым цвет-ом отмечены элементы, относящиеся к задаче гильотин во го раскроя и составляющие предмет .исследования.
1.3* Постановка задачи гидытшиого раскрои
Рассматривается задача гильотинного раскроя на прямоугольные детали нескольких типов. Различаются задачи раскроя полубескоиечной полосы (1,5 Dimensional Guillotines Cutting Problems, 1,51>8Р) в задачи раскроя листов, 2DCSP. Под гильотинным понимается раскрой, реализуемый 1:гееледо.ааз:ель.носгыо сквозных резов, параллельных кромкам материала (рис. 3). При этом направление детали либо фиксируется, либо ее можно поворачивать на 90.
Рис. 3 - Примеры прямоугольного двумерного раскрой: а - гильотинный раскрой; 6 - негильотниный раскрои
Исходная информация задач может ое.ггь задана кортежами следующего евда;
2DCSP =
в которых:
W- ширина полосы или листа;
L - длина листа;
т - количество типов деталей;
w ^ (wj, w2, ...,Wb ....wj, w( - ширина детали і — 1, тп ;
1 = (її. h,-,h-,U, h~ длина детали i = l,m;
b = (bi, Ьг, —,ЬЬ ...,Ьщ), bi — количество деталей типа і = 1, Ш;
n = ^bt - общее количество деталей;
у — признак гильотинности; у = 2, если раскрой гильотинный; 7 ~ 0 в противном случае;
є - признак направления детали в полосе (листе); е = 1, если детали можно поворачивать на 90; е = 0 в противном случае.
В случае 1,5DCSP требуется найти гильотинный раскрой рулона R на прямоугольные детали, минимизирующий длину Л использованной части полосы.
В случае 2DCSP требуется найти совокупность гильотинных раскроев листов R, минимизирующих их суммарное количество N.
Решения задач может быть записано в виде кортежей <Д Л > для 1,5DCSP и <Пі,П2,-М],-Мм> Для 2DCSP, в которых П - последовательность сквозных резов рулона, TIj - последовательность сквозных резовj-ro листа; А-длина использованной части полосы; JV- количество использованных листов.
Пример.
Описание исходной информации задачи рисунка Ъ,а: W = 12; L = 16 (для задачи 2DCSP);
m = 10;
w = (6, 5, 5, 2, 2, 1, 2, 5, 3, 8);
/ = (7, 8, 4, 4, 2, 2, 5, 5, 8, 2);
b = (1, 1, 1, 2, 1, 1, 1, 1, 1, 1);
n = 11;
7- 7; = 1.
1.4. Математическая модель задачи гильотинного раскроя
Задача гильотинного раскроя полосы 1,5DCSP.
Набор R~{ri,...,r„...,rJ векторов гі = (хі,Уі), і = 1,...,п, называется гильотинным раскроем при выполнении условий:
1 Взаимное непересечение деталей
О,- >Xj +lj)v(Xj >xi + /,) или О, >yj + Wj) v(yj >Уі + iv,);
2 Непересечение деталей с гранями полосы \fi = l,...,n:(xi^0)A{yi^0)A(yi+wi
3 Условие гильотинности разделения
Для любого прямоугольника Рей (рис. 4) с размерами (wj):w& Wj v7 ^/,-, выполнено условие разделения на два прямоугольника Pt(wr,V)Ts.P"(w,,,l")\
(w'= W"= w) л (/*+/"= 0 v (W+W^ w) л (/'=/" = /), если (м/„/,)еР",то (WfJJeF.
! і -- L '
Рж:. 4 -- Условие гильотинности раскроя
Раскрой R является опяшшыьпым, если длина Л - нтах(х. +0).) достигает минимума.
Задача гильотинного раскроя листов 20CSP.
Набор шаблонов / ;-"-;V;t,.,,.....^ векторов ?\*';; ,fx<.yj, , -- / ,-V
называется плавом гильотинного раскроя листоа, если лекторы г:^, і - /,....« для каждопї листа к ""- /, ...,Л' удовлетворяют условиям типа. ! \ 2", 3* (непересечений и гилъотинности раскроеїї).
Набор Q іішб-юінж Rk является ошпшяльньш, если число N достигает мшшмума.
m'
Ї.5. Ofwop методов решения задачи раскроя
В течение последних пятидесяти лет" проблема «раекроя-упзкснїки.о привлекает внимание научных исследователей и производственников. Начало хсому положила в 1951 г, книга Ленинградских ученых ЛВ. Канторовича и В.А.Залїаллера [19]. 'Задачи раскроя рассматривание е. ими как примеры применения ранее развитого Л.В.Канторовичем линейного программирования, })дя решения эадач раскроя-укашвзш применяется модель .чиненного программирования с неявно задашюй информацией о раскроях (столбцах матрицы). Для генерации столбцов В.А.Залгадлером был предложен прием.
предвосхитивший появившееся позднее динамическое программирование. Аналогичные методы получили развитие в 60-е годы за рубежом в работах P.Giimore & RGomory [67], [68] и позднее XTerno, RXindeman & G.Scheithauer [92]. Для решения задачи генерирования раскроя были разработаны метод склейки И.В.Романовским [43], сеточный метод для линейного раскроя В.А.Булавским и МА.Яковлсвой [6], для гильотинного раскроя Э.А.Мухачсвой [33], [39]. На базе линейного программирования Э.А.Мухачевой разработаны также алгоритмы условной оптимизации, учитывающие специфику реального производства [31]. В то время основной целью этих и многих других работ являлось применение линейного программирования в сфере производственных задач. Эта цель в той или иной мере была достигнута в условиях массового и серийного производства. В зарубежной литературе признан приоритет Л.В.Канторовича и В.А.Залгаллера [58]. Однако задачи раскроя и упаковки по своей сути являются проблемами дискретной оптимизации и их решение с помощью линейного программирования не более чем непрерывная релаксация, которая дает решение близкое к оптимальному при дополнительных ограничениях, возникающих в условиях серийного производства. Далее задачи раскроя-упаковки рассматриваются как прикладные проблемы комбинаторных задач исследования операций. Н.Гэри и Д.Джонсон показали, что задача одномерной упаковки в контейнер принадлежит к классу MP-трудных задач и для точного решения необходимо применять схемы полного перебора [11], [64].
Впервые качественная типология в области раскроя-упаковки проведена в 1990 г. немецким ученым H.Dykhoff [59]. Она принята в мировой практике и используется при изучении моделей и методов решения задач раскроя-упаковки. Разнообразие моделей определяется, прежде всего, фактором геометрии. Различаются задачи линейного (одномерного), прямоугольного (двухмерного) и параллелепипедного (трехмерного) раскроя-упаковки. Среди этих задач выделяются гильотинный раскрой и упаковка. Особо выделены проблемы размещения деталей сложной геометрической формы в заданных областях. Для них на первый план выступают информационные проблемы задания фигур, учета и обеспечения их непересечения, кодировки и другие.
Задачи раскроя-упаковки являются типичными представителями NP-трудных проблем и для их решения применяются общие подходы: точные методы, простые эвристики и метаэвристики. Ввиду неполиномиальной сложности точных алгоритмов, авторами многих работ уделяется значительное внимание приближенным методам и эвристикам.
В течение 90-х годов прошлого столетия на тему раскроя-упаковки было выпущено шесть специальных изданий: под редакцией H.Dyckhoff & G.Wascher в 1990 г. [60], S.Martello в 1994 г. [77], [78], Y.Lirov в 1995 г. [73], E.Bischoff & G.Wascher в 1995 г. [54], E.Mukhacheva в 1997 г. [83], KYanasse в 1999 г. [98], P.Wang & G.Washer в 2000 г. [97]. Более того, сотни статей опубликованы в международных и российских журналах: European Journal of Operational Research (EJOR), Computers & Operations Research, Computers & Industrial Engineering, Operations Research Letters, Pesquisa Operacional; Информационные технологии, Автоматика и телемеханика, Дискретный анализ и исследование операций, Вестник высшей школы, Кузнечно-штамповочное производство и другие центральные и ведомственные издания. При этом статьи и книги имеют как теоретический, так и прикладной характер. Последний аналитический обзор проведен в 2003 году под руководством Э.А.Мухачевой по заданию РФФИ, проект 03-01-07002.
В советский период проводились научно-практические семинары и
конференции в Ленинграде, Уфе, Звенигороде и других городах. В современный период организуются небольшие секции в рамках работы конференций: Математическое программирование и приложения (Екатеринбург, ИММ УРО АН РФ); Дискретный анализ и исследование операций (DAOR, Новосибирск, ИМ СО РАН); Компьютерные науки и информационные технологии (CS1T, Уфа, УГАТУ); Ресурсосберегающие технологии (ОПТИМ, СПетербург); Методы оптимизации и их приложения (Байкальская международная конференция по математическому программированию, Иркутск); Дискретная математика и экономические приложения (Омск, филиал ИМ СО РАН).
Причина растущего интереса к задачам раскроя-упаковки состоит в их принадлежности к NP-трудным проблемам, в широкой применимости результатов, разнообразии и сложности задач реального мира, которые можно реализовать как NP-трудные.
Модели задач гильотинного и негилъотинного, двух и трехмерного раскроя различаются введением дополнительных условий, например, способами достижения непересечения деталей между собой и с границей области, гильотинностью резов, учетом допусков на получение деталей. Эти и другие условия учитываются в рамках декодеров - алгоритмов генерации шаблонов раскроя.
1.5.1. Точные методы решения задач раскроя
Систематическое изучение проблемы раскроя-упаковки заложено в книге Ленинградских ученых Л.В.Канторовича и В. А.Залгаллера в 1951 г. и развито в их более поздних работах [18] и в статьях P.Gilraore & R.Gomory [бб]. Они впервые применили к решению CSP-метод линейного программирования с генерацией столбцов на каждом шаге процесса. G.Scheithauer & J.Terno, использовали полученный непрерывный оптимум для построения целочисленного решения [87]. С этой целью после округления снизу непрерывного решения, формируется малая остаточная задача. Последняя решается с помощью эвристик до достижения нижней границы или процесс останавливается на лучшем из полученных решений.
Методы, основанные на линейном целочисленном программировании, оказались приемлемыми для решения задач линейного и гильотинного раскроя. Задачи ВРР - классические представители NP-трудных проблем и для их решения, как правило, применяются методы полного перебора с отсечением неперспективных вариантов. Еще в 1973 г. И.В.Романовский и Н.П.Христова предложили для решения дискретных минимаксных задач метод дихотомии [44], который получил развитие и для решения задач ВРР в работе С.В.Кацева [20]. В 1977 г. И.В.Романовским представлена общая идея переборного метода
для решения экспериментальной задачи, и предложена его конкретизация в виде метода «ветвей и границ» (Method Branch and Bound, МВБ) для решения задач упаковки [42]. В дальнейшем метод получает развитие за счет введения процедур сокращения перебора в работах Э.А.Мухачевой и В.М.Картака [36], [84].
Большинство существующих точных методов решения задачи прямоугольного негильотинного раскроя сводятся к перебору всего множества допустимых решений. Методы улучшенного перебора объединены для этих задач под названием «метода ветвей и границ».
Другой подход к точным методам решения 1,5DBPP и 2DBPP разработан в середине 80-х гг. А.И. Липовецким [25]. Он сформулировал задачу как проблему комбинаторной оптимизации. На основе понятия «зоны» доказывается, что для любой упаковки прямоугольников можно указать такой их порядок, при котором каждый следующий прямоугольник не пересекается ни с одной из зон предыдущих (топологическая сортировка). Метод зон реализован в 1988 г., усовершенствован и исследован в 2001 г. В.В.Бухваловой (С.Петербург) [8].
Несмотря на многообразие различных подходов к созданию точных алгоритмов, размерность решаемых задач редко превосходит т = 20. Это связано с тем, что пока не найдено способа определения эффективной нижней границы и для доказательства оптимальности приходится перебирать все возможные варианты.
1.5.2. Приближенные и эвристические методы
При изучении задач раскроя-упаковки и разработке методов их решения особая роль отводится обобщенной проблеме загрузке рюкзака, подробно описанной S. Martello & P.Toth еще в 1990г [79]. Бинарная, ограниченная, неограниченная, двумерная задача рюкзака находят свое применение в составе алгоритмов для решения задач раскроя и упаковки.
Дальнейшие теоретические изыскания, разработка методов и их исследование посвящены задачам 1DBPP, как представителям более общей рюкзачной проблемы. Они являются классическими примерами NP-трудных проблем и методы их решения рассматриваются именно в этом контексте. В работе Е. Coffman, M.Garrey & D.Jonson, опубликованной в 1984г., приведен обзор приближенных однопроходных методов упаковки контейнеров [56]. Ими описан принцип самого худшего случая для он-лайн и офф-лайн вариантов однопроходных эвристик. Асимптотическое отношение наихудшего представления алгоритмов первый подходящий (First Fit, FF) и лучший подходящий (Best Fit, BF) не превосходит 1,22. Лучший из алгоритмов дает отношение не более чем 1,15. Результаты такого рода можно перечислять и далее. Например, этой проблеме посвящена статья DJhonson, A. Demers and all [71]. Ими установлены гарантированные оценки относительной погрешности в наихудшем случае. Метод перебора с усечением, разработанный А. Валеевой и И. Гареевым и опубликованный в 2003г [9], работает с недопустимыми упаковками до тех пор, пока все предметы не разместятся в контейнеры. Его результативность (достижение оптимума) близка к 100%. Количество предметов от 20 до 1000. Обзор эвристических методов для решения задач прямоугольной упаковки представлен в статье A.Lodi, S.Martello & D.Vigo в 2002г. [75]. Было замечено, что поведение приближенных алгоритмов в «среднем» значительно отличается от полученных оценок. Анализ «среднего» поведения таких алгоритмов как бы приближает к их практическому использованию. Этот факт стимулировал появление работ с вероятностным исследованием задачи. Э.Х. Гимади, В.В. Залюбовским предложен асимптотически точный подход для решения 1DBPP [13]. На этой основе ими разработан приближенный алгоритм со случайными весами предметов. Получены оценки относительной погрешности и вероятности несрабатывания алгоритма.
Среди простых алгоритмов выделяются те, которые служат декодерами в многопроходных алгоритмах. Их разработка стала актуальной в связи с появлением и развитием вероятностных методов локального поиска оптимума.
Они вычисляют значение целевой функции и восстанавливают эскиз упаковки. Для этого с помощью декодера достаточно найти прямую схему кодирования, которой является последовательность координат (х, у), удовлетворяющая условиям допустимости упаковки. В качестве исходных кодов часто используют приоритетные списки (перестановки номеров прямоугольников) [29]. Затем с помощью декодера переходят к прямой схеме. Известны различные алгоритмы - декодеры и между ними возникла некая конкуренция. Широкое распространение на западе получил декодер нижнего-левого угла. Он состоит в размещении очередного прямоугольника в самое левое из самых нижних допустимых положений. Усовершенствованный декодер нижнеголевого угла предложен D.Liu & H.Teng в 1999г. [74]. Различные варианты реализации этого алгоритма использует И.П. Норенков в рамках генетического алгоритма [40]. Е.Норрег & В. Turton применяют декодер нижнего-левого угла в составе других метаэвристик [70]. Н. Murata (Япония) в 1995 г разработал схему парных последовательностей кодирования упаковок для комбинаторного поиска [86]. Для заданного приоритетного списка прямоугольников, упорядоченная пара последовательностей прямоугольников представляет упаковку. Эффективный блочный декодер разработан А.В. Чиглинцевым в 2000 г [29]. Он использует вертикальную блок-структуру упаковки. На базе блочного кодирования упаковки А.С. Мухачевой предложены варианты схемы парного декодера [28] и декодеры перестройки [37].
Среди эвристик более высокого уровня выделяются жадные алгоритмы. Стратегия «жадности» использовалась Г. Аккуратовым, В. Березневым и О.Брежневой [1]. Аналогичная стратегия применяется А.Ф. Валесвой и Э.А. Мухачевой при разработке метода динамического перебора [30]. Многие эвристики включают послойную стратегию, начало которой заложено в работах М. Adamowich & A. Albano [52]. Послойный подход использовался Э.А. Мухачевой для. решения задач гильотинного раскроя [34]. Графовый метод и/или для решения 2D и 1,5DBPP развивается в работах R.Morabito & М. Arenales [80], [82].
К многопроходным эвристикам относится метод последовательного уточнения оценок (Sequentative Value Correction, SVC), берущий начало от идеи объективно-обусловленных оценок Л.В. Канторовича [85], [38]. Метод SVC реализуется по модифицированной схеме FFD с процедурами приоритета и повторения. Упорядочивание элементов основано на экономическом смысле двойственных переменных в линейном программировании. Метод можно назвать общим для решения задач раскроя-упаковки. Он применяется в случаях линейного и гильотинного раскроя, 2-х и 3-х мерной упаковки, а также и для решения задач фигурного раскроя [10], [95]. Кроме того, метод использовался германскими авторами при разработке гибридных алгоритмов [89].
1.5.3. Вероятностные методы локального поиска оптимума
Внесение в детерминированный алгоритм элементов случайности повышает его результативность. Так, например, повысилась эффективность упомянутых выше алгоритмов SVC и DS после внесения в них элементов стохастики [38], [30]. А применение А.Р.Усмановой недетерминированных простых эвристик превзошло все ожидания [45]. Бурное развитие вероятностных методов локального поиска оптимума началось 20 лет назад с появлением метаэвристик для решения NP-трудных задач, систематическое обоснование и характеристика которых приведены в 1996 г. в книге под редакцией E.Aurts, JXenstra [51]. В России обзор вероятностных методов локального поиска оптимума для NP-трудных задач сделан в 2001 г. Ю.А. Кочетовым [24]. В обзоре обсуждаются общие схемы алгоритмов поиска с запретами, имитация отжига и генетических алгоритмов. Показано, что эти разные по своей структуре алгоритмы используют общую математическую конструкцию конечных цепей Маркова. Это свойство гарантирует сходимость по вероятности наилучшего найденного решения к оптимальному решению задачи.
Первыми среди метаэвристик для задач раскроя-упаковки стали применяться генетические алгоритмы. В этой связи хорошо зарекомендовали
себя работы 1992-2000 годов, Е. Folkenaur, например, [61], [62]. В этой работе он ввел процедуру группирования в классическую схему. Классический генетический алгоритм для решения задач 1,5DBPP и 2DBPP представлен, например, в работах D. Пи & RTeng [74]; Н Cehring & A.Bortfeld [65]; А.С Мухачевой, М.А. Смагиным [29]. Они различаются деталями и программной реализацией.
Основы метода «поиск с запретами» (Tabu Search, TS) заложил F.Glover в 1996г. [69]. Метод состоит в управляемом локальном поиске в пространстве решений, для оптимизации которого используются списки запретов. Процесс описывается набором состояний и на каждом шаге производится переход из текущего состояния в одно из соседних. Совокупность всех соседних состояний называется окрестностью. Последнее понятие является существенным в эволюционных алгоритмах, в том числе и для «поиска с запретами». А.И. Ермаченко, А.Р. УсмановоЙ и Ю.А. Кочетовым разработаны алгоритмы «поиска с запретами» для решения задач гильотинного и линейного раскроя [35].
Метаэвристика «имитация: отжига» (Simulated Armeling, SA) также используется при решении задач раскроя-упаковки, например, Loris Faina в 1999 г., [76], H.Forster & G.Washer в 1998 г. [63]. Метод Washer моделирует физический процесс отжига - медленного охлаждения нагретого до высокой температуры твердого тела. Метод SA работает с последовательностью деталей, называемой приоритетным списком (состоянием). В расчетном процессе участвует матрица генерации, элементы которой зависят от степени изменения текущего состояния.
В середине 80-х годов получила разработку новая метаэвристика: алгоритмы муравьиной колонии (Ant Colony, АС) и их модификации, например, Max-Min Ant System [91]. В ней в качестве декодеров используются жадные алгоритмы. Вычислительная парадигма муравьиной колонии сформулирована М. Dorigo [57]. Основными характеристиками модели АС являются: положительная обратная связь, распределенное вычисление и использование конструктивной жадной эвристики. Положительная обратная
связь позволяет быстро находить хорошие решения, распределенное вычисление препятствует ранней сходимости, а жадная эвристика помогает найти допустимые решения на ранних стадиях процесса поиска. Адаптацией общих приемов Ant System к решению проблем раскроя-упаковки посвящены работы А.Ф. Валеевой и М.Н. Аглиуллина [93].
Разработка и исследование эволюционных алгоритмов, в том числе и метаэвристик, подкрепляется результатами численных экспериментов. Экспериментальному исследованию эффективности алгоритмов посвящено небольшое количество специальных статей. Это статьи P. Schwerin&G.Wascher, например, [89], развитие методики G. Wascher в статье А.С.Мухачевой, Э.А. Мухачевой и Г.Н. Белова [38] и некоторых других. В них исследованы алгоритмы FFD и другие эвристики. При этом выделены классы трудных и очень трудных задач. Общая методика исследования алгоритмов NP-трудных задач предложена Ю.А.Кочетовым в статье [14]. Другой путь — результаты численных экспериментов на тестах из международной библиотеки OR-Library [53]. Так, E.Forkenauer выделил класс чрезвычайно трудных задач 1DBPP, называемых триплетами. На этом классе проводятся эксперименты многими исследователями, например, в России А.Ф. Валеевой и И.Р. Гареевым [9]. Тестовые примеры опубликованы P.Wang [96]. Не преувеличивая, можно сказать, что описание каждого нового подхода или эвристического алгоритма обязательно сопровождается численными экспериментами. Результаты экспериментов позволяют сопоставить информационным областям подходящие алгоритмы расчета раскроя-упаковки с учетом требований заказчика.
1.5.4. Применение методов решения задач раскроя-упаковки в автоматизированных системах раскроя-упаковки
Разработка и использование автоматизированных систем раскроя и упаковки представляет собой специальный предмет исследования. Методы расчета раскроя и упаковки занимают в них центральную, оптимизационную часть. Однако они редко используются в чистом виде. На них накладывается
ряд дополнительных, отраслевых ограничений, связанных с особенностями раскройного оборудования и организацией производства до, во время раскроя и после раскроя. В этой связи остановимся на некоторых этапах развития автоматизированных систем.
В конце 70-х, начале 80-х годов наблюдалось опережающее развитие автоматизированных систем по сравнению с использованием методов рационального раскроя и созданием нового автоматизированного оборудования, например, [2], [15], [26]. В этих и других работах речь шла об автоматизации ручных расчетов, как правило, не опирающихся на математические методы.
Одновременно и независимо от автоматизированных систем стали развиваться математические методы расчета раскроя, которые цитировались выше. При этом отдельные результаты, вплоть до экономных карт раскроя внедрялись в производство в качестве рациональных предложений. Например, так обстояло дело с поэтапным внедрением результатов расчета на заводе «Кировский завод» (Ленинград) [32].
Совершенствование оборудования и создание раскройных автоматов. Это направление развивалось главным образом за рубежом: в Европе, США и Японии. Методы расчета оказывались зашитыми в оборудование и АСУ. Если АСУ и подвержено некоторой модификации, то с оборудованием гораздо сложнее. Предприятия, технологические отделы охотно идут на приобретение различного рода АСУ и раскройных автоматов, не задумываясь при этом об экономии материальных ресурсов.
В современном мире, в условиях развитой промышленности наблюдаются различные направления применения математических методов расчета раскроя. Чаще всего реализуется следующая схема: независимое создание и исследование методов расчета раскроя - упаковки; разработка базового обеспечения с учетом производственных условий; передача программного обеспечения посреднику для внедрения на предприятии.
Наиболее перспективными являются предприятия и организации, разрабатывающие раскройное оборудование и специализированные АСУ.
Теоретические предпосылки для создания АСУ-раскроя содержатся в статьях В.Д. Фроловского [46], [47], [48], [49] М.А. Верхотурова [9], [10], Е.В. Бабковой [4], [5], АА. Петунина [41], [94] и других авторов.
Успешно работают над созданием и внедрением автоматизированных систем коллективы под руководством А.А. Петунина (Екатеринбург) и В.Д. Фроловского (Новосибирск).
Система «Сириус» (Система Интерактивного Раскроя и Управления Станками) (А.А. Петунии, ООО Химмаш, г. Екатеринбург) предназначена для проектирования рационального раскроя промышленных материалов на заготовки произвольной геометрической конфигурации, а также для подготовки управляющих программ резки листовых материалов для станков с ЧПУ. САПР «Сириус» имеет постпроцессоры для широкого спектра станков российского и зарубежного производства, в том числе: «Комета», «Енисей», «Кристалл», «Грант», «HEBER» (Болгария), «ESAB» (Швеция), «MESSER GRIESHEIM» (Германия), «TRUMPF» (Германия), «ТАНАКА» (Япония) и другие. Система используется более чем на 30 предприятиях России и ближнего зарубежья. Более подробная информация о системе и поддерживающих ее алгоритмах в работе [41].
Система «Техтран-Раскрой» компании НИП Информатика (В.Д. Фроловский, г. Новосибирск) объединяет возможности САМ-системы с функциями организации производственного процесса, используя опыт работы ряда предприятий, эксплуатирующих машины термической резки. Функции аналогичны системе «Сириус». В состав системы включены данные для машин термической резки «Комета», «Енисей», «Кристалл», «Грант», «HEBER», «ESAB». Система внедрена на нескольких предприятиях: Bivstar Carving Wood, ПКФ Кристалл, Пролетарский завод, Ленинградский металлический завод и других. Всего система установлена на 100 рабочих местах. Внедрением
занимается НИП «Информатика». В системе используются методы расчета, опубликованные в работах В.Д. Фроловского и его коллег.
В рамках проекта РФФИ [49] коллектив В.Д. Фроловского занимается параметрическим моделированием сложных трехмерных объектов и его применением в легкой промышленности.
Краткий обзор существующих САПР конструкторской и технологической подготовки производства одежды сделан Н.А. Коробцевой (Московский государственный университет дизайна и технологии) [22]. Одной из первых разработок в области САПР для конструктора швейных изделий явилась белорусская система «АВТОКРОЙ» (г. Минск), функционирующая в 80-е годы в НПО «Белбыттехника». Первой системой, предназначенной специально для конструирования одежды с помощью персонального компьютера, стала система ЛЕКО, разработки Центрального научно-производственного института швейной промышленности (ЦНИИШП). В настоящее время систему используют небольшие швейные и трикотажные предприятия, а также ВУЗы, ведущие подготовку специалистов в области проектирования швейных изделий. Вслед за ЛЕКО появляется серия САПР: Система АССОЛЬ (Центр компьютерных технологий при Московском физико-техническом институте); Система T-FLEX/ОДЕЖДА использует типовые методики конструирования; ГРАЦИЯ и другие. Одной из последних разработок стала система ELEANDR-САД (Научно-технический центр дизайна и технологии при МГУДТ и компания ООО «Элеандр» 2003).
Проектирование меховых изделий рассматривается в работах группы А.А.Колоколова [21], эти разработки ближе к задаче о минимальном покрытии.
Анализ западного рынка программного обеспечения, представленного в сети Internet, показал, что данный вид программного обеспечения представлен также мало, небольшим количеством компаний, в основном североамериканских. Приведем характеристики зарубежных программных продуктов, заслуживающих наибольшего внимания.
Канадская компания Magic Logic Optimization Inc. предлагает два вида программного обеспечения для Windows 95/98/NT/2000 () -PlanlQ для двумерного раскроя и CubelQ для трехмерной упаковки. PlanlQ предназначен для использования в деревообрабатывающей, стекольной, металлообрабатывающей промышленности, используется также при производстве ковров и обработке пластмассы/пластика. Есть версия программы для обычного двумерного раскроя и для гильотинного. Время работы программы исчисляется секундами. Стоимость программы варьируется следующим образом: обычный раскрой - 1250$, гильотинный раскрой - 1250$, оба вида раскроя - 1995$. CubelQ позволяет сэкономить до 10% места, при заданной ориентации каждого предмета. Имеет графический интерфейс, причем графический движок можно приобрести отдельно. Производителями утверждается, что их CubelQ - единственный программный продукт на рынке, который позволяет загружать любые авиационные контейнеры, специфика которых в том, что они не всегда имеют форму параллелепипеда: к примеру, часть контейнера может занимать рефрижератор, т.е. у контейнера как бы «вырезан» угол. Также CubelQ позволяет учитывать вес объектов и рассчитывать оптимальный центр тяжести. Загружает сотни объектов в 25 контейнеров за время в пределах секунды на Pentium-III-500. Позволяет определять дополнительные правила для каждого объекта (может быть только сверху, сбоку и т.п.). Программный продукт может быть переведен на любой европейский язык. Для любого решения можно распечатать подробную инструкцию по упаковке с рисунками.
Оба программных продукта позволяют получать выходные данные в графическом виде или в табличной форме, а также обладают возможностями импорта/экспорта. Компанией планируется выпуск программы CutlQ для одномерного раскроя.
Программа CutPlanner, представленная новозеландской компанией Remarkable Ideas (), считается лидером среди программ двумерного раскроя и упаковки прямоугольных объектов. Применяется в деревообрабатывающей и металлообрабатывающей промышленности, при
резке стекла и пластмассы. По утверждению производителей, программа позволяет сэкономить от 10 до 100 процентов стоимости материала. Также определяет время, необходимое дли раскроя материала. Главная рекламируемая особенность - возможность быстрой и легкой интеграции с любым существующим раскройным или режущим оборудованием.
1.6. Выводы
Анализ моделей и методов решения задач раскроя в САПР раскроя, а также литературы и современного состояния процесса проектирования карт гильотинного раскроя позволяет сделать следующие выводы:
задача прямоугольного гильотинного раскроя является одной из задач подсистемы генерирования карт раскроя САПР раскроя-упаковки;
на сегодняшний день существует следующие основные группы методов решения задач гильотинного раскроя:
- методы, основанные на линейном целочисленном программировании
и полного перебора с отсечением неперспективных вариантов, которые
позволяют получать решения задачи только при малых размерностях (до 10 —
20);
простые эвристические алгоритмы;
метаэвристики: «поиск с запретами», «имитация отжига», «муравьиная колония», «генетические алгоритмы», из-за высокой сложности которых при увеличении количества деталей резко возрастает время, затрачиваемое на решение задачи, что затрудняет их применение в процессе подготовки производства;
В среде эвристических алгоритмов выделяются:
— уровневые алгоритмы, позволяющие решать задачи с большими
размерами относительно ширины полосы, но малым количеством деталей
одного типоразмера, при изменении этих условий эффективность уровневых алгоритмов резко снижается;
многие эвристики включают послойную стратегию, начало которой заложено в работах М. Adamowich & A. Albano [52]. Послойный подход использовался Э.А. Мухачевой и Л.Ф. Розановой для решения задач гильотинного раскроя [34]. Графовый метод и/или для решения 2DBPP и 1,5DBPP развивается в работах RMorabito & М. Arenales [80], [82]. Послойные алгоритмы неэффективны при малых количествах деталей одного типоразмера;
методология последовательного уточнения оценок (SVC) реализуется по модифицированной схеме FFD с процедурами приоритета и повторения. Упорядочивание элементов основано на экономическом смысле двойственных переменных в линейном программировании. Метод можно назвать общим для решения задач раскроя-упаковки. Он применяется в случаях линейного и гильотинного раскроя, 2-х и 3-х мерной упаковки, а также и для решения задач фигурного раскроя [10], [95].
2. Эвристические методы решения задачи гильотинного раскроя
В рамках диссертационной работы разработано два новых эвристических метода решения задачи гильотннзкдо раскроя. Новые методы решения могут быть нсподьзов-аны при решении задач с большой размерностью, обеспечивая качественный раскрой материала за приемлемое время. Оба разработакз-шх алгоритма основаны иа послойной технологии решения задачи гильотинного раскроя.
2,1. Уровншше алгоритмы
Уровневвш алгоритмі»! были представлены в работе У:.. Coffman, М. Carrey & DJonson [56]. За основу уровневык алгоритмов принимается ириншт иоследоеательііой укладки деталей а полосу с выравниванием по левому и нижнему краю.
Рис 5 - Пример работы уровневых алгоритмов: а - стратегия NFD, б ~ стратегия FPD; в - стратегия ВЇ: D
Укладка деталей' по стратегии Nexi. Fit Decreasing (NFD) представляет собой последовательное заполнение контейнеров. По алгоритму следующая деталь списка укладывается її очередной контейнер. В случае, когда размер детали больше размера свободной области контейнера, создается новый контейнер и деталь укладывается ії него (рис. 5,я),
По стратегии First Fit Decreasing (FF0) следующая деталь списка укладывается в очередной контейнер. В случае, когда размер детали больше размера свободной области контейнера, рассматривается следующая. Новый контейнер сшдается, когда ни одна деталь не может быть уложена (рис. 5,6").
По стратегии Best Fit Decreasing (BFI>) в контейнер укладывается делась наиболее подходящего размера. Нове.-ш контейнер создается, когда ни одна деталь не может быть уложена (ряс. 5,6-!.
('ложность уроішеішх алгоритмов O(nhgn), где п~общее количество леталей.
2.2. Послойная технологии расчета гильотшшого раскроя
Послойная технологий гюдучшла стюе начало от раїюі M.Adamowich & А.АІЬшю [52], Она развита а России ЗА.Мухачевой" и Л.Ф.Розановой ['34].
За основу послойных алгоритмов принимается принцип размещения іхрймоупшьников группами, составляющими хюдоеы (слой). Алгоритм состоит в последовательном выполнении идентичных Hiaroti, каждый и:і когоры>; выполняется зля выделенного на предыдущем шаге прямоугольника {V, W).
Рис. 6 -- Пример работы послойного алгоритма
В модификации послойного алгоритма, предложенной Э.Л.Мухачевой и Л.Ф.Розаиовой [34]. на каждой итерации укладки деталей вычисляется опенка для каждого типоразмера. На основе вычисленных ое^стюк определяется
укладываемый на очередной итерации типоразмер деталей и необходимость поворота деталей на 90. На рисунке 6 представлен пример карты раскроя,
полученный послойным алгоритмом.
Сложность алгоритма 0(пт log т)^ где т — количество типоразмеров деталей, п — общее количество деталей.
2.3. Использование послойной технологии для разработки новых детерминированных методов решения задачи гильотинного раскроя
Описанные в 2.2 подходы послойной технологии, используются для разработки других эффективных методов решения.
2.3.1. Рекурсивный метод
Основной процедурой рекурсивного метода является раскрой прямоугольного участка. При укладке деталей в прямоугольную область образуется два прямоугольных остатка- Детали укладываются группами как в послойном алгоритме. Для получения раскроя получаемых остатков рекурсивно вызывается эта процедура. На каждом шаге рассматривается два варианта укладки деталей (с поворотом или без него) и два варианта формирования остатков (первый рез делается вертикально или горизонтально).
Рекурсивный алгоритм (Recourse algorithm, RCA) является специализированной эвристикой с частичным перебором, ориентированной на эффективный раскрой листового материала. Основной процедурой метода является укладка деталей в прямоугольную область материала.
Для заданной прямоугольной области из списка деталей выбирается деталь с наибольшей меньшей стороной. Далее рассматривается каждый из четырех вариантов укладки выбранной детали в имеющуюся прямоугольную область (рис. 7). В результате укладки образуется две новые области меньшего размера.
a h с d
Рис* 7 - Способы укладки детали в прямоугольную область
Для варианта а алгоритм укладки вьплвдш следующем образиш
1> BlockaDoiie - значение указателя ш первый элемент списка уложенных деталей на текущий момент времени.
2, Укладка выбранной детали с учетом ее комплектности, как указано на
рисунке 7fa> При укладке каждая деталь добавляется в голову списка
уложенных деталей.
3. Запуск процедуры укладки деталей в прямоугольную облвеї ь А.
4 Запуск процедуры укладку деталей в прямоугольную область В.
Восстановление комплектности деталей путем перебора списка уложенных деталей от текущей головы епиека до BlocksDone.
Head А - значение указателя ни голову списки уложенных деталей па тек-ущий момент времени (для варианта (Ь) используется переменная HeadB, для (с) - HeadC дш (d) - HcadD),
Текущая голова описка устанавливается в BiocksDone*
Во время выполнения процедуры эти действия выполняются четыре pais для каждого варианта раскроя* изображенных на рисунке 7. Результатом выполнение будет древовидная структура, изображенная на рисунке 8. Она представляет собой четыре односвизных списка, причем часть элементов, начиная е BloeksDone, шляттт общими.
Рис- 8 - Структура результата процедуры построения карты раскроя
По наименьшему количеству бесполезных отходов Q выбирается одна из полученных карт раскроя, корректируется комплектность деталей с учетом выбранной карты раскроя. Элементы списков, не используемые в выбранном варианте, удаляются,
В задаче раскроя листов за прямоугольную область материала принимается весь лист. В задаче раскроя полосы от неиспользованной части рулона материала отделяется фрагмент - слой. Ширина W слоя равна ширине полосы W^ а длину слоя V определяет размер укладываемой детали (рис. 9). Для остатка А вызывается процедура раскроя прямоугольного участка материала. В процессе работы алгоритма рассматривается два вариапга создания слоя - с поворотом укладываемой детали на 90 и без него. После получения раскроя обоих вариантов нового слоя, выбирается слой с большим коэффициентом раскроя.
Благодаря выбранной структуре данных, метод отличается высоким качеством получаемых результатов при незначительных затратах времени несмотря на большое дерево перебора. Метод легко и быстро может быть адаптирован под дополнительные технологические ограничения. Метод строит полную карту раскроя за один проход, делая перебор для ее фрагментов.
Упрощенная модификация данного метода может быть использована в более сложных алгоритмах в качестве эффективного декодера. Этот вариант реализации не предусматривает перебора вариантов укладки.
Рш.\ 9 - Два способа образования нового слоя: а - - деталь укладывается без поворота; 6 - деталь укладьт&ется с поворотом
Выбор способа уклада раскроя с иенользошшием оценок алгоритме:
сразу же па этапе построения карты аналогичных используемым в послойном
:тш
где и
которые могут быть уложены в один спой бкз поворша;
количество деталей,,
>ые моїуг быть уложены В один слой е с ~ номер укладываемой р L' и W' размер!,! текущего
шраетсл тот вариант укладки, который соответствует меньшему
Для уменьшение вычислительной СЛОЖНОСТИ ограничение перебора вариантов укладки деталей по количеству вложенных вызовов процедуры укладки в прямоугольную область, В случае, когда
процедуры укладки больше >%хш алгоритм работает по упрощенной ехемс,
Сложность алії.
пт \щт), гт к -гальотинпости. Это шшчдаг, что алгоритм работает быстрее для крупных заготовок, Сложность упрощенной модификации алгоритма 0(nm\ogm)y где
їтялсїз, п - общ% количество деталей.
раскроить лі-
заготовки четырех различных видов
количество указаны в ті
ты заготовок и их заданное
абяица
їходіше дашшіе тадтт
їй в диет для этого
глубина рекурсии ї, вариаїгт (а); і глубина рекурсии 2,
варвдшы (b, d) не имеют смысла
Z<№ ЪМ"
Qa - і?
UTTlVEMHUuj||b *F "^ "
глуоина рекурсии 3, варианты (а, с):
варианты (b? dj не имеют смысла выбирается вариант (х a), Qcun, = 9
лубина рекурсии 1. вариант (b):
-#-,
глубина рс&урши 2. Шфшшты (1% d):
анты (а, с) пс имеют смысла
въкшраетсн вариант Ос - Ь>. О,, - 2
глубина рекурсии 1, вариант (с)
№
глубина рекурсии I, вариант (d);
>скурсии 2У варианты ((х сі):
db л %d
ї лубина рекурсии 2* варианты (а, с)
варианты (а, с) не имеют смысла выбирается r-нзриант (х b). Qjx - 15
варианты (п, й) іш имеют смысла выбирается вариант (х ~ а), & - IJ
М< ~ w
1 Іри выборе варианта раскроя их карты выглядят следующим образом:
.1 I. I і... J I і І З t і
(а) (Ь) (с) Q* = 3? Qb~2 QC~6I О, = 26 Выбирается вариант (b) по минимальной площади бесполезных отходов 2.3.2* Метод ншежп пустых корзин Метод поиска пустых корзин таюйй рассматривает прямоугольные области материала. Изначально вся полоса (весь лист) представляє гея одной прямоугольной областью- При укладке деталей производится добавление всевозможных црямоу гсэдшых остатков в список. Детали укладываются груїш&ші как в послойном алгоритме- Во избежание потери свойства гильотипгюсти все прямоугольные области, пересекшшдиеся скшользов&нной областью, разделяются на несколько частей ретми, ограничивающими использованную часть материала при укладке деталей. Далее объединяются прямоугольные области, слияние которых ие повлечет -іа собой потерю свойства гяльотанностн раскроя. Алгоритм является специализированной эвристикой с частичным перебором, ориентированной на эффективный раскрой рулонного материала. Основной процедурой метода является перебор списка всевозможных прямоугольных областей незанятых участков материала, называемых остатками, Перед началом работы метода следует отсортировать соисок деталей по убыванию меньшей стороны. всю полосу щиого элемента, характеризуют на каждой ятера подЬирается иаи&олее подходящий по размерам остаток. >раэом: ори укладке деталей в прямоугольную область список ості Рассматривается задача гильотинного раскроя на прямоугольные детали нескольких типов. Различаются задачи раскроя полубескоиечной полосы (1,5 Dimensional Guillotines Cutting Problems, 1,51 8Р) в задачи раскроя листов, 2DCSP. Под гильотинным понимается раскрой, реализуемый 1:гееледо.ааз:ель.носгыо сквозных резов, параллельных кромкам материала (рис. 3). При этом направление детали либо фиксируется, либо ее можно поворачивать на 90. Исходная информация задач может ОЕ.ГГЬ задана кортежами следующего евда; у — признак гильотинности; у = 2, если раскрой гильотинный; 7 0 в противном случае; є - признак направления детали в полосе (листе); е = 1, если детали можно поворачивать на 90; е = 0 в противном случае. В случае 1,5DCSP требуется найти гильотинный раскрой рулона R на прямоугольные детали, минимизирующий длину Л использованной части полосы. В случае 2DCSP требуется найти совокупность гильотинных раскроев листов R, минимизирующих их суммарное количество N. Решения задач может быть записано в виде кортежей Д Л для 1,5DCSP и Пі,П2,-М],-Мм Для 2DCSP, в которых П - последовательность сквозных резов рулона, TIj - последовательность сквозных резовj-ro листа; А-длина использованной части полосы; JV- количество использованных листов. В течение последних пятидесяти лет" проблема «раекроя-упзкснїки.о привлекает внимание научных исследователей и производственников. Начало хсому положила в 1951 г, книга Ленинградских ученых ЛВ. Канторовича и В.А.Залїаллера [19]. Задачи раскроя рассматривание Е. ИМИ как примеры применения ранее развитого Л.В.Канторовичем линейного программирования, })дя решения эадач раскроя-укашвзш применяется модель .чиненного программирования с неявно задашюй информацией о раскроях (столбцах матрицы). Для генерации столбцов В.А.Залгадлером был предложен прием. предвосхитивший появившееся позднее динамическое программирование. Аналогичные методы получили развитие в 60-е годы за рубежом в работах P.Giimore & RGomory [67], [68] и позднее XTerno, RXindeman & G.Scheithauer [92]. Для решения задачи генерирования раскроя были разработаны метод склейки И.В.Романовским [43], сеточный метод для линейного раскроя В.А.Булавским и МА.Яковлсвой [6], для гильотинного раскроя Э.А.Мухачсвой [33], [39]. На базе линейного программирования Э.А.Мухачевой разработаны также алгоритмы условной оптимизации, учитывающие специфику реального производства [31]. В то время основной целью этих и многих других работ являлось применение линейного программирования в сфере производственных задач. Эта цель в той или иной мере была достигнута в условиях массового и серийного производства. В зарубежной литературе признан приоритет Л.В.Канторовича и В.А.Залгаллера [58]. Однако задачи раскроя и упаковки по своей сути являются проблемами дискретной оптимизации и их решение с помощью линейного программирования не более чем непрерывная релаксация, которая дает решение близкое к оптимальному при дополнительных ограничениях, возникающих в условиях серийного производства. Далее задачи раскроя-упаковки рассматриваются как прикладные проблемы комбинаторных задач исследования операций. Н.Гэри и Д.Джонсон показали, что задача одномерной упаковки в контейнер принадлежит к классу MP-трудных задач и для точного решения необходимо применять схемы полного перебора [11], [64]. Впервые качественная типология в области раскроя-упаковки проведена в 1990 г. немецким ученым H.Dykhoff [59]. Она принята в мировой практике и используется при изучении моделей и методов решения задач раскроя-упаковки. Разнообразие моделей определяется, прежде всего, фактором геометрии. Различаются задачи линейного (одномерного), прямоугольного (двухмерного) и параллелепипедного (трехмерного) раскроя-упаковки. Среди этих задач выделяются гильотинный раскрой и упаковка. Особо выделены проблемы размещения деталей сложной геометрической формы в заданных областях. Для них на первый план выступают информационные проблемы задания фигур, учета и обеспечения их непересечения, кодировки и другие. Задачи раскроя-упаковки являются типичными представителями NP-трудных проблем и для их решения применяются общие подходы: точные методы, простые эвристики и метаэвристики. Ввиду неполиномиальной сложности точных алгоритмов, авторами многих работ уделяется значительное внимание приближенным методам и эвристикам. В течение 90-х годов прошлого столетия на тему раскроя-упаковки было выпущено шесть специальных изданий: под редакцией H.Dyckhoff & G.Wascher в 1990 г. [60], S.Martello в 1994 г. [77], [78], Y.Lirov в 1995 г. [73], E.Bischoff & G.Wascher в 1995 г. [54], E.Mukhacheva в 1997 г. [83], KYanasse в 1999 г. [98], P.Wang & G.Washer в 2000 г. [97]. Более того, сотни статей опубликованы в международных и российских журналах: European Journal of Operational Research (EJOR), Computers & Operations Research, Computers & Industrial Engineering, Operations Research Letters, Pesquisa Operacional; Информационные технологии, Автоматика и телемеханика, Дискретный анализ и исследование операций, Вестник высшей школы, Кузнечно-штамповочное производство и другие центральные и ведомственные издания. При этом статьи и книги имеют как теоретический, так и прикладной характер. Последний аналитический обзор проведен в 2003 году под руководством Э.А.Мухачевой по заданию РФФИ, проект 03-01-07002. В советский период проводились научно-практические семинары и конференции в Ленинграде, Уфе, Звенигороде и других городах. В современный период организуются небольшие секции в рамках работы конференций: Математическое программирование и приложения (Екатеринбург, ИММ УРО АН РФ); Дискретный анализ и исследование операций (DAOR, Новосибирск, ИМ СО РАН); Компьютерные науки и информационные технологии (CS1T, Уфа, УГАТУ); Ресурсосберегающие технологии (ОПТИМ, СПетербург); Методы оптимизации и их приложения (Байкальская международная конференция по математическому программированию, Иркутск); Дискретная математика и экономические приложения (Омск, филиал ИМ СО РАН). Основной процедурой рекурсивного метода является раскрой прямоугольного участка. При укладке деталей в прямоугольную область образуется два прямоугольных остатка- Детали укладываются группами как в послойном алгоритме. Для получения раскроя получаемых остатков рекурсивно вызывается эта процедура. На каждом шаге рассматривается два варианта укладки деталей (с поворотом или без него) и два варианта формирования остатков (первый рез делается вертикально или горизонтально). Рекурсивный алгоритм (Recourse algorithm, RCA) является специализированной эвристикой с частичным перебором, ориентированной на эффективный раскрой листового материала. Основной процедурой метода является укладка деталей в прямоугольную область материала. Для заданной прямоугольной области из списка деталей выбирается деталь с наибольшей меньшей стороной. Далее рассматривается каждый из четырех вариантов укладки выбранной детали в имеющуюся прямоугольную область (рис. 7). В результате укладки образуется две новые области меньшего размера. Для варианта а алгоритм укладки вьплвдш следующем образиш 1 BlockaDoiie - значение указателя ш первый элемент списка уложенных деталей на текущий момент времени. 2, Укладка выбранной детали с учетом ее комплектности, как указано на рисунке 7fa При укладке каждая деталь добавляется в голову списка уложенных деталей. 3. Запуск процедуры укладки деталей в прямоугольную облвеї ь А. 4 Запуск процедуры укладку деталей в прямоугольную область В. 5, Восстановление комплектности деталей путем перебора списка уложенных деталей от текущей головы епиека до BlocksDone. 6, Head А - значение указателя ни голову списки уложенных деталей па тек-ущий момент времени (для варианта (Ь) используется переменная HeadB, для (с) - HeadC дш (d) - HcadD), 7, Текущая голова описка устанавливается в BiocksDone Во время выполнения процедуры эти действия выполняются четыре pais для каждого варианта раскроя изображенных на рисунке 7. Результатом выполнение будет древовидная структура, изображенная на рисунке 8. Она представляет собой четыре односвизных списка, причем часть элементов, начиная е BloeksDone, шляттт общими. По наименьшему количеству бесполезных отходов Q выбирается одна из полученных карт раскроя, корректируется комплектность деталей с учетом выбранной карты раскроя. Элементы списков, не используемые в выбранном варианте, удаляются, В задаче раскроя листов за прямоугольную область материала принимается весь лист. В задаче раскроя полосы от неиспользованной части рулона материала отделяется фрагмент - слой. Ширина W слоя равна ширине полосы W а длину слоя V определяет размер укладываемой детали (рис. 9). Для остатка А вызывается процедура раскроя прямоугольного участка материала. В процессе работы алгоритма рассматривается два вариапга создания слоя - с поворотом укладываемой детали на 90 и без него. После получения раскроя обоих вариантов нового слоя, выбирается слой с большим коэффициентом раскроя. Благодаря выбранной структуре данных, метод отличается высоким качеством получаемых результатов при незначительных затратах времени несмотря на большое дерево перебора. Метод легко и быстро может быть адаптирован под дополнительные технологические ограничения. Метод строит полную карту раскроя за один проход, делая перебор для ее фрагментов. Упрощенная модификация данного метода может быть использована в более сложных алгоритмах в качестве эффективного декодера. Этот вариант реализации не предусматривает перебора вариантов укладки. Практическая ценность диссертационной работы заключается в создании на базе разработанных методов программного обеспечения для проектирования планов гильотинного раскроя прямоугольных деталей в составе автоматизированного рабочего места технолога планово-заготовительного производства. Основными подсистемами структуры САПР раскроя-упаковки являются: 1. Подсистема препроцессорной обработки исходной информации об объектах и областях размещения, которая предназначена для подготовки, хранения и редактирования данных о геометрии объектов для решения конкретной задачи, 2. Подсистема генерирования карт раскроя, основной целью гсоторой является формирование на основе задания на рациональное размещения геометрических объектов в автоматическом режиме. 3. Подсистема постпроцессорной обработки информации о размещенных іеомеїрических объектах (подсистему разработки технологического процесса раскроя-упаковки). Подсистема препроцессорной обработки исходной информации предназначена для подготовки, хранения и редактирования данных о геометрии объектов для решения конкретной задачи. Информация о геометрических характеристиках объекта используется не только для получения графического изображения, но и для расчета различных характеристик объекта и технологических параметров его изготовления. Подсистема генерирования карт раскроя преобразует информацию об объектах согласно их размещению в области. Существует три способа получения карт раскроя: 1, Ручной, при котором карта раскроя полностью составляется человеком. Качество карт раскроя-упаковки при этом способе зависит от: — количества объектов, которые необходимо разместить; — опыта операторов, производящих укладку; — времени, отведенного на процесс размещения, 2. Автоматический, при котором процесс генерирования карт раскроя-упаковки происходит без вмешательства человека. Поиск и выбор рационального решения осуществляется программными процедурами на основе исходных требований, сформулированных оператором. 3. Автоматизированный, подразумевающий разумное разделение функций хмежду человеком и машиной [6], [11]. Критерием рациональности размещения объектов является расчетный коэффициент раскроя и затраченное время. Предлагаемая система СЕТАМ1-CUT является автоматизированной подсистемой генерирования карт раскроя, К моменту раскроя необходимо знать размеры раскраиваемого материала. В зависимости от наличия или отсутствия на предприятии мерного материала возможны два варианта организации работ: создание архива карт раскроя с их дальнейшим повторным использованием или постоянное ведение оперативного раскроя в зависимости от фактического наличия требуемого материала. Возможно сочетание этих форм организации работ. Первый из этих способов (с архивом) более пригоден для серийного производства с постоянной номенклатурой. При индивидуальном (единичном) производстве приходится вести постоянный оперативный раскрой. Постпроцессорная обработка состоит из следующих задач: — возврат к исходным поверхностям уложенных объектов; — описание последовательности вырезки деталей; — моделирование хода режущего инструмента; — получение управляющей программы на карту раскроя для станка с ЧПУ. Функциональная модель системы CETAM1-CUT, а также ее место в ТПП САПР раскроя представлена в приложении 4. Разработанные методы могут быть использованы для решения задач рационального размещения прямолинейных объектов. Однако применение программного обеспечения к решению конкретной задачи должно проводится с учетом специфики как самой задачи, так и ограничений, накладываемых на ее решение. Экономия материалов представляет собой сложную комплексную проблему. Одним из путей и средством решения этой проблемы является рациональный раскрой материалов. В большинстве отраслей промышленности и строительства приходится встречаться с раскроем материала. Металл, дерево, фанера, стекло и другие промышленные материалы поступают на производство в виде целых единиц: листы, профильный прокат, полосы. При использовании их приходится раскраивать на части нужных размеров и форм. При этом, как правило, оказывается невозможным полное использование материала, и некоторая часть его идет в отходы, которые обычно не находят применения, поэтому необходимо максимально уменьшать отходы. Размеры заготовки устанавливаются на основе конструкторской документации, в зависимости от применяемой техники резания и технологии производства, При резке металлопроката на соответствующем оборудовании (термическим способом, механическим или в штампах) необходимо предусмотреть припуски на разрезку, зажим, перемычки между деталями, нв механическую обработку, под захваты при термообработке деталей типа валов и др. Поэтому важной технологической задачей предприятия является применение новых, более совершенных способов резки проката и труб, позволяющих уменьшить потери материала, связанные с припусками [2]. Для деталей, вырезаемых термическим способом из листового проката, к размерам деталей по чертежу добавляются припуски на разрезку заготовок (ширину реза) и припуски на последующую механическую обработку (на строгание после резки). При установлении размеров припусков учитываются: марка стали, толщина металла, размера заготовки и способ резки. При определении размеров заготовки, вырезаемой механическим способом (на гильотинных и пресс-ножницах? дисковых Й ленточных пилах, вибрационных и дисковых ножницах, приводных ножовках, резцом) учитывается размер детали по чертежу, припуск на разрезку, припуск па зажим. Величины припусков устанавливаются в соответствии с технологией изготовления детали и в зависимости от имеющегося оборудования [3]. Размеры заготовок, рассчитанные с учетом припусков и закодированные определенным образом, являются исходной информацией для расчета оптимального раскроя с помощью программного обеспечения. Рекурсивный метод способен получать качественные решения за относительно небольшое время. Это позволяет использовать его в работе метаэвристик в качестве процедуры, строящей карту раскроя, В эксперименте участвуют две метаэвристики: «поиск с запретами» (TS) [55], [69], [72] и «имитация отжига» (SA) [17]? [63], [76]. Во ксех экспериментах этой группы разрешены повороты деталей, причем при использовании метаэвристик повороты деталей делает процедура, строящая карту раскроя. Следует обратить внимание на то, что, в отличие от рекурсивного метода в чистом виде, при использовании метаэвристик метод запускается много раз с различной последовательностью деталей- Целью эксперимента является получение незначительного улучшения результата, полученного рекурсивным методом, что будет подтверждать высокую эффективность самой эвристики. Результаты экспериментов представлены в приложении 2, Метод ПОИСКИ пустых корзин способен получать качественные решения за относительно небольшое время. Это позволяет иснолкшвагь его в раЙоте метаэврнстнк в качестве процедуры, строящей карту раскроя. В эксперименте снова участвуют те же метазвристию : «поиск с апретами» (TS) [55], [6913 [72] и «имитация отжига» (SA) [17], [63 J, [76]. Во всех экспериментах этой і руины разрешены повороты деталей причем при иеполышшшии мегаэвриетик повороты деталей делает процедура, строящая карту раскроя. Следует обратить внимание на то, что, в отжгше от метода поиска пустых корзин в чистом виде, при использовании метаэвристик метод запускается много рат с различной последовательностью деталей. Целью эксперимента является получение иезшчїїгельиого улучшения результата, полученного методом поиска пустых корзин, что будет подтверждать высокую эффективность самой эвристики. На основе полученных данных можно сделать следующие выводы: — использование метаэвристик позволяет улучшить результат, полученный методом поиска пустых корзин, но незначительно, особенно при большом количестве деталей; — использование метаэвристик влечет значительное увеличение временных затрат, особенно при большом количестве деталей. Таким образом, использование метаэвристик становится нерациональным при количестве деталей более 500. Система CETAMI-CUT позволяет накапливать статистику уже решенных задач и использовать ее в процедуре автоматизированного выбора метода решения задачи раскроя на основе входных данных. В рамках этого численного эксперимента рассматривается только задача раскроя полосы с разрешенными поворотами деталей, при количестве деталей от 300 до 4 000, Именно при таком количестве деталей, судя по результатам сравнительных экспериментов, выбор лучшего метода решения зависит от размеров деталей (см. приложение 1). Процедура автоматизированного выбора метода решения на основе входных данных задачи показала хорошие результаты. Б большинстве случаев выбранный метод решения позволяет получить лучший результат. Эксперимент 2, Количество деталей 1 000-4 000, ширина полосы 100 (таблица 6). Процедура автоматизированного выбора метода решения на основе входных данных задачи снова показала, хорошие результаты. Следует обратить внимание на предпоследнюю строку таблицы 6: среднее значение коэффициента раскроя при решении задач с количеством деталей 1 000 - 4 000, типоразмеров 200 - 400? шириной полосы 1005 размерами деталей 40 - 60; 30 -60 при использовании процедуры автоматизированного выбора метода оказалось выше, чем при использовании любого другого метода на одном и том же наборе задач. Это объясняется тем, что на некоторых задачах из этого набора лучшие результаты показал рекурсивный метод, а на других - метод поиска пустых корзин, что подтверждает высокую эффективность процедуры выбора метода раскроя. В рамках исследования качества работы процедуры автоматизированного выбора метода решения задачи раскроя эксперименты с раскроем листов, эксперименты с участием метаэвристик не представляют интереса, так как , выбор лучшего метода решения не зависит ни от количества деталей ни от их размеров.Постановка задачи гильотинного раскроя
Использование послойной технологии для разработки новых детерминированных, методов решения задачи гильотинного растфоя
Применение разработанного программного обеспечения в САПР раскроя-упаковки Error! Bookmark not defined
Использование рекурсивного метода в составе метаэвристшс
Похожие диссертации на Проектирование гильотинного раскроя листового и рулонного материала с использованием послойных алгоритмов
