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

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

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

ИСПОЛЬЗОВАННЫЕ ОБОЗНАЧЕНИЯ.

ВВЕДЕНИЕ.

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

1.1. Задачи одно и двумерного раскроя-упаковки.

1.1.1. Простейшая одномерная задача раскроя и упаковки.

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

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

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

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

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

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

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

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

1.3. Основные задачи исследования.

1.4. Выводы.

2. МОДЕЛИРОВАНИЕ ПРЯМОУГОЛЬНЫХ УПАКОВОК.

2.1. Математические модели задач упаковки в полосу и на листы.

2.2. Блочная модель упаковки.

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

2.4. Алгоритмы декодеры. Блочный декодер.

2.5. Свойство декодеров «реставрация».

2.6. Выводы. 3. ГЕНЕТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ УПАКОВКИ.

3.1. Общая характеристика генетических методов.

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

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

3.4. Выводы.

4. ЗАДАЧА ГИЛЬОТИННОГО РАСКРОЯ.

4.1. Математическая модель задачи раскроя полосы.

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

4.3. Метод дискриминации простых эвристик.

4.4. Выводы.

5. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ.

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

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

5.3. Исследование декодеров. Проверка на наличие свойства «реставрации».

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

5.5. Исследование эффективности генетического гильотинного алгоритма с применением дискриминации эвристик.

5.6. Выводы.

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

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

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

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

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

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

1. Анализ вероятностных методов локального поиска оптимального решения для задач раскроя и упаковки;

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

3. Разработка и исследование эффективности генетического блочного алгоритма;

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

5. Разработка алгоритмов-декодеров, формирующих упаковку на основе заданного кода;

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

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

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

1. Блочный способ кодирования упаковки;

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

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

4. Алгоритм конструирования упаковки - «блочный декодер»;

5. Генетический алгоритм гильотинного раскроя на базе мультиметодной технологии дискретной оптимизации И.П. Норенкова с дискриминацией эвристик;

6. Компьютерная программа, реализующая разработанные алгоритмы;

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

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

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

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

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

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

Практическая значимость работы: программная реализация генетического блочного алгоритма показала значительные преимущества перед известными классическими способами применения эвристических методов к задачам упаковки на достаточно широком классе задач. Это позволяет использовать разработанные алгоритмы при практических расчетах. Программное обеспечение зарегистрировано в РОСПАТЕНТ свидетельство №2002610945; результаты работы внедрены в ОАО АСКОН, г. Москва и учебный процесс У Г АТУ.

Апробация работы. Работа выполнялась в рамках заданий РФФИ, проекты 99-01-00937, 01-01-00510. За цикл работ «Новые генетические алгоритмы решения задач двумерного раскроя и упаковки» присуждена Медаль РАН. За лучшую научную студенческую работу автор награжден медалью Министерства Образования РФ. Во время учебы в аспирантуре был удостоен стипендии Президента РФ и стипендии Правительства РФ. Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:

1. Международная молодежная научно-техническая конференция «Интеллектуальные системы управления и обработки информации» (Уфа, 1999г.);

2. Республиканская научно-техническая конференция «Интеллектуальное управление в сложных системах» (Уфа, 1999г.);

3. Международная научная конференция «Моделирование, вычисления, проектирование в условиях неопределенности» (Уфа, 2000г.);

4. Международная конференция «Дискретный анализ и исследование операций» (Новосибирск, 2000г.);

5. Международная конференция INFORMS (USA, San Antonio, 2000г.);

6. Всероссийская научно-практическая конференция "Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования" ОПТИМ-2001 (Санкт-Петербург, 2001г.);

7. Международная конференция IFORS 2002 (UK, Edinburgh, 2002г.);

8. Международные конференции CSIT'2001, CSIT'2003 (Уфа, 2001г., 2003г.);

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

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

По теме диссертации опубликовано 16 работ, в том числе в центральной печати 7 статей.

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

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

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

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

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

Четвертая глава посвящена исследованию мультиметодной технологии дискретной оптимизации И.П. Норенкова на примере рулонного гильотинного раскроя.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Чиглинцев, Артем Владимирович

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

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

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

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

4. Разработан новый алгоритм «блочный декодер», доказано наличие свойства «реставрации»;

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

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

Заключение

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

Развитие генетических алгоритмов для решения задач 1.5DBP и 2DBP проведено на базе блочной модели упаковки, а задачи гильотинного раскроя 1.5DCSP на базе технологии И.П. Норенкова с использованием простых эвристик. В первом направлении разработан генетический блочный алгоритм GBA с блочном декодером IBD, он показал лучшие результаты при сравнительном эксперименте. Совершенствование генетического алгоритма для задачи упаковки реализовалось за счет новой идентификации элементов генетического метода: генов, аллелей, хромосом и процедур над ними. Во втором направлении совершенствование известной методики достигнуто за счет применения дискриминации простых эвристик.

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

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

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

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

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

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

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

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

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

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

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

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

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

13. Канторович Л.В., Заллгаллер В.А. Расчет рационального раскроя материалов// Лениздат. 1951.

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

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

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

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

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

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

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

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

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

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

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

25. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. -М . -.Машиностроение. 1984. С. 176.

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

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

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

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

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

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

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

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

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

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

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

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

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

39. Aurts Е., Lenstra J., edit. Local Search in Combinatorial Optimization // John Wiley&Sons. 1996.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

54. 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. 167182.

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

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

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

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

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

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

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

62. Jhonson 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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