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

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

4841иг»

Чеканин Владислав Александрович

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

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

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

1 7 МАР 2011

Москва-2011

4841029

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Московский государственный технологический университет «Станкин» на кафедре «Управление и информатика в технических системах»

Научный руководитель: доктор технических наук, профессор

Ковшов Евгений Евгеньевич

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

Демидова Лилия Анатольевна

доктор технических наук, доцент Толчеев Владимир Олегович

Ведущая организация: ГОУ ВПО «Московский государственный

университет приборостроения и информатики»

Защита состоится «31» марта 2011 г. в 14ш часов на заседании диссертационного совета Д 212.147.03 при Московском государственном университете печати (127550, Москва, ул. Прянишникова, 2а).

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Московский государственный университет печати» (МГУП).

Автореферат разослан «26» февраля 2011 г.

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

Агеев В.Н.

Общая характеристика работы

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

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

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

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

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

Степень разработанности проблемы. Разработке методов решения задач ортогональной упаковки посвящены работы, как отечественных авторов (A.C. Филиппова, А.Ф. Валеева, Ю.Г. Стоян, И.В. Романовский, В.М. Картах, Ю.И. Валиахметова, И.П. Норенков, P.P. Ширгазин, A.B. Чиглинцев, В.В. Бухвалова, А.Р. Усманова, М.А. Смагин и др.), так и зарубежных (П. Гилмори, Р. Гомори, И. Терно, Г. Шайтхауэр, Э. Фолкенауэр, А. Бортфельдт, X. Дикхофф, С. Мартелло, Д. Виго, А. Лоди, Е. Хоппер и др). Значительный вклад в развитие методов решения задач упаковки внесла отечественная научная школа Э.А. Мухачевой. Проблемы эволюционного моделирования в задачах упаковки изучены в работах таких исследователей, как В.М. Курейчик, В.В. Курейчик, В.В.Емельянов, И.П. Норенков,

Д.И. Батищев, Э. Фолкенауэр и других отечественных и зарубежных исследователей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

2. Результаты тестирования разработанного критерия останова эволюционного алгоритма.

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

4. Унифицированная модель решения задач упаковки объектов произвольной размерности.

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

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

Реализация результатов работы. Результаты диссертационной работы внедрены в учебный процесс ГОУ ВПО МГТУ «Станкин» и в настоящее время используются при подготовке бакалавров по направлению 080800.62 «Прикладная информатика», магистрантов по магистерским программам: 220200.68-20 «Человеко-машинные системы управления» и 230100.68-01 «Теоретическая информатика». Материалы диссертационной работы использованы в качестве методологической основы при разработке общеуниверситетских курсов лекций и практических занятий по дисциплинам «Информатика» и специальным дисциплинам магистерской подготовки: «Интеллектуальные системы обработки информации», «Технология программирования в интеллектуальных системах управления».

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

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

• научно-практической конференции «Автоматизация и информационные технологии (ЛИТ)» (Москва, ГОУ ВПО МГТУ «Станкин», 2008,2009,2010);

• XI научной конференции ГОУ ВПО МГТУ «Станкин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» -ИММ РАН» по математическому моделированию и информатике, (Москва, 2008);

• XI международной конференции «ПРОТЭК'08» (Москва, ГОУ ВПО МГТУ «Станкин», 2008);

• школе-семинаре «Задачи системного анализа, управления и обработки информации» (Москва, ГОУ ВПО «Московский государственный университет печати», 2008,2009);

• II Всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, ГОУ ВПО «Московский государственный университет печати», 2008);

• III Всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, ГОУ ВПО «Московский государственный университет печати», 2009);

• IV Всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, ГОУ ВПО «Московский государственный университет печати», 2010);

• межвузовской научной конференции молодых ученых и студентов «Инновации в экономике» (Москва, ГОУ ВПО МГТУ «Станкин», 2009);

• III Всероссийской конференции студентов, аспирантов и молодых ученых «Искусственный интеллект: философия, методология, инновации» (Москва, ГОУ ВПО МИРЭА, 2009);

• VII международной научно-практической конференции «Trans-Mech-Art-Chem» (Москва, ГОУ ВПО МИИТ, 2010);

• III научно-образовательной конференции «Машиностроение -традиции и инновации» (Москва, ГОУ ВПО МГТУ «Станкин», 2010).

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

Публикации. По теме диссертации опубликовано 20 научных работ, из них 14 основных, в том числе 3 статьи в изданиях, входящих в Перечень ведущих периодических изданий ВАК Министерства образования и науки РФ и 1 монография.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырёх глав, списка литературы и трёх приложений. Основной текст содержит 155 страниц. Список литературы состоит из 137 наименований. Приложения выполнены на шести страницах.

Основное содержание работы

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

В первой главе представлен обзор существующих задач раскроя-упаковки и методов их решения. Приведена классификация задач раскроя-упаковки, проведенная H. Dyckhoff, а также современная классификация, предложенная H. Dyckhoff, J. Terno и G. Scheithauer.

В общем виде задача ортогональной упаковки размерности D описывается следующим образом: имеются набор прямоугольных контейнеров с габаритами \Vj,Wj ,...,}Vj'],j = l,...,N и набор прямоугольных предметов

[w,1,iv,2,...,H'P},/ = l,...,w. Запишем положение объекта i в j-м контейнере в следующем виде: {x]j;x^;...;x®). Необходимо разместить все объекты в минимальном числе контейнеров при выполнении следующих условий:

1) ребра упакованных в контейнере прямоугольных объектов параллельны ребрам контейнера;

2) упакованные объекты не пересекаются друг с другом, т.е. для Md = 1,...,ДV/,<? = 1,..„и,i*q >xdqj + w^jv(х% >xfj + wf);

3) упакованные объекты не пересекаются со сторонами контейнера, т.е. для Vd = l,...,D;Vi = l,...,n {х? >o)*(xtj+w? <ivf).

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

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

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

