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

г"*

Государственный комитет Российской Федерации по высшему образованию Ыосковокий государственный технологический университет ОТАНКИН

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

УДК 658.52. 011. 56.012. а 001. 57(043.3)

Горшков Авенир Федорович

1ЮШПЕНИЕ эффективности ИНТЕГРИРОВАННОГО АВТОМАТИЗИРОВАННОГО УПРАВЛЕНИЯ ПРОИЗВОДСТВО!! НА ОСНОВЕ МЕТОДА ЗАМЕЩЕНИЯ

Специальность: 05.13.07 - Автоматизация технологических процессов и производств

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

Мооква - 1995

Работа выполнена в Центральном научно-исследовательском технологическом институте Министерства Оборонной Промышленности и на кафэдре "Автоматизации технологических процессов" Московского Государственного Технологического Университета "СТАНКИН" •

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

профессор Дегтярев Ю. И.

I - доктор технических наук ! профессор Оултан-Заде ЕМ.

; • - доктор технических наук ' доцент Фролов Е. Б.

Ведущее предприятие - еавод имени Владимира Ильича

Защита состоитоя| . 23 февраля 1995 г. в ' час, на заседании специализированного Совета Д 063. 42.02 в Шсковокого Государственного Технологического Университета . "СТАНКИН". | :

Отвывы (в дв^х экземплярах, еаверенных печатью учреждения) просим направлять по адресу: 103055, Москва, • ! '- ' Вадковский пер., Ва. !

Ученый оовет ЫГТУ "СТАНКИН" Д 063. 42. 02. '

С диссертацией в форме научного доклада «окно ознакомиться в библиотек^ ЫГТУ "СТАНКИН".. ■ '

Диссертация в форма научного доклада - .' ■

разослана "20 " АХ^О^-А, 1995 г.

Ученый секретарь специализированного Совета к.т.н., доцент р'Д. Волкова

/

' /

(ДОЛЯ Х'.РАКТЕРПСТШ РАБОТЫ

/КТУАЛЫЮСТЬ РАГОТН. В свявн с переходом экономики Россия ил рмю'шыэ огноязния мешкает необходимость Со.тоо бмстрогс» и адекватного реагирования предприятий на иэжженио спроса на рынке. Это новое дм нодзэго мшяиоотроения экономическое чество требует ссодяния итерированного автоматизированного управления проиаводсаленнуми сиотешии (ИАУГО) на бане комплексной автоматизация процесс оз создания тле ям, кйчжчя с;-ого проектирования до ив готов дзж'д. При этом вовникапт нроб-ходиаосгь вшшюшя ааркзтингойих исследований аку на' ахолг-лрсегаированяя нового ивцэжя а сдеяэния ва зфйектигкоотыо отдельных гидов реклам на различных сегментах ршта в щю-цосое реализации новых ивделий. Хотя многие вновь произноди-шз ив до лет, отвечают самым дестким требованиям, предъявляемым потребителем, нередко многие ив них не выдерживает конкуренции с импортными дажэ на внутреннем рынке.

Анализ совокупности задай» решаемых . в рамках ИАУГО, включающего этапы маркетинга, проектирования изделий, их изготовления/ ¡правления оашм процессом производства и т.д., показал отоутотвие единого подхода (единого метода) при решении, показал приближенность решения некоторых вадач, эмпиризм ив-ва трудностей формализации, вынуждающий разрабатывать многочисленные эвриотические методы и. приемы и, нас эледбтвие, малая эффективность решения. Отовда возникает проблема формирования адекватных моделей в рамках аадач ЙА-ГОЗ и единого метода их решения, . что позволит .

- экономить интеллектуальные ресурсы при постановке и ¡юрмалявации еадач ИАУПО; •

- в определенной степени унифицировать программное обвс-тчение, функционирующее в решках ИАУШ.

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

- г -

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

ЦЕЛЬ РАБОТЫ состоит в повышении эффективности подготовки и управления производством на основе разработки теоретических основ методического обеспечения, компьютерная реализация которого позволяет расширить класс задач, решаемых в рамках интегрированного автоматизированного управления производственными системами, что повывает рентабельность производства и, в конечной счете, способствует ускоренному продвижению товара на рынок и повышению конкурентоспособности выпускаемых ивделий.

ЦЕЛ ОДЫ ИССЛЕДОВАНИЯ базировались на результатах математической теории графов, численных методов, методов системного анализа и исследования операций, методов теории расписаний и логических методов синтеза технологических структур производственных систем.

НАУЧНАЯ НОВИЗНА работы заключается в открытии нового перспективного научного направления в области автоматизации технологических процессов и производств в машиностроении, »включающееся в:

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

- разработке так нааывавмых векторов топологии и матрицы доцуотхмых отепеней, являювдхся математическими ограниченном)! при постановке и реяошш прикладных вадач автоматизации геяюлйгичеоки* лроцвооов и производств;

г оовдадн* алгоритмических методов защиты от некоррект-8ое*я ьходида, дьяных. оОеспечй^&хздкх аффективное функциони-

рование компьютеризированного интегрированного производства

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ работы заключается в создании алгоритмического и программного обеспечения, что повволило ва счет более рациональной вагрувки оборудования и оптимизации управления материальными потоками в условиях мелкосерийных и единичных производств увеличить фондоотдачу технологического и транспортного оборудования в среднем на 30-40Х и уменьшить объем незавершенного производства в 2-3 раза. . /

Разработанные в ходе выполнения научно-исследовательр$<их работ в ЦНИТИ МОП метод замещений, методики, алгоритмы jk программы испольбованы для проведения дальнейших исследований и и их реализации на заводах отрасли. Разработанные в диссертации алгоритмы решения прикладных вадач интегрированного автоматизированного управления проивводственйыми системами внедрены на ааводах машиностроительного профиля.'

Программная система для решения оптимизационных и комбинаторных вадач методом вамещэний испольвуется в учебном процессе при выполнении лабораторных работ и практических занятий по курсам "Системный анализ и исследование операций", "Планирование и оперативное управление" в ЫГГУ "СТАНКИН" и по курсам "Математические методы исследования операций" и "Аналив и проектирование систем менеджмента" в Академии На-хдного Хэвяйотва им. Г. R Плеханова.

АПРОБАЦИЯ РАБОТЫ. Основные ревультаты диссертационной >аботы докладывалиоь и обсуждались на научно-технических конференциях, совещаниях, школах-семинарах, кафедрах, в том шоле:

!-е Шесошюв совещание "Методы и программы решения опти-мвационных задач на графах (Новосибирск, 1982), Воеоохвный импоэиум по теории графов (Одесса, 1991), Постоянно дебетующий семинар при кафедре дискретной математики ЫЙИТа (Мос-ва 1984), Вычислительный центр Академии Наук ООСР (Москва, 985 и 1986), Московский Государственный Университет мы. К. R , V эмоносова механико-математический факультет (Москва. 10S6)," •» :ютоянно действующий семинар в Центральном акоиомико-шгег,

маякчаскоа шютмтуте АН ССОР (Москва, 19S?), Институт Техни-«й>о;юй Кивернодош АН БСОР (Шнек, 1089), Научно-иселадовэ-тельеинй ииститут системных исследований АН СССР (Мэскъа, Ш6Э, Кафедра технической кибернетики Харьковского политех-иичвокого института (Харьков, 1989), Международные конференции "Актуальные проблемы фундаментальных наук" (Изсква, 1691 в 1994. За полученный фундаментальный ревудьтат в области дискретной математики работа била удостоина специального международного диплома), Научная сессия Отделения информатики и вычислительной техники РАН "Проблемы математического моделирования" (Шсшза, 1992), Школа-семинар при кафедре "Прикладная математика" Московского Государственного Технического университета им. Баумана (ЬЬсква, 1994), Постоянно действующий семинар "Проблемы искусственного интеллекта" при Московском Государственном Университете им. U. В. Ломоносова, механико-математический ¡факультет (Москва, 1994).

ПУБЛИКАЦИИ. . По материалам исследования опубликовано 28 работ к получено 7 авторских свидетельств на ивобретения.

Введение

- 5 -

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

Допросам создания а. повышения эффективности ввтонатазированншс. ситем управления производством (АСУП) и кх подсистем,-а таюювап-росан оперативного планирования и: управления в:, интегрированных мв-шиностроительнш; производствах посвяйевы работы мнопа оубчестввя-; них ученых: П.Н.БелянинвВ.Н.Васильева, А.М.йшлюна,. Г.К.Горааского, В.Ф.Горнзвг, Ю.'и. Дегтярева, В. В.Емельянова, К.М.Капустина, И.М.Колеоова.М Л\Косова» Л.Еклй®--яекого, В.В.Лшшевв.В.Г.Логатева, % И.М.Макарова,. О.П.1йгфофвнова, В„Г.Митрофанова, В.В.Павлова» В.А.Патрова, ¿.¿.Первозванного-, Е.В. Овсянникова, Ю.И.Сололшфва,: В^

Тимковского, Э.А.^тьзшза, Е.В.^лою,. В.Д: Цюткова, В.Е.Целя-вдва, А.Д.Чудаковаидругиг. ,':' '.

Авалю» рассмотренных работ юкавал г .'что при соадании методолог гичзских основ- построениа подсистем АСУП этими учеными истюяьаова-лись, как правгло^класаичесюге шфсш!8пр<5ироваиные. математигвс- •■ кие гатодарешегаигзадачиз такихкяассов кахлинвЙжй.прохз^^ рование* велшневноесросграш1фование, дискретное програ«*фоваяив и др. Поскольку' производственные процессы в машинюстроеиш аооят, как правило, дискретны* характер, то наибольшее применение в-';мих работах наили метода целочисленного программирования с булмици переменннми. Вполае естеоотвенно, чтояаиболвешфакоа щяммютш а научвнх работшс исследователей находаг такие/ эетвей и границ, метод датаячвохого прогришшроваац» миад* уряя графов. Перечисленные метода исследования кнаензи научных в прикладах вадм АСЯШ, являясь мйода^

тщтмтого перебора, Maso отлвчввгся от штодов подного перебора. Кроме того, соврвкИЕНш проблемы управления производством ста- . вят трех «аолвдовагелэи юш еадача, которые являются либо саоша тртдоекхшн для трададаоших ыатвиатаческих методов, либо в щезцвиэ w когут быть розеш послэдааа. ato объясняется тем, что соцт&тио проблма автоматизации технологических процессов в прссз©одств требуют форкашшцка возншсакдш в производстве огра-шчешй, ш реалазуеьых юасснчасюзд катодаин. По этим причинам шош» учэшв раерабатыаагэт рврасткчэскве и прибдзаЕвнныв алгорагг-toi, »«здаш вв которых пркшша лезь к узкому кругу задач, йакото-раа дегорэтш, являясь ушталышнд, прекенклы только к отдельно взятов аадачв. Эта обстоятельства требуют повшэншх интеллектуальных затрат как от сеаогр исследователя, так и от програкааста, пра разработка шялтвща программ йнтегрнрованного автоматизированного управления производственншш снстемама (йаУПО). Пра бо-льша обьвешх исходных данных, вводимых оператором ЭВМ, существует проблема всздти от опвбок, поэтому весьма актуальной является задача &лгоратшчаской проверка на корректность исходной инфоркавди.

Кьвсшдашэ, проблеш ЙШЮ потребовали постановки новш еадач упраздэкзя. разработки вогого иатеыатического метода нх ре-csisa, в scssa вовах катештачасках способов задания ограничений, гяшщхпшсзото а цровэводствэшхого характера.

1. Кэкотораэ пробта а еадача ШЦО

/ Сзрааад цгзвккгсроатбдыая: нрэдпрштей в производств к caapoeam» 9 усжтоях ривочках отраве«®® тробует нового подхода к ездою» цтрамыаст s в^оршиштап вотокоз, iщ&ущррвщ. «es

а сфэрэ производства, таи я в с&эрэ закупок и продел, т.в, ринка. На рас. 1 показано укруппенпол схема циркуляции упомянутых шко потоков, гдэ икформащюншэ потока показаны тонгаш сярелкшга, а ма-твраальшв ~ ааатрявэвшшшгз. В пв^ормационном тптурз "пронзвод-с7Ёо~рнюо!(-ШШ)" вщяэгт щушсцпональныэ бшаг, характерные дня ярвдпряйтай, раб6теп532 ;а усговяях рыночной экоиожка. К тати ; Ьткен отоосятсл: "МАРКЕТШГ" й "ШШ}'Ап . ОуншгонаябшЗ- блок "1Ш110" яшкстся грэдяцчоншг,!.;' Кспдрму (Т.тшадаоналы!о;.<у/*Охо::у соот-ВЭТСГОУЕ? СВОЗ ЕОДСЕСТеКУ 1ШЛ10, ОСПОШЩв ИЗ КОТОраХ ' ПОКЙЗШ1 на роюИ. Нзгэ для гфзткосга слово "подспсте^а" пс.-экопо сяовоа "сис-

а«СГОКА

МАРКЕТИНГ

/|\

ПРОИЗВОДСТВО Р иК 0 к НА У ПС

У'

V.

РШША-

АСЙИ

шга®

САПР (5);

Г /СТПП®

¿СОУП@

АТСС.<§)

