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

На правах рукопис^г -

СУРНАЧЕВ Максим Юрьевич

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

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

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

Уфа 2005

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

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

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

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

Житинков Владимир Павлович канд. техн. наук, доц. Григорчук Татьяна Ивановна

Ведущая организация Башкирский государственный университет

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

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

Автореферат разослан « 2 5 » 2005 г.

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

тй-м 1153 Г?/

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

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

Актуальность проблемы. В научной и производственной деятельности часто встречаются ситуации раскроя и упаковки встречаются очень часто: это задачи раскроя материала на заготовки различных форм и размеров, и задачи размещения совокупности предметов на ограниченной площади или в ограниченном пространстве. Многие другие проблемы также сводятся к ситуациям раскроя и упаковки. Среди многообразия постановок задач раскроя и упаковки самостоятельный интерес представляют задачи упаковки параллелепипедов (ЗБВРР). К таким задачам относятся, например, оптимизация перевозки и складирования грузов, планирование помещений, проектирование систем, конструктивно выполненных в виде набора блоков, компоновка деталей. К рассматриваемым проблемам сводится также и ряд задач планирования и распределения ресурсов. Несмотря на конкретное практическое применение, круг работ по решению задач параллелепипедной упаковки невелик. Это объясняется сложностью задач и высокой трудоемкостью их решения. Поэтому является актуальной разработка эффективных алгоритмов решения задач раскроя-упаковки параллелепипедов.

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

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

Задачи, поставленные для достижения цея#0вбШИ£ИОНАЛЬНАЯ I

I БИБЛИОТЕКА \

09 гау/«-- , л

1. Рассмотреть постановки основных задач трехмерной упаковки, описать их математические модели;

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

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

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

5. Разработать программное обеспечение, реализующее предложенные методы и алгоритмы;

6. Провести численный эксперимент с целью исследования эффективности предложенных алгоритмов.

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность работы: Разработанное программное обеспечение решает задачу, имеющую 1<яюго численное практическое применение, в том

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

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

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

1. Международная научная конференция "Моделирование, вычисления, проектирование в условиях неопределенности-2000" (Уфа, 2000).

2. Студенческая научно-теоретическая конференция 2001 (Уфа, 2001)

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

4. CSIT'2001: Computer Science and Informational Technologies (Уфа, 2001);

5. Вторая Всероссийская научно-техническая конференция «Мехатроника, автоматизация, управление - 2005» (Уфа, 2005).

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

По теме диссертации опубликовано 10 работ: 6 статей и 4 трудов конференций.

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

Диссертация состоит из введения, четырех глав и заключения. Объем работы составляет 97 страницы машинописного текста, включая 17 рисунков на 16 страницах, 12 таблиц на 6 страницах, библиографию, содержащую 81 название.

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

1. Задачи раскроя-упаковки являются NP-трудными, поэтому в этой области большое внимание уделяется не только точным, но и эвристическим методам.

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

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

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

Упаковка в контейнер с неограниченной высотой (3DCPP) Контейнер имеет фиксированную ширину и длину, но бесконечную высоту. Целью является упаковка всех ящиков (параллелепипедов) таким образом, чтобы высота заполненной части контейнера была минимальной. В итоге получается паковка трехмерной полосы [25].

Исходная информация представляется следующим набором данных <L, W, т, I, w, h>.

Решение, представляется в виде <Н, X, Y, 2> Параметры математической модели: Входные параметры: L - длина контейнера; W- ширина контейнера; т - количество ящиков (параллелепипедов);

/ = (/,,. ..,/„. ,.,lm), U - длина г'-го ящика, i = l,m;

w = (wi,.. .,w„...,wm), w, - ширина ¿-го ящика, i = \,m;

h = (hu ...Ji„...Ji„), ht- высота 1-го ящика, / = 1,m; Выходные параметры: H- высота упаковки;