Решение любой задачи упаковки п объектов кодируется строкой 5 натуральных чисел длиной 2п:

5 = {А{,ВЬА2,В2.....А„,В„}, (1)

где число ^ содержит номер типа /'-го размещаемого объекта из списка размещаемых объектов; число Б, - информацию об ориентации этого объекта в пространстве контейнера. Целевой функцией является отношение суммарного объема размещенных в контейнере объектов к объему V описанного вокруг полученной Б -мерной упаковки контейнера:

о ,

5 = ^—, (2)

V

где п! - число размещенных в контейнере объектов.

В узловой модели контейнер хранит информацию о размещенных объектах в виде набора точек, называемых узлами. Каждый узел к содержит структуру вида:

ик=(Хк,а,Ь), (3)

где Хк =|с|1,х|,...,л|3| - вектор положения узла в контейнере при решении Б -мерной задачи ортогональной упаковки, а - ссылка на присоединенный к узлу объект, Ь - номер положения ориентации объекта в контейнере. Выделяется два типа узлов: свободные (с нулевой ссылкой на тип присоединенного объекта) и несвободные.

Разработанная модель «виртуальные объекты» является производной от узловой модели. В модели «виртуальные объекты» узлы дополнительно содержат информацию о наибольших габаритах ортогональных объектов, которые могут быть к ним присоединены. Каждый узел контейнера содержит структуру вида:

и'к=(Хк,Рк,а,Ь), (4)

где Рк = \р\,р1,---,р!к\- вектор виртуального объекта, описывающий габариты наибольшего прямоугольного объекта, который может быть присоединен к узлу к без пересечений с размещенными в контейнере объектами.

На рис. 1 изображен двухмерный контейнер, содержащий объект с габаритами / х и', присоединенный к узлу 1 контейнера с вектором виртуального объекта Р = {Ц1У}. После присоединения объекта в контейнере образованы новые узлы: узел 2 с вектором Р = {Ь-1;1¥}, узелЗ с вектором Р = {Ь-1;1¥-ц>} и узел 4 с вектором Р = {¿; IV - м>}.

Рис. 1. Виртуальные объекты контейнера

Работа модели «виртуальные объекты» представлена в виде блок-схемы на рис. 2.

С

Выбор следующего объекта для размещения

Создание набора объектов

D

Генерации первого узда и контейнере в точке {О, 0,... . 0}

Выбор первого объекта для размещения

I

Присоединение объекта к свободному узлу

Выбор следующего узла из списка свободных узлов

Формирование новых

узлов и перерасчет виртуальных объектов всех узлов: контейнера

Рис. 2. Блок-схема алгоритма размещения в модели «виртуальные

объекты»

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

Рис. 3. Качество размещения для различных моделей представления

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

Рис. 4. Скорость размещения для различных моделей представления

При использовании модели «виртуальные объекты» определение возможности присоединения размещаемого объекта к узлу вместо проверки на

0.88

Узловая Блочная Модель модель модель "виртуальные объекты"

С

Узловая Блочная Модель модель модель "виртуальные объекты"

пересечение со всеми размещенными в контейнере объектами сводится к единственной проверке нахождения объекта целиком внутри виртуального объекта узла к: (wj. <pi)v/ = \,...,d, к которому он присоединяется, за счет чего скорость размещения повышается.

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

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

Декодер Packer работает следующим образом:

1. Проводятся выбор размещаемого объекта i из строки решения s и выбор контейнера с, содержащего, как минимум, один свободный узел. В случае если выбраны все объекты, работа декодера завершается.

2. Осуществляется последовательный поиск свободного узла j текущего контейнера с, к которому возможно присоединить текущий объект i:wf < PjVd = 1,...,Z). В случае если искомый узел не может быть найден, осуществляется переход к следующему контейнеру с:-с+1 и повтор п.2. В случае если среди всех контейнеров не найден искомый узел, выполняется переход к п.1.

3. Объект / присоединяется к найденному узлу j контейнера с. В результате формируются новые узлы

{U *}= fx';*} + „})х [х]-х] + wf)x... х (xf^xf + wf3)]. (5)

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

D

f h

D

( ъ D Л

А тт rj/d

s j пк т

A=1V d=h+1 7 A=1V d=h+1 У

Vje{U=>U*}. (6)

Осуществляется переход к п.1.

Описанный алгоритм размещения объектов позволяет динамически заполнять контейнеры объектами в порядке, определяемом положением узлов контейнеров. Декодер Packer при размещении объектов учитывает все свободные области контейнера и размещает новые объекты как можно ближе к основанию контейнера благодаря упорядочиванию узлов после добавления в контейнер каждого нового объекта.

Исследована ресурсная эффективность алгоритма размещения ортогональных объектов. Его верхняя асимптотическая оценка равна o(jV3). Описаны оптимизационные методы повышения скорости размещения объектов в контейнерах. Предложена модифицированная структура узлов в контейнере, использование которой в среднем вдвое сокращает время размещения объектов.

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

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

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

Таблица 1.

Действия эволюционного алгоритма при различных значениях параметра останова К

Число пройденных эпох после обновления популяции

К 2К ЗК

Постоянный параметр Лучшее решение в текущей популяции обновление популяции останов поиска

Лучшее найденное решение обновление популяции останов поиска

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

• значение параметра останова не зависит от числа пройденных эпох;

• время поиска решения прямо пропорционально значению параметра останова поиска (см. рис. 5);

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

Рассмотрены и исследованы следующие эволюционные алгоритмы: алгоритм отжига, генетический алгоритм, а также комбинированный

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

о. 0.20 я

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Значение параметра останова

■ Время решения —Целевая функция

Рис. 5. Графики зависимости решений от значения параметра останова

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

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

1) присоединение к узлу у текущего контейнера наиболее подходящего объекта / вдоль выбранного направления упаковки /:

(7)

