Модели и методы решения задач прямоугольного раскроя и упаковки на базе метаэвристики "Поиск с запретами" тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Ермаченко, Александр Иванович

• Ермаченко, Александр Иванович
• кандидат технических наук
• 2004

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

Введение.

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

1.1. Задачи раскроя и упаковки и их классификация.

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

1.3. Точные методы комбинаторной оптимизации.

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

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

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

1.5.2. Поиск с запретами.

1.5.3. Имитация отжига.

1.5.4. Муравьиная колония.

1.6. Использование декодеров.

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

1.8. Выводы.

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

2.1. Исходная информация задач двумерного прямоугольного раскроя.

2.2. Модель прямоугольной упаковки и условия допустимости.

2.3. Постановка задач прямоугольного раскроя и упаковки.

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

2.4.1. Рекурсивный декодер.

2.4.2. Декодер поиска пустых корзин.

2.4.3. Декодер «Нижний левый».

2.4.4. Блочный декодер.

2.5. Декодер последовательного конструирования для прямоугольной упаковки.

6. Выводы по второй главе.

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

3.1. Метаэвристическая методика поиска с запретами для решения задач дискретной оптимизации.

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

3.3. Реализация метода поиска с запретами в составе автоматизированной системы проектирования карт двумерного прямоугольного раскроя СЕТАМ1-СиТ.

3.4. Выводы по третьей главе.

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

4.1. Выбор числа шагов до смены вторичной оценки.

4.2. Эксперимент на случайно сгенерированных примерах.

4.2.1. Примеры с количеством предметов 40.

4.2.2. Примеры с количеством предметов 400.

4.3. Сравнение декодера последовательного конструирования и блочного декодера.

4.4. Эксперимент на безотходных примерах Евы Хоппер.

4.5. Выводы по четвертой главе.

Введение диссертации (часть автореферата) на тему «Модели и методы решения задач прямоугольного раскроя и упаковки на базе метаэвристики "Поиск с запретами"»

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

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

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

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

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

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

Цель работы

Разработать метод решения задач прямоугольного раскроя и упаковки на базе метаэвристики «Поиска с запретами».

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

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

2. Разработать процедуры декодеров и использовать их в составе метаэвристического алгоритма «Поиск с запретами»;

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

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

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

Методы исследования

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

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

Обобщенная математическая модель для задач двумерного прямоугольного раскроя-упаковки;

Декодер последовательного конструирования для задачи прямоугольной упаковки;

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

Программная реализация разработанных методов в составе системы двумерного прямоугольного раскроя СЕТАМ1-С11Т;

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

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

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

Разработан декодер последовательного конструирования для задачи прямоугольной упаковки. Новыми в алгоритме являются метод описания границы упаковки и процедура укладки прямоугольника. Разработанный декодер превосходит известный алгоритм «Нижний Левый». Найдены классы задач, на которых он превосходит также разработанный аспирантом кафедры A.B. Чиглинцевым «Блочный декодер». Показано, что разработанный алгоритм обладает свойством реставрации;

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

Практическая значимость работы:

1. Метод интегрирован в систему автоматизированного проектирования двумерного прямоугольного раскроя CETAMI-CUT. Имеются акты внедрения разработанных методов и программного обеспечения в учебный и производственный процесс. Программа CETAMI-CUT зарегестрирована в РОСПАТЕНТ, свидетельство № 2004611452;

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

Апробация работы

Работа выполнялась при поддержке грантов Российского Фонда Фундаментальных Исследований (РФФИ), проекты 99-01-000937 и 01-01000510; технического задания фирмы АСКОН-М (Москва).

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

1. Двенадцатая Байкальская международная конференция «Методы оптимизации и их приложения» (Иркутск, 2001);

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

3. Всероссийская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002);

4. Международная научно-техническая конференция «Информационные системы и технологии» ИСТ-2003 (Новосибирск, 2003);

5. Семинары группы изучения метаэвристических алгоритмов института математики СО РАН (Новосибирск, 2003);

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

Публикации. По теме диссертации опубликовано 11 работ: 7 статей, в том числе две в центральном журнале, 3 трудов конференций, выполненных по теме диссертации при непосредственном участии автора, и один акт о регистрации программы. в

Структура и объем работы

Диссертация состоит из введения, четырех глав, выводов, списка литературы, и приложений, содержащих акты внедрения результатов работы. Работа изложена на 95 страницах машинописного текста, кроме того, содержит 15 рисунков и 8 таблиц. Библиографический список включает 98 наименований и занимает 10 страниц.

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

Основные результаты диссертационной работы заключаются в следующем:

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

2. Разработан декодер последовательного конструирования упаковки, значительно превосходящий традиционно использовавшийся «Нижний левый». Полученные с использованием декодера результаты сравнимы с результатами блочного декодера Чиглинцева A.B.;

3. Разработана модифицированная схема поиска с запретами с использованием нескольких типов окрестностей текущего решения и вторичных оценочных функций. Метод не зависит от декодера, и может быть использован для решения задач прямоугольной упаковки и гильотинного раскроя листов и полу бесконечной полосы. Использование вторичных оценочных функций позволило улучшить КРА в среднем на 1 -3%, а в некоторых случаях до 6-8%;

