автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Автоматизированная система предпроектного исследования моделей и алгоритмов рационального раскроя

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ Л 4 ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

На правах рукописи

ГАБИТОВ Валерий Амировкч

АВТОМАТИЗИРОВАННАЯ СИСТЕМА ПРЕДПРОЕКТНОГО ИССЛЕДОВАНИЯ МОДЕЛЕЙ И АЛГОРИТМОВ РАЦИОНАЛЬНОГО РАСКРОЯ

05.13.06 — Автоматизированные системы управления

АВТОРЕФЕРАТ

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

Уфа 19.94

Работа выполнена на кафедре вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.

Научный руководитель — доктор технических наук,

профессор Мухачева Э. А.

Официальные оппоненты—доктор физико-математических

наук, профессор Залгаллер В. А., кандидат технических наук, доцент Черняховская Л. Р.

Ведущая организация — ОКБ «Гидромеханика» (г. Уфа).

Защита состоится 1 июля 1994 г. в 10-00 часов на заседании диссертационного совета К-063.17.03 в Уфимском государственном авиационном техническом университете по адресу: 450000, Уфа-центр, ул. К- Маркса, 12.

С диссертацией можно ознакомиться в библиотеке Уфимского государственного авиационного технического университета.

Автореферат разослан «_____» _1994 г.

Ученый секретарь специализированного совета, доктор технических наук, профессор

В. И. Васильев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

Диссертационная работа представляет собой часть исследований в рамках хоздоговорной работы ИФ-ВК-01-92-ОГ (гос. per. № 01920007257), работы ИФ-ВК-23-93-ПЭ, выполняемой по программе «Университеты России», проводимой в УГАТУ с 1991 по 1994 годы, а также входит в состав темы «Разработка теории и методики организации раскроя», выполняемой по международной программе «Авиа-космос» ИФ-ВК-27-94-ПЗ.

Цель диссертационной работы:

— исследование многообразия постановок задач раскроя п их классификация, характеризующая задачи раскроя;

— исследование эффективности, выявление параметров и области применения алгоритмов, их классификация;

— разработка методов предоптимизационного анализа задач раскроя;

— создание методологии разработки автоматизированной системы предпроектного исследования (АСПИ) задач раскроя в условиях технологической подготовки заготовительного производства;

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

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

Научная новизна

— проведена классификация алгоритмов решения задач раскроя с определением области их применения, положенная в основу создания АСПИ;

— выявлены параметры, характеризующие ожидаемый остаток, которые эффективно влияют на выбор подходящего алгоритма;

— разработан и исследован метод нредоптимпзациошюго анализа задач раскроя;

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

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

Разработанное программное обеспечение является составной частью пакета прикладных программ по автоматизации рабочего места руководителя службы цеха, который находится на стадии внедрения на УАО «Гидравлика». АСПИ широко используется в учебном процессе при изучении курсов «Математическое программирование», «Информатика», «Базы данных н знаний» и других.

На защиту выносятся:

— классификация задач и методов расчета рационального раскроя;

— методика предоптимизационного анализа исходных данных задачи раскроя на базе расчета ожидаемого остатка;

— структура представления знаний в базе знаний и механизм выбора.

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на: VII научно-техническом семинаре (Тюмень, 1990 г.); конференции «Разработка и внедрение САПР и АСТПП в машиностроении» (Ижевск, 1990 г.); VIII научно-техническом семинаре (Ижевск, 1992 г.); научно-практическом семинаре «Автоматизация

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

Публикации. По материалам диссертации опубликовано 8 работ.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

Фактор раскроя мерного или немерного материала порождает классы задач соответственно детерминированного и стохастического раскроя.

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

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

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

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

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

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

Составлен перечень алгоритмов рационального раскроя и определена область их применения. Рассматривалось около 60 алгоритмов только для решения задач линейного раскроя.

Непрерывные алгоритмы строятся на базе линейного программирования с использованием для генерации раскроя динамических схем. Среди них выделяются: приближенные методы (решение задачи линейного программирования на заданном множестве раскроев) ; точные методы («сеточный», «склейки», «каскад»); методы условной оптимизации (различные реализации метода «юго-восточного угла»).

