Повышение эффективности интегрированного автоматизированного управления производством на основе метода замещений Горшков, Авенир Федорович

Введение к работе

АКТУАЛЬНОСТЬ PAFOTH. В сваей с переходом экономики Россия на рмю'шые огноязния возникает необходимость Со.тоо быстрого и адекватного реагирования предприятий на иогененио олрооа на

рЫИКе. ЭТО НОВОе ДМ НЯЛЮГО КаИИНООТрСеНИЯ OKOHOHil'J'JOKOP !'П"

чэство требует сслдашя итерированного автоматизированного управления проивЕодсакеннуии снотешьш (йАУШ) на 0,-we комплексной автоматизация процессов создания изделия, качжчл i~v его проектирования до ивготовдзн:«. При этом вовникапт необ-хсдшюсгь вьпіогне-шш уаркэтингогьк исследований ецз на'ихал;? проектирования нового ивцэдил а сдемэпня ва зфйеитигкооть» отдельных видоЗ'реклам на различных сегментах ріжка в щю-цооое реализации новых ивделий. Хотя многие вновь производили изделия отвечают самым яест.кии требованиям, предъавяяв-емш потребителем, нередко многие из них не выдерживают конкуренции о импортными даже на внутреннем рынке.

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

.- экономить интеллектуальные ресурсы при постановке и
Іюрм&югеацин вадач ИАУГО;

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

Лредотоявие структурные ивмепения в промывленности пот-«Суют более энергичного иопольеоваиия современных инфэрма-дашных технологий яри управлении вроивводственными С1ГОТвМ8~~ и. Современное машиностроительное прока водство хирактери-уетоя дискретностью и большим числом технологических и иных

- г -

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

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

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

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

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

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

\ fuat при постановке и роивиии прикладных вадач автоматизации
геологических npoi^oooe и производств;
і',, г ооедадад» адгорятмичваких методов защиты от некоррект-

у_; і' вое*я ьходиык яздяых. оЛишечиаавди* аффективное функциони-

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

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

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

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

!-е Взесоювііов совещание "Методы и программы решения опти-М8ационных вадач на графах (Новосибирск, 1982), Воеоохеный импоаиум по теории графов (Одесса, 1991). Постоянно деяот-укдий семинар при кафедре дискретной математики ЫШв (Мос-ва 1984), Вычислительный центр Академии Наук ООСР (Москва, 985 и 1986), московский Государственный Университет км. Ы. R , '>' омоносова механико-математический факультет (Москва. 1086)»^ хгсоянно действующий семинар в Центральном зковомико-тгег,

- A -

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

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

'^.foammya .''../y\'yy.y:_t

