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

Министерство общего и профессионального образования Российской Федерации

Московский государственный горный университет

На правах рукописи ЛАЩЕНКОВ Андрей Валерьевич

УДК 681.3

РАЗРАБОТКА МАТЕМАТИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЙ ОПТИМИЗАЦИИ ПРОЕКТНЫХ РЕШЕНИЙ НА ОСНОВЕ РАСКРАСКИ ВЕРШИН ГРАФА (МОГРАФА)

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

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: проф., докт. техн. наук ГОРБАТОВ В. А.

Москва 1999

Содержание

Стр.

Введение ..................................................................................................................3

Глава I. Существующие методы группирования объектов на основе раскраски вершин графа...................................................................................23

1.1. Точные методы раскраски...............................................................................2 б

1.2. Приближенные методы раскраски..................................................................39

1.3. Характеризация раскраски вершин графа...................................................... 57

1.4. Сравнительный анализ методов раскраски вершин графа.............................62

Выводы ...................................................................................................................71

Глава II. Разработка эффективных инвариантных средств группирования

объектов на основе раскраски графа (мографа) ............................................72

11.1. Улучшенные критерии соцветности вершин................................................72

11.2. Совместное применение слабо-коррелированных приближенных алгоритмов раскраски........................................................................................8 5

11.3. Декомпозиционный подход к раскраске вершин графа ...............................94

11.4. Редукция и раскраска графов.......................................................................10 6

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

Выводы .................................................................................................................127

Глава III. Описание пакета программ "Раскраска".......................................12 8

111.1. Назначение, характеристики и структура пакета программ "Раскраска" ..128 II 1.2. Описание библиотеки "ColorLib", реализующей разработанные

методы раскраски..............................................................................................131

111.3. Форматы данных, используемых пакетом программ "Раскраска".............14 4

111.4. Руководство пользователя пакета программ "Раскраска"..........................155

Выводы .................................................................................................................158

Глава IV. Использование пакета программ "Раскраска" при оптимизации

проектов технологических процессов машиностроительного профиля....159

Выводы .................................................................................................................187

Заключение .........................................................................................................188

Список литературы............................................................................................191

Введение.

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

При этом основной стратегией по совершенствованию технической и технологической базы и оптимизации организации производства является осуществление интегральной автоматизации цикла "исследования - проектирование - технологическая подготовка производства - производство", использование промышленной робототехники и организация гибких производственных систем (ГПС).

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

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

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

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

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

Большинство задач такого рода могут быть эффективно решены в рамках теоретико-графового подхода.

В исследование проблем оптимизации проектных решений на основе теоретико-графового подхода внесли большой вклад российские и зарубежные ученые: В.А.Горбатов [15-23], Н.Г.Малышев [48], А. В. Суворов [48, 58], Л. С. Берштейн [8], О. С. Бартенев [5], 3. Б. Хадонов [63], В. М. Лохин [46], М.И.Смирнов [23, 56-57],

А. Г. Дедегкаев [27], К. X. Пагиев [51], Т. А. Крупа [40], П. Г. Павлов [22], Н. Кристофидес [39, 77], Н. Део [91] и др.

Разнообразные задачи, возникающие при проектировании и организации функционирования гибких производственных систем, проектировании радиоэлектронной аппаратуры, нейронных сетей, оптимизации программного кода, составлении графиков осмотра, хранении и транспортировке товаров, и многие другие задачи оптимизационного характера часто могут быть сведены к одной из наиболее общих комбинаторных задач теории графов - задаче раскраски вершин графа, или некоторым ее обобщениям [4, 9, 10, 14, 15, 18-24, 27-31, 33-39, 45, 49, 52, 55, 59, 61, 62, 67, 69, 70, 72, 76, 79, 88, 94]. (Наиболее общей трактовкой задачи раскраски вершин графа является разбиение некоторого множества объектов, для которых задано бинарное отношение несовместимости, на минимальное число подмножеств, таких, что все объекты, принадлежащие одному подмножеству, попарно совместимы.)

Однако понятие раскраски графа в классической формулировке [6, 36, 50, 60, 64] далеко не всегда является адекватным средством формализации при решении реальных задач группирования, т.к. на практике отношение несовместимости, определенное на множестве группируемых объектов, часто имеет произвольный порядок (арность); в этом случае задача группирования сводится к раскраске вершин модельного графа, или мографа. (Введенное в середине шестидесятых годов российским ученым В. А. Горбатовым понятие мографа позволяет осуществлять формализацию процессов с учетом отношений произвольного порядка; позднее в западной литературе для обозначения того же понятия появился термин гиперграф [73].) Под раскраской вершин мографа в К цветов принято понимать разбиение множества его

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

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

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

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

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

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

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

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

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

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