АСМО ф

ОАН . ©

ЙЗС.1,

тока». ЙорядкогкЭ пойэр- шдастс»Д1 шгссзея на рзсувко в врусочг&з, 1 - АСКЛ - явтсжатвзяроЕйшгл: снстегэ- поучпгг ссолзАогатЕЙ» • 2. САИН1 - (псглма автеглтпжфоватого кяркэгепга» рмш л пяйЕроэшта. .< '

3. САП? - с.;стст-'э (итжатпстроззш&го проаятароЕсам. 'Г;

/1

■'-'s'/í' / v'S:;'8} ■'-. .:'■.•/.......

4. АСТПП - автоматизированная система технологической подготовка прсшаводства.

6. АООУП - автоматизированная система оперативного управления производством. - .

6. АТОС - автоматизированная транспортно-складская система.

7. АСИО ~ автоматизированная система инструментального обеспечения. ' А .

8. САК - система автоматизированного контроля.

.Математическое обеспечение перечисленных подсистем ИАУПС в

своем составе юнеет набор'' задач, решение которых позволяет повысить эффективность управления производством. Однако современное высокотехнологичное производство, а также возможные изменения спроса на рынке;выпускаемого предприятием товара, требуют создания более точнш: математических моделей, отвечающих требованиям гибкости производства и маркетинга. При атом расход машинного времени наременивотдельных задач новыми алгоритмами должен быть приемлемым для необходимого времени реакции конкретной подсистемы ИАУПС.

Рассмотрим перечень некоторых задач, входящих в состав подсистем КАУПС, которые являются предметом рассмотрения в данной рабрте в качестве примаров задач на графах со сложной топологией и требующих формализации возникающих ограничений. Задачи имеют циф-робукввииую нумерацию, где цифра соответствует номеру подсистемы,. а бую* - порядковому индексу задачи внутри подситежк

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

.8-* рчстг щашюлотавааоШ прогртш щя постоянном «тате рЯйЯОЧМИ ММОЧЦНС" J3p0$90(Vft«

2ч5 - расчет производственной программа при переменном штате работах ведущих профессий.

2-в - стандартизация и модификация изделий. •

2-г ~ выбор поставщиков сырья, материалов и кошлектущих.

3-а - генерация структура размерных цепей : с ограничением на сумму допусков по каидой из ее ветвей. • ^

4-а - формирование технологических операций. /

- балансировка технологических марврутов с цеЛью равномерной загрузки станочного оборудования. .

4-в - закрепление технологических операций за станками.

4~г - опткшзация последовательности технологических переходов при токарной обработке.

4-д - оптимизация карарута даремээдния сверлильного, узла при обработке деталей типа "корпус" шш "плата" < .,-..'

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

- маншазация времени сборки изделия. ,

б-а - составление расписания работы станочного оборудования.

Б-б - оптимизация раскроя прутков,

б-в - рациональное• перекреаление операторов-станочников по станочному оборудованию при возникновении возмупдащих юздэйстажЗ в ходе производства.

5-в - баленстфоша производственных мощностей.

6-а - расчет очередности выполнения заявок, поступающих с •рабочих мэст.

7-а - шнимиэацкл числа магазиш-кошлектов.

8-а - еатсаетгйЦЕЯ рэбочэго трзруте иэр^^ашя кпетргкзлшой хтеовки ИШ.

2. Новый класс оптимизационных задач автоматизации технологических процессов и производств

Выше был представлен перечень некоторых задач, входящих в состав подсистем ИАУПС. ,Назовем перечисленные задачи задачами-представителями, так как их перечень никогда не может быть полным. Для задач со взвешенными;ребрами (дугами) целевая функция имеет следующий вид -.'.'/ , : :

п п • |

Е Е 0..Х - еЛг. (1)

Для задач со взвешенными ребрами (дугами) и вершинами целевая функция принимает вид ' | ■ • ;

■ } : ' • ■:''■. ' ■

£ Ёс + Е Ь,у. - тШ. (2)

Некоторые задачи-представители для формализованной математической постановки требуют введения ограничений на топологию подграфа 0'{у,Е'}.' В 1975. Года, английский математик Н.Кристофидес сформулировал одно ограничение на задачу с целевой функцией <1) , назвав ее "общей Задачей построения остобного подграфа с предписанными степенями". Для формализованного описания ограничений в задаче Кристофидесавведем вектор закрепленных степеней:

г - (о1,ог. ...ог...оп); (3)

гдэ - степень вершины номер I.

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

(5)

где векторы допустимых степеней, векторы

запрещенных степеней, В - вектор подвижных степеней.

Для моделирования топологически сложных структур на графах ограничения задаем матрицей допустимых степеней (ЦЦО):

аог аог. • у- - ••• аоп V " ач а13 ••' • •• ......а<п ' (7)

ап+» , I ап+(,2 ап+Г ,1 "• ап+1,п

где а^;- элемент ВДС, находящийся в (-ой строке и /-ом столбце.

Ограничения (3)-(7) позволит задавать ограничения не только на аставныв подграфы, как ето сформулировано, в задача Кристофиде-са, но и на графы, содержащие изолщ»ваннне вершины.

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

3. Новый класс комбинаторных задач автоматизации технологических процессов и производств

Введем следуидав формы

f ¿. —

Ооновдае постановки оптимизационных задач

TaöAuuß 1.

Наименование задачи Векторы топологии Авторы постановки Страна Год

Задача о коммивояжере (3) или (6) Гильморе, Гомори ; США 1964

Открытая задача коммивояжера (4) или (6) ДеоДакими США 1965

Открытая задача коммивояжера с отмеченными концевыми вершинами ■ i 43) Део.Хакиш США 1966

Задача о назначениях 1 (3) или (6) Гловер США 1967

Задача Кристофвдеса Кристофидес Англия 1976

Новый класс задач (3) или (6) Горшков - СССР 1985

rt п ,

Е (8)

t=U=i ^

n n

E £ x,. -> min, (9)

1*1 %J

где j ( 10,1 У, и - число ребер в подграфе (G'(V.E').

Новый класс комбинаторных задач ИАУПС формализуется с использованием ограничений на топологию искомого подграфа G'(V,E') (3)-(7).

Рзоомотраы место классических задач и нового класса задач, за-дшмча фор»цш (8) в <9), которые имеют прикладное значение в интегрированных автоматизированных системах управления производст-ОШЯ4,

Вош кто мхачв, определяемые формой (8), относятся к классу комбшаторша авдач. в формой (9) - к классу коыбинаторао-екст-

. _'. ' ' " - ' . - 13 — .

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

Наиболее.применимые комбинаторные задачи сведены в таблицу 2.

Постановка;, комбинаторных задач

Таблица 2.

L

Наименование задачи ' Вектора , ТОПОЛОГИЙ Авторы постановки Стран/ Год

Гамильтонов . цикл (4) ИЛИ (6) • Гамильтон, Роберте Флорес АНГЛИЯ США 1859 1966

Гамильтонов цикл с отмеченными концевыми вершина?® . (3) Роберте , ' Фюрес . . США' 1966

