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

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

ЕРМАЧЕНКО Александр Иванович

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

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

Автореферат

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

Уфа 2004

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

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

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

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

МУХАЧЕВА Элита Александровна

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

д-р физ.-мат. наук, проф. ЖИТНИКОВ Владимир Павлович канд. техн. наук, доц. ГРИГОРЧУК Татьяна Ивановна

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

Петрозаводский государственный университет

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

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

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

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

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

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

На данный момент для решения задач дискретной оптимизации наиболее активно используются генетические алгоритмы. Также широкое распространение получили метаэвристики «Поиск с запретами», «Имитация отжига» и «Муравьиной колонии».

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

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

Целью работы является разработка метода решения задач прямоугольного раскроя и упаковки на базе метаэвристики «Поиска с запретами».

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

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

2. Разработать процедуры декодеров и использовать их в составе метаэвристического алгоритма «Поиск с запретами»;

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

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

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

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

1. Обобщенная математическая модель для задач двумерного прямоугольного раскроя-упаковки.

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

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

4. Программная реализация разработанных методов в составе системы двумерного прямоугольного раскроя СЕТАМ1-СЦТ;

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

Научная новизна работы. Новыми в работе являются:

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

2. Разработан декодер последовательного конструирования для задачи прямоугольной упаковки. Новыми в алгоритме являются метод описания границы упаковки и процедура укладки прямоугольника. Разработанный декодер превосходит известный алгоритм «Нижний Левый». Найдены классы задач, на которых он превосходит также разработанный аспирантом кафедры А.В. Чиглинцевым «Блочный декодер». Показано, что разработанный алгоритм обладает свойством реставрации;

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

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

1. Метод . интегрирован в систему автоматизированного проектирования двумерного прямоугольного раскроя CETAMI-CUT. Имеются акты внедрения разработанных методов и программного обеспечения в учебный и производственный процесс. Программа CETAMI-CUT зарегестрирована в РОСПАТЕНТ, свидетельство № 2004611452;

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

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

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

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

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

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

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

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

5. Семинары группы изучения метаэвристических алгоритмов института математики СО РАН (Новосибирск, 2003);

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

Публикации. По теме диссертации опубликовано 11 работ: 7 статей, в том числе две в центральном журнале, 3 трудов конференций, выполненных по теме диссертации при непосредственном участии автора, и один акт о регистрации программы.

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

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

Содержание диссертации

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

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

Основными объектами исследования в данной работе являются задачи прямоугольной упаковки в полубесконечную полосу (1.5DBP), задачи прямоугольной упаковки в листы (2DBP) и задачи гильотинного раскроя полубесконечной полосы (1.5DCS) и листов (2DCS). Задачи гильотинного раскроя имеют дополнительное ограничение, согласно которому возможными являются только сквозные резы, параллельные кромкам материала.

Первоначально в работах Л.В. Канторовича и В.А. Залгаллера в 1951 г., и независимо P. Gilmoгy, R. Gomoгy в 1961г. задачи планирования гильотинного раскроя описывались моделью линейного программирования с

неявно заданной информацией. Дальнейшее развитие эта задача получила в 1983 г. в работах Э.А. Мухачевой, и в то же время J. Terno, R. Lindemam&G. Scheithauer в Германии. В моделях линейного программирования для генерации раскроев, вводимых в базис, используется динамическое программирование. Это направление, связанное с использованием непрерывной релаксации, пользовалось и продолжает пользоваться популярностью у многих ученых.

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

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

Основы метода поиска с запретами заложил Fred Glover в 1996 г. Метод состоит в управляемом локальном поиске в пространстве решений, для оптимизации которого используются списки запретов. Процесс описывается набором состояний и на каждом шаге производится переход из текущего состояния в одно из соседних. Совокупность всех соседних состояний называется окрестностью. Также важными составляющими метода поиска с запретами являются процедуры интенсификации и диверсификации поиска. Процедура интенсификации направлена на повышение интенсивности поиска в окрестности возможного локального оптимума. В свою очередь, диверсификация должна обеспечивать возможность выхода из области локального оптимума для осуществеления поиска в других областях.

