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

МЕСЯГУТОВ Марат Артурович

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

Специальность 05.13.01 - системный анализ, управление и обработка информации (в промышленности)

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

1 6 СЕН 2010

Уфа - 2010

004608060

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

ГОУ впо

,Уфимский государственный авиационный технический университет"

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

д-р физ.-мат. наук, профессор РОМАНОВСКИЙ Иосиф Владимирович,

профессор Санкт-Петербургского государственного университета

канд. физ.-мат. наук, доцент КОЧЕТОВ Юрий Андреевич, старший научный сотрудник Института математики им. С.Л. Соболева СО РАН

ГОУ ВПО „Башкирский государственный университет", г. Уфа

Защита диссертации состоится 1 октября 2010 г. в 10 час. 00 мин. на заседании диссертационного совета Д-212.288.06 при Уфимском государственном авиационном техническом университете по адресу: 450000, г. Уфа, ул. К.Маркса 12.

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

Автореферат разослан 2010 г.

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

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

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

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

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

Актуальность темы. Диссертация посвящена одному из прикладных разделов исследования операций, задачам раскроя-упаковки1, непосредственно связанных с системным анализом. Этот класс задач представляет большой интерес как с точки зрения теории, так и с практической стороны. Рассматриваемые задачи принадлежат к Л/'Р-трудным проблемам. Точные методы позволяют решать эти задачи с небольшим количеством предметов, а приближенные методы слабо структурированы и, по мнению многих уче-

94 _

пых , перспективным направлением для их решения является системных подход.

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

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

С теоретической стороны интерес представляет построение улучшенных нижних границ и точных методов для повышения размерности решаемых задач. Однако, поиск нижней границы зачастую представляет собой так же -Л/Р-трудную проблему. Что касается точных методов решения, то продвижение на этом пути осуществляется очень медленно. Для приближённого решения задачи большую роль играет вычисление локальной нижней границы при оценке окрестностей допустимых решений, что позволяет организовать процесс принятия решений для поиска локального оптимума, направленный на достижение рационального решения, подходящего с точки зрения промышленности по критерию оценки отклонения от оптимума.

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

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

'L.V. Kantorovich. Mathematical Methods of Orga.ni7.ing and Planning Production (translation of the paper of 1939) // Management Science. 1960. V. 6(4). P. 366-422.

2H.H. Моисеев. Математические задачи системного анализа. M.: Наука. 1981.

3Е.П. Голубков. Системный анализ как методологическая основа принятия решений // Менеджмент в России и за рубежом. 2003. №3.

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

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

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

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

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

4. Реализация предложенных методов на ЭВМ и проведение анализа юс эффективности. Исследование качества полученной нижней границы. Выделение области применимости разработанных методов.

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

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

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

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

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

4. Численное исследование эффективности предложенных методов и качества новых нижних границ и решений задачи двухмерной упаковки.

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

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

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

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

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

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

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

Программная реализация полученного приближённого метода для задачи двухмерной упаковки показала преимущества перед известными приближёнными алгоритмами на широком классе задач, что подтверждено расчетами. Это делает программную реализацию метода практически применимой в реальных производственных ситуациях. Программное обеспечение, разработанное в рамках диссертационной работы, зарегистрировано в ВНТИЦ, свидетельство №50200601233.

Алробация работы. Работа выполнялась в рамках научной школы по раскрою-упаковке УГАТУ, при финансовой поддержке РФФИ, грант №10-07-91330-HHUO_a, гранта на исследования Германской службы академических обменов (DAAD), стипендии Georgius-Agrícola Саксонского министерства наук и искусства, и Европейского исследовательского гранта Erasmus

Mundus. Результаты работы и её разделы докладывались и обсуждались на 3-ей и 4-ой Всероссийских конференциях „Проблемы оптимизации и экономические приложения" (г. Омск, 2006, 2009), Всероссийской конференции „Математическое программирование и приложения" (г. Екатеринбург, 2007), 5-ой Европейской конференции по раскрою и упаковке (Euro special interest group on cutting and packing, ESICUP) (г. Л'Акуила, Италия, 2008), 14-ом Юговосточном немецком коллоквиуме (Südostdeutsches Kolloquium) (г. Лейпциг, Германия, 2008), 18-ом и 19-ом Симпозиуме по дискретной оптимизации (Workshop on discrete optimization) (г. Кёнигштейн, Хольцхай, Германия, 2008, 2010), 6-ой Европейской конференции по раскрою и упаковке (ESICUP) (г. Валенсия, Испания, 2009), 13-ом Симпозиуме международной федерации автоматики (International federation of automatic control, IFAC) по проблемам управления информацией в промышленном производстве (г. Москва, 2009), Международной школе-конференции для студентов, аспирантов и молодых ученых „Фундаментальная математика и её приложения в естествознании" (г. Уфа, 2005), Международных симпозиумах по информатике и информационным технологиям (International workshop on computer science and information technologies, CSIT) (г. Карлсруэ, Уфа, 2006, 2009), Региональной зимней школе-семинаре аспирантов и молодых ученых УГАТУ, (г. Уфа, 2007), на семинарах института вычислительной математики Дрезденского Технологического Университета (г. Дрезден), семинарах кафедры Вычислительной Математики и Кибернетики УГАТУ (г. Уфа), семинарах кафедры Математики УГАТУ (г. Уфа), семинаре института математики с вычислительным центром Уфимского научного центра РАН (г. Уфа).

Публикации. По теме диссертации автором опубликовано 15 работ, в том числе три работы в рецензируемых журналах, рекомендованных ВАК.

Структура и объём работы. Диссертация изложена на 132 страницах, содержит введение, три главы, заключение, 7 таблиц, 18 иллюстраций и список литературы, содержащий 109 наименований.

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

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

В первой главе приводятся постановки задач одно- и двухмерных задач упаковки, основные модели, обзор точных и приближённых методов их решения. В качестве основных рассматриваются задача одномерной продолженной упаковки контейнеров (ID Contiguous Bin Packing Problem, 1CBPP) и задача двухмерной упаковки полосы (2D Strip Packing Problem, 2SPP).

Задача 1СВРР состоит в определении минимального количества одномерных контейнеров длины W, в которые необходимо разместить предметы т типов заданной длины удовлетворяя их потребность Ь;, i € I :=

{1,..., т}, с соблюдением последовательности загрузки контейнеров при их упаковке: каждый предмет должен содержаться в смежных контейнерах (нет таких двух контейнеров, содержащих данный предмет, что имеется между ними третий контейнер без этого предмета). Последовательность контейнеров - фиксированная. Величины \У, и>;, и ^ (г 6 7) - целые.

Задача 2ЭРР состоит в размещении заданных т прямоугольных предметов ширины и){ и длины ¡¡, 1 6 I :— {1,..., тп} в полосе фиксированной ширины V/ и полубесконечной длины так, чтобы стороны прямоугольников были параллельны сторонам полосы и предметы не перекрывались между собой и со сторонами полосы, при этом длина занятой части полосы достигала минимума. Величины ТУ, иц и Ц (г £ I) - целые.

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

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

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

Утверждение 1. Пусть дана задача 1СВРР с исходной информацией (ТУ, т, и], Ь). Если существует Ж < ТУ/2, для которого справедлива система неравенств:

