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

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

ЧИГЛИНЦЕВ Артем Владимирович

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

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Уфа-2004

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

Научный руководитель заслуженный деятель науки РФ

д-р техн. наук, проф. Мухачева Элита Александровна

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

Морозкия Николай Данилович

канд. физ.-мат. наук, доц., Бухвалова Вера Вацлавовна

Ведущая организация Институт математики с Вычислительным

центром УНЦ РАН

Защита состоится 2004 г. ъШВР часов

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

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

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

/ Г.Т. Булгакова /

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

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

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

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

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

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

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

3. Разработка и исследование эффективности

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

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

5. Разработка алгоритмов-декодеров, формирующих упаковку на основе заданного кода;

6. Применение мультиметодной технологии дискретной оптимизации И.П. Норенкова для решения задачи прямоугольного гильотинного раскроя и исследование эффективности данного подхода;

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

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

1. Блочный способ кодирования упаковки;

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

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

4. Алгоритм конструирования упаковки - «блочный декодер»;

5. Генетический алгоритм гильотинного раскроя на базе мультиметодной технологии дискретной оптимизации И.П. Норенкова с дискриминацией эвристик;

6. Компьютерная программа, реализующая разработанные алгоритмы;

7. Исследование эффективности предложенных методов на основе результатов вычислительного эксперимента.

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

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

2. «Блочный декодер» - новый алгоритм конструирования упаковки; для него доказано наличие свойства «реставрации»; может применяться в других метаэвристиках;

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

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

известными в литературе реализациями;

4. Применение принципов мультиметодной технологии дискретной оптимизации ИМ. Норенкова к задаче гильотинного раскроя. Введение дискриминации простых эвристик позволило увеличить эффективность алгоритма.

Практическая значимость работы: программная реализация генетического блочного алгоритма показала значительные преимущества перед известными классическими способами применения эвристических методов к задачам упаковки на достаточно широком классе задач. Это позволяет использовать разработанные алгоритмы при практических расчетах. Программное обеспечение зарегистрировано в РОСПАТЕНТ свидетельство № 2002610945; результаты работы внедрены в ОАО АСКОН, г. Москва и учебный процесс УГАТУ

Апробация работы. Работа выполнялась в рамках заданий РФФИ, проекты 99-01-00937, 01-01-00510. За цикл работ «Новые генетические алгоритмы решения задач двумерного раскроя и упаковки» присуждена Медаль РАН. За лучшую научную студенческую работу автор награжден медалью Министерства Образования РФ. Во время учебы в аспирантуре был удостоен стипендии Президента РФ и стипендии Правительства РФ. Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:

1. Международная молодежная научно-техническая конференция «Интеллектуальные системы управления и обработки информации» (Уфа, 1999г.);

2. Республиканская научно-техническая конференция «Интеллектуальное управление в сложных системах» (Уфа, 1999г.);

3. Международная научная конференция «Моделирование, вычисления, проектирование в условиях неопределенности» (Уфа, 2000г.);

4. Международная конференция «Дискретный анализ и исследование операций» (Новосибирск, 2000г.);

5. Международная конференция INFORMS (USA, San Antonio, 2000г.);

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

7. Международная конференция IFORS 2002 (UK, Edinburgh, 2002г.);

8. Международные конференции CSIT'2001, CSIT'2003 (Уфа, 2001г., 2003г.);

9. Международная конференция ESICUP (Европейская специальная группа по раскрою и упаковке) (Germany, 2004г.);

10. Семинары кафедры вычислительной математики и кибернетики

Уфимского государственного авиационного технического университета.

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

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

Диссертация состоит из введения, пяти глав и заключения. Объем работы составляет 92 страницы машинописного текста, включая 25 рисунков на 21 странице, 1 пример на 2 страницах, 4 таблицы на 4 страницах, библиографию, содержащую 85 названий.

Благодарности

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

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

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