Х={хъ ...,х„ ...,хт), Г=(уь ■■■>У» Z=(zb ...,zh ...,zm), где (x„y„z,)

- координаты i-ro ящика в упаковке, если начало координат совпадает с передней левой, нижней вершиной контейнера.

Математическая модель 3DCPP: Имеется набор данных <W, L, т, w, /, h>.

Необходимо найти упаковку предметов <#, X, У, Z>, такую что Я = »

max(z( + h,) min, при условиях:

/=1

1. ребра упакованных ящиков параллельны ребрам контейнера;

2. упакованные предметы не перекрываются друг с другом: ([*, £ {х] +7,)]V[Х] > (х, + /,([>-, & {У] + )]V{У) + м>,)])V

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

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

Блочная структура (Вв) трехмерной упаковки представляет собой способ кодирования расположения ящиков в контейнере. Данный подход базируется на разбиении контейнера на двумерные, а затем на одномерные блоки.

Пусть имеется упаковка ящиков <1=4, 1¥=5, Н=4, т=5, /={2,1,1,1,2}, м>={5,5,5,3,2}, Й={3,2,1,2,2},Х={0,2,3,3,2}, 7={0,0,0,0,3}, 2={0,0,0,1,1}>.

Рис.1. Линии рассечения контейнерной упаковки

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

к

Каждый из этих слоев представляет собой прямоугольную упаковку (Rectangular Packing, RP). Тем самым мы от трехмерной задачи перешли к двумерной. Блок структура запишется следующим образом:

BS = {RP(\) уи RP(2) 72, ..., RP(k) у*}, RP{k) - прямоугольная упаковка к-го

СЛОЯ ВЫСОТЫ fk-

BS = {Щ1)1, ЯР(2)1, ДР(3)1, Я/>(4)1} (см рис. 2).

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

1. Установка четкой последовательности элементов в каждом из прямоугольно-ориентированных линейных раскроев, из которых состоит RP.

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

RP(i) RP(2)

п Р2 РЗ PI Р2 Е

■ Р4

RP(3) RP(4)

Рис. 2. Набор ЯР, полученных из контейнерной упаковки

Исходя из этих допущений, мы устанавливаем жесткий порядок для всех элементов блок структур и решаем проблему однозначности в построении упаковок М» для ЗБВРР.

Блок структура, получаемая с учетом вышеизложенных допущений, запишется одним списком:

КР= {(пЪ, {гг)Х2,..., (гдх*}, У = где блок представляет собой последовательность номеров прямоугольных предметов записанных для каждого блока снизу - вверх; х у ~ интенсивность применения раскроя V.

Таким образом, упаковки ИР представленные на рис. 1 запишутся в виде:

ДР(1)={(Р1)2,(Р2)1,(РЗ)1}

ЯР(2) = {(Р1)2, (Р2)1, (Р4,-2)1} (1)

Д/>(3) = {(Р1)2, (-3, Р5)1, (Р4, Р5)1}

ЯР(4)={(-5)2,(-3,Р5)2}

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

= {АР(1)1, ЛР(2)1, Щ3)1, ДР(4)1} с элементами (1).

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

1. По сравнению с приоритетным списком РЬ блочный способ кодирования обладает свойством однозначности при определении координат (х,у,г) ящиков, т.е. эскиза упаковки.

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

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

Свойства трехмерной блок-структуры:

1°. Разнородность: элементы любого кортежа любой ЯР{к) различные.

2°. Продолженностъ: 1) Если элемент ] обнаруживает первое включение в кортеже г„ то он будет содержаться во всех последующих кортежах для кото-

р~ 1

рых выполняется неравенство < , где р - номер последующего кортежа;

2) Если элемент у обнаруживает первое включение в слое КР(г'), то он будет содержаться во всех последующих ИР, для которых выполняется неравенство

ук<1Ъ], где р - номер последующей ЫР. ы

3°. Постоянство места: 1) Если элемент} содержится в кортеже г, и г1+и то сумма /, элементов предшествующих элементу ] для обоих кортежей будет равна; 2) Если элемент у содержится в слое КР(г) и КР(г+7), то проекции этих элементов на плоскость ХОУ будут совпадать.

4°.

Для получения координат (X, У, 7) из блок-структуры достаточно осуществить проход по всем кортежам всех И* и занести координаты ящиков (левый, нижний, ближний угол) в тех позициях, в которых они обнаружили первое вхождение. Координаты ящика г запишутся в виде:

х,=2^Х]> ГдеР ~ номер кортежа, где впервые встретился элемент г;

У> ~ Х1"./ ' где ^ЧУ ~ множество элементов предшествующих элементу г в уеЛ«) кортеже к, к-1

= £>,, ГДе к~ номер ИР, в которой впервые встретился элемент г.

М

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

На базе контейнерной блок-структуры предложен однопроходный алгоритм (декодер) построения упаковок из перестановки ящиков и рассмотрены возможные ходы по учету технологических ограничений. Проиллюстрируем работу декодера на примере для представленного выше набора <¿=4, УУ^Ъ, Н= 4, т~5, /={2,1,1,1,2}, >^={5,5,5,3,2}, А={3,2,1,2,2}>. РЬ={ 1,2,3,4,5}.

Работа блочного декодера

На рис. 3 показана работа декодера при заполнении дна контейнера или первого слоя, обозначенного как КР(1). Декодер последовательно в соответствии с приоритетным списком укладывает ящики в свободные области. При заполнении слоя декодер работает непосредственно с кортежами, т.е. с одномерными упаковками. Если после завершения прохода по приоритетному списку

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

РР=5

Ж=5

£=4

№*5

Уп

№=5

1 1

Рис. 3. Работа блочного декодера при заполнении ЛР(1)

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

у><

1

Рис. 4. Работа блочного декодера при заполнении ИР(2)

Аналогично декодер работает при заполнении ИР(3). См рис. 5.

X

Р1 Р5

2

а

б

Рис. 5. Работа блочного декодера при заполнении ЯР(3)

Полученная блок-структура соответствует упаковке, представленной на рис. 1. Но Алгоритм построил не окончательную блок-структуру. Упаковка должна описываться набором из 4 слоев. Мы же получили только 3. Отказ от нахождения последующих ЯР обусловлен тем, что для нахождения координат ящиков и высоты упаковки уже достаточно текущей блок-структуры. Поэтому построение полной блок-структуры будет нерациональным. Мы же хотим получить декодер, работающий быстро.

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

1. Ограничение на повороты

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

2. Условие стабильности

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

3. Ограничение по весу

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

4. Условие баланса

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

5. Ограничение на вертикальные образования

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

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

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

Метод случайных перестановок приоритетного списка

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

Работа метода строится следующим образом:

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

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

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

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

П. Борисовским доказано, что, если оператор мутации обладает свойством монотонности, то алгоритм (1+1)-ЕА является оптимальной стратегией поиска среди различных ЭА. Для операторов мутации применяемых в среде задач раскроя-упаковки, свойство монотонности мутации пока не доказано.

Классический генетический алгоритм

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

Для задач раскроя-упаковки широкую известность получил традиционный генетический алгоритм, развитый в работах западных ученых (1Ли Б., Тегщ Н., A.Bortfeldt, Н.ОеЬгш£ и др.).

В качестве хромосом для него служат приоритетные списки. Элементы PL, которые соответствуют упаковываемым предметам, являются генами.

Работа оператора скрещивания:

PLI, PL2 - приоритетные списки соответствующие родителям.

PL3, PL4 — потомки PL1 и PL2, созданные путем скрещивания.

Сначала выбираются два случайных числа g яр, 0<g<m, 0</K»»-g+2. Затем начиная с позиции g копируем р элементов из PL1 в PL3. Оставшиеся позиции в PL3 заполняем элементами из PL2 в той же последовательности, в которой они встречаются в этом списке. Аналогично строится PL4.

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

Оператор естественного отбора удаляет хромосомы с наихудшей функцией цели. В частности для задач 3DBPP, функцией цели является H упаковки. Естественный отбор удалит упаковки с наибольшими Я.

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

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

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

Целью численного эксперимента является сравнение эффективности разработанных алгоритмов SABD (метод случайных перестановок), GABD (классический генетический алгоритм), EABD (эволюционный алгоритм 1+1). Тестовые задачи генерировались случайным образом по методике G.Waescher.

На рис.6 отображена зависимость целевой функции от количества ящиков.