Введение ; ;"''"" ,.'-,-.. ' .'"'"-'". ."':."- -""- ї.:'.'- ;*; - V V." с '."'т.Г S- - "^г" -'" '-.-<:; '"'. ''."' ''''' '.^'.'.

':. Вопросам создания и говшеняя афїективности автоматязированншс
ситем управления производством ЦСУЩ .к. ихшдсиствмга '-.Т8К»:;вап~
росамоперативного планирования и: управления в, іштегрированвнх; ма
шиностроителей*яроетводствах восвя^ви.раЛ>№ многих о^адотввнг
; них, учешх: П.Н.Ввляяина, М.Х.Вйв-хермана; Н.Г.БруввичаУ Q.E.B&cz-
льева_кА.М.Г^Мя№,^ 1>;И.дЪетярева,

В.В;ЕЬюльяюва» jt.>(.KanyctHBa» ;&М.Колвоова;. МЛЧКбоова, ЛЛ) некого, B.B.JBfflraeBa,B.r.JIoraa»Bai % И.М.Макарова,. О.П.1*гфофвнова. В.Г.1№тр6фвяова,^: В.В.Павловаг ВІА^^в

Овсянникова, Ю.И.СолонюнЦева,.'ВіЛ.босюнкня»,: Й'.^іЬулйган-ОаДв»- В»Г. Тимковского, Э.АЛретьякова, 'Е.Б»ФрэлЬаа,гВ;Д:лЦ»я^^\Ві8ІЦвл»-Пвва.-А.Д.Яудааюва^вг'другазсі, Д ;/:у_::уу_:ї},ууЩууукуУУ\-;'.

Аналия расежлранвш^ра^
гическях основ- построениа тюдгяствм АСУП эими учеными аспояьаова-
лиск, как !л»ви^« RJ^caneoote, ш

кие метода решения;задач из такихклассов ^,''яхяф^^:у'хг^фвімі~ ровен»* BfljmmftiK» програжаїрованив, диежратнов програ»*ировввив и'др* Поетя^

как правило, даскреяшй характер, то наиболывее применение в;':. атих работах нашли метода целочисленного программирования с бужвжи переменными. Вполае еотеостванно, что наиболее иирокоаV щттттш з научннх работах исследователей находят -такие у^щіот^жЖ^Ш&бя.у. ютвай и границ, метод дкяаюрчвохого дрогрвмммроианцди м»тщ» .-«н»^ >рии графов. Перачислениме---метода';яселдсыии'аафвя&і-іхр$у «аенан научннх в прикладнихвадвч^ ШЯУуіпмшеь у,ЩіЩШ ,

наярлаженаого перебора, шмо омвчаэтся or штодов полного перебора. Кроив того, соврекакные проблемы управленая производством ста- . вят перед васладователзи шшэ вадачв, которые являются либо саоша трудоекхшн для традшдаоших иатвкатяческих методов, либо в пргзцЕВз ш когут быть раваш послэдааа. Это объясняется тем, что соБргдадаш проблема автоаатнзащш технологических процессов в прссзводств требуют форкалазацви возникаю!! в производстве огра-ничеекй, ш> реаладуешх клаасическкиа катодами. По втим причинам шош» учеше разрабатывает вврасткчэскве и прабдзаввнше алгорит-ta, ««здаз в» которых праашвзм лкаь к узкому кругу задач, йакото-раа ьхгорзтзд, являясь уннкальныма, првэгенвма только к отдельно ваятоЭ эедаче. Эта обстоятельства требуют повышенных интеллектуальных эатра* Как от сеаогр исследователя, так и от програкыаста, пра разработка коагьютерных программ йатегрнровашюго автоматизи-роваш>го управленая производственныш системами (йаУПО). Пра большоеобъемах исходных данных, вводимых оператором ЭВМ, существует пробдзаэ везите от опвбок, поэтому весьма актуальной является задача адгоратдачеокон проверки на корректность исходной информация. Ськшдавде', проблаш ШЛО потребовали постановки новых еадач уораалензя, разработки tiosoro иатематического катода нх ре-Esisa, в sesss вовах йатештаческах способов задания ограничений, тзхЕШСГЕчасаого а правэводствэшхого характера.

1, Кэюяораэ пробйзш а еодача ШИО

/.. Сзраадд ц^швдотрдагашздс предорватей н проззводств в Сункод-с^о@ш»> 9 условиях pasossax оттУга>шЙ требует нового подхода к щгчмэт взтераахша s е^орцщюдагаа вотоков, щах<ул5фукада їда

в офзрэ производства, таз я в сфэрэ закупок и продел, т.е, ринка. На ряс.1 показеяо укрупненная схема циркуляции упомянутых вике потоков, гдэ ипфорлащоншэнотохя показанн тонкша сярелкшга, а материальные - ааатршювшшшгз. В Пй^оряационном коптурз "прстзвод-стккршонЧІАУІЮ^ гэдгшот фушсцпональныэ блоки, харектеряив дня предприятий, работ8П532;а уояовяях рыночной экояожкп. ,'ji" terns*

Йдакем относятся: .'ШИЙИШгУ й "РЕШМА". ОункцпоналшгЗ- блок "ШУЛО* являете*!':файшройшсі.;'Йсадоау фуякдааяалодх^блозу' соот-йэтствук? сйоа'шдсЕОТйы- ЙІУГО, осношнв из которая ' показш! иа

рм*1^.Ніет';^)чраїтосй-<^в6^;"подсаетеїяі" псзпапо еловой "саго-

еайша

ПРбйЭЙСЩОТВО

/*-*

Р н К О к

;Й /(Г

ЇІАРШИНГ

Ж.

Ж.

'Н'АУ ПС

РВДАЙА-

>

ЙЗС.і.

тока». ПорядкогкЭ поиэр- тадсястс?»» покезея на рзеувко в жруаслввд.
1; АСЕ! - югодатвзнрогавя&іг ^:систокэ- поучлах соамАовскй»--'
. 2. САННІ - сгстзма йвтеглтпзярозшногї) каркэтяпга, рішай и
плйапроэаяяя...,' " - *""'-

3. САПР - - систем» антетгапЕзрсзгигого проактяровсая. 'Г;.-''-'

'' v-ч"-':'.^^----^/:/ :'" *'/;"^:.-.-8^':/-'""';.— -,".'' .;'. -,' . '.'-";

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

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

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

2. АШО - автоматизированная система инструментального обеспечения. .'-/ - - ' А .

8. САК - система автоматизированного контроля.
.Математическое обеспечение перечисленных подсистем ИАУПО в

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

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

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

'-';;;JM'.-.'-':]*тг;1!&ют)Ш»ш*' прогримми при ооотоянном «тате

-' МІЙОЧИОЕ- ЯвАЧИРЕ* fflK^frffflVlfft г

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6-а - расчет очередности выполнения заявок, поступявдях с рй-СС-ЧИХ М9СТ.

7-а - минимизация числа магазино-комплвктов.

8-а - «тгмигсцЕЯ рэбочэго шрзруте нэр^^ашя вниеря'гзяькой головка Km.

- 1(3 -

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

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

П ft ' і

ЕЕ о, ,х,. -> estr. (1)

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

' '.''''' '"'} : '; :''. ' . -

Е Ее J, *- Z Ъ,у -mln. .,(2)