В первой главе проведен аналитический обзор задач прямоугольной упаковки и раскроя и методов их решения. Впервые качественная типология проведена в 1991г. немецким ученым Н. Dykhoff. Разнообразие моделей определяется главным образом фактором геометрии. Задачи одномерной упаковки (ID Bin Packing, 1DBP) и раскроя (ID Cutting stock, 1DCS) выполняют в работе вспомогательную роль. Основными объектами исследования являются задачи прямоугольной упаковки в полубесконечную полосу (1.5DBP) (термин 1.5D ввел в 1980 г. A.Hinxman), задачи прямоугольной упаковки в листы (2DBP) и задачи гильотинного раскроя (1.5DCS).

Задачи упаковки и гильотинного раскроя различаются технологией разрезания материала, а именно условием, когда возможными являются только сквозные резы, параллельные кромкам раскраиваемого материала. Задачи гильотинного раскроя берут свое начало от одномерного случая и рассматривались как обобщение последней Л.В.Канторовичем, В. А. Зал галл ером в 1951г. и независимо P. Gilmory, R. Gomory в 1961г. Подробно эта задача описана в 1983 г. Э.А. Мухачевой и в то же время J. Тегпо, R. lindeman&G. Scheithauer в Германии. Методы, основанные на линейном и

линейном целочисленном программировании, оказались приемлемыми для решения задач линейного и гильотинного раскроя. Задачи упаковки (ВР) являются типичными представителями NP-трудных проблем и для их решения применяются методы полного перебора с отсечением неперспективных вариантов. В России известны работы И.В. Романовского (1977), СВ. Кацева (1979), В.М. Картака (2001). За рубежом этой тематике посвящено много работ S. Martello&P. Toth (1990). Однако, ввиду NP-трудности размерность решаемых задач невелика (¿200 ДЛЯ 1D И ¿20 для 1.5D и 2D). Поэтому на ряду с точными применяются приближенные и эвристические алгоритмы, в том числе получившие широкое распространение - метаэвристики. Среди последних раньше других получили развитие генетические алгоритмы. Непревзойденным автором по генетическим алгоритмам для решения задач 1DBP и 1DCS является Е. Folkenauer (1998). Что касается двумерных задач, то эффективность зависит и от организации генетических процедур (кроссовера и мутации), а также от способа кодирования и алгоритма-декодера, с помощью которого происходит конструирование упаковки. Широкую известность на западе получил декодер «нижний-левый» (Improved Bottom Left, IBL), усовершенствованный D. Liu&H.Teng в 1999 г. На востоке (Япония) I. Imahori в 1995 г. разработал схемы парных последовательностей (Sequence Pair, Seq Pair) кодирования упаковок для комбинаторного поиска.

Исследуемый в диссертации генетический алгоритм разработан на основе блочных технологий, начало которых получено в работах А.С. Мухачевой. В диссертации разработан новый «блочный декодер» (Block Decoder, BD).

Наряду с простыми эвристиками, развиты и имеют большую теоретическую значимость асимптотически точные подходы (Э. Гимади, В. Залюбовский). В последние 20 лет бурно развиваются вероятностные методы локального поиска оптимума в комбинаторных задачах. Обзор методов в книге AurtsE. 1996 г. и статье Ю.А. Кочетова 2001г. В диссертации основное внимание уделено генетическим алгоритмам. Последние отличаются не только различными декодерами, но и идентификацией основных генетических элементов. Используется идентификация ген - блок, хромосома - совокупность блоков. Оригинальная методика используется в генетическом алгоритме И.П. Норенкова, ген - метод упаковки очередного предмета. Методология Норенкова модифицирована в новом алгоритме гильотинного раскроя.

Во второй главе приводятся математические модели задач прямоугольной упаковки в полубесконечную полосу (1.5DBP) и упаковки на листы (2DBP). Предложена блочная модель упаковки и изучены две задачи: кодирование упаковки с помощью блочного кода и обратная ей восстановление допустимой упаковки (декодирование).

