Характерными чертами современного производства являются: постоянное усложнение конструкций выпускаемых изделий, увеличение их номенклатуры и необходимость частой смены объектов производства, причем сроки освоения и переподготовки производства наряду с объемом необходимых для этого материальных затрат являются важнейшими факторами, определяющими жизнеспособность предприятия.
При этом основной стратегией по совершенствованию технической и технологической базы и оптимизации организации производства является осуществление интегральной автоматизации цикла «исследования — проектирование — технологическая подготовка производства — производство», использование промышленной робототехники и организация гибких производственных систем (ГПС).
Одной из актуальных проблем современности является ускорение процесса проектирования новых изделий и технологий их производства одновременно с повышением качества получаемых при этом проектных решений. В непростых современных условиях мировой и, особенно, российской экономики эта проблема приобретает особое значение.
Продолжающееся бурное развитие микроэлектронной технологии, являющееся одним из главных факторов, определяющих прогресс во всех сферах жизнедеятельности человечества, начиная со второй половины 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/, состоит из всех тех букв, которым соответствуют инструменты, используемые для обработки детали V,-.) В этом случае исходная задача группирования деталей (операций) может быть сформулирована как разбиение множества слов мографа на минимальное число подмножеств, при котором общее число букв, образующих слова, принадлежащие одному подмножеству, не превосходит Z — число позиций в инструментальном магазине (револьверной головке) станка.
Построим граф попарной несовместимости операций (7(У) = <У, Ц>, вершины которого взаимно однозначно соответствуют операциям, и две вершины V/, V} е У смежны тогда и только тогда, когда соответствующие им операции в совокупности используют более чем Z различных инструментов, т. е., число ненулевых столбцов в подматрице, составленной из строк / и у матрицы Г, превышает 2.
Смежность вершин графа С (У) означает, что соответствующие им операции не могут входить в одну группу. Как и в задаче группирования при фиксированном размещении инструмента, каждая группа совместимых операций является пустым подграфом графа попарной несовместимости операций <7(У). Однако обратное утверждение (т.е., утверждение о том, что каждый пустой подграф образует группу операций, которые могут быть выполнены в рамках одной инструментальной наладки) в данном случае уже неверно, поскольку, например, в треугольнике попарная совместимость вершин не гарантирует совместимость третьей вершины с объединением двух других вершин.
Таким образом, задачу группирования при свободном размещении инструментов также можно рассматривать как задачу о покрытии графа попарной несовместимости операций С (Т) минимальным числом пустых подграфов, но не любых, а только таких, что общее число различных инструментов, необходимых для выполнения подмножества операций, соответствующих носителю этих подграфов, не превышает числа позиций в инструментальном магазине станка.
Иными словами, задача группирования при свободном размещении инструментов сводится к раскраске в минимальное число цветов вершин мографа несовместимости операций <7м = <(К 1/д>, множество вершин V которого однозначно соответствует исходному множеству группируемых операций, а множество слов IVк (^с V2 и V* и. и У^) соответствует множеству всех неизбыточных подмножеств операций, таких, что общее число различных инструментов, необходимых для их выполнения, превышает число позиций в инструментальном магазине станка.
Помимо класса задач группирования деталей и операций по набору применяемых инструментов, к задаче раскраски вершин графа (мографа) могут быть сведены и другие задачи, связанные с проектированием машиностроительных технологий. Ниже рассмотрены некоторые такие задачи. (Хроматическое число графа (7 будем обозначать как к{С)).
1. Задача распределения ресурсов (оборудования) [29, 39].
Задано множество работ V— {V/, 1>2,V"}, и для каждой работы V,-задано множество ресурсов Я, необходимых для ее выполнения. При этом каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и никакой из ресурсов не может быть одновременно занят в нескольких работах, т. е., работы, использующие хотя бы один общий ресурс, не могут выполняться одновременно. Требуется разбить все множество работ V на подмножества, включающие в себя работы, которые используют различные ресурсы (т.е., могут выполняться одновременно), таким образом, чтобы общее время выполнения всех работ было минимальным.
Эта задача непосредственно сводится к задаче раскраски графа (7, носитель которого совпадает с множеством работ V, и две вершины V/ и V] соединены ребром тогда и только тогда, когда соответствующие им работы используют хотя бы один общий ресурс, т. е., когда п Ф 0. При этом работы, соответствующие вершинам одного цвета, могут выполняться одновременно, а наименьшее время выполнения всех работ достигается при минимальной раскраске и составляет.
Однако на практике более вероятна ситуация, когда в распоряжении имеется более одной единицы ресурсов одного или нескольких типовтогда работы не могут выполняться одновременно только в том случае, если число используемых ими ресурсов некоторого типа превышает общее число имеющихся в распоряжении единиц ресурсов данного типа. В этом случае задача распределения ресурсов (оборудования) сводится к раскраске мографа, носитель которого совпадает с множеством работ, а множество слов состоит из всех таких неизбыточных подмножеств работ, которые не могут выполняться одновременно ввиду нехватки некоторых ресурсов.
2. Задача оптимизации станочного парка [23]. Некоторый технологический процесс включает множество операций У= (у^, у2, уп), и для каждой операции V, — задано плановое время начала ее выполнения (¡-нач и время ее окончаниякон. Одно и то же оборудование может выполнять различные операции, однако существуют операции, которые не могут выполняться на одном оборудовании, т. е., может отсутствовать станок (технологический аппарат), способный выполнить как операцию V/, так и операцию V-. Требуется разбить все множество работ V на подмножества, включающие в себя работы, которые могут выполняться на одном оборудовании, таким образом, чтобы не нарушались плановые сроки выполнения операций и число единиц оборудования, необходимого для их выполнения, было минимальным.
Эта задача непосредственно сводится к задаче раскраски графа С, носитель которого совпадает с множеством операций V, и две вершины V, — и V) соединены ребром тогда и только тогда, когда отсутствует станок, способный выполнить как операцию у,-, так и операцию V,-, либо операции V, — и V] в некоторый момент времени должны выполняться одновременно: (//шч < ^кон) & (*/сои > //ач). При этом операции, соответствующие вершинам одного цвета, выполняются на одной единице оборудования, а наименьшая численность парка оборудования достигается при минимальной раскраске и составляет /г©.
В общем случае возможна также ситуация, при которой отношение несовместимости операций с точки зрения возможности их выполнения на одном технологическом аппарате не является бинарным. В этом случае данная задача также сводится к раскраске специальным образом построенного мографа.
Помимо задач, связанных с проектированием машиностроительных технологий, к задаче раскраски вершин графа (мографа) могут быть сведены и многие другие проектные и оптимизационные задачи.
1. Задача о проектировании коробки передач [29].
Одна из задач, возникающих при проектировании коробки скоростей, заключается в минимизации числа валов, на которых размещаются шестерни.
Эта задача непосредственно сводится к раскраске графа С, носитель которого совпадает с исходным множеством шестерен, и две вершины соединены ребром тогда и только тогда, когда соответствующие им шестерни по каким-либо причинам не могут быть расположены на одном валу. При этом шестерни, соответствующие вершинам одного цвета, могут быть расположены на одном валу, а наименьшее число валов достигается при минимальной раскраске и составляет А (<7).
На практике отношение несовместимости шестерен редко является бинарным, например, ввиду существования ограничения на максимальный общий вес шестерен, которые могут быть расположены на одном валу. В этом случае задача сводится не к раскраске вершин графа попарной несовместимости шестерен, а к раскраске вершин мографа несовместимости шестерен.
2. Задача проектирования многослойных печатных плат [39].
Задано множество клемм, соединенных некоторым множеством прямолинейных проводников У= {у-, у&bdquo-}. Требуется распределить эти проводники по нескольким параллельным платам, на каждой из которых проводники не пересекались бы, таким образом, чтобы число плат было минимально. {Примечание. Клеммы «доступны» на всех платах.).
Эта задача непосредственно сводится к раскраске графа, носитель которого совпадает с исходным множеством проводников, и две вершины соединены ребром тогда и только тогда, когда соответствующие им проводники пересекаются. При этом проводники, соответствующие вершинам одного цвета, могут быть расположены на одной плате, а минимальное число требуемых плат достигается при минимальной раскраске.
Однако данная модель не учитывает тот факт, что на практике топология проводников, соединяющих клеммы, обычно может быть изменена таким образом, чтобы избежать их пересечения. В этом случае задача минимизации числа слоев платы может быть сведена к раскраске мографа, носитель которого совпадает с исходным множеством проводников, а множество слов состоит из всех таких неизбыточных подмножеств проводников, которые не могут быть разведены на одном слое.
3. Составление графиков осмотра (проверки) [39].
Задано множество осмотров (или проверочных операций) У= {V/, V,} одинаковой продолжительности и для каждой пары осмотров известно, могут ли они быть выполнены одновременно. Требуется составить такой график осмотра, который связан с наименьшими затратами времени.
Эта задача непосредственно сводится к раскраске графа <7, носитель которого совпадает с исходным множеством осмотров V, и две вершины соединены ребром тогда и только тогда, когда соответствующие им осмотры не могут выполняться одновременно. При этом осмотры, соответствующие вершинам одного цвета, могут выполняться одновременно, а кратчайший срок выполнения всех осмотров достигается при минимальной раскраске и составляет к (С)*(.
В общем случае возможна также ситуация, при которой отношение несовместимости осмотров с точки зрения возможности их одновременного выполнения не является бинарным. В этом случае данная задача также сводится к раскраске мографа, множество слов которого состоит из всех таких неизбыточных подмножеств осмотров, которые не могут быть осуществлены одновременно.
К задаче раскраски вершин графа (мографа) могут быть сведены и многие другие задачи, такие, как задача составления расписаний [29] и организации конференций [45], ряд задач, возникающих при проектировании радиоэлектронной аппаратуры, автоматов и нейронных сетей [4, 9, 14, 15, 18, 19, 20, 27, 33, 34, 35, 37, 38, 39, 61, 67, 70], оптимизации программного кода [28, 30, 31, 79], хранении и транспортировке товаров [39], и др. [24, 29, 39, 43, 49, 52, 55, 62, 69, 72, 76, 88, 94].
Для решения задачи раскраски вершин графа предложено довольно много алгоритмов (в том числе несколько десятков эвристических), однако далеко не всегда известные алгоритмы дают хорошие результаты на практике, так что выявление лучших методов среди существующих и разработка новых методов, позволяющих повысить эффективность и качество решения этой задачи, по-прежнему является актуальной проблемой.
Задача раскраски вершин мографа (которую можно рассматривать как обобщение задачи раскраски вершин графа), имеющая большую практическую значимость при проектировании гибких технологий машиностроительного профиля и решении других оптимизационных задач, связанных с группированием объектов различного рода, является малоизученной, и общеизвестных эффективных методов ее решения нет, что определяет необходимость их разработки.
Целью работы является разработка эффективных методов решения задачи о разбиении множества объектов на минимальное число групп и разработка инвариантного относительно предметных интерпретаций пакета программ, реализующего эти методы, предназначенного для применения при оптимизации проектных решений.
Идея работы заключается в создании модели группирования объектов, основанной на использовании теоретико-графового подхода, и разработке соответствующих алгоритмических средств на основе развития методов компьютерно-информационной математики.
Задачи исследований:
1. Разработка новой модели организационно-технологического группирования деталей и операций, учитывающей разнообразие инструментального парка и ограниченность емкости инструментальных магазинов при проектировании гибких технологий в машиностроении.
2. Исследование и оценка приближенных алгоритмов раскраски вершин графа с учетом требуемых временных и емкостных ресурсов ЭВМ с целью разработки оптимальной стратегии решения задачи группирования объектов в условиях существования бинарного отношения несовместимости.
3. Обобщение разработанной стратегии на общий случай группирования с целью учета отношений произвольного порядка, определяющих характерные задачи проектирования технологий для ГПС.
4. Реализация разработанных алгоритмов в виде инвариантного относительно предметных интерпретаций программного обеспечения, ориентированного на оптимизацию проектных решений.
Методы исследований. Для решения поставленной в работе проблемы использовались методы дискретной математики, в том числе теории графов, математической логики и характеризационного анализа, и многочисленные машинные эксперименты.
Научные положения, выносимые на защиту, и их новизна:
1. Модель группирования объектов, основанная на понятии мографа несовместимости объектов, и разработанный впервые метод последовательной раскраски вершин специальных мографов, определяющих характерные задачи проектирования технологий для ГПС, позволяющий осуществлять разбиение множества объектов на минимальное число групп.
2. Разработанный впервые декомпозиционный подход к решению задачи раскраски вершин графа, позволяющий повысить качество проектных решений при существующих ограничениях на время их поиска, и алгоритм, реализующий данный подход.
3. Новые критерии соцветности вершин графа, основанные на учете подобия сечений вершин и приближенном учете распределения порожденных цепей нечетной длины, и основанные на этих критериях новые приближенные алгоритмы быстрой раскраски вершин графа, позволяющие повысить качество проектных решений по сравнению с известными методами, имеющими временную сложность того же порядка.
4. Комплекс методов повышения эффективности решения задачи раскраски графа, позволяющий получить оптимальные проектные решения, включающий стратегию совместного применения различных приближенных алгоритмов раскраски, отличающуюся оптимальным подбором применяемых алгоритмов, и стратегию применения методов редукции раскрашиваемых графов, направленных на понижение размерности исходной задачи.
Научная значимость работы состоит в разработке новых подходов и методов решения задачи разбиения множества объектов на минимальное число групп, рассматриваемой как задача раскраски вершин графа (мографа) несовместимости объектов.
Практическое значение работы заключается в разработке эффективного инвариантного программного обеспечения раскраски вершин графов, имеющих до 10 000 вершин, и раскраски вершин мографов, в том числе специальных мографов, характерных для задач проектирования ГПС, причем входящая в состав пакета программ библиотека классов и функций на языке С++ позволяет использовать обратную связь инвариантного пакета раскраски с предметно-ориентированной системой (путем переопределения соответствующих виртуальных функций) для раскраски специальных мографов, сигнатура которых определяется предметно-ориентированной системой.
Обоснованность и достоверность научных положений, выводов и рекомендаций подтверждаются:
• корректным использованием теории множеств, теории графов, и методов оптимизации;
• анализом результатов проведенных машинных экспериментов;
• положительными результатами применения разработанных средств в промышленности.
Реализация результатов работы. Разработанное математическое обеспечение и его реализация в виде инвариантного пакета программ «Раскраска» были внедрены на ОАО «Москвич» включением в состав САПР технологических процессов. Использование пакета «Раскраска» привело к сокращению (до 15%) длительности подготовительно-заключительных работ в цехе мелкосерийного производства и увеличению гибкости производства.
Апробация работы. Основные положения диссертационной работы доложены и обсуждены на Всероссийской Конференции «Логическое управление организационными системами» (Владикавказ,.
1998 г.), семинаре «Автоматизация, информатизация и управление горным производственным комплексом», посвященном 80-летию МГГУ (Москва, 1999 г.), XXX Юбилейной Всероссийской Конференции «Характеризационный анализ и логическое управление» (Москва,.
1999 г.).
Публикации. По материалам диссертационной работы опубликовано четыре работы.
Объем работы. Диссертация состоит из введения, четырех глав и заключения, содержит 3 рисунка, 27 таблиц и список использованной литературы из 94 наименований.
Основные результаты работы.
1. Разработана новая мографовая модель организационно-технологического группирования деталей и операций, учитывающая разнообразие инструментального парка и ограниченность емкости инструментальных магазинов при проектировании гибких технологий в машиностроении.
2. Проведен экспериментальный сравнительный анализ существующих методов раскраски вершин графа, что позволило выделить среди этих методов наилучшие с точки зрения качества решения и требуемых временных и емкостных ресурсов ЭВМ и в итоге повысить эффективность решения задачи группирования объектов. Разработаны новые критерии соцветности вершин графа, основанные на учете подобия сечений вершин и приближенном учете распределения порожденных цепей нечетной длины, и основанные на этих критериях приближенные методы раскраски вершин графа, позволившие существенно повысить качество проектных решений по сравнению с известными методами, особенно в тех случаях, когда модели объектов проектирования описываются графами с большой плотностью.
3. Впервые разработан метод последовательной раскраски вершин специальных мографов с функционально заданной сигнатурой, составляющих основу разработанной модели группирования объектов в машиностроении.
4. Впервые разработан декомпозиционный подход к решению задачи раскраски вершин графа, применение которого позволяет при существующих ограничениях на время поиска решения существенно повысить качество проектных решений по сравнению с известными методами в тех случаях, когда модели объектов проектирования описываются графами, имеющими более тысячи вершин.
5. С целью получения оптимальных проектных решений разработан комплекс методов повышения эффективности решения задачи раскраски графа, включающии стратегию совместного применения различных приближенных алгоритмов раскраски и стратегию применения методов редукции раскрашиваемых графов.
6. Разработан инвариантный пакет программ, реализующий разработанные методы раскраски вершин графа (мографа). Пакет содержит реализацию предложенного метода последовательной раскраски мографов, в том числе специальных мографов с функционально заданной сигнатурой, характерных для задач проектирования ГПС, и взвешенных графов при условии наличия ограничения на суммарный вес вершин, окрашенных в один цвет. Пакет также содержит реализацию шестидесяти четырех различных методов решения задачи о раскраске вершин графа (в том числе точных методов и приближенных методов различной временной сложности, которые могут быть применены для раскраски графов, имеющих до 10 000 вершин), причем пакет снабжен средствами проведения сравнительного анализа различных методов раскраски на сериях графов с целью выявления наиболее эффективных методов для конкретной предметной области.
7. Разработанное математическое обеспечение и его реализация в виде инвариантного пакета программ были внедрены на ОАО «Москвич» включением в состав САПР технологических процессов. Использование этого пакета привело к сокращению (до 15%) длительности подготовительно-заключительных работ в цехе мелкосерийного производства и увеличению гибкости производства, о чем имеется соответствующий акт о внедрении.
Заключение
.
На основании проведенных исследований в диссертационной работе решена задача разработки эффективных математических и программных средств оптимизации проектных решений, связанных с автоматизацией проектирования гибких технологий в машиностроении, на основе разбиения множества объектов на минимальное число групп, сводящегося к раскраске специально построенных мографов (графов).