4. Разработанные алгоритмы реализованы в соответствие с принципами объектно-ориентированного программирования, и интегрированы в систему прямоугольного раскроя и упаковки CETAMI-CUT. На основе вычислительного эксперимента проведен анализ зависимости получаемых результатов от различных параметров алгоритма. Алгоритм поиска с запретами в составе системы CETAMI-CUT был внедрен в различных отраслях производства и подтвердил свою эффективность. Полученные им результаты при количестве заготовок до 300-500 в среднем на 2-10% лучше, чем у других реализованных в системе методов;

5. Проведен объемный вычислительный эксперимент на более чем 50 классах задач, в том числе на случайно сгенерированных примерах различных классов и на безотходных примерах Евы Хоппер. Полученные результаты близки к оптимальным на примерах с известным оптимальным планом и превосходят результаты других исследователей на широком наборе классов задач прямоугольной упаковки и гильотинного раскроя.

Заключение

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

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

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

Список литературы диссертационного исследования кандидат технических наук Ермаченко, Александр Иванович, 2004 год

1. Аккуратов Г.В., Березнев В.А., Брежнева O.A. О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Уфа: УАИ. 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. Гончаров E.H., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследование операций. 1999. Серия 2. 6. №1. С. 12-32.

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

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

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

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

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

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

17. Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет, анализ и исслед. операций. Сер. 2. 2003, Т. 10, № 1. С. 11-43.

18. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения.

19. Сборник лекций молодежных и научных школ по дискретной математике и ее приложениям. М.: Издательство центра прикладных исследований при механико-математическом факультете МГУ. 2000. С. 87-117.

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

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

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

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

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

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

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

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

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

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

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

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

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

33. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование // Новосибирск. Наука СО. 1987. 272 с.

34. Норенков И.П., Косачевский О.Т. генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации // Информационные технологии. 1999. №2. С. 2-8.

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

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

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

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

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

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

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

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

43. Baker B.S., Goffman Jr. E.G., Riverst R.L. Orthogonal packing in two dimensions // SI AM J. Comput. 9 (1980) 846-855.

44. Baum S., Trotter Jr.L. Integer rounding for polymatroid and branching optimization problems. // SIAM J. Alg. Disc. Meth. 1981. 2(4). P. 416-425.

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

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

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

48. Burke E., Kendall G. Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem // Accepted for the 1999 International Conference on Artificial Intelligence, Monte Carlo resort. Las Vegas. Nevada. USA. 1999.

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

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

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

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

53. Dorigo M., Gambardella L.M. Ant Colonies for the traveling salesman problem // IRIDIA, Technical Report 1996. 3.

54. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation. 1997. Vol.1. No.l.

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

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

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

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

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

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

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

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

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

64. Gilmore P.C. and Gomory R.E. A Linear Programming Approach to the Cutting-stock Problem, Operations Research 9(1961), pp. 849-859.

65. Glover F. Tabu search and adaptive memory programming advances, applications and challenges // Interfaces in Computer Science and Operations Research. 1996. P. 1-75.

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

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

68. Keller H., Kotov V. An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing // Operations Research Ketters. V. 31. N1. 2003.

69. Kochetov Yu., Usmanova A. Probabilistic Tabu Search with Exponential Neighborhood for Bin Packing Problem // Proceedings MIC'2001, Porto, 2001. P. 619-624.

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

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

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

73. Loris Faina. An application of simulated annealing to the cutting stock problem // European Journal of Operational Research. 1999. 114. P. 532-556.

74. Marcotte O. The cutting stock problem and integer rounding // Math. Program. 1985. 33(1). P. 82-92.

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

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

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

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

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

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

81. 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. Pp.829-832.

82. Scheithauer G. and Terno J., Theoretical Investigations on the Modified Integer Roundup Property for the One-dimensional Cutting Stock Problem, Operations Research Letters, 20, (1997) pp. 93-100.

83. 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. P. 1390-1401.

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

85. Schwerin P., Wascher G. The Bin-Packing Problem: a Problem Generator and Some Numerical Experiments with FFD Packing and MTP // International Transactions in Operational Research. 1997. 4. P.337-389.

86. Sergeyeva O.Y., Scheithauer G. and Terno J. The value correction method for packing of irregular shapes // Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa 1997. P. 261-270.

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

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

89. Tarnowski T., Terno J., Scheithauer G. A polynomial time algorithm for the guillotine pallet loading problem. INFOR 32. 1994. P. 275-287.

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

91. 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. 110114.

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

93. Wang P., Valenzeva L. Data set generation for rectangular placement problems // European Journal of Operational Research. 2001. 134(2). P.378-391.

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

95. E. Burke, G. Kendall. Comparison of Meta-Heuristic Algorithms for Clustering Rectangles. //Computers & Industrial Engineering 37 (1999), 383386

96. A. Lodi, S. Martello, D. Vigo. Approximation algorithms for the oriented two-dimensional bin packing problem. // EJOR 112 (1999), 158-166