Введем прямоугольную систему координат: оси Ох и Оу совпадают

соответственно с нижней неограниченной и боковой сторонами полосы. Положение каждого прямоугольника Р, зададим координатами (X„y¡) его левого нижнего угла.

Математическая модель задачи 1.5DBP.

Имеется прямоугольная полоса заданной ширины W и неограниченной длины, а также набор прямоугольных предметов (элементов), заданных размеров w„" }„ i = \,ni (ширина и длина /-го прямоугольника). Найти упаковку

предметов в полосу, занимающую минимальную длину L = mzx(xi +/,)—» min , при следующих условиях:

1. ребра упакованных предметов параллельны ребрам полосы

2. упакованные предметы не пересекаются друг с другом;

([*, ^ (*, + /,)] V[х, > (х, + /,)])V (у, > (у, + w,)]v [уJ > (у, + w,)]ji / * j; /, j = 1,/н

3. упакованные предметы не пересекаются со сторонами полосы.

Соответствующая условиям 1-3 карта размещения прямоугольных предметов в полосе называется прямоугольной упаковкой (Rectangular Packing, RP). Если длина L занятой части полосы достигает минимума, то RP -оптимальная упаковка.

Математическая модель задачи 2DBP.

Имеется неограниченное количество прямоугольных листов заданной ширины Wvl длины L, а также набор прямоугольных предметов (элементов), заданных размеров Найти упаковку предметов с минимальным

расходом листов, при следующих условиях: 1,2 аналогично задаче 1.5DBP

3. упакованные предметы не пересекаются со сторонами листов. Кодирование упаковок

Если рассматривать укрупненную структуру системы раскроя/упаковки, то выделяют два основных блока: 1) блок оптимизации; 2) блок геометрических преобразований. Блок оптимизации отвечает лучшего поиск решения на множестве допустимых решений, которые представляются с помощью заданного способа кодирования упаковки. Блок геометрических преобразований используется на этапе построения карты упаковки с целью оценки решений генерируемых в блоке оптимизации.

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

Рис. 1: Пример упаковки в полубесконечную полосу

Рассмотрим блочную модель упаковки. Упаковка разбивается на прямоугольные блоки одной и той же ширины Ж и различной длины При этом начало первого блока совпадает с началом полосы, а конец - с концом самого короткого прямоугольника, входящего в блок. Каждый последующий блок v~2,... начинается, как только заканчивается предыдущий. На рисунке пунктиром обозначено разбиение упаковки на пять различных блоков. Каждый блок мысленно разрезаем на одинаковые полосы длиной I мм и шириной W. Тогда блоку у = 1,к можно сопоставить линейный раскрой г„ полос длины Wс интенсивностью применения Х„, равной длине блока V. Такой способ разбиения упаковки представляет блочную модель упаковки.

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

(8,7,5,6) х4Ч,: (8,6) х5=19}

Аналогично можно представить план линейного раскроя. Каждому блоку V отвечает шаблон карты линейного раскроя г„ с указанием интенсивности

применения х„. Обозначим через Ж - план линейного раскроя, через Х(я) — соответствующее значение функции цели. План п линейного раскроя, отвечающий RP, назовем прямоугольно-ориентированным линейным раскроем (Rectangular Oriented Linear Cutting, ROLC).

Утверждение 1. Для любой допустимой упаковки RP длина /(RP) занятой части полосы совпадает со значением линейной функции в

соответствующей задаче линейного раскроя.

Утверждение 2. Для того, чтобы план U линейного раскроя, являлся ROLC, необходимо и достаточно выполнения следующих условий: 1°. разнородность элементов в блоке, 2°-. продолжениость; 3°. постоянство места; 4. соответствие интенсив)ностей длинам прямоугольников; 5°. размещаемость.