Целочисленные алгоритмы основаны на различных методах дискретной оптимизации: приближенные методы («первый подходящий», «жадные» алгоритмы); метод последовательного уточнения оценок; методы дихотомии и ветвей и границ; метод Гоморп для решения задач целочисленного линейного программирования.

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

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

Рассмотренная выше многовариантность задач раскроя показывает, что проведению расчетов раскроя целесообразно провести предоптимизациоиный анализ задач раскроя.

В третьей главе описывается метод предоптпмизационного анализа задач раскроя; алгоритм вычисления ожидаемого остатка; приводится методика определения соответствия оценки ожидаемого остатка различным группам алгоритмов; дается экспериментальная оценка качества ожидаемого остатка.

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

G

Табл.

Список rpynri непрерывных алгоритмов линейного раскроя

Имя группы

Назначение

Сопутствующие задачи

Расчет S=i

плана из однородных раскроен,

Выбор одного типоразмера материала (рациональной смеси)

lindw

LINTR

LIX.UW

L1NSII

LIWSK

LIXKD

Расчет плана из комбинированных раскроев не более чем на две различные заготовки (двоичные раскрои, S = 2)

Расчет плана из комбинированных раскроев не более чем на три различные заготовки (троичные раскрои)

Л\поговарпангная схема расчета оптимального плана раскроя по двум критериям: Коэффициент раскоря (КРЛ) =>тах: S = > min

Расчет оптимального плана раскроя с применением динамической шкалы оценок

Расчет оптимального плана раскроя с применением метода «склепки»

Расчет оптимального плана раскроя с применением метода «каскад»

Выбор материала одного типоразмера (рациональной смеси]

Выбор материала одного типоразмера (рац. смеси)

Выбор материала одного типоразмера (рац. смеси)

Выбор материала одного типоразмера (смеси материала)

Выбор материала одного типоразмера (рац. смеси)

Выбор материала одного типоразмера (рац. смеси)

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

Продолжение табл. 1

Список групп целочисленных алгоритмов линейного раскроя

Имя группы

Назначение

Сопутствующие задачи

ыгрр

ыгоо

игом

игк\'

Расчет допустимого плана раскроя с применением метода «первый подходящий»

Расчет допустимого плана раскроя с помощью жадного алгоритма

Расчет плана раскроя с помощью метода ветвей и границ

Расчет квази — оптимального плана раскроя [¡а базе методов непрерывного раскроя

Расчет оптимального плана раскроя с помощью метода Гомори

Расчет квазиоптимального плана раскроя с помощью .метода МПУО

Выбор материала одного типоразмера (рац. смеси)

Выбор материала одного типоразмера (рац. смеси)

Выбор одного типоразмера материала (рац. смеси)

Выбор одного типоразмера материала (рац. смеси)

Выбор одного типоразмера (смеси материала)

Выбор одного типоразмера материала (рац. смеси) (некондиции)

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

Предлагается сначала все заготовки, в зависимости от их размеров, разбить на 5 групп: Оь 02) вз, 04, 05. Первые три составляют группу больших заготовок Сб, остальные — группу малых заготовок йм. Оптимальный план (или близкий к оптимальному) может быть получен с помощью алгоритмов, основанных на приближенных методах в случае, если ожидаемый остаток А, полученный при раскрое на заготовки из группы 06, полностью заполняется заготовками из группы См.

Обозначим через Ц длины материала каждого вида ] = 1, п; } 1 п Ь 1 — длины и требуемое количество заготовок каждого вида ¡= 1, ш.

Анализ с целью выявления группы подходящих алгоритмов состоит из следующих элементарных процедур.

1. Упорядочивание. Материал п заготовки упорядочиваются по невозрастанию их длин.

2. Расчет начальных параметров.

Определяются: суммарная длина 20 всех заготовок; нижняя граница расхода материала Ы0; группы заготовок Сл' и доля ч г суммарной длины заготовок каждой группы г, общей длине всех заготовок, \'= 1,5.

3. Первичный анализ

