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

004604048

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОСС1ШСКОЙ ФЕГ[ЕРАЦГНI

НОВОС11Б1 1РСКПЙ ГОСУДАРСТВЕННЫЙ УННВЕРС11ТЕТ

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

РУДНЕВ Антон Сергеевич

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

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

АВТОРЕФЕРАТ

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

Новосибирск — '2010

1 7 ИЮН 2010

004604048

Работа выполнена в Государственном общеобразовательном учреждении высшего профессионального образования «Новосибирский государственный университет» на Кафедре теоретической кибернетики.

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

доцент Кочетов Юрт"! Андреевич

Официальные оппоненты: доктор технических наук.

профессор Родионов Алексеи Сергеевич

кандидат физико-математических наук, доцент Еремеев Антон Валентинович

Ведущая организация: Учреждение Российской академии паук-

Институт динамики систем и теории управления СО РАН

Защита состои тся 24 июня 2010 г. в 16 час. 00 мни. на заседании диссертационного совета Д 003.001.02 при Учреждении Российской академии наук Институте вычислительной математики и математической геофизики СО РАН по адресу: 030090. Новосибирск, пр. Академика Лаврентьева, 6.

С диссертацией можно (.»знакомиться в библиотеке Учреждения Российской академии наук Института вычислительной математики и математической геофизики СО РАН.

Автореферат разослан 2-1 мая 2010 г.

Ученый секретарь диссерта Ц1 юнного совета Д 003.001.02 при Учреждении Российской академии паук ИВМн.МГ СО РАИ, д.ф.-м.н.

С. Б. Сорокин

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

Актуальность проблемы. Задачи раскроя-упаковкп занимают важное место ]'. современной комбинаторно!! оптимизации и привлекают внимание многих ученых как в России, так и зарубежом. Международная группа IiSICl.JP объединяет исследователе!"!, занимающихся задачами раскроя-упаковки, но всему миру. В настоящее время она. насчитывает около пятисот участников, среди которых стоит отметить уфимскую школу под руководством профессора Э. А. Мухачевой п харьковскую школу профессора К). Г. Стояпа.

Интерес к задачам раскроя-упаковки объясняется. I» частности, их большой практической значимостью. Как правило приложения задач раскроя-упаковки относятся к магерпалоемкнм производствам, где одним из основных факторов снижения себестоимости выпускаемой продукции является рациональное использование ресурсов. На заре исследования этой проблемы Л. В. Канторовичем н В. А. Залгаллером было предложено использовать линейное программирование с неявно заданной матрицей ограничений. что позволило успешно решить важные производственные задачи. На сегодняшний день для решения задач раскроя-упаковки используются различные оптимизационные алгоритмы. В. М. Картаком и Э. А. Мухачевоп разработай метод ветвей и границ для решения одномерной задачи упаковки в контейнеры. В работах Э. X. Гнмадн и В. В. Залкяювского рассматриваются асимптотически точные алгоритмы. Для решения задачи гильотинной прямоугольной упаковки в контейнеры М. И. Свпрпденко была предложена, асимп готическая полиномиальная агшрокснмационная схема. Задачи раскроя-унаковкн относятся к классу МР-трудных задач комбинаторной оптимизации. Многие из них являются КР-трудными в сильном смысле. В связи с этим большое значение приобретает разработка и исследование итерационных методов решения задач раскроя-упаковки, в том числе и методов локального поиска, хорошо зарекомендовавших себя на практике.

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

В соответствии с целью исследования были поставлены и выполнены ( лед у roiji.ii е • ¡ада > I и:

1. Формулировка, рассматриваемых задач раскроя-упаковки в терминах математического программирования и оценка эффективноеги точных методов их решения;

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

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

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

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

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

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

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

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

I 1еслед<шан ионий класс задач прямоугольной упаковки в контейнеры с запрещенными областями. Получены математические модели н терминах частично-целочисленного программирования. Для решения задач разработаны новые кодирующие схемы. На их основе разработан модифицированный алгоритм имитации отжига, позволяющий решать четыре тина задач с запрещенными областями. Экспериментально установлено, что алгоритм позволяет находить решения с малой погрешностью, и том числе и оптимальные решения на примерах с числом предметов до 120.

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

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

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

• Российская конференция «Дискретным анализ и исследование операций^, г. Новосибирск. 2001;

• Международный симпозиум по исследованию операций (СШ). г. Бремен. 2005. г. Карлсруэ, 2006 и г. Аугсбург. 2008;

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

• Азиатская международная школа-семинар «Проблемы оптимизации сложных систем», г. Новосибирск. 2006 и п. Чемал. 2008;

• .\ 1еждунароцная школа-семинар по раскрою и упаковке (ЕЗЮОР). т. Токио. 2007;

• Российская конференция «Математика в современном мире», г. Новосибирск, 2007;

• Байкальская международная школа-семинар «Методы оптимизации и их приложения», г. Северобайкальек, 2008;

• Научные семинары Института математики СО РАН.

Публикации. По теме диссертации опубликовано 11 работ, в том числе 1 статья в рецензируемом журнале из списка ВАК.

Структура и объем диссертации. Диссертация состоит из введения, трех глав п 'заключения. Объем работы составляет 104 страницы машинописного текста, включая 23 рисунка. 10 таблиц и библиографический список, содержащий 75 наименований.

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

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

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

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

В разд. 1.2 приводится математическая постановка задачи. Обозначим исходные данные следующим образом: / — {1.2.....//} — множеств,о прямо,'угольников, 'с, и ■< е I — ширина и высота /-го прямоугольника. Введем переменные: х,- и //, — координаты левого нижнего угла, /-го прямоугольника. И-' и Я — ширина, и высота окаймляющего прямоугольника.

Переменная /,, с. {0.1} равняется единице, есдп i-ii прямоугольник находится левее .у-го, п нулю в противном случае. Аналогично переменная l>, I £ {0. I} равняется единице, если ¡■-и прямоуголышк находится ниже ./го. и нулю в противном случае. С использованием введенных обозначений исследуемая задача может быть представлена следующим образом:

miii \\'Н

При ограничениях на размеры окаймляющего прямоугольника: г, > 0. и, > 0. хf + w, < И'. ;/, + h, < Н. i £ I.

II ограничениях, исключающих пересечения прямоугольников:

и

.г, -I- и:, < X:i + (1 - /,,) £ «7,. г. j е 1.

к = 1 и

П. + < ill + (1 - М Е j € /.

А=1

I,, + /„ + />„■ +/>„• = 1, i.jei.

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

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

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

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

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

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

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

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

В разд. 2.] приводится содержательная постановка-задачи. Описываются результаты, полученные для задач, близких к рассматриваемым.

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

Теорема 2.2 Задачи ЁВР/О/С и 2ВР/Я/С с лапрещешшми областями могут быть сформулированы в терминах част-ично-целочисленного квадратичного программирования с линейной целевой функцией.

Доказательство. Обозначим исходные данные задачи: I = {1.2.....7*}

— предметы; а:, и 1ц. / е / •— ширина и высота ¿-го предмета: параметр </, равняется единице, если /-и предмет может пересекаться с запрещенными областями, и нулю иначе; Л/ = А^иА/з — контейнеры; АД = {1.2,..../} -контейнеры с запрещенными областям: А/г = {1,2.....а} — дополнительные одинаковые контейнеры без запрещенных областей, имеющие доета-

точные размеры, чтобы вместить самый большой предмет; IV',,, и В,„. >и

М - ширина и высота »1-го контейнера: — {'1.2.....К\ — запрещенные

области: х)'., //¡' и //•{'. Ь". к £ Iй — координаты и размеры запрещенных областей соответственно: параметр '/а„, равняется единице, если к-я запрещенная область находится в т-м контейнере, н нулю в противном случае.

Рис. 1. Матрица, гильотинного раскроя

Представим рекурсивный процесс разрезания прямоугольного контейнера. на. v предметов г. виде ,матрицы п х п, изображенной на рис. 1. Все элементы матрицы над главной диагональю тождественно равны нулю. Каждому ненулевому элементу соответствует некоторая прямоугольная область, имеющая свои координаты и размеры. Элементу пц соответствует сам прямоугольный контейнер. Процесс гильотинного раскроя можно представить г. виде последовательности переходов от первой строки матрицы ко второй, третьей и т.д. Г1рп каждом переходе совершается разрез одной из областей предыдущей строки на две части. Одна часть сохраняется а следующей строке на месте выбранной области, другая добавляется в качестве новой, увеличивая количество элементов-областей на единицу. Чтобы получить п предметов, необходимо сдела ть п — 1 разрез.

В последней строке получаем п областей a,~, i.....каждая из которых

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

Введем переменные: х, и //, — координаты левого нижнего угла /'-го предмета: ■"., С {0. 1} принимает значение 1, если /-п предмет повернут на

90°, и значение (I иначе; Л'^у. У"', П"(;. Я,-'-. i,j £ I — координаты и размеры прямоугольных областей, соответствующих элементам матриц, гильотинного раскроя: сf" € {0,1}, 1 < j < i < п — Х. т б М принимает значение 1. если при раскрое т-го контейнера i-м разрезом разрезается j-я область, при этом разрез горизонтальный, и значение 0 иначе: v"j <= {U, 1} -- аналогичная переменная для вертикальных разрезов; .s"' принимает значение, равное длине отрезаемой -г'-м разрезом части при раскрое m-го контейнера: г"' е {П. 1}. i. j £ /. m € Л/, принимает значение 1, если /'-й предмет в т-м контейнер: занимает j-ю область, п значение 0 в противном случае; bfl„ ЬЦ, ЬЦ, Ь]),- ' El. /•' £ /" принимают значение 1. если г-н предмет находится левее, правее, ниже, либо выше к-и запрещенной области, и значение 0 иначе: и,,, £ {(). L} принимает значение 1. если в т-й контейнер используется, и значение 0 иначе. Целевая функция примет вид:

Ij-n

min V^ </„■,.

и 1=3

Зададим порядок использования контейнеров от первого к последнему: "ш > ulll + i. т £ М.

Контейнер используется, если в нем содержится хотя бы один предмет:

и, „п > У г"', т е М.

Каждый предмет находится только в одной области одного из контейнеров:

Е Е '■::; - i. <■ ¡.

В каждой области находится не более одного предмета:

Е '1" < ./ € I. т £ М.

/ = 1 '

Элементам «и матриц гильотинного раскроя присваиваются параметры контейнеров:

X'l'i = 0. W"[ = «,„irm. т £ М.

Т"\ = 0. Н'п = и1пн,„. m € М.

При переходе на новую строку в матрице гильотинного раскроя совершается не более одного разреза:

Е (&"?' + '< "/) < и">- 1 <t< II - L m £ М.

)=1

I 1оелс каждого разреза координаты и размеры прямоугольных <юла-е'1011 преобразуются следующим образом:

-С,.,

-г;;.

= п;;

= н""

1 < ./ < ¡'_L-.II— I . III ь Л/,

1 < .у < ' < » - 1- 'и е А/,

Г> результате разреза добавляется новая область:

А-;:; ,- ± (« +г»'):У:'; + <тг;'; ,.,). !<;<»-1.,,,6 м.

/.-г-1 ■

у"'п - = Е (« + +<77;"!.,.). I < 1 п - I- е м.

,-и = Е + «■•;;'«;")• | • • » • I.»»с м.

й"!,- Е ('•¡"Ж", +!/,",*',")■ 1 < ; < п -1. /и ^ л/.

Каждый предмет размещается в области допустимого размера. 'Адесь 11, п Я,,,,,., — максимальная ширина и максимальная высота контейнеров:

.г, > г;;, - (I - ё '"¡)и'">"■>■• ' ^ '" е

/=1

//; - П - Ё , с /. и» £ .1/.

<еЛ1 - :,')+ < ТГ'^ + (1 - ¿''"Л"'»»,.,, ' € I. ш £ А/.

7=1

/,,(1 - :,■) 4 «•,--, < //;;, + (1 - ё '■;';)#<"<"■■ '6 ше л/Последняя группа ограничений исключает пересечения предметов и запрещенных областей, находящихся в одном контейнере, в случаях когда это недопустимо:

г, + »',(1 - :,! +■ //,=, < 4 + (1 - '4)1Г......,.. / 6 /. /.' € /".

4 + < + (1-/^)1г„„,,. ' /. к е /",

„, +/,,(!-.:;) -г (Г, 0, < ^ + (1 - /.,'•)//.....,.. / е /. к е У".

.'/!' + /''/ •: </,+ (I '<;)//,„,,. , £1. к

а

/4 + + + ЬД > Е >1" + яьп - 4 - 1, ¿6 I. к 6 Г. € А/. 1

Выписанные условия определяют неориентированную задачу с гильотинными разрезами 2BP|R|G. Аналогично при ц ~ 0 формулируется ориентированная задача 2BP|0|G. □

Задача прямоугольной упаковки с гильотинными разрезами впервые формулируется в терминах частично-целочисленного квадратичного программирования. В разделе также формулируются задачи 2BP|0|F и 2BP|R|F с запрещенными областями в терминах частично-целочисленного линейного программирования

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

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

В разд. 2.5 приводится модифицированный алгоритм имитации отжига. Пусть число контейнеров в начальном решении равняется т. и содержимое каждого контейнера представлено в закодированном виде S¡. I. < / < т. Оптимизация делится на два уровня. На первом уровне с помощью локального поиска осуществляется независимая упаковка предметов в каждом контейнере. В качестве целевой функции выступает высота упаковки контейнера F[S,). Процесс поиска идет в области допустимых и недопустимых решений, когда предметы могут выступать за г раницы контейнера. В этом случае в целевую функцию добавляется штраф. Второй уровень — выполнение алгоритма РАЗГРУЗКА, выполняющего функцию уплотнения. Критерием остановки алгоритма служит количество итераций. либо время работы. Общая схема алгоритма представлена ниже:

1. Построить начальное решение ,S'i.....S„>.

2. Задать начальную температуру Г > 0.

3. Повторять, пока не выполнен критерий остановки.

Никол нить цикл заданное число раз для j-го контейнера 1 < j < ш.

.11.1. Выбрать случайного соседа S'j из окрестности решения Sj.

.'{.1.2. Если F(S'j)- F(Sj) < 0. то S¡ := S'¡.

1 ..'5. Ксли > Оло с вероятностью/ --т--

.4.2. Понизить температуру Т :— г'Г. 3.3. Выполни гь алгоритм РАЗГРУЗКА.

I. Выдать лучшее найденное решение.

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

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

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

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

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

В разд. 3.2 приводится постановка задачи в терминах частпчно-целочпелеиного квадра тичного программирования. Обозначим исходные данные задачи: И' — ширина, полосы; I — {1.2.....и,. } — множество кругов: I — {1.2.....//,.} •- множество прямоугольников: /-,. ] £ I. - радиус

1-го круга.; /у и «г;. ] 6 ./ — длина и ширина ./-го прямоугольники.

Введем переменные: ,г'( и у]' — координаты центра, /-го круга: хг и у' — координаты левого нижнего угла. ;-го прямоугольника; переменная

6 {0.1 } равняется единице, если ./'-й прямоугольник повернут на 90е, и нулю в противном случае; переменная е {0. 1}. ¡,т £ ./ равняется единице, если /-и прямоугольник находится левее ///-го. и нулю иначе; аналогично переменная а®„ € {0.1} равняется единице, если _/-й прямоугольник находится ниже т-го. и нулю иначе. В качестве целевой функции выступает длина. занятой части полосы тш£, которая определяется с помощью ограничений:

+ 1-, < I. I 6 /. х', + /,(1 - + < е .7.

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

.г';' - г, >0. I е I. у) - г, > 0. i G I. Vj + Г, < IV. i 6 I.

Выпишем аналогичные ограничения для прямоугольников:

•»•• г 0. J € .1. y'j ■> о, j е J. y'j + wj(i - с,) + /я.; < И'. J е J.

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

(•'•;■ - ->i)2 + (v'i - y'k)J > (г, + rfc)2. i.h G I.

Следующая группа ограничений исключает пересечения прямоугольников между собой. Здесь L,„„.,• — достаточно большое число, £„,„,,. > L:

■>■', +1.,{ 1 - ;,) + < + (] - »> е J.

?/'у + (1 - =j) + Ijzj < !/'w + (1 - a%,)W. j. m G J.

"■>„, +«-5m +"n,:l = 1- J.me J.

Последняя группа ограничений исключает пересечения кругов и прямоугольников. Круг > не пересекается с прямоугольником ./, если точка «.(/•) лежит вне фигуры, которую очерчивает центр круга при движении круга по периметру прямоугольника. Переменные К 4 £ {0.1} используются для реализации дизъюнкции неравенств.:

< + 'V < -т', + (1 - ,,„,/•

,г'( + /у( I - .:,-) 4- /с,-с.у < .Ту - г, + (1 - b'fj)Lmt,x.

У, <у',

v'j +- "'л' - --.,) + <+ (1 -

v: L

Г-Л

.г; < -f (1 - cl^Lmux-

r'; + //(1 - = ,) + < .су + (1 - cj:j)L,nar.

!/; +-;-. <«; + (.] <•;',! IV.

.(/; f ii'y ( 1 - Су) 4 IjZ, < y\ - V j + (1 - cf.,)W,

Я " '•

и; - (< + ',U - + »',-,)У + Ы - y'j)2 ^ (•'•: - + Ы - (tf + ^d -=.,■) + /,.-,))2 > rf.

G I. j e

e /. G

g /. J G

G /. j € .7.

G /, J £

G /. .7 G ■A

G /, j G J.

G /. £ J,

G /. j e ./.

G /. j G J.

G /. :i g J.

G ./ G J.

G L j e J.

+ - :,) + '.,-,) Г > rf. i С l. j •/.

В разд. 3.3 ыюдится понятие двухконтактпой схемы кодирования: предметы упаковываются в полосу в заданном порядке так. чтобы каждый следующий предмет имел как минимум две точки касания с уже упакованными предметами, либо границами полосы. Предлагается двухконтактная кодировка с трудоемкостью декодирования ()(/»') и мощностью />!, где и — число предметов. Доказывается следующая теорема

Теорема 3.1 Существует семейство входных данных задачи упаковки кругон (V полосу лигнимильпоу, длины, на которых множество дьух-кон.такптых решети'/ не содержит оптимум.

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

В разд. З.-l определяется окрестность квадратичной мощности.

В разд. о.Г) описывается разработанный алгоритм вероятностного поиска с запретами. Алгоритм осуществляет вероятностный локальный попек по рандомизированной окрестности Л'я(й-) Я где каждый элемент

окрестности .V(ü-) решения ?/,. включается в множество Л7> ('/..) с вероятностью 0 < /' < I независимо от других элементов. Основным механизмом, позволяющим алгоритму покидать локальные оптнмумы. является список запретов TABU/(а-), который строится по предыстории поиска п запрещает часть окрестности Л'('/, ) текущего решения. Длина списка запретов определяется параметром I > I) и показывает максимальное количество элементов, которое может содержаться в списке. На каждом .шаге алгоритма очередная точка, /дчл является оптимальным решением подзадачи /,(//,.., ]) = min{X,(,/') | j € Arp(ü-)\TABU/(ü)}, где L(i) - длина полосы. Ниже представлена общая схема алгоритма:

1. Построить начальное решение /о-

2. Положить TABU/(¿(0 := 0, Г := m.L' := К Г). Г := /о, L' := !(/"'), к := 0.

Р :■= Рты. «gl» : = 1.

3. Повторят ь, пока не выполнен критерий остановки.

.4.1. ВЫПОЛНИТЬ ЦИКЛ Nfoop Р<1-3.

.'(.1.1. Сформировать окрестность Аг;> (?'/.•)•

3.1.2. ПаГттп 'такое, что } = min Ц /').

? V) -'' I. !' ГА 13 11, 1 ,. ¡. ! "'

.4.1.3. Вели // > /.(//,.-]-■ 1). то L" :■-■ Цп-i-i) 11 ' '/. н-

3.1 .-I. Вели V Lttitn). то /.' /.(//,..ц). /'' //, + 1 и sgn :- 1.

3.1.Г). Положить к := к + I и обновить TABUi(u-).

3.2. Если sgn = 1, то и := Г.

Н.З. Положить Р := Р + кцп • ДР.

•4.1. Если Р > Ртах- ГО вйП := —1.

,4.5. Если Р < Р,ш„, то ^п := 1, V := Ци ) и Г : = и-.

4. Выдать результат Г и

Параметры Рг„ш, Рин.х — верхняя и нижняя границы параметра рандомизации. АР — величина изменения параметра рандомизации, I — длина списка запретов и ЛГ|,Ю|1 — количество итераций локального поиска при фиксированной рандомизации являются заданными. Выполнение алгоритма начинается с построения начального решения и присвоения начальных' значении внутренним переменным, которыми являются к номер итерации алгоритма, /д. — текущее решение, ТАВЩп-) -• список запретов па /,--й итерации. Р — параметр рандомизации окрестности, sgn £ {-1.+1} — убывание или возрастание параметра рандомизации, Г, /.' — лучшее найденное решение и значение целевой функции для него и аналогично Г. I.' — лучшее найденное решение при фиксированном значении параметра Р и значение целевой функции для него. Далее происходит локальный попек с запретами по рандомизированной окрестности Л'/'(')\ТАР>и;(7). В процессе поиска параметр рандомизации меняется в

пределах ¡Рт-„,.....Ртах| на величину АР в зависимости от тою, как часто

встречаются решения с малой относительной погрешностью. Таким способом осуществляется интенсификация п диверсификация поиска. В начале работы алгоритма Р принимает минимальное значение Р,т„. Алгоритм выполняет заданное число ЛГ|„,,,, шагов локального поиска при фиксированном значении Р и запоминает наилучшее найденное решение для него. В что решение алгоритм возвращается при последующем увеличении значения параметра. Р. Таким образом, увеличивая долю просматриваемой окрестности, и возвращаясь в наилучшее найденное на предыдущем этапе решение, реализуется интенсификация поиска. Другими словами, алгоритм осуществляет более детальный поиск в окрестности лучших, ранее найденных решений. Действия повторяются до тех пор. пока значение параметра Р не достигнет максимального значения Ршах. Затем доля просматриваемой окрестности начинает уменьшаться, п алгоритм переходит в фазу диверсификации, пытаясь перейти в новую область пространства решений. Если в процессе диверсификации удается найти решение лучше, чем ¡'. то алгоритм начинает интенсификацию поиска, запомнив это решение как /'. Этап диверсификации длится до тех пор, пока параметр Р не достигнет минимального значения Ршц,. Критерием остановки алгоритма служит число итераций, либо время работы.

Разд. ').(> содержит результаты численных экспериментов. Исследуется

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

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

[1] Руднев А. С. Вероятностный поиск с запретами для задачи упаковки кругов п прямоугольников в полосу .'/ Дискретный анализ и исследование операций. — 200!). — Т. 1С. № -1. — (Л (И—N0.

|2] Кочапоч Ю. .4.. Руднев А. С. Алгоритм ими тации отжига для задач прямоугольной упаковки Материалы конференции «Дискретный анализ и исследование операций». — Новосибирск: Пзд-во Пн-га математики. 2004. - С. 187.

