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

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

ВАЛЕЕВА Аида Фаритовна

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических'Ьаук

Уфа 2006

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

Научный консультант

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

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

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

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

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

заслуж. работник высш. шк. РФ, д-р техн. наук, проф. Прохоров Сергей Антонович

д-р техн. наук, проф. Фроловский Владимир Дмитриевич

Ведущая организация Институт математики с вычислительным центром УНЦ РАН, Уфа

Защита состоится 2006 г. ^ 0

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

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан "ДУ''2006 г.

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

Миронов В.В.

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

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

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

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

Фундаментальные научные результаты в области решения задач раскроя в условиях массового производства принадлежат Л.В. Канторовичу и В.А. Залгаллеру. Результаты дальнейших исследований в этой области отражены в работах В.А. Булавского и М.А. Яковлевой, Э.А. Мухачевой, И.В. Романовского, В.А. Кузнецова, а за рубежом П. Гилмори и Р. Гомори, И. Терно и Г. Шайтхауэра и др.

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

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

пор, пока оно не построено полностью и методы локального поиска оптимума, поиск локально оптимальных решений ведется в некоторой окрестности допустимого решения. Разработке эвристических методов локального поиска оптимума при решении задач упаковки и раскроя посвящены работы М. Дориго, И.П. Норенкова, Ю.А. Кочетова, Э.А. Мухачевой, Э. Фолкенауэра и др.

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

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

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

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

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

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

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

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

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

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

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

1. Теоретические основы расчета рациональной упаковки и раскроя, базирующиеся на модифицированном псевдополиномиальном алгоритме решения задачи 0-1 рюкзак, что позволяет решать задачу «-мерной упаковки (и = 1,2,3) в рамках единого подхода. Это обеспечивает высокое качество получаемых решений задач упаковки и раскроя, а также инвариантность к размерности решаемых задач.

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

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

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

5. Математическое и программное обеспечение, реализующее разработанные конструктивные методы и позволяющее решать задачи и-мерной упаковки (п = 1,2,3), возникающие в условиях единичного производства. Результаты анализа эффективности разработанного математического обеспечения для решения задач одномерной, прямоугольной и параплелепи-педной упаковки, полученные на базе численного эксперимента.

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

1. Разработана теоретическая база создания нового унифицированного метода высокой эффективности для решения задачи ортогональной п-мерной упаковки (и=1,2,3).

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

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

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

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

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

Обоснованность и достоверность результатов диссертации

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

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

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

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

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

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

• методического, алгоритмического и программного обеспечения для решения задач упаковки и раскроя промышленных объектов, позволяющего сократить в 1,5-2 раза сроки подготовки оптимальных решений при упаковке и раскрое и повысить показатели эффективности при решении задачи ресурсосбережения на 5—10%.

Результаты диссертационной работы внедрены в виде методов, алгоритмов, методик и программного обеспечения на ООО «Уралтехно-проект» (Екатеринбург), ООО «ВИВ-ФАРМ» (Москва), ГУП УАП «Гидравлика» (Уфа), а также в учебном процессе Уфимского государственного авиационного технического университета.

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

Исследования проводились в рамках научных грантов №01-01-00510, №03-01-07002 Российского фонда фундаментальных исследований.

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

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

• Международной научно-технической конференции «Актуальные проблемы математического моделирования и автоматизированного проектирования в машиностроении: МОДЕЛЬ-ПРОЕКТ 95», Казань, 1995;

• Конференции «Комплексный анализ, дифференциальные уравнения, численные методы и приложения. Геометрические задачи», Уфа, ИМВЦ РАН, 1996;

• 1-П Сибирских конгрессах по прикладной и индустриальной математике (ИНПРИМ-96,98), Новосибирск, 1996, 1998;

• 16-ой Европейской конференции по исследованию операций, Брюссель, Бельгия, 1998;

• Международной Сибирской конференции по исследованию операций, Новосибирск, 1998;

• Международной конференции «Поддержка жизненного цикла в производственных системах», Бремен, Германия, 1998;

• Конференции «Математическое программирование и приложения», УрО РАН, Екатеринбург, 1999, 2003;

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

• Международной конференции «Дискретный анализ и исследование операций» (ОАСЖ), Новосибирск, 2000, 2002, 2004;

• 16-ой международной конференции по исследованию операций, Эдинбург, Великобритания, 2002;

• Международной конференции «Компьютерные науки и информационные технологии» (СБГГ), Уфа, 2003-2005;

• 13-й Байкальской международной школе-семинаре, Иркутск, 2005;

• Международной уфимской зимней школе-конференции по математике, Уфа, 2005;

• Международном семинаре европейской группы по раскрою и упаковке (ЕигоЗЮПР), Порто, Португалия, 2006;

• III Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, 2006.

Публикации

Результаты диссертационной работы отражены в 80 публикациях, в том числе в одной монографии (в соавторстве), учебном пособии (в соавторстве), 31 статье, в том числе 8 статьях в изданиях из списка ВАК, 40 материалах международных и российских конференций, 2 свидетельствах государственной регистрации программ для ЭВМ.

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

Диссертация состоит из введения, пяти глав основного материала, библиографического списка и содержит 265 страниц основного текста. Библиографический список включает 191 наименование литературы.

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

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

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

В работе приведены задачи ортогональной «-мерной упаковки, где п=1,2,3 (Bin Packing Problem, ВРР), и раскроя (Cutting Stock Problem, CSP), представленных в следующих постановках:

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

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

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

Постановка задачи одномерной упаковки (1 Dimensional Bin Packing, JDBP) заключается в следующем. Даны контейнеры заданной вместимости íf и набор из т - предметов с весами w, е Z*, w,< W, i = 1,2,..., т. Требуется упаковать предметы в контейнеры так, чтобы количество занятых контейнеров было минимально.