2) присоединение к узлу ] текущего контейнера первого подходящего объекта / с максимальным объемом:

а ° ?

ПрМ>?

и=1 </=1

(8)

3) присоединение первого объекта ; из списка упорядоченных по ширине неразмещенных объектов к ближайшему свободному узлу } текущего контейнера:

Vh<j3d:pcj <w?,w? <pjvd = l,...,D. (9)

4) присоединение первого объекта i из списка тс, упорядоченных по объему неразмещенных объектов к ближайшему свободному узлу j текущего контейнера при выполнении условия (9).

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

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

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

В четвертой главе приведено описание разработанной унифицированной библиотеки классов задач упаковки «UniPacker»; приведены результаты проведенных вычислительных экспериментов над разработанными алгоритмами и методами.

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

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

• задач упаковки различных видов объектов;

• задач многомерной упаковки (одномерной, двухмерной, трёхмерной и большей размерности);

• задач упаковки на основе различных эвристических алгоритмов.

Унификация библиотеки классов достигается благодаря инвариантности

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

Рис. 6. Диаграмма классов разработанной библиотеки задач упаковки

Описана программная реализация разработанных алгоритмов и методов в виде прикладного программного обеспечения для решения задач ортогональной упаковки, созданного на основе разработанной унифицированной библиотеки классов задач упаковки «UniPacker». Разработанные алгоритмы реализованы на платформе Microsoft Win 32 с использованием языка программирования С++. Результаты проведенных вычислительных экспериментов показали высокую эффективность разработанных алгоритмов решения задач ортогональной упаковки объектов.

Эксперимент 1. Решение задами двухмерной упаковки на листы

Эффективность применения разработанных алгоритмов и методов для решения задач двухмерной контейнерной ортогональной упаковки объектов исследована на эталонных примерах из библиотеки OR-library, размещенной на сайте http://people.brunel.ac.uk/~mastiib/ieb/info.html, для наборов объектов, взятых из тестовых задач, сформулированных S.P. Fekete и J. Schepers, для которых известны точные нижние границы решений. Во всех задачах габариты контейнеров одинаковые и равны 100x100. В ходе вычислительного эксперимента были решены задачи двухмерной прямоугольной упаковки размерности яг = 40, 50, 100, 150, 250, 500, 1000. Для каждой задачи была проведена серия из 100 экспериментов. Показателем качества размещения является относительное отклонение ц от нижней границы, которое рассчитывается по формуле:

ц(%) = *'~Л'100%, (10)

т

где N, - целевая функция решения (число заполненных объектами

контейнеров), Л* - точная нижняя граница задачи.

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

• генетический блочный алгоритм Норенкова И.П. GMA;

• жадный генетический алгоритм Genetic Greedy Sub (GGSub).

Полученные результаты сведены в таблицу 2.

Таблица 2.

Результаты эксперимента 1 с задачами упаковки на листы_

Отклонение от нижней границы ц, %

Типы задач GMA GGSub Packer FIT Packer MGA

ngcutfs 1 2.39 1.87 2.03 1.63

ngcutfs 2 1.76 1.37 1.56 1.06

ngcutfs 3 0.88 0.88 1.02 0.78

Мультиметодный генетический алгоритм Packer MGA с разработанными эвристиками и унифицированным декодером Packer обеспечивает наилучшее размещение объектов на всех классах решаемых задач двухмерной контейнерной упаковки на листы.

Эксперимент 2. Решение задачи двухмерной упаковки на полубесконечную полосу

Численный эксперимент проводился при решении эталонных тестовых задач рулонного раскроя из статей Berkey и Wang (классы задач С1-С6), а также

из статей Martello и Vigo (классы задач С7-С10). В ходе эксперимента было решено 500 задач раскроя прямоугольных объектов на полубесконечной полосе. Число прямоугольников в каждом классе - от 20 до 100. Показателем эффективности рулонного раскроя служит отклонение от нижней границы, которое рассчитывается по следующей формуле:

т](%) = ~^-т%, (11)

где L - длина занятой части полосы, - теоретическая нижняя граница задачи.

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

• генетический алгоритм Бортфельдта A. SPGAL;

• жадный генетический алгоритм GGSub;

• генетический блочный алгоритм GBA;

• алгоритм поиска с запретами Ермаченко А.И. TS;

• генетический блочный алгоритм Норенкова И.П. GMA;

• реализованный мультиметодный генетический алгоритм с разработанными эвристиками Packer MGA.

Таблица 3.

Результаты эксперимента 2 с задачами двухмерной упаковки на

полубесконечную полосу

Отклонение от нижней границы tj, %

Класс задач SPGAL GGSub GBA TS GMA Packer MGA

С1 0.75 0.59 0.89 0.58 1.21 0.70

С2 0.84 1.23 1.21 0.80 1.24 0.78

СЗ 2.52 1.99 2.75 1.71 3.23 1.45

С4 3.08 3.22 3.17 3.33 3.61 4.04

С5 2.53 2.08 2.77 2.06 3.25 2.04

С6 4.67 4.44 4.56 4.24 4.97 5.79

С7 1.22 1.13 1.35 1.12 1.40 1.17

С8 3.66 3.60 4.81 3.35 5.54 5.65

С9 0.12 0.07 0.07 0.07 0.07 0.11

СЮ 3.04 3.19 3.92 2.82 4.60 2.79

Среднее С1-С10 2.20 2.13 2.55 1.98 2.91 2.45

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

Показана эффективность применения классического генетического алгоритма с унифицированным декодером Packer при решении задач трёхмерной ортогональной упаковки объектов. Применение генетических алгоритмов при решении задач трёхмерной ортогональной упаковки объектов позволяет более чем на 16% повысить среднее значение целевой функции конечного решения, что говорит о целесообразности их применения.

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

В результате проведенных исследований получены следующие новые научные и практические результаты:

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

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

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

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

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