ш ш

ЕЕЬ^Е Е 1<я<я-1,

& И?

ЕЕ^Е Е

Ш=1 Ш{ш) ш=1 ¡6/(1У-и>)

№

где 7(го) = {г € I : Wi — т}, то множество предметов I = и (7(ш) и

/(ТУ — гу)) может быть удалено из рассмотрения, при этом значение оптимального решения начальной задачи ОРТ(1) — Н 4- ОРТ{1\1), где Н = м

X) 1С ьи ОРТ(/\/) - значение оптимального решения остаточной задачи, состоящей из предметов /\/.

Раздел 2,3 посвящен вопросу организации ветвлений. Сопоставим упаковке (7) в одномерный контейнер вектор упаковки о? = (а],... с булевыми компонентами: а- = 1, если предмет г размещен в контейнере,

иначе of = 0. Для фиксации положения предметов в контейнере удобно воспользоваться шаблоном упаковки: рр = ((1 (i), yi),..., (i(j), yi),...), где i(j) - номер предмета, занимающего позицию г в шаблоне j, yi - минимальная ордината предмета i(j).

Определение 1. Две упаковки и и v назовем эквивалентными, если au = av.

Определение 2. Пусть дана одномерная продолженная упаковка состоящая из шаблонов р1,... ,pN. Множество последовательных эквивалентных шаблонов упаковок pk,... ,pq, k,q G {1,..., N}, к < q, максимальной мощности с вектором упаковки а называется блоком и обозначается S = (а, х), где х — Я"к + 1 - мощность блока.

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

Определение 3. Пространство представлений решений называется Р-допустимым, если оно удовлетворяет следующим требованиям: 1) пространство кодов конечно; 2) каждый элемент кода соответствует допустимому решению; 3) решение задачи может быть получено по его коду за полиномиальное время; 4) наилучший элемент в пространстве кодов соответствует оптимальному решению исходной задачи.

В качестве кодов предлагается использовать перестановки размерности то в сочетании с алгоритмом следующий подходящий (Next Fit, NF), описанным в разделе 2.3, в качестве декодирующей процедуры. Для полученного таким образом пространства решений верно следующее утверждение.

Утверждение 2. Множество перестановок элементов списка {i\, ...,гт) определяет Р-допустимое пространство решений задачи 1СВРР размерности т, которое состоит из т\ перестановок, каждая из которых может быть трансформирована в допустимую упаковку за время 0(т • log 7П) и, по меньшей мере, одна из них соответствует оптимальному решению задачи 1СВРР.

Из данного утверждения следует, что применение NF к приоритетным спискам обеспечивает получение хотя бы одного оптимального решения. Ветвления заключаются в последовательном и направленном размещении каждого элемента множества I в соответствии с правилом NF. Посредством этого строится дерево ветвлений Т = (V, Е), листья которого представляют собой множество всех перестановок элементов из I. Каждому узлу и 6 V соответствует упорядоченная последовательность (список) и = (¿i,..., ij} размещенных предметов ц е I, I = 1,..., d; d < m, и частичная упаковка (блок-структура4) SS(u) — {(a1, Xi), • - ■, (аа(и\ x<r(u)))i которая получается

4Э.А. Мухачева, A.C. Мухачева. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Автоматика и Телемеханика. 2004. №2. С. 101-112.

применением правила ИР к упорядоченной последовательности и, где а* -вектор упаковки блока Хз ~ интенсивность применения блока Предметы 1(и) = 1\{гI,..., ¿¿} подлежат размещению. Ребро (и, и), где и, V € V, и ф и, принадлежит множеству Е, если подзадача и получается из и размещением предмета г е /(и), то есть у — (и, г). Следующий выбранный предмет г € /(и) для узла и £ V размещается в соответствии с правилом ИР в блоках хци)), • ■ - > Хст(и))}, где последний размещенный элемент г^ в и, помещен в блоке (а^^, Хз{и)), т.е. а}^ = 1 Л о^-1 = 0. Если г € 1{и) не может быть размещен в этих блоках, то для размещения этого предмета инициализируется новый блок а(и) + 1, где а (и) - количество блоков. При этом в каждом блоке Sj Е Б Б (и) содержаться предметы С 1(и), из которых размещение предметов — {г е : г £ /^-г} было начато впервые.

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

