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

• Смагин, Михаил Анатольевич
• кандидат технических наук
• 2005

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

Оглавление.

Введение.

1. Анализ современных моделей и методов проектирования двумерного размещения.

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

1.2. Классификация задач размещения и место исследуемых задач в ней.

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

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

1.5. Обзор методов решения задачи двумерного размещения.

1.5.1. Точные методы, их достоинства и недостатки.

1.5.2. Простые эвристики.

1.5.3. Методы локального поиска оптимума. Общая схема и метаэвристики.

1.6. Автоматизированные системы проектирования размещения деталей.

1.7. Выводы.

2. Эвристические методы размещения деталей на заданных объектах.

2.1. Схемы кодирования.

2.1.1. Прямая схема кодирования.

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

2.1.3. Кодирование парой последовательностей.

2.1.4. Кодирование блок-структурой.

2.2. Однопроходные эвристики проектирования размещения.

2.2.1. Декодер "нижний левый".

2.2.2. Декодер "усовершенствованный нижний левый".

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

2.2.4. Двойственный декодер.

2.2.5. Метод размещения деталей в открытую область на базе двойственного алгоритма.

2.2.6. Декодер замещения.

2.2.7. Метод локальной перестройки.

2.2.8. Схема применения алгоритма замещения для размещения деталей на листы.

2.3. Выводы.

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

3.1. Генетический алгоритм с позиций локального поиска экстремума.

3.2. Процедуры скрещивания и мутации.

3.3. Модификации генетического алгоритма.

3.4. Схема ограничения поиска решений в генетическом алгоритме.

3.5. Выводы.

4. Автоматизированный комплекс построения рационального размещения. Численные эксперименты.

4.1. Организация раскройно-заготовительного производства.

4.2. Структура САПР рационального размещения.

4.3. Описание автоматизированного комплекса построения рационального размещения.

4.3.1. Схема нахождения рационального размещения.

4.3.2. Выполнение задачи размещения автоматизированным комплексом.

4.3.3. Функциональные возможности автоматизированного комплекса

4.4. Постановка численных экспериментов и анализ их результатов.

4.4.1. Исследование работы генетического алгоритма с различными декодерами.

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

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

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

4.5. Выводы.

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

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

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

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

В настоящее время используются системы автоматизированного проектирования размещения деталей (как отечественных, так и зарубежных разработок), отличающиеся структурой и объемом выполняемых работ, качеством конструирования решения и технологической подготовки производства. В первую очередь были разработаны автоматизированные системы «Нестинга» (размещение деталей сложных форм), особого внимания заслуживают разработки В.Д. Фроловского и A.A. Петунина. Система «Техтран-Раскрой» компании «НИП-Информатика», разработанная под руководством Фроловского В.Д., объединяет возможности CAM-системы с функциями организации производственного процесса [48]. Система «Сириус» (A.A. Петунин) предназначена для проектирования рационального раскроя, а также для подготовки управляющих программ резки [43]. Однако в различных системах проектирования долгое время вопросы экономии материальных ресурсов уходили на второй план. Внимание уделялось главным образом логическим, а не расчетным операциям. Расчеты и проектирование выполнялись быстро за счет использования простых однопроходных эвристик. Попытка объединить два критерия, затраты времени и экономия материала, была осуществлена в докторской диссертации ЭА. Мухачевой[34]. Она использовала в системах автоматизации линейное программирование. Это оказалось возможным в условиях массового производства.

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1. Двойственный алгоритм, разработанный на базе блочного представления упаковки для получения карты размещения деталей в открытой области;

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

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

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

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

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

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

3. Разработаны методы и алгоритмы конструирования размещения деталей:

• вычислительная схема применения алгоритма замещения для размещения прямоугольных деталей на листы. Основана на учете дополнительного ограничения по длине листа при укладке деталей;

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

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

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

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

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

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

Внедрение результатов в виде автоматизированной системы проектирования рационального размещения прямоугольных деталей осуществлено на следующих предприятиях:

1. ООО «Научно-инженерное предприятие - Информатика», г. С.-Петербург -внедрение в промышленную систему «Тенхтран-Раскрой», 2005.

2. УГАТУ - учебный процесс по специальностям: 080116 «Математические методы в экономике», 010503 «Математическое обеспечение и администрирование информационных систем», в рамках курсов «Методы оптимизации» и «Математические методы и модели исследования операций» и при выполнении курсовых и дипломных работ, 2004-2005. Связь исследования с научными проблемами

