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

• Чеканин, Владислав Александрович
• кандидат технических наук
• 2011

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

ОГЛАВЛЕНИЕ.

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

ВВЕДЕНИЕ.

ГЛАВА 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. Получены практические результаты анализа эффективности разработанных алгоритмов по временным и качественным критериям, что иллюстрирует актуальность и ценность диссертационного исследования в виде алгоритмических решений задачи ортогональной упаковки.

Список литературы диссертационного исследования кандидат технических наук Чеканин, Владислав Александрович, 2011 год

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