Задача прямоугольной упаковки в полосу (1.5 Dimensional Bin Packing, 1.5DBP) состоит в следующем. Исходная информация задается набором данных <W,m,w,l>, W, т, w, le 2*. где IV - ширина полубесконечной полосы; т — количество прямоугольников; w=(w,,wj, ...,w„ ...,wm) — вектор ширин прямоугольников; /=(//,...,/„...,/„) — вектор длин прямоугольников. Вводится прямоугольная система координат XOY, у которой оси ОХ и OY совпадают соответственно с нижней неограниченной и боковой сторонами полосы. Решение задачи представляется в виде набора элементов <Х, К>, где X=(xj, х2,...,х„...,хт), У=(у/, у2,...,y¡.....ут) - векторы координат прямоугольников, (х„ у) — координаты нижнего левого угла прямоугольника соответственно по оси X и Y. Набор элементов <X,Y> называется допустимой прямоугольной упаковкой, если выполнены следующие условия:

1. Стороны прямоугольников параллельны граням полосы (условие ортогональности);

2. Прямоугольники не перекрывают друг друга: для i* j\i,j = \,...,m

((Х, > Xj +1j ) v {Xj £ x, + /.)) v (( v, > уj + Wj ) v (Vj > .v, + w,))

3. Прямоугольники не выходят за границы полосы: для всех 1 = 1,.. ,,т (х, >0)л(у, > 0)л ((у, + w,.) < W).

При выполнении условий допустимости требуется найти такую упаковку полосы, для которой длина ее занятой части L = max(jc, + /,| / = I,...,т) достигает минимума.

В задаче упаковки в прямоугольные листы 2DBP, кроме ширины листа W, известна его длина L. Обычно исходная информация о прямоугольниках такова, что одного листа для их размещения бывает недостаточно и требуется найти упаковку с минимальным числом занятых листов. При этом каждая допустимая упаковка удовлетворяет условиям 1, 2 и условию: для/=1,2,...,т(х, > 0) л {у] >0) л((у. + w,) < (Г) л(х.+/, < L).

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

Рассматривается задача параллелепипедной упаковки (3 Dimensional Bin Packing, 3DBP), состоящая в следующем. Исходная информация задается набором данных <W,L,H,m.w,l,h>, W, L, Н, т, iv, /, h е Z*, где W — ширина параллелепипеда; L — длина параллелепипеда; Н — высота параллелепипеда; /«-количество заданных предметов; w =(wi,-'iv,,-,w„)- вектор ширин предметов; / = (/,,...,/, ,...,/„) - вектор длин предметов; h - (h],~;h,-,---,h„)~ вектор высот предметов. Требуется найти упаковку т предметов в параллелепипед, занимающую минимальную высоту параллелепипеда (если задан параллелепипед неограниченной высоты, Н= со). При этом по аналогии с задачей прямоугольной упаковки, должны быть выполнены условия допустимости параллелепипедной упаковки. Если в задаче 3DBP, кроме ширины W, длины L, задана высота Н параллелепипеда, то при выполнении условий допустимости, требуется минимизировать количество упакованных параллелепипедов.

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

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

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

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

• отсутствуют методы для решения задач упаковки и раскроя, базирующиеся на решении задачи 0-1 рюкзак, несмотря на то, что сама задача 0-1 рюкзак сходна с простейшей задачей одномерной упаковки

С учетом изложенного выше в работе предлагаются:

• разработка конструктивных методов для решения задачи и-мерной упаковки (и=1,2,3) на базе модифицированного метода решения задачи 0-1 рюкзак, ставшего основой унификации методов для решения поставленных задач. Это позволило создать инвариантное математическое обеспечение, представляющее собой единое оптимизационное ядро;

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

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

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

Предложен унифицированный конструктивный метод динамического перебора для решения задачи ортогональной «-мерной упаковки (и=1,2,3) на базе модифицированного алгоритма решения задачи 0-1 рюкзак в детерминированном и стохастическом вариантах.

В работе используется следующая формулировка задачи 0-1 рюкзак: даны целые числа и>„ i=I,2,...,m и W. Требуется определить, существует ли такое подмножество I множества {1,2,...,т}, что w, = W.

Известно, что для решения задачи 0-1 рюкзак разработан псевдополиномиальный алгоритм (Pseudo-polynomial Algorithm, РА), в котором стро-

ятся множества М„ i=l,2,...,m, содержащие всевозможные суммы целых чисел w„ i=l,2,...,m, не превышающие W.

В работе устанавливается взаимно-однозначное соответствие между

числами w„ i—I,2.....т и множеством натуральных чисел {1,2.....т}: w,—»1,

w2—*2,...,wm—*т и ввести в рассмотрение кортежи вида (1,2,..., т) — упорядоченные наборы натуральных чисел. При этом пусть К — множество всех кортежей, тогда задача поиска кортежей (Tuple Search Problem, TSP) формулируется следующим образом:

Задача TSP. Даны целые числа и>„ i=l,2.....т и IV. Требуется сформировать такое множество К кортежей, чтобы выполнялись условия:

1. w, - Wу где /- подмножество множества {1,2.....т}\

2. добавление любого элемента из / , не входящего в кортеж, нарушает условие 1.

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

М„ i=l,2.....т, которые находятся по алгоритму РА, строится множество

кортежей К. Структурограмма модифицированного алгоритма РА (MP А) приведена на рис. 1.

Алгоритм МРА

Входные дачные: (V, м>„ 1=1,2.....т;

Выходные данные: К — множество кортежей

М(г{О},К=0.

Для I=1,...,т выполнить

Построение множеств М,:

для каждого целого числа из М,./ выполнить: добавить к А/, целые числа и если уу+м^ IV и М,-

Формирование множества кортежей К:

для каждого целого числа из М,., выполнить: найти кортежи, состоящие из номеров тех чисел, которые вошли в сумму м'+и',, если м>+Ы1< IV (кортежи находятся и в том случае, если число н'+н,,< IV уже есть в М,)

Найти н,„л1=шах и соответствующие и>та, кортежи из К.

__ч-еЛ/т____

Рис. 1 - Структурограмма модифицированного алгоритма решения задачи 0-1 рюкзак (МРА)

В работе разработан метод динамического перебора, в основу которого положен алгоритм МРА. При решении задачи ЮВР в качестве чисел /=1,2,...,т, и IV соответственно выступали веса предметов и емкость одномерного контейнера.

Идея детерминированного метода динамического перебора (Dynamic Sorting, DS), предложенного в работе, состоит в том, что строится множество кортежей К по алгоритму MP А. Из кортежей этого множества формировалось дерево вариантов упаковок, в котором вершины — емкость контейнера, а ветви — кортежи. При этом путь от корня до листьев определяет одну из упаковок. В дереве осуществлялся поиск упаковки с минимальным количеством контейнеров. При этом может быть найдено множество различных вариантов упаковок с одним и тем же значением целевой функции, что позволяет в случае необходимости выбирать наиболее приемлемое решение.

При решении задачи прямоугольной упаковки 1.5DBP в качестве чисел Wj, i=],2,...,m, и W соответственно выступали ширины прямоугольников и ширина полосы. При этом упаковка конечного набора прямоугольников мысленно разрезается вертикальными резами, проходящими через правые стороны прямоугольников. В каждом вертикальном резе выделяется опорная грань - непрерывный отрезок в упаковке, параллельный боковой стороне полосы, являющийся объединением левых вертикальных сторон, упакованных в полосу прямоугольников (см. рис. 2). На рис. 2 приведен пример упаковки с W=5, т-7, w~ (1,2,3,4,3,1,2), /=(1,2,2,2,3,5,5), списком кортежей (5,7), (2,6), (1,3), (4). Опорные грани выделены сплошными линиями.

5 6 1 1 1 1 Н

2 3 4 1

7

< 1

! ! ! ! !

Рис. 2 — Пример прямоугольной упаковки

Идея метода DS для решения задачи 1.5DBP состоит в поиске локальных минимумов в процессе упаковки прямоугольников для каждой длины опорной грани (см. рис. 2), а именно: решалась задача локальной упаковки (Local Packing Problem, LPP).

Постановка задачи LPP формулируется следующим образом: необходимо найти min у при следующих условиях

IwrZi+)' = s, У г О, z,e{0,l}; / = 1,2,...,т, !

где Wi — ширина /-го прямоугольника, se S, S — множество длин опорных граней, zy = 1, если используется /-я ширина прямоугольника, и z, = 0 в противном случае.

Для решения задачи 1.РР метод ОБ создает для каждой длины опорной грани множество кортежей и формирует дерево вариантов упаковок, в котором вершины — это длины опорных граней, ветви — кортежи, а пути от корня дерева до листьев — прямоугольные упаковки. Среди полученных упаковок ищется упаковка с минимальным значением целевой функции (длиной занятой части полосы). При решении задачи 20ВР с помощью этого метода в дереве вариантов упаковок ищется упаковка с минимальным количеством листов. Структурограмма предложенного алгоритма ОЗ1 для решения задач прямоугольной упаковки приведена на рис. 3.

Алгоритм ЛУдля решения задач ¡ 5ОВР, 2ВВР Входные данные: IV- ширина полосы или листа; - 1.2.....т - размеры прямоугольников Полагаем: текущая длина опорной грани 5= IV

Процедура!. Построение множества кортежей К по алгоритму МРА для каждой длины опорной грани

Процедура 2. Формирование дерева вариантов упаковок для длины опорной грани 5

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

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

Процедура 3. Проход по дереву вариантов и поиск в нем квазиоптимальной упаковки

Рис. 3 - Структурограмма алгоритма динамического перебора (DS) для решения задач прямоугольной упаковки

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

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

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

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

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

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

Рис. 4 - Пример работы модифицированного алгоритма проверки планарности графа упаковки

Экспериментальные исследования метода £>5 показали, что при возрастании количества предметов (т> 40) число кортежей во множестве кортежей К резко возрастает, и не представляется возможным не

только хранить все кортежи, но и осуществить проход по всем вершинам дерева вариантов.

В связи с этим был разработан рандомизированный метод динамического перебора (Dynamic Sorting Randomized, DSR), который является вероятностной модификацией метода DS.

Идея метода DSR состоит в том, что задача LPP решалась с помощью алгоритма МРА только для длины опорной грани s —fV. Затем строилось множество кортежей К, из которого случайным образом формировалось подмножество К*(р), мощность которого сверху ограничена параметром Nk — максимально возможным количеством кортежей. При построении подмножества К'(р) вводился параметр ре [0,1], определявший вероятность включения кортежа из К в подмножество К*(р): для каждого кортежа генерировалась псевдослучайная величина р*, равномерно распределенная на [0,1] и если она оказывалась меньше или равна р, то кортеж включался в К"(р), в противном случае — нет. Поскольку в подмножестве К~(р) должны также содержаться кортежи из одного элемента вида {/}, /=/.....т, то в этом случае р*=0. Далее, как в методе DS,

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

• при полном проходе задается количество обрабатываемых вариантов упаковки, которое равномерно распределяется между непосредственными потомками корня дерева вариантов;

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

При этом в обоих способах прохода по дереву вариантов при выборе пути от предка к одному из непосредственных потомков генерировалось псевдослучайное число от 1 до q, подчиненное равномерному закону распределения, где q — количество непосредственных потомков, и выбиралась вершина, соответствующая этому числу. Для сокращения перебора вариантов упаковки при проходе по дереву задаются ограничивающие перебор параметры: — число обрабатываемых вариантов упаковки и - число обрабатываемых вариантов в каждой ветви дерева. Если число обработанных вариантов в текущей ветви дерева становится равным осуществляется переход к другой ветви дерева. Это приводит к обработке множества различных областей дерева и расширению пространства поиска квазиоптимального решения.

На рис. 5 приведена структурограмма из основных процедур алгоритма DSR для решения задач 1.5DBP, 2DBP.

Алгоритм ОЯЯ для решения задач 1.50ВР, 2ВВР Входные данные: IV- ширина полосы или листа; ; /, •' = 1.2,...,/и - размеры прямоугольников

Процедура 1. Создание подмножества К множества кортежей

Процедура 2. Построение дерева вариантов упаковок

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

Процедура 4. Формирование случайным образом упаковок без построения дерева вариантов упаковок

Повторять до тех пор, пока не найдена квазиоптимальная упаковка

Рис, 5 — Структурограмма алгоритма рандомизированного динамического

перебора (£>5Л)

Методы решения задачи параллелепипедной упаковки базируются на декомпозиции исходной задачи и сведении ее к задаче меньшей размерности путем разбиения упаковки на слои специальной структуры: на слои по высоте самого высокого предмета (на рис. 6 высота слоя /&/ ) и на частичные слои - по высоте самого короткого предмета (на рис. 6 высота /'-го частичного слоя упаковки - //£>,, ¡=1, ...,5). Все множество предметов 7*„ ¡—},...,т, обозначим через Р, множество упакованных предметов - Р„ (в начальный момент Ри~0), множество предметов, которые еще предстоит упаковать - Р„, Рии Р„ = Р.

Рис. 6 — Разбиение параллелепипедной упаковки на слои

Рассматривается модификация известного послойного алгоритма С л-™ > который состоит в следующем: высота предмета Г, определяет высоту №/ первого слоя в параллелепипеде, параллельного дну. Затем,

как и в задаче прямоугольной упаковки, основание Ь• IV параллелепипеда заполняется прямоугольниками /, -ус,, являющимися основаниями предметов Г/, по методу N1<Х> («следующий подходящий с упорядочиванием») до тех пор, пока все предметы не будут упакованы или следующий предмет в последовательности Г, не станет невозможно упаковать в прямоугольник Ь ■ IV. Если не все предметы упакованы, то слой закрывается, и аналогично определяется следующий слой высоты /Л^. Если все предметы из Р упакованы, то процесс завершается. Используемая высота контейнера //„ равна сумме высот определенных слоев.

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

Метод на основе слойного алгоритма (СА). Основания слоев — прямоугольники представляются в виде 5 различных вертикальных слоев одной и той же ширины IV н длины гк, к=1,...,з. Совокупности вертикальных слоев отвечает список кортежей вида:

(т,2(к).....т{к]);гк, (1)

где = гшп н^*) • Высота слоя устанавливается по высоте самого высокого

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

Метод на основе модифицированного слойного алгоритма (МСА). Для более плотного заполнения слоя высоты Ш,, он разбивается на частичные слои длины Ь, ширины IV и высоты НЪЬ НЪк=тт{к), к~1.....Ъ. где Ь —

количество частичных слоев в рамках слоя высоты При этом начало первого частичного слоя совпадает с основанием параллелепипеда - прямоугольником который упаковывается по методу ОБ прямоугольниками, представляющими собой нижние грани предметов Т^Р,, до тех пор, пока не останется пространства для упаковки очередного предмета. Высота слоя = тах(Ъ¡), а высота первого частичного слоя В/ вычисляется

по формуле НЬ1=тт(И¡), Т, еБ,. Если Р„ =0, то упаковка слоя на этом заканчивается, в противном случае осуществляется переход к упаковке основания к-то частичного слоя. Открывается следующий частичный слой Вк. Его заполнение сводится к двухмерной упаковке прямоугольников, представляющих собой нижние грани еще не упакованных параллелепипедов Г, еРп, в прямоугольник, представляющий собой верхнюю грань самого низкого предмета ГЛга,„ частичного слоя Вк/ с размерами ¿ь При этом

выбор предметов Tt для упаковки осуществляется исходя из следующих условий:

hi + НЬ,+... +НЬк < = Hss; (2)

<= Lh w,<= Wk. (3)

Частичный слой Вк закрывается. Высота Вк вычисляется по формуле

НЬк = min (hr(Hb,+...+Hbk.i)), T,eB,,i=l,...,m; k=l,...s. Структурограмма из основных процедур метода МСА приведена на рис. 7.

Алгоритм МСА Входные данные: /„ w„ h„ i=l,..., т - размеры предметов; L. IV— размеры основания параллелепипеда

Процедура1. Упаковка 1-го частичного слоя Hss = max(hi), T.eSJIb^minfb), Т>еВ,

Процедура 2. Упаковка k-го частичного слоя НЪк = min (hr(Hb,+...+Hbk.,) Л TteBk

Процедура 3. Формирование слоя: если Р„ #0, то повторить процедуру 2 для нового слоя Вк+1 Проверка условия завершения слоя: упаковка слоя Ss заканчивается, когда все предметы упакованы, либо когда ни один предмет в рамках слоя уже не может быть упакован.

Рис. 7 - Структурограмма предлагаемого алгоритма МСА

Метод на основе бесслойного алгоритма (БСА). Разработанный метод МСА обобщен на случай, когда снимаются ограничения на высоту слоя Hs, (см. условие 2). Для того чтобы в качестве основания для упаковки частичного слоя всегда принимался прямоугольник максимально возможной площади, разработан алгоритм, в котором вместо объединения доступных областей при поиске основания частичного слоя используется отсечение занятых участков. Пример работы алгоритма представлен на рис. 8, который демонстрирует эффективность применения алгоритма отсечения для поиска основания частичного слоя.

На рис. 8,а в качестве основания частичного слоя используются только верхние грани упакованных параллелепипедов. Высота упаковки равна 260 ед.

На рис. 8,6 представлен результат упаковки с использованием алгоритма отсечения для поиска основания частичного слоя. Высота упаковки равна 200 ед.

Метод на основе модифицированного бесслойного алгоритма (МБА). В этом методе для каждого частичного слоя рассматривалось два варианта упаковки: полученный методом динамического перебора и его симметричное отображение относительно центра основания частичного слоя.

Рис. 8 — Иллюстрация работы предлагаемого алгоритма БСА

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

Рис. 9 — Схема унифицированного метода решения задач упаковки

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

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

Разработан конструктивный метод для решения задач I.5DBP, 2DBP на базе метаэвристики муравьиной колонии. Основная идея алгоритма муравьиной колонии состоит в том, что на каждой итерации конечное число агентов — искусственных муравьев — строят допустимые решения задачи. Каждый агент строит решение, начиная с некоторого начального частично построенного решения, и на каждом шаге добавляет к нему компоненты решения, руководствуясь некоторым вероятностным правилом. Компоненты решения характеризуются уровнем феромона (численная характеристика компонента, показывающая, насколько часто данный компонент входил в лучшие решения на предыдущих итерациях алгоритма) и эвристической информацией, характерной для решаемой задачи. Известны различные алгоритмы муравьиной колонии, лучшими из которых при решении ряда задач комбинаторной оптимизации признаны алгоритмы Ant Colony System (ACS) и Max-Min Ant System (MMAS).

Разработан алгоритм решения задач прямоугольной упаковки (Ant Colony Packing, АСР) на базе метаэвристики муравьиной колонии. При этом компонентом в алгоритме АСР является заданный прямоугольник с шириной w и длиной /, а феромон (т0) наносится на последовательности из двух прямоугольников (ij), i,j=l,2.....т (т — заданное количество прямоугольников). Эвристическая информация для последовательности прямоугольников (ij), где i - последний компонент, добавленный некоторым агентом в свое решение, а у — один из компонентов-кандидатов на добавление в решение, определяется как площадь прямоугольника j: r/j = Wj • Ij ■

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

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

На примере рис. 10 показан результат работы гибридного алгоритма, в котором три агента строят решения задачи 1.5DBP. Размеры прямоугольников заданы в табл. 1, ширина полосы W=5. Лучшее решение получено третьим агентом. При этом длина занятой части полосы лучшей упаковки £,hesl = 9. В табл. 2 показаны кортежи, полученные с помощью алгоритма DSR.

Таблица 1 — Размеры исходных прямоугольников

/ 1 2 3 4 5 6 7

2 1 3 4 3 2 1

1, 5 5 3 2 2 2 I

Таблица 2 - Кортежи, полученные алгоритмом

1 I ............ 4 4

1 (?)

г г.«} Н>. ПЯ

...... {»л-

*

5 {Ч {». (7.2) ii.ll. {7,1}, {«.!) 1«}. {«.и, {1.51.17.5.1). (7.6.21 (З.ч, (5,1 к (УД2). (7,5,1}, (в,г,п. (7,л.гк i4.ii

ОПТИМАЛЬНАЯ УПАКОВКА

Л

Рис. 10 - Результаты работы предлагаемого алгоритма ЛСР-ОБК

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

Разработан конструктивный метод перебора с усечением (Sorting with Truncating, ST) для решения задачи одномерной упаковки 1DBP, в котором происходят направленные изменения частичного и построенного решения. Эти изменения основаны на переборе различных вариантов упаковки путем обмена предметов между контейнерами (разрешен обмен предмета из одного контейнера на один предмет из другого контейнера). Все множество вариантов обмена предметами сокращается за счет введения правил отсечения. Вводятся следующие понятия:

Резерв контейнера j, j=l,2,...,k (Container's Reserve, CRJ) — это разность между его размером и суммарной длиной предметов, входящих в этот контейнер. Если в упаковке есть хотя бы один контейнер с отрицательным резервом, то она является недопустимой (сумма длин предметов в каком-либо контейнере больше размера самого контейнера).

Резерв упаковки (Packing's Reserve, PR) - это сумма всех отрица-

к

тельных резервов контейнеров, входящих в упаковку, = гДе СЛ,,

¡•л

j=l,2,...,k~ резерв у'-го контейнера.

Разработанный метод ST состоит из трех основных процедур:

1. Процедуры построения начального варианта упаковки. Создается недопустимая упаковка (сумма весов предметов в контейнере превышает его длину), в которой количество контейнеров равно нижней границе No, полученной с помощью задачи линейного программирования.

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

Правила отсечения заключаются в следующем: рассматриваются только те варианты обмена предметов между контейнерами, в которых присутствовал хотя бы один контейнер с резервом CRj < 0; не рассматриваются варианты обмена, в которых вес предмета из контейнера с отрицательным резервом меньше веса предмета из другого контейнера; контейнеры в упаковке упорядочиваются в зависимости от их резерва: сначала контейнеры с неотрицательным резервом по возрастанию, затем контейнеры с отрицательным резервом по убыванию; предметы в контейнере упорядочиваются по убыванию их веса. Если вес предмета it из контейнера ji с отрицательным резервом больше веса предмета ь из другого контейнера j\ и резерв контейнера j2 после такого обмена стал отрицательным, а резерв - положительным, то нет необходимости рассматривать варианты обмена предмета // и предметов, которые находятся справа от предмета ¡2 в контейнере j2.

Для каждого варианта обмена вычисляется изменение резерва упаковки и выбирается вариант с наибольшим изменением резерва. При этом вводится параметр р - вероятность рассмотрения варианта обмена, ре [0,1]. Для каждого варианта обмена генерируется псевдослучайная величи-

нар*, равномерно распределенная на [0,1]. Если р* превышает р, то вариант обмена отсекается, иначе — вариант выбирается. С помощью выбранного варианта обмена создается новая упаковка, которая проверяется на допустимость.

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

Разработан эффективный метод SA-CP (Simulated Annealing Cutting Packing) на базе основных процедур метаэвристики имитация отжига для решения задач прямоугольного гильотинного раскроя.

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

Для оценки эффективности разработанного математического обеспечения на основе известной методики Г. Вешера была проведена серия численных экспериментов. Кроме того, представлены результаты экспериментальных исследований разработанных алгоритмов для задач электронной библиотеки OR-library, размещенной на сайте http://mscmga.ms.ic.ac.uk/info.html.

Серия №1. Для определения лучших параметров алгоритмов перебора с усечением ST и динамического перебора DSR при решении задачи одномерной упаковки (1DBP) проводился эксперимент, при котором достигалось бы хорошее поведение этих алгоритмов на большинстве задач. В качестве параметров алгоритмов DSR и ST выбраны: р — вероятность включения кортежей в подмножество кортежей /Г для DSR и вероятность выбора варианта из множества вариантов обмена предметов между контейнерами для ST; к — число запусков алгоритма. Использовались 8 тестовых наборов библиотеки OR-library, в каждом наборе было сгенерировано 20 задач:

• тест № 1—№ 4 (1К=150; ет=120, 250,500,1000; веса предметов распределены в интервале [20,100]);

• тест № 5-№ 8 (№'=1000; т=60,120, 249,501; веса предметов распределены в интервале [200,500]). Эти тесты названы «триплетами» (в каждый контейнер можно поместить ровно по три предмета), которые считаются особенно трудными при поиске эффективных решений.

Выбирались следующие значения параметров: £=10, 100, 1000; р=0.05, 0.25. 0.5, 0.75, 1.00. На рис. 11 на диаграммах а) — г) представлены (для тестов № 4 и № 6) средние для 20 задач отклонения г* полученных алгоритмами DSR и ST решений от нижней границы NLP, определенной с помощью решения задачи линейного программирования, округленного до целого сверху. На основе результатов проведенного эксперимента сделан следующий вывод. Лучшие параметры для алгоритма ST: ¿=1000 для всех тестов № 1-№ 8, ре [0.5, 1 ] для тестов № 1— № 4 и р= 1, для тестов № 5-№

8. Лучшие параметры для алгоритма ОБЯ: р=0.15, ¿=10 для тестов № 1— №4,/т=1, £=10 для тестов № 5 — № 8.

0.05 0,25 0.5 0.75 1

параметр р

Рис. 11 — Результаты численного эксперимента для задачи ЮВР: а — метод БТ для теста № 4; б — метод ОБЯ для теста № 4; в — метод 57" для теста № 7; г — метод £>£/? для теста № 7

Серия №2. При решении задачи ЮВР также проводилось сравнение эффективности работы алгоритма динамического перебора ИБП, алгоритма перебора с усечением БТ и генетического алгоритма НОСА (идея Э. Фол-кенауэра) на тестах № 5 — № 8 с лучшими значениями параметров. На диаграмме рис. 12 представлены значения средних отклонений , полученных алгоритмами ОБЛ, НйСА и БТ решений от нижней границы N¿/>, определенной с помощью решения задачи линейного программирования и округленного до целого сверху. Для экспериментального исследования задачи ЮВР использовалась методика генерации тестовых наборов, предложенная Г. Вешером. Параметрами задачи ЮВР являются: т - размерность задачи (количество предметов); (V— длина контейнера; V/—нижняя граница для весов предметов в отношении к длине контейнера, т.е. ео,> V, IV.

1=1,2,...,т\ у2 — верхняя граница для весов предметов в отношении к длине контейнера, т.е. т,< IV, 1~1,2,...,т.

Рис. 12 - Результаты эксперимента с ВПК, 5Т, 1ЮСА

Для эксперимента использовались тестовые наборы: «малые предметы», «средние предметы» и «малые и большие предметы». Проводилось сравнение алгоритмов ОБК, БТ и 1ЮСА. На рис. 1 За,б на диаграммах приведен результат эксперимента для трудного класса задач «средние предметы» с параметрами: 0.15,0.3; у2=0.4, 0.6; Ж=1000; т=200.

Рис. 13 - Результаты эксперимента по методике Г. Вешера (1DBP): a— W = 1000, т = 200, v,= 0.15; б - W = 1000, т = 200, V/= 0.3

Серия №3. Целью эксперимента при решении задачи прямоугольной упаковки 1.5DBP являлось сравнение алгоритма динамического перебора DSR, генетического классического алгоритма с блочным декодером GCA&BD и генетического классического алгоритма с улучшенным декодером «нижний-левый» GCA&JBL. Применялась методика Г. Вешера, пролонгированная для задач прямоугольной упаковки. Параметрами задачи 1.5DBP являются: т~ количество прямоугольников; W — ширина полубесконечной полосы; v¡, v2 — нижняя и верхняя граница для ширины прямо-

угольников по отношению к ширине полосы, соответственно; со1, а>2~ нижняя и верхняя граница для длины прямоугольников по отношению к ширине полосы, соответственно. Были сгенерированы следующие классы задач: «малые предметы» (МП) (»^=0.05; у2=0.1; со /=0.1; со 2=0.15), «средние предметы» (СП) (и/=0.25; 1^=0.35; а>/=0.35; ш2=0.45) и «малые и большие предметы» (МБП) (у/=0.25; 1^=0.05; а>;=0.05; со2= 0.95). Для каждого класса было просчитано 50 примеров, количество запусков £=10, р=0.6, р — вероятность включения кортежа во множество кортежей 1С. Результаты экспериментов приведены на рис. 14а — в. Критерием оценки этих алгоритмов выступал коэффициент раскроя (КРА) — процентное отношение суммарной площади всех заданных прямоугольников к площади затраченного материала.

Рис. 14 - Результаты эксперимента по методике Г. Вешера (1.50ВР): а —«средние предметы» й^=255; Уу=0.25; 1^=0.35; со /=0.35,' су г=0.45; б-«малые предметы» РГ=255; 1^=0.05; Уг=0.1; со /=0.1; со2=0.15; «-«малые и большие предметы» 1У=255; У/=0.25; 1^=0.05; со /=0.05; а>2=0.95; г — метод /357? для решения задач большой размерности

Серия №4. Целью эксперимента при решении задачи прямоугольной упаковки ¡.ЗИВР являлось выяснения качества работы алгоритма ОБЯ на задачах большой размерности (Ж=1000, тл=Ю0, 250, 500, 750, 1000). Для этого использовались наборы «малые предметы», «средние предметы» и «малые и большие предметы». Результаты экспериментов приведены на рис. 14 г.

Серия №5. Для исследования алгоритма муравьиной колонии АСР решалась задача 2ВВР на тестовых задачах из библиотеки ОЯ-ИЬгагу, При этом размеры листа во всех задачах равны 100x100. Для каждой задачи 2ВВР размерности от=40, 50, 100, 150, 250, 500, 1000 было сгенерировано по 10 примеров. При генерации использовались различные диапазоны размеров прямоугольников (рассматривались 4 класса: «широкие прямоугольники», «длинные прямоугольники», «большие прямоугольники»). Размер прямоугольника из заданного класса определялся как реализация двух случайных величин с равномерным распределением в заданном диапазоне. Было сгенерировано три типа задач: тип 1 - 20% прямоугольников классов 1-3, 40% прямоугольников класса 4; тип 2 — 15% прямоугольников классов 1-3, 55% прямоугольников класса 4; тип 3 - 10% прямоугольников классов 1—3, 70% прямоугольников класса 4. Результаты сравнивались с нижней границей (НГ), полученной С. Фекет и др. В алгоритме АСР использовались следующие параметры: число агентов составило 30; минимальный уровень феромона на шаге Го=0.01; минимальное значение феромона Ттшп=о.1; максимальное значение феромона гтах=Ю; а=1, /Ь2, (а, /? -управляющие параметры алгоритма); вероятность нанесения феромона на лучшие решения рф=0.5; коэффициент локального испарения феромона £=0.01; коэффициент испарения феромона р= 0.5; начальное значение феромона хыи=0Л. На рис. 15 показан срез экспериментов для задач третьего типа, где алгоритм АСР показал лучшие результаты.

Рис. 15 - Сравнение результатов работы АСР на тестовых наборах

из ОЯ-ИЬгагу

Серия №б. Исследовался алгоритм БА-СР на базе процедур имитации отжига для решения задачи гильотинного прямоугольного раскроя РЗИСЗ.

Для анализа алгоритма был проведен численный эксперимент на тестовых наборах: «большие прямоугольники» (от =60-1000, w,e [0.45И7, 0.5 W\, /,е [0.45И', 0.55Щ), «узкие и длинные прямоугольники» (т =60-1000, w,6 [0.02W, 0.1 W\, /,е [0.4W, 0.5if]), «мелкие прямоугольники» (т=60 -1000, w,e[0.02PF, 0ЛЩ, /,е[0.02Ж, 0.1№"]), «триплеты» (w =60-1000, w.efOJW, 0.35W], l¡e[03W, 0.35W\). При решении задачи гильотинного раскроя полосы лучшие результаты были получены на классах «большие предметы», «мелкие предметы» и «триплеты» (КРА от 90 до 97%).

Серия №7. Выполнены численные эксперименты для анализа методов решения задач параллелспипедной упаковки 3DBP, параметры которой: длина основания параллелепипеда ¿=150; ширина основания параллелепипеда W=100; количество предметов ти=10; 20; 30; 40; 60; 80; нижнее ограничение длины предметов v, = 0.25; верхнее ограничение длины

предметов v2 = 0.4; 0.6; 0.8 (/, >v¡L, I, <v3L , i=l.....m); нижнее ограничение

ширины предметов co¡ — 0.25; верхнее ограничение ширины предметов а>2 = 0.4; 0.6 (w¡>co¡L, w, <oj2L , i=l.....m); нижнее ограничение высоты предметов г/, = 0.2; верхнее ограничение высоты предметов r¡2 = 0.25; 0.6 (h¡ > r¡,L, /, <7j2L , i~J.....m). Для каждого из этих классов было отобрано по 10 тестовых примеров: мелкие предметы (v, = co¡ = 0,1; r¡, = 0,2 и r¡2 ~ 0,25); средние предметы (i// = со, — 0,2; r¡¡ = 0,2 и r¡2 = 0,25); разнородные предметы (v, = со, = 0,1; r¡, = 0,2 и r¡2 = 0,25). Для каждого класса задач было сгенерировано по 10 тестовых примеров. В тестировании принимали участие алгоритмы: сnfd (слойный алгоритм на базе алгоритма «следующий подходящий с упорядочиванием», Г. Шайтхауэр), СЛ (слойный алгоритм), МСА (модифицированный слойный алгоритм), БСА (бесслойный алгоритм), МБА (модифицированный бесслойный алгоритм), SABD (метод случайных перестановок), GABD (классический генетический алгоритм), EABD («наивный» эволюционный алгоритм (1+1)-.Е/1). Оценка эффективности алгоритмов оценивалась по КРА. На рис. 16 на диаграмме приведены результаты тестируемых алгоритмов (поскольку алгоритмы С nfd • CVÍ, МСА, БСА уступали другим тестируемым алгоритмам, они не были включены в диаграмму).

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

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

1. Для задачи одномерной упаковки на рассматриваемых тестовых наборах из библиотеки тестовых задач ОЛ-ИЬгагу при проведении эксперимента для тестовых наборов «средние предметы» алгоритмы 5Т и НС С А решили оптимально практически все задачи, алгоритм ВБЯ решил оптимально 64% задач. Для тестовых наборов «триплеты» алгоритм БТ решает оптимально практически все задачи, алгоритм £>57? — 68% задач, НСйА решил оптимально только две задачи из 80.

2. Для задачи прямоугольной упаковки в полосу результаты эксперимента показали, что на наборах «средние предметы» коэффициент раскроя КРА, полученный методом £>57?, составил КРА от 98% до 99% и превышает коэффициент раскроя сравниваемых методов на 6-16%; на наборах «малые предметы» результаты ОБЯ. (КРА от 92% до 96%) также превышают КРА сравниваемых методов на 4-14%; на наборах «малые и большие предметы» метод ИЗЯ (КРА от 92% до 94%) уступает алгоритму ССА&ВО примерно на 1%. Для тестовых примеров большой размерности лучшие результаты алгоритмом £>57? были получены в классе «средние предметы», при этом КРА составил от 95.58% до 99.58%.

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

¿¿(%) - ^ д х 100% решений Ы, полученных алгоритмом АСР для трех ти-ш

пов тестовых задач от нижней границы Л , составляют: для задач первого типа /¿=2.88 %; для задач второго типа /¿=2.33 %; для задач третьего типа ц=1.59%. Алгоритм АСР показал лучшие результаты для задач второго и третьего типа. При увеличении количества итераций наблюдались улучшения решений для АСР, однако время решения индивидуальной задачи заметно увеличивалось (в 1000 раз по сравнению с другими методами).

4. При тестировании алгоритмов параллелепипедной упаковки в классах «мелкие» и «разнородные предметы» лучшие результаты показали МБА, С А ВО и ЕАВО соответственно. Классы с «мелкими предметами» наиболее эффективно были решены алгоритмами МБА, С А ВО. В классах, где имелись предметы со «средними» и «разнородными предметами», лучшим был алгоритм МБА (КРА - от 75% до 90%.), а в классе «мелкие предметы» — алгоритм ОЛВО.

Предложенные методы и алгоритмы для решения задачи ортогональной и-мерной упаковки ВРР (л=1,2,3) инвариантны к технологическим ограничениям, возникающим в единичном производстве. Предложенные методы решения задачи одномерной упаковки применялись при решении задачи «Использование отходов по цехам» (ГУП УАП «Гидравлика»), что позволяет обеспечить экономию материалов и сокращение сроков при проектировании планов упаковки деталей в составе автоматизированного рабочего места технолога планово-заготовительного производства. Предложенные методы решения задачи параллелепипедной упаковки применя-

лись при упаковке железнодорожных платформ и вагонов разногабаритными ящиками (ООО «Уралтехнопроект»), а также при размещении ящиков с медикаментами и изделиями медицинского назначения на фармацевтическом складе (ООО «ВИВ-ФАРМ»).

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

1. Поставлена и решена проблема разработки методологической основы нового направления унификации поиска решений задач ортогональной упаковки на основе применения модифицированного псевдополиномиального алгоритма решения задачи 0-1 рюкзак, что позволяет решать задачу и-мерной упаковки (п ~ 1,2,3) в рамках единого метода.

2. Разработан высокоэффективный конструктивный метод динамического перебора для решения задач одномерной и прямоугольной упаковки в детерминированном и рандомизированном вариантах, основанный на декомпозиции задачи на множество задач 0-1 рюкзак. Этот метод послужил основой унификации решения задач ортогональной упаковки. Данный метод для задачи одномерной упаковки показывает лучшие результаты в трудном классе задач «средние предметы» по сравнению с другими методами. При решении задач прямоугольной упаковки по сравнению с классическими генетическими алгоритмами рандомизированный метод динамического перебора превосходит их на классах "средние предметы" и "малые предметы" (коэффициент раскроя от 96.4% до 99.4%). Для очень трудных задач (триплетов) прямоугольной упаковки коэффициент раскроя предлагаемого метода составляет от 96.54% до 100%. Разработанные алгоритмы на основе этого метода позволяют сократить отходы материала в 2-3 раза. Показана эффективность применения метода динамического перебора для решения задачи упаковки параллелепипедов. Разработанные методы па-раллелепипедной упаковки на базе метода динамического перебора по сравнению с эволюционными алгоритмами позволяют улучшить коэффициент раскроя, а, следовательно, и коэффициент использования материала в классах «средние предметы» и «разнородные предметы» (до 5-15%). Кроме того, метод динамического перебора позволяет получать множество квазиоптимальных решений исходной задачи, что позволяет в случае необходимости выбирать лучшее приемлемое решение с учетом технологических ограничений.

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

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

4. Разработан эффективный метод решения задач прямоугольной упаковки на базе конструктивной метаэвристики муравьиной колонии, успешно применяемой для решения задач комбинаторной оптимизации. Как показал численный эксперимент, проведенный на тестовых примерах из электронной библиотеки тестов для решения трудных задач комбинаторной оптимизации, отклонение решений от нижней границы составило в среднем 2,23%. Однако этот метод требует больших затрат времени и поэтому значительно уступает методу динамического перебора. Разработаны эвристические алгоритмы с применением процедур метаэвристики имитация отжига для решения задач гильотинного прямоугольного раскроя, что позволяет получить рациональные решения для раскроя промышленных материалов в условиях единичного производства. Лучшие результаты по сравнению с тестируемыми методами, были получены в классах «большие предметы», «мелкие предметы», «триплеты» (КРА от 90.93% до 98.08%).

5. Предложенные в работе теоретические положения для решения задач упаковки и раскроя промышленных объектов в условиях единичного производства реализованы в виде методик, алгоритмов и прикладного программного обеспечения в среде программирования Borland Delphi 3.0. Разработанное программное обеспечение имеет развитый интерфейс и может использоваться как автономно, так и в составе комплексов программ упаковки и раскроя. Результаты диссертационной работы приняты к внедрению в виде алгоритмов, методик и программного обеспечения на ООО «Уралтехнопроект» (г. Екатеринбург), ООО «ВИВ-ФАРМ» (г. Москва), ГУП УАП «Гидравлика» (г. Уфа). Полученные в работе результаты используются в Уфимском государственном авиационном техническом университете в учебном процессе при выполнении курсовых и дипломных работ, в исследованиях аспирантов, а также отражены в учебном пособии, рекомендованном УМО по образованию в области экономики, статистики, информационных систем и математических методов.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Монография:

1. Моделирование прямоугольной упаковки на базе метода динамического перебора и метаэвристики муравьиной колонии. Глава 3 А.Ф. Ванеева // Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума / Под общ. ред. Э.А. Му-хачевой, М. : МАИ, 2004. С. 76-144.

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

2. Локальный поиск в задачах оптимального распределения двухмерного ресурса. Глава 3 Валеева А.Ф. // Методы локального поиска в задачах оптимального распределения ресурса. Учебн. пособие / Э.А. Мухачева,

А.Ф. Валеева, A.C. Мухачева (Рекомендовано УМО по образованию в области экономики, статистики, информационных систем и математических методов в экономике) Уфа : УГАТУ, 2001. С. 75-81; 85-87; 93-102.

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

3. Метод динамического перебора в задаче двумерной упаковки / Э.А. Мухачева, А.Ф. Валеева // Информационные технологии. 2000. № 5. С. 3037 (автору принадлежит 4 ж. стр.).

4. Методы решения задачи параллелепипедной упаковки на базе алгоритма динамического перебора / Э.А. Мухачева, А.Ф. Валеева, И.Е. Тоцков //Информационные технологии. 2001. №1. С. 21-29 (автору принадлежит 3 ж. стр.).

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

6. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур / Э.А. Мухачева, А.Ф. Валеева, В.М. Картак, A.C. Мухачева // Информационные технологии. Приложение. 2004. №5.-31 с (автору принадлежит 7,75 ж. стр.).

7. Методы частичного перебора локального поиска оптимума в задаче двумерной упаковке / А.Ф. Валеева // Информационные технологии. 2004. № 1. С. 36-43 (автору принадлежит 8 ж. стр.).

8. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки / А.Ф. Валеева //Информационные технологии. 2005. №10. С. 36-43 (автору принадлежит 8 ж. стр.).

9. Задача двумерной контейнерной упаковки: нижние границы и численный эксперимент с алгоритмами локального поиска оптимума / Э.А. Мухачева, А.Ф. Валеева, A.C. Филиппова, С.Ю. Поляковский И Информационные технологии. 2006. № 4. С. 45—52 (автору принадлежит 2 ж. стр.).

10.Конструктивная эвристика для задачи прямоугольной упаковки / А.Ф. Валеева // Вестн. Башк. ун-та. 2006. № 3. С. 5-6 (автору принадлежит 2 ж. стр.).

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

11. Математическое обеспечение интеллектуальной системы поддержки решений в задачах плотной упаковки / Э.А. Мухачева, А.Ф. Валеева, Л.Ф. Розанова,Т.Д. Тарасова /Деп. в ВИНИТИ 06.06.95, № 1665.-Юс.

12. Алгоритмы решения задачи плотной упаковки геометрических объектов / А.Ф. Валеева, Р.З. Мухаметзянов, С.К. Тихомиров, Ж.Л. Юлдыбае-ва // Принятие решений в условиях неопределенности: межвуз. научи, сб. Уфа : УГАТУ, 1996. С. 23-28.

13. Алгоритм построения прямоугольной упаковки и применение его к задаче фигурного раскроя / А.Ф. Валеева // Труды международной конфе-

ренции по прикладной и индустриальной математике, Новосибирск, ИМ СО РАН. 1997. С.47-57.

14. Методы решения задачи прямоугольной упаковки / Л.Ф. Валеева, И.Е. Тоцков, И.Р. Гареев // Интеллектуальное управление в сложных системах— 99: Тр. респ. науч.-техн. конф. Уфа. 1999. С.36-38.

15. Метод динамического перебора для решения задачи одномерной упаковки / А.Ф. Валеева, И.Р. Гареев, В.А. Габитов // Моделирование, вычисления, проектирование в условиях неопределенности 2000: Тр. между-нар. науч. конф. Уфа. 2000. С. 369-373.

16. Задача одномерной упаковки: вычислительный эксперимент с методом динамического перебора / А.Ф. Валеева, И.Р. Гареев // Принятие решений в условиях неопределенности: межвуз. науч. сб. Уфа : УГАТУ, 2000. С. 74-79.

17. Программа плотной упаковки прямоугольных объектов. / С.С. Валеев, А.Ф. Валеева Свидетельство об официальной регистрации программы для ЭВМ, № 940280 от 11.07.1994. РосАПО.

18. Оптимальное планирование работ в вычислительных системах реального времени / С.С. Валеев, А.Ф. Валеева, Чуен Лин. // Международное научное издание «Интеллектуальные автономные системы»: УГАТУ. Уфа. Карлсруе. 1996. С.135-139.

19. Метод динамического перебора и применение нейросетей для задачи рационального использования ресурса. / С.С. Валеев, А.Ф. Валеева // Международное научное издание «Проблемы принятия решений в условиях неопределенности». Уфа. 1997. С. 188-198 (на англ. языке).

20. Решение задачи трехмерной упаковки / А.Ф. Валеева, И.Е. Тоцков // Комплексный анализ, дифференциальные уравнения, численные методы и приложения. Геометрические задачи. Уфа: ИМВЦ УИЦ РАН. 1996. С. 30-36.

21. Метод отсечения для решения задачи трехмерной упаковки / И.Е. Тоцков, А.Ф. Валеева // Межвузовский научный сборник «Принятие решений в условиях неопределенности». Уфа. 1999. С.112-118.

22. Разработка методов трехмерной упаковки Международное научное издание / А.Ф. Валеева, И.Е. Тоцков // «Проблемы принятия решений в условиях неопределенности». Уфа. 1997. С. 198-206 (на англ. языке).

23. Получение множества квазиоптимальных решений в задаче рационального использования ресурса / А.Ф. Валеева, С.С. Валеев // Труды межд.конферен. «Поддержка жизненного цикла в производственных системах». 1998. С.125-127 (на англ. языке).

24. Стохастические методы локального поиска для задач упаковки / А.Ф. Валеева // Труды международной конференции «Моделирование, вычисления, проектирование в условиях неопределенности-2000». УГАТУ. 2000. С.25-31.

25. Метод динамического перебора для решения задач упаковки / А.Ф. Валеева И Материалы конференции «Ресурсосберегающие техноло-гии:математическое обеспечение оптимизационных задач в системах авто-

матизированного проектирования» (ОПТИМ—2001), Санкт-Петербург. 2001. С.29-32.

26. Алгоритм муравьиной колонии для задачи двухмерной упаковки: численный эксперимент / А.Ф. Валеева, М.Н. Аглиуллин // Труды межд. конф. «Компьютерные науки и информационные технологии». Уфа. 2003. С. 110-114 (на англ.языке).

27. Решение задач прямоугольной упаковки на базе ее блочной структуры / Э.А. Мухачева, А.Ф. Валеева, A.C. Мухачева // Труды межд. конф. «Компьютерные науки и информационные технологии». Уфа. 2000. С. 43—51 (на англ. языке).

28. Классы нижних границ для задач двухмерной упаковки / A.C. Валеева, С.Ю. Поляковский // Труды межд. конф. «Компьютерные науки и информационные технологии». Уфа. 2005. С. 152-158 (на англ. языке).

29. Применение алгоритмов локального поиска оптимума для проектирования СБИС / А.З. Хуббутдинов, М.Н. Аглиуллин, А.Ф. Валеева, Ю.В. Никитин // Труды межд. конф. «Компьютерные науки и информационные технологии». Уфа. 2005. С. 175-180 (на англ. языке).

30. Моделирование прямоугольной упаковки на базе метаэвристики муравьиной колонии / А.Ф. Валеева, М.Н. Аглиуллин // Межвузовский научный сборник «Принятие решений в условиях неопределенности». Вып. 2. Уфа. 2005. С. 55-63.

31. Алгоритмы муравьиной колонии для задач двухмерной упаковки: результаты численного эксперимента / А.Ф. Валеева, М.Н. Аглиуллин // Труды 13-й Байкальской международной школы-семинара. Математическое программирование. Том 1.2005. С. 429-443.

32. Конструктивные эвристики в задачах раскроя—упаковки / А.Ф. Валеева // Труды «Международной уфимской зимней школы-конференции по математике и физике для студентов, аспирантов и молодых ученых». Т.1. Уфа. 2005. С. 109-119.

33. Программа решения задачи двухмерного прямоугольного раскроя материалов / С.Ю. Поляковский, А.Ф. Валеева и др. Свидетельство об официальной регистрации программы для ЭВМ № 2006612022 от 14.06.2006. М.

ВАЛЕЕВА Аида Фаритовна

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

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

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

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