[3] Руднев А. С. Алгоритм имитации отжига для задачи упаковки кругов п прямоугольников в контейнеры // Материалы конференции «Дискретная оптимизация и исследование операций». — Новосибирск: Изд-во Ий-га математики. 2007. •- С. 150.

[-1] Р¡¡днем А. С. Алгоритм имитации отжига для упаковки кругов и пря моугольников на. плоскости , ' Материалы конференции «Математика в современном мире». — Новосибирск: Пзд-во Ин-та математики. 2007. - С. 284.

|5] Pydnc.it А. С. Вероятностный попек с запретами для задачи упаковки кругов и прямоугольников в полосу 7 Труды XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения». Иркутск: Изд-во Ин-та систем энергетики, 2008. Т. 1. — Г. 521-52!).

|С>] Руднев А. С. Задачи двумерной прямоугольной упаковки с запрещенными областями Труды ИВМиМГ СО РАН. Сер. Информатика. -Новосибирск: Изд-во ИВМиМГ СО РАН. 2000. - Вып. Г». - С. 156102.

[7] Руднев А. С. Прямоугольная упаковка в полосу с запрещенными областями ■ / Материалы конференции «Проблемы оптимизации и экономические приложения». — Омск: Изд-во ОмГТУ, 2006. — С. 120.