6. Разработана унифицированная модель решения задач упаковки объектов произвольной размерности в виде универсальной библиотеки классов «UniPacker», на основе которой разработано специализированное программное обеспечение для реализации и исследования моделей, алгоритмов и методов решения задачи ортогональной упаковки.

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

Основные публикации по теме диссертации

В изданиях, рекомендованных ВАК Министерства образования и науки

РФ:

1. Чеканин В.А., Ковшов Е.Е. Систематизация и анализ структур данных при автоматизации управления складом на основе генетических алгоритмов / В.А. Чеканин, Е.Е. Ковшов // Известия высших учебных заведений. Проблемы полиграфии и издательского дела. 2008. - № 5. С. 42-51.

2. Чеканин В.А., Ковшов Е.Е., Хуэ H.H. Повышение эффективности эволюционных алгоритмов при решении оптимизационных задач упаковки объектов / В.А. Чеканин, Е.Е. Ковшов, H.H. Хуэ // Системы управления и информационные технологии. 2009. - № 3. С. 63-67.

3. Чеканин В.А., Ковшов Е.Е. Моделирование и оптимизация технологических операций в промышленном производстве на основе эволюционных алгоритмов / В.А. Чеканин, Е.Е. Ковшов // Технология машиностроения. 2010. — № 3. С. 53-57.

Монографии:

4. Чеканин В.А., Ковшов Е.Е. Эволюционно-генетические алгоритмы в оптимизации контейнерной упаковки отходов промышленного производства / В.А. Чеканин, Е.Е. Ковшов // Управление качеством машиностроительных технологических процессов формообразования (серия «Производство, Технология, Экология - ПРОТЭК») /

B.И. Серебряков, Л.Э. Шварцбург. - М.: ГОУ ВПО МГТУ «Станкин», 2009. С. 79-88.

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

5. Чеканин В.А. Комплексный подход в решении задачи трёхмерной упаковки / В.А. Чеканин // Задачи системного анализа, управления и обработки информации: Межвузовский сборник научных трудов. Вып. 2. - МГУП, 2008. С. 168-171.

6. Чеканин В.А. Выбор оптимальных параметров генетического алгоритма при решении задачи упаковки / В.А. Чеканин // Производство. Технология. Экология. Научные труды. Сборник монографий №11 в 2-х тт. Том 2: Москва / Под ред. члсн-корр. РАН Ю.М. Соломенцева и проф. Л.Э. Шварцбурга. - М.: «Янус-К», 2008.

C. 234-236.

7. Чеканин В.А. Компонентный объектно-ориентированный подход при разработке программного обеспечения для автоматизации управления складом / В.А. Чеканин // Материалы XI научной конференции МГТУ «Станкин» и «Учебно-научного центра математического

моделирования МГТУ «Станкин» - ИММ РАН» по математическому моделированию и информатике: Программа. Сборник докладов. / Под ред. O.A. Казакова. - М.: ИЦ ГОУ ВПО МГТУ «Станкин». 2008. С. 127-130.

8. Чеканин В.А. Решение задачи упаковки при автоматизации склада путем применения аппарата генетических алгоритмов / В.А. Чеканин II Прикладная информатика и математическое моделирование: Межвузовский сборник научных трудов. - М.: МГУП, 2008. С. 103-108.

9. Чеканин В.А. Унификация библиотеки классов эволюционных алгоритмов для решения организационно-логистических задач /

B.А. Чеканин II Инновации в экономике-2009: материалы научной конференции молодых ученых и студентов. - М.: ГОУ ВПО МГТУ «Станкин», 2009. С. 103-106.

Ю.Чеканин В.А. Сравнительный анализ эвристических алгоритмов для решения задачи трёхмерной упаковки объектов / В.А. Чеканин // Прикладная информатика и математическое моделирование: Межвузовский сборник научных трудов. - М.: МГУП, 2009.

C. 179-188.

11.Чеканин В.А. Выбор критерия остановки работы эволюционного алгоритма как фактора получения субоптимального решения /

B.А. Чеканин // Искусственный интеллект: философия, методология, инновации. Материалы III Всероссийской конференции студентов, аспирантов и молодых ученых, г. Москва, МИРЭА, 11-13 ноября 2009 г. Под ред. Д.И. Дубровского и Е.А. Никитиной. - М.: «Связь-Принт», 2009. С. 324-326.

12.Чеканин В.А. Исследование модели виртуальных объектов в задаче ортогональной упаковки произвольной размерности / В.А. Чеканин // Задачи системного анализа, управления и обработки информации: Межвузовский сборник научных трудов. Вып. 3. - М.: МГУП, 2010.

C. 176-181.

13.Чеканин В.А. Принципы оптимального выбора критерия остановки работы эволюционного алгоритма при решении оптимизационной задачи упаковки / В.А. Чеканин // Труды VII Международной научно-практической конференции «TRANS-MECH-ART-CHEM». - М.: МИИТ, 2010. С. 385-386. 14.Чеканин В.А. Оптимизация прямоугольного раскроя в заготовительном производстве на основе мультиметодного генетического алгоритма / В.А. Чеканин // Материалы III научно-образовательной конференции «Машиностроение - традиции и инновации» (МТИ-2010). Секция «Автоматизация и информационные технологии». Сборник докладов. М.: МГТУ «Станкин», 2010. С. 194-200.

Подписано в печать: 24.02.2011

Заказ № 5037 Тираж - 110 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ОГЛАВЛЕНИЕ.

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

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

1.1. Классификация задач упаковки, проведенная Н. Буск1юГ£.

1.2. Современная классификация задач упаковки.

1.3. Задача ортогональной упаковки.

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

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

1.4. Методы решения задач упаковки.

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

1.4.2. Методы комбинаторной оптимизации.

1.4.3. Эвристические методы.

1.4.4. Вероятностные и эволюционные методы.

1.5. Постановка задачи исследовательской работы.

