WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |
  1. Создание эффективных технологий разработки методов раскроя стекла, ориентированных на особенности производства светопрозрачных конструкций.
  2. Разработка средств повышения эффективности конструктивных алгоритмов расчета раскроев стекла.
  3. Использование метаэвристик типа эволюционные алгоритмы для конструирования улучшенных раскроев.
  4. Создание специализированных САПР раскроя с оптимизационным ядром в первую очередь для включения в автоматизированное место технолога.

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

Рациональный план раскроя представляет собой совокупность шаблонов (карт) раскроев r1, r2, …, r, …, rk, характеризуемых номером j(r) раскраиваемого куска материала длины Lj(r) и вектором (r) = (a1(r), a2(r), …, ai(r), …, am(r)), его компоненты указывают количество заготовок каждого вида в раскрое.

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

Приблизить решение к оптимуму удается путем применения двух эволюционных алгоритмов: на этапе раскроя материала при фиксированной последовательности материала различного типа и на множестве перестановок заготовок; на втором (внешнем) этапе ищется лучшая перестановка материала, для которой дает хорошее приближение к оптимальному решению. На этом этапе предложен «эволюционный точечный алгоритм (1+1) - ЕА» изменения списка, на внутреннем этапе применяется метод «последовательного уточнения оценок». Индивидуальные раскрои конструируются путем применения простого декодера типа «подходящий». Возможно применение и более сильных алгоритмов, таких как динамическое программирование. Модификация метода SVC состоит в включении барьерной политики, смягчающей эффект жадности декодера и, следовательно, равномерно использующей материал. В качестве барьера принимается средняя величина между верхней и нижней границами функции цели. Предложенный подход полностью оправдывает себя в ситуациях с ограниченным количеством материала каждого вида.

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

  1. Количество прутков каждого вида, или некоторого вида, практически не ограничено. Тогда функция цели остается той же самой, а метод решения другой. Аналогичный подход сохраняется при ассортиментном задании материала, когда задается отношение k1:k2:…:kn-m, в котором задан материал.
  2. Требуется из имеющегося набора исходного материала выбрать один тип прутка. Тогда на множестве раскроев требуется минимизировать величину. В этой постановке наряду с коэффициентом раскроя в качестве функции цели можно использовать его технологичность: оценку по деловым отходам, норму расхода материала, и т. д.

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

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

  • Допускаются только гильотинные резы (сквозные разрезы, параллельные кромкам материала).
  • Возможен поворот деталей на 900, т.к. стекло изотропный материал.
  • Конструкция вертикалей. Для вырезания детали из
    листов, последние располагаются на столе для резки. Каретка с
    алмазом на ее дне, режет лист стекла в направлениях
    x и y. С большими стеклянными листами трудно манипулировать и
    первые разрезы делаются по оси у от одной кромки листа до
    противоположной. Они делят прямоугольные листы на несколько
    секций, именуемых вертикалями. Размеры вертикалей по
    оси x не должны превосходить заданной величины.
  • Ширина реза. Расстояние между разрезами не должно быть меньше заданной величины. Поэтому важно заботиться о расстоянии между разрезами. Резка стекла осуществляется надрезанием материала с его надламыванием вдоль надреза. Если соседние надрезы расположены слишком близко, стекло не удается сломать.
  • Обязательными являются припуски для последующей
    обработки кромок деталей.
  • Дефекты материала. Возможен раскрой некондиционного
    материала, содержащий в своей структуре дефекты или надломы по
    краям. Их задания и обход составляют специальный раздел
    проекта, предназначенный для оперативного раскроя.

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

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

  • ортогональное размещение прямоугольников в каждом листе: для прямоугольной заготовки с координатами левого нижнего угла (xi, yi) (ось Ox проходит через нижнюю грань листа, а ось Oy – через левую боковую грань) и любой другой вершины (xik,yik) этого прямоугольника ;
  • неперекрытие деталей: для ij,

;

  • неперекрытие деталей гранями листов: для всех

.

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

a б

Рисунок 1 – Иллюстрация гильотинного раскроя:

а – гильотинный раскрой; б – негильотинный раскрой

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

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

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

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

Рисунок 2 – Уровневые стратегии:

а – стратегия NF; б – стратегия FF; в – стратегия BF

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

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

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

L

а б

в

Рисунок 3 – Конструирование С-прямоугольников:

а – вертикаль; б – недопустимые С-прямоугольники;

в – допустимые С-прямоугольники

Вариант отбрасывается, если один из размеров С-прямоугольника не менее длины L или ширины W исходного листа. Это случай б рис. 3. При этом в случае а С-прямоугольник является вертикалью и он помещается в соответствующий файл. Из оставшихся С-прямоугольников выбирается тот, который имеет лучший показатель некоторого критерия, например, минимальная неиспользованная площадь (зазор). На следующих итерационных шагах С-прямоугольники обрабатываются как обычные детали, т.е. они склеиваются между собой или с заданными деталями. При этом постоянно корректируется ассортиментный список. Комплексные прямоугольники, как было указано, исключаются из алгоритма, если они становятся вертикалями. Процесс прекращается, если все полученные С-прямоугольники стали вертикалями. На этом заканчивается первый этап, и приступают к выполнению второго. Конечный результат одной итерации эволюционного алгоритма – количество N раскраиваемых листов. Если это число менее полученного ранее рекорда, то N объявляется рекордом. Далее переходят к следующей итерации эволюционного алгоритма или его работа заканчивается.

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

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»