[8] BcmegelB., KaUrath J., Kochc.tov Y., RudncvA. Efficient encoding schemes for rectangular packing with impurities // Abstracts of international conference on operations research. — Karlsruhe, 2000. — P. Г>0.

|9| BeishytlВ.. Kulhuth./.. Kochetor Y.. Rutincv A. Simulated annealing based algorithm for the 2D bin packing problem with impurities Operations research proceedings. 2005. — Heidelberg: Springer, 2006. — P. 109-1 Ki.

[10] Kallrath J., Koche.tov Y., RudnevA. Probabilistic tabu search for packing circles and rectangles into the strip / ■ Abstracts of international conference on operations research and global business. — Augsburg, 2008. - P. 197.

[11] Kallrath J., KoiJuitov )".. RudncvA. Strip packing problem for circles and rectangles - Abstracts of international conference on cutt ing and packing problems «4l.li ES1CUP Meeting». - Tokyo, 2007. - P. 20.

РУДНЕВ Антон Сергеевич

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

Автореферат диссертации

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

Подписано в печать 12.05.2010. Формат 60x84 1 /1С. Усл. печ. л. 1.0. Уч.-изд. л. 1.0. Тираж 110 экз. Заказ X« 60.

Отпечатано в ООО «Омега Принт» пр. Ак. Лаврентьева, 6. 630090. Новосибирск