Определение 4. Пусть дана упаковка и — (и,..., г^,..., г3,..., 6 V с её блок-структурой , где к < д и г*, гч е Ц, ^ 6 {1,..., ст(гг)}. Упаковку и' — (¿1,..., г?,..., г*,..., ¿¿) 6 V с блок-структурой Б8(и) назовём вертикально эквивалентной упаковке и.

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

Лемма 1. Пусть дана оптимальная упаковка и = (¿1,...,гт) £ V с блок-структурой Если существует блок € в Я (и), в котором

имеются такие элементы А, д 6 {1,..., т}, что

й, гд € г* > г„ (1)

то существует оптима.1ьная упаковка и' € V, для которой условия (1) не выполняются.

Определение 5. Пусть дана упаковка и & V с блок-структурой = ((а^хО, ■ ■ ■ > Хе(и)))- Упаковку и' £ V с блок-структурой

38(и') = ({аа(и\ х<г(и))) • • •) (а1!*!)) назовём горизонтально эквивалентной упаковке и.

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

Лемма 2. Пусть дана оптимальная упаковка и £ V с блок-структурой SS(u). Если для предмета i* £ I и блока Sj> € SS(u) : г* £ в котором он размещен, выполнено неравенство

j'-l ^ <7(и)

j=i j=i

то существует оптимальная упаковка и' £ V, для которой условие (2) не выполняется.

Определение 6. Пусть дана упаковка и = (г'х,..., i¡¡,. ■ ■, iq,..., id) £ V с блок-структурой SS(u), где ik, iq G и : iq £ 7S(¿¿) = {j £ /\{fc} : = Wj A = í»j}. Упаковку и' = (¿i,..., iq,..., ik, ■ ■ ■, id) € назовём эквивалентной упаковке и по отношению к идентичным предметам i¡, и iq.

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

Лемма 3. Пусть дана оптимальная упаковка и — (i\,... ... ,iq, ..., im) € V, с блок-структурой SS(u), где к < q и iq £ Is{ik) ■ Если для некоторого j 6 {1,..., cr(u)}, ц £ Ij:

ik > i„ iq Ij, (3)

то существует оптимальная упаковка и' 6 V, для которой условия (3) не выполняются.

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

Лемма 4. Пусть дана оптимальная упаковка и — {i\,..., im) £ V с блок-структурой SS(u). Если для некоторого предмета i* £ I, размещенного в блоке j*, нашлось такое подмножество S(i*) = {Skv ■ ■ ■, S1^} С SS(u)\{Sj-,..., ¿^(u)}, что выполнены условия h

&¿«<X>, (4)

j—ki

Wi. <{W- £>,•), V¿ 6 ih,..., k2), (5)

¿e/í

то существует оптимальная упаковка и' £ V, для которой не существует такого S(i*), что условия (4), (5) выполняются.

Для исключения решений в соответствии с правилом NF применяется правило П5: если при упаковке текущего блока следующий пакуемый предмет

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

Лемма 5. Пусть дана оптимальная упаковка и = {ii,...,im) £ V с блок-структурой SS(u). Если для некоторого предмета i* € / и блока j* >2: г* е IJ., в котором он размещен, верно

(6)

»€/

то существует оптимальная упаковка и' € V, для которой условие (6) не выполняется.

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

Лемма 6. Пусть дана оптимальная упаковка и 6 F с блок-структурой SS(u) и значением целевой функции J^j^i Xj- Дм упаковки и верно

А(») \

д15>1 <д(я0),

где Д (-L) = W ■ L — Eiei Wi • bi, а Щ - верхняя граница для значения целевой функции задачи.

В разделе 2.4 обсуждаются нижние границы для узлов дерева ветвлений Т. Рассматриваются два типа нижних границ: очевидная - материальная нижняя граница и нижняя граница, основанная на релаксации линейным программированием (Linear programming, LP) задачи одномерного раскроя с различными типами прутков5.

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

JM-i lbm{u) = J2 Xj +

3=1

<x(u)

E (xj

j=j{ u)

• E1

¿e/j

>i) + E wi ■ bi

iei(u)

W

Утверждение 3. Пусть дан узел и = {ц,... ,id) 6 V, ц € I, I — 1,..., d, d < т. Число lbm(u) является нижней границей для значений решений, которые могут быть получены ветвлением узла и.

На Рис. 1 изображена блок-структура SS(u) узла и — (ii,...,id) € V. В соответствии с дискретностью задачи, неиспользованная область (А*, щ)

5G. Belov and G. Scheithauer. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths // European Journal of Operational Research. 2002. V. 141(2). P. 274—294.

h

h

q блоков

Рисунок 1 - Частичная упаковка: горизонтальная и вертикальная LP-релаксации.

рассматривается как множество одномерных прутков материала ширины Xk и длины 1. Поэтому, каждый тип прутка А к доступен в количестве щ за исключением последнего А9(„)+1, q(u) = а (и) — j(u) + 1, который доступен в неограниченном количестве. Оставшееся множество предметов Wi х 1, г G 1(и) в количестве bi с единичной длиной могут быть раскроены из этого набора прутков в соответствии со следующими правилами. Каждый предмет Wi х 1 может быть выкроен только один раз из одного прутка. Комплектность каждого типа прутка не может быть превышена.

Любой допустимый раскройный шаблон описывается следующим бинарным вектором:

а» = (af,..., a£)T g {0,1}т при ]Г wt ■ af < A*, (7)

tel

где j £ J* - множество шаблонов для каждого типа прутка к = 1,..., q(u) +1 ; af = 0, г G 1(и), если предмет г вырезается из j-го шаблона к-то типа прутка.

Для узла и = (ii,..id) G V формулируется следующая задача LP-релаксации одномерного раскроя с различными длинами прутков (ID Cutting Stock Problem with Multiple Stock Lengths, 1CSPM), задача LlCSPM(u):

i

Xj,q(u}и min,

«W+i

EE

^af -xjk :

b.

k=i

E

bi = o,

Ь'к < uk,

i G I (и); i G I (и)-,

к G K= {!,...,«(«)};

(8)

(9)

(10) (И)

к в К и {д(и) + 1}, 2 € Л, (12) где х^ - интенсивность применения ^'-го шаблона к-го типа прутка. Задача решается методом генерации столбцов с использованием процедур динамического программирования (задачи 0/1 рюкзак).

Обозначим значение оптимального решения Хьр — {х]к : х^ > 6, 6 > 0} задачи ЫС8РМ(и).

Лемма 7. Пусть дан узел и — (¿1,..., £ V, ц £ I, I = 1,..., й < т. Число

"Ы«) = 1>+Г*£г(и)1, (13)

3=1

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

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

при условии допустимости • о^]к А^ формулируется

следующая задача ЬР-релаксации, задача ЫСЗРМ^и, Но):

X] ^ 1п1п> (14)

з

9(«)+1 к=1 л

= 0, г £ /(и); (16)

£

£ ч4, I' К - {1.....?(и)}; (17)

+ (18) Обозначим ¿'^(и, Но) значение оптимального решения = {з^ : х^к > е, е > 0} задачи Ь1С8РМ'(и, Я0).

