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

• Ширгазин, Рамиль Ришатович
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Ширгазин, Рамиль Ришатович

Введение.

1. Модели и методы решения задач упаковки.S

1.1. Задача одномерного раскроя.

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

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

1.4. Задача гильотинного раскроя.

1.5. Обзор методов решения задач одно и двухмерного раскроя-упаковки

1.5.1. Использование методов математического программирования.

1.5.2. Применение методов комбинаторной оптимизации.

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

1.5.4. Вероятностные методы локального поиска оптимума.

1.6. Выводы.

2. Способы кодирования упаковок.

2.1. Прямой способ кодирования.

2.2. Кодирование приоритетным списком.

2.3. Схема парных последовательностей.

2.4. Блочная технология кодирования-декодирования упаковок.

2.4.1. Блок структуры упаковок и их свойства.

2.4.2. Преимущества блочной технологии кодирования упаковок.

2.4.3. Алгоритмы построения упаковки - декодеры. Декодер замещения Sub (NF), следующий подходящий.

2.4.4. Декодер замещения Sub (FF), первый подходящий.

2.4.5. Декодер жадного замещения Greedy Sub.

2.4.6. Декодер «пара списков» Dual Local Search (DLS).

2.5. Выводы.

3. Эволюционные методы решения задач упаковки.5S

3.1. Наивный эволюционный метод {Naive Search, NS).

3.2. Эволюционный алгоритм (1+1).

3.3. Метод последовательного уточнения оценок (Sequentative Value Correction, SVC).

3.4. Генетические методы решения задачи упаковки. Общая характеристика генетических методов.

3.5. Схема «жадного» генетического алгоритма.

3.6. Гибридный генетический алгоритм на базе SVC и Greedy Sub.

3.7. Модификация методов для решения задачи упаковки на прямоугольные листы.

3.8. Оценка эффективности алгоритмов. Нижние границы.

3.8. Выводы.

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

4.1. Программная реализация алгоритмов.

4.2. Решение задач размещения на полосу на примерах Bortfeld.

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

4.4. Исследование эффективности генетического гибридного алгоритма Genetic Greedy Sub. Сравнительный эксперимент с метаэвристическими алгоритмами.

4.5. Решение задач размещения на листы на примерах S.P Fekete и J. Schepers

4.6. Выводы.

Введение диссертации (часть автореферата) на тему «Эволюционные методы и программное обеспечение для решения задач ортогональной упаковки на базе блочных структур»

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

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

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

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

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

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

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

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

4. Разработать наивный эволюционный алгоритм на базе простых эвристик и «наивного оператора мутации»

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

6. Создать программное обеспечение реализующее модифицированные и новые разработанные методы.

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

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

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

2. Декодер жадного замещения Greedy Sub на базе блочной структуры и его модификации.

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

4. Гибридизация генетического алгоритма с блочным декодером жадного замещения.

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

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

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

1. «Блочный декодер жадного замещения» - создан новый эффективный метод конструирования двухмерной упаковки, который реализует жадную стратегию одновременно в разных направлениях, оперируя несколькими приоритетными списками прямоугольников; декодер может применяться в различных метаэвристиках.

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

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

4. Программное обеспечение реализующее новые методы расчета упаковок - ориентированное на численные эксперименты и промышленные расчеты.

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

Связь исследования научными проектами: Работа выполнялась при частичной поддержке РФФИ, проект 01-01-00510.

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

Международная конференция «Ресурсосберегающие технологии». Санкт-Петербург 2001.

Байкальская международная школа-семинар «Математическое программирование», Иркутск, 2002.

Международная конференция «Математическое программирование и приложения», Екатеринбург 2003.

Международная конференция ESICUP (Европейская специальная группа по раскрою и упаковке) (Germany, 2004г.);

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

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

Конференция региональной зимней школы-семинара аспирантов и молодых ученых. «Интеллектуальные системы обработки информации и управления», Уфа, 2006г.

В 2004-2005 учебном году прошел, по линии ДААД, научную стажировку в институте вычислительной математики Дрезденского технического университета. Результаты работа внедрены в учебный процесс УГАТУ и в Центр Обработки Информации ОАО «Башнефтегеофизика» г.Уфа.

По теме диссертации опубликовано 9 работ: 5 статей (2 из них в изданиях рекомендованных ВАК), 3 материала конференций и одно авторское свидетельство. Правовая сторона программного обеспечения защищена в РОСПАТЕНТ «Свидетельством об официальной регистрации программ для ЭВМ» №2006612649.

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

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

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

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

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Ширгазин, Рамиль Ришатович

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

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

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

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

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

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

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

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

Заключение

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

• эффективность использования ресурсов

• продуктивность использования оборудования