Введение

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

1.1 Введение.

1.2 Математическая постановка задачи

1 3 Решение задачи с помощью коммерческого пакета.

1 4 Кодирующая схема Ориентированное дерево.

1 5 Кодирование ориентированных деревьев.

1.6 Окрестность.

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

1.7.1 Алгоритм локального спуска.

1.7.2 Алгоритм имитации отжига.

1.7.3 Диверсификация поиска.

1.7.4 Гибридный алгоритм.

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

1.8 1 Влияние диверсификации поиска.

1.8.2 Гибридный алгоритм с диверсификацией поиска . 37 1.9 Выводы к главе 1.

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

д

2.2 Математические постановки задач.42

2.3 Кодирующие схемы .48

2.4 Окрестность.52

2.5 Модифицированный алгоритм имитации отжига.54

2.6 Начальное решение.56

2.7 Алгоритм РАЗГРУЗКА.58

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

2.8.1 Примеры прямоугольной упаковки с запрещенными областями.59

2.8.2 Примеры классической прямоугольной упаковки . 60

2.8.3 Использование пакета GAMS.66

2.9 Выводы к главе 2.68

3 Алгоритм вероятностного поиска с запретами для задачи упаковки кругов и прямоугольников в полосу ТО

3.1 Введение.70

3.2 Математическая постановка задачи .73