- - SABD

GABD

— EABD

20 40 80

количество ящиков

Рис.6

Тестирование проходило при следующих условиях: длина основания контейнера L = 150; ширина основания контейнера W= 100; количество предметов

т = 20; 40; 80; Размеры ящиков генерировались случайно в пределах 0,21 < /, 5 0,621; 0,2 Г < ^ < 0,6 Я'; 0Д£ </г,< 0,61

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

При небольших значениях т (<40) лучше вели себя метод случайных перестановок и эволюционный (1+1). С увеличением т отмечается устойчивый рост, как средней целевой функции, так и общего числа наилучших решенных задач, у генетического алгоритма. На рис.7 приведена зависимость количества наилучших решений у алгоритмов с ростом т.

Рис.7

Сравнительный эксперимент с другими методами решения

В тестах принимали участие 6 алгоритмов: метод случайных перестановок (SABD), классический генетический алгоритм (GABD), эволюционный алгоритм (1+1)-ЕА (EABD), алгоритм G. Scheithauer (SA), модифицированный алгоритм G. Scheithauer (MSA), блочный алгоритм с ограниченным перебором (ВРА) А.Ф. Валеевой, И.Е. Тоцкова,.

Тестирование проводилось при т=30 для трех классов: мелкие, средние и разнородные ящики. И двух высот ящиков: небольшим разбросом (0,2£ < h, < 0,25/,) и с большим (0,2L <h,< 0,6L). При этом для каждого из классов генерировалось по 3 подкласса по 10 примеров. Поскольку алгоритмы SA и MSA существенно уступали остальным, они не были включены в диаграмму (рис.8) для наглядности.

Разработанные методы были лучшими в 14 из 18 классов (В 6 лучшим был метод случайных перестановок, в 6 - генетический алгоритм и в 2 эволюционный). В четырех классах лучшим был ВРА, он также лучше повел себя для классов средних ящиков.

0,78

Я °-7

Ф

§ 0,68 0,66

бЭАВО ШвАВО

□ ЕАЕЮ

□ ВРА

средние раэнордные

класс

Рис. 8

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

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

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

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

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

5. Разработано программное обеспечение полиномиального времени работы, реализующее предложенные алгоритмы. ПО позволяет за 0,5-10 минут находить рациональные упаковки для 20-100 различных ящиков.

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

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

1. Сурначев М.Ю., Собко С.Н. Гибридный группирующий генетический алгоритм для задачи упаковки // Моделирование, вычисления, проектирование в условиях неопределенноста-2000: Сб. науч. тр. Уфа: УГАТУ, 2000. С.458-459.

2. Мухачева A.C., Собко С.Н., Сурвачев М.Ю. Сравнение алгоритмов решения задач одномерного раскроя: метод последовательного улучшения опенок и гибридный группирующий генетический алгоритм // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2000. С.90-95.

3. Сурначев М.Ю., Собко С.Н. Гибридный группирующий генетический алгоритм // Дискретный анализ и исследование операций: Матер, конф. Новосибирск: Изд-во Института математики, 2002. С.237.

4. Сурначев М.Ю. Задача целочисленного линейного раскроя: обзор алгоритмов // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2002. C.I68-171.

5. Сурначев М.Ю., Собко С.Н. Гибридный группирующий генетический алгоритм // Математическое моделирование в решении научных и технических задач. Вып. 2. Уфа: Технология, 2001. С.70-75.

6. Собко С.Н., Сурначев М.Ю. Сравнение алгоритмов для решения задач одномерного раскроя. Гибридный группирующий генетический алгоритм и метод последовательного улучшения оценок // 0птим-2001: Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования. СПб: ЦНИИТС, 2001. С.137-140.

7. Гареев И.Р., Шнргазнн P.P., Собко С.Н., Сурначев М.Ю. Эвристики для задачи одномерной упаковки (1DBPP) // КНИТ'2001: Компьютерные науки и информационные технологии. Уфа: УГАТУ. С.263-267 (Статья на англ. языке).

8. Сурначев М.Ю. Задача параллелепипедной упаковки в контейнер: обзор методов решения // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2003. С.20&-211.

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