Для однозначности представления упаковки необходимо также знать размеры пустых участков, остающихся в блоках. Такие участки добавляются в список блоков в виде отрицательных чисел, которые по модулю равны ширине занятого ими участка. Например, последний блок для упаковки рис. 1. будет представлен так (8, -(W-w$-w¿), б). Сформированная подобным образом последовательность соответствует блочному способу кодирования упаковки.

Сравнительный анализ способов кодирования. Таблица 1.

•rtjjjjw»')* procSa ПК «ТёЛЗрНбСТЮНВетМнВ^м

Учет неиспользованных участков Нет Нет Нет Да

Однозначность представления карты упаковки Да Нет Нет Да

М.б. использован в блоке оптимизации Нет Да Да Да

М.б. использован в блоке геометрических преобразований Да Нет Нет Да

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

Алгоритмы декодеры

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

приоритетному списку формируются и модифицируются блоки.

» в) »)

Рис. 2: Размещение прямоугольников с помощью декодера IBD. а)- начало формирования блоков; б)- первая модификация; в)- вторая мод.

В . улучшенной версии блочного декодера IBD (Improved BD) используется стратегия, направленная на увеличение размера зон, остающихся незаполненными. Она основана на принципе притяжения предметов к краям полосы. На рисунке 2 б) предмет 4 притягивается (сдвигается) к нижнему краю полосы.

Код ДО сдвига [(1,2,-1,4,-1) 7; (6,-1,2,-1,4,-1) 2; (3,4,-1) 2; (3,-3) 3] После сдвига [(1,2,-2,4) 7; (6,-1,2,-2,4) 2; (3,4,-1) 2; (3,-3) 3]

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

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

Важной характеристикой декодера является его способность получить оптимальную упаковку, по заранее известному оптимальному коду (приоритетному списку), т.е. способность правильно декодировать. Назовем это свойство декодера термином «реставрация». Декодер обладает свойством «реставрации», если с его помощью по известному оптимальному приоритетному списку формируется оптимальная безотходная упаковка, при любом количестве испытаний. Проверить это свойство декодера возможно на тестовых заданиях, для которых заранее известны: 1) оптимальное значение длины занятой части полосы; 2) оптимальный приоритетный список, отвечающий безотходной упаковке.

Для BD сформулировано и доказано следующее утверждение.

Утверждение 3. Декодер BD обладает свойством «реставрации».

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

Каждой допустимой упаковке ЯР отвечает ее блочное представление. Блоки расположены в установленном порядке и связаны друг с

другом. Это позволяет интерпретировать их как гены. Тогда структуру упаковки можно интерпретировать хромосомой, содержащей п сцепленных между собой генов (блоков). Согласно хромосомной теории наследственности передача качественных принципов, закодированных в генах, будет осуществляться через хромосомы от «родителей» к «потомкам».

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

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

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

1. Для заданного набора исходных данных найти ROLC, для которого выполняются усл. 10 и 20 утв. 2. (Решается задача линейного программирования специальной структуры; исходный приоритетный список формируется по убыванию площадей прямоугольников); длина ROLC Л0 -квази-нижняя граница решения задачи упаковки и первоначальная локальная граница.

2. Создать начальную популяцию Ро (множество ROLC, полученное путем случайных перестановок элементов в блоках исходного ЬЮЬС); значение целевой функции

3. Пока не выполнен критерий остановки делать следующее.

{Скрещивание} Повторить заданное количество раз. Выбрать 2-х 3.1. родителей, построить потомков (рекомбинация блоков). Вычислить целевую функцию для потомков. Запомнить лучшее решение.

3.2. {Мутация} На основе лучшего решения сформировать новый исходный приоритетный список. Найти ROLC, для которого выполняются условия 1° и 2° утверждения 2. Длина - новая

локальная граница (осуществлен переход в новую окрестность).

Описаны способы оценки эффективности алгоритмов.