ГЛАВА 2. АЛГОРИТМЫ КОНСТРУИРОВАНИЯ УПАКОВКИ.

2.1. Представление контейнеров.

2.2. Представление размещаемых объектов.

2.2.1. Представление на основе многомерного массива.

2.2.2. Узловая модель.:.

2.2.3. Модель «виртуальные объекты».

2.2.4. Блочная модель представления объектов.

2.2.5. Тестирование моделей.

2.3. Кодирование размещаемых объектов.

2.3.1. Создание групп геометрически одинаковых объектов.

2.3.2. Алгоритм формирования строки решения.

2.3.3. Алгоритм декодирования строки решения.

2.4. Размещение упаковываемых объектов.

2.4.1. Формирование узлов.

2.4.2. Декодер строки решения Packer.

2.4.3. Организация набора узлов.

2.4.4. Проверка возможности присоединения объекту к узлу.

2.4.5. Оценка ресурсной эффективности разработанных алгоритмов.

2.4.6. Исключительные ситуации при размещении объектов.

2.5. Выводы по главе 2.

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

3.1. Алгоритм получения решения оптимизационной задачи.

3.1.1. Формирование начального множества решений.

3.1.2. Локальный оптимум решения.

3.1.3. Критерии останова поиска эволюционного алгоритма.

3.2. Методы поиска оптимального решения.

3.3. Эволюционные алгоритмы.

3.3.1. Алгоритм отжига.

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

3.3.3. Комбинированный генетический алгоритм.

3.3.4. Генетические операторы.

3.3.5. Выбор параметров генетического алгоритма.

3.3.6. Мультиметодный генетический алгоритм.

3.3.7. Выбор алгоритма оптимизации конечного решения.

3.4. Выводы по главе

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ И ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ.

4.1. Программная реализация алгоритмов решения задач многомерной упаковки.

4.1.1. Структуры данных.

4.1.2. Особенности разработанной библиотеки классов задач упаковки.

4.1.4. Реализация интерфейса пользователя в программном решении.

4.1.5. Решение задач двухмерной и одномерной упаковки.

4.2. Вычислительные эксперименты.

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

4.2.2. Решение задачи двухмерной упаковки объектов.

4.2.3. Решение задачи трёхмерной упаковки объектов.

4.3. Выводы по главе 4.

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

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

Таблица 1.

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

Задача Область применения

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

Промышленный раскрой • системы оптимального раскроя промышленных материалов; • обувная и текстильная промышленность (автоматизированные системы раскроя материалов)

Компоновочный синтез • компоновка и размещение оборудования; • планировка помещений; • электронная промышленность (проектирование больших интегральных схем)

Продолжение таблицы 1

Задача Область применения

Покрытие заданной области одинаковыми объектами (кругами, шарами) • системы автоматической противопожарной защиты; • системы телекоммуникаций; • агротехнические и экологические системы; • в медицине (лучевая терапия)

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

Упаковка цилиндрических объектов в прямоугольные контейнеры • системы проектирования перевозки грузовых контейнеров; • системы проектирования захоронения радиоактивных отходов

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

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

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

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

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

Разработке методов решения задач ортогональной упаковки посвящены работы, как отечественных авторов (A.C. Филиппова, А.Ф. Валеева, Ю.Г. Стоян, И.В. Романовский, В.М. Картак, Ю.И. Валиахметова,

И.П. Норенков, P.P. Ширгазин, A.B. Чиглинцев, В.В. Бухвалова, А.Р. Усманова, М.А. Смагин и др.), так и зарубежных (П. Гилмори, Р. Гомори, И. Терно, Г. Шайтхауэр, Э. Фолкенауэр, А. Бортфельдт, X. Дикхофф, С. Мартелло, Д. Виго, А. Лоди, Е. Хоппер и др). Значительный вклад в развитие методов решения задач упаковки внесла отечественная научная школа Э.А. Мухачевой. Проблемы эволюционного моделирования в задачах упаковки изучены в работах таких исследователей, как В.М. Курейчик, В.В. Курейчик, В.В. Емельянов, И.П. Норенков, Д.И. Батищев, Э. Фолкенауэр и других отечественных и зарубежных исследователей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

2. Результаты тестирования разработанного критерия останова эволюционного алгоритма.

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

4. Унифицированная модель решения задач упаковки объектов произвольной размерности.

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

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

Реализация результатов работы. Результаты диссертационной работы внедрены в учебный процесс ГОУ ВПО МГТУ «Станкин» и в настоящее время используются при подготовке бакалавров по направлению 080800.62 «Прикладная информатика», магистрантов по магистерским программам: 220200.68-20 «Человеко-машинные системы управления» и 230100.68-01 «Теоретическая информатика». Материалы диссертационной работы использованы в качестве методологической основы при разработке общеуниверситетских курсов лекций и практических занятий по дисциплинам «Информатика» и специальным дисциплинам магистерской подготовки: «Интеллектуальные системы обработки информации», «Технология программирования в интеллектуальных системах управления».

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

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

• научно-практической конференции «Автоматизация и информационные технологии (АИТ)» (Москва, ГОУ ВПО МГТУ «Станкин», 2008, 2009, 2010);

• XI научной конференции ГОУ ВПО МГТУ «Станкин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» -ИММ РАН» по математическому моделированию и информатике, (Москва, 2008);

• XI международной конференции «ПРОТЭК'08» (Москва, ГОУ ВПО МГТУ «Станкин», 2008);

• школе-семинаре «Задачи системного анализа, управления и обработки информации» (Москва, ГОУ ВПО «Московский государственный университет печати», 2008, 2009);

• II Всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, ГОУ ВПО «Московский государственный университет печати», 2008);

• III Всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, ГОУ- ВПО «Московский государственный университет печати», 2009);

• IV Всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, ГОУ ВПО «Московский государственный университет печати», 2010);