Работа выполнялась при частичной поддержке грантов Российского Фонда Фундаментальных Исследований (РФФИ), проекты 99-01-000937, 01-01-000510 и 03-01-07002.

Апробация работы и публикации

Первые результаты в виде генетического алгоритма с двумя известными алгоритмами конструирования размещения нашли свое место в дипломной работе «Генетический алгоритм на базе различных декодеров для решения задачи распределения двумерного ресурса», которая была отмечена медалью

Министерства Образования РФ «За лучшую научную студенческую работу». Созданный программный комплекс отмечен дипломом за первое место в конкурсе на «Лучшую программу для ЭВМ, созданную при дипломном проектировании» Уфимского государственного авиационного технического университета.

Результаты работы, а также отдельные ее разделы докладывались, обсуждались и получили положительную оценку на конференциях: Республиканский конкурс научных работ (Уфа, 2000 (доклад отмечен дипломом), 2002 (работа отмечена грамотой дипломата конкурса научных работ)); Двенадцатая Байкальская международная конференция «Методы оптимизации и их приложения» (Иркутск, 2001); Международная конференция «Компьютерные науки и информационные технологии» СБГГ (Уфа, 2001, 2002, 2005); Всероссийская научно-практическая конференция "Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования" ОПТИМ-2001 (С.-Петербург, 2001); Всероссийская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002, 2004); Всероссийская научно-техническая конференция с международным участием «Мехатроника, Автоматизация, Управление» (Уфа, 2005); семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.

По теме диссертации опубликовано 17 работ. Правовая сторона автоматизированного комплекса защищена «Свидетельством об официальной регистрации программ для ЭВМ» № 2002610945.

Выражаю глубокую благодарность к.ф.-м.н., доценту Мухачевой-Филипповой Анне Сергеевне, д.т.н., профессору Мухачевой Элите Александровне за их ведущую роль при подготовке совместных публикаций, советы и помощь при проведении экспериментов и редактировании текста диссертации.

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

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

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

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

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

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

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

4. В рамках системы САПР рационального размещения разработана подсистема размещения деталей в полубесконечной полосе, листах, в открытой области. Применена схема использования генетического алгоритма совместно с алгоритмами конструирования карт размещения, такими, как «нижний левый», «улучшенный нижний левый», блочный, замещения, двойственный и другими. Все это позволяет повысить коэффициент использования материала в среднем на 5-10% по сравнению с ручным способом или применением простых эвристик, значительно сократить время проектирования и упростить процедуру получения карты размещения деталей.

5. Разработана и программно реализована система учета технологических параметров, таких, как возможность поворота деталей на 90°, припуск на ширину реза, окантовку рулона или листов. Это позволяет расширить практические возможности и значимость разработанного автоматизированного комплекса.

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23. Липовецкий А.И. Свойства прямоугольных укладок и алгоритмы оптимального раскроя // Управляющие системы. ИМ СОАН ССР. 1984., вып. 25. 34 с.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

44. Петербург: ЦНИИТС. 2001. С.182-188.

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

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

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

48. Adamovicn A., Albano A. Nesting two-dimensional shapes in rectangulark M, ,

49. Modules // Comput. Aeded Design. 1976. 8(1). P.27-33.

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

51. Beasley. J.E. A population heuristic for constrained two-dimensional nonguillotine cutting. EJOR, 156, 2004, p.601-627.

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

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

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

55. Caprara A. and Toth P. Lower bounds and algorithms for the 2-dimentional vector packing problem. Discrete Applied Mathematics, 111. 2001. pp. 231-262.

56. Cavique L., Rego C. and Themido I., Case oriented paper Subgraph ejection chains and tabu search for the crew sheduling problem. 50. 1999. pp. 608-616.

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

58. Coffman E.G., Garey M.R., Johnson D.S. and Tarjan R.E., "Perfomance bounds for level-oriented two-dimentional packing algorithms" S1AM Journal on Computing 9 (1980) P. 801-826.

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

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

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

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

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

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

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

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

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

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

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

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

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

72. Glover F. and Laguna M. Tabu search. Kluwer Academic Publishers.1997.

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

74. Holland J.H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, The University of Michigan Press (1975), and MIT Press (1992).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

93. 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. 261270.

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

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

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

97. 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. Работа поддержана РФФИ, проект 99-01-00947.

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

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

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