Четвертая глава посвящена исследованию мультиметодной технологии дискретной оптимизации И.П. Норенкова на примере рулонного гильотинного раскроя. Задача разбивается на множество подзадач, последовательное решение которых дает решение исходной задачи. Для решения подзадач, формулируется набор альтернативных элементарных эвристик. Задача сводится к поиску и использованию оптимальной последовательности эвристик, применяемых в подзадачах. Направленный перебор решений осуществляется с помощью генетического алгоритма. Главная особенность заключается в том, что аллелями служат не значения проектных параметров, а имена эвристик, используемых для определения этих значений: /-й ген соответствует /-и подзадаче, аллелями являются имена эвристик, именно среди них генетический алгоритм и выбирает члены последовательности, приближаясь к оптимальной последовательности.

Гильотинный генетический алгоритм (Guillotines genetic algorithm, GGA) построен по мультиметодной технологии. При решении задач гильотинного раскроя существенное значение имеет повторяемость прямоугольников что обусловлено производственными требованиями. Основная задача разбивается на Р подзадач. В качестве подзадачи можно рассматривать однотипное размещение набора прямоугольников qJy j = 1,Р, с помощью одной из случайно

выбранных эвристик, тогда Задача рулонного гильотинного

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

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

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

В пятой главе описывается реализация ПО согласно принципов объектно-ориентированного программирования и ряд экспериментов.

Эксперимент №1 - Исследование эффективности «блочного способа кодирования» и «блочного декодера». Использовалась классическая реализация генетического алгоритма, в котором на стадии декодирования упаковки из приоритетного списка использовались декодеры: IBL - «улучшенный нижний левый», D.Liu & H.Teng, 1999; SubRec - «декодер замещения с перестройкой», А.С Мухачева, 2004; IBD - «блочный декодер», Чиглинцев А.В., 2000.

Сравнение производилось на классе, задач с набором предметов различных размеров от малых 5% до 95% ширины полосы. Количество прямоугольников 40,80,120. Графически результаты представлены на рис. 3.

Рис. 3. Результаты эксперимента № 1.

Наилучшие результаты у «блочного декодера» IBD, за ним с небольшим отставанием следует SubRec. Декодер IBL показывает плохие результаты.

Эксперимент №2 - Исследование эффективности генетического блочного алгоритма. Для сравнения были выбраны пять алгоритмов: GBA-«2en. блочный алгоритм», Мухачева А.С, Чиглинцев А. В., 2000; GIBL -«классический ген алгоритм», D.Liu & H.Teng, 1999; GMM - «ген. мультиметодный алгоритм», И.П.Норенков, 2000; ACSP - «алгоритм муравьиной колонии», Валеева А.Ф., Аглиуллин М.Н., 2003; NDLS - «алгоритм наивного поиска двойственной блок-структурь», Мухачева А.С, Ширгазин P.P., 2002. Сравнение производилось на классе сложных задач (триплеты) V/=0.3, Vz=0A, W/=0 35, W/=0.45. Замечено, что характеристики по длине мало влияют на результативность, при решении задачи с запретом поворотов.

Рис. 4. Результаты эксперимента №2.

В качестве критерия эффективности упаковки применяется «коэффициент раскроя» (Cutting Coefficient, CC) равный отношению полезной площади ко всей затраченной. Для безотходной упаковки СС=100%. Лидируют «блочный генетический» и «мультиметодный генетический» алгоритмы.

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

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

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

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

4. Разработан новый алгоритм «блочный декодер», доказано наличие свойства «реставрации»;

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

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

Список публикаций

1. А.В. Чиглинцев. Генетический алгоритм моделирования прямоугольной упаковки на базе линейной аппроксимации. // Деп. ВИНИТИ. №2643-В99. 13.08.1999.

2. А.В. Чиглинцев. Генетический алгоритм прямоугольной упаковки на базе её линейной аппроксимации: применение в интеллектуальной системе. // Материалы международной молодежной научно-технической конференции «Интеллектуальные системы управления и обработки информации». Уфа: УГАТУ, 1999. С. 89.

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

