Технические науки/12. Автоматизированные системы управления на производстве

К.т.н. Хасанова Э. И.,

Д.т.н. Филиппова А. С.,

Телицкий С. В.

Уфимский государственный авиационный технический университет, Россия

Оптимизация размещения технических объектов в системах автоматизированного проектирования

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

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

Области возникновения задачи

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

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

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

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

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

Подсистема автоматизации проектирования размещений

объектов в многосвязный ортогональный полигон

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

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

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

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

Имеется многосвязный ортогональный полигон. Опишем вокруг него прямоугольник (рис. 6). Образовавшиеся при этом многоугольные области этого прямоугольника, не принадлежащие полигону, представим как виртуальные препятствия. Далее разделим многоугольные препятствия сквозными линиями так, чтобы они разбились на прямоугольники (рис. 6). Таким образом, исходная задача сводится к следующей: Дана прямоугольная область ширины W и длины L, а также набор прямоугольных препятствий заданных размеров, , где μ – количество препятствий, ω_ν, λ_ν – ширина и длина ν-го препятствия. Введем прямоугольную систему координат и зададим положение каждого прямоугольного препятствия B_ν координатами (χ_ν, η_ν) его нижне-левого угла (рис. 6). Таким образом, многосвязный полигон можно представить в следующем виде: .

Требуется найти множество П={П_1, П₂, …, П_m} прямоугольных боксов минимальной мощности, где (x_i,y_i) – координаты нижне-левого угла i-го прямоугольника, w_i и l_i – его ширина и длина, m – искомая мощность множества П, удовлетворяющие следующим условиям: 1° Ребра боксов параллельны ребрам области; 2º Взаимное неперекрытие боксов; 3º Неперекрытие боксов с гранями области; 4º Неперекрытие боксов с препятствиями; 5º Прямоугольные боксы должны покрывать всю свободную область многосвязного ортогонального полигона.

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

в боксах многосвязного ортогонального полигона.

Имеется набор прямоугольных боксов П_k, заданных размеров W_k, L_k, , где m – количество боксов, W_k, L_k – ширина и длина k-ой области. Имеется также набор прямоугольных предметов заданных размеров w_i, l_i, , где n – количество прямоугольников, w_i, l_i – ширина и длина i-го предмета. Таким образом, исходная информация задачи может быть представлена следующим набором данных:

.

Положение каждого прямоугольника P_i в области П_k зададим координатами (x_ki,y_ki) его левого нижнего угла. Решение рассматриваемой задачи может быть представлено в виде набора .

Набор GP=(x,y) является допустимым сквозным размещением, если выполняются следующие условия: 1 º Ребра предметов параллельны ребрам бокса; 2º Взаимное неперекрытие предметов; 3º Неперекрытие предметов с гранями области. Набор GP=(x,y) является сквозным размещением, если при выполнении условий 1º, 2º, 3º имеет место 4º –Условие сквозного размещения.

Критерием качества может служить коэффициент размещения РС [1].

При исходных данных требуется максимизировать PC на множестве размещений {GP=(x,y)}, удовлетворяющих условиям 1º, 2º, 3º, 4º.

Методы решения задачи

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

При размещении прямоугольных объектов в выделенных областях применимы эволюционные подходы, в частности модифицированный эволюционный метод поиска решения в окрестностях для проектирования размещения объектов внутри прямоугольных областей [4], метод последовательного уточнения оценок (SVC) [5], а также методы горизонтального и вертикального заполнения боковых пустот с использованием уровневых технологий [6].

Литература

1. Мухачева Э. А., Валиахметова Ю. И., Хасанова Э. И., Телицкий С. В. Проектирование размещения ортогональных объектов на полигонах с препятствиями // Информационные технологии. 2010. № 10. С. 16–22.

2. Хасанова Э. И. Алгоритм гильотинного размещения контейнеров в полосу с препятствиями // Фундаментальная математика и ее приложения в естествознании: матер. Междунар. шк.-конф. для студентов, аспирантов и молодых ученых. Уфа: РИЦ БашГУ, 2009. С. 78.

3. Хасанова Э. И., Валеев Р. А. Матричный способ декомпозиции многосвязного полигона на множество прямоугольных областей минимальной мощности // Вестник УГАТУ. Уфа: УГАТУ, 2010. Т. 14. № 2 (37), С. 183–187.

4. Хасанова Э. И. Гильотинный раскрой промышленных материалов: эволюционный метод на базе уровневых алгоритмов // Актуальные проблемы в науке и технике: сб. ст. 3-й Всерос. зимн. шк.-сем. аспирантов и молодых ученых. Уфа: Диалог, 2008. Т. 1. С. 247–255.

5. Belov G., Scheitchauer G., Mukhacheva E.A. On dimensional heuristics adapted for two-dimensional rectangular strip packing. Technical report. Dresden University. 2006. URL http://www.math.tu-dresden.de/capad/. Preprint MATH-NM-02-2006.

6. Мухачева Э. А., Хасанова Э. И. Гильотинное размещение контейнеров в полосе: комбинирование эвристических технологий // Информационные технологии. 2009. № 11. С. 8–14.