Лемма 8. Пусть дан узел и = (¿1,...,£У,ц £ I, 1 = 1,..., й, <2 < т. Если ¿^(и, Но) > е, е > 0, то решение, которое будет получено ветвлением узла и, будет иметь значение не лучше, чем верхняя граница Но для значения целевой функции.

В случае, если для некоторой частичной упаковки и £ V условие леммы 8 верно, то узел и исключается из рассмотрения.

Раздел 2.5 посвящен реализации точного метода на основе метода ветвей и границ. Во время ветвлений нет необходимости рассматривать узлы, нижняя граница которых больше или равна верхней границе для задачи. Поэтому, для некоторого узла и = £ V и его потомков V— (¿1,..., г), где г 6 1{и), ребро (и, у) £ Е, только если:

тах{1Ът{у),1Ьър(у)}<иЬ{1). (19)

Теорема 1. Алгоритм, основанный на методе ветвей и границ на приоритетных списках с учетом условия (19) и правил отсечений П1, ..., П6, является точным.

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

рассматриваются узлы с приоритетом.

Определение 7. Пусть дан узел и = (¿i,...,¿d) дерева ветвлений Т. Тогда потомок v = (и, i) узла и, i £ 1(и) называется приоритетным для заданного параметра г £ Z+, если существует такой столбец а*к в оптимальном решении XLP = {xjk : Xjk > е, е > 0} задачи LlCSPM(u), ■чтпо а{к = 1, к < г.

Стратегия ветвлений:

LP0 Выбрать г £ {1,..., W}.

LP1 Построить множество всех приоритетных узлов V+ С V. Если V+ = 0, тогда LP2. Ветвить и* £ У+: построить множество самых глубоких узлов = {v £ V+ : |wj = тах^су+ М}; среди узлов V^ ветвить узел с наименьшей нижней границей v* — argmin{/&Lp(u) : v € V^J. Переход к LP1.

LP2 Построить множество всех неприоритетных узлов V. Если V = 0, тогда Выход. Иначе, ветвить v* £ V: ветвить в соответствии со стратегией лучшей границы v* = BestBound(V). Переход к LP i. В разделе 2.6 приводятся результаты численного эксперимента. Около 42% задач из библиотеки Bortfeld®, на которьк тестировался метод, были решены оптимально, несмотря на большую размерность задач (20-100). В связи с тем, что значение точного решения задачи 1СВРР является нижней границей для решений задачи 2SPP, было произведено сравнение значений полученной нижней границы с уже известными из литературы, которые подтверждают эффективность метода. Выделена область применимости метода.

В главе 3 предложена конкретизация метода локального поиска на основе направленного перебора окрестностей с использованием решения задачи 1СВРР.

Рассмотрим индивидуальную задачу ортогональной упаковки (Т, L), Т - конечное множество упаковок р с исходными данными {W\ ш; w\ I) и упаковку р* £ Т, доставляющую минимум функции цели L = max,-(г, + 1г). Упаковка р* длины L* = mini — глобальный минимум. Далее, для каждой допустимой упаковки р £ Т определим функцию окрестности Л, которая задает для р множество соседних решений, в некотором смысле близких к данному. С индивидуальной задачей (Т, L) связана задача 1СВРР. В связи с её применением в разработке методов решения задачи двухмерной упаковки, авторы Э.А. Мухачева и A.C. Филиппова назвали её прямоугольно ориентированной (Rectangular Oriented Cutting Stock Problem, ROCSP), а допустимое решение - прямоугольно ориентированным раскроем (Rectangular Oriented Linear Cutting, ROLC). Функцией цели в задаче ROCSP является количество Л затраченных прутков. В связи с тем, что длина предметов в задаче одномерной продолженной упаковки и ширина предметов в задаче двухмерной упаковки

6A. Bortfeld. A genetic algorithm for the two-dimensional strip packing problem with rectangular prices. European Journal of Operational Reseach. 2006. V. 172(3). P. 814-837.

обозначаются одинаково, введем новые обозначения ширины и потребности в предметах, Aí и Д соответственно. Если при решении задачи ГЮСЭР множества предметов {А,/3} с очередностью размещения, заданной списком тг, полученным из блок-структуры задачи (Т, Ь), применяется алгоритм то прямоугольно ориентированный раскрой запишем как 110ЬСпе((А,/3),тг).

Интересующая нас Л-окрестность определяется перестановками элементов в 7Г, в результате которых получают прямоугольно ориентированные одномерные раскрои, различающиеся только порядком следования предметов в одном и том же контейнере. Такие раскрои и отвечающие им списки названы эквивалентными.

Определение 8. Перестановка, элементов в списке 7Г называется пассивной, если применение ИР к полученному списку тг1 приведет к раскрою НОЬСщ?((А, /?),7г0, эквивалентному исходному 1ЮЬСир((А, Р), тг).

Пусть имеется ортогональная упаковка р £ Т, отвечающий ей список 7г(р) и прямоугольно ориентированный раскрой ШЭЬСдаЦА, /3), 7г(р)) со значением целевой функции Л. Тогда построение соседнего с р решения состоит из выполнения следующих процедур:

Л1 Построение последовательности ■к', эквивалентной 7г: случайный выбор блока, в котором начальных элементов не менее двух, и пары пассивных элементов. Перестановка пассивных элементов в отмеченном блоке.

Л2 Конструирование соседнего ср решения: при входных данных ■ш;/} применяем № к списку тг1, получаем р' — НРцрС^О)7^) длины V.

Пусть известна допустимая упаковка р € Т множества предметов {А,/3} и ей отвечают перестановка я(р) и ЮЬС№((Л,/3), 7г(р)) со значением целевой функции Л, где 110ЬСлпр((А, /3),7г(р)) - упаковка полученная применением модифицированной процедуры М№ для задачи 110 СЭР на списке 7г(р), описанной в разделе 3.3. Тогда справедливо следующее утверждение.

Лемма 9. Для любой прямоугольной упаковки р множества предметов {ш, /} и ИР-активного прямоугольно ориентированного раскроя ШЭЬСот^А, ¡3), 7Г(р)), А = ю, ¡3 = I, справедливо неравенство:

