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

• Тарасов, Андрей Евгеньевич
• кандидат технических наук
• 2007

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

ВВЕДЕНИЕ.

ГЛАВА I. ПРОЕКТИРОВАНИЕ РАЦИОНАЛЬНОГО РАСКРОЯ ПРОМЫШЛЕННЫХ МАТЕРИАЛОВ С ИСПОЛЬЗОВАНИЕМ КОМБИНАТОРНЫХ МЕТОДОВ.

1.1. Основные задачи.

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

1.3. Проектирование ресурсосберегающих технологий.

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

1.5. Основные подходы к разработке системы автоматизации раскроя светопрозрачных конструкций.

ВЫВОДЫ ПО ГЛАВЕ I.

ГЛАВА 2. ЗАДАЧИ ЛИНЕЙНОГО РАСКРОЯ МАТЕРИАЛА СМЕШАННЫХ ДЛИН И МЕТОДЫ ИХ РЕШЕНИЯ В УСЛОВИЯХ МЕЛКОСЕРИЙНОГО ПРОИЗВОДСТВА СВЕ-ТОПРЗРАЧНЫХ КОНСТРУКЦИЙ.

2.1. Задача оптимизации раскроя материала различной длины в условиях единичного и мелкосерийного производства.

2.2. Методы расчета рационального раскроя линейного материала.

2.2.1. Простые эвпистики для решения задач линейного раскроя

2.2.2. Использование метода последовательного уточнения оценок (SVC) для решения задачи линейного единичного раскроя.

2.2.3. Эвристические алгоритмы линейного раскроя.

2.3. Экспериментальная оценка эффективности метода SVC расчета рационального линейного раскроя.

ВЫВОДЫ ПО ГЛАВЕ 2.

ГЛАВА 3. ПРОБЛЕМНО-ОРИЕНТИРОВАННЫЕ АЛГОРИТМЫ КОНСТРУИРОВАНИЯ

РАЦИОНАЛЬНЫХ КАРТ РАСКРОЯ СТЕКЛА.

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

3.2. Уровневые методы конструирования карт раскроя стекла.

3.3. Послойные алгоритмы решения целочисленной задачи раскроя стекла.

3.3.1. Послойные алгоритмы расчета рационального раскроя, основанные на рулонном принципе.

3.4. Метод конструирования вертикалей.

ВЫВОДЫ ПО ГЛАВЕ 3.

ГЛАВА 4. МЕТОДИКА СОЗДАНИЯ САПР ТП ПРОИЗВОДСТВА СВЕГОПРОЗРАЧНЫХ КОНСТРУКЦИЙ НА БАЗЕ ОПТИМИЗАЦИОННЫХ МОДУЛЕЙ РАСКРОЯ.

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

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

4.3. Промышленное внедрение результатов раскроя.

ВЫВОДЫ ПО ГЛАВЕ 4.

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

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

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

Цель работы

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

Задачи исследования

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

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

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

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

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

5. Исследовать эффективность предложенных методов и алгоритмов, провести с этой целью численные эксперименты.

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

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

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

1. Концепция разработки и использования проблемно-ориентированных методов оптимизации в системах автоматизации проектирования раскройно-заготовительного производства.

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

3. Новые послойные алгоритмы проектирования гильотинных раскроев: «модификация уровневого двухфазного алгоритма» и «метод конструирования вертикалей», в рамках которых реализуются проблемно - ориентированные ограничения на гильотинный раскрой стекла.

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

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

Научная новизна результатов

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

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

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

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

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

Практическая значимость и внедрение результатов

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

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

• ООО «Промышленно-строительный комплекс-6», г. Уфа;

• ООО «Комплекс строительно-монтажных работ», г. Уфа;

• ООО «О.К.Н.О.», г. Уфа.

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

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

Связь исследования с научными проектами

Работа выполнялась при частичной поддержке грантов и программ:

Структура работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений.

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

ВЫВОДЫ ГЛАВЕ 4

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

101

ЗАКЛЮЧЕНИЕ

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

На основании вышеизложенного была проведена настоящая работа, основные выводы и результаты которой состоят в следующем:

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

2. Модифицирован базовый метод «последовательного уточнения оценок» путем введения в него специальной барьерной политики, которая позволила повысить эффективность метода в технологической среде. Разработан новый эволюционный метод для решения задачи раскроя смеси материала различной длины. Суть алгоритма в применении гибридизации известных метаэв-ристических алгоритмов в процессе поиска оптимальной последовательности поставки материала и отрезания заготовок. Этот подход позволил существенно сократить время расчета типового плана раскроя (с 30 минут до 2 секунд). При этом полученный коэффициент ресурсосбережения отличается от оптимального не более чем на 0,1%.

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

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

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

103

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

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

2. Ананьев В.В. Информационные технологии в строительном бизнесе // Гузаиров М.В., Тарасов А.Е. Компьютерные науки и информационные технологии (CSIT'2006) : матер. 8-й Междунар. конф. Карлсруэ, Германия, 2006. С. 183 -187. (Статья на англ. яз.).

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

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

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

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

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