3.3 Двухконтактные кодировки.76

3.4 Окрестность.80

3.5 Алгоритм вероятностного поиска с запретами .80

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

3.6.1 Влияние рандомизации и длины списка запретов . . . 84

3.6.2 Упаковка кругов и прямоугольников.87

3.6.3 Использование пакета GAMS.92

3.7 Выводы к главе 3.95

Заключение 96

Список литературы 97

Введение

Актуальность проблемы. Задачи раскроя-упаковки занимают важное место в современной комбинаторной оптимизации и привлекают внимание многрк ученых как в России, так и зарубежом. Международная группа ЕЯЮиР объединяет исследователей, занимающихся задачами раскроя-упаковки, по всему миру. В настоящее время она насчитывает около пятисот участников, среди которых стоит отметить уфимскую школу под руководством профессора Э. А. Мухачевой и харьковскую школу профессора Ю. Г. Стояна.

Интерес к задачам раскроя-упаковки объясняется, в частности, их большой практической значимостью. Как правило приложения задач раскроя-упаковки относятся к материал о ем ким производствам, где одним из основных факторов снижения себестоимости выпускаемой продукции, является рациональное использование ресурсов. На заре исследования этой проблемы Л.В.Канторовичем и В. А. Залгаллером было предложено использовать линейное программирование с неявно заданной матрицей ограничений, что позволило успешно решить важные производственные задачи. На сегодняшний день для решения задач раскроя-упаковки используются раз-' личные оптимизационные алгоритмы. В.М. Картаком и Э. А. Мухачевой разработан метод ветвей и границ для решения одномерной задачи упаковки в контейнеры. В работах Э.Х. Гимади и В. В. Залюбовского рассматриваются асимптотически точные алгоритмы. Для решения задачи гильотинной прямоугольной упаковки в контейнеры М. И. Свириденко была предложена асимптотическая полиномиальная аппроксимационная схема. Задачи раскроя-упаковки относятся к классу МР-трудных задач комбинаторной оптимизации. Многие из них являются МР-трудными в сильном смысле. В связи с этим большое значение приобретает разработка и исследование итерационных методов решения задач раскроя-упаковки, в том числе и методов локального поиска, хорошо зарекомендовавших себя на практике.

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

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

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

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

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

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

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

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

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

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