10. Сурначев М.Ю. Применение блочных технологий к задаче упаковки контейнера // Мехатроника, автоматизация, управление - 2005: Вторая Всероссийская научно-техническая конференция. Сб. тр. Т.2. Уфа: УГАТУ, 2005.

С.10-12.

Диссертант

Сурначев М.Ю.

СУРНАЧЕВ Максим Юрьевич

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

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

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

Подписано в печать 24.11.2005. Формат 60x84 V16 Бумага офсетная. Печать плоская. Гарнитура Times New Roman Cyr. Усл. печ. л. 1,0. Усл. кр. отт. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ Jfe 533.

ГОУВПО Уфимский государственный авиационный технический

университет Центр оперативной полиграфии УГАТУ 450000, Уфа-центр, ул. К.Маркса, 12

•25671

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

2006-4 28145

Введение.

1. Задачи раскроя-упаковки: аналитический обзор моделей и методов их решения.

1.1 Задача одномерного раскроя-упаковки. w 1.1.1 Методы, использующие математическое программирование.

1.1.2 Комбинаторные методы.

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

1.1.4 Методы локального поиска оптимума.

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

Актуальность проблемы. В научной и производственной деятельности часто встречаются ситуации раскроя и упаковки встречаются очень часто: это задачи раскроя материала на заготовки различных форм и размеров, и задачи размещения совокупности предметов на ограниченной площади или в ограниченном пространстве. Многие другие проблемы также сводятся к ситуациям раскроя и упаковки. Среди многообразия постановок задач раскроя и упаковки самостоятельный интерес представляют задачи упаковки параллелепипедов (3DBPP). К таким задачам относятся, например, оптимизация перевозки и складирования грузов, планирование помещений, проектирование систем, конструктивно выполненных в виде набора блоков, компоновка деталей. К рассматриваемым проблемам сводится также и ряд задач планирования и распределения ресурсов. Несмотря на конкретное практическое применение, круг работ по решению задач параллелепипедной упаковки невелик. Это объясняется сложностью задач и высокой трудоемкостью их решения. Поэтому является актуальной разработка, эффективных алгоритмов решения задач раскроя-упаковки параллелепипедов.

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

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

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

Задачи, поставленные для достижения цели работы:

1. Рассмотреть постановки основных задач трехмерной упаковки, описать их математические модели;

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

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

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

5. Разработать программное обеспечение, реализующее предложенные методы и алгоритмы;

6. Провести численный эксперимент с целью исследования эффективности предложенных алгоритмов.

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

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

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

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

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

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

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

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

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

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