|коьсот((А,/^(р))1<ЬК01, (20)

какой бы алгоритм для воспроизведения р ранее не был применен.

Определение 9. Нижней локальной границей в А-окрестности упаковки ре Т называется число к такое, что для любой упаковки р из этой окрестности к < [р|.

Из леммы 9 согласно определению 9 следует утверждение.

Теорема 2. Решение А = Е0ЬСш?((А,/3), тт(р)) задачи ИОСБР с исходной информацией (ТУ;т;А = — I), я"(р), является локальной нижней границей в А-окрестности упаковки р множества предметов {и>,1}.

В разделе 3.4 предложен гибридный алгоритм поиска лучшего решения в Л-окрестности ШЗ-Л. Стратегия ИБЭ-Л основана на том, что Л-границу можно вычислить до построения текущего решения. Для этого решается за-

дача ROCSP. Её решение - начальная локальная Л-граница. Для списка 7г, отвечающего ROLC, применяя NF, находят начальную упаковку р = RP. Выполняя пассивные перестановки в 7Г, строят окрестность и находят в ней упаковку с рекордным значением длины L. Далее, применяя одноточечный эволюционный алгоритм (1+1)-ЕА7 выполняется генерация новой окрестности с меньшим значением Л и поиском в ней упаковки с L' < L.

Задача ROCSP решается с использованием метода последовательного уточнения оценок (Sequential Value Correction, SVC8). Процедура SVC повторяется до тех пор, пока отклонение рекорда от нижней границы не достигнет заданного значения или не закончится лимит расчетного времени. Если Л улучшилось, то происходит переход на генерацию Л-окрестности и поиск в ней лучшей упаковки.

Утверждение 4. Временная сложность вычисления одной итерации алгоритма поиска лучшего решения в К-окрестности HSS-Л составляет 0{W-m3).

В разделе 3.5 приведены результаты численного эксперимента. Разработанный метод сравнивается с другими известными приближёнными методами. Результаты сравнения отклонений решений (gap) от нижних границ подтверждают эффективность предложенного метода. Анализируя полученные результаты с нижними границами, полученными с помощью алгоритма, описанного в главе 2, можно сделать следующие выводы: из 50 подклассов задач библиотеки Bortfeld в шести получены оптимальные решения, в 10 подклассах отклонение от оптимума в среднем не превосходит 0,1%; в 25 подклассах отклонение от оптимума в среднем не превосходит 1%.

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

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

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

7П.А. Борисовский, A.B. Еремеев. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. 2004. №3. С. 3—9.

8Е.А. Mukhacheva, G.N. Belov, V.M. Kartack, and A.S. Mukhacheva. Linear one-dimensional cutting-packing problems: numerical experiments with the sequential value correction method (SVC) and a modified branch-and-bound method (MBB) // Pesquisa Operational. 2000. V. 20(2). P. 153-168.

9A. Bortfeld. A genetic algorithm for the two-dimensional strip packing problem with rectangular prices. // European Journal of Operational Reseach. 2006. V. 172(3). P. 814-837.

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

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

4. Предложенные методы реализованы на ЭВМ. Результаты экспериментов показали, что существуют классы задач, на которых методы имеют различную результативность. Проведён анализ эффективности методов на различных классах задач и выделена область применимости разработанных методов. Это позволяет априорно сделать выбор лучшей схемы решения по классу рассматриваемых задач. Исследовано качество полученной нижней границы. Результаты экспериментов показали, что разработанная нижняя граница не хуже известных для задач из открытой библиотеки и для 37% задач удалось существенно улучшить значение нижней границы по сравнению с известными результатами.

Основные результаты диссертации опубликованы в работах в рецензируемых изданиях из перечня ВАК:

1. В.М. Картак, М.А. Месягутов, Э.А. Мухачева, A.C. Филиппова. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика. 2009. №6. С. 167-180.

2. М.А. Месягутов. Задача двухмерной ортогональной упаковки: поиск нижней границы на базе решения одномерной продолженной упаковки // Информационные технологии. 2010. №6. С. 13-23.

3. М.А. Месягутов. Модификация метода ветвей и границ для поиска оптимального решения задачи одномерной упаковки прямоугольно-ориентированной структуры // Научно-технические ведомости СПбГПУ, серия „Информатика. Телекоммуникации. Управление". №3. С. 130-134.

в других изданиях:

4. В.П. Житников, A.C. Филиппова, М.А. Месягутов. Проектирование ортогональной упаковки, основанное на блок-структурах // Симпозиум по информатике и информационным технологиям (CSIT): труды международной конференции. Карлсруэ. 2006. №2. С. 131-134. (на англ. языке).

5. Э.А. Мухачева, М.А. Месягутов и A.C. Филиппова. Эволюционный алгоритм (1+1)-ЕА с локальной нижней границей для задач прямоугольной упаковки полосы // Проблемы оптимизации и экономические приложения: материалы III Всероссийской конференции. Омск. 2006. №1. С. 114.

6. М.А. Месягутов. Поиск локальных оптимумов в задачах раскроя-упаковки с использованием локальных границ // Интеллектуальные системы обработки информации и управления: сборник статей 2-ой региональной зимней школы-семинара аспирантов и молодых ученых. Уфа. 2007. №1. С. 22-24.

7. М.А. Месягутов, A.C. Филиппова. Задачи ортогональной упаковки: поиск решений в окрестностях с локальной нижней границей // Информационный бюллетень Ассоциации математического программирования. Екатеринбург. 2007. №11. С. 219.

8. М.А. Месягутов, Г. Шайтхауэр, Г. Белов. Метод ветвей и границ для задачи одномерного продолженного раскроя // бая Европейская конференция по раскрою и упаковке (ESICUP): труды конференции. Л'Акуила. 2008. №1. С. 20. (на англ. языке).

9. М.А. Месягутов, Г. Шайтхауэр, Г. Белов. Точный метод решения задачи одномерного продолженного раскроя, основанный на линейном программировании // 18ый Симпозиум по дискретной оптимизации: труды конференции. Кёнигштейн. 2008. С. 19-21.

10. М.А. Месягутов, Г. Шайтхауэр, Г. Белов. Точный метод решения задачи одномерного продолженного раскроя // бая Европейская конференция по раскрою и упаковке (ESICUP): труды конференции. Валенсия. 2009. №1. С. 33-34. (на англ. языке).

И. М.А. Месягутов и Мухачева Э.А. Точный метод решения задачи одномерной упаковки с продолженным выбором идентичных предметов // Проблемы оптимизации и экономические приложения: материалы IV Всероссийской конференции. Омск. 2009. №1. С. 150.

12. М.А. Месягутов, В.М. Картак, P.C. Валеев. Нижние границы для задачи двухмерной упаковки: линейная и одномерная продолженная релаксация // 13ый Симпозиум (IFAC) по проблемам управления информацией в производстве (INCOM): препринты конференции. Москва. 2009. С. 2003-2007. (на англ. языке).

13. М.А. Месягутов. Точный метод для задачи одномерной продолженной упаковки // Симпозиум по информатике и информационным технологиям (CSIT): труды международной конференции. Крит. 2009. №1. С. 280-281. (на англ. языке).

14. М.А. Месягутов, Г. Шайтхауэр. Методы branch-and-price для задачи одномерной продолженной упаковки // 19ый Симпозиум по дискретной оптимизации: труды конференции. Хольцхау. 2010. С. 37-40. (на англ. языке)

15. М.А. Месягутов и A.C. Филиппова. Решение задачи двухмерной прямоугольной упаковки объектов в полубесконечную полосу алгоритмом (1+1)-ЕА блочной структуры с использованием локальной нижней границы. Программа для ЭВМ. Регистрационный номер №50200601233. Всероссийский научно-технический информационный центр (ВНТИЦ).

Соискатель dfj ^ Месягутов М.А.

■;(■№ и! Ii

МЕСЯГУТОВ Марат Артурович

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

Специальность 05.13.01 — системный анализ, управление и обработка информации (в промышленности)

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

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

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

Символика и обозначения.

Введение

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

1.1 Задача одномерной упаковки.

1.2 Задача двухмерной упаковки.

1.3 Задача продолженного одномерного раскроя.

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

1.5 Выводы.

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

2.1 Математические модели.

2.2 Сокращение размерности задачи.

2.3 Ветвления. . ;.

2.4 Нижние границы.

2.5 Точный алгоритм.

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

2.7 Выводы.■.

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

3.1 Кодирование и декодирование ортогональной упаковки.

3.2 Л-окрестность допустимой упаковки.

3.3 Нижняя граница в Л-окрестности

3.4 Поиск лучшего локально оптимального решения с использованием Л-окрестностей . :.

3.5 Численный эксперимент . . ;.

3.6 Выводы.

Результаты и выводы.

Список публикаций автора по теме диссертации.

Актуальность темы. Диссертация посвящена одному из прикладных разделов исследования операций, задачам раскроя-упаковки, непосредственно связанных с системным анализом. Этот класс задач представляет большой интерес как с точки зрения теории, так и с практической стороны. Рассматриваемые задачи принадлежат к J\fV-трудным проблемам. Точные методы позволяют решать эти задачи с небольшим количеством предметов, а приближенные методы слабо структурированы и, по мнению многих ученых, перспективным направлением для их решения является системных подход.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Численное исследование эффективности предложенных методов и качества новых нижних границ и решений задачи двухмерной упаковки.

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

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

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

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

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

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

Программная реализация полученного приближённого метода для задачи двухмерной упаковки показала преимущества перед известными приближёнными алгоритмами на широком классе задач, что подтверждено расчетами. Это делает программную реализацию метода практически применимой в реальных производственных ситуациях. Программное обеспечение, разработанное в рамках диссертационной работы, зарегистрировано в ВНТИЦ, свидетельство №50200601233.

Апробация работы. Работа выполнялась в рамках научной школы по раскрою-упаковке УГАТУ, при финансовой поддержке РФФИ, грант №10-07-91330-HHUOa, гранта на исследования Германской службы академических обменов (DAAD), стипендии Georgius-Agricola Саксонского министерства наук и искусства, и Европейского исследовательского гранта Erasmus Mundus. Результаты работы и её разделы докладывались и обсуждались на следующих конференциях и семинарах:

1. 3-я и 4-я Всероссийская конференция „Проблемы оптимизации и экономические приложения", Омский филиал института математики им. Соболева СО РАН, г. Омск, 2006, 2009 года.

2. Всероссийская конференция „Математическое программирование и приложения", институт математики и механики УрО РАН, г. Екатеринбург, 2007 год.

3. 5-ая Европейская конференция по раскрою и упаковке (Euro special interest group on cutting and packing, ESICUP), г. ЛАкуила, Италия, 2008 год.

4. 14-ый Юговосточный немецкий коллоквиум (Siidostdeutsches Kolloqui-um), г. Лейпциг, Германия, 2008 год.

5. 18-ый Симпозиум по дискретной оптимизации (Workshop on discrete Optimization), г. Кёнигштейн, Германия, 2008 год.

6. 6-ая Европейская конференция по раскрою и упаковке (Euro special interest group on cutting and packing, ESICUP), г. Валенсия, Испания, 2009 год.

7. 13-ый Симпозиум международной федерации автоматики (International federation of automatic control, IFAC) по проблемам управления информацией в промышленном производстве, г. Москва, 2009 год.

8. Международная школа-конференция для студентов, аспирантов и молодых ученых „Фундаментальная математика и ее приложения в естествознании", Б ГУ, г. Уфа, 2005, 2009 года.

9. Международный симпозиум по информатике и информационным технологиям (International Workshop on Computer Science and Information Technologies, CSIT), г. Карлсруэ, Германия, г. Уфа, 2006, 2009 года.

10. 19-ый Симпозиум по дискретной оптимизации (Workshop on discrete Optimization), г. Хольцхау, Германия, 2010 год.

11. Региональная зимняя школа-семинар аспирантов и молодых ученых факультета Информатики и Робототехники УГАТУ, г. Уфа, 2007 год.

12. Семинары института вычислительной математики Дрезденского Технологического Университета, г. Дрезден.

13. Семинары кафедры вычислительной математики и кибернетики УГАТУ, г. Уфа.

14. Семинары кафедры математики УГАТУ, г. Уфа.

15. Семинар института математики с вычислительным центром Уфимского научного центра РАН, г. Уфа.

Публикации. По теме диссертации автором опубликовано 15 работ, в том числе три работы в рецензируемых журналах, рекомендованных ВАК.

Структура и объём работы. Диссертация изложена на 132 страницах, содержит введение, три главы, заключение, 7 таблиц, 18- иллюстраций и список литературы, содержащий 109 наименований.

3.6 Выводы

Предложен и реализован одноточечный метод локального поиска оптимума. Рекордные допустимые решения определяются в Л-окрестности и улучшаются при переходе к другой Л-окрестности. При этом на текущей итерации эволоционного алгоритма реализуется NF-стратегия для различных списков 7г, различающихся перестановками пассивных элементов. Приведены численные результаты сравнения предложенного алгоритма с другими эффективными алгоритмами. HSS-Л показал на болыпенстве классов лучшие результаты. При этом видны пути его совершенствования: применение метода с запретами при поиске в окрестности; использование других метаэвристик, генетического алгоритма и метода отжига. Кроме того, перспективы имеет гибридизация точного метода и эвристики. Среднее отклонение решений от нижней гранцы, предложенной A. Bortfeld, равно 1,38%, т.е. меньше чем отклонение 1,94% от точного решения задачи 1СВРР, полученные тем же алгоритмом.

Результаты и выводы

В заключении сформулируем основные результаты исследований и выводы.

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

2. Разработан точный метод решения задачи одномерной продолженной упаковки, который основан на использовании правила „следующий подходящий" и оценок, получаемых с помощью решения вспомогательной задачи линейного программирования. Доказана точность метода. Предложены и обоснованы новые критерии доминантности и правила отсечения. Разработана новая стратегия ветвлений при поиске верхней границы для значения целевой функции. Это позволяет существенно сократить переборный процесс. Разработанный метод позволяет решать в ограниченное время & 42% задач из открытой библиотеки оптимально.

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

4. Предложенные методы реализованы на ЭВМ. Результаты экспериментов показали, что существуют классы задач, на которых методы имеют различную результативность. Проведён анализ эффективности методов на различных классах задач и выделена область применимости разработанных методов. Это позволяет априорно сделать выбор лучшей схемы решения по классу рассматриваемых задач. Исследовано качество полученной нижней границы. Результаты экспериментов показали, что разработанная нижняя граница не хуже известных для задач из открытой библиотеки и для 37% задач удалось существенно улучшить значение нижней границы по сравнению с известными результатами.

Список публикаций автора по теме диссертации

1] В.М. Картак, М.А. Месягутов, Э.А. Мухачева и А.С. Филиппова. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика, 6: 167-180, 2009. •

2] М.А. Месягутов. Задача двухмерной ортогональной упаковки: поиск нижней границы на базе решения одномерной продолженной упаковки // Информационные технолргии, 6: 13-23, 2010.

3] М.А. Месягутов. Точный метод поиска оптимума задачи одномерной продолженной упаковки // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета, 3: 130-134, 2010.