• межвузовской научной конференции молодых ученых и студентов «Инновации в экономике» (Москва, ГОУ ВПО МГТУ «Станкин», 2009);

• III Всероссийской конференции студентов, аспирантов и молодых ученых «Искусственный интеллект: философия, методология, инновации» (Москва, ГОУ ВПО МИРЭА, 2009);

• VII международной научно-практической конференции «Trans-Mech-Art-Chem» (Москва, ГОУ ВПО МИИТ, 2010);

• III научно-образовательной конференции «Машиностроение — традиции и инновации» (Москва, ГОУ ВПО МГТУ «Станкин», 2010).

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

Публикации. По теме диссертации опубликовано 20 научных работ, из них 14 основных, в том числе 3 статьи в изданиях, входящих в Перечень ведущих периодических изданий ВАК Министерства образования и науки РФ и 1 монография.

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

Заключение

В результате проведенных исследований получены следующие новые научные и практические результаты:

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

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

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

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

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

6. Разработана унифицированная модель решения задач упаковки объектов произвольной размерности в виде универсальной библиотеки классов «ишРаскег», на основе которой разработано специализированное программное обеспечение для реализации и исследования моделей, алгоритмов и методов решения задачи ортогональной упаковки.

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

1. Бабаев Ф.В. Оптимальный раскрой материалов с помощью ЭВМ. -М.Машиностроение, 1982. 168 е., ил.

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

3. Библиотека OR-library наборов объектов из задач Fekete и Schepers. Электронный ресурс. — Режим доступа: http://people.brunel.ac.uk/~mastiib/ieb/info.html (дата обращения: 13 декабря 2010).

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

5. Валеева А. Ф. Применение конструктивных эвристик в задачах раскроя-упаковки // Приложение к журналу «Информационные технологии», №11. 2006. С. 1-24.

6. Валиахметова Ю.И., Карамова Е.В. Расширение генетического алгоритма комбинирования эвристик для решения задачи прямоугольной упаковки // Вестник ВЭГУ. — 2009. №2. С. 89-94.

7. Валиахметова Ю.И., Филиппова A.C. Мультиметодный генетический алгоритм для решения задач ортогональной упаковки // Информационные технологии. 2007. №12. С. 50-56.

8. Васильев В.И., Ильясов Б.Г. Интеллектуальные системы управления с использованием генетических алгоритмов // Приложение к журналу «Информационные технологии». — 2000. № 12. 25 с.

9. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация: Пер. с англ. М.: Мир, 1985. - 509 е., ил.

10. Гладков JI.A., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2006.-320 с.

11. Горанский Г.К., Зозулевич Д.М., Шерлинг Д.Р. Алгебрологический метод решения геометрических задач автоматизации проектирования с помощью ЭЦВМ. В кн.: Вычислительная техника в машиностроении. Минск: ИТК АН БССР, апрель 1967. С. 121-127.

12. Гудман Э.Д. Эволюционные вычисления и генетические алгоритмы// Обозрение прикладной и промышленной математики, 1996. — Т.З, вып.5.

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

14. Де Янг К. Эволюционные вычисления: достижения и проблемы // Обозрение прикладной и промышленной математики, 1996. — Т.З, вып.5.

15. ДейтелХ., ДейтелП. Как программировать на С++: Третье издание. Пер. с англ. -М.: ЗАО «Издательство БИНОМ», 2003 г. 1152 е.: ил.

16. Джонс М.Т. Программирование искусственного интеллекта в приложениях / М. Тим Джонс; Пер. с англ. Осипов А.И. М.: ДМК Пресс, 2006-312 е.: ил.

17. Емельянов В.В., Курейчик В.В., Курейчик В.М., Теория и практика эволюционного моделирования. М.: ФИЗМАТЛИТ, 2003. 432 с.

18. Ермошин A.C., Плиско В.А. Экспериментальное определение рациональных параметров генетического алгоритма для решения задачи коммивояжера на основе сравнений с точными решениями // Прикладная информатика и математическое моделирование. — 2007. С. 4-10.

19. Канторович JI.B., Залгаллер В.А. Расчёт рационального раскроя материалов. Лениздат, Л., 1951. С. 30-61.

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

21. КартакВ.М. Матричный алгоритм поиска оптимального решения для решения задачи упаковки прямоугольников в полубесконечную полосу // Информационные технологии. 2008. — №2. С. 24-30.

22. Кент Бек. Экстремальное программирование Питер, 2002. — 224 с.

23. Ковшов Е.Е., Чеканин В.А. Систематизация и анализ структур данных при автоматизации управления склада на основе генетических алгоритмов // Вестник высших учебных заведений. Проблемы полиграфии и издательского дела. 2008. - №5. С. 42-51.

24. Куприянов М.С., Матвиенко Н.И. Генетические алгоритмы и их реализации в системах реального времени // Информационные технологии.-2001.-№1. С. 17-21.

25. Курейчик В.В. Эволюционные методы решения оптимизационных задач. Таганрог: Изд-во ТРТУ, 1999. 99 с.

26. Курейчик В.М. Генетические алгоритмы. Обзор и состояние // Новости искусственного интеллекта. — 1998. №3. С. 14-64.

27. Курейчик В.М. Генетические алгоритмы. Состояние, проблемы, перспективы // Известия академии наук. Теория и системы управления. 1999.-№1. С. 144-160.

28. Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование // Известия академии наук. Теория и системы управления. 2002. -№1. С. 127-137.

29. Ли К. Основы САПР (CAD/CAM/CAE). СПб.: Питер, 2004. - 560 с.

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

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

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

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

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

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

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

37. Мухачева Э.А., Мухачева A.C. JI.B. Канторович и задачи раскроя-упаковки: новые подходы для решения комбинаторных задач линейного раскроя и прямоугольной упаковки. — Записки научных семинаров ПОМИ. Том 312. 2004. С. 239-255.