4. А.В. Чиглинцев, Н.М. Садретдинова. Генетический алгоритм для моделирования прямоугольной упаковки с использованием нижних границ. // Problems oftransfer technology, Patras,1999.P.87-89 (англ. яз.).

5. Э.А. Мухачева, А.С. Мухачева, В.М. Карта к и А.В. Чиглинцев.

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

6. А.С. Мухачева, А.В. Чиглинцев. Гибридные генетические алгоритмы для двухмерных задач раскроя-упаковки // INFORMS. San Antonio. 2000. P. 115.

7. А.С. Мухачева, А.В. Чиглинцев и Э.Д. Кульбарисов. Поиск нижней границы длины упаковки неориентированных прямоугольников в полубесконечную полосу. // Материалы международной научной конференции «Моделирование, вычисления, проектирование в условиях неопределенности -2000» Уфа:УГАТУ, 2000. С. 456-457.

8. Э.А. Мухачева, А.С. Мухачева и А.В. Чиглинцев. Генетические алгоритмы для решения задач прямоугольного раскроя-упаковки // Материалы международной конференции «Дискретный анализ и исследование операций -2000» - Новосибирск, Издательство Института математики, 2000, С. 194. -

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

10. А.С.Мухачева, А.В.Чиглинцев, М.А.Смагин и Э.А.Мухачева.

Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения. // Информационные технологии. 2001. №9. Приложение. С. 1-24.

11. А.В. Чиглинцев, М.А. Смагин и Д.И. Бунаков. Задача прямоугольной упаковки: гибридный алгоритм на базе генетических процедур (MChS). // Труды 1-й всероссийской научно-практической конференции по вопросам решения оптимизационных задач в промышленности «Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования ОПТИМ-2001». СПб.: ЦНИИТС. С. 109112.

12. Э.А. Мухачева, А.С. Мухачева, А.В. Чиглинцев и Н.М. Садретдинова. Гибридные алгоритмы решения задачи двумерного раскроя-упаковки на базе генетических процедур. // CSIT-2001, The 3rd International Workshop on Computer Science and Information Technologies. - Ufa, Russia, P.I 12-126 (на англ. яз.).

13. А.С. Мухачева, А.В. Чиглинцев, М.А. Смагин и Э.А. Мухачева. Задачи двумерной упаковки: разработка генетических алгоритмов. // IFORS 2002: OR in a globalised, networked world economy. University of Edinburgh. 2002. P. 79. (на англ. яз.).

14. А.В. Чиглинцев, Н.М. Садретдинова. Алгоритмы упаковки прямоугольных предметов на листы с использованием блочной структуры упаковок. // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Уфа: УГАТУ. 2002. С.139-145.

15. А.С. Мухачева, А.В. Чиглинцев, М.А. Смагин и Н.М. Садретдинова. Процедуры декодирования при решении задачи двумерной упаковки // Proceedings ofthe 5th International Workshop on Computer Science and Information Technologies. -Ufa, Russia, 2003. V.2 P. 44-47.

16. А.В. Чиглинцев. Алгоритмы упаковки прямоугольных предметов на листы // Вестник УГАТУ. Уфа: УГАТУ. 2003. №2. С. 181-187.

Чиглинцев Артем Владимирович

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

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

АВТОРЕФЕРАТ

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

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

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

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

119794

РНБ Русский фонд

2005-4 17300

ИСПОЛЬЗОВАННЫЕ ОБОЗНАЧЕНИЯ.

ВВЕДЕНИЕ.

1. ЗАДАЧИ РАСКРОЯ-УПАКОВКИ: ОБЗОР МЕТОДОВ РЕШЕНИЯ.

1.1. Задачи одно и двумерного раскроя-упаковки.

1.1.1. Простейшая одномерная задача раскроя и упаковки.

1.1.2. Задача прямоугольной упаковки в полубесконечную полосу.

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

1.1.4. Задача гильотинного раскроя.

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

1.2.1. Использование методов математического программирования.

4 1.2.2. Применение методов комбинаторной оптимизации.

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

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