Научная новизна работы. Для решения задачи упаковки прямоугольников в прямоугольную область минимальной площади предложен гибридный алгоритм имитации отжига, использующий новую процедуру уплотнения упаковки, аналогичную Т-поздним расписаниям в календарном планировании. В ходе вычислительных экспериментов с помощью разработанного алгоритма были найдены новые рекордные значения целевой функции для семи примеров из электронных библиотек МС1ЧС и С811С с числом предметов от 33 до 300.

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

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

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

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

• Российская конференция «Дискретный анализ и исследование операций», г. Новосибирск, 2004;

• Международный симпозиум по исследованию операций (СЖ), г. Бремен, 2005, г. Карлсруэ, 2006 и г. Аугсбург, 2008;

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

• Азиатская международная школа-семинар «Проблемы оптимизации сложных систем», г. Новосибирск, 2006 и п. Чемал, 2008;

• Международная школа-семинар по раскрою и упаковке (ЕЗЮИР), г. Токио, 2007;

• Российская конференция «Математика в современном мире», г. Новосибирск, 2007;

• Байкальская международная школа-семинар «Методы оптимизации и их приложения», г. Северобайкальск, 2008;

• Научные семинары Института математики СО РАН.

Публикации. По теме диссертации опубликовано 11 работ, в том числе 1 статья в рецензируемом журнале из списка ВАК.

Структура и объем работы. Диссертация состоит из введения, трех глав и заключения. Объем работы составляет 104 страницы машинописного текста, включая 23 рисунка, 16 таблиц и библиографический список, содержащий 75 наименования.

3.7 Выводы к главе 3

Рассмотрена задача упаковки кругов и прямоугольников в полосу. Выписаны математические постановки для общего и частных случаев задачи. Для решения задачи разработан алгоритм вероятностного поиска с запретами, использующий двухконтактную схему кодирования решений. Эта схема использует оригинальную процедуру декодирования, восстанавливающую упаковку предметов по заданному коду. Алгоритм осуществляет локальный поиск в пространстве двухконтактных решений с использованием процедур интенсификации и диверсификации, основанных на адаптивном изменении параметра рандомизации окрестности. Численные эксперименты показали, что алгоритм позволяет находить решения с малой погрешностью, в том числе и глобально оптимальные на примерах небольшой размерности. На известных тестовых примерах для частных случаев задачи алгоритм нашел новые рекордные значения целевой функции для четырех примеров упаковки кругов в полосу. Представляет интерес разработка новой, менее трудоемкой схемы кодирования, которая за фиксированное время позволит выполнить большее количество итераций. В качестве одного из вариантов интересно рассмотреть декодер с использованием контура частичной упаковки предметов. Подобная идея рассматривалась в работе [15] для задачи прямоугольной упаковки в контейнеры с запрещенными областями. Это бы позволило сократить трудоемкость декодирования на порядок и существенно ускорить работу алгоритма локального поиска, особенно, на примерах большой размерности.

Заключение

1. Для решения задачи упаковки прямоугольников в прямоугольную область минимальной площади предложен гибридный алгоритм имитации отжига, использующий новую процедуру уплотнения упаковки. В ходе вычислительных экспериментов с помощью разработанного алгоритма были найдены новые рекордные значения целевой функции для семи примеров из электронных библиотек МСЫС и СЭР^С с числом предметов от 33 до 300.

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

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

1. АбгарянК. К, Хачатуров В. Р. Компьютерное моделирование устойчивых структур кристаллических материалов / / Журнал вычислительной математики и математической физики — 2009. — Т. 49, № 8. С. 1517-1530.

2. Вайнштейн А. Д. Задачи об упаковке прямоугольников в полосу (обзор) // Управляемые системы. — 1984. — Вып. 25. — С. 17—37.

3. ВалееваА. Ф., Сиразетдинова Т. Ю. Алгоритмы решения задачи прямоугольного гильотинного раскроя на базе метаэвристики имитации отжига // Материалы конференции «Проблемы оптимизации и экономические приложения». — Омск- Изд-во ОмГТУ, 2006. — С. 126.

4. Гончаров Е. Н., Кочетов Ю. А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискретный анализ и исследование операций. Сер. 2. — 2002. — Т. 9, № 2. — С. 13—30.

5. ГэриМ. Р., Джонсон Д. С. Вычислительные машины и трудноре-шаемые задачи. — Москва: Мир, 1982. — 416 с.

6. Кочетов Ю. А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ по дискретной математике и ее приложениям. — М: МГУ, 2001, — С. 87-117.

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

8. МухачеваЭ. А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки // Материалы конференции

9. Дискретный анализ и исследование операций». — Новосибирск: Изд-во Ин-та математики, 2002. — С. 80-87.

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

11. Стрекаловский А. С. Элементы невыпуклой оптимизации. — Новосибирск: Наука, 2003. — 352 с.

12. Alvarez-Valdes R., ParrenoF., Tamarit J.M. Reactive GRASP for the strip packing problem // Comput. Oper. Res. — 2008. — Vol. 35, N 4.- P. 1065-1083.