38. Мухачева Э.А., Валеева А.Ф., Филиппова A.C., Поляковский С.Ю. Задача двухмерной контейнерной упаковки: нижние границы и численный эксперимент с алгоритмами локального поиска оптимума // Информационные технологии. 2006. № 4. С. 45-52.

39. Мухачева Э.А., Мухачева A.C., ВалееваА.Ф., КартакВ.М. Методы локального поиска оптимума в задачах ортогонального раскроя и упаковки: аналитический обзор и перспективы развития // Информационные технологии. 2004. №5, приложение. С. 2-17.

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

41. Описание методов мутации. Электронный ресурс. Режим доступа: http://www.sussex.ac.uk/space-science/Nature/tsp.html (дата обращения: 13 декабря 2010).

42. Петунин A.A., Мухачева Э.А., Филиппова A.C. Метод прямоугольной аппроксимации для решения задач нерегулярного фигурного раскроя-упаковки// Информационные технологии. 2008. № 1. С. 28-31.

43. Подлазова A.B. Генетические алгоритмы на примерах решения задач раскроя // Проблемы управления. 2008. №2. С. 57-63.

44. Прикладное программное обеспечение трёхмерной упаковки объектов 3D Load Packer. Электронный ресурс. — Режим доступа: http ://astrokettle. com/ргЗ dip .html (дата обращения: 13 декабря 2010).

45. Пушкарёва Г.В. Генетическое программирование при автоматизированном проектировании управляющих программ для систем ЧПУ // Сборник научных трудов НГТУ. 2004. №1. С. 67-72.

46. Редько В.Г. Эволюционная кибернетика. — М.: Наука, 2001. 159 с.

47. Романов В.П. Интеллектуальные информационные системы в экономике: Учебное пособие / Под ред. Н.П. Тихомирова. — М.: Экзамен, 2003.-496 с.

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

49. Сортировка данных в массиве. Электронный ресурс. Режим доступа: http://www.rsdn.гu/artic 1 c/alg/sоrt.xml (дата обращения: 13 декабря 2010).

50. Сравнение алгоритмов сортировки массива. Электронный ресурс. — Режим доступа: http://codelib.ru/task/arraysort benchmark (дата обращения: 13 декабря 2010).

51. Стецюра Г.Г. Эволюционные методы в задачах управления, выбора, оптимизации // Проблемы и системы управления. 1998. №3. С. 54-62.

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

53. Труб И.И. Объектно-ориентированное моделирование на С++. — СПб.: Питер, 2006.-411 с.

54. Уайс Марк Аллен. Организация структур данных и решение задач на С++ / Уайс М.А.; пер. с англ. МА. ЭКОМ Паблишерз, 2008. - 896 с.

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

56. Фаулер М., Скотт К. UML. Основы. Пер. с англ. - СПб: Символ-Плюс, 2002.-192 с.

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

58. Чеканин В.А. Выбор оптимальных параметров генетического алгоритма при решении задачи упаковки // Производство. Технология. Экология. Научные труды. Сборник монографий №11 в 2-х тт. Том 2:

59. Москва / Под ред. член-корр. РАН Ю.М. Соломенцева и проф. Л.Э. Шварцбурга. — М.: «Янус-К», 2008. С. 234-236.

60. Чеканин В.А. Комплексный подход в решении задачи трёхмерной упаковки // Задачи системного анализа, управления и обработки информации: Межвузовский сборник научных трудов. Вып. 2. — МГУП, 2008. С. 168-171.

61. Чеканин В.А. Решение задачи упаковки при автоматизации склада путем применения аппарата генетических алгоритмов // Прикладная информатика и математическое моделирование: Межвузовский сборник научных трудов. -М.: МГУП, 2008. С. 103-108.

62. Чеканин В.А. Сравнительный анализ эвристических алгоритмов для решения задачи трёхмерной упаковки объектов // Прикладная информатика и математическое моделирование: Межвузовский сборник научных трудов. -М.: МГУП, 2009. С. 179-188.

63. Чеканин В.А. Унификация библиотеки классов эволюционных алгоритмов для решения организационно-логистических задач // Инновации в экономике-2009: материалы научной конференции молодых ученых и студентов. М.: ГОУ ВПО МГТУ «Станкин», 2009. С. 103-106.

64. Чеканин В.А., Ковшов Е.Е. Моделирование и оптимизация технологических операций в промышленном производстве на основе эволюционных алгоритмов // Технология машиностроения. 2010. №3. С. 53-57.

65. Чеканин В.А., Ковшов Е.Е., Хуэ H.H. Повышение эффективности эволюционных алгоритмов при решении оптимизационных задач упаковки объектов / В.А. Чеканин, Е.Е. Ковшов, H.H. Хуэ // Системы управления и информационные технологии. — 2009. № 3. С. 63-67.

66. Ширгазин P.P. Эволюционные методы и программное обеспечение для решения задач ортогональной упаковки на базе блочных структур // Автореф. дис. на соиск. уч. степ. канд. техн. наук: 05.13.18. — Уфа.: УГАТУ, 2006. 15 с.

67. Ширгазин P.P., Ильина К.В. Упаковка прямоугольников в полубесконечную полосу: декодеры пары последовательностей и замещения // Принятие решений в условиях неопределенности: сб.статей. Уфа: УГАТУ, 2005. С. 82-88.

68. Babel, L., Chen, В., Kellerer, Н., Kotov, V. Algorithms for on-line bin-packing problems with cardinality constraints. Discrete Applied Mathematics, 2004, Vol. 143, pp. 238-251.

69. Beasley J.E. A population heuristic for constrained two-dimensional nonguillotine cutting // EJOR. 2004. Vol. 156. P. 601-627.

70. Beasley, D., Bull, D.R., and Martin, R.R. «An Overview of Genetic Algorithm: Part I, Fundamentals», University Computing, Vol. 19, No. 2, pp. 58-69, Inter-University Committee on Computing, 1993.

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

