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

ООЗОб1376

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

ФИЛИППОВА Анна Сергеевна

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

Специальность: 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Уфа 2006

003061976

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

Научный консультант: д-р физ.-мат. наук, проф.

Житников Владимир Павлович

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

Кораблин Михаил Александрович

заслуж деятель науки и техники РФ, д-р техн. наук, проф., Норенков Игорь Петрович

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

Фроловский Владимир Дмитриевич

Ведущая организация ГОУ ВПО «Петрозаводский государственный

Университет»

Защита состоится 27 апреля 2007 года в 10 часов на заседании диссертационного совета Д-212.215.05 при ГОУ ВПО «Самарский государственный аэрокосмический университет имени академика С.П. Королева» по адресу 443086, г. Самара, Московское шоссе, 34, к. 209 (конференц-зал СГАУ)

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Самарский государственный аэрокосмический университет имени академика С.П Королева».

Автореферат разослан «_

2007 г.

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

Калентьев А.А.

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

Актуальность проблемы. Исследование технологических процессов в различных отраслях промышленности показывает, что многие из этапов заготовительного производства связаны с раскроем и размещением деталей. Эти процессы являются очень важными с точки зрения экономии ресурсов и сложными для принятия решений. Возникают оптимизационные задачи раскроя и упаковки в процессе планирования и заказа материалов, а также на этапе оперативного проектирования карт раскроя и упаковки. Принятие оптимального или близкого к нему решения позволяет существенно сократить расход материала и понизить себестоимость продукции. В условиях глобальной автоматизации промышленных процессов давно появилась необходимость в создании и использовании систем автоматизации проектирования подготовки раскроя и упаковки. К серьезным компьютерным продуктам, разработанным в России в этом направлении, можно отнести САПР «СИРИУС» (Екатеринбург) и «ТЕХТРАН-РАСКРОЙ» (С.-Петербург). Первая базируется на работах P.A. Вайсбурда и А А Петунина, вторая - на методах сквозного проектирования, развитых В.Д. Фроловским. Применение классических методов раскроя осуществлено В.А. Ворониным и В.А. Кузнецовым в лесоперерабатывающих комплексах Карелии. Больших успехов добиваются за рубежом. Общим недостатком всех систем является слабая степень оптимизации раскроя и упаковки. В хорошее сервисное окружение оказываются зашитыми неэффективные методы расчета.

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

А. Бортфельда (A. Bortfeld), И. Фолкнера (Е. Folkenauer), Е. Хоппер (Е. Hopper), С. Имахори (S. Imahori), С. Мартелло (S. Martello), Г. Шайтхауера (G. Sheithauer), П. Ванг (P. Wang), Г. Вешера (G. Wascher) и другие. Следует отметить, что методы, разработанные для ортогональной упаковки с успехом применяются и для задач нестинга. Ввиду NP-трудности рассматриваемых задач, применение точных методов приводит к непреодолимым препятствиям, в связи с высокой размерностью решаемых задач.

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

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

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

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

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

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

3. Разработать способ определения окрестности локально-оптимального решения и алгоритм поиска этого решения.

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

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

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

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

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

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

На защиту выносятся следующие результаты:

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

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

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

4. Эволюционные алгоритмы решения задач ортогональной упаковки: блочные модификации классического генетического алгоритма и эволюционного алгоритма (1+1)-ЕА с локальной нижней границей; разработка генетического блочного алгоритма; алгоритмы с синтезом простых декодеров конструирования упаковок, допускающих учет технологических параметров

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

Рис. 1 - Основные функциональные элементы блочной технологии

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

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

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

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

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

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

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

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

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

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

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

учетом ограничений, возникающих в производственных системах. Для использования блочной технологии удобны метаэвристики, в составе которых применяются инвариантные к производству процедуры. Производственный фон включается только в процедуры конструирования упаковок, т.е. в декодеры. Такое включение может быть реализовано простыми приемами пользователя. Предлагаемый комплекс алгоритмов и программ отличается от аналогов малыми временными затратами для расчета ресурсосберегающих упаковок за счет применения высокоэффективных эволюционных алгоритмов с быстродействующими блочными декодерами. Это подтверждено использованием блочных технологий в процессе размещения контейнеров (ящиков) на складах и транспортных средствах, ЗАО «Новое время», г. Уфа; технологической подготовки производства металлоконструкций, ОАО «Буммаш», г. Ижевск; в подготовке производства целлюлозно-бумажной промышленности, г. Петрозаводск. Программное обеспечение интегрировано в промышленную систему Техтран-Раскрой, г. С.Петербург и автоматизированную систему проектирования прямоугольного раскроя, СЕТАМ1-ШТ, г. Уфа. Программы официально зарегистрированы, свидетельства № 2004611452, №2006612649 Результаты работы используются в учебном процессе Уфимского государственного технического университета, Уральского государственного технического университета - УПИ и Башкирского государственного университета.

Связь исследований с научными проектами. Работа выполнялась при поддержке Российского Фонда Фундаментальных Исследований, проекты 9901-00937, 01-01-00510, 02-01-06331, 03-01-07002; фонда Президента РФ поддержки молодых кандидатов наук, проект МК 145.2003.01; программы Мин. Образования РФ «Научные исследования высшей школы в области производственных технологий» (2001), раздел технологии современных заготовительных производств.

Апробация работы. Основные научные и практические результаты диссертации докладывались и обсуждались на Международных и Российских научных конференциях, в том числе: Сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-98) г.Новосибирск, 1998; Международной Сибирской конференции «Дискретный анализ и исследование операций», ИМ СО РАН, г.Новосибирск, 1998, 2000, 2002, 2004; 16-ой Европейской конференции по исследованию операций, г.Брюссель, Бельгия, 1998 ; Международной конференции 1Р0115-2000, г. Сан-Антонио, США, 2000; Международной конференции 1РОЯ5 2002, Эдинбург, Англия 2002; «Европейский научный семинар ЕБЮНР», Виттенберг, Германия, 2004; Международные конференции «Математическое программирование и приложения», ИММ УРО РАН г. Екатеринбург, 1999, 2001, 2003, 2004, 2007; Международная научная конференция «Моделирование, вычисление, проектирование в условиях неопределенности», УГАТУ, Уфа, 2000, Байкальская международная школа-семинар «Математическое программирование», г. Иркутск 2002, 2005; Всероссийская научно-практическая конференция «Ресурсосберегающие технологии», Санкт-Петербург, 2001; Международная конференция «Математика и экономика старые проблемы и новые подходы», памяти Л В. Канторовича, С-Петербург,

2004; Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, 2003, 2006, Международная конференция CSIT, УГАТУ, Уфа, 2002, 2004, 2005; Международная Уфимская зимняя школа-конференция по математике и физике, БГУ, Уфа, 2005; на семинарах Института Вычислительной математики Дрезденского технического университета, Дрезден, 2002, семинарах кафедр «Вычислительной математики и кибернетики» и «Компьютерной математики» УГАТУ.

Публикации. По теме диссертации опубликовано более 80 работ. Основные результаты представлены в работах [1-40]. В число указанных публикаций входят 22 статьи из «перечня ВАК ведущих научных журналов и изданий, в которых должны быть опубликованы основные научные результаты на соискание ученой степени доктора наук» В совместных работах с проф Э.А. Мухачевой, доц. А.Ф. Валеевой, доц. В.М Картаком и аспирантами УГАТУ A.B. Чиглинцевым, P.P. Ширгазиным принадлежат автору диссертации следующие разделы: идеи и подходы к созданию технологии блочных структур; блочные методы кодирования и декодирования упаковок; необходимые и достаточные условия соответствия блок-структур и упаковок; аппроксимация прямоугольной упаковки парой ослабленных задач прямоугольно ориентированного линейного раскроя; способ «замещения» в блочных алгоритмах конструирования упаковки; алгоритмы «двойныхх списков» и генетического блочного алгоритма с новой идентификацией элементов генетики, проведение и анализ результатов численного эксперимента Э.А. Мухачевой принадлежат идеи разделения упаковки на прямоугольные блоки и ситуации «перестройки», возникающей в ходе конструирования упаковок. A.B. Чиглинцеву принадлежат разработки блочных декодеров с использованием стратегий нижний-левый и свойство «реставрации» некоторых декодеров. В М. Картак ввел условие неперекрытия прямоугольников для пары блок-структурЧ

Структура и объем работы. Диссертация состоит из введения, шести глав основного материала, заключения, библиографического списка и приложений; содержит 325 страниц основного текста. Библиографический список включает 212 наименований литературы.

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

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

Глава 1 посвящена аналитическому обзору работ в области моделей и методов раскроя-упаковки. Вначале приведены фундаментальные работы Л.В. Канторовича и В А. Залгаллера, которые появились в эпоху открытия Л.В. Канторовичем линейного программирования и развития прикладных ас-

"'ВМ Картак Решение задачи упаковки прямоугольников в полубесконечную полосу // Уфа БГУ Региональная школа-конференция молодых ученых по математике и физике 2001 С 110-121

пектов методов оптимизации. За рубежом аналогичные результаты были получены П. Гилмори (P. Gilmore), Р. Гомори (R. Gomory) и И. Терно (I. Теттю), Г. Шайтхауером (G. Scheithauer). Эти методы оказались приемлемыми для решения задач планирования раскроя в массовом производстве. В условиях единичного и мелкосерийного производства применение непрерывных моделей малопригодно. Известно, что простейшая задача одномерной упаковки является NP-трудной проблемой и точных методов полиномиальной сложности для ее решения не найдено. Качественная типология в области раскроя-упаковки (Cutting&Packing, С&Р) проводилась в 1990 г. германским ученым X. Дикхоффом Она принята в мировой практике и используется при исследовании моделей С&Р и методов их решения. Рассматривается класс задач ортогонального раскроя и упаковки, в которых элементы имеют только прямые углы и могут быть вырезанными параллельно кромкам материала. Различаются гильотинный и негильотинный способы разделения объекта на части. Гильотинный раскрой реализуется только сквозными резами.

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

Задача упаковки прямоугольников в полосу (2 Dimensional Strip Packing Problem, 2DSP). Один из размеров полосы, например ширина W задан, второй - длина является переменным. Требуется найти упаковку в полосу минимальной длины L.

Задача упаковки прямоугольников в контейнеры (2 Dimensional Bin Packing Problem, 2DBP) Оба размера W и L заданы. Требуется найти минимальное количество N контейнеров, в которые упакованы все предметы.

Задача упаковки прямоугольников в открытую область (квадрант) (2 Dimensional Area Packing, 2DAP). Оба размера, ширина W и длина L являются для объекта переменными. Требуется найти упаковку элементов в угол, образованный осями координат, совпадающими с гранями области, для которой площадь огибающего упаковку прямоугольника достигает минимума.