13. ArayaL, NeveuB., RiffM. C. An efficient hyperheuristic for strip-packing problems // Studies in Comput. Intelligence. — 2008. — Vol. 136.- P. 61-76.

14. Baker B. S., CoffmanE. G., RivestR. L. Orthogonal packing in two dimensions // SIAM J. Compututing. 1980. Vol. 9, N 4. — P. 846-855.

15. BeisiegelB., KallrathJ., KochetovY., RudnevA. Simulated annealing based algorithm for the 2D bin packing problem with impurities // Proc. Operations Research, 2005. — Heidelberg: Springer, 2006. — P. 109-113.

16. BirginE. G., Martinez J. M., NishiharaF. H, RonconyD.P.

17. Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization // Comput. Oper. Res. — 2006. — Vol. 33. — P. 3535-3548.

18. Boschetti M. A., MingozziA. The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case // 40R. — 2003. -Vol.1. -P. 27-72.

19. BoschettiM. A., MingozziA. The two-dimensional finite bin packing problem. Part II: New lower and upper bounds // 40R. — 2003. — Vol. 1. P. 135-147.

20. Bortfeldt A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces // Europ. J. Oper. Res. — 2006. Vol. 172, N 3. P. 814-837.

21. Burke E., Kendall G., WhitwellG. Metaheuristic enhancements of the best-fit heuristic for the orthogonal stock cutting problem // Computer Science Technical Report No. NOTTCS-TR-2006-3, University of Nottingham, 2006. — 30 p.

22. ChanH. H., Markov I. L. Practical slicing and non-slicing block-packing without simulated annealing // Proc. Great Lakes Symposium on VLSI, 2004. New York: ACM, 2004. - P. 282-287.

23. Chang Y.C., ChangY.W., WuG.M., WuS.W. B*-trees: A new representation for non-slicing floorplan // Proc. DAC, 2000. — New York: ACM, 2000. P. 458-463.

24. ChazelleB. The bottom-left bin packing heuristic: An efficient implementation // IEEE Trans. Compututing. — 1983. Vol. 32. P. 697707.

25. ChungF. R. K., GareyM.R., JohnsonD. S. On packing two-dimensional bins // SIAM J. Algebraic Discrete Meth. — 1986. Vol. 3. — P. 66-76.

26. CoffmanE. G., GareyM.R., JohnsonD.S, TarjanR.E.

27. Performance bounds for level-oriented two-dimensional packing algorithms // SIAM J. Compututing. 1980. Vol. 9. - P. 801-826.

28. Dell'AmicoM., MartelloS., VigoD. A lower bound for the non-oriented two-dimensional bin packing problem // Discrete Appl. Math. — 2002. Vol. 118. - P.-13-24.

29. DongS., HongX., QiX., WangR., ChenS., GuJ. VLSI module placement with pre-placed modules and considering congestion usingsolution space smoothing // Proc. ASP-DAC, 2003. — New York: ACM, 2003. P. 741-744.

30. DongS., HongX., WuY., XiuZ., GuJ. VLSI placement with pre-placed modules based on less flexibility first principles // Proc. ASIC, 2001. Beijing: IEEE Press , 2001. - P. 106-109.

31. Dongarra J. J. Performance of various computers using standard linear equations software // Technical Report No. CS-89-85, University of Manchester, 2008. — 102 p.

32. DowslandK. A., DowslandW. B. Packing problems // Europ. J. Oper. Res. 1992. - Vol. 56. - R'2-14.

33. DreoJ., PetrowskiA., SiarryP., TaillardE. Metaheuristics for hard optimization: methods and case studies. — Berlin: Springer-Verl., 2005. — 369 p.

34. FeketeS.P., Schepers J. On more-dimensional packing II: Bounds // Technical Report No. 97.289, Universität zu Köln, 2000. — 20 p.

35. Gardner M. Some packing problems that cannot be solved by sitting on the suitcase // Scientific American — 1979. — Vol.-241, N 4. — P. 22-26.

36. George J. A., George J. M., Lamar B.W. Packing different-sized circles into a rectangular container // Europ. J. Oper. Res. — 1995. — Vol. 84. P. 693-712.

37. Glover F., LagunaM. Tabu search. — Dordrecht: Kluwer Acad. Publ., 1997. 382 p.

38. GuoP. N., Cheng C.K., YoshimuraT. An O-tree representation of non-slicing floorplan and its applications // Proc. DAC, 1999. — New York: ACM, 1999. P. 268-273.

39. Hifi M., M'HallahR. A hybrid algorithm for the two-dimensional layout problem: the cases of regular and irregular shapes // Internat. Transaction in Oper. Res. 2003. - Vol. 10. - P. 195-216.

40. HifiM.; M'HallahR. Approximate algorithms for constrained circular' cutting problems. // Comput. Oper. Res. — 2004. — Vol. 31. — P. 675-694.

41. HongX., HuangG., CaiY., GuJ., DongS., ChengC.K., GuJ.

42. Corner Block List: An effective and efficient topological representation of non-slicing fioorplan // Proc. ICCAD, 2000. — Piscataway: IEEE Press, 2000. P. 8-12

43. Hopper E., TurtonB. C. H. An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem // Europ. J. Oper. Res. 2001. - Vol. 128. - P. 34-57.

44. Huang W., ChenD., XuR. A new heuristic algorithm for rectangle packing // Comput. Oper. Res. 2007. - Vol. 34. - P. 3270-3280.

45. Huang W. Q., Li Y., Akeb H., Li C. M. Greedy algorithms for packing unequal circles into a rectangular container // J. Oper. Res. Soc. — 2005. -Vol. 56. P. 539-548.

46. Huang W. Q., LiY., LiC.M., XuR. C. New heuristics for packing unequal circles into a circular container // Comput. Oper. Res. — 2006. — Vol. 33. P. 2125-2142.