Задача о паросоче-тании (3)или^4)или '■ Еймоццс " ^.CUlA „■ ■1965

Новый класс 'комбинаторных задач (3) - (7) Горшков Россия 1994

4. Классификация задач интегрированного' автоматизированного управления производственными системами".

Поскольку метод замещений позволяет решать широкий круг задач ИЩЮ па графах, то для целенаправленного применения алгоритмов и программ, базирующихся на методе замещений, представляется цэлэсо-обрвзннм классифицировать как решенные так и вновь возннкапциэ задачи. В основе классификатора задач ИАУСП должны лежать теорэтако-графовнз признаки. Какдому элементу клпссн£эдкамра должэл соответствовать свой набор программна модулей. Для гех задач ШЖ.С, но-

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

I. Buöu зсьЭач: 1. Оптимизационные. 2. Комбинаторные.

II. Типы графов: 1. Неориентированные. 2. Ориентированные. 3. Двудольные. 4. Многодольные.

III. Ограничения (на степами вершин): 1. Вектор закрепленных степеней. 2. Вектор допустимых степеней. 3. Вектор запрещенных степеней. 4. Вектор подвижных степеней. 5. Матрица допустимых степеней.

К классу оптимизационных, задач относятся падачи ИАУПС со взвешенными ребрами (дугами) и (или) вершинами. Исходный граф в таких задачах задается матрице^ весов и (или) вектором весов вершин. К

классу комбинаторных заддч относятся такие задачи ИАУПС, у которых

i

исходный граф задан матрйцей -смежности. Следует заметить при »том, что оптимизационные задали на графах тоте имеют комбинаторный характер. Используя нумерацию классификатора можно любой задаче ИАУПС,. поставленной в терминах теории графов, присвоить классификационный код. Пример: оптимизационная задача на двудольном графе с ограничениями по первой доле графа, заданными вектором закрепленных степеней;- и по ьторой доле графа - вектором подвижных степеней, имеет классификационный код 1:1.11:3.111:1,4.

, Такой подход к классификации задач ИАУПС имеет не только теоретическое значение, но и практический смысл, так как позволяет по классификационному коду достаточно быстро сгенерировать компьютерную програ*в<у из готовых программных- модулей для определенного подкласса задач или кокхретной задачи.

5. Принцип парного реберного замещения

Вводом адздевдие обозначения: G(V,E) - исходный граф, содержащий шюж®е?во вершин 7 и множество ребер Е; (Р(У,ТР) - начальный подграф» содаракщай множество ребер Е°; G'(7,E') - искомый подграф, еодаржадй мгахвство ребер Е'; GP(V,EP) - промвжуточйый подграф; в -чаш» pe.Stp вшэдого подграфа; п - число вэршш графа. При этом ¡йв!®*!®!®®)»!^! и п*|?|, а степени вершин дуй множества 7 относитедаш G4f,E') задана.

Определение U Яара. сосисдаря из эах$шелого (уда-ляелого) г^Е"« (дово&ля&хого) rf$E\1?ребер , называ-

ется парой реСврносо гш^хия. :

Обозначим огоращш рзбвряого замещения символом На. Кзпрямэр: £ Re J- ребро, t asvsaa&atea та ребро J; 6 Ее 10 - рэбш N б эамэяа-ется на ребро,Я Ш; Л Ш В ~ tammctm ыятнтъв А зитхчътся ка paBHCWÄKse ШШОЛШ ЬЖШЮШ В.

Доказада отцрщ« теорема, фармуяирувдаа праздш тарного ра-бершго ашдаш.

Теорема I. %еж& граф G(V,E) тозердаа möspаф ß*(t,B*}r а ровер Е пртовальна ¡шдтто т т&лмохвспва Б? и

если w л&ляетел G'fV.S'i. ш гмя граДг GfV\S,J ct/-

t} гъзри sa*mnßtw& (ritrj} msзя, чйо г, Кэ rf .при-

ЭоЗш к ¡¡зляншв» яшолдата

$) зш <5Ы «Умк коряеа, еоЭвравдив ю ймк чад t^Hef! щ» scMßrt^iiSi, гдавдркй nptt6oÖie» к am&<am& пЫЗграфз. G'ff.B").

feoye.m 3 1Ш1 не только фувд8М*вт8льша х&ржктвр, ко. и дзй* 53Щ К формЗфОВЗШГО ИОЙ9ЛЭЙ КЗ ГрафвХ , 0055СМ>ШИХ «ВТ8р£^?«фС-

вать различные технологические, производственный и другие процесса в терминах теории графов. Так, ¡гг^шзр, для задачи "Генерация структуры размерных цепей по . * . : ■ 4. ¡-¡метрам" число размерных стрелок, отходящих от плоскости , относительно которой оп-

ределятся размер до другой плоскости моделируется степенью вершины. Номер плоскости детали соответствует номеру моделирующей ее вершины. Одно ребро моделирует конкретные размерные стрелки, а пара замещений - замену/одни^ размерных стрелок на другие и т.п.

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

б. Применимость реберных замещений в классе ■ оптимизационных задач ИАУПС

Класс задач ИАУПС, определяемый функционалами (1) и (2), относится к МР-полным задачам. Поэтому при разработке нового математического метода"необходимо было объединить два взаимно противоречивых требования: абсолютная точность при минимально возможной трудоемкости . Компромисс между этими требованиями достигнут путем создания вычислительной схемы, сводящейся к следующим построениям при рвшвшп» оптимизационных задач.

I. Мнокество ребер упорядочиваатои по возрастанию их весов с^ (для аад«ч минимизации).

II, Множество ребер Б разделяется на два подмножества Е° и

ß\B°. Кавдое ребро г € является кандидатом на удаление, а ребро г € Е\Е° - кандидатом на добавление.

III. Построение дерева решений или точнее дерева замощений (ДЗ) начинается с корневого узла. Если топология Т,Е°) удовлетворяет заданным ограничениям из набора (3)-(7), то решений задачи получено. ■ /

IV. В противном случав строится ДЗ, в каждом узле/ которого конструируется некий подграф ^(У.тР), который называемся тгронеау-точнкм. Узлы-братья, находящиеся на одном ярусе. ДЗ, упорядочиваются по возрастании разности весов пары замещений. Это позволяет отсекать узлы-братья, находящиеся справа, в том случае, если левый узел-брат достиг требуемой топологии. '

V. Отсечете бесперспективных ветвей ДЗ вглубь выполняется по следующим критериям: а) по превшогою верхней граница; б) по необратимому нарушению топологии подграфа,(Р(7,5*7; в) по прогнозному значению веса промеауточного подграфа; г) по достав нив запрещениях значений тех величин, которые заданы дополнительными ограничениями по условии задачи.

VI. Возврат на верхний ярус ДВ выполняется по критерию а). Переход к узлу-брату, находящемуся справа, выполняется по критериям 0), в) иг).

Описанная вычислительная схеме отностнтся к тому разделу метода замещений, который занимается формированием алгоритмов ревения оптиыизащюшшх задач на графах с топологически слохпнмя структурами искомых подграфов. В этой класса задач алгоритмы ®»пт дело с графами 0(7,В) со взвешенными ребрами (1), а тага» со взвввепннмя вершиншп а ребрами (2). При моделировании на Грефах весом ребра задается некоторый производственный ресурс (sporn, расстояние, за-

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

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

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

Основные метода решения оптимизационных задач на графах : '..;/ Таблищ 3.

■• ' ■ V | ; - ' ' ■_■ ■_' ' ' ;

Ы е то д Авторы Страна Год

Метод ветвей и границ Дшишческов ирограм-мированне Мальгранж, Фор Литл, Мурти Суини, Кэрол Хелд.Карп Бедлман США США США США : США 1961 1963 1963 1970 1952

Венгерок«* метод Егервари Кун Венгрия Венгрия 1953 1955

Метод вашцаша Гораков СССР 1965

7. Щямвшмооть реберных замещений в классе жачйюаторш* задач КШС

Апжятоо «моем аадач (1)1 (2) классы задач (8) а (9) Ш-

ПС тага» является НР-полнымн. При этом необходимо заметить, что такие математические метод» как динамическое программирование, метод ветвей и границ я некоторые другие классические метода не могут быть приманены в классе задач (8) и (9), поскольку они выро-адаются в простой перебор'" из-за отсутствия, весов ребер в исследуе-ышс графах. БенгерскиЙ метод решает ограниченное число кдабилатор-пах задач на графах. . , /

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

I. Из шозества ребер.Б исходного графа ССУ.г^ формируется подграф 0°f7,B°), каеиций минимальнув начальпую деформацию по отношение к задагазкм ограничениям из набора (3)~(7)< Начальная деформация определяется алэлущэй метрикой:. /

р° » Е |ÖI- в°|, (10)

гда ÖJ - заданная (предписанная) степень t-ой верешны; б" - значение степени t-оЗ вершин, подученное в корневом узле ДЗ.