Если ОгЬЮз = 0, то расчет на этом заканчивается и рекомендуются группы алгоритмов ЫМОО, ЫХРР, (см. табл. 1). Если вышеприведенное условие не выполняется, то расчет продолжается.

4. Оценка остатка Л при раскрое на заготовке из й ^

4.1. Если раскрой непрерывный, то определяется количество прутков, необходимых для раскроя каждого вида заготовок и количество прутков для раскроя всех заготовок группы О ^ .

Р , = [1Л 1 ], х ! =й ,/Р , , ¡еС 6 ; N 8 =2х ;

б

Оценка ожидаемого остатка Д=1-7.б/НбЬ

где Z д —длина всех заготовок, входящих в группу в ^ .

В зависимости от полученной величины оценки ожидаемого остатка, по таблице 2 определяется приемлемая группа алгоритмов.

4.2. Если раскрой целочисленный или ситуация не определена, то предварительно вычисляются:

Резерв И в случае безотходного раскроя на заготовки из

С ^ и отношение q ^ =2 ч ^ > \'=1, 3.

Обозначим через д'ь 72- Тз — остатки в среднем при раскрое на заготовки из соответствующих групп Оь С2, (}3. И--значення 71 = 0.266; у2 = 0.102; у3 = 0.058, найдены экспериментальным путем.

С этой целью для каждой группы к=-1, 2, 3 заготовок

Таблица 2

A 0<Д<0.08 0.08^ Д <0.16 0.16< Д <0.24 0.24< Д <0.32

H 0<H<0.2 0.2<H <0.5 0.5<H <1.0 1.0<H <2.0

Группа алгоритмов LINOD LIZPP LIZGD LINOD LINDW LIZGD LIZKV LIZPP LINDW LINTR LIZGD LIZKV LINTR LIYMW LINGR LIZKV LIZWG

при различных исходных данных рассчитывались остатки после Д и;, Д 2k> А зк .а затем остатки в среднем yi—для первой группы, 72— для второй группы и уз для третьей группы заготовок. Вычислительный эксперимент проводился при помощи алгоритма «первый подходящий с упорядочиванием».

Предположим, что оценки yi> Y2. Тз> полученные при раскрое исходного материала, остаются верными н при раскрое остатков.

Алгоритм вычисления ожидаемого остатка А состоит в

с

следующем: рассчитывается ожидаемый остаток Ai = q 1 Yi после раскроя заготовок группы Gi и проверяется возможность использования остатка при раскрое заготовок групп G2 и G3. Если ожидаемый остаток после раскроя заготовок группы G2 удовлетворяет условию Дг^О, то проверяется, можно ли использовать этот остаток при раскрое заготовок группы G3.

Если Ai<q 2Ô , то At: = 0.5 Ai и q б =q б2 —Дь иначе

A, : = Ai—q2Ô u q2 S : = 0; Д2:=0.

Если A,<q3 6 и q2 ô ФО, то Д,: = 0.25 Ai и q3 6 = q3—0.75 Аь иначе,

если Ai<q3 ô и q2 6 =0, то A,: = 0.5 Ai и q3 = q3—Ai;

R с

иначе Ai'. = Ai—q3 u q3 1 :"=0; A3: = 0. Если q2 6 ^0, то A2: = q2 6 Уь

Если Д2<яз Й , то Д2: = 0.2 Д2 и чз 6 = чз 6 —0.75 Д2;

с о

иначе Дг'-^Аг—Чз и qз : =

Если Чз^ =^0, то Дз: = дз^ узД ~Д1+Д5+ Дз; Д-. —шах !Д, Ш.

5. Выбор рекомендуемых алгоритмов.

Если О м =0, то рекомендуемые группы определяются по показателю Д из табл. 2.

Если С м. Ф0, то вычисляют отношение длины остатка после раскроя на заготовки из й ^ на длину всех заготовок

нз О

и-- А(д,+д2+дз)

(1-Д) (Ч4+Ц5) '

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