1.3. Основные задачи исследования.

1.4. Выводы.

2. МОДЕЛИРОВАНИЕ ПРЯМОУГОЛЬНЫХ УПАКОВОК.

2.1. Математические модели задач упаковки в полосу и на листы.

2.2. Блочная модель упаковки.

2.3. Способы кодирования упаковок.

2.4. Алгоритмы декодеры. Блочный декодер.

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

2.6. Выводы. 3. ГЕНЕТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ УПАКОВКИ.

3.1. Общая характеристика генетических методов.

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

3.3. Оценка эффективности алгоритмов. Нижние границы.

3.4. Выводы.

4. ЗАДАЧА ГИЛЬОТИННОГО РАСКРОЯ.

4.1. Математическая модель задачи раскроя полосы.

4.2. Использование мультиметодной технологии. Гильотинный генетический алгоритм.

4.3. Метод дискриминации простых эвристик.

4.4. Выводы.

5. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ.

5.1. Программная реализация алгоритмов.

5.2. Исследование эффективности способов кодирования упаковки и алгоритмов декодеров при использовании генетических алгоритмов

5.3. Исследование декодеров. Проверка на наличие свойства «реставрации».

5.4. Исследование эффективности генетического блочного алгоритма. Сравнительный эксперимент с метаэвристическими алгоритмами.

5.5. Исследование эффективности генетического гильотинного алгоритма с применением дискриминации эвристик.

5.6. Выводы.

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

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

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

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

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

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

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

3. Разработка и исследование эффективности генетического блочного алгоритма;

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

5. Разработка алгоритмов-декодеров, формирующих упаковку на основе заданного кода;

6. Применение мультиметодной технологии дискретной оптимизации И.П. Норенкова для решения задачи прямоугольного гильотинного раскроя и исследование эффективности данного подхода;

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

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

1. Блочный способ кодирования упаковки;

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

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

4. Алгоритм конструирования упаковки - «блочный декодер»;

5. Генетический алгоритм гильотинного раскроя на базе мультиметодной технологии дискретной оптимизации И.П. Норенкова с дискриминацией эвристик;

6. Компьютерная программа, реализующая разработанные алгоритмы;

7. Исследование эффективности предложенных методов на основе результатов вычислительного эксперимента.

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

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

2. «Блочный декодер» - новый алгоритм конструирования упаковки; для него доказано наличие свойства «реставрации»; может применяться в других метаэвристиках;

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

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

Практическая значимость работы: программная реализация генетического блочного алгоритма показала значительные преимущества перед известными классическими способами применения эвристических методов к задачам упаковки на достаточно широком классе задач. Это позволяет использовать разработанные алгоритмы при практических расчетах. Программное обеспечение зарегистрировано в РОСПАТЕНТ свидетельство №2002610945; результаты работы внедрены в ОАО АСКОН, г. Москва и учебный процесс У Г АТУ.

Апробация работы. Работа выполнялась в рамках заданий РФФИ, проекты 99-01-00937, 01-01-00510. За цикл работ «Новые генетические алгоритмы решения задач двумерного раскроя и упаковки» присуждена Медаль РАН. За лучшую научную студенческую работу автор награжден медалью Министерства Образования РФ. Во время учебы в аспирантуре был удостоен стипендии Президента РФ и стипендии Правительства РФ. Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:

1. Международная молодежная научно-техническая конференция «Интеллектуальные системы управления и обработки информации» (Уфа, 1999г.);

2. Республиканская научно-техническая конференция «Интеллектуальное управление в сложных системах» (Уфа, 1999г.);

3. Международная научная конференция «Моделирование, вычисления, проектирование в условиях неопределенности» (Уфа, 2000г.);

4. Международная конференция «Дискретный анализ и исследование операций» (Новосибирск, 2000г.);

5. Международная конференция INFORMS (USA, San Antonio, 2000г.);

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

7. Международная конференция IFORS 2002 (UK, Edinburgh, 2002г.);

