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

На правах рукописи

ТАРАСОВ Андрей Евгеньевич

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

05.13.12 - Системы автоматизации проектирования

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

ГТ1 15

Уфа 2007

003177115

Работа выполнена в ГОУ ВПО «Уфимский государственный авиационный технический университет» на кафедре вычислительной техники и защиты информации

Научный руководитель

Официальные оппоненты

Ведущая организация

д-р техн наук, проф Гузаиров Мурат Бакеевич

д-р техн наук, проф

Мухачева Элита Александровна

канд техн наук, доцент

Петунии Александр Александрович

ГОУ ВПО МО «Международный университет природы, общества и человека «Дубна»

Защита состоится 2007 г в часов

на заседании диссертационного совета Д-212 288 03 при Уфимском государственном авиационном техническом университете по адресу 450000, Уфа - центр, ул К Маркса 12, УГАТУ

С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан_ ^ 2007 ]

Ученый секретарь диссертационного совета д-р техн наук, проф

В.В. Миронов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные научные и практические результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах Международной конференции «Computer Science and Information Technologies», Уфа, 2005, 2007, Зимней школе аспирантов и молодых ученых (Уфа, 2006,2007), Международном форуме Ассоциации строителей России по проблемам автоматизации строительного бизнеса, Москва, 2006, научных семинарах кафедры «вычислительной техники и защиты информации» Уфимского государственного авиационного технического университета

По теме диссертации опубликовано 5 работ, в том числе две из них в рецензируемых журналах из списка ВАК

СТРУКТУРА РАБОТЫ

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

Во введении обоснована актуальность работы, сформулированы цель диссертации, основные задачи, новизна полученных результатов и их практическая значимость Приведено краткое содержание работы

Глава 1 посвящена обзору работ в области САПР раскроя, моделей и методов раскроя и их анализу с позиции пригодности применения в САПР свегопрозрачных конструкций Приведены фундаментальные работы Л В Канторовича и В А Залгаллера, которые возникли в связи с развитием прикладных аспектов линейного программирования. Аналогичные работы появились и за рубежом Они оказались приемлемыми для задач планирования в массовом производстве В условиях мелкосерийного и единичного производства, применение линейного программирования мало пригодно Известно, что простейшая задача одномерной упаковки является NP — трудной и точных методов полиномиальной сложности для ее решения не найдено В качестве основных рассмаг-риваются следующие задачи

1 Задача одномерного раскроя материала смешанных длин Входная информация определяется набором следующего вида <т, п, X, ß>, где т - количество различных линейных заготовок, (п-т) - количество хлыстов (прутков) различной длины, X — (Хь Х2, , /ч11+1, , Х^) - вектор длин X,, г -1 ,т заготовок и размеров 1тЫ, г = \п-т, хлыстов (прутков), ß = (bj, b>, , bm, bm+j, , b„) -вектор требуемого количества Ъ„ i = 1, т заготовок, и количество Ът+is i — ~т, хлыстов, имеющихся в наличии Требуется, располагая набором хлыстов заданных размеров, составить план из карт раскроев с минимальными затратами

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

2 Задача гильотинного раскроя Входная информация задается следующим набором данных <W, L, т, w, I, е>, где W - ширина листа, L — длина листа, m - количество прямоугольных заготовок, w = (wl: w2, , w„ , wm) - вектор ширин заготовок, I = (/,, l2, , l„ , lm)~ вектор длин, e - признак возможности поворота заготовки Предполагается, что все размеры целые Требуется получить гильотинным способом раскроя все заготовки, затратив минимальное количество листов Под гильотинным понимается сквозной рез, параллельный кромкам материала

В диссертации приведен обзор известных методов решения задач раскроя и их анализ на предмет эффективности и пригодности для раскроя свегопрозрачного листового материала На основе анализа выбрана послойная методология генерации раскроя стекла Она применялась ранее для раскроя металла, древесных и других материалов Подход был предложен MAdamowich и A Albano в 70-е годы Независимо от них аналогичные алгоритмы разрабатывались в школе Э А Мухачевой Послойные алгоритмы представляют детерминированные эвристики для построения «хорошего» плана раскроя без его дальнейшего улучшения Реализованы два варианта рулонный и раскрой листа Однако не все, присущие данной производственной среде ограничения выполнялись Более подходящими оказались уровневые алгоритмы, приведенные в обзоре A Lodi, S.Martello и D Vigo А именно - «двухфазные уровневые алгоритмы» Эти алгоритмы нуждаются в адаптации и модификациях Тем не менее, специального алгоритма для раскроя стекла найти путем анализа литературы не удалось Анализ существующих на российском рынке САПР в строительной индустрии, показал отсутствие подсистем раскроя с оптимизационным ядром, в том числе - в рамках автоматизированного места технолога

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

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

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

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

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

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