Для оценки качества алгоритма подсчета ожидаемого остатка Д был проведен вычислительный эксперимент. От программного датчика случайных чисел с нормальным законом распределения моделировались исходные данные для задач раскроя. Для каждой из них была рассчитана величина ожидаемого остатка Д, а также с номощыо алгоритма «первый подходящий с упорядочиванием» реальная величина остатка А".

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

В четвертой главе рассматриваются основы разработки и функционирования, а также общие принципы построения ЛСПИ задач раскроя.

Автоматизированная система прсдпросктного исследования предназначена для поиска наиболее подходящего в за-

данных условиях алгоритма решения задачи раскроя. АСПИ может быть реализована автономно и в составе комплекса программ CUT—CAD. В первом случае система реализована без применения блока предоптимнзационного анализа и целью ее работы является формирование группы подходящих алгоритмов для решения определенного круга задач. Результаты работы системы обеспечивают настройку CUT—CAD непосредственно на потребителя этой системы. Это необходимо в случае поставки усеченной системы CUT—CAD потребителю. Если система реализована в составе комплекса программ CUT—CAD, то ее целью является выбор конкретного алгоритма на основании исходных данных с применением блока предоптимнзационного анализа и передача управления системе CUT—CAD для получения раскройной задачи. Этот режим используется непосредственно для решения производственной задачи.

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

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

Диагностическими системами 2-го поколения являются экспертные системы, которые основаны на применении методов искусственного интеллекта.

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

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

Множество факторов {И 5 }к определяют предметную об-

5=1

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

Р.-М, \ 1/п,

р» ., —а) 5 , ]' = 1 , п 5

к к , п к

где й"="= 1, к, к — число факторов,

5 , п з , п3 — число значений э-го фактора,

Л — множество имен алгоритмов ]-го значения .ч-го фактора.

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

База знаний представляет собой множество модулей определенной структуры. В каждом модуле имеется несколько значений ]=1, п, где п — количество значений фактора.

Структура модуля в базе знании:

Фактор: (название фактора)

Вопрос: (содержание вопроса)

Значение 1: (название значения)

ГП1

М-¡а , }

Значение п: (название значения)

tri ri

M = {a i }

i=l

M — множество имен алгоритмов значения ш n — количество имен алгоритмов, соответствующих значению п.

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

N={a . } k ; N — множество имен алгоритмов модуля. i=l

Структуру базы знаний можно представить следующим образом:

f s ={Р j }" S ,

i = l _

где f s — модуль s, s=l, k (k — число модулей БЗ) P j — множество значений каждого модуля s; j = l, n (n — число значений модуля);

m j

P j ={« ; }

i = l

где a j — множество имен алгоритмов, i=i, ш (m — количество имен алгоритмов, соответствующих одному значению) .

Рассмотрев работу механизма выбора (MB) системы. Работа MB системы состоит из двух этапов. На первом этапе осуществляется переход к следующему модулю в базе знаний и проверка на пересечение множеств имен алгоритмов рабочей памяти и образца модуля базы знаний. Это можно представить следующим образом:

!<=-{« ü )m j ,j = l7rT

i-Ч j = l,m

К — множество имен алгоритмов образца модуля, п — количество значений модуля, ш — количество имен алгоритмов j-го значения, а л — имя алгоритма,

B = {« i } г ,

¡=1

где В — множество имен алгоритмов рабочей памяти,

В1 = ВПК — пересечение множеств имен алгоритмов рабочей памяти и образца модуля,

В, — пересечение множеств В и К,

«еВь если <хеВ и а

Те имена алгоритмов, которые не пересекаются, составляют множество В*, а^В?, если а^В и а ф К.