4] М.А. Месягутов, Э.А. Мухачева, Г.Н. Белов и Г. Шайтхауэр. Упаковка одномерных контейнеров с продолженным выбором идентичных предметов: точный метод поиска оптимального решения // Автоматика и ' Телемеханика, 2010. Принята в цечать.

5] М.А. Месягутов. Поиск локальных оптимумов в задачах раскроя-упаковки с использованием локальных границ // Интеллектуальные системы обработки информации и управления. Сборник статей 2-ой региональной зимней школы-семинара аспирантов и молодых ученых, Уфа, 1: 22-24, 2007.

6] Zhitnikov V.P., Philippova A.S., and М.А. Mesyagutov. Projecting of orthogonal packing based on slice-structures // Proceeding of the Workshop on Computer Science and Information Technologies, Karlsruhe, 2: 131-134, 2006.

7] Э.А. Мухачева, М.А. Месягутов и А.С. Филиппова. Эволюционный алгоритм (1+1)-ЕА с локальной нижней границей для задач прямоугольной упаковки полосы // III Всероссийская конференция "Проблемы оптимизации и экономические приложения". Материалы конференции, Омск, 1: 114, 2006.

8] М.А. Месягутов и А.С. Филиппова. Задачи ортогональной упаковки: поиск решений в окрестностях с локальной нижней границей // Информационный бюллетень Ассоциации математического программирования, Екатеринбург, 11: 219, 2007.

9] М.А. Mesyagutov, G. Scheithauer, and G. Belov. A branch & bound approach for the ID contiguous cutting-stock problem // 5th Euro special interest group on cutting and packing (ESICUP) meeting. Collected papers, L'Aquila, 1: 20, 2008.