Рациональный план раскроя представляет собой совокупность шаблонов (карт) раскроев гь г2, , гУ1 , гь характеризуемых номером у(г) раскраиваемого куска материала длины Ь](г! и вектором \(г) = (а¡(г), аг(к), , а,{г), , ат(г)), его компоненты указывают количество заготовок каждого вида в раскрое

Кроме того, выходными данными являются количество кусков материала с номером }(/), кроимых по шаблону г Величину %Л,) принято называть интенсивностью применения раскроя г При решении задачи об оптимальной смеси требуется минимизировать общий расход материала, т е величину

Приблизить решение к оптимуму удается путем применения двух эволюционных алгоритмов на этапе раскроя материала при фиксированной последовательности я1 материала различного типа и на множестве перестановок заготовок, на втором (внешнем) этапе ищется лучшая перестановка материала я'щя, для которой я'ор, £ {nd} дает хорошее приближение к оптимальному решению На этом этапе предложен «эволюционный точечный алгоритм (I+I) -

ЕА» изменения списка ТС1, на внутреннем этапе применяется метод «последовательного уточнения оценок» Индивидуальные раскрои конструируются путем применения простого декодера типа «подходящий» Возможно применение и более сильных алгоритмов, таких как динамическое программирование Модификация метода SVC состоит в включении барьерной политики, смягчающей эффект жадности декодера и, следовательно, равномерно использующей материал В качестве барьера принимается средняя величина между верхней и нижней границами функции цели Предложенный подход полностью оправдывает себя в ситуациях с ограниченным количеством материала каждого вида

Модификациями основной задачи являются следующие ситуации

1 Количество прутков каждого вида, или некоторого вида, практически не ограничено Тогда функция цели остается той же самой, а метод решения другой Аналогичный подход сохраняется при ассортиментном задании материала, когда задается отношение kj к2 к„.пг, в котором задан материал

2 Требуется из имеющегося набора исходного материала выбрать один тип прутка Тогда на множестве раскроев требуется минимизировать величину

1

f1 ~ £ ^ В этой постановке наряду с коэффициентом раскроя в каче-

стве функции цели можно использовать его технологичность оценку по деловым отходам, норму расхода материала, и т д

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

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

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

• Допускаются только гильотинные резы (сквозные разрезы, параллельные кромкам материала)

• Возможен поворот деталей на 90°, т к стекло изотропный материал

• Конструкция вертикалей Для вырезания детали из листов, последние располагаются на столе для резки Каретка с алмазом на ее дне, режет лист стекла в направлениях х и у С большими стеклянными листами трудно манипулировать и первые разрезы делаются по оси у от одной кромки листа до противоположной Они делят прямоугольные листы на несколько секций, именуемых вертикалями Размеры вершкалей по оси х не должны превосходить заданной величины

• Ширина реза Расстояние между разрезами не должно быть меньше заданной величины Поэтому важно заботиться о расстоянии между разрезами Резка стекла осуществляется надрезанием материала с его надламыванием вдоль надреза Если соседние надрезы расположены слишком близко, стекло не удается сломать

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

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

Инвариантная к этим условиям геометрическая постановка представляет собой комбинаторную задачу следующего содержания

Задача прямоугольного раскроя листов (2 Dimensional Bin Rectangular Cutting, 2DBRC) Для входных данных <W, L, w, I, e> требуется минимизировать количество N раскраиваемого множества {.S} листов при выполнении условий

• ортогональное размещение прямоугольников в каждом листе для прямоугольной заготовки i = \,т с координатами левого нижнего угла (х„ у,) (ось Ох проходит через нижнюю грань листа, а ось Оу - через левую боковую грань) и любой другой вершины (х,\у,) этого прямоугольника ((х/ = х,) V (ж/ = х, + /,)) а (у,* = у,) V {у? = y¡ + w,)) ,

• неперекрытие деталей для гф], i,j =\,т

((*, >х, + Zj ) V (Xj >х, +¿,))v(y, >yj +wJ)v(yJ >y,

• неперекрытие деталей гранями листов для всех г,) = 1 ,т (х, > 0) а Си, > 0) Л ((у, +>!>)< Ж)) л ((х, + /,)<£)

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

1

Ё

JJ

а 6

Рисунок 1 - Иллюстрация гильотинного раскроя а - гильотинный раскрой, б - негильотинный раскрой

На рис 1 ,а изображен гильотинный раскрой, но он может оказаться непригодным для раскроя стекла, второй разрез - горизонтальный и он может превосходить допустимую длину вертикали Таким образом, не любой гильотинный раскрой является допустимым для раскроя стекла Анализ на соответствие гильотинного раскроя технологическим ограничениям, приведенным выше, позволил выделить уровневую технологию конструирования технологически допустимых раскроев Эта технология подробно рассмотрена в обзоре А Lodi, S Martello, D Vigo Уровневые алгоритмы используют прием, когда каждый новый элемент упаковывается с выравниванием по левому и нижнему краю Через правую сторону прямоугольника максимальной длины проводят вертикальную линию Исходный прямоугольный объект оказывается разделенным на уровни прямоугольной формы, содержащие целиком входящие прямоугольники Что касается стратегии выбора прямоугольников, то она может исходить из известных правил В качестве примера приведем стратегии выбора подходящего прямоугольника Они определяют однопроходные декодеры