Если существует непустое пересечение множеств, т. е. аенВ, то происходит переход ко второму этапу; если нет, то осуществляется переход к следующему модулю базы знаний и проверка на непустое пересечение множеств повторяется. На втором этапе осуществляется проверка на пересечение множств имен алгоритмов, соответствующих выбранному значению модуля и множества В[.-

Р = {* , }

где Р — множество имен алгоритмов выбранного значения; М^В^Р — пересечение множеств имен алгоритмов В[ и Р,

аеМь если аеВ, и «<=Р.

Формируется новая рабочая память как объединение множеств М, и В2: М=М,иВ2,

а^М, если а^М, или «еВ2.

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

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

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

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

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

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

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

Автоматизированная система преднроектного исследования реализована на ПЭВМ типа IBM PC/AT вереде MS—DOS на языке Quick С версии 2.5.

Применение АСПИ в составе комплекса программных средств «CUT—CAD» позволяет получить экономический эффект, который составляет до 15% стоимости расходуемого материала, а также сокращение сроков проектирования комплекта технологической документации в 10—20 раз.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ

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

2. Исследован а многовариантность подходов к решению задач раскроя оптимизационными, условно-оптимизационными и эвристическими методами. Разработана классификация алгоритмов решения задач раскроя; определена область применения различных алгоритмов.

3. Разработан н исследован метод предоптимизационного анализа задач раскроя:

— определены параметры, которые характеризуют ожидаемый остаток и эффективно влияют на выбор подходящего алгоритма;

— разработана методика определения соответствия оценки ожидаемого остатка различным группам алгоритмов.

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

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

6. Создано программное обеспечение которое может быть реализовано как автономно, так и в составе программного комплекса «CUT—CAD», служащего для решения задач линейного, прямоугольного и фигурного раскроя. Программное обеспечение используется в процессе технологической подготовки раскройно-заготовптелнього производства и в учебном процессе.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Мухачева Э. А., Бабкова Е. В., Габитов В. А. Программно-технические средства формирования алгоритмов планирования основного производства //VII научно-техннче-ском семинар: Математическое обеспечение систем с машинной графикой.: Тез. докл.— Тюмень, 1990.—С. 30.

2. Бабкова Е. В., Бабков О. К., Габитов В. А. Разработка АСТПП заготовительного производства на основе СУБД //Научно-техническая конференция: Разработка и внедрение САПР и АСТПП в машиностроении.: Тез. докл.— Ижевск, 1990,— С. 186—188.

3. Бабкова Е. В., Габитов В. А. Автоматизированная система планирования заготовительного производства на основе базы знаний в САПР «Раскрой». VIII научно-технический семинар: Математическое обеспечение систем с машинной графикой. Тез. докл.— Ижевск, 1992 г.—С. 15.

4. Ибатуллина С. М., Иванова Л. LLL, Габитов В. А. Интеллектуальная поддержка учебных курсов и принятие решении в системах управления /Научно-техническая конференция «Актуальные проблемы авиастроения»: Тез. докл.— Уфа, 1992 г.— С. 83—84.

5. Разработка программного обеспечения банка данных цеха и проектирование автоматизированного рабочего места

руководителя службы. Этап 1. Организация банка данных цеха, сопровождение задач «Номенклатура», «Кладовые».: Отчет о НИР/УГАТУ; Руков. работы Мухачсва Э. Л.; № ГР 01920007257; Инв. № 02930002105, Уфа, 1992,—45 е.: ил. Отв. нсполн. Е. В. Бабкова.— Библиогр.: с. 45. (В. А. Габитов — раздел 6— С. 37—42).

6. Разработка программного обеспечения банка данных цеха и проектирование автоматизированного рабочего места руководителя службы. Этап 2. Программы сопровождения меню автоматизированного рабочего места руководителя службы.: Отчет о НИР/УГАТУ; Руков. работы Мухачева Э. Д.; № ГР 01920007257; Инв. № 02940000922, Уфа," 1993— 103 е.: ил. Отв. исполн. Е. В. Бабкова.— Библиогр.: с. 102— 103. (В. А. Габитов — раздел 5.— С. 76—92).

7. Габитов В. А., Мухачева Э. А., Розанова Л. Ф. Пред-оптимизационный анализ задачи планирования рационального раскроя. УГАТУ. Уфа. 1994. 22 е., пл. Библиогр. 8 назв.— 'Рук. Деп. в ВИНИТИ/. 02.03.94, № 513-В94.

8. Габитов В. А., Иванова Л. Ш. Система предпроектного исследования задач раскроя. УГАТУ Уфа. 1994. 7 е., ил. Библиогр. 4 назв.— /Рук. Деп. в ВИНИТИ/. 08.04.94, № 854-В94.