Введение к работе
Диссертационная работа посвящена разработке методов повышения эффективности при проектировании размещения технических объектов на многосвязном ортогональном полигоне и созданию на этой базе программного обеспечения.
Актуальность темы исследования
Результатом экономического роста в России является появление новых производственных организаций и предприятий по оказанию услуг, что ведет к увеличению конкуренции среди них. Основными факторами успеха при этом являются: снижение стоимости и повышение качества продукции и оказываемых услуг, гибкость при внедрении новой продукции, сокращение времени вывода ее на рынок. Существенного уменьшения времени цикла и подготовки производства, увеличения гибкости можно добиться благодаря внедрению автоматизированных систем управления и проектирования. В сложной системе автоматизации определенное место занимают подсистемы автоматизации заготовительного производства, в составе которого важное место занимают программные комплексы расчета рационального размещения предметов. Еще одним из путей снижения стоимости продукции является уменьшение транспортных издержек и расходов на хранение, которое достигается путем составления рациональных планов размещения продукции на складах и в транспортных средствах. Применение автоматизированных систем управления и проектирования на данном этапе позволит быстро и качественно решать эту проблему.
При проектировании рационального размещения предметов область размещения может иметь различную форму. Под многосвязными ортогональными полигонами будем понимать ортогональные многоугольники, внутри которых расположены односвязные многоугольники (препятствия). Задачи размещения прямоугольных объектов внутри многосвязных ортогональных полигонов находят широкое применение в различных отраслях деятельности человека. При проектировании сверхбольших интегральных схем на этапе глобальной трассировки после выделения областей для трассировки, внутри которых запрещено размещение элементов; при размещении грузов на палубах судов, когда необходимо учитывать наличие различных препятствий в виде люков, кранов, стрел и других палубных устройств; при проектировании размещения товаров в складских помещениях, где помимо зоны хранения имеются проходы, зоны погрузки и разгрузки, приемки и фасовки товаров; при раскрое некондиционных промышленных материалов. Создание эффективных планов размещения с обходом имеющихся препятствий способствует увеличению плотности компоновки элементов на кристаллах микросхем и миниатюризации электронных устройств; сокращению доли неиспользуемого полезного пространства при хранении и перевозке то-
варов; уменьшению отходов при раскрое промышленных материалов, что в итоге приводит к снижению затрат и стоимости продукции.
Задачи размещения прямоугольных объектов внутри многосвязного ортогонального полигона являются обобщением задач 2DBP (2-Dimensional Bin Packing), то есть, как и они, относятся к классу NP-трудных задач комбинаторной оптимизации. На сегодняшний день не известно алгоритмов поиска оптимального решения полиномиальной сложности для этого класса задач, и точный результат в общем случае может быть получен переборным алгоритмом только за экспоненциальное время. При больших размерностях задач целесообразно использовать эвристические методы поиска рационального решения.
Вышесказанное определяет актуальность разработки эффективных методов и алгоритмов решения задачи размещения прямоугольных объектов в многосвязных ортогональных полигонах в рамках системы автоматизации проектирования.
Цель работы - повышение эффективности проектирования размещения прямоугольных объектов внутри многосвязных ортогональных полигонов с использованием двухуровневого подхода для декомпозиции задачи с применением эволюционных метаэвристик.
Для достижения цели работы были поставлены следующие задачи:
Изучить известные технологии размещения прямоугольных предметов внутри прямоугольной области, а также алгоритмы покрытия многоугольных фигур прямоугольниками и рассмотреть возможность их применения для решения задачи построения плана размещения прямоугольных объектов внутри многосвязных ортогональных полигонов; исследовать технические особенности различных областей возникновения задачи размещения прямоугольных объектов внутри многосвязного ортогонального полигона;
Разработать эффективные эвристические алгоритмы для решения задач размещения прямоугольных предметов внутри прямоугольных областей с использованием базовых методов;
Разработать эффективные алгоритмы декомпозиции многосвязного ортогонального полигона на прямоугольные боксы для определения области размещения;
Разработать подсистему автоматизации проектирования размещения геометрических объектов, реализующую предложенные алгоритмы и применить её для проектирования рационального размещения;
Исследовать эффективность расчетного модуля разработанной системы проектирования при помощи численного эксперимента.
Объектом исследования является комплекс задач, возникающих в различных производственных отраслях и связанных с размещением геометрических объектов в многосвязный ортогональный полигон.
На защиту выносятся:
Модифицированный эволюционный метод поиска решения в окрестностях для проектирования размещения объектов внутри прямоугольных областей или на полубесконечной полосе;
Методы горизонтального и вертикального заполнения боковых пустот при проектировании размещения объектов в прямоугольную область с использованием уровневых технологий;
Метод матричной декомпозиции многосвязного ортогонального полигона на прямоугольные области для последующего размещения в них объектов;
Метод условных резов для декомпозиции ортогонального полигона на прямоугольные области для последующего размещения в них объектов;
Подсистема автоматизации проектирования инвариантных размещений объектов, реализующая предложенные методы, и результаты численных экспериментов на основе созданного математического и программного обеспечения.
Научная новизна работы
Разработан модифицированный эволюционный метод поиска решения в окрестности, новизна которого состоит в способе изменения окрестности на каждой итерации при проектировании размещения объектов в прямоугольную область. Он позволяет улучшить найденное ранее решение путем исследования его окрестностей и предусматривает возможность смены локальной области поиска.
Разработаны методы горизонтального и вертикального выделения боковых пустот, новизна которых состоит во включении в уровневый алгоритм процедур заполнения свободного пространства в каждом уровне прямоугольных предметов. Он позволяет конструировать более плотные планы размещения и в большинстве случаев превосходит результаты уровневого алгоритма.
Разработан метод условных резов для декомпозиции ортогонального многоугольника на прямоугольные области для последующего размещения в них объектов. Он основан на последовательном разделении области с препятствиями сквозными горизонтальными и вертикальными линиями до тех пор, пока не останется областей с препятствиями. Он может быть использован в частном случае для декомпозиции многоугольника без препятствий.
Разработан метод матричной декомпозиции многосвязного ортогонального полигона на прямоугольные области для последующего размещения в них объектов, новизна которого состоит в представлении многосвязного ортогонального полигона в виде бинарной матрицы и последующем объединении ячеек с использованием уровневых технологий.
Разработана подсистема автоматизации проектирования инвариантных размещений объектов, реализующая предложенные алгоритмы. Она
позволяет решать задачи размещения прямоугольных предметов в полосу, прямоугольную область и многосвязный ортогональный полигон.
Практическая значимость работы: предложенные в диссертационной работе методы ориентированы на достаточно широкий класс прикладных задач, связанных с проектированием рационального размещения прямоугольных объектов в многоугольную область с препятствиями. Результаты диссертации могут быть рекомендованы к решению различных прикладных задач, например, задачи размещения грузов на палубах судов, проектирования размещения товаров в складских помещениях, задача проектирования размещения элементов интегральных схем с учетом областей трассировки и т.д.
Разработанная программная система проектирования рациональных размещений позволяет быстро строить планы расположения технических объектов с высоким коэффициентом использования свободного пространства.
Связь исследования с плановыми исследованиями
Работа выполнялась при поддержке гранта Президента Российской Федерации для государственной поддержки ведущих научных школ Российской Федерации НШ-65497.2010.9.
Апробация работы
Результаты работы, а также отдельные ее разделы докладывались и обсуждались на конференциях: III Всероссийская зимняя школа-семинар аспирантов и молодых ученых (Уфа, 2008 г.); Всероссийская молодежная научная конференция «Мавлютовские чтения» (Уфа, 2008 г.); IV Всероссийская зимняя школа-семинар аспирантов и молодых ученых (Уфа, 2009 г.); IV Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2009 г.); Международная школа-конференция для студентов, аспирантов и молодых ученых (Уфа, 2009 г.); Российская конференция «Дискретная оптимизация и исследование операций» (Алтай, 2010 г.); научные семинары кафедры вычислительной математики и кибернетики и кафедры математики Уфимского государственного авиационного технического университета.
По теме диссертации опубликовано 10 работ, в том числе 3 статьи в рецензируемых журналах из списка ВАК. Правовая сторона программного продукта защищена «Свидетельством об официальной регистрации программ для ЭВМ» № 2010617454.
Структура и объем работы
Диссертация состоит из введения, четырех глав и заключения. Объем работы составляет 187 страниц машинописного текста, включая 53 рисунка, 21 таблицу, список литературы, содержащий 153 название, и 3 приложения.
Выражаю благодарность профессору Э. А. Мухачевой за консультации и советы при выполнении исследований и написании диссертационной работы.