Следующий подходящий (Next Fit, NF, рис 2,а) Первый предмет из п упаковывается в исходный прямоугольник, плотно прилегая к левой и нижней граням листа Через правую сторону проводят разделительную линию, выделяется блок, в который уже уложен один прямоугольник Каждый следующий прямоугольник упаковывается полностью в тот же блок, если позволяет сверху остаточная емкость В противном случае прямоугольник укладывается в нижнюю свободную позицию следующего блока

Первый подходящий (First Fit, FF, рис 2,6) На каждом шаге первый подходящий предмет из к помещается в частично заполненный по ширине блок

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

Лучший подходящий (Best Fit, BF, рис 2,в)) Является одним из вариантов жадного алгоритма, когда каждый из уровневых блоков упаковывается с наименьшим остатком

а б в

Рисунок 2 - Уровневые стратегии а — стратегия NF, б - стратегия FF, в — стратегия BF

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

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

Метод конструирования двухмерного раскроя в стеклопромышленности основан на следующей идее на каждом итерационном шаге некоторые прямоугольники объединяются по парам из списка ж Каждую пару описывает новый, сложный (Complex, С-прямоугольник) Возможно 8 различных способов размещения деталей при их объединении (см рис 3)

Р1 шш

Р2

в

Рисунок 3 - Конструирование С-прямоугольников а — вертикаль, б - недопустимые С-прямоугольники, в — допустимые С-прямоугольники

Вариант отбрасывается, если один из размеров С-прямоугольника не менее длины Ь или ширины Ш исходного листа Это случай б рис 3 При этом в случае а С-прямоугольник является вертикалью и он помещается в соответствующий файл Из оставшихся С-прямоугольников выбирается тот, который имеет лучший показатель некоторого критерия, например, минимальная неиспользованная площадь (зазор) На следующих итерационных шагах С-прямоугольники обрабатываются как обычные детали, т е они склеиваются между собой или с заданными деталями При этом постоянно корректируется ассортиментный список /3 Комплексные прямоугольники, как было указано, исключаются из алгоритма, если они становятся вертикалями Процесс прекращается, если все полученные С-прямоугольники стали вертикалями На этом за-

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

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

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

• САПР раскроя, включая автоматическое управление процессом раскроя,

• автоматизированное рабочее место технолога раскройного производства,

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

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

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

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

изделия, технологические и организационные ограничения и параметры деловых отходов, блок раскроя материала, его основным содержанием является оптимизационное ядро для получения информации о раскрое и расчета норм расхода материала

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

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

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

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

Визуализация работы ПО приведена на рис 5

Разработанное программное обеспечение используется на следующих уфимских предприятиях ООО «Промышленно-строительный комплекс -6», ООО «Комплекс строительно-монтажных работ», ООО «О К Н О » Использование программного обеспечения позволило снизить отходы материала от 14% (ООО «ПСК-6») до 26% (ООО «ОКНО») На предприятии ООО «ОКНО » снижение отходов и, как следствие, снижение себестоимости изделий позволило увеличить объем заказов за три месяца на 18%

К

а я ш

0 а

01 о

П. Щ

с 5

а § щ

Ь и 5

и §

и

в %

р

а V

е- ¡8

« 8

£ Н

41 У

Б I

В *

и §

в

№

Ч

Технологическая карта изделия

Подетальные нормы расхода материала

Блок расчета стоимости изделия

Счет на оплату

Нормативно-справочная информация

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

£ 1> ► Артикул

[риупоипа)

гехнолога ргккронного прон>»бдст»а

]] З&Шпе вапопи

I О

[М10*

¡неаюсооо

Арт«@ Сшрв»яо [Киюииа

16й0х130Р 1300x2440

Дпта! Ширим,

Раучеры простиля

Лли)«.1

11«

■МС6 4 •

537 ь

142? в

2545 18

гаге *

Ппан раекроя

Тип пруту-а Ткоя-ео пру.оа | Ддма мгатоул ТКолм загет

Ввод ограничений Реостам« между дареэоми

ц

•• Дмгкп» г-иге&а«

Результаты

Рисунок 5 - Визуализация работы ПО

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в рецензируемых журналах из списка ВАК:

Другие публикации:

Диссертант

А Е Тарасов

Тарасов Андрей Евгеньевич

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

Специальность 05 13 12 - Системы автоматизации проектирования

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано к печати 09 11 2007. Формат 60x84 1/16 Бумага офсетная Печать плоская Гарнитура Тайме Уел печ л 1,0 Уел кр -отт 1,0 Уч.-изд л 1,9 Тираж 100 экз Заказ № 560

ГОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул К Маркса, 12

ВВЕДЕНИЕ.

ГЛАВА 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

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. Конструктор-технологСимченко Г.В.