Помимо особенностей реализации метаэвристического подхода для задачи двумерного прямоугольного раскроя и упаковки, важную роль играют способы выбора окрестности и оценки получаемых решений, а также выбор процедуры декодера, с помощью которой происходит конструирование упаковки. В работах А.С. Мухачевой, А.В. Чиглинцева, М.А. Смагина (2002 г.) показано влияние декодеров на эффективность упаковок, и приведены результаты экспериментов в рамках генетического алгоритма. Широкую известность на западе получил декодер «нижний-левый» (Improved Bottom Left, IBL), усовершенствованный D. Liu&H.Teng в 1999 г. Кроме того, в последние годы на востоке разработан ряд эффективных декодеров для задачи упаковки прямоугольников на полубесконечной плоскости, которые могут быть адаптированы для решения задач прямоугольного

раскроя полубесконечной полосы и листов. Одним из таких декодеров является декодер парных паследовательностей (Sequence Pair, SP), разработанный Toshihide Ibaraki, Shinji Imahori и Mutsunori Yaguira.

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

Во второй главе приводится обобщенная математическая модель задач прямоугольной упаковки в полубесконечную полосу (1.5DBP), упаковки на листы (2DBP), а также прямоугольного гильотинного раскроя полубесконечной полосы (1.5DCP) и листов (2DCP). Модель состоит из трех компонентов - модели исходной информации задачи раскроя, модели карты раскроя и постановки задачи с использованием первых двух составляющих и коэффициента раскроя в качестве целевой функции. Предложен новый алгоритм-декодер для прямоугольной упаковки со сложностью О(п), где п -количество заготовок.

Далее рассмотрим систему координат (OX, OY):

Y*

Рис. 1 - Карта раскроя и система координат Координаты прямоугольника - координаты его нижнего левого угла.

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

Ц- ширина полубесконечной полосы или листа; Ь - длина листа, для полубесконечной полосы Ь = со; т - количество типов прямоугольных предметов (прямоугольников, ПП);

- ширина прямоугольника типа