Входная информация для выделенных задач задается набором данных (fV, L, т, w, I, е ), в котором W, L - ширина и длина прямоугольного объекта; в задаче 2DSP длина Ь= <*>; в задаче 2DAP - W-°о и L=со; т - количество прямоугольных элементов; w~(w!t w?,..., w„.., w„) - вектор ширин элементов; l-(h. h.—, h—, L,)~ вектор длин элементов; е - признак возможности изменения ориентации прямоугольников.

Введем прямоугольную систему координат: ось ОХ совпадает с горизонтальной гранью объекта, а ось OY - с вертикальной. Решения рассматриваемых задач могут быть представлены в виде набора (W, L, m,w,l,X,Y,S,E), где X={x¡, х2,~ .*„... *„,), У=(у\, уг-У„ ..., Ут) - векторы минимальных координат прямоугольников; S^i, s2,— s„,. .,.sm) - номера заполненных объектов (s, -номер контейнера. в который упакован i'-й прямоугольник); Е=(еi, ег,....е„ ... е,„), е,=Т, если элемент / повернут на 90°, иначе е,~0.

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

• ортогональное размещение прямоугольников в упаковке'

для (х[ ,yt ), i= \,т и любой другой вершины [rf,у\ j /-го прямоугольника ((xf = х, ) v (xf = х, + /, )) л (Ск* = у,-) V Си* = Л + w, ));

• неперекрытие прямоугольников: для /* у; г, у =

((х, >Xj+lj)v (Xj >х, + If)) v ((у, > у j + Wj ) v ));

• неперекрытие прямоугольников гранями объектов: для всех i-\rn

Далее основное внимание будет уделено задаче 2DSP, в которой при исходных данных (W, m,w,l ) требуется минимизировать

L(x;y) = max (х, + /,) i-\,m

на множестве допустимых векторов x=(x\,...,x„y,y=(yt,.. ,ут)-

Применение методов линейного и целочисленного программирования. Непрерывная релаксация задачи 2DSP состоит в получении оптимума в соответствующей задаче линейного программирования. Полученный непрерывный оптимум используется для построения целочисленного решения. С этой целью после округления снизу непрерывного решения формируется малая остаточная задача. Последняя решается с помощью эвристик до достижения нижней границы или процесс останавливается на лучшем из полученных решений. В 1985 г. О. Map копе (О. Marcotte) сформулировал важные свойства целочисленного оптимального решения для задачи линейного раскроя. На основе этих свойств построены схемы точного решения. Продолжают развиваться точные алгоритмы на базе линейного целочисленного программирования. Приближение непрерывной релаксации к целочисленному оптимуму реализовали Г. Шайтхауэр и Г. Белов (Германия) в 1999 г.

Применение методов комбинаторной оптимизации. Задачи упаковки являются классическими представителями NP-трудных проблем, и для их решения применяются методы полного перебора с отсечением неперспективных вариантов. И.В. Романовский и Н.П. Христова предложили для решения дискретных минимаксных задач метод дихотомии. Другой подход к переборным методам решения 2DSP и 2DBP разработан А.И. Липовецким. На основе понятия «зоны» доказывается, что для любой упаковки прямоугольников можно указать такой их порядок, при котором каждый следующий прямоугольник не пересекается ни с одной из зон предыдущих. Метод зон усовершенствован и исследован В.В. Бухваловой.

Приближенные и эвристические методы. При изучении задач С&Р особая роль отводится обобщенной проблеме загрузки рюкзака, описанной С. Мартелло (S. Martello) и П. Тот (P. Toth) в 1990 г. Большое внимание уделяется проблеме поиска сумм подмножеств (Subset Sum, SS), которую также называют независимой оценкой задачи рюкзака. Примером является использование SS А.Ф. Валеевой в составе алгоритмов динамического перебора для ре-

шения различных задач упаковки. Э.Х. Гимади и В.В. Залюбовским предложен асимптотически точный подход для решения 1DBP и 2DSP. Получены оценки относительной погрешности и вероятности несрабатывания приближенного алгоритма. Эвристические алгоритмы для решения двухмерных задач прямоугольной упаковки можно разделить на две основные группы: конструктивные эвристики и вероятностные методы локального поиска оптимума. Однопроходные (конструктивные) эвристики используются для конструирования упаковки по ее коду и применяются в качестве декодеров в процессе локального поиска. Широкое распространение на западе получил декодер нижний-левый (Botton Left, BL). Многие эвристики включают послойную стратегию, начало которой заложено в работах М. Адамович (М. Adamowich) и А. Альбано (A. Albano). Послойный подход использовался Э.А. Мухачевой для решения задач гильотинного раскроя. Графовый метод и/или для решения 2DSP развивается в работах Р. Морабито (R. Morabito) и М. Ареналиса (М. Arenales)

Вероятностные методы локального поиска оптимума. Бурное развитие вероятностных методов локального поиска оптимума началось 30 лет назад с появлением метаэвристик для решения NP-трудных задач. В России обзор вероятностных методов локального поиска оптимума для NP-трудных задач сделан в 2001 г. Ю.А. Кочетовым. В обзоре обсуждаются общие схемы алгоритмов поиска с запретами, имитации отжига и генетических алгоритмов. Показано, что эти алгоритмы используют общую математическую конструкцию конечных цепей Маркова. Это гарантирует сходимость по вероятности к оптимальному решению задачи.

Основные технологии конструирования ортогональных упаковок. Обзор эвристических методов для решения задач прямоугольной упаковки представлен в статьях А. Лоди (A. Lodi), С. Мартелло и Д. Виго (D. Vigo). В них приведены известные детерминированные эвристики. Большое разнообразие среди них привело к необходимости объединения в классы по способам конструирования упаковок. Таким образом, появились уровневая и безуровне-вая технологии разработки декодеров. Уровневые алгоритмы используют прием, когда каждый новый элемент упаковывается с выравниванием по левому и нижнему краю. Через правую сторону прямоугольника максимальной длины проводят вертикальную линию. Полубесконечная полоса оказывается разделенной на уровни прямоугольной формы, содержащие целиком все покрывающие их прямоугольники

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

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

2. Определение нижних границ для оценки получаемых решений.

3. Разработка средств повышения эффективности декодеров.

4 Методики формирования соседних решений и построения окрестностей для поиска локальных оптимумов.

5. Разработка конструктивных эвристик.

7. Создание новых методик исследования эффективности алгоритмов.

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

9. Применение технологий параллельного программирования.

В диссертации представлены разработки в направлениях 1, 2, 3 и 4. Глава 2 представляет теоретическую основу технологии блочных структур Она представляет базовые способы моделирования методов решения задач ортогональной упаковки с кодированием в виде блок-структур и оценкой качества полученных решений..

Пара блок-структур как способ кодирования прямоугольной упаковки. Пусть имеется прямоугольная упаковка ЯР. Проведем мысленно через правые стороны прямоугольников вертикальные резы. Они разделяют КР на прямоугольные вертикальные блоки одной и той же ширины Ж и различной длины X] • Пусть длина ИР равна Ь. Проведем через верхние стороны прямоугольников горизонтальные линии. Тогда ЯР разобьется на горизонтальные блоки одной и той же длины I. и различной ширины г) ^. Так мы получаем две

блок-структуры для ИР, вертикальную и горизонтальную, см. рис 2.

Каждому блоку у соответствует запись (), в которой перечислены

номера прямоугольников, пересекающих этот блок по направлению снизу-вверх в вертикальном случае (слева-направо в горизонтальном). Для каждого вертикального блока у указана его длина Х/ > Для горизонтального - ширина

Г1!. Упаковке, изображенной на рис. 2 соответствуют блок-структуры.

5: ((1,3,6)^1; (1,7,6)^2; (1,6)^; (2,4,6)^; (2,5)^), 5 : ((1,2)7,; (1,4,5)772; (3,4,5)%; (3,7,4,5)т74; (3,7,5)т75; (6,5)т76; ).

w

Р6!

РЗ

Р1

Р4

Р2

Р5

Р6 wMy<

-ТР7ГЙ-:'Л- -----

РЗ |;ЧЧ-'

Р4 Р5

PI

Р2

Чз 17 2

V,

% j X ■уХ X ^ X $ ^

а б

Рис. 2- Блок-структуры упаковки-а - разделение упаковки на вертикальные блоки; б - разделение упаковки на горизонтальные блоки

Блок-структуру, заданную списком S, назовем вертикальной (Upright Block Structure, UBS); блок-структуру, заданную списком S - горизонтальной

(Horizontal Block Structure, HBS). Показателями пригодности упаковки явля-

г -Я

юте я длина Xj из UBS (ширина L = £ Л j из HBS). В задаче 2DSP

;= 1 У=1

I => min ; L<W. UBS и HBS представляют двойные блок-структуры (Double Structure, DBS).

Сформулируем основные условия соответствия пары блок-структур и допустимой упаковки.

Обозначим: Ij(Ij) ~ множество прямоугольников, пересекающиху'-ый

вертикальный (горизонтальный) блок; ij(I^) - множество прямоугольников,

заканчивающихся в j-ом вертикальном (горизонтальном) блоке; 1~(1J) -

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

Теорема 1. Пара блок-структур, заданная списками (S, S ) соответствует допустимой упаковке RP с исходной информацией (W; m; w; !) в том и только в том случае, если выполнены следующие условия:

1°. Разнородность прямоугольников в каждом блоке. Элементы /(/') в каждом блоке j различные.

2°. Продолженностъ прямоугольников. Если некоторый элемент

/(у) g /; (Tj+ ), то z(y) е Ij(lj+1 ).

3°. Неперекрытие прямоугольников. Для любых вертикального и горизонтального блока выполняется одно из следующих условий:

(a) для любой пары ('ь'г) € любого блока : если i) е J j, то ij £ I}

или если ¿2 б 1 j, то i\ £ I j\

(b) для любой пары (jj,^) е/уи любого блока 11 ■ если ^ е , то iji ¡k или если ij е , то i\ г •

4°. Неперекрытие с границами полосы.

ÎXJ-L; X Vj =L<W, 7=1 /=1

где r(q) - количество вертикальных (горизонтальных) блоков.

5°. Линейная зависимость длины (ширины) прямоугольника от длин (ширин) пересекающих его блоков Если прямоугольник г е I~ ( i е IJ ) и + р ?

ielj+p(iel то /, = £ Zi+k\wi = Z Vj+k ■ i=0 /с=0

Связь между упаковкой (прямой схемой кодирования) и отвечающей ей DBS, заданной парой (S, S ), устанавливает следующее утверждение.

Лемма 1. Для любой упаковки RP и отвечающей ей пары (S, S ) существует взаимно-однозначное соответствие и координаты (х^у,), i-\,m прямоугольников в упаковке можно вычислить по следующим формулам' к-1 _ к-1

j=l j=i где Iк ) - множество прямоугольников, которые начинаются в вертикальном блоке к (в горизонтальном блоке к )

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

Определение 2. Упаковку назовем плотной, если все ее прямоугольники размещены плотно.

Связь между плотной упаковкой и отвечающей ей UBS устанавливает следующее утверждение.

Лемма 2. Существует взаимно-однозначное соответствие между плотной упаковкой RP и отвечающей ей UBS, заданной списком S и координаты (хп у,), i = \,m прямоугольников в упаковке вычисляются по следующим формулам:

ВД-1

= Z Xj ; У, =0+ max (yv + w„) (2)

где k(i) - номер вертикального блока, в котором начинается г-й прямоугольник; — множество прямоугольников, предшествующих прямоугольнику i в блоке k(i).

Теорема 2 (условия соответствия). Вертикальная блок-структура UBS, заданная списком S, соответствует допустимой упаковке RP с исходной информацией (W\ m,w,l) в том и только в том случае, если при выполнении свойств 1°, 2°, 4°, 5° справедливо следующее условие:

6°. Замещение. Если в некотором блокеj закончился один или несколько

прямоугольников, ielj , то новые прямоугольники iе7J+j должны разместиться без перекрытия с другими в освободившихся и пустых областях

Списки 5 и 5 представляют собой план линейного раскроя, запись каждого из блоков Sj(Sj) - раскрой одного стержня с указанием их количества Xj (л /) • Блок-структуры тесно связаны с решениями задач линейного раскроя.

Задача линейного раскроя (Cutting Stock Problem, 1DCS) Имеется материал, поступающий в виде стержней длины Z. Путем его раскроя требуется получить набор из т различных предметов заданной длины Лп i = 1, т, и в не-

обходимом количестве Д каждого вида i = 1,т. Требуется раскроить материал на линейные предметы (элементы) с минимальными затратами стержней

Задача 1DCS задается информационным вектором р ) ;

^m)' Р ~(А>•■■> Ая)■ Шаблон раскроя j может быть записан как (1(у),2(у'),...,г(у),.--)> в котором перечислены номера /(/') предметов, получаемых по способу j. План раскроя S материала представляет совокупность из п записей шаблонов с указанием интенсивности Xj применения каждого из них, т.е

£ Xj, 7=1

где 5 - список шаблонов, N — количество расходуемых стержней.

Задача прямоугольно-ориентированного линейного раскроя (.Rectangular Oriented CS, ROCS). При исходных данных 2DSP и Z=W; Á = w; /? = /, найти допустимое решение задачи 1DCS, удовлетворяющее условиям Io, 2°.

Допустимое решение задачи ROCS, назовем прямоугольно-ориентированным линейным раскроем (Rectangular Oriented Linear Cutting, ROLC), ему отвечает вертикальная блок-структура, заданная парой (S; TV).

Учет ограничения Io не представляет труда. Что касается 2°, то продол-женность элементов в соседних блоках удобно учитывать в рамках алгоритмов последовательного раскроя, когда шаблоны генерируются один за другим по мере их заполнения деталями из приоритетного списка л. Это - алгоритмы «следующий подходящий» (Next Fit, NF), «первый подходящий» (First Fit, FF), «лучший подходящий» (Best Fit, BF) и некоторые жадные алгоритмы.

Для построения и оценки решений в задаче 2DSP важно знать не только длину L упаковки, но и ее нижнюю границу А. В качестве оценки решения многие авторы принимают относительное отклонение длины L от нижней границы Л, называемое пробелом, gap - '' ^ 100%.

Локальная нижняя граница. Локальную границу можно получить путем решения задачи ROCS при (Z-fV;m;À = w,/} = l} методом следующий подходящий с перестановкой п, отвечающей решению L задачи 2DSP. Обоснование поиска локальной нижней границы для текущей RP базируется на свойствах представлений перестановками допустимых решений одномерной задачи упаковки \ Рассматриваются перестановка л, отвечающие ей ROLC и упаковка RP. Алгоритм, воспроизводящий упаковку (раскрой) согласно ее кода, принято называть декодером. В качестве стратегии декодеров воспроизведения 7Г =>ROLC и к => RP используем следующий подходящий (NF)

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

1 В В Залюбовский О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры/.'Труды XII! Байкальской международной школы-семинара Иркутск Том 1 2005 С 461-467

Назовем такие упаковки и отвечающие им перестановки ж и ж' эквивалентными. Пусть известна NF-активная одномерная упаковка PNf((A,/?),tt), полученная алгоритмом NF для множества предметов (À,J3) в порядке, заданном перестановкой ж.

Определение 3. Обмен позиций элементов в списке ж назовем пассивным, если применение NF к эквивалентному списку к' приведет к Pnf{(A,£0,я"'), эквивалентной исходной упаковке PNF ((Л,/?),тг).

Лемма 3. Пусть имеется блок-структура прямоугольной упаковки RP в полубесконечную полосу ширины W множества предметов (w,/) и ей отвечает ж). Тогда при любой ж', эквивалентной ж справедливо неравенство JV=|ROLC nf ((Я, 0),ж\< |RP((w, 1\ ж'} =L.

Следствием из этой леммы является следующее утверждение.

Теорема 3. Решение N =|ROLCi^f((A,^),^)| задачи ROCS с исходной информацией (Z = W\Л = w;0 = l), является локальной нижней границей А для любого решения L = |RP((w, l\ ж'^ задачи 2DSP, где ж' - перестановка, эквивалентная к.

Теорема 4. Оптимальное решение задачи ROCS с исходными данными, отвечающими RP, является глобальной границей для решения задачи 2DSP.

Определение 4. Множество перестановок {л}, отличающихся друг от друга только перестановками пассивных элементов, определяет ROLC-окрестиостъ прямоугольной упаковки RP.

Установленная связь между перестановкой ж и блок структурами ROLC и RP позволяет организовать поиск решения в ROLC-окрестности. При этом выполняется неравенство Z(RP,;r)> N(ROLC,;r)= Л, какие бы пассивные изменения в списке ж не произошли. Численные эксперименты подтверждают эффективность предложенного метода поиска локального оптимума.

В главе 3 представлены задачи одномерного раскроя-упаковки и основные методы их решения. Наряду с задачами одномерного раскроя, подробно описаны задачи прямоугольно-ориентированного раскроя и пригодные для ее решения алгоритмы. Особое внимание уделено методу последовательного уточнения оценок (Sequential Value Correction, SVC), идея которого связана с объективно-обусловленными оценками JI.B. Канторовича. Эта глава имеет важное вспомогательное значение. В начале главы описаны некоторые популярные методы решения задач одномерного раскроя и упаковки- релаксация линейным программированием; генетический алгоритм и метод последовательного уточнения оценок. Далее приведена модель задачи прямоугольно-ориентированного раскроя, ее особенности и методы решения. В заключение главы приведены результаты численных экспериментов и принцип разделения задач на классы по степени трудности достижения оптимума с помощью предлагаемых алгоритмов.

В главе 4 приведена общая характеристика известных безуровневых и уровневых декодеров нижний-левый (Bottom-Left, BL) и усовершенствован-

ный алгоритм «нижний-левый» (IBL), представляющих альтернативу блочной технологии и развитые в работах западных ученых. Вычислительная сложность этих алгоритмов О (от2). Уровневые алгоритмы представлены простыми стратегиями «следующий подходящий» (NF), «первый подходящий» (FF) и «лучший подходящий» (BF). Их вычислительная сложность соответственно равна <9 (от), 0(m\og(m)), 0(mlog(«)).Определено их асимптотическое поведение в худшем случае. Далее приведены разработанные в диссертации способы декодирования на основе блочных структур: «замещение», «двойных списков блок-структур» и «блочные».

Алгоритмы замещения (Substation, Sub). Рассматриваются одно- или малопроходные методы и алгоритмы конструирования прямоугольных упаковок. Исходной информацией являются (W, m,w,l) и перестановка 7Г = {[(ж),2(ж),...,1(ж),...,т(л)). По мере надобности задается признак возможности поворота детали в полосе. Однопроходные алгоритмы замещения базируются на общем способе «замещения» (теорема 2).

Замещение следующим подходящим (SubNF). Первый предмет из л упаковывается в полосу, занимая нижне-левую позицию, плотно прилегая к левой (опорной) грани полосы. Через правую сторону прямоугольника мысленно проводят вертикальную прямую. При этом выделяется блок, в который уже уложен прямоугольник №1. Каждый следующий предмет упаковывается полностью или частично в тот же блок, что и предыдущий, если позволяет ограниченная сверху остаточная емкость. В противном случае прямоугольник укладывается в нижнюю свободную позицию следующего блока. Алгоритм

о

Sub(NF) имеет временную сложность 0(т ) из-за необходимости формирования и поиска не заполненных блоков. В программной реализации разделения на блоки явно не присутствуют, при этом сложность алгоритма 0(m\ogm).

Замещение первым подходящим (SubFF). На каждом шаге первый подходящий предмет (его ширина не превосходит ширины остаточной емкости блока) из ж помещается в частично заполненный по ширине блок. Если подходящего предмета не нашлось, то формируется свободная позиция следующего блока и в нее упаковывается первый подходящий из ж предмет. Алгоритм Sub(FF) требует 0(т2 logm) времени

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

На рис. 3 и 4 приведены упаковки одного и того же набора прямоугольников с помощью стратегий NF, FF и BF В первом случае использовались уровневые структуры, во-втором - блочные. Длины упаковок, изображенных на рис.4 соответственно равны: L\ {Sub) = /j + /4 + /5; ¿2(Sub) = I\ + /3;

+ /5. Сравнивая их с длинами Ц, L2 и L3 уровневых упаковок, заключаем: L\(Sub)< L\, Lj(Sub) = Lj: ¿3(Sub) < ¿3. Преимуществом блочных структур является лучшее использование свободных областей.

а б в

Рис. 3 - Уровневые упаковки: а - стратегия NF; б - стратегия FF; в - стратегия BF

а б в

Рис. 4 - Упаковки блочной структуры, алгоритм Sub-а - стратегия NF; б - стратегия FF; в - стратегия BF

Метод перестройки (Reconstruction, Ree). Выполняется в качестве дополнительной процедуры в процессе конструирования упаковки. В диссертации она описана в рамках алгоритмов Sub.

Предположим, что получено частичное решение задачи ROCS. Оно представлено списком S и удовлетворяет свойствам 1° и 2° Определяющим для RP является выполнение свойства 6° размещаемости прямоугольников Предположим, что для некоторой пары последних кортежей (j, j+1 ) при формировании свободной области нарушено это свойство Тогда будем говорить, что при переходе с кортежа j к кортежу (/+1 ) возникла ситуация перестройки, а соответствующие области (/+1)-го блока назовем критическими. Для преодоления ситуации перестройки предложены два переборных алгоритма: «сверху-вниз» (Up-Down Reconstruction, URec) и «снизу-вверх» (Down-Up Reconstruction, DRec).

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

• URec почти во всех случаях обеспечивает получение упаковок с лучшим значением показателя качества (коэффициента упаковки)

• в трудных случаях время t расчета алгоритмом URec почти на порядок больше времени t с алгоритмом DRec;

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

Метод поиска двойных блок-структур (Double Block Structure Search, DBSS). Алгоритм DBSS конструирует RP в два этапа. На первом решается задача ROCS при заданной перестановке к. На втором этапе решается задача ROCS* с учетом условий 3°. Если решение удовлетворяет условию N* <W, то ROLC* - допустимо, остается найти координаты (х; у) упаковки. Однако предложенная переборная эвристика не гарантирует быстрого получения допустимой ROLC*.

Декодеры блочной структуры. Блочный декодер BD разработан для генетического блочного алгоритма GBA. Там он применяется на этапе расшифровки ж, полученного путем конкатенации блок-структуры упаковки. Вместе с тем BD ориентирован на формирование блочной структуры любой RP. В качестве начального блока принимается полоса бесконечной длины. По мере упаковки прямоугольников согласно ж формируют и модифицируют блоки. В блок-структуре хранятся фрагменты прямоугольников. Для добавления в блок-структуру очередного прямоугольника необходимо также знать размеры пустых участков, остающихся в блоках. Для этого предложено хранить ширину такого участка в самой блок-структуре. При формировании блоков и их заполнения используется стратегия «нижний-левый».

Усовершенствованный блочный декодер (Improved BD, IBD). Под усовершенствованием блок-структуры понимается корректное (в соответствии с размерами размещаемых прямоугольников) изменение длины блоков, ширины пустых участков, а также добавление новых блоков. Эксперименты показали, что алгоритм дает лучшие результаты, если в декодере на этапе размещения добавить простые эвристики, смещающие прямоугольник в пределах пустого участка. Применение эвристики для смещения прямоугольника зависит от случайной величины, разыгрываемой для каждого прямоугольника. Вычислительная сложность BD и IBD - 0(т3).

Развитие декодеров блочной структуры. Пусть имеется прямоугольная упаковка RP длины L в полосу ширины W и представлена ее вертикальная блок-структура S. Каждому блоку v поставлен в соответствие список номеров прямоугольников, пересекающих и-й блок длины %v ■ При этом легко вычисляется и фиксируется х-координата каждого размещенного прямоугольника. В модификации нет априорного закрепления у-координаты за прямоугольником. Она может изменятся в процессе конструирования упаковки*'.

Свойство реставрации упаковки. Важной характеристикой декодера является его способность получить оптимальную безотходную упаковку, по заранее известному оптимальному коду (приоритетному списку), т.е. способность правильно декодировать. Названо это свойство декодера термином «реставрация». Алгоритмы SubNF, SubFF, BD и FBD обладают свойством рестав-

* Модификация предложена Д С Назаровым, и названа нами плавающим блочным декодером (РВИ) [23]

рации. Это было замечено нами и доказано при проведении экспериментов с безотходными упаковками Е. Хоппер.

Численные эксперименты. Проведены два численных эксперимента с задачами Е. Хоппер и В. Тартон серий С и N. В этих экспериментах задачи решались с помощью детерминированных алгоритмов-декодеров. Эксперимент 1 проведен на задачах серии С в заданном авторами порядке прямоугольников. Эксперимент 2 проведен на задачах серии NR, которые отличаются от исходных задач серии N порядком следования прямоугольников.

Эксперимент 1. Исходными данными являются задачи Е. Хоппер и В. Тартон серии С. Приведено 7 групп задач. В каждой группе по 3 задачи. Выходными данными являются коэффициенты раскроя (Cutting Coefficient,

m

СС), СС = ——^100%, где L - достигнутая длина допустимой упаковки. WL

Эксперимент проведен с блочными декодерами: BD, IBD, SubFF, SubNF, GSub, FBD, IFBD (нерсставрационный FBD). Кроме того, приведены результаты алгоритма BLF "нижний-левый" Б. Чазелле (В. Chaselle) с модификацией Е. Хоппер и В. Тартон. Эти данные взяты из диссертации С. Имахори. Средние значения СС по каждой группе задач приведены в табл. 1.

Таблица 1 - Результаты численного эксперимента 1, средние значения СС _____декодеры блочной структуры _

Группа m W Оптимум BLF BD IBD SubFF SubNF GSub FBD IFBD

С1 16, 17 20 20 89 100 88 100 100 84 100 88

С2 25 40 15 84 100 100 100 100 90 100 96

СЗ 28, 29 60 30 88 100 96 100 100 84 100 96

С4 49 60 60 95 100 93 100 100 87 100 90

С5 73 60 90 95 100 87 100 100 87 100 92

С6 97 80 120 95 100 93 100 100 80 100 91

С7 196, 197 160 240 95 100 90 100 100 88 100 96

Среднее значение СС 91 100 92 100 100 86 100 93

Жирным шрифтом в таблице выделены лучшие значения коэффициентов СС, полученные алгоритмами, не обладающими свойством реставрации. Время, затраченное на решение одной задачи (С1-С6) Е. Хоппер и В. Тартон менее 0 I секунды, задачи серии С7 - 0.64 секунды. Мы на эту задачу затрачивали менее 0.09 секунд.

Эксперимент 2. Исходными данными являются задачи NR, полученные изменением порядка из задач Е. Хоппер и В. Тартон серии N. Это сделано с целью исключения эффекта «реставрации» для декодеров FBD, IFBD, BD, IBD, SubNF и SubFF. Средние результаты численных расчетов (средние значения СС) приведены в табл. 2, выделены лучшие их них.

Декодер IFBD показывает лучшие результаты, чем реставрационные декодеры FBD, BD и SubNF. Декодер BD уступает своей усовершенствованной версии IBD Декодеры SubNF и SubFF достигают лучших результатов, чем BD и IBD. Заметим, что в эксперименте 1 декодер SubFF показывает худшие

результаты. Это демонстрирует зависимость эффективности алгоритмов от порядка подачи прямоугольников на упаковку. По результатам экспериментов можно судить о тенденции алгоритмов 1РВВ и 5иЬРЕ "быть лучшими".

Таблица 2 -Результаты численного эксперимента 2, средние значения СС

Группа задач m FBD IFBD BD IBD SubNF SubFF

NR1 17 67 2 77.2 73 0 72 4 73 0 77.5

NR2 25 67 2 79.0 74 6 76 6 75 7 78 0

NR3 29 68 0 80.8 74 0 78 9 78 4 77 9

NR4 49 69 1 80.7 77 6 77 3 76 4 76 5

NR5 73 69.9 84.5 81 1 83 0 79 7 81 7

NR6 97 67 1 82.3 77 5 78 1 81 6 80 7

NR7 197 68 3 83 0 82.2 82 6 87.0 84 3

Среднее 68 1 81.1 77.1 78 4 78 8 79 5

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

Эволюционные алгоритмы (Evolution Algorithm (ЕА)) включают в себя группу метаэвристик, предназначенных для поиска и отбора лучших решений. В основе ЕА находятся элементарные понятия теории эволюции: наследственность, мутация, селекция. Основная идея ЕА состоит в построении некоторого множества решений оптимизационной задачи (популяции) и получении путём случайных действий новых решений взамен плохо пригодных старых. Хранение информации о нескольких допустимых решениях на каждой итерации создает эффект параллельных вычислений и казалось бы, повышает шансы нахождения оптимума. Вместе с тем алгоритмы с одной пробной точкой являются эффективными Это относится и к скорости решения и получению качественных результатов. Мы пришли к этому заключению экспериментальным путём Разработан ряд эволюционных алгоритмов для решения задач упаковки. В диссертации приведен эволюционный алгоритм (1+1)-ЕА, генетический классический алгоритм (GA) и генетический блочный алгоритм (GBA). Все алгоритмы работают с декодерами блочной структуры.

Ключевыми моментами ЕА являются механизмы отбора особей с хорошей пригодностью. В общей схеме ЕА популяция размерности ç определяется как вектор П = (jj,^»—компоненты sni- l,ç которого являются особями. Предположим, что имеется некоторый алгоритм Init для построения начальной популяции П^. К преобразованию популяции на каждой итерации применяются операторы Тс - селекции, Тр -репродукции и Тв — выживания,

предназначенные соответственно - для выбора родительских особей, построения новых особей и отбора их в новую популяцию. Кроме того, используется оператор 7"д./ - мутации, который выводит особи из текущей окрестности. Простые эволюционные стратегии (1+1)-ЕА и (1, А)-ЕА предложил И. Рехтенберг (I. Rechtenberg) в связи с решением задач непрерывной оптимизации. Подробнее остановимся на одноточечной стратегии (1 + 1)-ЕА.

Общая схема стратегии (1 + 1)-ЕА для решения задач 2DSP. В эволюционных алгоритмах для задач 2DSP в качестве особей выступают блок-структуры упаковок. Помимо особей в ЕА принято рассматривать их генотипы, представляющие множество особей с одинаковой пригодностью Л генотипа. В качестве генотипа для (RP, ж) выступает прямоугольно-ориентированный линейный раскрой (ROLC, ж) с пригодностью Л, и ему отвечают особи в виде блок-структуры RP различной длины L > Л. Пара (генотип ROLC, особь RP) воспроизводится из одного и того же кода ж (перестановки), несущего смысл хромосомы особи. Приведем одну из схем этого алгоритма для задач 2DSP.

Эволюционный алгоритм (1+1)-ЕА, который часто называют «наивным», работает с входной информацией (W\m\w,l). Результатом работы каждого этапа алгоритма являются упаковка RP, закодированная в виде блок-структуры BS, её длина L. Исходная и текущая информация подвергаются эволюционным преобразованиям. При этом популяция содержит только одну особь - прямоугольную упаковку RP, её генотип - прямоугольно ориентированный раскрой ROLC и код (хромосому) - перестановку ж. Качество решения определяется показателями Л —N и отклонениями (gap в %) решения L от Л - локальной и /,5-глобальной нижней границы (Lower Bound (LB)):

/д. L-А L-LB

gap (A) = —j—; gap (LB) = —-—.

Блочная схема (1+1)-EA с поиском в ROLC-окрестности

Вход (W;m,w;l).

0. Применить Init: k~0; рекорд /?•=со; ж0 = (л^.Я"® k:=k + \.

1. Для к = 1 до к = ктъх выполнять:

1.1. (ROLC*; Ак):=Тр {якЛ => ROLC, А); выполняется декодером,

воспроизводим перестановку ж (хромосому) в ROLC (генотип) с показателем пригодности А;

1.2. (ROLC4): если Ак > R и к < kmzx, то перейти на 3, иначе

1.3. (RP к; Lk ).= Тр (ROLC к => RP, L), R = min(Lk; R);

1.4. rg(RPfe): если Lk > Ak и критерий окончания поиска в окрестности

к к >■* не выполнен, то переити на 2, иначе если L = А перейти на 3, иначе если

к = ктях перейти на 4.

2. Мутация в ROLC-окрестности.

к к к ¿—1 71 new '-'гТм (ROLC ); к.~к+\, ж '.~ft„ew, выполняется перестановкой

пассивных элементов в блоках ROLC с последующей конкатенацией. Перейти на 1.3.

3. Мутация вче окрестности ROLC

Лпем>'~Тм (OutROLC*): к:=к+1, кк перейти на 1.1.

4. Конец Найдена лучшая упаковка.

Выход. <RP, L; gap Л; gap LB; ¿-количество итераций> На базе (1+1)-ЕА с применением различных декодеров и операторов приёмов мутации можно конструировать различные алгоритмы с поиском локального оптимума в ROLC-окрестности и приближением к глобальному оптимуму.

Генетический блочный алгоритм (Genetic Block Algorithm, GBA).

Пусть задана исходная информация для решения задачи 2DSP. На ее основании формируется задача 1DCS. Решая эту задачу с учетом ограничений 1° и 2°, получаем ROLC и значение Л функции цели Плану линейного раскроя отвечает блок-структура, вообще говоря, не являющаяся прямоугольной упаковкой. Кортежи (блоки) расположены в установленном v=l,2,... порядке и связаны друг с другом. Это позволяет интерпретировать их как гены. Тогда блочную структуру, соответствующую ROLC, можно интерпретировать хромосомой, содержащей сцепленные между собой гены (кортежи), которые расположены «слева-направо». Местоположение определенного гена в хромосоме является локусом, а альтернативные формы одного и того же гена, расположенные в одинаковых локусах хромосомы, интерпретируются аллелями. Хромосома, содержащая в своих локусах конкретные значения аллелей, является генотипом. Конечное множество всех допустимых генотипов образует генофонд. Численность генофонда популяции в множестве эквивалентных ROLC, к п

= 2>v!> где r'J ~~ количество пассивных в блоке v элементов. Фиксированный

V = 1

ROLC и отвечающий ему генофонд определяют окрестность, в которой далее реализуется поиск локального оптимума. В качестве ареала - области, в пределах которой только и могут встречаться особи, участвующие в эволюционном процессе, рассматривается область поиска RP. В общем случае экстремальной задачи 2DSP популяция соответствует совокупности допустимых решений. С помощью основных генетических операторов кроссовер Тк и селекция Тс может быть найдена особь с показателем L=Л. Далее ареал расширяется за счет мутации перехода к новой окрестности, например введения, удовле-

о "

творяющих только условию 1 , ROLC. Численность генофонда k =п\ X rv'

V = 1

Численные эксперименты. Целью численных экспериментов являлось сравнение эффективности эволюционных алгоритмов: (1 + 1)-ЕА, генетического блочного алгоритма (GBA) с известными методами: классическим генетическим алгоритмом (GA) и мультиметодным генетическим алгоритмом (GMA).

Здесь приведен небольшой срез экспериментов.

Эксперимент 3.1. В качестве исходных использовались данные, сгенерированные случайным образом. При этом были заданы параметры: 1 ООО -

ширина полосы; т=20; 40; 60; 80; 100 - количество прямоугольников; ОД) -размеры г-го прямоугольника, i = \,m.

Расчеты проводились на ПЭВМ Pentium III-933 для трех наборов исходных данных с параметрами: v, - нижнее ограничение ширины прямоугольника, т.е. w, > v, • W ; v2- верхнее ограничение ширины, т.е. w, < v7 ■ W ; et, - нижнее ограничение длины прямоугольника, т.е. /, > ет, • W ; т2 - верхнее ограничение длины, т.е. < ет2 • W.

Набор №1 : v, =0.10; v2=0.50; е7,=0.15; щ =0.50 (большой разброс размеров прямоугольников).

Набор №2: v, =0.25; и2=0.40; ет, =0.35; ят2 -0.60 (средние и крупные прямоугольники)

Набор №3: v, =0.10; v2=0.15, й7,=0.15; ш2 =0.20 (мелкие прямоугольники).

В каждом классе задач и для каждого набора было просчитано по 100 примеров. На основании интегральной теоремы Лапласа этого достаточно для оценки эффективности алгоритмов. Средние результаты решения в виде коэффициентов раскроя (Cutting Coefficient, СС) записаны в табл. 3. Показателем

m /

эффективности служит коэффициент CC=I'.w,^ /(LxW). Для решения ис-

(=1 /

пользовались эволюционные алгоритмы, реализованные по схемам (1+1)-ЕА и генетического метода GA. Первая группа ((1+1)-ЕА) включает E(Sub) - наивный алгоритм с декодером Sub; E(DBS) - наивный алгоритм с использованием двойных блок-структур; E(GSub) - наивный алгоритм с жадным замещении. Во второй группе, генетических алгоритмов, в эксперименте участвовали GMA - генетический мультиметодный алгоритм И.П Норенкова и GA(BL) -классический генетический алгоритм с декодером «нижний-левый».

Жирным шрифтом в табл. 3 выделены лучшие значения коэффициентов СС. Анализируя результаты, можно сделать следующие выводы:

• эффективность эволюционных алгоритмов блочной структуры (E(Sub), E(DBS), E(GSub)), реализованных по схеме (1+1)-ЕА мало зависит от выделенных наборов данных и от количества m прямоугольников;

• лучшие решения получены с помощью блочных алгоритмов для прямоугольников средних или мелких габаритов (наборы №2 и №3);

• E(DBS) дает лучший коэффициент раскроя по сравнению с E(Sub);

• блочные схемы значительно эффективнее традиционного генетического алгоритма GA;

• для набора №1 (разброс различных размеров прямоугольников) лучшие результаты показал алгоритм E(Gsub);

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

• лучшие результаты среди всех испытываемых алгоритмов демонстрирует Е(С8иЬ).

Заметим, что временные затраты были отведены примерно равные для всех алгоритмов и увеличивались до 60 секунд по мере роста т Заметим, что при м>100 эффективность (>МА и Е(С8иЬ) возрастает.

Таблица 3 - Результаты численного эксперимента 3.1

m Набор N°1

алгоритмы с блочной структурой генетические алгоритмы

E(Sub) E(DBS) E(GSub) GA(BL) GMA

20 93.11 94.65 94 00 89 76 94 27

40 92 41 94.03 95.00 89.65 94 70

60 92.52 94.10 95.46 88 85 95.62

80 92.34 93 87 96.03 88.34 95 57

100 92.7 93.91 96.10 87.83 95 80

Набор №2

m алгоритмы с блочной структурой генетические алгоритмы

E(Sub) E(DBS) E(GSub) GA(BL) GMA

20 94.55 92.86 88.25 90.67 85.22

40 93.74 94.19 91.75 92 10 93.22

60 93.82 94.65 93.93 91.51 93.61

80 94.54 94.22 94.27 91 27 94 29

100 94 37 94 37 95.20 90.62 95.21

Набор №3

m алгоритмы с блочной структурой генетические алгоритмы

E(Sub) E(DBS) E(GSub) GA(BL) GMA

20 92.00 91.90 89.28 85.06 90 12

40 93 29 94.04 92.76 92.19 92.83

60 94 00 93 56 94.09 92.16 93.42

80 93 70 94.32 94.13 92.00 93.31

100 94 10 94.88 94 54 91 72 93.84

Эксперимент 3.2. Исходные данные для этого эксперимента взяты из статей И. Беркли (J. BerkJey), П. Ванг (P. Wang) и С. Мартелло, Д. Виго. Эти данные использованы А. Боргфельдом при тестировании генетического алгоритма SPGAL, разработанного им на базе уровневой технологии. В эксперименте участвовал также генетический алгоритм с декодером «жадное замещение» (GA(GSub)) Для сравнения приведены значения нижней границы, полученные с помощью линейного программирования с учетом условия 1°. Результаты эксперимента сведены в таблицу 4. Наборы данных состоят из 10 классов и 50 подклассов. GA(GSub) работает лучше для 7 из 10 классов и для 30 из 50 подклассов. Для сравнения приведены лучшие результаты А. Иори от 2002 г. GA(GSub) работает лучше во всех классах. Только в 2-х подклассах результаты А. Иори превосходят GA(Sub). В среднем для всех 500 задач, результаты, представленные А. Иори, А. Бортфельдом и полученные блочными алгоритмами в виде отклонений (gap) от нижней границы составляют 3.05, 2.21, 2.13.

Лимит расчетного времени - 60 сек. для всех алгоритмов. При лимите в 360 сек. результаты с отклонением 1.85 показал алгоритм Е(С8иЬ).

Таблица 4 - Результаты эксперимента 3.2

Класс Ш Нижняя граница и? 1оп еЬа! 2002 8аР (%) лучший алгоритмы с блочной ст| эуктурой

8РСАЬ СА(С8иЬ) СЗА(1В0) Е(С8иЬ)

длина! 8ар(%) длинаЬ £ЯР(%) длина! цлина £ ёар(%)

С1 10 187,20 0,62 188,08 0,75 187,98 0,59 188,46 0,89 188,12 0,65

С 2 30 64,50 1,93 60,74 0,84 61,22 1,23 61,30 1,21 61,30 1,35

СЗ 40 504,10 3,08 513,40 2,52 511,58 1,99 516,82 2,75 511,92 2,08

С4 100 193,50 4,80 197,90 3,08 199,66 3,22 200,36 3,17 200,16 3,49

С5 100 1613,20 3,12 1646,98 2,53 1640,14 2,08 1653,78 2,77 1640,88 2,13

С6 300 506,40 5,62 524,68 4,67 527,74 4,44 532,22 4,56 528,70 4,52

С1 -Сб среднее 3,20 521,96 2,40 521,39 2,26 525,49 2,56 521,85 2,37

С7 100 1577,80 1,18 1592,70 1,22 1591,40 1,13 1595,82 1,35 1591,40 1,13

С8 100 1397,90 5,77 1442,12 3,66 1446,38 3,60 1470,48 4,81 1451,82 3,97

С9 100 3343,10 0,07 3346,70 0,12 3346,16 0,07 3346,16 0,07 3346,16 0,07

СЮ 100 909,20 4,58 933,34 3,04 937,28 3,19 946,82 3,92 942,42 3,66

С7-С10 среднее 2,90 1828,97 2,01 1830,31 2,00 1839,82 2,54 1832,95 2,21

С1- СЮ среднее 3,05 1175,47 2,21 1175,85 2,13 1182,66 2,55 1177,40 2,29

Глава 6 заключительная, в ней рассматриваются: общая технология блочных структур для решения задач ортогональной упаковки, представляющая синтез эволюционных алгоритмов с различными декодерами блочной структуры и примеры применения разработанной блочной технологии к решению некоторых других задач раскроя и упаковки. Это задачи упаковки в листы (контейнеры); параллелепипедные упаковки; прямоугольные упаковки в открытый квадрант и задача прямоугольного покрытия. Для всех рассмотренных задач и методов их решения проведены численные эксперименты и на основании их результатов сформулированы выводы о высокой эффективности блочной технологии для решения приведенных в диссертации задач. Описаны примеры использования методов и алгоритмов в промышленных разработках: при расчете подетальных норм расхода материала в раскройно-заготовительных цехах машиностроительных предприятий; упаковке товаров на складах и при транспортировке; проектировании размещений газоанализаторов; и другие.

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

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

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

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

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

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

4. Блочная технология использована для разработки новых алгоритмов конструирования упаковок (декодеров): декодеры замещения, декодер «поиска двойных блок-структур» (ОВЗБ), «блочные» декодеры. Они показали свои преимущества как при использовании в качестве конструктивных эвристик, так и при включении в схемы эволюционных алгоритмов. Их применение позволяет сократить отходы при упаковке в среднем в 2-3 раза. Кроме того их одномерная структура облегчает учет технологических и иных производственных ограничений.

5. Модифицированы эволюционные алгоритмы с использованием декодеров блочной структуры: (1+1)-ЕА и генетический алгоритм С А. Предложен и детально разработан генетический блочный алгоритм вВА, в котором элементы генетики идентифицированы согласно блочным структурам. Результаты численного эксперимента подтвердили преимущества эволюционных алгоритмов с блочными декодерами по сравнению с другими алгоритмами

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

7. Блочная технология методов конструирования упаковок применена для решения различных задач упаковки и раскроя: упаковки в контейнеры (листы); параллелепипедной упаковки; упаковки в открытый квадрант; простейшей задачи покрытия. Результаты эксперимента показали: высокую эффективность применения генетического алгоритма с блочным декодером для задачи контейнерной и параллелепипедной упаковки. Впервые удалось решить задачу упаковки в открытый квадрант с применением пары блок-структур. Блочная структура покрытия оказывается удобной для обхода запрещенных областей.

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

Основное содержание работы полностью раскрывается в следующих

публикациях:

Монография:

1. A.C. Мухачева. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума / A.C. Мухачева, А.Ф. Валеева, В.М. Картак // Москва. Изд-во МАИ. 2004. 192 с. Глава 1. Основные задачи и обзор методов решения. С. 8-25. Глава 2. Моделирование прямоугольной упаковки на базе блочных структур. С. 25-72.

Учебное пособие:

2. Э.А. Мухачева. Методы локального поиска в дискретных задачах оптимального распределения ресурса. Рекомендовано УМО по образованию в области экономики, статистики, информационных систем и математических методов в экономике / Э.А. Мухачева, А.Ф. Валеева, А.С Мухачева // Уфа. Изд-во УГАТУ. 2001. 103 с. Глава 2. Локальный поиск в задачах оптимального распределения одномерного ресурса. С. 33-75. Глава 3. Локальный поиск в задачах оптимального распределения двумерного ресурса. С. 78-85, 89-93.

Методические указания:

3. A.C. Мухачева. Методика тестирования и анализа результатов вероятностных алгоритмов локального поиска оптимума. Методические указания к выполнению курсовых работ / A.C. Мухачева, А.Р. Усманова // Уфа Изд-во УГАТУ. 2003. 24 с.

Публикации в периодических изданиях из списка ВАК:

4. Мухачева Э.А. Генетический алгоритм блочной структуры в задачах двумерной упаковки / Мухачева Э.А., Мухачева A.C., Чиглинцев А.В // М Машиностроение. Информационные технологии. 1999.№11.С. 13-18.

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

6 Мухачева Э.А. Метод перестройки для решения задачи прямоугольной упаковки / Мухачева Э.А., Мухачева A.C. // М.: Машиностроение. Информационные технологии. 2000, №74. С. 11-17. (Личный вклад 0,3 м/п л.)

7. Мухачева A.C. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя / Мухачева A.C., A.B. Чиглинцев // М.: Машиностроение. Информационные технологии. 2001, №3. С. 27-32.

8. Мухачева A.C. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения / Мухачева A.C., Чиглинцев A.B., Смагин М.А., Мухачева Э.А. // М.: Машиностроение. Информационные технологии. 2001, №9. 28 с.

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

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

11. Мухачева A.C. Задачи упаковки прямоугольников: рандомизированная эвристика на базе двойственной схемы локального поиска оптимума / Мухачева A.C., Ширгазин P.P. // М.: Новые технологии. Информационные технологии. 2003 №5 С. 24-31.

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

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

14. Мухачева Э.А. Задача прямоугольной упаковки: методы локальною поиска оптимума на базе блочных структур / Мухачева Э.А., Мухачева A.C. // М.:Наука. Автоматика и телемеханика. 2004, №2. С. 101-112.

15. Шайтхауер Г. Планирование одномерного раскроя материала различной длины на базе непрерывной релаксации и метода отсекающих плоскостей / Шайтхауер Г., Белов Г.Н., Мухачева Э.А., Мухачева A.C.// М : Новые технологии. Информационные технологии. 2004, №1. С. 28-36.

16. Мухачева Э.А. Л.В. Канторович и задачи раскроя упаковки: новые подходы для решения комбинаторных задач линейного раскроя и прямоугольной упаковки / Мухачева Э.А., Мухачева А.С.//Санкт-Г1етербург: Записки научных семинаров ПОМИ. Теория представлений; динамические системы. XI специальный вып. 2004. Том 312. С. 239-256.

17. Филиппова A.C. Задача двумерной упаковки в полубесконечную полосу: численный эксперимент с алгоритмами локального поиска и с декодерами блочной структуры / Филиппова A.C. // М.: Новые технологии. Информационные технологии. 2005, №6. С. 32-48.

18. Филиппова A.C. Задача прямоугольной упаковки в полубесконечнуто полосу: численный эксперимент с безотходными задачами Е. Hopper на базе алгоритмов блочной структуры / Филиппова А.С , Мухачева Э А Чиглин-цев A.B. // М.: Новые технологии. Информационные технологии. 2005, №7. С.23-32.

19. Филиппова A.C. Проблемы декодирования прямоугольных упаковок: краткий обзор современных технологий / Филиппова A.C. // М.: Новые технологии Информационные технологии. 2005. № 12. С. 13-20.

20. Филиппова A.C. Блочная технология конструирования алгоритмов для решения задач прямоугольной упаковки полубесконечной полосы / Филиппова A.C. // Уфа: Уфимск. гос. авиац. техн. ун-т. Вестник УГАТУ. 2005, т.6, №1 (12). С. 106-116.

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

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

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

24. Мухачева Э.А., Проектирование упаковок на базе развития технологии блочных структур / Мухачева Э.А., Назаров Д.А., Филиппова A.C., Чиг-линцев A.B. // М.: Новые технологии. Информационные технологии. 2007, №1. С. 12-21.

25. Филиппова A.C. Конструирование ортогональной упаковки в полубесконечной полосе на базе декодеров блочной структуры / Филиппова АС// Уфа. Вестник БГУ. 2006. №3. С. 6-8.

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

26. Мухачева Э.А. Модели и алгоритмы расчета прямоугольного раскроя и упаковки на базе оценок Л.В. Канторовича / Мухачева Э.А., Мухачева A.C., Шехтман Л.И. // Уфа. Комплексный анализ, дифференциальные уравнения, численные методы и приложения, т. IV. Применение численных методов, геометрические задачи. ИМВЦУНЦРАН. 1996. С. 97-103.

27. Мухачева A.C. Метод оценок для решения задач линейной и прямоугольной упаковки / Мухачева A.C., Житников В.П. // Уфа: Материалы международной научной конференции. Оптимизация численных методов. 1998. С. 40-45.

28. Мухачева А.С Генетический блочный алгоритм расчета прямоугольной упаковки на базе ее линейной аппроксимации / Мухачева А.С // Уфа: Межвузовский научный сборник. Выпуск третий. Вычислительная техника и новые информационные технологии. 1999. С. 61-69.

29 Мухачева A.C. Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем / Мухачева A.C. // Уфа. Дисс. канд физ-мат. наук. 1999. 117 с.

30. Мухева Э.А. Задачи одномерного раскроя-упаовки: численный эксперимент с методом последовательного улучшения оценок и методом ветвей и границ / Мухачева Э.А. Белов Г.Н., Картак В.М., Мухачева A.C. // Исследование операций. Бразилия. Т. 20, №. 2. 2000. С. 153-168. (на англ. языке)

31. Мухачева Э.А. Двойственный метод локального поиска оптимума для задачи двумерной упаковки / Мухачева Э.А., Мухачева A.C. // Екатеринбург: Институт математики и механики УрО РАН. Алгебра и линейная оптимизация. Труды международного семинара, посвященного 90-летию со дня рождения С Н Черникова. 2002. С. 292-299.

32. Мухачева A.C. Процедуры декодирования для решения задачи двумерной упаковки / Мухачева A.C., Чиглинцев A.B., Смагин М.А., Садрегдино-ва Н.М. // Труды 5-й межд. конф. «Компьютерные науки и информационные технологии». Уфа. Т.2. 2003. С. 44-47. (на англ. языке)

33. Мухачева A.C. Методы решения задач прямоугольной упаковки на базе генетического алгоритма / Мухачева A.C. // Уфа: Уфимск. гос. авиац. техн. унив. Принятие решений в условиях неопределенности: Межвуз. науч. сб. 2003. С. 164-169.

34. Филиппова A.C. Блочный декодер алгоритма локального поиска для задач упаковки в листы / Филиппова A.C., Месягутов М.А., Смагин М.А. // Труды 7-й межд. конф «Компьютерные науки и информационные технологии». Уфа. Т.2. 2005. С. 164-167. (на англ. языке)

35. Белов Г. Задача двумерной упаковки полубесконечной полосы: численный эксперимент с алгоритмами на основе блок-структур для безотходных примеров / Белов Т.Н., Чиглинцев A.B., Мухачева A.C., Мухачева Э.А., Шайтхауэр Г., Ширгазин P.P. // Дрезденский технический университет. Препринт. 2005. 17 р. (на англ. языке)

36. Филиппова A.C. Простые эвристики для решения двумерной задачи максимального покрытия / Филиппова A.C. // Уфа: Уфимск. гос. авиац. техн. ун-т. Принятие решений в условиях неопределенности: Межвуз. науч. сб. 2005. С. 38-44.

37. Мухачева A.C. Задача параллелепипедной упаковки: декодер на базе блочных структур / Мухачева A.C., Сурначев М.Ю.// Уфа: Уфимск. гос. авиац. техн. ун-т. Принятие решений в условиях неопределенности: Межвуз. науч. сб. 2005. С. 51-55.

38. Филиппова A.C. Модели и методы решения задач ортогональной упаковки на базе технологии блочных структур / Филиппова A.C. // Уфа Изд-во БГ'У. Международная уфимская школа-конференция по математике и физике для студентов, аспирантов и молодых ученных. 2005. С.

39. Сиразетдинов Т.М. Автоматизированная система проектирования прямоугольного раскроя CETAM1-CUT / Сиразетдинов Т.М., Мухачева A.C. и др. // Свидетельство об официальной регистрации программы для ЭВМ. №2004611452.

40. Ширгазин P.P. Программа расчета прямоугольных упаковок / Ширгазин P.P., Филиппова A.C. // Свидетельство об официальной регистрации программы для ЭВМ. №2006612649.

СПИСОК СОКРАЩЕНИЙ

(1+1)-ЕА - (наивный) эволюционный алгоритм

1DBP - задача одномерной упаковки в контейнер

1DCS - задача одномерного раскроя

2DBP - задача упаковки прямоугольников в контейнеры

2DSP (1.5DBP) - задача упаковки прямоугольников в полосу

2D АР - задача прямоугольной упаковки в открытую область (квадрант)

BD - блочный декодер

BF - лучший подходящий

BL - нижний-левый

BS — блок-структура

С&Р - раскрой-упаковка

СС - коэффициент раскроя

DBS - двойная блок-структура

DBSS - метод поиска двойных блок-структур

DRec - Rec алгоритм «снизу-вверх»

ЕА - эволюционный алгоритм

ES - эволюционные стратегии

FBD - плавающий блочный декодер

FF - первый подходящий

GBA - генетический блочный алгоритм

G А - генетический алгоритм

GMA - генетический мультиметодный алгоритм

gap - отклонение в % от нижней границы

GSub - жадный Sub

HBS - горизонтальная блок-структура

IBD - усовершенствованный блочный декодер

IBL - усовершенствованный нижний-левый,

LB - нижняя граница

NF - следующий подходящий

Rec -перестройка

ROCS - прямоугольно-ориентированная задача линейного раскроя ROLC - прямоугольно-ориентированный линейный раскрой RP — допустимая прямоугольная упаковка SS - поиск сумм подмножеств Sub - алгоритм замещения

SVC - метод последовательного уточнения оценок

TS - поиск с запретами

UBS - вертикальная блок-структура

URec - Rec алгоритм «сверху-вниз»

Диссертант

Филиппова А.С.

Филиппова Анна Сергеевна

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

Специальность: 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

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

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

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

СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

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

1.1. Комбинаторная задача оптимизации.

1.2. Задачи раскроя и упаковки.

1.3. Математические модели задач прямоугольной упаковки и раскроя.

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

1.5. Краткий обзор основных технологий решения 2DBP.

1.6. Проблемы кодирования и декодирования прямоугольных упаковок.

1.7. Применение методов решения задач С&Р в системах автоматизации раскроя-упаковки.

1.8. Результаты и выводы по главе 1.

2. БЛОК-СТРУКТУРЫ ПРЯМОУГОЛЬНОЙ УПАКОВКИ.

2.1. Пара блок-структур как способ кодирования прямоугольной упаковки.

2.2. Вертикальная блок-структура.

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

2.4. Воспроизведение перестановки в блок-структуру.

2.5. Воспроизведение перестановки в пару блок-структур.

2.6. Преобразование пары последовательностей в пару блок-структур.

2.7. Локальная нижняя граница прямоугольной упаковки.

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

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

2.10. Результаты и выводы по главе 2.

3. ЗАДАЧИ ЛИНЕЙНОГО РАСКРОЯ И УПАКОВКИ.

3.1. Модели и методы линейного программирования для решения задач одномерного раскроя.

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

3.3. Результаты и выводы по главе 3.

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

4.1. Конструирование прямоугольной упаковки полубесконечной полосы на базе стратегии нижний-левый».

4.2. Уровневые стратегии конструирования прямоугольных упаковок.

4.3. Блочные стратегии конструирования прямоугольных упаковок.

4.4. Свойство «реставрации» декодеров.

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

4.6. Результаты и выводы по главе 4.

5. ЭВОЛЮЦИОННЫЕ МЕТОДЫ ЛОКАЛЬНОГО ПОИСКА ОПТИМУМА В ЗАДАЧАХ ПРЯМОУГОЛЬНОЙ

УПАКОВКИ В ПОЛОСУ.

5.1. Общие схемы эволюционного алгоритма.

5.2. Алгоритм (1+1)-ЕА блочной структуры с локальной нижней границей.

5.3. Генетические алгоритмы.

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

5.5. Результаты и выводы по главе 5.

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

УПАКОВКИ И ПОКРЫТИЯ.

6.1. Алгоритмы размещения прямоугольных предметов на листах (контейнерной упаковки).

6.2. Задача и алгоритмы упаковки трехмерного контейнера.

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

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

6.5. Развитие и применение блочной технологии в задачах комбинаторной оптимизации.

6.6. Результаты и выводы по главе 6.

Актуальность проблемы. Исследование технологических процессов в различных отраслях промышленности показывает, что многие из этапов заготовительного производства связаны с раскроем и размещением деталей. Эти процессы являются очень важными с точки зрения экономии ресурсов и сложными для принятия решений. Возникают оптимизационные задачи раскроя и упаковки в процессе планирования и заказа материалов, а также на этапе оперативного проектирования карт раскроя и упаковки. Принятие оптимального или близкого к нему решения позволяет существенно сокращать расход материала и понизить себестоимость продукции. В условиях глобальной автоматизации промышленных процессов давно появилась необходимость в создании и использовании систем автоматизации проектирования подготовки раскроя и упаковки. К серьезным компьютерным продуктам, разработанным в России в этом направлении, можно отнести САПР «СИРИУС» (Екатеринбург) и «ТЕХТРАН-РАСКРОЙ» (Новосибирск). Первая базируется на работах Р.А. Вайсбурда и А.А. Петунина, вторая - на методах сквозного проектирования, развитых В.Д. Фроловским. Применение классических методов раскроя осуществлено В.А. Ворониным и В.А. Кузнецовым в лесоперерабатывающих комплексах Карелии. Больших успехов добиваются за рубежом. Это Канадские системы «Plan Q», «Cubel Q», разработка компании «Magic Logic Optimization Inc»; программный комплекс «Cut Planner» (Новозелендская компания «Remarkable Ideas»). Их разработки применяются в металлообрабатывающей, стекольной и мебельной индустрии. Общим недостатком всех систем является слабая степень оптимизации раскроя и упаковки. В хорошее сервисное окружение оказываются зашитыми неэффективные методы расчета.

Кроме того, появилось огромное количество мелких и средних предприятий, которые не могут позволить приобретение комплексов сквозного проектирования. Поэтому разработка и исследование численных методов оптимизации раскроя и упаковки, направленных на получение ресурсосберегающих технологий, является актуальной проблемой. Более того, задачи раскроя-упаковки встречаются не только в связи с проектированием технологической подготовки производства изделий. Проблема объединяет разные по математической и прикладной постановке задачи. В литературе они встречаются под различными названиями. Общим для них является наличие двух групп объектов. Требуется установить соответствие и порядок назначения между ними так, чтобы некоторая целевая функция достигала минимума. Начало развитию методов рационального раскроя положили в России лауреат Нобелевской премии JT.B. Канторович и профессор В.А. Залгаллер. Они заложили основы оптимизации гильотинного раскроя в массовом производстве с использованием линейного программирования. Работы были продолжены В.А. Булавским, Э.А. Мухачевой, И.В. Романовским, Г.Ш. Рубинштейном, М.А. Яковлевой,. Независимо за рубежом аналогичные результаты были получены П. Гилмори (P. Gilmore) и Р. Гомори (R. Gomory), И. Терно (J. Тегпо) и Г. Шайтхауер (G. Scheithauer). В индивидуальных производственных условиях задачи раскроя-упаковки оказываются NP-трудными, именно они охватывают огромный пласт прикладных и теоретических проблем. Принципиально различаются задачи упаковки геометрических объектов сложных форм (нестинга) и ортогональной упаковки прямоугольных объектов. В области нестинга известны работы Л.Б. Беляковой, М.А. Верхотурова, В.В. Мартынова, Ю.Г. Стояна, и других ученых. В области ортогональной упаковки - это работы Санкт-Петербургской (В.В. Бухвалова, И.В. Романовский), Новосибирской (Э.Х. Гимади, А.А. Колоколов, Ю.А. Кочетов), Петрозаводской (В.А. Воронин,

B.А. Кузнецов) и Уфимской (А.Ф. Валеева, Э.А. Мухачева) школ. За рубежом многие ученые занимаются этой проблемой. Наиболее известны работы X. Дикхоффа (Н. Dyckhoff), А. Бортфельда (A. Bortfeld), И. Фолкнера (Е. Folkenauer), Е. Хоппер (Е. Hopper),

C. Имахори (S. Imahori), С. Мартелло (S. Martello), Г. Шайтхауер (G. Sheithauer), П. Ванг (P. Wang), Г. Вешера (G. Wascher) и другие. Следует отметить, что методы, разработанные для ортогональной упаковки с успехом применяются и для задач нестинга.

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

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

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

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

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

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

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

3. Разработать способ определения окрестности локально-оптимального решения и алгоритм поиска этого решения.

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

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

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

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

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

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

На защиту выносятся следующие результаты:

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

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

3. Основные способы конструирования упаковок (декодеры) на основе блочных структур: «замещения» и «парных списков», их базовые и улучшенные версии.

4. Эволюционные алгоритмы для решения задач ортогональной упаковки: блочные модификации классического генетического алгоритма и эволюционного алгоритма (1+1)-ЕА с локальной нижней границей; разработка генетического блочного алгоритма; алгоритмы с синтезом простых декодеров конструирования упаковок, допускающих учет технологических параметров.

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

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

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

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

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

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

4. Создан метод кодирования упаковок блок-структурами: доказаны необходимые и достаточные условия соответствия блок-структур и упаковок. Это позволило разработать алгоритмы преобразования ранее известных кодов в «блок-структуры» для использования на различных уровнях при решении задачи упаковки.

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

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

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

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

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

Практическая значимость результатов. Разработанная в диссертации блочная технология ориентирована на создание методов расчета упаковок с учетом ограничений, возникающих в производственных системах. Для использования блочной технологии удобны метаэвристики, в составе которых применяются инвариантные к производству процедуры. Производственный фон включается только в процедуры конструирования упаковок, т.е. в декодеры. Такое включение может быть реализовано простыми приемами пользователя. Предлагаемый комплекс алгоритмов и программ отличается от аналогов малыми временными затратами для расчета ресурсосберегающих упаковок за счет применения высокоэффективных эволюционных алгоритмов с быстродействующими блочными декодерами. Это подтверждено использованием блочных технологий в процессе размещения контейнеров (ящиков) на складах и транспортных средствах, Холдинг «Новое время», г. Уфа; технологической подготовки производства металлоконструкций, ОАО «Буммаш», г. Ижевск; в подготовке производства целлюлозно-бумажной промышленности, г. Петрозаводск. Программное обеспечение интегрировано в промышленную систему Техтран-Раскрой, г. С.Петербург и автоматизированную систему проектирования прямоугольного раскроя, CETAMI-CUT, г. Уфа. Программы официально зарегистрированы, свидетельства № 2004611452, №2006612649. Результаты работы используются в учебном процессе Уфимского государственного технического университета, Уральского государственного технического университета - УПИ и Петрозаводского государственного университета.

Связь исследований с научными проектами. Работа выполнялась при поддержке Российского Фонда Фундаментальных Исследований, проекты 99-01-00937, 01-01-00510, 02-01-06331, 03-0107002; фонда Президента РФ поддержки молодых кандидатов наук, проект МК 145.2003.01; программы Мин. Образования РФ «Научные исследования высшей школы в области производственных технологий» (2001), раздел технологии современных заготовительных производств.

Апробация работы. Основные научные и практические результаты диссертации докладывались и обсуждались на Международных и Российских научных конференциях, в том числе: Сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-98) г.Новосибирск, 1998; Международной Сибирской конференции «Дискретный анализ и исследование операций», ИМ СО РАН, г.Новосибирск, 1998, 2000, 2002, 2004; 16-ой Европейской конференции по исследованию операций, г. Брюссель, Бельгия, 1998;

Международной конференции IFORS-2000, г. Сан-Антонио, США, 2000; Международной конференции 1FORS 2002, Эдинбург, Англия 2002; «Европейский научный семинар ESICUP», Виттенберг, Германия, 2004; Международные конференции «Математическое программирование и приложения», ИММ УРО РАН г. Екатеринбург, 1999, 2001, 2003, 2004; Международная научная конференция «Моделирование, вычисление, проектирование в условиях неопределенности», УГАТУ, Уфа, 2000; Байкальская международная школа-семинар «Математическое программирование», г. Иркутск 2002, 2005; Всероссийская научно-практическая конференция «Ресурсосберегающие технологии», Санкт-Петербург, 2001; Международная конференция «Математика и экономика: старые проблемы и новые подходы», памяти JI.B. Канторовича, С-Петербург, 2004; Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, 2003, 2006; Международная конференция CS1T, УГАТУ, Уфа, 2002, 2004, 2005; Международная Уфимская зимняя школа-конференция по математике и физике, БГУ, Уфа, 2005; на семинарах Института Вычислительной математики Дрезденского технического университета, Дрезден, 2002; семинарах кафедр «Вычислительной математики и кибернетики» и «Компьютерной математики» УГАТУ.

Публикации. По теме диссертации опубликовано более 80 работ. Основные результаты представлены в работах [1-44]. В число указанных публикаций входят 23 статьи из «перечня ВАК ведущих научных журналов и изданий, выпускаемых в Российской Федерации, в которых должны быть опубликованы основные научные результаты на соискание ученой степени доктора наук» В совместных работах с проф. Э.А. Мухачевой, доц. А.Ф. Валеевой, доц. В.М. Картаком и аспирантами УГАТУ А.В. Чиглинцевым, P.P. Ширгазиным принадлежат автору диссертации следующие разделы: идеи и подходы к созданию технологии блочных структур; блочные методы кодирования и декодирования упаковок; необходимые и достаточные условия соответствия блок-структур и упаковок; аппроксимация прямоугольной упаковки парой ослабленных задач прямоугольно ориентированного линейного 1 раскроя; способ «замещения» в блочных алгоритмах конструирования упаковки; алгоритмы «парных списков» и генетического блочного алгоритма с новой идентификацией элементов генетики, проведение и анализ результатов численного эксперимента. Э.А. Мухачевой принадлежат идеи разделения упаковки на прямоугольные блоки и ситуации «перестройки», возникающей в ходе конструирования упаковок. А.В. Чиглинцеву принадлежат разработки блочных декодеров с использованием стратегий нижний-левый и свойство «реставрации» некоторых декодеров (определение и доказательства), приведенные в главе 4 диссертации. В.М. Картак добавил условие неперекрытия прямоугольников для пары блок-структур.

Структура и объем работы. Диссертация состоит из введения, шести глав основного материала, заключения, библиографического списка и приложений; содержит 313 страниц основного текста. Библиографический список включает 212 наименований литературы.

Выводы по результатам эксперимента №6.

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

2. Для 10 из 26 "плохих" задач получено оптимальное решение.

3. Только для 3-х "плохих" задач оптимум может отличаться от достигнутого решения примерно на один процент.

4. Локальный оптимум достигнут в 24-х задачах из 26.

ЗАКЛЮЧЕНИЕ

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

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

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

4. Блочная технология использована для разработки новых алгоритмов конструирования упаковок (декодеров): декодеры замещения, декодер «поиска двойных блок-структур» (DBSS), «блочные» декодеры. Они показали свои преимущества как при использовании в качестве конструктивных эвристик, так и при включении в схемы эволюционных алгоритмов. Их применение позволяет сократить отходы при упаковке в среднем в 2-3 раза. Кроме того их одномерная структура облегчает учет технологических и иных производственных ограничений.

5. Модифицированы эволюционные алгоритмы с использованием декодеров блочной структуры: (1+1)-ЕА и генетический алгоритм GA. Предложен и детально разработан генетический блочный алгоритм GBA, в котором элементы генетики идентифицированы согласно блочным структурам. Результаты численного эксперимента подтвердили преимущества эволюционных алгоритмов с блочными декодерами по сравнению с другими алгоритмами.

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

7. Блочная технология методов конструирования упаковок применена для решения различных задач упаковки и раскроя: упаковки в контейнеры (листы); параллелепипедной упаковки; упаковки в открытый квадрант; простейшей задачи покрытия. Результаты эксперимента показали: высокую эффективность применения генетического алгоритма с блочным декодером для задачи контейнерной и параллелепипедной упаковки. Впервые удалось решить задачу упаковки в открытый квадрант с применением пары блок-структур. Блочная структура покрытия оказывается удобной для обхода запрещенных областей.

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

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

2. Батищев Д.Ю. Генетические алгоритмы решения экстремальных задач: Учебное пособие / Под ред. Я.Е.Львовича. Воронеж: Воронежский гос. техн. ун-т; Нижегородский ун-т, 1995. -96с.

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

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

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

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

7. Валеева А.Ф., Гареев И.Р., Мухачева Э.А. Задача одномерной упаковки: рандомизированный метод динамического перебора и метод перебора с усечением // Информационные технологии. Приложение. 2003. №2. -24с.

8. Верхотуров М.А. Задача нерегулярного размещения геометрических объектов: современное состояние методов решения // Материалы всероссийской конференции ОПТИМ. -С.Петербург: ЦНИИТС, 2001. С. 33-37.

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

10. Воронин А.В., Кузнецов В.А. Математические модели и методы планирования и управления предприятиями ЦБП // Петрозаводск: Изд-во ПетрГУ. 2000. 256 с.

11. Галага А.Я., Стоян Ю.Г. О плотной упаковке параллелепипедов произвольных размеров в параллелепипеде наименьшего размера // Киев: Кибернетика. 1972. №2. С. 81-86.

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

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

14. Гимади Э.Х., Залюбовский В.В., Шарыгин П.И. Задачи упаковки в полосу: асимптотически точный подход // Известия высших учебных заведений. Математика. 1997. №12(427). С. 34-44.

15. Гончаров Е.Н., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследование операций. 1999. Серия 2. 6. №1. С. 12-32.

16. Горелик А.Г. Одиночно-последовательный метод параметризации моделей геометрических объектов // Информационные технологии. 2000. №10. С.38-44.

17. Грицюк 10. Регулярне размщувания прямокутних объект1в вздовж смуг односиоронньо обмежено! стр1чки. Льв1в: УкрДЛТУ. 2002. 220 с.

18. Ермаченко А.И., Сиразетдинов Т.М. Рекурсивный метод для решения задачи гильотинного раскроя // Принятие решений в условиях неопределенности: Межвуз. науч. сб. / Уфимск. гос.авиац. техн. ун-т. -Уфа, 2000. -С.35-39.

19. Залюбовский В.В. О представлении перестановками допустимыхрешений одномерной задачи упаковки в контейнеры // Иркутск. Изд-во института систем энергетики СО РАН. 13-я Байкальская международная школа семинар. Том 1. 2005. С. 461-468.

20. Канторович Л.В. Математические методы организации и планирования производства // JL: изд-во ЛГУ. 1939. 68 с.

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

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

23. Картак В.М. Решение задачи упаковки прямоугольников в полубесконечную полосу // Уфа: Регион, школа-конф. Молодых ученых по математике и физике. БГУ. Том 1. 2001. с. 110-121.

24. Картак В.М. Оптимальная упаковка N-мерных параллелепипедов в полубесконечность // Методы оптимизации и их приложения: 12-я Байкальская международная конференция. Иркутск, 2001. -С. 18-22.

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

26. Кокотов В.З. Алгоритм плотного размещения разногабаритных элементов на плате // Информационные технологии. 1998. -№ 11. -С. 16-21.

27. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Новосибирск: Сиб. журнал. Исследование операций. 1994. №2. С. 18-39.

28. Кофман А.Ф. Введение в прикладную комбинаторику. М.: Наука, 1975.447с.

29. Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет, анализ и исслед. операций. Сер. 2. 2003, Т. 10, № 1. -С. 11-43.

30. Кочетов Ю., Усманова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // Методы оптимизации и их