10] M.A. Mesyagutov, G. Scheithauer, and G. Belov. LP-based exact approach for the ID contiguous cutting-stock problem // 18th Workshop on discrete Optimization. Collected papers, Konigstein, P. 19-21, 2008.

11] M.A. Mesyagutov, G. Scheithauer, and G. Belov. Exact approaches for the ID contiguous cutting-stock 'problem // 6th Euro special interest group on cutting and packing (ESICUP) meeting. Collected papers, Valencia, 1: 33-34, 2009.'

12] M.A. Месягутов и Мухачева Э.А. Точный метод решения задачи одномерной упаковки с продолженным выбором идентичных предметов //IV Всероссийская конференция "Проблемы оптимизации и экономические приложения". Материалы конференции, Омск, 1: 150, 2009.

13] М.А. Mesyagutov, V.M. Kartak, and R.S. Valeev. Lower bounds for the 2D strip packing problem: linear and ID contiguous relaxation // Preprints of the 13th IFA.C Symposium on Information Control Problems in Manufacturing (INCOM), Moscow, P. 2003-2007, 2009.

14] M.A. Mesyagutov. LP-based exact approach for the ID contiguous cutting-stock problem // Proceeding of the Workshop on Computer Science and Information Technologies (CSIT), Crete, 1: 280-281, 2009.

15] M.A. Mesyagutov and G. Scheithauer. Branch-and-price algorithms for the ID contiguous bin packing problem // 19th Workshop on discrete Optimization, Holzhau, P. 37-40, 2010.

16] M.A. Месягутов'и А.С. Филиппова. Решение задачи двухмерной прямоугольной упаковки объектов в полубесконечную полосу алгоритмом (1+1)-ЕА блочной структуры с использованием локальной нижней границы. Программа для ЭВМ. Регистрационный номер №50200601233. Всероссийский научно-технический информационный центр (ВНТИЦ).

1. L.V. Kantorovich. Mathematical methods of organizing and planning production (translation of the paper of 1939) // Management Science. 1960. 6(4): 366-422.

2. P.C. Gilmore, R.E. Gomory. A linear programming approach to the cutting-stock problem // Operations Research. 1961. 9(6): 849-859.

3. A.H. Land, A.G. Doig. An automatic method of solving discrete programming problems // Econometrica. 1960. 28(3): 497-520. '

4. J.M. Valerio de Carvalho. LP models for bin packing and cutting stock problems // European Journal of Operational Research. 2002. 141: 253-273.

5. G. Belov. Problems, models.and algorithms in one- and two-dimensional cutting. PhD thesis. Dresden University of Technology. 2003.

6. Jl.В. Канторович, В.А. Залгаллер. Расчет рационального раскроя промышленных материалов. Лениздат. 1951.

7. S. Martello, P. Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. NY, USA. 1990.

8. O. Marcotte. The cutting stock problem and integer rounding // Mathematical Programming. 1985. 33: 82-92.

9. O. Marcotte. An instance of the cutting stock problem for which the rounding property does not hold // Operations Research Letters. 1986. 4/5: 239-243.

10. J. Rietz, G. Scheithauer. Tighter bounds for the gap and non-irup constructions in the one-dimensional cutting stock problem // Optimization. 2002. 51.6: 927-963.

11. G. Scheithauer, J. Terno. The modified integer round-up property of theone-dimensional cutting stock problem // European Journal of Operationalt, \

12. Research. 1995. 84: 562-571.

13. F. Vanderbeck. On dantzig-wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm // Operations Research. 2000. 48: 111-128. •

14. P. Vance. Branch-and-price algorithms for the one-dimensional cutting stock problem // Computational Optimization and Applications. 1998. 9(3): 212— 228.

15. J.M. Valerio de Carvalho. Exact solution of bin-packing problems using column generation and branch-and-bound // Annals of Operational Research. 1999. 86: 629-659.

16. J.F. Shapiro. Dynamic programming algorithms for the integer programming // Operations Research. 1968. 16(1): 103-121.

17. R.K. Ahuja, T.L. -Magnanti, J.B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall. 1993.

18. G. Wascher, T. Gau. Heuristics for the integer one-dimensional cutting stock problem: a computational study // OR Spektrum. 1996. 18: 131-144.

19. F. Vanderbeck, L. Wolsey. An exact algorithm for ip column generation /■/ Operations Research Letters. 1996. 19(4): 151-159.

20. C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W. Savelsbergh, P.H. Vance. Branch-and-price: Column generation for solving huge integer programs // Operations Research. 1996. 46: 316-329.

21. Z. Degraeve, L. Schrage. Optimal integer solution to industrial cutting stock problems // INFORMS Journal on Computing. 1999. 11: 406-419.

22. F. Vanderbeck. Computational study of a column generation algorithm for binpacking and cutting stock problems // Mathematical Programming. 1999. 86: 565-594.

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

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

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

26. A. Scholl, R. Klein, G. Juergens. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin-packing problem // Computers and Operational Research. 1997. 24(7): 627-645.

27. D. Simchi-Levi. New worst case results for the bin-packing problem // Naval Research Logistics. 1994. 41: 579-585.

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

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

30. J.M. Valerio de Carvalho. Using extra dual cuts to accelerate column generation // INFORMS Journal on Computing. 2005. 17(2): 175-182.

31. E.A. Mukhachevaj V.A. Zalgaller. Linear programming cutting problems /./1.ternational Journal of Software Engineering and Knowledge Engineering. 1993, 3: 463-476.

32. E. Aarts, J. Lenstra. Local search in combinatorial optimization. John Wiley & Sons, Inc. NY, USA. 1997.

33. Ю.А. Кочетов. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и её приложения: Сборник лекций молодежных и научных школ по дискретной математике и её приложениям. 2000. pages 87-117.

34. Е.Е. Bischoff, M.D. Marriott. A comparative evaluation of heuristics for container loading // European Journal of Operational Research. 1990. 44(2): 267-276.

35. Батищев Д.Ю. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж: Воронежский гос. техн. ун-т. 1995.

36. Е. Falkenauer. A hybrid grouping genetic algorithm for bin packing // Journal of Heuristics. 1998. 33(1): 5-30.

37. F. Glover. Tabu search and adaptive memory programming advances, application and challenges // Interfaces in Computer Science and Operations Research. 1996. pages 1-75.

38. Yu. Kochetov, A. Usmanova. Probabilistic tabu search with exponential neighborhood for the bin packing problem. In Proceedings MIC'2001. pages 619-624. 2001. .

39. F. Loris. An application of simulated annealing to the cutting stock problem // European Journal of Operational Research. 1999. 144(3): 542-556.

40. H. Foerster, G. Wascher. Simulated annealing for order spread minimization in sequencing cutting patterns // European Journal of Operational Research. 1998. 110(2): 272-281.

41. П.А. Борисовский. Исследование эволюционных алгоритмов решения некоторых задач дискретной оптимизации. PhD thesis. Омский филиал Института математики им. С. JI. Соболева СО РАН, Омск. 2005.