• время проектирования и производительность труда

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

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

Список литературы диссертационного исследования кандидат технических наук Ширгазин, Рамиль Ришатович, 2006 год

1. Аккуратов Г.В., Березнев В.А., Брежнева О.А. О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Уфа: УАИ. 1990. С. 145-154.

2. Бабаев Ф.В. Оптимизация раскроя материалов: Обзор. М.: НИИМАШ, 1978,-С.72.

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

4. Бабкова Е.В. Задача оценки сложности раскроя в условиях автоматизированного управления производством // Принятие решений в условиях неопределенности: Межвуз. науч. сб. -Уфа: УГАТУ, 2000. -С.136-141.

5. Бабкова Е.В. Модель сменной загрузки раскройного оборудования // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2002.-С.184-190.

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

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

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

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

10. Верхотуров М.А. Задача нерегулярного раскроя плоских геометрических объектов: моделирование и расчет рационального раскроя // Информационные технологии. 2000. №5. С. 37-42.

11. Гамберг В.Я., Липовецкий А.И., Петунин А.А. Автоматизация проектирования раскройных карт в условиях индивидуального производства // Кузнечно-штамповочное производство, 1982.-N3 С.26-27.

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

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

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

15. Грицюк Ю. Регулярне размщувания прямокутних объетв вздовж смуп' односиоронньо обмежено1 стр1чки // Льв1в. УкрДЛТУ. 2002. С. 220.

16. Гончаров Е.Н., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения .// Дискретный анализ и исследование операций. 1999. Серия 2. 6. №1. С. 12-32. Работа поддержана РФФИ: проекты 99-01-00601, 98-07-90259.

17. Горанский Г.К., Бендерева Э.И. Технологическое проектирование в комплексных автоматизированных системах подготовки производства. -М.Машиностроение, 1981. С. 455

18. Долгопольский Б.С., Бритарев К.Ф. Арцишевский IO.IO. Система автоматизированного проектирования на ЭВМ процессов холодной листовой штамповки. -М.: Кузнечно-штамповочное производство. 1979. №6. С. 13-14.

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

20. Жукова Т.Ю. Применение метода "Моделирование отжига" для решения задачи раскроя // Уфа: Принятие решений в условиях неопределенности. 2003. С. 230-235. Работа поддержана РФФИ, проект 01-01-00510.

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

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

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

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

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

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

27. Макеев Б.А., Батозский В.И. и др. Автоматизация раскроя тонколистового проката. -М.: Кузнечно-штамповочное производство. 1978. №6. С. 30-33.

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

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

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

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

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

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

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

35. Мухачева Э.А. Рациональный раскрой прямоугольных листов на прямоугольные заготовки // Оптимальное планирование: Сб. научных трудов СО АН СССР. 1966. Вып. 6. С. 43-115.

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

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

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

39. Мухачева Э.А., Мухачева А.С. Метод перестройки для решения задачи прямоугольной упаковки // Информационные технологии. 2000 №4. С. 3036.

40. Мухачева Э.А., Мухачева А.С., Белов Г.Н. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя Информационные технологии. 2000 №2. С. 11-17.

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

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

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

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

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

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

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

48. Фроловский В. Моделирование и оценка качества проектных решений в системах сквозного проектирования корпусных изделий из листового материала // Информационные технологии. 2000. №5. С. 18-25.

49. Фроловский В.Д. Целочисленная аппроксимация и оптимальное группирование геометрических объектов в задачах размещения // Научный вестник НГТУ. № 1(8). 2000. С. 37-46.

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

51. Aurts Е., Lenstra J., edit. Local Search in Combinatorial Optimization // John Wiley&Sons. 1996. P. 8-13

52. Adamovicn A., Albano A. Nesting two-dimensional shapes in rectangular Modules // Comput. Aeded Design. 1976. 8(1). P.27-33.

53. Baesley J.E. http://mscmga.ms.ic.ac.-uk/info.html.

54. Beasley. J.E. A population heuristic for constrained two-dimensional non-guillotine cutting. EJOR, 156, 2004, P.601-627.

55. Baker B.S., Coffman E.G. and Rivest R.L., Orthogonal packing in two dimentions. SIAM Journal of Computing 9. 1980. P. 846-855.

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

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

58. Bischoff E., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1995. P. 84.

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

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

61. Chung F.K.R., Garey M.R., Johnson D.S. On packing two-dimensional bins // SIAM J. Algebraic Discrete Meth. 3 (1982) P. 66-76.

62. Coffman E., Garey M., Jchonson D. Approximation algorithms for bin-packing-an updated survey // Algorithm Design for Computer System Design (Ausiello G., Lucertini M., Serafini P.eds) Berlin etal. 1984.