8. Гинзбург А.В. Автоматизация организационно-технологического проектирования в строительстве // Коган П.Б. Открытые системы. 2004. №4. С.36 -42.

9. Гончаров Е.Н. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Кочетов Ю.А. Дискретный анализ и исследование операций. 1999. Серия 2. 6. №1. С. 12 32.

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

11. Гузаиров М.Б. Автоматизация проектирования раскроя стекла: проблемно-ориентированные алгоритмы конструирования рациональных карт раскроя //Тарасов А.Е. Системы управления и информационные технологии. 2007. №3(29). С. 53-57.

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

13. Житников В.П. Задача прямоугольной упаковки в полубесконечную полосу: поиск решения в окрестности локальной нижней границы // Филиппова А.С. Информационные технологии. 2007. №5. С.55 62.

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

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

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

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

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

19. Ли К. Основы САПР (CAD/CAM/CAE) / Спб.: Питер, 2004. 560 с.

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

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

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

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

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

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

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

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

28. Мухачева А.С. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума // Валеева А.Ф., Картак В.М. Москва: изд-во МАИ, 2004. 192 с.

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

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

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

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

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

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

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

36. Мухачева Э.А. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Мухачева А.С. М.: Наука. Автоматика и телемеханика. 2004. №2. С. 10 -15.

37. Мухачева А.С. Технология блочных структур локального поиска оптимума в задачах прямоугольной упаковки // Информационные технологии. Приложение. 2004. № 5. С. 18 -31.

38. Нетесова А. Современная автоматизация управления в строительной компании // Строительный бизнес. 2005. №2. С. 16 20.

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

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

41. Норенков И.П. Основы автоматизированного проектирования / Учебн.для студ. Вузов. М.: МГТУ им. Баумана, 2006. 448 с.

42. Пасерба А. Программные продукты для промышленно-строительных холдингов // Финансовая газета. 2004. №38. С. 33 37.

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

44. Романовский И.В. Пакетный вариант симплекс-метода. Эволюционное описание основных конструкций // Исследование операций и статистическое моделирование. Л.: Изд-во ЛГУ, 1979. Вып. 5. С. 55 -71.

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

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

47. Системы автоматизированного проектирования: Учеб.пособие для втузов: В 9 кн./Под ред. И.П.Норенкова. М.: Высш.шк., 1986. 341 с.

48. Силин Н.К. Методы автоматизации строительного проектирования //Технологии строительства. 2003. №5. С. 23-28.

49. Тарасов А.Е. Решение задачи одномерного раскроя материала различных длин на базе гибридизации эволюционных алгоритмов // Вестник УГА-ТУ. 2007. Т. 9, № 4 (22). С. 111 115.

50. Тарасов А.Е. О проблеме автоматизации промышленно-строительных компаний в РФ // Интеллектуальные системы обработки информации и управления : сб. статей регион, зимн. шк.-сем. аспирантов и молодых ученых. Уфа: Технология, 2006. С. 40 44.

51. Тарасов А.Е. Основные подходы к разработке системы автоматизации раскроя стекла // Компьютерные науки и информационные технологии (CSIT'2007) : матер. 9-й Междунар. конф. Уфа, Россия, 2007. С. 209 211. (Сгагъя на англ. яз.).

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

53. Шайтхауэр Г. Планирование одномерного раскроя материала различной длины на базе непрерывной релаксации и метода отсекающих плоскостей // Мухачева А.С., Белов Т.Н., Мухачева Э.А. Информационные технологии. 2004. № 1. С. 37-45.

54. Aurts Е. Local Search in Combinatorial Optimization // Lenstra J., edit. John Wiley&Sons. 1996. P. 36-43.

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

56. Baesley J.E. http://mscmga.rns.ic.ac.-uk/info.htrnl.

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

58. Belov G. A branch-and price algorithm for one-and-two dimensional two-stage cutting (stock) problems. // Technical report MATH-NM-03-03. Dresden University. 2003. URL: www/math.tu-dresden.de/~capad.

59. Belov G.N. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths // G.Scheithauer. European Journal of Operational Research. 2002. 141. P. 274-294.

60. Bischoff E. Special issue: Cutting and Packing // Wascher G., edit. European Journal of Operational Research. 84 (1995). P. 178 186.

61. Bischoff E.E. A comparative evaluation of heuristics for container loading // Marriott M.D. European Journal of Operation Research. 44(1990). P. 267 276.

62. Bortfeld A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieses // European Journal of Operation Research. 2006. 172(3). P. 814-837.

63. Boschetti M.A. The Two-Dimensional Finite Bin Packing Problem // Qua-terly Journal of the Belgian, French and Italian Operations Research Societies. 2002. P. 256-269.

64. Bortfeld A. Applying tabu search to container loading problems // Ge-hring H. Operations Research Proceedings. 1997. P. 533 538.

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

66. Chung F.K.R. On packing two-dimensional bins // Garey M.R., Jchonson D.S. SIAM J. Alg. Disc. Meth. 3 (1982). P. 66 76.