8. Международные конференции CSIT'2001, CSIT'2003 (Уфа, 2001г., 2003г.);

9. Международная конференция ESICUP (Европейская специальная группа по раскрою и упаковке) (Germany, 2004г.);

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

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

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

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

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

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

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

Четвертая глава посвящена исследованию мультиметодной технологии дискретной оптимизации И.П. Норенкова на примере рулонного гильотинного раскроя.

В пятой главе описывается реализация ПО согласно принципов объектно-ориентированного программирования и ряд вычислительных экспериментов.

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

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

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

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

4. Разработан новый алгоритм «блочный декодер», доказано наличие свойства «реставрации»;

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

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

Заключение

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

Развитие генетических алгоритмов для решения задач 1.5DBP и 2DBP проведено на базе блочной модели упаковки, а задачи гильотинного раскроя 1.5DCSP на базе технологии И.П. Норенкова с использованием простых эвристик. В первом направлении разработан генетический блочный алгоритм GBA с блочном декодером IBD, он показал лучшие результаты при сравнительном эксперименте. Совершенствование генетического алгоритма для задачи упаковки реализовалось за счет новой идентификации элементов генетического метода: генов, аллелей, хромосом и процедур над ними. Во втором направлении совершенствование известной методики достигнуто за счет применения дискриминации простых эвристик.

1. Аккуратов Г.В., Березнев В.А., Брежнева О.А. О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Уфа: УАИ. 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. Ю.Грицюк Ю. Регулярне разм1щувания прямокутних объек^в вздовж смуг односиоронньо обмежежм стр1чки // Льв1в. УкрДЛТУ. 2002. С. 220.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36. Романовский И.В., Христова Н.П. Решение дискретных минимаксных задач методом дихотомии // ЖВМ и МФ. 1973. 13(5). С. 1200-1209.

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

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

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

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

41. 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.

42. Berkey J.O., Wang P.Y. Two dimensional finite bin packing algorithms.// J. Oper. Res. Soc. 38 (1987) P. 423-429.

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

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

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

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

47. Coffman E., Garey M., Jchonson D. Approximation algorithms for bin-packing-an updated survey // Algorithm Design for Computer System Design (Ausiello G., Lucertini M., Serafini P.eds) Berlin etal. 1984.

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

49. 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.

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

51. Dykhoff H., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1990.

52. 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.

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

54. 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.

55. Garey M.R., Johnson D.S. Computers and Intractability: A guide to the Theory of NP-Completeness // San-Francisco, Freemau. 1979.

56. 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.

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

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

59. Hinxman A. The Trim-Loss and assortment problems: a survey // European Journal of Operational Research. 1980. N11. P.863-888.

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

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

62. Jhonson D.S., Demers A., Ullman J.D., Garey M.R., Graham R.L. Worst-case performance bounds for simple one-dimensional packing algorithms // SIAM J. Comput. V. 3. N4. 1974. P.299-325.

63. Lirov Y., edit. Special issue: Geometric Resource Allocation // Mathematical and Computer Modelling. 1995. 16(1).

64. 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.

65. 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.

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

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

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

69. Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementations. // YOHN WILEY&SONS. Chichester. 1990.

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

71. 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.

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

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

74. Mukhacheva E.A., Zalgaller V.A. Linear Programming Cutting Problems // International Journal of Software Engineering and Knowledge Engineering. 1993. V. 3. N4. P. 463-476.

75. 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. P. 829-832.

76. 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.

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

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

79. 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. 110-114.

80. 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.

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

82. Yanasse H., edit. Special issue: Cutting and Packing Problems// Pesquisa Operacional. 1999. 19(2).

83. Baesley J.E. OR-Library http://www.brunel.ac.uk/depts/ma/research/ieb/info.html.

84. Hopper E., Turton B.C.H. Test Problem Sets from Hopper/Turton http://www.apdio.pt/sicup/nonpub/research-support/hopper.html.