63. Coffman E.G. Jr., Garey M.R., Johnson D.S., Tarjan R.E. Performance bounds for level-oriented two-dimensional packing algorithms // SIAM J. Comput. 9 (1980) P. 801-826.

64. Dyckhoff H., Scheithauer G., Terno J. Cutting and Packing // Annotated Bibliographies in Combinatorial Optimization, edited by M.Dell'Amico, F.Maffioli and S.Martello. John Wiley&Sons. 1997. P.393-412.

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

66. Dykhoff H., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1990.

67. Faroe O., Pisinger D., Zachariasen M. Guided local search for the three-dimensional bin packing problem // Tech. Rep. 99/13, DIKU, University of Copenhagen, Denmark. Dept. of Computer Science, University of Copenhagen.

68. Folkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing // Journal of Heuristics. 1998.2(1). P. 5-30.

69. Folkenauer E. Tapping the full power of genetic algorithm through suitable representation and local optimization: Application to bin packing // Evolutionary Algorithms in Management Applications. Berlin. 1995. P. 167-182.

70. Garey M.R., Johnson D.S. Computers and Intractability: A guide to the Theory of NP-Completeness // San-Francisco, Freemau. 1979.

71. Gehring H., Bortfeld A. A Genetic Algorithm for Solving the Container Loading Problem // International transactions in operational research. 1997, V.4, №5/6. P.401-418.

72. Gilmore P., Gomory R. Multistage cutting stock problem of two and more dimensions//Operat.Res. 1965. 13(1). P.94-120.

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

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

75. Hopper E., Turton B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. // EJOR 128. 2001. P. 34-57.

76. Imahori S., Yaguira M., Ibaraki T. Local Search Heuristics for the Rectangle Packing Problem With General Spatial Costs // MIC'2001 4th Metaheuristics International conference. P. 471-476.

77. Johnson D.S., Demers A., Ullman J.D., Garey M.R., Graham R.L. Worst-case performance bounds for simple one-dimensional packing algorithms // SIAM J. Comput. V. 3. N4. 1974. P.299-325.

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

79. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. // European Journal of Operation Research. 1999. 112. P. 413-420.

80. Lodi A., Martello S., Vigo D. Heuristic algorithms for the three-dimensional bin packing problem // European Journal of Operational Research. 2002. 141. P. 410420.

81. Lodi A., Martello S., Vigo D. Recent advances on two-dimensional bin packing problems. // Discrete Applied Mathematics 123. 2002. P. 379 -396.

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

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

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

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

86. Morabito M. Arenales M. Staged and constrained two-dimensional guillotine cutting problems: an and/or-graph approach. // European Journal of Operational Research. 1996. 94. P.548-560.

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

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

89. Mukhacheva E.A., Zalgaller V.A. Linear Programming Cutting Problems // International Journal of Software Engineering and Knowledge Engineering. 1993. V.3.N4. P. 463-476.

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

91. Sakanushi K., Kajitani Y. The Quarter-State (Q-sequence) to Represent the Floorplan and Applications to Layout optimization // IEEE Asia Pacific Conference on Circuits and systems. 2000. P. 829-832.

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

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

94. Scheithauer G., Terno Y. Muller A., Belov G. Solveng one-dimensional cutting stock problems exactly with a cutting plane algorithm. // Journal of the Operational Research Society. 2001. 52. H. 1390-1401.

95. Stutzle Т., Hoos H.H. MAX-MIN Ant System // Preprint submitted to Elsiever Science, 1999.

96. Takahashi T. A New Encoding Scheme for Rectangle Packing Problem // Graduate School of Science and Technology. Niigata University. IEEE. 2000. P. 175-178.

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

98. Valeyeva A.F., Agliullin M.N. Ant Colony Algorithm for the 2-D Bin-Packing Problem: Numerical Study // Proceedings of the 5th International Workshop on Computer Science and Information Technologies, 2003. P. 110-114.

99. Verhoturov M.A., Sergeyeva O.Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // Pesquisa Operacional. 2000. V. 20. N2. P. 233-247.

100. Wang P., Wascher G., edit, {it Special issue: Cutting Packing Problems} Europen Journal of Operational research. 141 (2002).

101. Wascher G, Forster H.(1997) Simulated annealing for order spread minimization sequencing cutting patterns // European Journal of Operational Research. 1998. 110. P. 272-281.

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

103. Baesley J.E. OR-Library http://www.brunel.ac.uk/depts/ma/research/ieb/info.htinl.

104. Hopper E., Turton B.C.H. Test Problem Sets from Hopper/Turton http://www.apdio.pt/sicup/nonpub/research-support/hopper.html.

105. Bortfeld A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces // University of Hagen