47. IbarakiT., ImahoriS., YagiuraM. Hybrid metaheuristics for packing problems // Studies in Comput. Intelligence. — 2008. — Vol. 114. — P. 185-219.

48. Iori M., Martello S., MonaciM. Metaheuristic algorithms for the strip packing problem, — Dordrecht: Kluwer Acad. Publ., 2003. — P. 159—179.

49. Johnson D. S., AragonC.R., McGeochL.A., SchevonC.

50. Optimization by simulated annealing: An experimental evaluation, part I (graph partitioning) // INFORMS Oper. Res. — 1989. — Vol. 7, N 6. P. 865-891.

51. JohnsonD. S., DemersA., UllmanJ.D., GareyM. R., Graham R. L. Worst-case performance bounds for simple one-dimensional packing algorithms // SIAM J. Compututing. — 1974. Vol. 3. P. 299-325.

52. Kallrath J. Cutting circles and polygons from area-minimizing rectangles // J. Global Optimization. 2009. - Vol. 43. - P. 299-328.

53. Kallrath J., Kochetov Y., Rudnev A. Strip packing problem for circles and rectangles // 4th ESICUP Meeting. — Tokyo: University of Tokyo, 2007. P. 20.

54. KenmochiM., ImamichiT., NonobeK., YagiuraM., NagamochiH. Exact algorithms for two-dimensional strip packing problem with and without rotations // Europ. J. Oper. Res. — 2009. — Vol. 198. P. 73-83.

55. KirkpatrickS., GelattC., VecchiM. Optimization by simulated annealing // Science. 1983. — Vol. 220. - P. 671-680.

56. LinJ.M., Chang Y. W. Corner sequence — a P-admissible floorplan representation with a worst case linear-time packing scheme // IEEE . Trans. Very Large Integration Systems. — 2003. — Vol. 11, N 4. — P. 679686.

57. LinJ.M., Chang Y. W. TCG: A transitive closure graph-based representation for non-slicing floorplans // Proc. DAC, 2001. — New York: ACM, 2001. P. 764-769.

58. LodiA., MartelloS., MonaciM. Two-dimensional packing problems: A survey // Europ. J. Oper. Res. — 2002. — Vol. 141. — P. 241-252.

59. LodiA., MartelloS., VigoD. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems // INFORMS J. Computing. 1999. - Vol. 11. — P. 345-357.

60. Lodi A., MartelloS., VigoD. Recent advances on two-dimensional bin packing problems // Discrete Appl. Math. — 2002. — Vol. 123/124. — P. 373-380.

61. Martin O. C., OttoS.W. Combining simulated annealing with local search heuristics // Technical Report No. CSE-94-016, Oregon Graduate. Institute School of Science and Engineering, 1993. — 15 p.

62. MurataH., FujiyoshiK., NakatakeS., KajitaniY. VLSI module placement based on rectangle-packing by the sequence-pair // IEEE Trans. Computer Aided Design. 1996. - Vol. 15, N 12. - P. 1518-1524.

63. MurataH., KuhE. S. Sequence-pair based placement method for hard/soft/pre-placed modules // Proc. international symposium on Physical design, 1998. — New York: ACM, 1998. — P. 167-172.

64. NakatakeS., FujiyoshiK., MurataH., KajitaniY. Module placement on BSC structure and IC layout applications // Proc. ICC AD, 1996. - Washington: IEEE Computer Society, 1996. — P. 484491

65. OrtmannF. G., NteneN., van Vuuren J. H. New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems // Europ. J. Opcr. Res. — 2010. Vol. 203, N 2. — P. 306-315.

66. Osmanl. H., Laporte G. Metaheuristics: A bibliography // Ann. Oper. Res. 1996. - Vol. 63 - P. 513-628.

67. PisingerD., Sigurd M. The two-dimensional bin packing problem with variable bin sizes and costs // Discrete Optimization. — 2005. — Vol. 2, N 2. P. 154-167.

68. SakanushiK., KajitaniY., MehtaD.P. The quarter-state-sequence fioorplan representation // IEEE Trans. Circuits and Systems. — 2003. — Vol. 50. P. 376-386.

69. Stoyan Y. G., Yaskov G. N. Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints // Int. Trans. Oper. Res. — 1998, — Vol. 5, N 1. P. 45-57.

70. Stoyan Y. G., Yaskov G.N. A mathematical model and a solution method for the problem of placing various-sized circles into a strip // Euiop. J. Oper. Res. 2004. — Vol. 156. - P. 590-600.

71. TakahashiT. A new encoding scheme for rectangle packing problem // Proc. ASP-DAC, 2000. New York: ACM, 2000. - P. 175-178.

72. TangX., TianR., WongD. F. Fast evaluation of sequence pair in block placement by longest common subsequence>computation // IEEE Trans. Computer Aided Design of Integrated Circuits and Systems. — 2001. — Vol. 20. P. 1406-1413.

73. TangX., TianR., WongD. F. Fast-SP: A fast algorithm for block placement based on sequence-pair // Proc. ASP-DAC, 2001. — New York: ACM/2001. P. 521-526.

74. WongD. F., LiuC.L. A new algorithm for floorplan design // Proc. DAC, 1986. Piscataway: IEEE Press, 1986. — P. 101-107.

75. Wu Y. L., Huang W., LauS., Wong C. K., Young G. H. An effective quasi-human based heuristic for solving the rectangle packing problem // Europ. J. Oper. Res. 2002. - Vol. 141. - P. 341-358.

76. YongF.Y., WongD. F. Slicing floorplans with pre-placed modules // Proc. ICCAD, 1998. New York: ACM, 1998. - P. 252-258.

77. Zhang D.F., ChenS. D., Liu Y.J. An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem , / Automatic» Sinica. 2007. — Vol. 33, N 9. — P. 911-916.