4. Адаптация эволюционных алгоритмов - метода случайных перестановок, (J+1J-EA и генетического алгоритма для задач упаковки контейнера на базе блочного декодера.

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

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

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

1. Международная научная конференция "Моделирование, вычисления, проектирование в условиях неопределенности-2000" (Уфа, 2000).

2. Студенческая научно-теоретическая конференция 2001 (Уфа, 2001)

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

4. CSIT'2001: Computer Science and Informational Technologies (Уфа, 2001);

5. Вторая Всероссийская научно-техническая конференция «Мехатроника, автоматизация, управление - 2005» (Уфа, 2005).

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

По теме диссертации опубликовано 10 работ: 6 статей и 4 трудов конференций.

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

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

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

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

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

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

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

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

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

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

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

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

5. Разработано программное обеспечение полиномиального времени работы, реализующее предложенные алгоритмы. ПО позволяет за 0,5-10 минут находить рациональные упаковки для 20-100 различных ящиков.

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15. Мухачева А.С., Валеева А.Ф., Картак В.М. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. М.: МАИ, 2004, 193 с.

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

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

18. Мухачева А.С., Сурначев М.Ю. Задача параллелепипедной упаковки: декодер на базе блочных структур // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2005. С.51-55.

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

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

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

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

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

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

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

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

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

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

29. Сборник трудов ВНИИСИ "Модели и методы оптимизации" М., 1980, № 3. С.352.

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

31. Сурначев М.Ю. Задача параллелепипедной упаковки в контейнер: обзор методов решения. // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2003. С.208-211.

32. Сурначев М.Ю. Задача целочисленного линейного раскроя: обзор алгоритмов. // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2002. С. 168-171.

33. Сурначев М.Ю. Применение блочных технологий к задаче упаковки контейнера // Мехатроника, автоматизация, управление 2005: Вторая Всероссийская научно-техническая конференция. Сб. тр. Т.2. Уфа: УГАТУ. С.10-12.

34. Сурначев М.Ю., Собко С.Н. Гибридный группирующий генетический алгоритм для задачи упаковки. // Моделирование, вычисления, проектирование в условиях неопределенности-2000: Сб.науч.тр. Уфа: УГАТУ, 2000. С.458-459.

35. Сурначев М.Ю., Собко С.Н. Гибридный группирующий генетический алгоритм. // Дискретный анализ и исследование операций: Матер, конф. Новосибирск: Изд-во Института математики, 2002. С.237.

36. Сурначев М.Ю., Собко С.Н. Гибридный группирующий генетический алгоритм. // Математическое моделирование в решении научных и технических задач. Выпуск 2. Уфа: Изд-во "Технология", 2001. С.70-75.

37. Тоцков И.Е. Методы решения задачи трехмерной упаковки на базе алгоритма динамического перебора. Рукопись депонирована в ВИНИТИ, № 2589-В99, 1999.

38. Шабрина JI.M. К разработке линейного алгоритма решения задачи трехмерной упаковки// Математическое моделирование в решении научных и технических задач. Уфа, 1994. С.3-5.

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

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

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. Bischoff E.E., Marriott M.D. A comparative evaluation of heuristics for container loading // European Journal of Operation Research, 44(1990). P.267-276.

43. Bortfeldt A., Gehring H., Applying tabu search to container loading problems // Operations Research Proceedings 1997, Springer, Berlin, 1998, P.533-538.

44. Bortfeldt A., Gehring H. A hybrid genetic algorithm for the container loading problem. // European Journal of Operation Research, 131(2001). P.143-161.

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

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

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

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

49. Folkenauer E. The grouping genetic algorithms for Bin-Packing. JORBEL-Belgian Journal of operations Research, Statistics and Computer Science, 1995. V. 35. P.64-88.

50. Gehring H., Bortfeldt A. Genetic algorithm for solving the container loading problem. // International Transactions in Operation Research 4(5-6). P.401-418.

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

52. Gilmore P.C., Gomory R.E. Multistage cutting stock problems of two and more dimensions // Operation Research, 13(1965). P.94-120.

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

54. I.R. Gareev, R.R. Shirgasin, S.N. Sobko, M.Yu. Surnachev. Heurisms for One-Dimensional Bin-Packing Problem // CSIT'2001: Computer Science and Informational Technologies. Ufa: USATU Publishers. - P.263-267.

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

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

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

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

59. Martello S. and Toth P. Knapsack problems: Algorithms and Computer Implementations. In: Operations Research. 1990. v. 32. P.983-998.

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

61. Martello S., Pisinger D., Vigo D., The three-dimensional bin packing problem, Operations Research 48 (2000). P.256-267.

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

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

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

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

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

67. Pisinger D. Heuristic for the container loading problem // European Journal of Operation Research, 141(2002). P.3 82-392.

68. Rehtenberg I., Evolutionsstrategie: Optimerung Technischer systeme nach Prinzipen der Biologischen Evolution // Stuttgart: Formann-Holzboog Verlag, 1973.

69. Scheithauer G. and Terno J. A Branch-and-Bound Algorithm for Solving One- dimensional Cutting Stock Problems Exactly, Applicationes Mathematicae, 23.2:151-167, 1995.

70. Scheithauer G. and Terno J. About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem. Oper. Res. Proc. 1991, Springer-Verlag, Berlin Heidelberg, P.439-444.

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

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

73. Valeyeva A.F. and Totskov I.E. Developed of Three-Dimensional Methods Decision Making under Conditions of Uncertainty (Cutting-Packing Problems). Ufa, 1998.- P.198-206.

74. 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.l 10-114.

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

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