/ = (7/, ...,/„■•■,и, /, -длина прямоугольника типа I = 1,/и; Ь = (Ь\, ...,Ьи...,Ь„), Ь-, - количество прямоугольников типа / = 1,/и;

т

п = - общее количество прямоугольников;

7 - признак гильотинности; 7=1, если раскрой гильотинный; 7 = 0 в противном случае; •

£ - признак направления лрямоугольников; 6 = 1, если ПП можно поворачивать на 90°; е = 0 в противном случае.

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

Х-(х],...,х......х

У=(уь ...,уь __

х, и у, - координаты прямоугольника / по осям ОХ и ОУ, ¡' = 1, п;

Я = (¡1......... где я, - номер листа, в который упакован прямоугольник

/ = 1, п;

в случае раскроя полубесконечной полосы 0;

Набор Д = <Х, ¥, Б, А> называется допустимым прямоугольным раскроем, если выполняются следующие условия:

V ребра предметов параллельны ребрам полосы или листа Шх = ',)* (¡у = п.)) V ((¡х =*>.) л (1у = I.)), / = йт, где 1Х, I, - проекции заготовки I

на оси координат ОХ и ОУ.

2" Взаимное непересечение деталей

для раскроя полубесконечной полосы:

(л, > х1 + /,)у (х1 > х, + /,) или (>>, >у; >у,

для раскроя листов:

V , J> \\ 1 J у V J г ;} Jl \SJ ,//>

3" Непересечение деталей с гранями полосы для раскроя полубесконечной полосы: V/ = 1,...,л: (х. £ 0) л (у. >0)л (у. + < IV);

для раскроя листов: V/ = 1,...,«:(*. > 0) л (у, > 0) л (у. + <№г)л(х. +/. <£)

Набор Я = <Х, У, Б, А> называется гильотинным прямоугольным раскроем, если выполняются условия Г, 2" и 3", а также:

К = <Х, Г, 5, А>, где

(2)

А = (а,, ..., а,.....а„), а, -

1, если прямоугольник ¿повернут на 90° 0, иначе

4* Условие гшьотинности (Карта раскроя должна быть реализуема сквозными резами, параллельными кромкам материала). Логическая запись данного условия приведена в тексте диссертации.

Примечание: условия Г, 2\ 3* и 4° приведены для случая а, - О, i= 1,..../!. Если а, = 1, следует заменить w, на w/ = А, и А, на И,' = w,.

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

Задача 1.5DBP. Прямоугольный раскрой полубесконечной полосы.

Дано: Задача раскроя <W; L; т; w; I; b; у е>, L = те, у = 0; Найти: Допустимый раскрой R = <Х, Y, S, А>, удовлетворяющий условиям Г, 2' и 3", для которого длина занятой части полосы

Л = гпах(х( + /() достигает минимума.

Задача 2DBP. Прямоугольный раскрой листов.

Дано: Задача раскроя <W; L; т; w; I; b; у, е>, 7 = 0;

Найти: Допустимый раскрой R = <Х, Y, S, А>, удовлетворяющий условиям Г, 2' и 3', для которого количество израсходованных листов N = rnax(i,) достигает минимума.

Задача 1.5DCP. Гильотинный раскрой полубесконечной полосы.

Дано: Задача раскроя <W; L; т; w; I; b; у, О, L = <», 7= 1; Найти: Гильотинный раскрой R = <Х, Y, S, А>, удовлетворяющий условиям 1", 2", 3" и 4", для которого длина занятой части полосы

Л = +/,) достигает минимума.

Задача 2DCP. Гильотинный раскрой листов.

Дано: Задача раскроя <fV; L; т; w; /; b; у, е>, 7 = /;

Найти: Гильотинный раскрой R = <Х, Y, S, А>, удовлетворяющий условиям Г, 2', 3' и 4", для которого количество израсходованных листов N = max(s,) достигает минимума.

л

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

A = L*(N-\)+ max (*,+/,)

I \s,-N)

Декодер последовательного конструирования. Для задачи прямоугольной упаковки в полосу и в листы разработан декодер последовательного конструирования (Consequtive Designing, CD). Алгоритм декодирования основан на использовании специальных структур данных, позволяющих эффективно отслеживать крайний контур упаковки в

направлении построения (для полубесконечной полосы в нашей системе координат- правая граница упаковки).

Рис. 2 - Построение упаковки декодером CD

Общая схема работы алгоритма:

1. Инициализация алгоритма. Создание первоначального контура упаковки.

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

3. Укладка предмета, изменение контура упаковки.

4. Пока не достигнут конец приоритетного списка, переход к шагу 2.

Особенность данного алгоритма - представление правого контура упаковки списком точек, имеющих следующие параметры:

Ур - координата по оси OY для укладки прямоугольника.

Х/р - координата по оси ОХ для укладки прямоугольника.

dirp - признак расположения точки. Принимает значения 1 и -1.

Хгр - длина ограничивающей линии, которая начинается в точкер и

расположена снизу от нее, если и сверху, если

На рисунке отмечены ур, Xip И Хгр для точки 2 (р = 2). dir2 ~ 1.

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

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

2) Минимизация координаты X.

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

4) Минимизация расстояния до граней полосы.

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

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

Для описания решения используется приоритетный список Р длины т, состоящий из номеров заготовок. При этом, если заготовка /с[1,т] повернута на 90°, ее номер в списке Р будет отрицательным (-/). Получение карты раскроя из приоритетного списка осуществляется с использованием различных процедур декодеров, в том числе и разработанного в данной работе.

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

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

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

В случае раскроя листового материала (N - количество израсходованных листов)-

КРА = £(«< */,) /(Л *Н), где Л = I ♦(// -1) + шах (х, + /,)

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

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

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

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

Также в третьей главе описывается реализация предложенных методов и их интеграция в систему двумерного прямоугольного раскроя СЕТАМ1-СиТ. В составе системы метод был внедрен в производство.

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

1. Рекурсивный декодер для гильотинного раскроя.

2. Декодер поиска пустых корзин для гильотинного раскроя.

3. Блочный декодер для прямоугольной упаковки.

4. Декодер «Усоверш. нижний левый» для прямоугольной упаковки.

5. Декодер последовательного го конструирования для прямоугольной упаковки.

Проведены следующие эксперименты:

1. Выбор числа шагов до смены типа вторичной оценки. Для этой цели были случайно сгенерированы 120 задач четырех разлдичных классов. Было рассмотрено 6 возможных значений параметра от я/2 ДО 10л. В результате определено рекомендуемое значение числа шагов -

2. Исследование эффективности разработанного алгоритма на безотходных примерах Евы Хоппер. Сравнение полученных результатов с результатами других авторов.

3. Сравнение разработанного метода с методами других авторов на множестве случайно сгенерированных по методике О.^аевеИег задач различных классов. Решено более 500 задач. Результаты представлены в табличном виде.

4. Сравнение декодера последовательного конструирования и блочного декодера. Сравнение производится на случайно сгенерированных по методике О.^аевеИег задачах прямоугольной упаковки. Задачи решаются разработанным методом поиска с запретами с использованием сравниваемых декодеров. Результаты представлены в табличном виде.

В таблице 1 приведены результаты тестирования алгоритма на безотходных примерах Евы Хоппер. Примеры решались на компьютере с процессором РепИит1У-1400 в течение 30 секунд. Приведены результаты решения для всех предложенных задач. В качестве оценки решения

использовалась длина занятой части полосы

Результаты решения задач Евы Хоппер. Таблица 1

Задача М Опти Мум смм СВА №иЬ Иее N01. вР АСР РЯХ те

С1-! 16 20 20 го 20 20 20 21 20 20

С1-2 17 20 20 го 20 21 20 21 20 20

С1-3 16 20 20 20 20 20 20 21 20 20

С2-1 25 15 15 15 15 16 16 16 15 15

С2-2 25 15 16 15 15 16 16 16 15 15

С2-3 25 15 15 15 15 15 16 16 15

СЗ-1 28 30 31 31 30 30 31 32 30 31

СЗ-2 29 30 31 31 31 32 31 32 31 31

СЗ-З 28 30 31 31 30 31 31 32 31 31

С4-1 49 60 62 62 62 63 61 62 62 61

С4-2 49 60 63 62 62 64 62 61 62 61

С4-3 49 60 62 62 61 63 61 61 62 61

С5-1 73 90 92 92 92 95 92 92 91 91

С5-2 73 90. 93 92 92 95 92 92 93 92

С5-3 73 90 92 92 92 95 91 92 91 91

С6-1 97 120 123 123 123 127 123 122 125 122

С6-2 97 120 124 123 123 126 124 122 125 121

С6-3 97 120 123 124 123 127 123 122 125 122

С7-1 196 240 246 245 246 250 248 245 250 243

С7-2 197 240 245 245 247 256 247 244 253 242

С7-3 196 240 245 245 246 254 248 246 251 243

Суммарное отклонение 44 40 40 91 48 43 62 23

Лучших решений 6 8 И 4 8 5 10 12

Алгоритмы прямоугольной упаковки, участвовавшие в эксперименте:

GMM - Генетический мультиметодный алгоритм; GBA - Генетический блочный алгоритм;

NSubRec - наивный алгоритм с декодером замещения и перестройкой; NDL - наивный алгоритм с двойственным декодером;

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

АСР - алгоритм муравьиной колонии;

DSS - алгоритм динамического перебора;

TS - «Поиск с запретами» с блочным декодером.

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

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

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

2. Разработан декодер последовательного конструирования упаковки, значительно превосходящий традиционно использовавшийся «Нижний левый». Полученные с использованием, декодера результаты сравнимы с результатами блочного декодера Чиглинцева А.В.;

3. Разработана модифицированная схема поиска с запретами с использованием нескольких типов окрестностей текущего решения и вторичных оценочных функций. Метод не зависит от декодера, и может быть использован для решения задач прямоугольной упаковки и гильотинного раскроя листов и полубесконечной полосы. Использование вторичных оценочных функций позволило улучшить КРА в среднем на 1-3%, а в некоторых случаях до 6-8%;

4. Разработанные алгоритмы реализованы в соответствие с принципами объектно-ориентированного программирования, и интегрированы в систему прямоугольного раскроя и упаковки СЕТАМ1-СЦТ. На основе вычислительного эксперимента проведен анализ зависимости получаемых результатов от различных параметров алгоритма. Алгоритм поиска с запретами в составе системы СЕТАМ1-ШТ был внедрен в различных отраслях производства и подтвердил свою эффективность. Полученные им результаты при количестве заготовок до 300-500 в среднем на 2-10% лучше, чем у других реализованных в системе методов;

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

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

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

2000. С. 95-100.

2. Мухачева Э.А., Ермаченко А.И., Сиразетдинов Т.М., Усманова

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

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

2001. С. 18-23.

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

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

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

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

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

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

10. Мухачева Э.А., Ермаченко А.И., Жукова Т.Ю., Сиразетдинов Т.М. Комплекс алгоритмов и программ расчета гильотинного раскроя // Информационные технологии. 2004. № 8. С. 18-25.

Ермаченко Александр Иванович

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

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

АВТОРЕФЕРАТ

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

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

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

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

»24634

Введение.

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

1.1. Задачи раскроя и упаковки и их классификация.

1.2. Методы математического программирования.

1.3. Точные методы комбинаторной оптимизации.

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

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

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

1.5.2. Поиск с запретами.

1.5.3. Имитация отжига.

1.5.4. Муравьиная колония.

1.6. Использование декодеров.

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

1.8. Выводы.

2. Математические модели задач двумерного прямоугольного раскроя. Процедуры кодирования и декодирования.

2.1. Исходная информация задач двумерного прямоугольного раскроя.

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

2.3. Постановка задач прямоугольного раскроя и упаковки.

2.4. Процедуры декодирования в решении задач двумерного прямоугольного раскроя и упаковки.

2.4.1. Рекурсивный декодер.

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

2.4.3. Декодер «Нижний левый».

2.4.4. Блочный декодер.

2.5. Декодер последовательного конструирования для прямоугольной упаковки.

6. Выводы по второй главе.

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

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

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

3.3. Реализация метода поиска с запретами в составе автоматизированной системы проектирования карт двумерного прямоугольного раскроя СЕТАМ1-СиТ.

3.4. Выводы по третьей главе.

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

4.1. Выбор числа шагов до смены вторичной оценки.

4.2. Эксперимент на случайно сгенерированных примерах.

4.2.1. Примеры с количеством предметов 40.

4.2.2. Примеры с количеством предметов 400.

4.3. Сравнение декодера последовательного конструирования и блочного декодера.

4.4. Эксперимент на безотходных примерах Евы Хоппер.

4.5. Выводы по четвертой главе.

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

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

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

На данный момент для решения задач дискретной оптимизации наиболее активно используются генетические алгоритмы. Также широкое распространение получили метаэвристики «Поиск с запретами», «Имитация отжига» и «Муравьиной колонии».

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

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

Цель работы

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

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

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

2. Разработать процедуры декодеров и использовать их в составе метаэвристического алгоритма «Поиск с запретами»;

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

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

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

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

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

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

Обобщенная математическая модель для задач двумерного прямоугольного раскроя-упаковки;

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

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

Программная реализация разработанных методов в составе системы двумерного прямоугольного раскроя СЕТАМ1-С11Т;

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

Научная новизна работы. Новыми в работе являются:

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

Разработан декодер последовательного конструирования для задачи прямоугольной упаковки. Новыми в алгоритме являются метод описания границы упаковки и процедура укладки прямоугольника. Разработанный декодер превосходит известный алгоритм «Нижний Левый». Найдены классы задач, на которых он превосходит также разработанный аспирантом кафедры A.B. Чиглинцевым «Блочный декодер». Показано, что разработанный алгоритм обладает свойством реставрации;

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

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

1. Метод интегрирован в систему автоматизированного проектирования двумерного прямоугольного раскроя CETAMI-CUT. Имеются акты внедрения разработанных методов и программного обеспечения в учебный и производственный процесс. Программа CETAMI-CUT зарегестрирована в РОСПАТЕНТ, свидетельство № 2004611452;

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

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

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

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

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

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

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

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

5. Семинары группы изучения метаэвристических алгоритмов института математики СО РАН (Новосибирск, 2003);

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

Публикации. По теме диссертации опубликовано 11 работ: 7 статей, в том числе две в центральном журнале, 3 трудов конференций, выполненных по теме диссертации при непосредственном участии автора, и один акт о регистрации программы. в

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

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

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

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

2. Разработан декодер последовательного конструирования упаковки, значительно превосходящий традиционно использовавшийся «Нижний левый». Полученные с использованием декодера результаты сравнимы с результатами блочного декодера Чиглинцева A.B.;

3. Разработана модифицированная схема поиска с запретами с использованием нескольких типов окрестностей текущего решения и вторичных оценочных функций. Метод не зависит от декодера, и может быть использован для решения задач прямоугольной упаковки и гильотинного раскроя листов и полу бесконечной полосы. Использование вторичных оценочных функций позволило улучшить КРА в среднем на 1 -3%, а в некоторых случаях до 6-8%;

4. Разработанные алгоритмы реализованы в соответствие с принципами объектно-ориентированного программирования, и интегрированы в систему прямоугольного раскроя и упаковки CETAMI-CUT. На основе вычислительного эксперимента проведен анализ зависимости получаемых результатов от различных параметров алгоритма. Алгоритм поиска с запретами в составе системы CETAMI-CUT был внедрен в различных отраслях производства и подтвердил свою эффективность. Полученные им результаты при количестве заготовок до 300-500 в среднем на 2-10% лучше, чем у других реализованных в системе методов;

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

Заключение

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

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

Для решения задач раскроя успешно применяются метаэврестические методики решения задач дискретной оптимизации, в том числе методика поиска с запретами.

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

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

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

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

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

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

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

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

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

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

11. Грицюк Ю. Регулярне размщувания прямокутних объекив вздовж смуг односиоронньо обмежено1 стр1чки // JIlbîb. УкрДЛТУ. 2002. 220с.

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

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

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

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

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

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

18. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения.

19. Сборник лекций молодежных и научных школ по дискретной математике и ее приложениям. М.: Издательство центра прикладных исследований при механико-математическом факультете МГУ. 2000. С. 87-117.

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

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

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

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

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

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

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

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

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

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

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

31. Мухачева Э.А., Мухачева A.C. Метод перестройки для решения задачи прямоугольной упаковки // Информационные технологии. 2000 №4. С. 30-36.

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

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

34. Норенков И.П., Косачевский О.Т. генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации // Информационные технологии. 1999. №2. С. 2-8.

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

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

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

38. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. -Киев: Наукова думка. 1986. 268 с.

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

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

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

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

43. Baker B.S., Goffman Jr. E.G., Riverst R.L. Orthogonal packing in two dimensions // SI AM J. Comput. 9 (1980) 846-855.

44. Baum S., Trotter Jr.L. Integer rounding for polymatroid and branching optimization problems. // SIAM J. Alg. Disc. Meth. 1981. 2(4). P. 416-425.

45. Belov G., Scheithauer G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths // European Journal of Operational Research. 2002. 141. P. 274-294.

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

47. Boschetti M.A. The Two-Dimensional Finite Bin Packing Problem 11 Quaterly Journal of the Belgian, French and Italian Operations Research Societies 2002

48. Burke E., Kendall G. Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem // Accepted for the 1999 International Conference on Artificial Intelligence, Monte Carlo resort. Las Vegas. Nevada. USA. 1999.

49. Chen P., Chen Y., Goel M., Mang F. Approximation of Two-Dimensional Rectangle Packing // CS270 Project Report, Spring 1999.

50. Chung F.K.R., Garey M.R., Johnson D.S. On packing two-dimensional bins // SIAM J. Algebraic Discrete Meth. 3 (1982) 66-76.

51. Coffman E.G. Jr., Garey M.R., Johnson D.S., Taijan R.E. Performance bounds for level-oriented two-dimensional packing algorithms // SIAM J. Comput. 9(1980) 801-826.

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

53. Dorigo M., Gambardella L.M. Ant Colonies for the traveling salesman problem // IRIDIA, Technical Report 1996. 3.

54. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation. 1997. Vol.1. No.l.

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

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

57. Faroe O., Pisinger D., Zachariasen M. Guided local search for the three-dimensional bin packing problem // Tech. Rep. 99/13, DIKU, University of Copenhagen, Denmark. Dept. of Computer Science, University of Copenhagen.

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

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

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

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

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

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

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

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

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

67. Imahori S., Yaguira M., Ibaraki T. Local Search Heuristics for the Rectangle Packing Problem With General Spatial Costs // MIC'2001 4th Metaheuristics International conference. P. 471-476.

68. Keller H., Kotov V. An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing // Operations Research Ketters. V. 31. N1. 2003.

69. Kochetov Yu., Usmanova A. Probabilistic Tabu Search with Exponential Neighborhood for Bin Packing Problem // Proceedings MIC'2001, Porto, 2001. P. 619-624.

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

71. Lodi A., Martello S., Vigo D. Heuristic algorithms for the three-dimensional bin packing problem // European Journal of Operational Research. 2002. 141. P. 410-420.

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

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

74. Marcotte O. The cutting stock problem and integer rounding // Math. Program. 1985. 33(1). P. 82-92.

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

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

77. Martello S., Vigo D. Exact solution of two-dimensional finite bin packing problem // Management Science. 1997. 35. P.64-68.

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

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

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

81. Sakanushi K., Kajitani Y. The Quarter-State (Q-sequence) to Represent the Floorplan and Applications to Layout optimization // IEEE Asia Pacific Conference on Circuits and systems. 2000. Pp.829-832.

82. Scheithauer G. and Terno J., Theoretical Investigations on the Modified Integer Roundup Property for the One-dimensional Cutting Stock Problem, Operations Research Letters, 20, (1997) pp. 93-100.

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

84. Schwerin P., Wascher G. A New Lower Bound for the Bin-Packing Problem and its integration to MTP // Pesquisa Operational. 1999. 19(2). P.l 11-131.

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

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

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

88. Takahashi T. A New Encoding Scheme for Rectangle Packing Problem 11 Graduate School of Science and Technology. Niigata University. IEEE. 2000. P. 175-178.

89. Tarnowski T., Terno J., Scheithauer G. A polynomial time algorithm for the guillotine pallet loading problem. INFOR 32. 1994. P. 275-287.

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

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

92. Verhoturov M.A., Sergeyeva O.Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // Pesquisa Operacional. 2000. V. 20. N2. P. 233-247.

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

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

95. E. Burke, G. Kendall. Comparison of Meta-Heuristic Algorithms for Clustering Rectangles. //Computers & Industrial Engineering 37 (1999), 383386

96. A. Lodi, S. Martello, D. Vigo. Approximation algorithms for the oriented two-dimensional bin packing problem. // EJOR 112 (1999), 158-166