I Л

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

Задача группирования при фиксированном размещении инструментов возникает при группировании операций по уже имеющимся технологическим процессам на стадиях долгосрочного и краткосрочного планирования в том случае, когда поиск инструмента в магазине станка ведется по номеру позиции, в которой он установлен [10].

Пусть V— {V1, \>г, ••• Удг} ~ множество однородных операций, Я {Л, ... Гм} - множество всех инструментов, необходимых для выполнения множества операций К, а Z - число позиций в инструментальном магазине (револьверной головке) станка.

Для каждой операции V,- е V задан набор из не более чем Z пар чисел (р, Д где р - номер позиции магазина (револьверной головки), /}• -номер инструмента, установленного в этой позиции.

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

Эта задача характеризуется матрицей Q-\\qis\\ размерности N х в которой =/, если при выполнении операции V,- в я-й позиции должен быть установлен инструмент /), и ^ = 0, если при выполнении операции V,- позиция $ не используется. Таким образом, /-я строка матрицы б соответствует операции V/, а 5-й столбец соответствует 5-й позиции магазина (револьверной головки) станка.

Задача группирования при фиксированном размещении инструментов сводится к решению задачи о нахождении раскраски в минимальное число цветов вершин графа попарной несовместимости операций (7(0 = <У, Ц>, вершины которого взаимно однозначно соответствуют операциям, и две вершины V/, у/ е V смежны тогда и только тогда, когда соответствующие им операции хотя бы в одной из позиций магазина требуют наличия различных инструментов, т.е., существует 5 (5= 1,2, ... 2!), при котором выполняется следующее условие: - qjs) ■ • qjs Ф 0.

Смежность вершин означает, что соответствующие им операции не могут входить в одну группу. Очевидно, что каждая группа совместимых операций является пустым подграфом графа <7(0, и наоборот, каждый пустой подграф образует группу операций, которые могут быть выполнены в рамках одной инструментальной наладки.

Таким образом, задача группирования состоит в покрытии графа несовместимости операций <7(0 минимальным числом пустых подграфов, т.е., в нахождении раскраски графа (7(0 в минимальное число цветов.

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

станка могут варьироваться. Эта же задача возникает при группировании операций по уже имеющимся технологическим процессам в случае, кргда поиск инструмента в магазине станка ведется не по номеру позиции, а по коду, заданному на инструментальном блоке, либо когда устройство ЧПУ обеспечивает оперативную привязку управляющей программы к текущему размещению инструмента [10].

Пусть У= {V,-} (1 = 1, 2, ... Л) - множество однородных операций, Я ={/}•} (/ = 1,2, ... М) - множество всех инструментов, используемых множеством операций V, Z - число позиций в инструментальном магазине (револьверной головке) станка.

Для каждой операции V,- е V задан набор из не более чем Z номеров используемых инструментов.

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

Задача группирования при свободном размещении инструментов характеризуется двоичной матрицей У= (| у у (| размерности N у. М, в которой Уу~\, если инструмент /) используется при выполнении операции V,-, и у у = 0 - в противном случае. Таким образом, 1-я строка матрицы (? соответствует операции V/, а у-й столбец соответствует инструменту /). Очевидно, что в каждой строке может содержаться не более Z единиц. Задача группирования при свободном размещении инструмента состоит в нахождении перестановки строк, при которой матрица У разбивается на минимальное число подматриц Г/ (/ = 1,2, ... V) размерности (Л^ + N2 + ... + = А7), таких, что число

ненулевых столбцов в каждой из подматриц К, не превышает 2.

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

инструментальный магазин станка

Z - число позиций в магазине

Группа 1: У1с V

Множество инструментов:

щ<г

Множество деталей (операций):

У= {VI, У2, М

Множество инструментов:

М>1

К шт

Рис. 1. Постановка задачи группирования деталей и операций при свободном размещении инструментов в магазине станка.

Данная задача также может быть охарактеризована мографом &мк= к(Уя, ^у), иу>, множество вершин (букв) Уд которого однозначно соответствует множеству всех используемых инструментов В, а множество слов - множеству группируемых деталей (операций) V. (При этом слово, соответствующее детали V/, состоит из всех тех букв, которым соответствуют инструменты, использ