Некоторые задачи-представители для формализованной математической постановки требуют введения ограничений на топологию подграфа G'(V,E').' В 1975. Года, английский математик Н.Криотофидес сформулировал одно ограничение на задачу с целевой функцией (1) , назвав ее "общей задачей построения остобкого подграфа с предпи-сашшми степенями". для формализованного описания ограничений в задаче Крястофидеса введем вектор закрепленных степеней:

S т (а_},а_г,.,.а_і,...о_п);/ (3)

где a_t - степень вершины номер (,.

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

; :^(4^-:-^''%?!

где А_тхяі Ajmif векторы допустимых степеней/ P^, P_mf- векторы запрещенных степеней, D - вектор подвижных степеней. '"'

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

/

(4) (5)

оі'.';.'- ^аог — % J ' ' .%' _:'.. V

>#»*

,^вп+1.,Г ^an+f_#Z ": ^an+f,J ...^;V*.ntJ,n

где a_{t:- елемент ВДС, находящийся вЧ-ой строке, и /-ом столбце.}

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

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

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

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

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

Таблицу 1.

п П і

Е Е х,: = т; (8)

п п

Е Е х,. - min, (9)

где j.'t '{0,1)7* - число ребер в подграфе (G'(V.B').

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

Рассмотрим место классических задач и нового класса задач, за-дамвмых формами (8) в <9), которые шест прикладное значение в іщтфгрвроваидах автоматизированных системах управления производст-

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

. _ '. ' ' " - ' - із' —

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

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

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

Таблица Зі

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

управления производственными системами",

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

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

І. Види зодсп; 1. Оптимизационные. 2. Комбинаторные. II. Типы графов: 1. Неориентированные. 2. Ориентированные. 3. Двудольные. 4. Многодольные.

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

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

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

і исходный граф задан матрицей .смежност». Следует заметить при йтом,

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

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

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

Вводом слодевдив'обозначения: G(V,E) - исходный граф, содержащий шіожо?во вершин 7 и мнойбство ребер Е; (Fc?,]?³) - начальный подграф, содержащий множество ребер Е; G'(7,E') - искомый подграф, оад%ржащйІ шюжаство ребер в*; P<'V_>S^PJ - промежуточный подграф; в -4RQJK» ре.йшр искомого подграфа; .я - число вершин графа. При этом ^(t'lsjS)»!^! н п*|Т|, а степени вершин яцА множества 7 относительно Q4'7,E*) задана.

Определена U Жара, coenosaspa ш эая$телоео (уда-ляелого) г₍Е« тлт%т@ёО (добо&ія&хаео) г^ЕМРребер , называется парой ре^ерносо «жш^хия. :

Обозначим олеращш реберного замащення символом На. Кзпрямэр: і Re J- рэбро і замечается та рабро /; 6 Ев 10 - рввро N 6 заметается на рвОро.Н Ш; А Ш В - кдаайотво ^яймвнтсв Л зшгяйатся на равномойнйв »«кш«гао $шшггв В.

Доклада «юдуюдо теорема, фор^уиірїщаа прзаздш тарного реберного аемедаїш.

Теорій» I. %ежъ щхф в(?*Ю с3«рдаа тйераф О'ПчЙ'^ а тетозФ ребер В ярсдовздьмв pasdmmo т два вогимсикся&і S^0, и ENS⁹, єслі (P(?tS) т л&ляюяел G'fV.FV, ш #««« гра#а G(V,i) су-

f> порт ядакафячкй ft»₄,rJ ШЙЗЯ, ЧЙО бмг&мхэодэ г, Кэ У, .Прт-3ш к кз.*й?%?ш$ яшолдата &*(?,&*>:

3.) здаа Ф» @2ш коряея, еаЭвряяадвв наг &м&в чад ^-»|Ґ*) «j» зсмедежгй!!, гдавдркй крыбоЗит» к отскаюю побгрэфа G'^.E").

Творе*» I имавт не только фучдвмяутйлшгй ійрактвр, ко и д%а*

вать различные технологические, производственные и другие процессы в терминах теории графов. Так, іі'й;;п«р, для задачи "Генерация структуры размерных цепей по ^ . * . :,(. аметрам" число размерных стрелок, отходящих от плоскости детали, относительно которой определятся размер до другой плоскости моделируется степенью вершины. Номер плоскости детали соответствует номеру моделирующей ее вершины. Одно ребро моделирует конкретные размерные стрелки, а пара замещений - замену/одних размерных стрелок на другие и т.п.

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

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

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

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

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

- IT -

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

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

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

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

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

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

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

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

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

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

- ''^: '..> '"'..."/ Таблшр 3,

?

7. Прямйшмость pwjepma замещений в классе жомйинаторюа задач ДОШ

Ашогжчво шяаоот мдач (1)1 (2) классы вадач (8) а (9) Ш-

ПС такте является HP-полными. При этом необходимо заметить, что
токае математические метода как динамическое программирование, ме
тод ветвей и границ я некоторые другие классические метода не мо
гут быть приманены в классе задач (8) и (9), поскольку они выро-
вдаются в'простой перебор*из-за отсутствия.весов ребер в исследуе
мых графи:.: Венгерский метод решает ограниченное число комбинатор-
ша задач на графах. ;., -. /.-.

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

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

Р«Е |в!-в|, (10)

' - *' ..''*"

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

II. Ыногество ребер Б разделяется на два годмногества В⁰ и
BVB. Каздое ребро r_fe 5 является кандидатом на удаление, а ребро
глВ\Е - кандидатом на добавление.

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

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

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

а) по необратимому нарушению топологии подграфа G(Y,E,>;

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

Описанная вычислительная схема относится к разделу метода замещений, который занимается формированием алгоритмов решения комбинаторных задач на графах с топологически слоишми структурами подграфов G'(V,S'). В этом классе-задач алгоритмы имеют дело с графами, задаваемыми матрицами смежности. Элемент матрицы смежности а_{.і И, a_i .=1 является элементом модели некоторой производственной системы или процесса. Например: элемент размерной цепи йди наличие сопряжения между] двумя деталями при сборке; номер наименования инструмента, который может быть использ&ван для обработки конкретно» летали и т.аІ

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

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

ТабмллА 4.

8.. Црдаеншостъ вершинних замещении в классе задач ИАУГО

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

Для решения данного класса задач ЙАЭТЮ используется вычисли-

'..' ' ' ... ²² - ' '" ' ^:-'. "'" '': ' '.':'''

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

I. Вершины исходного графа 0(7, Е) взвешиваются значениями их степеней p t»J,2,...,n, а также величинами a_t*mln{p,), к_і'вах(р_і), где а_{ и A_t- соответственно минимальная и максимальная отвцень вершины y смежной вершине и₍. Для некоторых задач целесообразно введение дополнительного параметра р, который характеризует необходимый, но не достаточный признак принадлежности ве-рвины и,е F искомому подграфу G'(V',E')* Аналогично параметру р вводится необходимый и достаточный признак Р. Данные параметры являются булевыми и формируются исходя из технологического смысла применительно к свойству П. \ . '

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

III. множество вершин разделяется на два подмножества: первое
подмножество V^а, содержащее K=>|V| верпин верхней части списка, и
второе подмножество Y\Y, содержащее n-X*\V\V\ вершин нижней
части списка.

IV. Строится такое дерево решений, в каждом узле которого кон
струируется некоторый подграф, содержащий X=|V| вершин, который
является начальным подграфом. Если начальный подграф не обладает
свойством Й, то строится дерево решений путем замещения вершины
u_t« V^а на верюгау u^VV\Y в каждом его узле. При атом вершины v_%
* и, могут (Лвадать признаками p«f, і вершина, имеющая признак
jwt, це должна вамематься на любую другую вершину.

'?'*. Построение дерева ретевЛ выполняется до тех пор, пока не будет получвя ждораф оо свойством П либо пока не будет показано го отсутотаме а исходном графе.

'''. ' ', "'';'' -'; .-.-23-

0 п р в д в л в н и в 2. Пара, сосяшаря ua яаіецааюа (уОа-ляелдй) 0_iiti 7 и валеирачей (добавляемой) вщтм и полученная в 1-оЛ уэдв fe-eo *фі/са ДЗ,.. называется парой вершиккььг валеиіений. Этапы II и III вычислительной схема имеют дало о формированием начального подграфа, котоніни в некоторых случаях может явиться искомым подграфом, обладающим свойством П. Иногда отсутствие Двойства Остановится очевидным на 8^ же этапах решения. /Сложность этапов рейения задач о Х-вершганых подграфах показана/на рис.2. Принадлежность упомянутых выше этапов решения задачи it классу полиномиально решаемых задач определена еледуицей,теоремой.

.Те о ре м а II. Задана отыскания начального К-вершинноео '[. подерафй сР(??,]р) ка грзфз ее У, S) принадлежит, к классу Р.

Форкирававяе подграфе (Р

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

> Класо Р

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

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

Р-оложяая

W-оложная

Имеется ли подграф О* со свойством П в графе в ?

Да Нэт

РИС.2.

S Класс ИР

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

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

Поскольку задачи (8)-(9) сводимы к задаче отыскания гамильто-нова цикла iRim атого достаточно в векторе (3) все компоненты принять равными 2, матрицу весов ребер заполнить единицами, и принять v=l), то мы вынуждены признать,что задачи управления интегрированным машиностроительным производством, определяемые целевыми функциями (1)-(2) и формами (8)-(9) относятся к классу NF-полных задач. Это утверждение является г'тем 'более справедливым поскольку принадлежность хотя бы одной оптимизационной или комбинаторной задачи ПАЛЮ к классу Р, не доказана. С учетом изложенного при разработке алгоритмов, реализующих метод замещений, особое внимание уделялось скорости сходимости Вычислительного процесса.

Дефоржщия начального подграфа. Характерной особенностью метода замацаний по сравнению с методом ветвей и границ является то, что высота дерева замещении (число ярусов) не зависит от числа ребер подграфа G'(V,E'),а зависит от начальной деформации подграфа. Оооааачш* величину наманений деформации при элементарном реберном вамавитаи Ар -р₄-р_и,,где р, и p_(f> - величины деформации до и подо миецйния. Рассмотрим сладуияее утверждение.

Утверждениеі. При эалеаркшх ребра г «Е' на ребро E\B^r величина излечения Оефорлаиии ложет. пришить оОно из следующих значений Ар = -4, -2, О, 2, 4.

Процедурное прием* ускорения схоОилоат вычислительного процесса. Первый прием ускорения сходимости вытекает из утверждения 1. йобходимо по возможности стремиться,к максимальному значению Ао и юбегать отрицательных значений. Второй прием сводится/к генерации іачвльного подграфа с минимальной деформацией. Третий прием связан з уменьшением начальной деформации (релаксацией) подграфа G'(V.E'b їетвертнй прием выполняется путем прекращения вычислений по исчерпанию лимита времени»отводимого на реовниэ оптимизационной задачи.. [Три атом может быть получено как точное,так а приближенное рвивкиа, близкое к оптимальному. Пятый прием связан с порядком просмотра упорядоченных списков удаляемых и добавляемых ребер при генерации пар замещений на каждом ярусе ДЗ.Упорядочешый список из множества В' просматривается снизу-вверх,а список из множества Е\Е'- сверху-вниз.Это,в свою очередь позволяет существенно уменьшить число итераций при упорядочинии пар замещений го возрастанию разности их весов на каждом ярусе ДЗ.

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

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

," . \' ' " '-26-

Провктироввиве алгоритм» я врограми для ЖШО в звачительиоя смотав определяет стдщюсть я длительность разработки все! системы улгжвлекия, а главвое - эОДвияваосте. реяевяя основных целевых задач ШЛЮ. Лэ зарубежным давшш проминпенно развита отрав наблюдается тенденция jxxrra стошостя математического обеспечения в вона разработках. Это обусловлено усждаюнием сяствм управления я огреиачеввнми интеллектуальными ресурсами, обеспечиващякя сам процесс проектирования. ^л

іравцувскня математик, специалист в области искусственного интеллекта, создатель явформацяонноя системи АЫОВ Жан Жак Лорьер оформулировал принцип обработки вяформацнн, во которому формулиро-вха задачи должна быть подвоет» отделена от ее ранения. При таком подходе программных блох/ отвечаю»» за решение задачи, преврава-ется в- "Червні ящик", а программисты разрабатывают только человеко-машинные интерфейсы ввода я вывода. Црн втом роль унвфнкацки математических методов, вспольззуемых для реяевия в классе задач МАЙЮ, .существенно возрастает. Использование метода замещения для решения <штммИ»ационннх я комбинаторных задач ШЛО дает хорову» возможность для такой унификация, что наглядно подтверждается два-

Задачи ИШЮ

/MB ^\ '

Рве.».,

- 2T -

ґ і

грамм* Виша, петхттшЛ на ржс.3, где ясподьаовааи сждгивве со-краивіиш; «3 - метод веммдояя; ИМ* - метод ветвей я гревши ЯП -дшіампеское іфгятвмввровиш; ВН - вентерем! метод.

Рассмотревши) вши) виташітлпіний схеме tkwbojbbpt ватодить ре-

явяив в виде свойого подграфа, ябо и темнить отсутствие таково-

I - ^ г

го в вогадном подграфе, что оврея&пвтся сяедуяивЯ теоремой,

Теореме -Ш. МюоО шшщамА сдаЛмю* шл каткое чцело
шагов. > ^ _у > /

Прж отсутствии подграфа (f'(V,B^fJ в исходном Грефе ревел» ее-кеячжвеется в корневом увдв ДВ ж іфагфвмма» реализующая метод ва-мвиеявж. видает сиуітввістцупввв оосхімввве яв еврея мовяторв. В втек случае ЛР (липо, іцимиивщи* реви іди) дашок» виявить ввяпяе дли шик цтит іфоюводотмпнх р6с)роо&, B906tajPMBX дл# рмппи

_ г *

конкретная вадячи шл/ич я нищиїть.оивториов ревеяве. отсутствие искомого подгравв в результате ивкорревтиш постановки ведачя ево-дате* к инвииуиу сввпявемвввг мвтодеш яаижтн.

it. Вщщняі ваяйте от ведир^вичін'НІ постановки вадл КДУШ

ко воем комооаеятем КШС, реботеяввм в условиях рваяшого щиииититва, предышнянея вмошяв треоовавяя ПО, ЯВЯВЯИл ЯШ і ооо-

~ " ?

веяно ио касается ввинтя входной янфциинввд от яовяввяия оря во— вора яв тіввивтуре ЭВМ» в также врж подготовке исходных провввод-

следуяяяа творами» поавожжввяв яаиявят» МУПВ от мкорректноЖ входной информации*

Творена IV. Вусвь 0(Г,К) - юаршшюробтюа враф'_г яож> ва алвлвти я с |S|, ntyu еде/и п, я и v школоео поОграфх С'(Т,В'}

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

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

« u n п -п.

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

<«J i=l с=» 1*| t=>

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

1 « v < еп1Гп+1-П+-*Ш+7у? ; (12)

в) Оля графов с п петляли при п т С п(п+1)/2

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

1 U v < ft. : (14)

Теорема V. Яусть G(V,E) - неориентированный граф; тогда nopotempu n, m исколого пЬдграфа и колпоненши вектора подвижных степеней (6) связаны лехау собой систелой диофатовых уравнений

^ПаЛ = 2т, (15)

n+1

Е б.= п. (16)

{=0 *

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

Пример І.

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

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

Пример 2.

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

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

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

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

травспортвмх друга переходе к

требует

> вря

ва вх

вроцизоов. ярова того» црж воврастает удедьаяж вео аадач ако-харекмра. Чю» в част очередь, на-

аадач ШОВ*

задача;

подготовке

К амосу аадач

авва стввочвого обору,

итвосвтоа» ваврвмар» аадача рае-, ва PUT дм аервЯаЯФ прсввводства

аадачв дов-

ввн бвтъ еадавв: твш стащсов,

воордвафтв ш «в-npootr

ввтоматвческоЖ теявавв (теіитак) not подаче па шит с

ва ОЦ. передач» падает о ші^уДОрвкаташ с одвого ставка ва другої

код вадача:1:1.11:2,3.

.-..-..-: -^^-:.--.--^--.:-^.-:/^

К классу маркетингових аадеч отвосатся балввооваа воде» /Чо-вер - рекламе - рнвок". В осаова моделв авквт вдев матркщ двоять-ева "эатретн - првбиль". Отлвчва замечается в том. что'ревеввв выполняется на мвогодохыкш графе методом замеаавхЖ пра всполъэо-

в уборке готових детале!

111:1.2.4.

вшпш сбажжсжроаяшп матрац. Рвявнм задач ва балансовой модели повволяат маркетинговой служба првщшятм получать ажшггичесхя» давни по аЦектиамостя различных видов рекламі ва сегментах рака, по првивжательвостн различных модивикаций изделий для раалич-янх груш потребителей* па аффектяввостя различных каналов сбыта в продввввввв товара ва рынок я т.п. Классивнхацнонкый код задачи: 1:1.11:4.111:1,2,3.4.

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

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

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

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

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

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

Тайлиир 5.

функ-

/

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

Кроме упомянутых выше задач методом замещений решены такие задачи. Оптимизация маршруте автоматической тележки при сгущении потока заявок на обслуживание рабочих мест. Задача является двукри-териальной: минимизируется суммарный пробег автоматической тележки и простой станочногф оборудования в ожидании подачи детали. Поэтому решение ищется на парето-оптимальном множестве точек. (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.) и другие.

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

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

деталей составляют групповые магазиво-комплекты инструментов стан-
ров с W (Наянзин Н.Г.,Раздобреев .АЛ., Колосов В.Н.). Магазяно-
комплекти выступают в качестве сжстемообразуицих (потокообразую-
щих) факторов. При переходе к обработке от одной партии деталей к
другой выполняется смена магазино-комплекта. В атот период времени
станок не работает, что приводит к снижению производительности
труда. Ыагазино-комплекты инструментов, необходимые для обработки;
заданной партия деталей, могут быть скомплектованы различным обра
зом как по составу инструментов, так в по количеству магазино-ком-і
плектов. С уменьшением чийла магазино-комплектов суммарная величи
на простоев станков снижается. ,' - : ;
Технологическая постановка задета формулируется следующим об
разом. Пусть заданы: а) совокупность (перечень наименований) дета
лей, подлежащих обработке! D*fd_t.>, М,2,...,«; б) совокупность т-'.
'- струментов, необходимая для обработки заданной совокупности дета
лей ff=fu 1, fc=f,2,...,l; fc) прямоугольная матрица достижимостей
Н=Сг_{3гі, характеризующая соответствие между деталями и гаструмен-.
тами. Соответствие моделируется дугами, исходящими из множества' D '
вершин 2-ой доли трехдольного графа и заходящими во множество' U
вершин 1 -ой доли графа. Размер партии деталей каждого наименования
определяется стойкостью единичного инструмента, имеющего максима
льный расход ресурса при обработке одной детали. Это ограничение
приводит к тому# что, если инструмент одного наименования исполь-/
зуется одним станком для обработки деталей двух и более наименова
ний, то в магазино-комплекта должно быть соответствующее количе-
ство инструментов-дублеров. Вопрос задачи: какую минимальную сово-
купность магазино-комплектов If необходимо сформировать ? Где

М=ОпЛ„ J=1,2,...,pi J - номер магезино-комплекта; р - минимальное

/ /

число магазино-комплектов. При.этом |*|<д,, где q, - емкость инструментального магазина J-ro станка.

Сформулируем задачу в терминах теории графов. Для этого дополнительно введем следующие переменные: х,<0,1) - булева переменная, моделирующая использование /-го магазино-комплекта при х*1 (х=0 в противном случае); Ь_<, - полустепень исхода (-ой вершины, достижимой из вершины J, т.е. это количество наименований инструментов, необходимых для обработки (-ой детали, предположительно прикрепленной к J-му магазино-комплекту; S~ = (а , а₂,..., а_ж) -вектор закрепленных полустепеней захода вершин второй доли графа; Р - число вершин третьей доли графа (исходное количество магазино-комплектов). і

Форма

х,-* mtn; (IT)

/=і ^J ограничения

.'я р

Е Е8,Л $ Я,; (18)

^{lJ J J}

S~₂= (a_f, а_г ;-^Vi* V'- ⁽¹⁹⁾

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

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

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

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

Введем дополнительные переменные: N - помер дуги в списке дуг
исходного подграфа, содержащего вершины и_у (магазнно-комшюкт) и
Ю_н (деталь), соответственно 3-ей и 2-ой долей графа; Q, - теку
щее значение остаточной емкости магазина (при отрицательном значе
нии - магазин переполнен) і р_{- пометка 1-ой вершины 2-ой доли гра-т.
.-' Фа (р_{=ї - і-ая вершина помечена, р^О - не покачена); d_t - голу-
. степень исхода 1-ой верппфы 2-ой доли графа (соответствует числу
инструментов, необходимых: для обработки t-ой детали); а, р, S ~
вспомогательные переменные; D - множество вершин второй дола
' графа. . j |

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

Шаг О. Положить: 1=Ц К-0, V,, Qj=Q,- ;

Шаг 1. Положить l=\p\+1. J

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

Шаг 3. Если Vt,t, pt=y, то идти к шагу 5; иначе положить': Qj=S~a, u_n=f, w_n=p, pg=r, fT=ff+f; идти к шагу 1.

Шаг 4. Если pt=J ^л 1>І, то идти к шагу 2. Если pi=f л {=f_f то идти к шагу 3. Иначе если Qj-o<>0, го положить: a=Ot, б=і, S = Qj и перейти к шагу 2. ! Если Qj-бі < 0, то положить: N-N+1, Qj=Qj-6i, t>_N=J,' v>}f=i, р =1, 3=3+1, р=2 и перойти к шагу 1. /

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

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

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

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

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

Шаг О. Положить Я=0, №_K=U EG_K=1.

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

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

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

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

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

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

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

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

- за -

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

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

Рассмотрим постановку! и решение модифицированной задачи на ко-

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

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

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

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

Таблии/л 6.

Времена транспортировки

деталей между станками

Таблица 7.

^mlI4M<^(cV V^х и ⁽²⁰⁾

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

,j%^xtj-*''; . ^(2І)

l -номер вершины исхода; J - номер вершины захода; п - число вэр-

шик исходного графа; с,,- вес дуги графа, моделирующей время тран-

спортировки детали от t-ro .станка к J; о,- вес j-ой вершины графа,

моделирующей время обработки детали на одной операции; х_{ ==(0,1).

Для решения поставленной задачи воспользуемся математическим

методом замещений, ориентированным на решение задач на графах. В

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

7 в табл.8 дуг исходного урафа, упорядоченных По возрастанию весов

2, являвшихся суммой времен транспортировки деталей между станками

и между станками и складові t_T и времен выполнения отдельных опера-

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

чертой 10 верхних элементов списка, как наиболее "легких". Получе-

иные 10 элементов списка являются началышмподграфом, тпредставлен-

ным на рис. 4а. Формируем іследупцие векторы закрепленных степеней:

S_M={1,1,1,1, ijil.l. 1.1. М. 1.1,1,1.1,0),. (22)

S₃e(0,1,1,1,1 И,1,1,1,1,1,1,1,1,1,1,1), (23) где S_H - вектор полустепеней исхода и S₃ - воктор полустепеией захода. Порядковый номер компоненты каждого вектора соответствует

і номеру вершины начального подграфа. Значения компонент векторов,

вытекают из ограничения а). /

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

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

/

/

Й-

CO

е. душ 1-3 и 1-. Построив декартово произведение подученных мно-*е*ш» получаем множество пар замещений, упорядоченное затем по ьаэраэшшзе рвзнсшти весов (рис. 5). Первый ярус ДЦЗ сформирован. Вшййййй пару замощений первого узла ДЦЗ 6-12 зачеркиваем дугу N 8 <», І-?) и добавляем пунктиром дугу N 12 (т.е. 1-3). Получен адкуздй ярэкюжутодкнй подграф, который необходимо проанализировать на аеШгечдаеть а недостаточность полустепеней вершин в соответствий е 'Шйорш (22)и'(23).! Поступая далее аналогично изложенному, . ШдучаШ да», содержащее 5; ярусов. Остальные висячие узлы ДЦЗ яв-ляшея Шещрешшюными щбо по прогнозному значению нижней гра-тщ, т$о т шобратямому нарушению топологий. Построив про-нежушші подграф, $ор^фованный на пятом ярусе дцз, имеем сба-латировшаш га іршчЦию а) технологические маршруты для всех ярех кшшошвй деталей! т следует из содержимого строки "Ба-. аане* й ЯВШэи чаота рщута 46 - число задействованных станков на ка*д«й вдаращш Ш іфшгашЬт 1, Однако, из столбца "Баланс" в пра-йэ8 чаете риеуша еледу^тічіо ш ограничению б) технологические щрруш и е&ашшрешшґі, *,к, охтох 4 должен обрабатывать три тчъшь a ешш \ іш@ще щ задейатеавая. Лая БЩ по ограиичени-т Щй ш) »да$ iqpssMStats шчвкуиташцда еш*у вержаята йшда~

Одаоеть шмаеййшамюй-езшш вйзшвшк зювцшШ еводатся к &яШц8Яй» еджА щродзд е вд&почяэд таршаТіш (в»сом) на другу»''' вертану, е4аадмщ» ъщ^жютяш тщатчут (весом). При этом «втоматйчвйОй э?А*эдашга шаддамтшэ ъжаъттм вершинам дуги. & Найём йлуч&е іш^жважеде* Ей|шатг$ш «кюдагся данные столбца "Ба-.«аке*\ йхйй«щйй а м|>едш е-кашщй, аадшшых ограничением б). S&mwn йіїйчєшайЗ «каЗДїч>#і щра«а':ф 3 для станка 4 и .параметр О

Склад0 ' у

і Ф 0/7

/ . '(g)

(V /

(То) (Ті)

/

^п і, гі ^п-^у ,_г «на _3а^п~^у 0,э га У

«)

п о_п о_гі н-у о,;, n_sa о_за п-у о,₃ о_ЙЗ У

Склад (і,і (?; С, Д (?) (*'j\-

з \ .. /

^Сд ' К /
0, . V)

_ft

(

7 V

Оіз)

( 1н) . . '\is сіл- ifi.

дана

П 0,, o_a, П-У- о_1Й o_BB 0_3g П~У 0„ 0„ У

1 і

'13 "23

(7 .

Т?, ./ . (із) ./ .

б,

Склад Ґі ^ с.

Чг~

.і о, ., и

(Пу

(u) 'icy

in

Ба-

лана

2.'

Балоне

1 і

1 1 1 Гис.4.

'В)

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

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

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

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

ох-
минимизировать Е ^u^ij' ^4)

при ограничениях Ez.,=a,, 1-1,2i...,G; (25)

J=i -

ZS^^iZbj , Jf1,2,...,M; (27)

Еу.,-п' , Uf,2,...,G; (28)

^; ' . 1---.- .-

где t - тип операции; / -(номер станка; С₍,- стоимость выполнения

{-ой операции на 7-ом станке; t - длительность операции t-ro типа на J-ом станке; а_е- необходимое число операций типа 1; о - фонд рабочего времени J-vo станка; Sj-число инструментов, используемое для выполнения операции tl-ro типа; I,- емкость инструментального магазина (локальный складу) у J-ro станка; п - максимальное - чиелс-станков, способное выполнить операцию операцию t-ro типа; z_tJ- число операций типа I, которое необходимо выполнить на J-ou станке;

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

^J і . I

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

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

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

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

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

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

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

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

Для формализации, задачи на графах введена булева переменная

x_lJ, Если с-ни тип операции выполняется на /-ом станке, то г =1,

а в противном случае, х₍ .=0.

Целевая функция принимает вид .-*''
, а м
минимизировать Т.О. ,х. ; (29)

а
при ограничениях Е і₍,і,,ф,, J=1,2, .....Jf; (ЗО)

ES_(Ji_(j^ , J.I,2....,Mf . (31)

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

-544 с. '."'..".

j - номер станка; C_t,- стоимость выполнения t-oft операции на.
j-au станке; "t_t,- длительность выполнения -ой операции на /-ом
станке; а_{- необходимое число операций типа ( для ДСЕ определенных
объемным планом;, b,- фонд рабочего времени J-ro станка; 5₍-число '
инструментов, необходимое для выполнения (-ой операции; Lj-
емкость инструментального магазина (локальный склад) у 7-го 1 стан- -
ка; ?

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

о. и L, і

J J і ; ;.

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

І і

шать с такой ке точностью.! Вершины третьей доли моделируют стенки

и характеризуются фондом рабочего времени Ь.. Ребра, соеданяидие

вершили первой и второй долой, моделируют закрепление ДСЕ !за

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

графа, моделируют суммарную длительность !T_t,=a_t*t_t,.

Значения компонент векторов (3) и (4) вычисляются следующим'

образом. Для верапан первой доли графа компонента о. вектора (3)

ривна числу необходимых тгаїов оігераций в соответствии с технологи-

чоскпм маршрутом. Степени вершин второй доли графа, моделирующей

iwim технологических ")Порйч;-"^г! с-лп?долятся числом ребер, исходами

і'.н нерпой дол;: ч инцидентных дагаюй вершине. Вершины третьей доли

-.- 49 -

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

Aj*m-M+1; a.j=1. . (32)

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

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