II. Ыногество ребер Б разделяется на два тодмногэства В0 и BVB°. Каздое рэбро r(e является кандидатом на удаление, а ребро r^i - кандидатом на добавление.

III. Если р°=0, то искомый подграф найден.

П. В противном случае строится ДЗ, в каадом узле которого конструируется некий подграф &'(У.Р*). Еслв этот подграф удовлетворяет заданным ограничениям, то он является подграфом G'(V,B') я реаение комбинаторной задачи подучено.

V. Иначе необходимо выполнить отсечение бесперспективной ветви ДЗ по одному из следующих критериев:

а) по необратимому нарушению топологии подграфа

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

Описанная вычислительная схема относится к разделу метода замещений, который занимается формированием алгоритмов решения комбинаторных задач на графах с топологически сложными структурами подграфов С'(V,ЯВ этом классе-задач алгоритмы имеют дело с графами, задаваемыми матрицами смежности. Элемент матрицы смежности М, является элементом модели некоторой производственной системы или процесса. Например: элемент размерной цепи иди наличие сопряжения между, двумя деталями при сборке; номер наименования инструмента, который может быть использован для обработки конкретной летали и т.а;

Поскольку исследуемый производственный процесс в задачах {8). (9) задан матрицей смежности, то такие классические методы как метод ветвей и границ, метод динамического программирования и др. становятся не эффективными. Это объясняется тем, что принцип отсечения бесперспективных ветвей и принцип оптимальности Беллмана не "работают" при ревекии комбинаторных задач. В отличие от классических методов метод замещений, позволет отслеживать текущее состоя-ш» степеней вершга в подграфе Это новое качество, при-

суще вычислительной схеме замещений, позволило существенно расширит1» кмюс реааемых комбинаторных аадач(см.табл.2). Основные метода реяенм комбинаторных аадач представлены таблицей 4.

- 21 -

Основные метода решения комбинаторных задач на графах

Таблица 4.

Метод (алгоритм, система) Авторы Страна Год

Венгерский метод Егервари Кун Венгрия Венгрия^ / СССР / /'1953 1955

Алгоритм Леонтьева (задача раскраски верзшн) Леонтьев 1989

Алгоритм Гордеева (задача о ' вершинном покрытии) Гордеев СССР 1989

Информационная система ШСЕ Лорьер Франция 1974

Метод замещений Горшков СССР 1965

8. Применимость вершинных замещений в классе задач ИАУПС

Некоторые задачи ИАУПО математически сводятся к так называемым задачам о К-веропшных подграфах. Примерами таких задач могут быть: задача выявления достаточности комплекта инструментов для обработки заданного набора наименований деталей, задача выявления достаточности набора свободного станочного оборудования для обработки группы деталей и т.й. Такого рода задачи сводятся к решения задачи о вервштом покрытии, домшшрукцем многоствэ, звездном подграфа и т.д. В общем виде этот класс задач формулируется следущим образом. Заданы граф G(7,E) и положительное целое число Я<|У|. Существует ли подмнояество V'cV такое, что jУ'|(\V'\<sJ[), а подграф G'(V',Е') обладает свойством П? Свойство П определяется нябо-рои ограничений, исходя из технологического смысла задачи.

Для решения данного класса задач ИАУПО используется вачисда-

тельная схема вершинных замещений, которая сводится к следующим построениям. ' >

I. Вершины исходного графа 0(7,В) взвешиваются значениями их степеней р{, 1*1,2,...,п, а также величинами а1=т1п{р<), где а{ и Ач- соответственно минимальная и максимальная отвпень вершины и смежной вершине и(. Для некоторых задач целесообразно введение дополнительного параметра р, который характеризует необходимый, но не достаточный признак принадлежности вершины У искомому подграфу в'(7',Е'). Аналогично параметру р вводится необходимый и достаточный признак Р. Данные параметры являются булевыми и формируются исходя из технологического смысла применительно к свойству П. 1 .

II; божество (список) вершин последовательно упорядочивается по вычисленным параметра»^ и весам.

III. Множество вершад разделяется на два подмножества: первое подмножество 7°, содержащее вершин верхней части списка, и второе подмножество У\У°, содержащее п-Е=|| вершин нижней части списка.

IV. Строится такое дерево решений, в каждом узле которого конструируется некоторый подграф, содержащий Х=|У°| варшиЯ, который является начальным подграфом. Вели начальный подграф не обладает свойством П, то строится дерево решений путем замещения вершины и{( 7° ва верюиу и,с?\У° в каждомегоузле. При етом вершины и< ж и, могут обладать признаками р*1, а вершина, имеющая признак

до доджи* вмещаться на любую другую вершину.

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

• '••''. ' - 23 -

О п р е д в л в н и в 2. йара, сосяшаря иа эалечаалэО ij/ба-.-яяеиюй!' и валеирачеа (добавляемой) вершин и полученная в

l-ол увлв ft-во яруса ДЗ,, называется парой вершинных всиечений.

Этапы II и III вычислительной схема имеют дало о формированием начального подграфа, когагмй в некоторых случаях может явиться ис-комымподграфом, обладающим свойством П. Ийогда отсутствие ^бвойст-ва Й становятся очввидшв» на этих «а этапах решения. Ложность этапов рейения задач о i-вергаганых подграфах показана/на рис.2. Принадлежность упомянутых выие этапов решения задачи it классу по-линомиааьйо:решаема задач; определена следующей,теоремой.

.Т е о р & м а II. Эойана отыскания начального К-вершинноео подграфа на грзфз G(7,S} принадлежит, к классу Р.

Формирование подграфе Gr°

Обладает ли свойством И подграф (Р ?

Да Нвизвйотйо Нет

Формирование подграфа G' с помощью МВЭ

ЯТ-оложвая

Р-слохная

Имеется ли подграф С со свойством П в графе (J ?

Да Нэт

> Класо Р

> Класо KP

Рис.2.

- 24 -

9. Сложность алгоритмов метода замещений при решении задач ИАЭТЮ и процедуры, повышающие скорость сходимости вычислительною процесса

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

Поскольку задачи (8)-(9) сводимы к задаче отыскания гамильто-нова цикла ,(для этого достаточно в векторе (3) все компоненты принять равными 2, матрицу весов ребер заполнить единицами, и принять v=1), то мы вынуждены признать,что задачи управления интегрированным машиностроительным производством, определяемые целевыми функциями (1 )~(2) и формами (8)-(9) относятся к классу №-полных задач. Это утверждение является'тем'более справедливым поскольку принадлежность хотя бы одной оптимизационной или комбинаторной задачи ИАУГО к классу Р, не доказана. С учетом изложенного при разработке алгоритмов, реализующих метод замещений, особое внимание уделялось скорости сходимости вычислительного процесса.

Деформация начальноео подграфа. Характерной особенностью метода замещений по сравнению с методом ветвей и границ является то, что высота дерева замещений (число ярусов) не зависит от числа ребер подграфе С ),а зависит от начальной деформации подграфа. Обоааачш* величину накэнення деформация при элементарном реберном вамевитаи Ар -р4-ри,,где р, и р(+> - величины деформации до и подо аамеденад. Рассмотрим следующееутверждение.

Утверждение^ При эалещенш peópa г еВ' на ребро • «БХЕ< величина изменения Оеформплии ложею, пршшжть одно из следующие значений Ар = -4, -2, О, 2, 4.

Процевурше прием ij-гсорения входиласт вычислительного процесса. Первый прием ускорения сходимости вытекает из утверждения i. йобходимо по возможноеги стремиться к максимальному значению Ар и тзбегать отрицательны* значений. Второй прием сводится/'к генерации ючального пощшфа с минимальной деформацией. Третий прием связан з уменьшением начальной деформации (релаксацией) подграфа С* (V.E'). ЮтвертнЙ прием выполняется путем прекращения вычислений по исчерпанию лимита времани,отводимого на реоениэ оптимизационной задачи.. [Три атом штат быть получено как точное,так а приближенное рвивниа, близкое к оптимальному. Пятый прием связан с порядком просмотра упорядоченных списков удаляемых и добавляемых ребер при генерации пар замещений на каждом ярусе ДЗ.Упорядоченный список из множества Е' просматривается снизу-вверх,а список из многоства ENE*- сверху-вниз.Это,в свои очередь позволяет существенно уменьшить число итераций при упорядочится пар замещений по возрастании разности их весов на каждом ярусе ДЗ.

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

10. Сравнительная оценка применимости различных иатематичзских методов в классе задач ИАУПС

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

| ц

в вовыхрааработках. Это обусловлено усложнением систем управления

в огреяачевными интеллектуальными ресурсами, обеспечнващюв сам

' г ' 4' 1

процесс проектирования.

- I

«равцувсшй математвк, специалист в области искусственного ин-теллехта, создатель ввВДмацкияоЖ системы ШОК Хан Как Лорьер сформулкровал принцип обработки »формации, по которому формулкро-вка задача долею быть шдзостю отделена от ее ревет». Црв таком подходе nporpuwnrt блок/ отвечаю»* да ревете задача, превращается в "черны! ядОс", а фограмооты разрабатывают только человеко-машинные интерфейсы ввода в вывода . црн этом роль униЦгкжри матвмвтиче<жв1«тодс®, л«С11ольззуемых для реввнияв классе задач ИЛЙХЗ, луцвствеШо возрастает; Исполъэовашиметода замещений дня решения оптмагвятшнныт в комбмватордых задач ШИС дает хорошую возможность для тахой уняфмкмщи, что наглядно подтверждается два-.

Рвс.3.

грмисЛ Венаа. псжаваяао* на рмс.З, где «сподьвовааи ащнр) «>" «рацеям: МЗ - катод swamnirt; МИГ - метод ветвей « греши ЯП • яшпмки црогрммромш; - веигарскжй метвд. ••..•••

: Рассмотрению ши вншмшшм сит яйвкмнид находить ра-

■В Éup. юиюго подграфа, лвбороинвотатьшщтитввв таково* I - _ - ¿ > г

гов шя<у(И11и подграфе, что определяется следупкгй тесремо®.

Теорема III. Хаиод еаиющвтЛ довивав' шл пятков чцело теов. ' /

Opa (жцтитап подграфа 0'(7tg') в доходом rpefs раёапва • м.. nraMetcn: в. шдоавом |м> ДВж щдЛ'рамй» реалн/щая метод ва-ищидий. «дает wvitbbic шудра «поящмяю ав 'aspe мовятора. в

V атом ojqrtM JÉ1P (Jttqo, щиммзди» рашми) деиМво тянггь тягаю

t __* " ' J; * "' " ' 1 '

' дт»> мин птит. цимкявшяд péoypooBit BBo6toffwgt ХК ' рямп

Г i *

динаре nui Mira шш i wire шить , повторное ремаяве. отц/титвив

'ь ' > * > **

Кмщнл) ПОДГрйфВ В рЮудТЮВ IHOjPyWlMJi цхнаювя мют сво-

t. í W / '

дате* к йшмрог спацюдшавг методам;

11. Вопроси аамгга от яосиити мхл KUfDO

Ко воем ксмооаантам КШС, реОотаирм в joпкщ рввдыюго

щхшводотва, >фадышдавто< вмосяшв T^ja6¡»BHH< до Яадяшмпии Ооо.....................".......................

беши ко касается вацктв iiiiiiiiit' м4цияи от яовашявя щж вв— dopt вв <г1авшатур> 8М» а нивщ mjuvran ияд мш промввэд- •

слвдуя^ю ■ твстраш» nosBOJümpa ваамять ШЯЮ о» wufluitKÉ ямищ!; вн^цмацна,

t • о р в и * IV. Вусвь 0(Т,Ш) - таршняироваюшй враф; mót-Оа алвлвпш s e |5|, тюралвяры п, ш и v исколоео поОерафа е*(Т,Я'}

и компоненты векторов(3), (4) и (5) связаны между собой следующими отношениями:

в) Оля любых графов

п и п п -п.

ЕХ>ЕА>ГФ»Е(р>Еа; (11)

<«> 1=1 С=| 1=)

в) Для графов без петель при 1 $ т < п(п-1)/2

1 « V < епХШ1-(\+-ШП)/г ; (12)

в) Оля градов с я петляли при п £ т 4 п(п+1)/2

1 < V * еМ(п+1-(ПУ87п£п7+?)/2 ; (13)

Г) Оля графов с п петляли при 1 < т < п

1 * V < п. (14)

Теорема V. Пусть в(У,Е) - неориентированный граф; тогда параметры п, т искомого пЬз графа и компонент вектора подвижных степеней (6) связаны между совой системой диофантовых уравнений

гч-1

£ М =. 2т, (15)

(=0 * «♦»

Еб.= п. (16)

4=0 1

Можно показать каким образом выявляется некорректность входных данных с помощью теорем IV и V на следующих примерах. Пример 1.

Допуотям, что при подготовке исходных данных для решения задачи вибора вада обработки детали (из двух) и поиску оптимальных технологических параметров (материал детали, шероховатость, квали-т*т« диаметр отверстия и ваг резьбы по критерию минимума производства»«* затрет) в технологическом документе-в графе "Оптамизиру-

амые технологические параметры" были указаны параметры 1,2 и З.На основании полученных исходных данных были сформированы следующие векторы топологии Ал1п=(0,0); Рп<п=(1,1); ^=(3.3); АяаяГ(3,3), где число компонент соответствует двум допустимым видам обработки. Компьютерная программа', реализующая теорему IV, обнаружила некорректность исходных данных (по первой доле графа), а вектор Р^ откорректирован на

Пример 2.

По этой же задаче в технологическом документе в графе "Число допустимых альтернатив в технологических параметрах" было указано по материалу детали 5, по шероховатости 3, по квалитету 2. Всего 10 альтернатив. Следовательно, общее число вершин в двудольном графе равно 12, а число реСар - 3 (число оптимизируемых параметров). На основания заданных ограничений сформирован следующий вектор подвижных степеней. Ъ=(8,1,0,0,1,0,0,0,0,0,0). Проверка по зависимости (15) показала некорректность сформированного вектора О, который должен быть 1)^(8,1,0,1,0,0,0,0,0,0,0), так как 2т=6, а не 7.

Использование теорем IV и V, а также, технологического смысла решаешх комбинаторных и оптимизационных задач позволяют разрабатывать алгоритмы и программы автоматического формирования векторов топологии в рамках математического и программного обеспечения НАУПС.

12. Некоторые задачи КАУПС, требующие дополнительных ограничений и использования метода замещений

Классы топологически слотах заДач ИЛУ ПС. Развитие и совераен-ствование ГАЛ неизбежно приводит к усложнению технологически,

ipuwiyu, ж яругах щмижщимиют щюцесоов.Крсие toro«, щж переходе к рдоавм ояюмеяжамвоервстает удмниЁ вес вадич wo- ' ¡ вошческого i марнмшгового характере. Ч», в свое очередь» ,

стоятвльао требует резребопи шят. адвкветмх мпеигагаскях ,*>-:.••• деле«, поотмюшя ■ рвчмм щжп идп КДУШ.

Вэеякааврвщм сомрммктвамп щиивщвЯ! цовиш В .яв-г; ЩИ» чип Bâ жх речпво мжи» нем» усжшю ж у*иршви> рведв-

Кжлессу мериетвнгошх áum ошкянцв Ятиюоввв иодмь . вар - рекламе - ршкж". В осяове модоа тжж* вдея натра*/4еаахь~ : еве "затрете - щтОша,". Отлгаа замечается в там. чт^' реававв втолвдется на юогодолынм графе методом замаципЖ щя вспольэо- '

; вант сбалаисироваиих матрац. Рваенве аадач на балавсоао« модели ,.-Ч' иовволлет марквтанговс* служЗв тфедпраятая получать анадатачесхж девой поаффекташюста разлачниж видов рекламы на сегментах рыв; ка? оо привлекателыюста раалачвнх модафакац** надела! для раалач-ннх груш аотресмтедвЯ, по» аффектаввоста различных каналов сбыта в продвювнка товара на рыноки т.п. Класафосацвошшй код задача: 1:1.11:4.111:1,2,3,4.

К классу задач технико-экономического планирования относится задача рас<сата производственного распасания, в рвавши которое су-дестветш» научтШ1пра«^есжай вклад внес д.т.н. «ролов Е.В. Эта задачатам» решается методом замечена*, а ее классификационный код: 1:1Л1:2ЛД:1 -:;

К классу задач !те1Нолопсческо* подготовки проазводства относятся, например, задача оптимизации технологическах соответствай на этапе проектарованая аздалая (Тамковскав В.Г.).Огличие заключается во взвеиквашогнсюдной таблицы принятая ревений стоимостные показателями. Решение выполняется методом замещений. Классификационный код: 1:1.11:3.1,2'.

- К классу задач диспетчироваиия относятся задача перераспреде-1 левая проазводственннх ресурсов при возмуиащих воздействиях (отставание откаландараого плана, от сменно-суточного графика, поломка станочного оборудования, невыход на работу оператора-станочника и т.п.), Задача реяается на двудольном графе методом замацв-у ний к минимизирует убыток при оптимальном принятом ревении, " который моют возникнуть от возмущающе го воздействия на "производственный процесс. Классификационный код: 1:1.11:3.111:1,2. . (Далее классификационныйкод будет указываться в круглых скобках)..

Отдельные примеры задач ПАУЛС приведены в табл.5. Здесь же д»- .

Примеры задач ИАУПС, требупцие использования

вахтеров топологии для формализации ограничений

ТаИлисир 5.

Наименование задачи Целевая функция Ограни- Допустимый метод

чения ВиГ дп ВЫ из

1 Маркетинговые задачи

1. Балансовая маркетинговая модель 2. Расчет производственной программы с учетом прогноза спроса (1) (1) (3.4,6) (3,4) нет нет нет нет нет нет да Да

Проектирование производственных подразделений f

1. Размещение станочного Ьборудова- .. ния J • j (1) (3,4) да да нет Да

Технологическая подготовка производства j ... 1. Оптимизация технологических соответствий \ 2. Поиск способа сборки и его оптимизация t 3. Оптимизация холостых перемещений измерительной головки КИМ 4. Оптимизация последовательности технологических переходов 5. Балансировка технологических маршрутов ; 6. Минимизация числа магазино-ком-плектов \ «> (1) (1> (1) (1) (9) (3,4) (3,4) (3) (3,4) (3) (3,4) нет да нет нет да нет нет да нет нет да нет нет нет нет нет нет нет Да да ia Да t f8 да

Технико-экономическов\ планирование \

1. Расчет сменно-суточного ¡задания и сменно-сумочного графика 2- Балансировка производственных ■ мощностей (1) (1) (3) (3,4) Да нет Да нет нет нет да да

Дисдатчирование /

1. Перерасти^ по па няе производственных per-'. • "tw возмущапцих во-здейстр:- (1) (3,4) нет нет йат да

/

/

/

ны используемые целевые функции и ограничения технологического и иного характера, формализованные с помощью векторов топологии. В колонках графы "Допустимый метод" использованы следующие сокраше-ния: В и Г - метод ветвей и границ; ДП - метод динамического программирования; ВЫ - венгерский метод; ЫЗ - метод замещений. Слова "да" и "нет" означают, соответственно, возможность и невозможность применения данного метода при решении конкретной задачи.

Кроме упомянутых вайе задач методом замещений решены такие задачи. Оптимизация маршруте автоматической тележки при сгущении потока заявок на обслуживание рабочих мест. Задача является двукри-гариальной: минимизируется суммарный пробег автоматической тележки и простой станочной? оборудования в ожидании подачи детали. Поэтому решение ищется на парето-оптимальном множестве точек. (1:1. 11:2.111:2.) Прогнозирование потребностей в трудовых ресурсах в составе штатного расписания или по контракту по прогнозному значению спроса или по портфелю заказов. (1:1.11:3.1,2.) Минимизация транспортных перемещений сверлильного узла на станке с ЧПУ для сверления плат. (1:1.11:2.111:2,3,4.) Оптимизация размещения микросхем на плате при минимизации суммарной длины проводников, несущих высокочастотные сигналы. (1:1.11:3.111:5.) Задачи упаковки блоков внутри корпуса по разным критериям (1:1.11:1.111:4,6.) и другие.

Рассмотрим более детально актуальные задачи ИАУПС. Некоторые из них не могут быть решены классическими методами дискретной оптимизации. *

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

деталей составляют групповые магазино-комплекта инструментов станков с ЧПУ (Наянзин Н.Г. .Раздобреев .А.Х., Копосов В.Н.). Магазино-комплекты выступают в качестве системообразующих (потокообразу|ь щих) факторов. При переходе к обработке от одной партии деталей к другой выполняется смена магазино-комплекта. В атот период времени станок не работает, что щйводит к снижению производительности труда. Магазино-комплекта инструментов, необходимые для обработки; заданной партии деталей, могут быть скомплектованы различным образом как по составу инструментов, так в по количеству магазино-ком-плектов. С уменьшением чи£ла магазино-комплектов суммарная величина простоев станков снижается. ;

Технологическая постановка задачи формулируется следующим образом. Пусть заданы: а) совокупность (перечень наименований) деталей, подлежащих обработке! 1*1,2,...,т; б) совокупность ин~;

4 струментов, необходимая д^ия обработки заданной совокупности деталей J, прямоугольная матрица достижимостей характеризующая Соответствие между деталями и инструмен-. теми. Соответствие моделируется дугами, исходящими из множества; О вершин 2-ой доли трехдольного графа и заходящими во множество' 1} вершив 1 -ой доли графа. Размер партии деталей каждого наименования определяется стойкостью единичного инструмента, имеющего максимальный расход ресурса при обработке одной детали. Это ограничение приводит к тому, что, если инструмент одного наименования исполь-/ вуется одним станком для обработки деталей двух и более наименований, то в магазино-комшюкте должно быть соответствующее количе-

/

ство инструментов-дублеров. Вопрос задачи: какую минимальную сово-

/

купность магазино-комплектов И необходимо сформировать ? Где ,2,...,р; 3 - номер магазино-комплекта; р - минимальное

/

/

число магазино-комплектов. При этом где ^ - емкость ин-

струментального магазина /-го станка.

Сформулируем задачу в терминах теории графов. Для этого дополнительно введем следующие переменные: х^Ю, 15 - булева переменная, моделирующая использование /-го магазино-комплекта при х=1 в противном случае); - полустепень исхода (-ой вершины, достижимой из вершины т.е. это количество наименований инструментов, необходимых для обработки (-ой детали, предположительно

прикрепленной к /-му магазино-комплекту; = (а(, аг..... аж) -

вектор закрепленных полустепеней захода вершин второй доли графа; Р - число вершин третьей доли графа (исходное количество магазино-комплектов). /

Форма ограничения

Р

2 I,- шШ; (1Т)

/=» ' .

'. т р

'Е £ йих, $ Я.; (18)

ч=) ч * '

5~ = (а,, аг.....ат); V,, (19)

Наиболее близким аналогом задачи (1Т)-(19) является задача минимизации числа процессоров при выполнении набора заданий. При этом все я, равны между собой. Поэтому задача о процессорах является,частным случаем задачи (17)-(19).Задача о наименьшем покрытии не может быть аналогом нашей задачи, т.к. областью допустимых решений в нашей задаче является полный двудольный граф (2-я и 3-я доли). Задача (17)-(19) сводима к задаче разбиение , * является ОТ-полной.

Для решения задачи (17)-(19) использован метод замещений, вя

основе которого разработаны алгоритмы ее решения.

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

Введем дополнительные переменные: № - помер дуги в списке дуг

Исходного подграфа, содержащего вершины иу (магазино-комшюкт) и

I - .

Юн (деталь), соответственно 3-ей и 2-ой долей графа; ^ - текущее значение остаточной е^ости магазина (при отрицательном значении - магазин переполнен) | р4- пометка {-ой вершины 2-ой доли графа (р{=7 - 1-ая вершина помечена, р^О - не покачена); в4 - полустепень исхода {'-ой вершимы 2-ой доли графа (соответствует числу инструментов, необходимых! для обработки {-ой детали); а, р, 5 -■ вспомогательные переменнее; I) - множество вершин второй доли

графа. ] |

* _ •

Алгоритм формирований начального подграфа.

Шаг О. Положить: 1=Ц К-О, '

Шаг 1. Положить £=|Ь|+1.

Шаг 2. Положить 1=1\1. Если £>0, то идти к шагу 4; иначе положить N=11*1 и перейти к шагу 1.

Шаг 3. Если VI, £, то идти к шагу 5; иначе положить':

Ип=/, Рр=г, идти к шагу 1.

Шаг 4. Если р1-1 л Ы, то идти к шагу 2. Если р1*--1 л {«г, то идти к шагу 3. Иначе если QJ-д^>0, то положить: а=0{, &={, й = QJ и перейти к шагу 2. ! Если QJ~б^ 4 0, то положить: ¡¡----N+1, QJ=QJ-6l, »н={, р =1, 3=3+1, р=3 и перойти к шагу 1. /

Шаг 5. Если Сц^-О, то решение задачи (17)—(19) получено;'' шгачо перейти к алгоритму формирования ДЗ.

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

дложенннй алгоритм позволяет получить решение задачи (17)-(19). В тех случаях, когда данный алгоритм не приводит к решению задачи, тогда полученный начальный подграф становится корневым узлом дерева замещений (ДЗ). После чего реализуется алгоритм формирования последнего.

Введем следующие обозначения: К - номер яруса ДЗ; NPK - текущий номер пары замещений на К-ом ярусе ДЗ; KGK - количество сгенерированных пар замещений на К-ом ярусе ДЗ.

Алгоритм формирования ДЗ.

Шаг О. Положить Я=0, ffPR= 1, EGK=1.

Шаг 1. Если НРк > KGk, то идти к шагу 5: иначе положить К=К+1; сгенерировать Я-ый ярус ДЗ процедурой 2. Если KG >0, то идти к шагу 3.

Шаг 2. Положить УРк=УРк+1. Снять метки с левого узла-брата. Если NPK> RGK, то идти к шагу 5; иначе идти к шагу 4.

Шаг 3. Положить: К=К+1, NPR=1.

йаг 4. Если Ч Q. > 0, то идти к шагу б; иначе перейти к шагу 1. ;

Шаг 5. Если К>0, то идти к шагу 2; иначе положить Р=Р+1, дополнить список Е\Ег дугами, исходящими из вершины J=P и перейти к повторению алгоритма формирования ДЗ.

Шаг 6. Точное решение задачи (17)-(19) получено.

С помощью системы искусственного интеллекта ALICE (Лорьер Я., Франция) эта задача решается приближенно и то, только при одинаковых емкостях инструментальных магазинов. Классическими методами дискретной оптимизации такая задача не решается. Метод замещений является пока единственным методом, (кроме метода перебора) способным точно решать задачу минимизации числа магазино-комплектов.

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

- за -

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

Рассмотрим постановку/ и решение нодафгцированной задачи на ко: нкретном примере. Пусть задана последовательность технологических, операций, установленная я ля каждого из наименований деталей. Для каадой операции по кавдо4 из деталей определены допустимые назначения на станки и время ее выполнения подходящим для этого стан. ком (табл.6). Время транспортировки детали от одного станка к другому задано матрицей (таф.7). Время подачи заготовки из склада' и уборки детали в склад зацфно постоянным и равным 6. Кроме . того, заданы следующие ограничения: а) отдельная операция по каадой > из. деталей должна выполняться на одном станке, т.е. разветвление типа "ромб" в технологическом маршруте недопустимо; б) каждый; из станков должен выполнять минимальное число операций, относящихся к деталям разного наименования, при этом число наименований деталей, обрабатываемых'каждым из станков должно быть не более 2 и не менее/ 1; в) все станки ГПС должны быть задействованы на обработке, поступивших партий деталей, что следует из ограничения б); г) число станков ГШ равно 5. /

Математическая формулировка задачи следующая: найти /'

Времена выполнения операций на станках

Таблица 6.

Операции Наименования деталей

Деталь N 1 Деталь N2 Деталь N 3

с, сг сз Сд с5 С1 °2 С3 °4 С5 С, °г С3 °4 С5

7 - - 5 - _ 4 - - - - - 6 -11'

°2 - 10 8 - 12 - - а 7 - - - - 7 8

°3 ------ - - 10 - -----

Времена транспортировки деталей мэкду станками

ЗЪЗдшла 7.

°1 сг Сз °4 С5

С, - 1 3 5 6

С2 1 - 2 4 5

сз 3 2 - 1 3

5 4 1 2

С5 6 5 3 2

т11ЧМ|(си+ Vх и- (20)

при ограничении

I - номер вершины исхода; J - номер вершины захода; п - число вершин исходного графа; вес дуги графа, моделирующей время транспортировки детали от 1-го .станка к J; вес /-ой вершины графа, моделирующей время обработки детали на одной операции;

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

. . I

7 в табл.8 дуг исходного урафа, упорядоченных По возрастанию весов 2, являющихся суммой времен транспортировки деталей между станками и между станками и складо^ tт и времен выполнения отдельных онера-. ций на станках tQ. Для формирования начального подграфа отделяем чертой 10 верхних влементов списка, как наиболее "легких". Получе-

• I

нше 10 элементов списка являются началышмподграфом, представленным на рис. 4а. Формируем ^следующие векторы закрепленных степеней: Би={1,1,1,1,1^1,1.1.1.М, 1,1,1,1,1,0), (¿2)

8а»(0,1,1,1,1 И, 1,1,1,1,1,1,1,1,1,1,1), (23)

где 8И - вектор полу степеней исхода и53 - воктср полустепеией захода. Порядковый номер компоненты каждого вектора соответствует

1

номеру вершины начального подграфа. Значения компонент векторов/ вытекают из ограничения а). /

Формируем первый ярус дерева дуговых замещений (ДДЗ), для которого кандидатами на удаление являются дута с номерами У '6 и 2 списка, т.е. дуги 5-7 и 4-7, как дуги, даищие избыточную йоду степень захода верашне 7. Кандидатами на добавление (недостаточная

полустепень исхода вершины 1) являются дуги с номерам^ 12 и 18, т.

/

Упорядоченный список дуг графа Таблица 8.

N Дуга г о 2

1 6- 7 3 0 3

2 4- 7 б 0 6

3 11-12 6 0 6

и 15-17 б 0 6

! 5 16-17 6 0 6

/ 6 5- 7 8 0 8

! 7 13-15 8 0 8

' 8 3- 5 1 8 9

9 14-15 2 7 9

10 7- 8 6 4 10

11 8- 9 2 8 10

12 1- 3 6 5 11

13 2- 4 1 10 11

14 2- 5 3 8 11

15 9-11 1 10 11

16 13-16 3 8 11

17 12-13 6 6 12

18 1- 2 6 7 13

19 3- 4 4 10' 14

20 3-6 2 12 14

21 8-10 4 10 14

22 12-14 б 11 17

23 2- 6 б 12 18

й. дам 1-3 и 1-й. Построив декартово произведение подученных мно-5шШ» получаем множество пар замещений, упорядоченное затем по щцтшшзе рвзнсшти весов (рже. 5). Первый ярус ДЦЗ сформирован. Тшешша пару вамещениа первого угла ДЦЗ 6-12 зачеркиваем дугу N 8 (¥»©, Б-'?) и добавляем пунктиром дугу N 12 (т.е. 1-3). Получен ТйКущЙ 11ршйкуто,щый подгр^Ф» который необходимо проанализировать иа асШтечдаеть а недостаточность полустепеней вершин в соответствий е шяоршй (22)и(23).| Поступая далее аналогично изложенному, . Получаем да, содержащее 5| ярусов. Остальные висячие узлы ДЦЗ яв-Л'яшеа беешршшктшши щбо по прогнозному значению нижней гра-ш необрадающ нарушению топологии. Построив про-Межушшй вдгрф, сформированный на пятом ярусе ДДЗ, имеем сба-Лбнйирашаш ш ©граничению а) технологические маршруты для всех ившшэша® деталей] Это следует из содержимого строки "Ба-. Ланй* а чаота рисунка 46 - число задействованных станков на

каждой едаращи на цршшшЬт 1, Однако, из столбца "Баланс" в пра-т& чае?й риеуша <шда@т»|чю по, ограничению б) технологические щреруш т ешш 4 должен обрабатывать три

дгтшш, а 1 Щ зедэйетеаван, Для КЩ по ограничени-

* 1

ш е,)й в) ъмщж- шшжтаыадю вершш

шй» '

Сутаоеть вйркшшк еводатса к

башцаяя» «дай щродзд е взбатечшй тршгтзгш (в©сом) на другу»''' щрйину, караштрш (весом). При этой

№гомат»»?а<й ЗЖЩй« шящщтшэ задавши вершинвм дуги. В №Шт случм варштуш шмиея данные столбца "Ба-

дане'"., шй&ймий иредш йкашшй, заданных ограничением б). 1&ку(ми йиа'шшлла дадедайЯ! 3 для станка 4 и .параметр О

Склад(?)

(V ■ /

(¡0) (н)

1а>

« 1т)

. Г.

(1

(17) (1>.)

Я)

п оп ог1 П-У о1Я паа оза П-У о1Э 0ЙЗ У

Склад (п • • [г: . . (Г к) « (Г?)

С, Л П!) Гл\ I \ . . . / с„

г

(дУ/. \ - •

\ ' '0 / • 1»ЛЧ • ■/

°з • \' •, / ' • ФХ у ■ сд • (зЛ • ' • (Гд) • ■

■ V

о.

(1 6;

лапа

0

1

р

3 1

Баланс

1 1

1 1 1

1 1

п оп ой1 п-у. о1й овв озг п~у о,э о23 У Склад 0" ^ - • (Т • • • ГГг; • ' п.1 0.

Тз) ф

(У) .' - Го'

• • ••/ • £5 •/

V

К,

> ' I

6 ; •

V

.'10, И О

■ /•

' (М 16'

Ёа= лаяа

Баланс 1 1

•1 1 1 Гис.4.

1 1

'в)

с

для станка 1. Отсюда следует вывод о необходимости замещения одной из вершин, находящейся на горизонтали Сд, на одну из вершин, находящейся на горизонтали С,. При этом пара замещающихся между собой вершин должна находится на одной вертикали (операции). Просматривая горизонтали Сд и С) на каждой вертикали, устанавливаем, что единственной парой вершинных замещений являются вершины 3 и 2.Произведя вершинное замещение, получаем искомый подграф, показанный на рис. 4в, который сбалансирован как по ограничению а), так и по ограничению б). Следовательно, сбалансированные технологические маршруты для трех наименований деталей будут следующие: для детали N 1 - 1-»5, для детали N 2 - 2-*3->4, для детали N 3 - 3-»4.

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

Задача баланса производственных мощностей. Это задача планирования производственных мощностей, состоящая в распределении имеющегося фонда времени технологического оборудования под выполнение соответствующих операций так, чтобы обеспечить готовность двта-ле-сборочных единиц.(ДСЕ) к плановому сроку в соответствии с имеющимся объемным планом. ,

Математически эта задача относится к классу задач нелинейного целочисленного программирования, формализация которой имеет следующий вид:

ох-

минимизировать Е Е '24)

¿«1

ы

при ограничениях Е 1-1,2>...,0; (25)

Е (26)

Д^АА > ¿¿1>г> (27)

ЕУ„< , 1*1,2,...,в; (28)

1=1 Г

' . I ■ V' /

где I - тип операции; / -|номер станка; стоимость выполнения

/ {-ой операции на 7-ом станке; 1 - длительность' операции (-го типа

на ./-ом станке; (^-необходимое чксло операций'типа I; Ь - фонд

. рабочего времени ./-го станса; £^-число инструментов, используемое

для выполнения операции (|-го типа; I,- емкость инструментального

! 3 \ магазина (локальный склад) у ./-го станка; п - максимальное - число

' станков, способное выполнить операцию операцию 1-го типа; число операций типа С, которое необходимо выполнить на ¿-ом станке;

у,.- булева переменная. , если £-ая операция выполняется >на

' ! I

./-ом станке; у=0, в противном случае. ! .

Условие (25) гарантирует выполнение объемного плана. Условие (26) указывает, что имеющийся фонд времени станка не может быть превзойден. Ограничение (27) определяется фактической емкостью инструментальных магазинов (локальных складов инструмента). Условие (29) описывает лимиты на технологическое оборудование, выделяемой для выполнения операций определенного типа.

Специалисты* отмечают также необходимость учета следующих специфических особенностей задач расчета баланса производствейных мощностей (БПМ) в гибких производствах:

- отдельные операции могут Сыть .выполнены на любом из нескольких типов станков;

- при использовании различных инструментов на выполнение одной и той же операции может потребоваться разное время;

- для выполнения разных операций часто используются одни и те же инструменты;

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

Для решения задачи (24)-(28) до настоящего времени не существовало эффективного точного алгоритма решения. Поэтому исследователям приходилось выбирать способы ее решения либо из варианов полного перебора, либо из множества приближенных алгоритмов. Однако, с появлением новых,' ограничений на топологию искомых подграфов и новых классов задач на графах появилась возможность решать, эту задачу в терминах; теории графов.

Для формализации, задачи на графах введена булева переменная xlJ. Если с-ый тип операции выполняется на /-ом станке, то х^ =1, а в противном случае, х{^0.

Целевая функция принимает вид ' о и

минимизировать с Т.О. ,х. ; (29)

<=> }= г Ч

а

при ограничениях £ tlJX^J<bJ, J=1,2, .. .,¡1; (30)

• .-И'г/' ; / . (31)

* Искусственный интеллект, применение в интегрированных производственных системах / под.ред. Кьюсика. Ы.: Машиностроение, 1991.

-544 с.

/ - номер станка; С^- стоимость выполнения 1-ой операции на. /-ом станке; tiJ- длительность выполнения {-ой операции на /-ом станке; а{- необходимое число операций типа I для ДСЕ определенных объемным планом;. Ь^- фонд рабочего времени /-го станка; 5(-число инструментов, необходимое для выполнения (-ой операции; Ъ}-емкость инструментального магазина (локальный склад) у /-го станка; ?

Задача. БПМ решается на;трехдольном графе, где вершины первой доли моделируют наименования ДСЕ, определенные объемным планом. ¿Вершины второй доли - тиш] операций и их весовые характеристики, (число ДСЕ). При этом значения а{ задаются степенями вершин. Вер- ; шиш третьей доли моделируют станки и характеризуются значениями

и Ъ ':"

Для решения задачи : методом замещений необходимо доползи-.., ■ тельно ввести ограничения,(3) и (4), определяемые технологическими требованиями рассматриваемой задачи. Поскольку объемный план рассчитывается с точностью дс! дсе, то и задачу БПМ необходимо ре! ! шать с такой ке точностью.! Вершины третьей доли моделируют станки

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

Значения компонент векторов (3) и (4) вычисляются следующим' образом. Для верапан первой доли графа компонента о^ вектора (3) ривня числу необходимых типов операций в соответствия с технологическим маршрутом. Степени вэршшх второй доля графа, модэлирулхцей ■гита технологических пперапкс олр*долятся числом ребер, исходйчлх вн неркой доли ч ичдидоитнак данной вершине. Ввра&аш третьей доли

графа ограничиваются векторами топологии (4) и определяются следующим образом:'

к^п-Ч+1; а,=Ь - (32)

Использование векторов топологии позволило убрать ограничение (25).,

В тех случаях, когда объемно-календарный план не проходит в расчетные сроки по имеющимся производственным мощностям (есть перегруженные станки), то логическая схема перерасчета баланса производственных мощностей (БПМ) протекает следующим образом. Отыскиваются взаимозаменяемые станки. Если таковые имеются, то производится замена станков и перерасчет БПМ. Если замены нет, то выявляются альтернативные; технологические маршруты, производится перегруппирование ДСЕ и оборудования, а затем перерасчет БПМ. Если альтернативных технологических маршрутов нет, то выполняется перерасчет объемно-календарного плана и БПМ/

- 50 -ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1.. В результате наследования временных, экономических и технологических связей построены математичеакие модели, позво- "■' .ляющяе устанавливать оптимальные количественные параметры ав-: ; томативируемых технологических процессов и производств.

2. Разработана классификация вадач интегрированного автоматизированного управления производственными системами по ви- ; дам целевых функций и форм, по видам .ограничений на степени вершин и по видам исходных Графов, на которых.выполняется ре- , шение. ■ I ..." '' ;г V ' .•"'■' ."; .'Л

3. Сформулированы ¡новые классы еадач теории графог, ограничения в которых математически формализуются векторами топо- , логин и матрицей допуётимых степеней. ' / " -.

4. Разработан новей единый метод решения; широкого .'класса , оптимизационных и комбинаторных вадач на графах - метод аа-иэшений, обоснованный!рядом доказанных теорем. Метод позволяет' решить рад вадач, не решаемый существующими методами'"' (Ш1|оД" ветвей и границ, динамическое программирование.венгерский мз- ; тод), а такл© повысить вффективность вьшслигельнш процедур.

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

6. Бавработана оис^ема алгоритмов, позволяющая компоновать алгоритмические комплексы для решения различных вадач интегрированного автоматизированного управления производственными системами в соответствии с классификационным кодом. '•'/■

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

. 8. Полученные фундаментальные результаты позволяет утверждать. что открыто новое перспективное научное-/'направление в области автоматизации т-^'о.пэгических процессор и прокэводоти.

заключающееся

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

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

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

9. Исследована применимость различных математических методов и их сравнительная трудоемкость при реиении задач НАУШ. Выполненный сравнительный вычислительный эксперимент-на задачах 34АУЛС, решаемых классическими методами, показал увеличение скорости сходимости метода замещений в 2-4 раза ло сравнению с классическими методами.

10. Алгоритмы и программы, разработанные на основе метода замещений и реализованные- на машиностроительных заводах в подсистеме оперативно-диспетчерского управления производством, позволили увеличить фондоотдачу технологического оборудования в среднем на 35Z и уменьшили объем незавершенного производства в 2,5 раза. .

И. Программная система "Avenir" для ресения оптимизационных и комбинаторных вадач на графах методом вамецений иополь-зуетоя в учебном процессе при выполнении лабораторных работ H практических занятий по (курсам: "Системный анализ и исследование операция", "Планирование и оперативное управление" а 1Ьс-ковском Государственном технологическом университете "ÇfАНКШГ и по курсам "Математические методы исследования операций". "Анализ и проектирование систем менеджмента" в Академии Кзрод-' ного XoaafîcTBa им. Г. В Плеханова. , . ' -

ОБЩИЕ ВЫВОДУ

1. Для решения: вадач, возникающих при автоматизации совре- : менных технологических процессов и производств, характеривую- / щихся сложными комбинаторными' структурами с множеством времен-; ■■;'.■ ных, пространственных, ресурсных, экономических и иных ограничений, необходимо использовать единое методическое обеспечение на баве метода вамечцений. V/' , , : 2. . Дм более: адекватного математического • моделирования со- , . временных автомативируёмых процессов и производств следует .: , иопольвовать систему »¿тематических ограничений, на базе век-;;

торов топологии и матрицы допустимых степеней, позволяющих бо-, ле» точно учитывать реальные ограничения производственно-технологического характера. ■..■;;./•';:'•■ -'-Уч' -

3/ШВыгоние надежности информационного обеспечения интег-, • рированного автоматизированного управления производственными системами рекомендуете я обеспечивать использованием раэработа-;: иных алгоритмических I риемов и программных процедур защиты'< ■ входной информации от |некорректных данных на баве\ докаванйых '-теорем.;

4. В целях ёконоМик интеллектуальных ресурсов и сокращения - сроковраз работки математического и программного обеспечения , при проектировании интегрированного автоматизированного управления проивводствениьаЦ системами необходимо испольвовать кла-. .соификатор вадач и соответствующие ему системы алгоритмов и': , программных'модулей, базирующихся на методе замещений! у* б. Для повышения скорости сходимости вычислительного процесса при решении оптимизационных и комбинаторных вадач интегрированного автоматизированного управления производственными ■ системами необходимо еще на стадии совдания математического я программного обеспечения испольвовать алгоритмические приемы .и программные процедуры, ускоряющие процесс сходимости в рамках метода замещений.

Основное содержите опубликовано в слздутиг. juioc-'i'.yt:

1. Горшков А.®., Кирпичников D.M. Описание ц ¿«¡алиа «фукп-р» устройств ввода методом теории графов. Изв.ВУЭоо СССР,

хашша", N 5, 1968.

2. Горшков А.Ф. Исследование некоторых пароматроп ycrjMüoTi; ввода-вывода информации ЦВМ методом теории графов. Сб.тозиося докладов 11-ой научно-технической коиф. УГМ, 1968.

3. Горшков А.Ф. Экономный алгоритм выделения путей rp'kjf«. №ш. ВУЗов СССР, "Электромеханика", N 8, 1970.

4. Горшков А.Ф. Применение методов теории графов для исследования информационной.'структуры грузовой станции. Груды XI-оЯ общесетевой научно-технической конференции, 1974.

5. Горшков А.Ф. Оптимизация коммуникационных сетей при проектировании железнодорожных объектов. Труды МИИТа, вып.548, М.,"Транспорт", 1976.

6. Горшков А.ф. Разработка технического задания на сменно-суточное планирование работы грузовой станции. Отчет о НИР. Тема 466-ВТ-74,р. 26, 1974.

7. Горшков. А.Ф. Разработка алгоритмов и детальной технологии контейнерного пункта в условиях АСУ. Отчет о НИР. Тема 513-Гр-76, р.2а, 1976. '

8. Горшков А.Ф. Корректировка технической документации по результатам эксплуатационных испытаний. Отчет о НИР. Гос.регистр. Н 6SQ22349, 1969. . '

9. Горшков А.Ф. Козлов ЮЛ. н др. Выбор схещ .-¿азмвщэвкя

/

пунктов переработки крупнотоннажных контэйнвров. Bscjra« ЦНИИ ШЮ ■ И б, 1977. ' ^ ■ , '

10. Горисов А.Ф. Опташзащм плана кошш^тооброзовашя вонтеЗ-

неров. Вестник ВНИИЖТ, N 8, 1977.

11. Горшков А.Ф. Математические методы оптимизации технологических процессов на контейнерном пункте. Труды ВШШГ,вып.631, 1980.

12. Горшков А.Ф. Математический метод минимизации транспортных затрат при размещении пунктов переработки грузов. Труда ВНИШСТ, вып.631, 1980.

13. Горшков А.Ф., Ибрагимов А.Ф. Оптимизация прикрепления отправителей скоропортящихся' грузов к опорным станциям. Вестник ВНИИЖТ, N 8, 1980. j

14. Горшков А.Ф. Вычислительная схема замещений для решения экстремальных задач на графах. • Тезисы докл. 11-го Всесоюзного совещания "Методы и программа|решения оптимизационных задач на графах и сетях", Новосибирск, 19^2..

15. Горшков А.Ф. Об одном методе отыскания экстремальных сугра-"

фов. Сиб.мат.журнал АН СС^Р, т.26, N 1, 1985.

- ' !

16. Горшков А.Ф. Методj отыскания экстремальных подграфов на

двудольных графах. Изв.АН рССР, Техническая кибернетика К 4, 1986.

\ ' <

17. Горшков А.Ф., ЗгржеЬловский B.C., Мирхамидов Ш.Ш. Oirnwajjb- ,

нов прикрепление сельскохозяйственных грузов к опорным станциям. Вестник ВН1ШТ, N 2, 1988. ^ . '

18. Горшков А.Ф. Алгоритмы расчета расписания обработки партий

1

деталей на автоматизированном участке. Научно-технический сборник, серия 2, вып.б, 1988.

19. Горшков А.Ф. Постановка задач и выбор исходных данных для расчета приоритетов запуска, сменно-суточного графика и сменно-суточного задания. Отчет о НИР. Тема "Перспектива Н 474-21-89" ЦНИТИ М., 1989.

20. Горшков А.Ф. Постановка задач и разработка алгрритмов рас-

7 /

чета приоритетов запуска партий деталей, сменно-суточного задания и сменно-суточного графика. Отчет о 'НИР. Тема "Перспектива N 47421-89" ЦНИТИ, М., 1989.

21. Горшков А.Ф. Описание алгоритма расчета сменно-суточного графика. Технический проект "Автоматизированная система организационно-экономического управления корпусом и участками цехов N 1, 31". Отчет о ПИР. Тема ТТ9-619-86, ЦНИТИ, М., 1989.

22. Горшков А.Ф. Доработка алгоритмов и программ расчета ССГ в части повышения оперативности внесения изменений при случайных возмущающих воздействиях. Отчет о НИР. Тема "Перспектива N 489-21 -90", ЦНИТИ, М., 1990.

23. Горшков А.Ф., Гуров А.К. Методика синтеза алгоритмов управления гибкими производственными модулями роботизированных комплексов. Вестник АН СССР, Твхнич. киСернвт., К 4, 1990.

24. Петров В.М., Горшков А.Ф. Динамический синтез маршрутной технологии обработки деталей в ГАУ методом замещений. Сборник докладов 1-ой Международной научно-технической конференции "Актуальные проблемы фундаментальных наук", М., 1991.

25. Горшков А.Ф. Моделирование топологически сложных структур на графах методом замещений. Сборник докладов II-ой Международной научно-технической конференции "Актуальные проблемы фундаментальных наук", Ы., 1994.

26. Горшков А.Ф. Балансировка технологических маршрутов мето-цом замещений. Сб.трудов Волгоградского политехнического института. 1994.

27 Горщков А.Ф., Соломенцев D.M. Применимость вершинных зама-1вкий в классе задач о К-вершинных подграфах. Доклады Академии На-'К, том 336, N 2, 1994.

;:а Гормков А.Ф., Солшояц!>в 2.М. Применимость реберных закэда-Iслп в «даос* комоишторшх звдач но графах, доклада Академии Наук, VOM 037, И й, 1994.

Горшков А.Ф. №m>rp!ijjyw.fl устройство. Изобретение. Автор--•ко- N 140234, . ,

30. IVjfö^a А.ф., К1ф1Мчникой ВЛ4. и ,кр. Буферное запожшавдоа $ткч>3«пчк йаовретоико. Авторскоо «йгд. V 175095, 1966. ,

3U Горлкоь А.Ф., Куликов к др. 5!с?ро>?ство для считывала» вн-форчмв«? с подоашых объектов. Изобретение. Авторское свид. В 470426, 1974. i ; ' ;

32. Горшков .А.Ф., Козачжще и др. Устройство контроля и учета состояв:)! ячеек в cteinasax. Изобретение. Авторское свид.' Н 517544, 1975. j : ;

33. Горшков А.®., КаЗачюце и др. Устройство для контроля свободаостй ячеек стеллажа. Изобретение. Авторское свид. N 390542, .1973. i

I

34. Горшков А.Ф., Вало^з и др. Устройство для автоматического адресовшшя перемещаемых объектов. Изобретение. Авторское свид. К 492440, 1976. | 1

35.,Горшков А.Ф., Потек^ин Е.А. Устройство для учета и контроля времэни занятости ячеек,камеры хранения. Изобретение. Авторское свид, N 582520, 1977.