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

• Сиразетдинова, Татьяна Юрьевна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Сиразетдинова, Татьяна Юрьевна

Оглавление.

Введение.

1. Обзор моделей и методов решения задач раскроя.

1.1. Автоматизация проектирования и технологической подготовки производства.

1.2. Классификация задач раскроя.

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

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

1.3. Математическая модель задачи двумерного раскроя.

1.4. Обзор методов решения задачи раскроя.

1.4.1. Точные методы решения задач раскроя.

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

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

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

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

1.5. Выводы.

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

2.1. Метод имитации отжига.

2.2. Метод «холодного» отжига.

2.3. Декодер «вставки».

2.4. Применение метода (1+1)-ЕА к задаче прямоугольного раскроя.

2.5. Метод «поиск с запретами» с декодером «вставки».

2.6. Работа декодера «вставки» с учетом обхода дефектных областей материала.

2.7. Выводы.

3. Автоматизированная система двумерного прямоугольного раскроя 2БК-СиТ.

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

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

3.3. Программа-оболочка 2БК-СиТ, ее взаимодействие с расчетными модулями.

3.4. Интеграция системы 2БК-С1Л в стороннюю систему автоматизированного проектирования.

3.5. Алгоритмы, реализованные в системе 2БК-СиТ.

3.6. Выводы.

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

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

4.2. Выводы.

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

1. Декодер «вставки», разработанный для реализации технологических ограничений и обхода дефектных областей раскраиваемого материала.

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

3. Программная реализация разработанных методов в составе системы прямоугольного раскроя 2БК-СиТ.

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

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

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

2. Предложен метод «холодного» отжига, основанный на принципах метаэвристики «имитация отжига», который в отличие от последней:

- работает с постоянным параметром температуры;

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

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

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

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

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

Разработанное программное обеспечение, реализующее методы и алгоритмы расчета прямоугольного раскроя листового и рулонного материала с учетом технологических ограничений, в качестве подсистемы для решения задач прямоугольного раскроя интегрировано в известную систему автоматизированного проектирования «Сириус», внедренную на следующих предприятиях: ООО «Центр автоматизации проектирования и высоких технологий» (г. Екатеринбург), ЗАО «Курганстальмост» (г. Курган), ОАО «Мечел» (г. Челябинск). Применение разработанного программного обеспечения позволило повысить эффективность использования материала на 5-8%.

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

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

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

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

1. Международной уфимской зимней школе-конференции по математике (Уфа, 2005);

2. III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2006);

3. Зимней школе для аспирантов и молодых ученых (Уфа, 2006, 2007);

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

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

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

Диссертация состоит из введения, четырех глав, выводов, списка литературы, и приложений. Работа изложена на 130 страницах машинописного текста, кроме того, содержит 37 рисунков. Библиографический список включает 123 наименования и занимает 13 страниц.

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

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

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

Реализован алгоритм (1+1)-ЕА как частный случай алгоритма «имитация отжига» с нулевой температурой.

2. Разработан новый метод проектирования прямоугольного раскроя -декодер РЦР, учитывающий дефекты раскройного материала. Этот декодер используется в составе метаэвристик (1+1)-ЕА, «холодного» отжига и «поиска с запретами». Они включены в автоматизированную систему расчета прямоугольного раскроя 20Я-Си1. Использование нового декодера позволяет повысить качество решения по сравнению с известными декодерами на 3-5%.

3. Разработаны методы и алгоритмы, позволяющие учитывать ряд технологических ограничений: припуски на резы, окантовку рулона или листов, дефекты раскраиваемого материала, реализованные в виде программного обеспечения. Программное обеспечение в составе системы 20Я-СиТ автоматизированного рабочего места технолога раскройно-заготовительного производства позволяет повысить коэффициент использования материала в среднем на 5-8% по сравнению с простыми эвристиками и значительно сократить время проектирования.

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

5. Исследована эффективность предложенных методов на базе численного эксперимента с использованием системы двумерного прямоугольного раскроя 2Б11-СиТ. При раскрое полосы наблюдается заметное улучшение качества решения задачи раскроя на некоторых классах задач.

Заключение

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

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

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

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

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

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

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

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

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

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

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

7. Борисовский П.А. Исследование эволюционных алгоритмов решения некоторых задач дискретной оптимизации: диссертация кандидата физ.-мат. наук: 05.13.18. Омск, 2005.109 с.

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

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

10. Валеева А.Ф., Сиразетдинова Т.Ю. Задача прямоугольного гильотинного раскроя на базе метаэвристики «Имитация отжига» // Проблемы оптимизации и экономические приложения, III Всероссийская конф.: матер, конф. Омск, 2006. С. 55-62.

11. Валеева А.Ф., Сиразетдинова Т.Ю. Решение задачи прямоугольного гильотинного раскроя с применением процедур имитации отжига // Социально-экономические и технические системы. Электронный ресурс. Набережные Челны, №9 2006 (http://kampi.ru/sets). 7 с.

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

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

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

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

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

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

18. Ермаченко А.И., Сиразетдинов Т.М. Метод поиска с запретами для решения задач прямоугольного гильотинного раскроя // Дискретный анализ и исследование операций: сб. трудов всерос. конф. Новосибирск: НГТУ, 2002. С. 230.

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

20. Жукова (Сиразетдинова) Т.Ю. Применение метода «моделирования отжига» для решения задачи раскроя // Принятие решений в условиях неопределенности: сб. статей. Уфа: УГАТУ. 2003. С. 45-51.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35. Мухачева Э.А., Валеева А.Ф., Картак В.М., Мухачева A.C. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур// Информационные технологии. Приложение. 2004. №5.31 с.

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

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

38. Мухачева Э.А., Ермаченко А.И., Сиразетдинов Т.М., Жукова (Сиразетдинова) Т.Ю. Комплекс алгоритмов и программ расчета гильотинного раскроя // Информационные технологии. 2004. №8. С. 18-25.

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

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

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

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

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

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

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

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

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

48. Руднев А.С. Задачи двумерной прямоугольной упаковки в контейнеры с запрещенными областями // Магистерская диссертация, 2006. 120с.

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

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

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

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

53. Aurts Е., Lenstra J., edit. Local Search in Combinatorial Optimization/ // John Wiley&Sons. 1996. P. 10-15.

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

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

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

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

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

60. 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. P. 34-35.

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

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

63. 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. P. 89-94.

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

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

66. 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. 1.

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

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

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

70. 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. P. 251-259.

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

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

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

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

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

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

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

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

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

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

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

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

83. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing. Science. v220 (1983), pp 671-680.

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

85. Lirov Y., edit. Special issue: Geometric Resource Allocation // Mathematical and Computer Modelling. 1995.16(1).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

106. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische Losung. Leipzig. 1987.215p.

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

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

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

110. Yanasse H., edit. Special issue: Cutting and Packing Problems// Pesquisa Operacional. 1999.19(2).