Содержание к диссертации
Введение
1. Основные задачи двумерного раскроя-упаковки и методы их решения .! 1
1.1. Задачи раскроя и упаковки и их классификация 11
1.2. Методы математического программирования 15
1.3. Точные методы комбинаторной оптимизации 16
1.4. Приближенные и эвристические методы 18
1.5. Вероятностные методы локального поиска оптимума 20
] .5.1. Генетические алгоритмы 21
1.5.2. Поиск с запретами 22
1.53. Имитация отжига 24
1.5.4. Муравьиная колония 24
1.6. Использование декодеров 25
1.7. Численные эксперименты 28
1.8. Выводы 29
2, Математические модели задач двумерного прямоугольного раскроя. Процедуры кодирования и декодирования 31
2.1. Исходная информация задач двумерного прямоугольного раскроя 31
2.2. Модель прямоугольной упаковки и условия допустимости 32
2.3. Постановка задач прямоугольного раскроя и упаковки 35
2.4. Процедуры декодирования в решении задач двумерного прямоугольного раскроя и упаковки 37
2.4.1. Рекурсивный декодер 38
2.4.2. Декодер поиска пустых корїин 41
2.4.3. Декодер «Нижний левый» 42
2.4.4. Блочный декодер 44
2.5. Декодер последовательного конструирования для прямоугольной упаковки 46
2.6. Выводы по второй главе 51
3. Метод поиска с запретами с переменными окрестностями и вторичными оценками для решения задач двумерного прямоугольного раскроя 52
3.1. Методика поиска с запретами для решения задач дискретной оптимизации 52
3.2. Алгоритм поиска с запретами с переменными окрестностями и вторичными оценками для решения задач двумерного прямоугольного раскроя 57
3.3. Реализация метода поиска с запретами Й составе автоматизированной системы проектирования карг двумерного прямоугольного раскроя CETAMI-CUT 66
3.4. Выводы по третьей тлаве 71
4. Численные эксперименты 72
4.1. Выбор числа шагов до смены вторичной оценки , 72
4.2. Эксперимент на случайно сгенерированных примерах 73
4.2.1. Примеры с количеством предметов 40 74
4.2.2. Примеры с количеством предметов 400 77
4.3. Сравнение декодера последовательного конструирования и блочного декодера 78
4.4. Эксперимент на безотходных, примерах Евы Хоппер 80
4.5. Выводы по четвертой главе 82
Заключение 83
Литература
- Точные методы комбинаторной оптимизации
- Модель прямоугольной упаковки и условия допустимости
- Алгоритм поиска с запретами с переменными окрестностями и вторичными оценками для решения задач двумерного прямоугольного раскроя
- Эксперимент на случайно сгенерированных примерах
Введение к работе
Диссертационная работа посвящена разработке методов расчета для задачи двумерного прямоугольного раскроя рулонного и листового материала на базе метаэвристики «Поиск с запретами», и реализации разработанных методов в составе программного обеспечения для автоматизированного проектирования раскроя.
Актуальность темы исследования. Актуальность проблемы создания эффективных эвристических и метаэвристических алгоритмов для решения задачи двумерного прямоугольного раскроя-упаковки обусловлена высокой сложностью решаемых задач, а также обширной областью практического применения данных задач. Проблемы раскроя-упаковки являются важным классом задач дискретной оптимизации. К прямоугольному раскрою-упаковке двумерного материала сводятся многие реальные процессы.
Задача раскроя-упаковки принадлежит к классу NP-трудных задач, то есть для ее точного решения не существует алгоритма полиномиальной сложности. Более того, рассматриваемая задача является NP-трудной в сильном смысле, так как содержит NP-трудную задачу в качестве подзадачи. До сих пор не разработано эффективных и достаточно точных способов расчета нижних границ для данной задачи, позволяющих определить достижение оптимума. Таким образом, точные алгоритмы сводятся к полному перебору вариантов. В связи с этим, использование точных алгоритмов для решения задачи раскроя-упаковки часто оказывается нецелесообразным и невозможным по причине больших затрат времени. Поэтому большое значение уделяется разработке и исследованию эвристических методов оптимизации. Одним из перспективных направлений является разработка метаэвристических алгоритмов, основанных на известных метаэвристических подходах, с успехом используемых для решения многих задач дискретной оптимизации. Для большинства
метаэвристик доказана их ассимптотическая сходимость, что является важным доводом в пользу их активного использования.
На данный момент для решения задач дискретной оптимизации наиболее активно используются генетические алгоритмы. Также широкое распространение получили метаэвристики «Поиск с запретами», «Имитация отжига» и «Муравьиной колонии».
Помимо выбранной методики и особенностей ее реализации конкретным автором, большое влияние на качество и быстроту получения результата
оказывает выбор алгоритма декодера Под декодером обычно понимается процедура, которая позволяет на основе абстрактной информации (например, приоритетный список заготовок), однозначно определить взаимное положение заготовок и построить карту раскроя. Выбор декодера является важным вопросом при проектировании нового метода. От него не в меньшей степени зависит качество конечного результата, чем от построения алгоритма метаэвристики. Также очень важен правильный выбор способа генерации множества решений на очередном шаге алгоритма и оценочной функции.
Таким образом, представляет интерес разработка и программная реализация метаэвристических алгоритмов, а также исследование их поведения на разных классах задач раскроя-упаковки и с применением различных процедур декодеров, с целью выявления наиболее перспективных путей дальнейшего развития таких методов. Особенно важным представляется возможность использования программного обеспечения на базе разработанных метаэвристических алгоритмов для оперативного и высокоэффективного проектирования отдельных производственных процессов и в составе более сложных систем автоматизации производственного цикла, В этом заключается актуальность данной работы.
7 Цель работы
Разработать метод решения задач прямоугольного раскроя и упаковки на базе метаэвристики «Поиска с запретами».
Для достижения цели работы были поставлены следующие задачи:
Разработать обобщенную математическую модель для задач раскроя-упаковки, рассмотренных в диссертации;
Разработать процедуры декодеров и использовать их в составе метаэвристического алгоритма «Поиск с запретами»;
Модифицировать вычислительную схему метода «Поиск с запретами» на основе использования дополнительных функций оценки решений, и исследовать эффективность предложенного метода для решения задач прямоугольной упаковки и гильотинного раскроя;
Разработать программное обеспечение на основе предложенных методов. Провести анализ эффективности и характеристик различных вариантов реализации метода поиска с запретами на основе результатов численных
экспериментов;
5. Провести численные эксперименты на тестовых наборах данных и
сравнить полученные результаты с результатами других исследователей.
Методы исследования
Результаты исследований, выполненных в работе, базируются на методах исследования операций, теории и практике математического моделирования, принципах модульного и структурного программирования. Для анаоиза эффективности методов применялись численные эксперименты и методы их обработки-
8 На защиту выносятся:
Обобщенная математическая модель для задач двумерного прямоугольного раскроя-упаковки;
Декодер последовательного конструирования для задачи прямоугольной упаковки;
Алгоритм поиска с запретами с переменными окрестностями и вторичными функциями оценки для решения задач прямоугольной упаковки и гильотинного раскроя полубесконечной полосы и листового материала;
Программная реализация разработанных методов в составе системы двумерного прямоугольного раскроя СЕТ AMI-CUT;
Результаты численного эксперимента на основе созданного алгоритмического и программного обеспечения.
Научная новизна работы. Новыми в работе являются:
L Разработана обобщенная математическая модель для задач раскроя-упаковки, рассмотренных в диссертации. Ее составными частями являются модели исходных данных и результатов решения задачи раскроя-упаковки, а также условия допустимости для гильотинного и негильотинного раскроя. На основе разработанной модели сформулированы постановки задач и целевые функции;
2. Разработан декодер последовательного конструирования для задачи прямоугольной упаковки. Новыми в алгоритме являются метод описании границы упаковки и процедура укладки прямоугольника. Разработанный декодер превосходит известный алгоритм «Нижний Левый». Найдены классы задач, на которых он превосходит также разработанный
аспирантом кафедры А,В. Чиглинцевым «Блочный декодер». Показано, что разработанный алгоритм обладает свойством реставрации;
3, Модифицирован метод поиска с запретами: нредложено использовать дополнительные функции оценки при выборе следующего решения. Исследовано влияние вторичных оценок на процесс поиска и изменение целевой функции.
Практическая значимость работы:
Метод интегрирован в систему автоматизированного проектирования двумерного прямоугольного раскроя СЕТ AMI-CUT. Имеются акты внедрения разработанных методов и программного обеспечения в учебный и производственный процесс. Программа СЕТ AMI-CUT зарегестрирована в РОСПАТЕНТ, свидетельство № 20046 і 1452;
Программная реализация метода поиска с запретами показала лучшие результаты в сравнении с алгоритмами других исследователей на широком наборе классов задач прямоугольной упаковки и гильотинного раскроя с количеством предметов до 500.
Апробация работы
Работа выполнялась при поддержке грантов Российского Фонда Фундаментальных Исследований (РФФИ), проекты 99-01-000937 и 01-01 -000510; технического задания фирмы АСКОН-М (Москва).
Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:
I. Двенадцатая Байкальская международная конференция «Методы оптимизации и их приложения» (Иркутск, 2001);
#
Всероссийская научно-практическая конференция "Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования4 ОПТИМ-2001 (С.-Петербург, 2001);
Всероссийская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002);
Международная научно-техническая конференция «Информационные системы и технологии» ИСТ-2003 (Новосибирск, 2003);
Семинары группы изучения метаэвристических алгоритмов института математики СО РАН (Новосибирск, 2003);
Семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.
Публикации. По теме диссертации опубликовано II работ: 7 статей, в том числе две в центральном журнале, 3 трудов конференций, выполненных по теме диссертации при непосредственном участии автора, и один акт о регистрации программы.
Структура и объем работы
Диссертация состоит из введения, четырех глав, выводов, списка литературы, и приложений, содержащих акты внедрения результатов работы. Работа изложена на 95 страницах машинописного текста, кроме того» содержит 15 рисунков и 8 таблиц. Библиоірафический список включает 98 наименований и занимает \ 0 страниц.
1]
Точные методы комбинаторной оптимизации
Методы, основанные на линейном целочисленном программировании, приемлемы для решения задач линейного и гильотинного раскроя. Что касается классов задач негильотинной упаковки, то алгоритмы LP вряд ли можно считать подходящими для их решения. Задачи ВРР (Bin Packing Problems) -классические представители NP-трудных проблем и для их решения, как правило, применяются методы полного перебора с отсечением неперспективных вариантов.
Большинство существующих точных методов решения задачи прямоугольного не гильотинного раскроя сводятся к перебору всего множества допустимых решений. Методы улучшенного перебора объединены для этих задач под названием «метода ветвей и границ». В 1977 г. И.В,Романовским представлена общая идея переборного метода для решения общей экспоненциальной задачи, и предложена его конкретизация в виде метода «ветвей и границ» (Method Branch and Bound, МВВ) для решения задач упаковки [35J. В дальнейшем метод получает развитие за счет введения процедур сокращения перебора в работах В.М.Картака и Э.А.Мухачевой [29], [81]. Независимо за рубежом выходит серия статей S.Martello & P.Toth, посвященная разработке улучшенных версий МВВ, называемых методами МТР, для решения 1DBP [77].
Большинство существующих комбинаторных методов решения задач прямоугольного негильотинного раскроя, 1.5DBP и 2DBP, и размещения объектов сложных форм сводятся к перебору всего множества допустимых решений. Методы улучшенного перебора объединены и для этих задач под названием «метода ветвей и границ». В 1986 г, Ю.Г.Стоян и С.В.Яковлев описали общую схему метода и привели основные алгоритмы [37]. Другой подход к переборным методам решения 1.5DBP и 2DBP разработан в середине 80-х гг. А.И. Липовецким [19]. На основе понятия «зоны» доказывается, что для любой упаковки прямоугольников можно указать такой их порядок, при котором каждый следующий прямоугольник не пересекается ни с одной из зон предыдущих (топологическая сортировка). Метод зон реализован в 1988 г., усовершенствован и исследован в 2001 г. В.В.Бухваловой (С.Петербург) [4]. Несколько точных алгоритмов, базирующихся на МВВ предложено S.Martello & D.Vigo [78].
Несмотря на многообразие различных подходов к созданию точных алгоритмов, размерность решаемых задач двумерного раскроя редко превосходит т=20. Это связано с тем, что пока не найдено способа определения эффективной нижней границы и для доказательства оптимальности приходится перебирать все возможные варианты. Новые нижние границы и их связь с методом «ветвей и границ» установлены P.Schwerin & G.Waescher [86]. M.Boschetti в 2002 г, предложил несколько новых методик подсчета нижней границы [46].
Обзор эвристических методов для решения задач прямоугольной упаковки предстанлен в статьях A.Lodi, S.Martello & D.Vigo в 2002г. [72], [73]. Там приведены известные детерминированные эвристики: следующий по убыванию длины (NFDL); первый по убыванию подходящей длины (FFDL); лучший подходящий по убыванию длины (BFDL).
При этом алгоритмы используют стратегию, когда каждый новый элемент упаковывается с выравниванием по левому и нижнему краю. E.Coffrnan and all [50] проанализировали стратегии NFDL и FFDL для решения двухмерной поуровневой упаковки полосы и определили асимптотическое поведение в «худшем» случае.
F. Chung and all исследовали так называемые двухфазные алгоритмы для решения задачи 2DBP. В первой фазе производится упаковка полосы по стратегии FFDL. Решение проблемы упаковки в ограниченный по длине контейнер достигается на второй фазе одномерной эвристикой. Двухфазный алгоритм, называемый гибридный первый подходящий (HFF), был предложен F.Chung, M.Garry, D.Johnson [49].
Лучшие результаты достигнуты в безуровневых алгоритмах. Самая распространенная безуровневая стратегия известна под названием нижний-левый (Bottom Left, BL) и состоит в упаковке элемента в самую нижнюю позицию, выравнивая по левому краю, В. Baker, J.CofTman, R-Rivest [42] в 1980 г. проанализировали алгоритм для наихудшего случая и доказали что при упорядочивании элементов по невозрастанию ширины в худшем случае ВЦ1)=ЗЮРТ(1). A.Lodi, S.Martello, D.Vigo предложили другой безуровневый подход,названный «переменные направления» (Alternate Directions, AD) ("73].
Алгоритм укладывает прямоугольники по порядку, как это делается в уровневых алгоритмах, но без выравнивания по левому краю и чередуя направления укладки,
H.Keller & VH Kotov [69] предложили новый приближенный алгоритм для задачи 2DBP с асимптотическим выполнением, который гарантирует отношение 2 наихудшего случая к оптимальному. Было замечено, что поведение приближенных алгоритмов в «среднем» значительно отличается от полученных оценок. Анализ «среднего» поведения таких алгоритмов приближает к их практическому использованию, Э.Х. Гимади, В.В. Залюбовским предложен асимптотически точный подход для решения 1DBP [8]. На этой основе ими разработан приближенный алгоритм со случайными весами предметов. Получены оценки относительной погрешности и вероятности несрабатывания алгоритма. Асимптотический подход пролонгирован авторами на задачи 1.5DBP [9].
Среди эвристик более высокого уровня выделяются жадные алгоритмы. С их помощью достигаются верхние границы. Стратегия «жадности» использовалась Г.В. Аккуратовым, В.А. Березневым и О.А. Брежневой [1]. Аналогичная стратегия применяется А.Ф, Валеевой при разработке метода динамического перебора DS [24]. Многие эвристики включают послойную стратегию, начало которой заложено в работах М. Adamowich & A, Albano [40]. Послойный подход использовался Э.А. Мухачевой для решения задач гильотинного раскроя [28]. Графовый метод и/или для решения 2D и 1.5DBP развивается в работах R.Morabilo & М. Arenales [79], [80].
Модель прямоугольной упаковки и условия допустимости
Рассматривается задачи раскроя двумерного ресурса на іірямоуїшьники нескольких типов. Ршяшшотся задачи раскроя полу бесконечной полосы (JL5BRP) и задачу раекрш листов (2DBP). Также рассматриваются задачи ГИЛЬОТИННОГО раскрой л исто» (21 С$) и пояубескопстюи полосы (1.51 СЗ). Под гильотинным понимается раскрой реализуемый последовательностью сквозных резов, параллельных кромкам материала (рис. 3).
Примеры прямоугольного двумерного раскроя: а - гильотинный раскрой; 6 - пегилштипнъш раскрой
Введем прямоугольную систему координат; оси Ох и Оу совпадают соответственно с нижнем неограниченной и боковой сторонами полосы (или листа). Положение каждого прямоугольника Pt зададим координатами (хТ9уІ) его левого нижнего угла.
Исходная информация задач прямоугольного раскроя и упаковки может быть представлена следующим набором данных: W; L; m; w; 1; b; % e , где (1) W - ширина полубесконечной полосы или листа: L - длина листа, для полубесконечной полосы L = со; т - количество типов прямоугольников; w = (wi, .„ м. т), wi- ширина прямоугольника типа і = 1,то ; 1 = (1, „, ,1,,-.Лі) її -длина прямоугольника типа z - l,m; b = (b[, ..,,b„...,bm), b,- количество прямоугольников типа / = 1 да; ГЦ n = Y\tbi - общее количество прямоугольников; у- признак гильотинности; 7 U если раскрой гильотинный; у= 0 в противном случае; е - признак направления детали в полосе (листе); е = 1, если детали можно поворачивать на 90; е = 0 в противном случае.
Решения рассматриваемых задач могут быть представлены в виде следующего набора данных: К_= Х,У,8,А ,где (2) X = (хь -, х„ ,.., хп), X; и yi - координаты прямоугольника і по осям ОХ и OY, / = 1,л ; i = (si, --, Si? sn), где Si - номер листа, в который упакован прямоугольник в случае раскроя полубесконечной полосы 5=0; А = (ах, ...,аь,.мап), ai 1, если прямоугольник і повернут на90 О, иначе Набор R = Х, Y, S, А называется допустимым прямоугольным раскроем, если выполняются следующие условия: 1 ребра предметов параллельны ребрам полосы или листа ((( =/.)л(/ =w.))v((i = w.)A(i -I.)), i = l,mt гдеі„ їу-проекции заготовки і на XI у І XI у І оси координат ОХ и OY. Т Взаимное непересечение деталей \?i j:ij=\4...,n для раскроя полубесконечной полосы: (xt xt+Ij)v (Xj xt + 1/) или (y\ y/+wJ)v(yj yf +мд); для раскроя листов: v t j і J J J і і J j J і і У Непересечение деталей с гранями полосы для раскроя полубесконечной полосы: Vi = 1,...,л :(х. 0)л(у. 0)л(у + w. W)\ і І і і для раскроя листов: V/ = Ц...,н :(х. 0)л( \ 0)л( , + w. і)л(х. +/. 1)
Набор R = Х, Ys S, A называется гильотинным прямоугольным раскроем, если выполняются условия 1 % 2 и 3, а также: 4 Условие гилъотинности
Для любого прямоугольника Р с размерами (w,l): w wt- v I = /„ / = 1,и (ограничивающего более 1 заготовки), должно выполняться условие разделения на два прямоугольника P (w , Г) и P"(\v", Г )\ (w = w"= w) А(Г+Г= l)v (w +w"= w) А(Р= Г= I): УУ = ГЛ если івР\ то / / , и если ieP",TO J?PT,
Примечание , условия 1\ 2\ V и 4 приведены для случая at = 0, / = 1,....,«. Если йі — 1, следует заменить w,- на iv/ — Л; и А, на А/ - vv ;. Задача 1.5DBP. Прямоугольный раскрой иолубесконечнои полосы. Дано: Задача раскроя W; L; т; w; I; Ъ; у; е , L - со, у = 0; Найти: Допустимый раскрой R = Х3 Y, S, Л , удовлетворяющий условиям 1 \ 2 и 3, для которого длина занятой части полосы Л — rnaxtXj + /,-) достигает минимума. Задача 2DBP. Прямоугольный раскрой листов. Дано: Задача раскроя W; L; т; w; I; b; у; с , у = 0; Найти: Допустимый раскрой R = Х, Y, S, А , удовлетворяющий условиям Г, 23 и 3 , для которого количество израсходованных листов nid.x A.j достигает минимума.
Алгоритм поиска с запретами с переменными окрестностями и вторичными оценками для решения задач двумерного прямоугольного раскроя
В данной работе представлен алгоритм поиска с запретами для задач двумерного прямоугольного раскроя. Алгоритм построен в соответствии с общей схемой метаэврестической техники поиска с запретами. Данный метод был реализован па ЭВМ в составе автоматизированной системы проектирования карг раскроя CETAMI-CUT и показал хорошие результаты на широком диапазоне классов задач прямоугольного раскроя, с использованием различных декодеров. Рассмотрим основные особенности реализации этого алгоритма. Введем следующие обозначения: п — количество прямоугольников; Р - приоритетный список; к - номер текущей итерации; Pk(i) - позиция прямоугольника і в приоритетном списке на шаге к; Рк [х] - элемент приоритетного списка в позиции х на шаге к;
Для представления решения используется приоритетный список Р длины п, состоящий из порядковых номеров прямоугольников. При этом, если прямоугольник і с; [1,п] повернут на 90, его номер в списке Р будет отрицательным (-І).
Получение карты раскроя из приоритетного списка осуществляется с использованием различных процедур декодеров, в том числе и разработанного в данной работе декодера CD.
На каждом шаге строится окрестность текущего решения - множество решений, получаемых из текущего путем проведения какого-либо простого преобразования. Затем в этой окрестности выбирается лучшая точка и принимается в качестве нового текущего решения. В алгоритме реализовано три простых метода построения окрестности, и они могут чередоваться с заданными вероятностями (см. таблицу 1).
Как видно из таблицы 1, в алгоритме используются две окрестности размера 0(п2). При большом количестве прямоугольников (п = 50) построение п2 упаковок может отнимать слишком много времени. Для того чтобы избежать этого, в алшритме поиска с запретами реализован случайный выбор заданного количества точек из окрестности. Как показывает практика, при большом п случайный выбор сравнительно небольшого количества точек в окрестности не приводит к ухудшению результатов, но позволяет существенно улучшить временные показатели алгоритма.
В качестве оценочной функции используется коэффициент раскроя (КРА) - отношение суммарной площади заготовок к площади израсходованного материала: КРА = V(w. /.) / (max(x. +/-) //). В случае раскроя листового материала (N - количество израсходованных листов): s_ KPA= Y(w /)/(А Л) где Л =L (N-1)+ max ( + /.) V
К сожалению, использование для оценки решения только коэффициента раскроя часто приводит к не самым лучшим результатам. Это связано с тем, что, при рассмотренных методах построения окрестности, в окрестности решения существует, как правило, множество решений, КРА которых равен КРА текущего решения
Как видно из графика, по завершении процесса локального спуска алгоритм поиска попадает на «плато», на котором большинство решений имеют одинаковую оценку. При этом количество различных решений с одинаковыми оценками слишком велико, чтобы можно было избежать данной ситуации с использованием списков запретов.
Для разрешения этой проблемы в данной работе предложено использовать дополнительные, вторичные оценочные функции, значение которых определяется структурой карты раскроя. Использование такой функции позволяет ранжировать различные решения с одинаковым КРА и избегать таким образом длительного «простоя» алгоритма на «плато». Кроме того, варьирование вторичных функций позволяет осуществлять качественную диверсификацию поиска в текущей области- В данной работе предложены две вторичные функции, представленные в таблице 2. В приведенном примере их использование позволило уменьшить полученный остаток более чем в два раза: от 5.5% до 2,2%.
Для управления поиском в представленном алгоритме используются два списка запретов. Локальный список запретов содержит сведения о последних шагах поиска и служит для предотвращения зацикливания. В него на каждом шаге заносится преобразование, обратное произведенному на этом шаге, и остается запрещенным в течение LOC шагов, где L0C - максимальная длина локального списка запретов. Впрочем, преобразования, находящиеся в локальном списке запретов, тем не менее могут быть выполнены, если значение основной оценочной функции (КРА) в результате их использования окажется меньше, чем для лучшего из ранее полученных решений. Это условие является условием преодоления запрета.
В глобальный список запретов заносятся сведения о первых шагах поиска после достижения лучшего решения в данной области. Он используется для интенсификации поиска. Условие преодоления запрета, рассмотренное выше, распространяется и на преобразования, включенные в глобальный список запретов.
Максимальные размеры локального и глобального списков запретов зависят от количества прямоугольников и определяются на этапе инициализации алгоритма.
В качестве условия прекращения поиска используется ограничение по времени, как наиболее практичное и удобное для проведения вычислительных экспериментов и решения производственных задач. Кроме того, процесс поиска завершается досрочно, если достигнута тривиальная нижняя граница (то есть если КРА = 100%, безотходный раскрой). Как уже было сказано, процедура диверсификации поиска должна обеспечивать выход за границы области вокруг локального оптимума для расширения поиска и обеспечения ассимптотической сходимости алгоритма.
Эксперимент на случайно сгенерированных примерах
Экономия материалов представляет собой сложную комплексную проблему. Одним из путей и средством решения этой проблемы является рациональный раскрой материалов, В большинстве отраслей промышленности и строительства приходится встречаться с раскроем материала. Металл, дерево, фанера, стекло и другие промышленные материалы поступают на производство в виде целых единиц: листы, профильный прокат, полосы. При использовании их приходится раскраивать на части нужных размеров и форм. При этом, как правило, оказывается невозможным полное использование материала, и некоторая часть его идет в отходы, которые обычно не находят применении, поэтому необходимо максимально уменьшать отходы.
Программа-оболочка системы CHTAM1-CUT отвечает за интерфейс и работу с базой данных. В программном коде расчетных модулей реализована расчетная часть системы, каждый из которых является программной реализацией определенного алгоритма решения задачи двумерного прямоугольного раскроя.
Функциональные возможности программы-оболочки CETAMI-CUT: — выбор метода решения; — ввод данных задания; — использование функций расчетных модулей для решения задачи; — графическое представление результата на экране в виде карт раскроя. Предоставляются стандартные возможности масштабирования, прокрутки, получения справочной информации, отображение последовательности резов для полученного раскроя, а также дополнительной информации; — вывод на печать, В программу-оболочку встроен менеджер печати, позволяющий настроить печать карт раскроя с интерактивным предварительным просмотром; — многодокументный интерфейс; — возможность автоматизированного выбора подходящего метода на основе накопленной статистики, настройка параметров выбора; — генерация случайных заданий для пополнения статистики, при решении любой задачи ее параметры и результат сохраняются в базе знаний; — настройка структуры дополнительных параметров; — работа с базой данных нестандартных листов, добавление в базу полезных остатков, получаемых при раскрое, для последующего использования; — автоматическое подключение новых алгоритмов и настройка их опций; — проведение и анализ численного эксперимента; — поддержка выбора языка интерфейса пользователя; — процедура автоматизированного выбора метода раскроя на основе исходных данных.
Нарис. 11 представлена архитектура системы CETAM1-CUT. Программа оболочка состоит из пяти основных модулей:
Каждый расчетный модуль состоит из четырех основных элементов:
— модуль проверки корректности входных данных служит для отсева некорректных входных данных и для определения возможности решения задачи методом (например, точный алгоритм не может решать задачи из 100 деталей);
— модуль подготовки входных данных производит инициализацию структур данных вычислительной части алгоритма;
— вычислительный модуль выполняет все необходимые операции для получения решения задачи, в процессе решения модулю интерфейса системы передается информация о проценте выполнения задачи;
— модуль подготовки выходных данных производит освобождение памяти от данных вычислительной части алгоритма и формирование результата.
Система CETAMI-CUT позволяет проводить сравнительное тестирование эффективности подключенных модулей. Это позволяет выделить наилучший метод решения для класса задач, для которого проводится сравнительное тестирование. При решении каждой задачи результат заносится в базу данных, которая используется процедурой автоматизированного выбора метода решения на основе входных данных задачи.
В системе CETAMI-CUT реализована процедура автоматизированного выбора метода решения на основе входных данных задачи раскроя. Реализован сбор статистики для решаемых задач, что позволяет улучшать качество выбора метода решения на этапе эксплуатации. Оператору автоматизированного рабочего места не обязательно знать характерные особенности алгоритмов системы, из-за которых только специалист может правильно выбрать метод, наиболее эффективный при решении конкретной задачи.
Представленный в данной рабтое алгоритм поиска с запретами был реализован на ЭВМ и интегрирован в систему двумерного прямоугольного раскроя CETAMI-CUT в качестве подключаемого расчетного модуля. С использованием средств системы был проведен объемный вычислительный эксперимент с участием всех включенных в нее методов. В качестве декодеров для алгоритма поиска с запретами использовались декодеры, представленные в главе 2 данной работы.
Реализация метода поиска с запретами в рамках системы позволяет решать все рассмотренные в данной работе виды задач. При этом для решения задач гильотинного раскроя листов и рулона (полубесконечной полосы) в составе метода поиска с запретами используются декодеры рекурсивный и поиска пустых корзин, а для решения задач негильотинного раскроя - декодеры блочный, последовательного конструирования и «нижний левый».