42. А.С. Филиппова. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе технологий блочных структур / / Информационные технологии. 2006. 6: Приложение (32 страницы).

43. П.А. Борисовский, А.В. Еремеев. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. 2004. 3: 3-9.

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

45. Р. С. Gilmore, R. E. Gomory. Multistage cutting stock problem of two and more dimensions // Operations Research. 1965. 13(1): 94-120.

46. J.E. Beasley. An exact two-dimensional non-guillotine cutting tree search procedure // Operations Research. 1985. 33(1): 49-64.

47. J.E. Beasley. Bounds for two-dimensional cutting // Journal of the Operational Research Society.' 1985. 36(1): 71-74.

48. M. Padberg. Packing small boxes into a big box // Mathematical Methods of Operations Research. 2000. 52(1): 1-21.

49. J. Terno, R. Lindemann, G. Scheithauer. Zuschnittprobleme und ihre praktische Losung. Verlag Harry Deutsch, Thun und Frankfurt/Main; Fachbuchverlag, Leipzig. 1987.

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

51. Yu. Stoyan, М. Novozhilova. Non-guillotine placement of rectangles into a strip of given width // Pesquisa Operational. 1999. 19(2): 189-211.

52. Yu. Stoyan, A. Pankratov. Regular packing of congruent polygons on the rectangular sheet // European Journal of Operational Research. 1999. 113: 653-675.

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

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

55. М. Kenmochia, Т. Imamichia, К. Nonobeb, М. Yagiurac, Н. Nagamochia. Exact algorithms for the two-dimensional strip packing problem with andwithout rotations // European Journal of Operational Research. 2009. 198(1): 73-83.

56. S. Martello, D. Vigo. Exact solution of the two-dimensional finite bin packing problem // Management Science. 1998. 44: 388-399.

57. G. Wascher, P. Schwerin. A new lower bound for the bin-packing problem and its integration to MTP // Pesquisa Operational. 1999. 19(2): 111-131.

58. M.A. Boschetti. The two-dimensional finite bin packing problem //A Quarterly Journal of Operations Research. 2003. 1(1): 27-42.

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

60. D. Liu, Н. Teng. An improved bl-algorithm for genetic algorithm of the orthogonal packing of rectangles // European Journal of Operational Research. 1999. 112(2): 413-420. •

61. A. Bortfeld, H. Gehring. Applying tabu search to container loading problem // Operations Research Proceedings. 1998. pages 533-538.

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

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

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

65. S. Imahori, M. Yagiura, T. Ibaraki. Local search algorithms for the rectangle packing problem with general spatial costs // Mathematical Programming. 2003. pages 543-569.

66. P. Chen, Y. Chen, M. Goel, F. Mang. Approximation of two-dimensional rectangle packing. Technical report. 1999.

67. E. Hopper, B. Turton. A review of the application of meta-heuristic algorithms to 2D strip packing problems // Artificial Intelligence Review. 2001. 16(4): 257-300.

68. D. Pisinger. • Heuristics for the container loading problem // European Journal of Operational Research. 2002. 141(2): 382-392.

69. Ю. Кочетов, H. Младенович, П. Хансен. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. 2003. 10(1): 11-43.

70. М. Monachi. Algorithms for packing and scheduling problems. PhD thesis. University of Bologna. 2001. •

71. S. Martello, M. Monachi, D. Vigo. An exact approach to the strip-packing problem // INFORMS Journal on Computing. 2003. 15(3): 310-319.

72. S. Fekete, J. van der Veen. Two-dimensional strip packing in reconfigurable computing. In 2nd ESICUP (Euro Special Interest Group on Cutting and Packing) Meeting-, Southampton. 2005.

73. Э.А. Мухачева, А.С. Мухачева. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Автоматика и телемеханика. 2004. 2: 10-15.

74. F. Clautiaux, A. Jouglet, J. Carlier, A. Moukrim. A new constraint programming approach for the orthogonal packing problem // Computers and Operations Research. 2008. 35(3): 944-959.

75. S. Fekete, J. Schepers. New classes of lower bounds for bin packing problems. In Mathematical Programming, pages 257-270. Springer. 1998. •

76. S.P. Fekete, J. Schepers. A general framework for bounds for higher-dimensional orthogonal packing problems // Mathematical Methods of Operations Research. 2004. 60(2): 311-329.

77. B.M. Картак, М.А. Месягутов, Э.А. Мухачева, А.С. Филиппова. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика. 2009. 6: 167-180.

78. В.П. Житников, А.С. Филиппова. Задача прямоугольной упаковки в полубесконечную полосу: поиск решения в окрестности локальной нижней границы // Информационные технологии. 2007. 5: 55-62.

79. S. Hartmann. Project Scheduling under limited resources. Models, methods and applications. Springer, Berlin. 1999.

80. M. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.

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

82. G. Belov, G. Scheithauer, E.A. Mukhacheva. One-dimensional heuristics adapted for two-dimensional rectangular strip packing // The Journal of the Operational Research Society. 2008. 59(6): 823-832.

83. Э.А. Мухачева, Д.А. Назаров. Конструирование прямоугольных упаковок: алгоритм перестройки на базе блочных структур // Автоматика и телемеханика. 2008. 2: 97-113.

84. Н. Murata, К. Fujiyoshi, S. Nakatake, Y. Kajitani. VLSI module placement based on rectangle-packing by the sequence-pair // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1996. 15(12): 1518-1524.

85. K.S. Booth, G.S. Lueker. Testing for the consecutive ones property, interval graphs, and planarity using p'q-tree algorithms // Journal of Computational Systems Science. 1976. 13: 335-379.

86. B.B. Залюбовский. Точные и асимптотически точные алгоритмы для задач упаковки и календарного планирования. PhD thesis. Институт математики им. С. JI. Соболева СО РАН, Новосибирск. 2006.

87. A. Bortfeld. A genetic algorithm for the two-dimensional strip packing problem with rectangular prices // European Journal of Operational Reseach. 2006. 172(3): 814-837.

88. J.O. Berkey, P.Y. Wang. Two dimensional finite bin packing algorithms // Journal of Operational Research Society. 1987. 38: 423-429.

89. R. Baldacci, M. Boschetti. • A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem // European Journal of Operational Research. 2007. 183: 1136-1149.

90. S. Fekete, J. Sthepers. A general framework for bounds for higher-dimensional orthogonal packing problems // Mathematical Methods of Operations Research. 2004. 60:'311-329.

91. A. Lodi, М. Martello, D. Vigo. Recent advances on two-dimensional bin packing problems // Discrete Applied Mathematics. 2002. 123(1-3): 379-396.

92. Э.А. Мухачева, Д.А. Назаров, A.C. Филиппова. Проектирование прямоугольных упаковок с использованием декодеров блочной структуры // Автоматика и телемеханика. 2006. 6: 161-173.

93. В.В. Залюбовский. О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры // Тр. XIII Байкальской международной шк.-семинара. Иркутск. 2005. 1: 461-466.