67. Coffman E. Approximation algorithms for bin-packing-an updated survey // Garey M., Jchonson D. Algorithm Design for Computer System Design (Ausiello G., Lucertini M., Serafini P. eds) Berlin etal. 1984. P. 56 79.

68. Coffman E. Performance bounds for level-oriented two-dimensional packing algorithms // Garey M., Jchonson D., Tarjan R. SIAM J. Comput. 9 (1980). P. 801 -826.

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

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

71. Eley M. Solving container loading problems by block arrangement // European Journal of Operational Research. 2002. 141. P. 393 409.

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

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

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

75. Frenk J.B. Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem // Galambos G.G. Computing 39 (1987). P.201 217.

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

77. Gehring H. A Genetic Algorithm for Solving the Container Loading Problem // Bortfeld A. International transactions in operational research. 1997. V.4, №5/6. P.401-418.

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

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

80. Gilmore P. A Linear Programming Approach to the Cutting-stock Problem // Gomory R. Operations Research. 9(1961). P. 849-859.

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

82. Gomes M. A 2-exchange heuristic for nesting problems. // Oliveria J. European Journal of Operational Research. 2002. 141. P. 359 370.

83. Hifi M. Exact algorithms for the guillotine strip cutting/packing problem // Computers and Operations Research. 1998. (25). P. 925 940.

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

85. Holthaus O. Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths // European Journal of Operational Research. 2002. 141. P. 295 312.

86. Jhonson D.S. Worst-case performance bounds for simple one-dimensional packing algorithms // Demers A., Ullman J.D., Garey M.R., Graham R.L. SIAM J. Comput. V. 3. N4. 1974. P. 299 325.

87. Jhonson D.S. Near-optimal bin packing algorithm // PhD Thesis, MIT, Cambridge, MA, 1973. P. 34 56.

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

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

90. Liu D. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. // Teng H. European Journal of Operation Research. 1999. 112. P. 413-420.

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

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

93. Lodi A. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems Algorithms // Martello S., Vigo D.INFORMS J. Comput. 11 (1999). P. 345 357.

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

95. Martello S. Knapsack problems: Algorithms and Computer Implementations. // Toth P. YOHN WILEY&SONS. Chichester. 1990. P. 34 56.

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

97. Morabito M. Staged and constrained two-dimensional guillotine cutting problems: an and/or-graph approach. // Arenales M. European Journal of Operational Research. 1996. 94. P.548 560.

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

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

100. Nitsche C. New cases of the cutting stock problem having MIRUP. // Scheithauer G., Terno J. Math. Meth. Oper. Res. 1998. Vol. 48. P. 105 115.

101. Scheithauer G. A Branch-and-Bound Algorithm for Solving One- dimensional Cutting Stock Problems Exactly // Terno J. Applicationes Mathematicae, 23.2:, 1995. P. 151-167.

102. Scheithauer G. About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem // Terno J. Oper. Res. Proc. 1991, Springer-Verlag, Berlin Heidelberg. P. 439 444.

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

104. Scheithauer G. Solveng one-dimensional cutting stock problems exactly with a cutting plane algorithm. // Terno Y. Muller A., Belov G. Journal of the Operational Research Society. 2001. 52. P. 1390 1401.

105. Scholl A. A fast hybrid procedure for exactly solving the one-dimensional Bin-Packing Problem. // Klein R., Juergens G. Computers and Operational Research, 1997. 24(7). P. 627 645.

106. Schwerin P. A New Lower Bound for the Bin-Packing Problem and its integration to MTP // Wascher G. Pesquisa Operational. 1999. 19(2). P. 111 131.

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

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

109. Tarnowski A.G. Advance polynomial time algorithm for guillotine generalized pallet loading problem // Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa 1997. P. 93 -125.

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

111. Terno J. Zuschnitprobleme und ihre praktische Losung. Lindeman R., Scheithauer G. // Leipzig. 1987. P. 39 56.

112. Vance P. Branch-and-price algorithms for the one-dimensional cutting stock problem // Computational optimization and Applications 9(3). 1998. P. 212 — 228.

113. Vanderbeck F. Exact algorithm for minimizing the number of setups in the one-dimensional cutting stock problem // Research Papers in management Studies, University of Cambridge. 1998. № 10. P. 123 143.

114. Verhoturov M.A. The sequential value correction method for the two-dimensional irregular cutting stock problem // Sergeyeva O.Y. Pesquisa Operacional. 2000. V. 20. № 2. P. 233 247.

115. Начальник отдела организации учебного процесса1. Копейкина Н.Г.

116. Зав.кафедрой ВТ и ЗИ, д.т.н., профессор1. Васильев В.И.1. Д.т.н., профессор1. Валеева А.Ф.1. АКТо внедрении результатов кандидатской диссертации Тарасова А.Е. на тему:

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

118. Начальник отдела производства У1^^ Сергеев А.С.методов оптимизации»предприятии на этапе технологической подготовки производства1. Инженер-технолог1. Федоров Г.А.1. УТВЕРЖДАЮ

119. Директор ООО «Комплекс строительно-монтажных работ»

120. Директор по производству Тимохин А.В.

121. Конструктор-технологСимченко Г.В.