72. Birgin, E.G., Martinez, J.M., Ronconi, D.P. Optimizing the packing of cylinders into a rectangular container: A nonlinear approach. European Journal of Operational Research, 2005, Vol. 160, pp. 19-33.

73. Bischoff E., Washer G., edit. Special issue: Cutting and packing // European Journal of Operational Research. 1995. P. 84.

74. Bortfeldt A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces // University of Hagen. Germany. 2004. Preprint.

75. Bortfeldt, A., Gehring, H. A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, 2001, Vol. 131, pp. 143-161.

76. Boschetti M.A. The two-dimensional finite bin packing problem // Quaterly Journal of the Belgian, French and Italian Operations Research Societes. Vol. l.No. 2. 2002.

77. Caprara, A., Monaci, M. On the two-dimensional knapsack problem. Operations Research Letters, 2004, Vol. 32, pp. 5-14.

78. Coffman E., Garey M., Johnson D. Approximation algorithms for bin-packing. An updated survey // Algorithm Design for Computer System Design. Berlin etal. 1984.

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

80. DyckhoffH. A typology of cutting and packing problems. European Journal of Operation Research, 1990, Vol. 44, pp. 145-159.

81. DyckhoffH., Scheithauer G., Terno J. Cutting and packing. In: Annotated Bibliographies in Combinatorial Optimization, M. Dell'Amico, F. Maffioli, S. Martello (eds.), John Willey&Sons, 1997, pp. 393-412.

82. EhrgottM. Approximative solution methods for multiobjective combinatorial optimization / M. Ehrgott, X. Gandibleux // TOP. Vol. 12. 2004. № l.pp. 1-63.

83. Fekete, S.P., Schepers, J. New classes of fast lower bounds for bin packing problems //ReportNo. 97.265a. 2001.

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

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

86. Gary, M., Johnson, D., Computers intractability: a guide to the theory of NP-completeness. San Francisco: W.H.Freeman, 1979.

87. Gehring H., Bortfeldt A. A Genetic Algorithm for Solving the Container Loading Problem // International transactions in operation research. 1997. V. 4. N5/6. P. 401-418.

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

89. Gilmore, P.C., Gomory, R.E. Multistage cutting stock problems of two and more dimensions. Operations Research, 1965, Vol. 13, P. 94-120.

90. Healy, P., Moll, R. A local optimization-based solution to the rectangle layout problem. Journal of the Operational Research Society, 1996, Vol. 47, P. 523-537.

91. Hinxman, A. The Trim-Loss and assortment problems: a survey / A. Hinxman // European Journal of Operational Research. 1980. - N 11. - P. 863-888.

92. Holland, J.H. «Adaptation in Natural and Artificial Systems», University of Michigan, Ann Arbor, 1975.

93. Hopper E., Turton B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem // European Journal of Operation Research. 2001. N. 128. P. 34-57.

94. Hopper E., Turton B. An empirical study of meta-heuristics applied to 2D rectangular bin packing // Special Issue on Cutting, Packing and Knapsacking Problems, Studia Informatica. 2002. Vol. 2, N. 1.

95. Johnson D.S., Demes A., Ullman J.D., Garey M.R., Graham R.L. Worst-case performance bounds for simple one-dimensional packing algorithms // SIAM J. Comput. Vol.3. No.4. 1974. P. 299-325.

96. Kureichik V.M. et all. Some New Features in Genetic Solution of the Traveling Salesman Problem // Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control.- Plymouth, UK, 1996, P. 294-296.

97. Land, A.H., Doig, A.G. An automatic method of solving discrete programming problems // Econometrica. 1960. V.28. P. 497-520.

98. Lins, L., Lins, S., Morabito, R., 2002. An N-tet graph approach for nonguillotine packings of N-dimensional boxes into an N-container. European Journal of Operational Research, 2002, Vol. 141, P. 421-439.

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

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

101. Lui D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal pacing of rectangles // European Journal of Operation Research. 1999.No.112. P. 413-420.

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

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

104. Martello S., Toth P. Lower bounds and Reduction producers for the Bin Packing Problem // Discrete Applied Mathematics, 1990.

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

106. Martello, S., Toth, P. Knapsack Problems Algorithms and Computer Implementations. John Wiley & Sons, Chichester, 1990.

107. Martello, S., Vigo, D. Exact solution of the two-dimensional finite bin packing problem. Management Science, 1998, Vol. 44, P. 388-399.

108. Mesyagytov M.A., Smagin M.A., Filippova A.S. Substitution decoder based on local search algorithm for packing on sheets // CSIT. 2005. Vol. 2. P. 164-166.

109. Miyazawa, F.K., Wakabayashi, Y. An algorithm for the three-dimensional packing problem with asymptotic performance analysis. Algorithmica, 1997, Vol. 18, pp. 122-144.

110. Morabito, R., Morales, S. A simple and effective recursive procedure for the manufacturer's pallet loading problem. Journal of the Operational research Society, 1998, Vol. 49, P. 819-828.

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

112. Ratcliff, M.S.W., Bischoff, E.E. Allowing for weight considerations in container loading. OR Spektrum, 1998, Vol. 20, pp. 65-71.

113. Rutenbar, R.A. «Simulated Annealing Algorithms: An Overview», IEEE Circuits and Devices Mag., pp. 16-26, January 1989.

114. Scheithauer, G. A three-dimensional bin' packing algorithm. Journal of Information Processing and Cybernetics, 1991, Vol. 27, P. 263-271.

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

116. Wang P., Wascher G., edit. Special issue: Cutting and Packing Problems // European Journal of Operational Research. 2002. N. 141.

117. Wong, D.F., Leong, H.W., and Liu, C.L. Simulated Annealing for VLSI Design, Kluwer Academic Publishers, Boston, 1989.

118. Yanasse H., edit. Special issue: Cutting and Packing Prolems // Pesquisa Operacional. 1999. N. 19(2).