Проектирование гильотинного раскроя листового и рулонного материала с использованием послойных алгоритмов тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Сиразетдинов, Тимур Маратович

• Сиразетдинов, Тимур Маратович
• кандидат технических наук
• 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. Выводы.

2. Эвристические методы решения задачи гильотинного раскроя.

2.1. Уровневые алгоритмы.

2.2. Послойная технология расчета гильотинного раскроя.

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

2.3.1. Рекурсивный метод.

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

2.4. Выводы.

3. Автоматизированная система двумерного прямоугольного раскроя CETAMI-CUT.

3.1. Современное состояние раскройно-заготовительного производства.

3.2. Структура САПР раскроя-упаковки.

3.3. Применение разработанного программного обеспечения в САПР раскроя-упаковки.Error! Bookmark not defined.

3.4. Программа-оболочка CETAMI-CUT, ее взаимодействие с расчетными модулями.

3.5. Детерминированные эвристические алгоритмы решения задачи гильотинного раскроя, реализованные в системе CETAMI-CUT.

3.5.1. Рекурсивный алгоритм в рамках системы CETAMI-CUT.

3.5.2. Алгоритм поиска пустых корзин в рамках системы CETAMI-CUT.

3.6. Автоматизированный выбор метода расчета раскроя.

3.7. Выводы.

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

4.1. Независимое использование рекурсивного метода и метода поиска пустых корзин.

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

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

4.1.3. Сравнение разработанных эвристик с послойным алгоритмом и между собой.

4.2. Использование рекурсивного метода в составе метаэвристик.

4.3. Использование метода поиска пустых корзин в составе метаэвристик

4.4. Использование процедуры автоматизированного выбора метода решения задачи.

4.5. Выводы.

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

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

Актуальность темы исследования. Определяющими факторами успеха в промышленном производстве являются: уменьшение времени выхода продукции на рынок, снижение стоимости и повышение качества. Темпы морального старения промышленных изделий таковы, что поставленные на конвейер новые образцы часто уже не соответствуют современным требованиям. Только значительное сокращение цикла проектирования и подготовки производства, подразумевающее внедрение систем автоматизации проектирования (САПР), может способствовать созданию конкурентоспособной продукции и своевременному выходу ее на рынок.

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

3. Особенности реализации разработанных методов, связанные с технологическими ограничениями производства;

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

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

Научная новизна работы

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

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

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

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

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

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

2. Разработанное математическое обеспечение двумерного прямоугольного раскроя в составе автоматизированного рабочего места технолога раскройно-заготовительного производства позволяет повысить коэффициент использования материала на 7-18% и значительно сократить время проектирования по сравнению с традиционным проектированием;

3. Разработанное программное обеспечение позволяет быстро строить карты раскроя с высоким коэффициентом использования материала;

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

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

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

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

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

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

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

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

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

Результаты диссертационной работы непосредственно отражены в 14 публикациях, в том числе в монографии (2 п.л.), 9 статьях, 5 трудах конференций (3 докладов и 2 тезисов), выполненным по теме диссертации при непосредственном участии и руководстве автора.

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

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

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Сиразетдинов, Тимур Маратович

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

1. Изучена послойная технология формирования карт двумерного прямоугольного гильотинного раскроя. Рассмотрены простые реализации идеи укладки деталей группами. Выявлены недостатки известных послойных алгоритмов: уровневых с использованием простых эвристик и более сложных алгоритмов М. Адамовича, Э.А. Мухачевой и Л.Ф. Розановой.

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

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

4. Исследована эффективность предложенных методов на базе численного эксперимента с использованием системы двумерного прямоугольного раскроя CETAMI-CUT. При раскрое полосы с разрешенными поворотами деталей рекурсивный метод получает лучшие результаты при большом количестве (свыше 50) типоразмеров деталей и при их удлиненной форме. В остальных случаях метод поиска пустых корзин показал лучшие результаты, особенно при больших размерах деталей и большом количестве однотипных деталей. При раскрое листов лучшие результаты обеспечивает рекурсивный метод независимо ни от размеров, ни от количества деталей.

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19. Коробцева Н.А. САПР одежды: исторический экскурс и обзор существующих систем // Текстильная промышленность. 2003. №5. С.61-62. №6. С. 63-65.

20. Кочетов Ю., Усманова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // Иркутск: XII Байкальская международная конференция. 2001. С.22-27. Работа поддержана РФФИ: проект 01-01-00510.

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

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

23. Мартынов В.В. Информационная система раскроя плоских геометрических объектов сложной формы: основные проблемы и подходы к их решению // Вестник УГАТУ. -Уфа, Изд.УГАТУ, 2001. С. 105-113.

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

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

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

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

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

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

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

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

32. Мухачева Э.А., Мухачева А.С. Метод перестройки для решения задачи прямоугольной упаковки // Информационные технологии. 2000 №4. С. 30-36. Работа поддержана РФФИ, проект 99-01-00947.

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

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

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

36. Петунин А.А. Интегрированная САПР "Сириус" для автоматизации раскройно-заготовительного производства // С.Петербург: ОПТИМ-2001. С.123-126.

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

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

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

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

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

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

43. Шпур Г., Краузе Ф.-Л. Автоматизированное проектирование в машиностроении. -М.Машиностроение, 1988.-648с.

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

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

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

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

48. Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem // Annals of OR. 1993. 41(4). P.313-325.

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

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

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

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

53. Dykhoff H., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1990. 44(2).

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. 167-182.

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

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

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

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

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

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

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

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

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

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

65. Kochetov Yu., Usmanova A. Probabilistic Tabu Search with Exponential Neighborhood for Bin Packing Problem // Proceedings MIC'2001, Porto, 2001. P. 619-624. Работа поддержана РФФИ: проект 01-01-00510.

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

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

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

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

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

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

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

73. Martynov V. Geometrical objects regular placement onto a stock sheet or strip // Pesquisa Operacional, Vol. 19, No.2. SP - BRAZIL, Instituto Nacional de Pesquisas Espaciais, dezembro de 1999. P.211-222.

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

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

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

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

78. Murata H., Fujiyoshi K., Nakatane S. and Kajitani Y. Rectangle-Packing-Based Module Placement // Proc. IEEE/ACM International Conf. on Computer-Aided Design. 1995. P.472-479.

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

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

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

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

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

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

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

86. Verhoturov M.A., Sergeyeva O.Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // Pesquisa Operacional. 2000. Y. 20. N2. P. 233-247. Работа поддержана РФФИ, проект 99-01-00947.

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

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

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