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

л

Р Г Б ОД9Н1ВЕРС14ТЕТ ВНУТР1ИН1Х СПРАВ ИБС 9КРА1НИ

1 й СЕН Т905'

На правах рукописд КОСТ1КОВА МАРИНА В0Л0ДИМИР1ВНА

КОМБIНОВАН1 АЛГОРИТМ« УПОРЯДКУВАННЯ РОБ1Т 3 БАГЙТОСТАД1ИНИХ ВИРОБНИЧИХ СИСТЕМАХ 4 дискретного типа

Спец1альн1сть 05.13.01 -

Системний анал1з 1 теор!я оптимальних р!вень

Автореферат дисертацП на здобцття надкового стдпеня кандидата технШних надк

Харк1в - 1995

ДисертаЩею е рукопис.

Робота виконана у Харк1вському дернавноку автомоб1льно-дорож-ньоку техШчному ун1верситет1.

Науковий кер!вник:

доктор техн1чних наук, професор Канцедал Серг1й йндр!йович. 0ф1ц1йн1 опоненти:

1. доктор технШних наук, професор Петров Едуард Георг1йович;

2. кандидат техн1чних наук, доцент Дан1льченко Олександр Михайлович.

Пров1дна орган1зац1я - 1нститут проблем машикобудування ЙН Йкра1'ни.

Захист в1дбудеться року о на

засЦанн! спец1ал1зовано!' вчено1' ради К 02.24.03 в Ун1версите-т1 вндтр1вн1х справ МВС Якра1'ни за адресов: 310080, м. Харк1в - 80, проспект 50-р1ччя СРСР, 2?.

3 дисертац1еп мовна ознайомитися у б1бл1отец1 Ун1верситету внутр1мн1х справ МВС НкраШ.

Автореферат роз1слано 1995 року.

Вчений секретар ¿^Юир^-*^- 1.В.Ар1стова

спец1ал1эовано1' вченоТ ради

- 3 -

ЗАГАЛШ ХАРАКТЕРИСТИКА РОБОТИ йктуальн!сть проблеми. Багатостад1йн1 виробнич! системи дискретного типу складавть основу промислових Шдприемств ка«инобуд1вного комплексу. Объективно - це традиц1йн1 або гнучк1 автоиатиэован1 д1льниц1 механообробки деталей, як1 являють собою розпод1лену в простор1 сукупн1сть мавин, «о об'еднан1 транспортним зв'язком I якими керупть люди. В дискреты! моменти часу на вх!д системи надходить ск1нченна мно-вина предмет1в (деталей), кожей з яких на мавинах системи повинен пройти к1лька посл1довних стад1й обробки, «о визна-чаються технолог1ев його виготовлення.

Яправл1ння процесом виготовлення предмет1в у так!й систем! полягае у виробленн! програми використання мавин у час! та в!дпрацпванн1 ц1е\' програми на основ1 принципу зворотного зв'язку з П корекц1еп в дискретн1 моменти так, щоб вих!дна мно«ина предмет!в була виготовлена в заданий пром1вок поточного часу. По сут1 як початкова, так 1 скоректован1 програми управл1ння являвть собов розклади використання мамин. як1 визначавться порядками, во формупться, обробки предмет1в на цих мавинах. В реальних умовах п!д д1еп багатьох випадкових Фактор1в, цо зривавть регулярну роботу макин, вказана мета управл!ння досягаеться формуванням таких порядк1в обробки гредме?!в на мавинах, як1 визначапть найб!льв повне (без не-виправданих гтростоУв) 1х використання у час!. У свои чергу ця вимога виконуеться т1льки тод1. коли складений розклад мае найменву доввину. Тим самим проблема оптимального управляя виконанням роб 1т у багатостад1йн1й виробнич!й систем! дискретного типу зводиться до пер1одичного вир1вення проблеми оптимального упорядкування вс1х роб 1т, ко виконувться ма-ииками ц!е1' системи.

В д1ючих виробничих системах вир1вення проблеми оптимального упорядкування роб1т зам1нпеться процедурою Ух поточного розпод1лу, яка зводиться до того, цо пер1одично в дискретн! моменти часу планувальник роб1т призначае списки предмет1в, як1 повинн1 обробити мавини системи в черговий пром1жок часу 11' Функц1онування. Можлив1сть такоУ заи!ни за-безпечуеться зб1львенкяи к1лькост1 паралельно д1ючих мавин, навмисним завиценням тривалост1 стад!й обробки предмет1в, змуиеним подовженням периоду Ух виготовлення 1 спираеться на тривалий досв1д та спец!альн1 знания планувальника системи. В результат1 назван1 фактори пом1тно знижують ефективн1сть виробничоУ системи, цо проявляемся в неповному вико{Гистанн1 мавин, подов«енн1 пер1оду виготовлення предмета та п1дви^ ценн1 Ух вартостЬ У зв'язку з цим описаний режим управл!ння системою повинен бути зам1нений б1льв рац!ональним, який дозволяв би усунути вказан1 недол!ки вляхом використання оптимального упорядкування роб1т. Б1льв того. гнучк1 автоматизо-ван! виробництва (ГАВ), цо йдуть на зм1ну традиц1йним вироб-ничим системам, ставлять проблему зам1ни режиму поточного розпод1лу роб1т б1льв загострено: дороговарт1сн1 центри обробки, во складають основу ГАВ. для того, цоб бути економ1ч-но виправданими, вимагавть максимального завантаження та уз-годження Ух роботи у час!, цо без застосування вказаних ме-тод!в упорядкування роб 1т практично не мове зд1йснитися.

Не зважапчи на практична важлив1сть розв'язакня пробле-ми оптимального дпорядкування роб 1т, цо виконуються багато-стад1йною виробничою системою, запропонован1 алгоритми упорядкування не в!дпов1дашть вимогам практики, а саке: можли-вост! розв'язувати точно задач! упорядкування в реальному масвтаб! часу. Це поясняется суто переб!рним характером за-

дач1 оптимального упорядкування роб!т, цо вимагапть пер! за все поиуку та обгрунтування ефективних схек обмеження перебору порядк1в виконання роб1т 1 розробки на *х основ! ефек-тивних алгоритма упорядкування, що реал1зувться на сучасних ЕОМ.

Робота виконана на кафедр I 1нформатики ХДЙДТН зг1дно з госпдогов1рною тепою N 52-07-89 1з заводом "Кондиц1онер" См. Харк1в) "Розробка ППП "Календарне планування виробництва для персональких ЕОМ (ПЕОМГ, К Г.Р.01.890005937.

Мета роботи - п!двицення експлуатац!йних характеристик багатостад1йних виробничих систем п!дприемств мавинобудуван-ня (ступ!нь використання мавин, пропускной здатност!, еконо-м!чност1) засобами математичного моделивання, розробка та досл1дження ефективних алгоритма упорядкування роб1т, що виконуються такими системами, створення програмного забезпе-чення для автоматизацП процес1в управл1ння виробничими системами на баз 1 ЕОМ.

Для досягнення мети були поставлен1 1 вир1мен1 так1 ос-новн! завдання: I) систематизац1я та огненна теоретичних I практичних результат^ у галуз1 розробки алгоритм1в оптимального упорядкування роб!т в 1деал1зованих та реальних ба-гатостад1йних виробничих системах; 2) конструввання набор1в алгоритм^, чо вир!вувть проблему упорядкування вляхом за-стосування ефективних схем обмеження перебору; 3) системати-зац1я алгоритм1в, 1'х теоретичний та чисельний анал1з, щоб в!д1брати алгоритми, цо найб1лы придатн! для практичного застосування; 4) розробка та анал1з алгоритма, що вир1вувть проблеми упорядкування роб1т в реальних виробничих системах; 5) розробка ППП, цо реал!зувть алгоритми упорядкування роб1т на 1ВМ-сум1сних персональних компьютерах»

- б - •

Наукова новизна. Нов 1 науков1 результати, викладен1 в дисертацП, полягавть у розробц1 та обгрунтуванн!: 1) набору ефективних комб1нованих алгоритме, ко пов'язуить "загальну задачу упорядкування з високов точн!стю та «видк1стю; 2) ви-значенн! теоретичних 1 робочих характеристик розроблених алгоритме - Их чзсовоГ 1 емк1сно1' складност!, а такой точнос-т1 розв'язання задач упорядкування, включавчи алгоритма для високопродуктивних багатопроцесорних ЕОМ: 3) набору-алгярит-м1в, но призначек! для вкр1«ення реальних проблем упорядкування I враховують групування машин та можлив1сть 1'х перенз лагодження.

Достов1рн1сть 1 обгрунтован1сть результат^ ро^оти Шд-тверджувться коректник застосуванням математичниго апарату, що використовуеться для доведения власти1-остей алгоритма, узгодвен'^тя встанозлекях властивост^^ з результатами екс-перименту.

Практична ц!нн1сть. Викладен! у дисертацП' результати е науковою основой проектування одного з головних блок1в авто-матизованих робочих, м!сць планувальник1в кеханообробних д1льниць. чо е нев1д'емним атрибуту ГйВ п1дприемств мавино-Счд1вноТ галуз!, як но», юс, тл:< 1 тих, «о реконструвйться. Також вони можуть бути використан! п1д час удосконалення управл!ння традиц1йними д1льницями вказаних виробництв.

Реал1зац1я 1 впровадження. Найб1льи точн1, мвидк1 й економн1 подо потр1бно!' пам'ят1 ЕОМ алгоритми впорядкування роб1т реал1зован1 у вигляд1 пакета прикладних програм "Роз-клад", чо призначений для використання на 1ВМ-сум1сних пер-сональних комп'втерах. Пакет передано заводу "Кондиц1онер" (м. Харк1в), Економ1чний ефект в!д впровадження роэробок склада« 60,319 тис, крб.

- ? -

Конкретна особиста участь автора в отриманн1 надкових результат^. Дисертац1йНа робота Кост1ково1' М.В. е самост1й-нов науково-досл1днов роботов. Автор особисто виконав: сис-тематизац1ю й оц1нювання теоретичних 1 практичних рездльта-т1в д сфер 1 розробки алгоритм1в оптимального дпорядкдвання роб 1т в 1деал1зованих 1 реальних багатостад1йних виробничих системах; констрдювання набор1в коыб1нованих алгоритма, *о вир1иують проблему дпорядкдвання вляхом застосдвання ефек-тивних схем обмеяення перебору; систематизац!ю алгоритма, 1'х теоретичний та чисельний анал1з, «об вЩбратк алгоритм«, як1 найб1льв придатн1 для практичного застосдвання; розробку й анал!з алгоритма, по вир1идвть проблема дпорядкдвання ро-61т д реальних виробничих системах, розробку пакет1в при-кладних програм, чо ре,ал1эувть алгоритми дпорядкдвання роб1т на 1ВН-сум1сних персональних комп'втерах.

Теоретичн1 дослЦяення, «о м1стяться у дисертац1йн1й робот 1, пЦтверд*ен1 обчислпвальними експеримёнтами.

Стдп1нь обгрднтдвання наукових полояень, висновк1в 1 рекомендац1й, сформульованих д дисертацН. Дисертац1йна робота базуе'ться на сдчасних п1дходах 1 результатах теорП' об-числень 1 моделввання.

Для виконання завдань дослЦяення за/учалися в!дом1 по-лояення й результати з теорП мнояин, комб!наторного анал1-зу, теорП' обчислювальноГ складност1 алгоритма, теорП' роз-клад1в, метод1в програмування та кснструювання пакет1в при-кладних программ (ППП).

йпробац!я роботи. Основн! результати досл!дяень допов1-далися й обговорювалися на надково-техн!чних конференц1ях профвсорсько-викладацького складу ХДЙДТН, на обласн1й конфе-ренцП "Досягнення вчених - народному государству" (м. Хар-

К1В).

Публ1кац1*. Основн1 результати дисертацП опубл1кован1 у 6 наукових роботах.

Структура й обсяг дисертацП. Робота складаеться 1з вступу, п'яти розд1л!в, заключно!' частини, списка л!тератури 1з 136 назв, двох додатк!в обсягом 49 сторшок, м1стить 11 рисунк1в та 25 таблиць: усього 245 сторШок.

ЗИ1СТ РОБОТИ

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

первому роздШ проведено анал!з багатостад1йних ви-робничих систем дискретного типу, викладен1 формальн1 проце-дури вдосконалення керування виробництвом. в результат1 чого отриман1 загальн1 висновки про досягнут1 результати у вказа-н1й сфер 1, сформульован1 завдання досл1дження.

Я другому роздШ мовов ор!ентованих граФ1в викладене математичне формулювання загально1' задач1 теорП розклад1в, яке представляе П як екстремальну задачу коиб1наторного типу. Викладена концепц1я ефективного обмеження перебору роз-в'язань загалько! задач1 теорП' розклад1в: вид1лення Шдмно-жин допустимих розв'язань задач1 малоХ потужност1, елементи яких за довжиною розкладу або абсолютно, або статистично не перевищ/пть елекенти ревти множини допустимих П' розв'язань. Викладен1 алгоритми побудови допустимих розв'язань загальноУ задач!, а також описан! обмежувальи! алгоритми, цо скорочу-

ють переб1р конб1кац1й. Обмевення перебору трактуеться як побудова деякого пЦдерева С э 1стотно менвов к1яьк1ст!1 листка, н1ж у повного дерева Б. Три алгоритм, во реал1зувть принцип обнеження перебору, представлен1 у вигляд1 фрагмента загального алгоритму 2.2, який Формуе допустиме розв'я-зання.

Алгоритм 2.4 дозволяе побудувати множину компактних

розклад!в (у побудованому розклад1 н1 для одно! машини, н1

один 1нтервал П простоювання не моще бути використаний для

виконання роб1т вляхок И перестановки - змЦення в1ссю.часу

вл1во - без змЦення вправо початку виконання ревти роб!т).

Алгоритм будуе п1ддерево 0 так, ко в кожному вузл! й не роз-

глядаються т1 г1лки, як1 в1дбивавть роботи, ко починавться

п1зн1ве, н1к найб1лы ранн1й момент завервення деяко1' роботи

з множини претендент1в.

Алгоритм 2.5 дозволяе побудувати мкожину компактних

розклад1в т1еУ найменво! потужност!, як1й завжди належить

оптимальне розв'язання. Суть полягае в тому, що у кожному

вузл1 0 розглядавться роботи, що виконувться мавиною д € О,

ь

яка визначена значениям II _ , 1 починавться ран1ве за момент ь и

и,. , де ир - найб1льн ранн1й момент завервення деяко* роботи.

Алгоритм 2.6 дозволяе побудувати множину розклад1в, не затримують. Кожкий елемент ц1е\' множини характеризуемся тим, чо у побудованому розклад1 жодна з готових до виконання робота не затримуеться, як*о маиина для 17 виконання в1льна. Потувн1сть множини розклад1в, во не затримувть, в середньому менма за потужн1сть множини компактних розклад1в, але у за-гальному випадку не м1стить оптимального розв'язання.

Я вказаному розд1л! описан! та досл!джен! алгоритми на-

ближеного розв'яэання задач1 однократно1' д 1V, в результат! чого п!дтверджено, «о найкрацими за величиною середньо! по-хибки е пр1оритетн1 правила NOPNR, HHKR/P (N0PNR - вибрати работу того предмета, який мае найб1льиу к!льк!сть роб!т, во не включен1 до розкладу; MHKR/P - вибрати роботу предмета, для якого максимальне в1дновення суиарноГ тривалост1 вс!х невпорядкованих ,операц!й до тривалост! операц1й, ко включа-еться до розкладу).

1 третьоыу розд!л! викладен! комб1нован! алоритми точного 1 наближеного розв'яэання эагально!' задач1 теорП' роз-клад1в, ко побудован1 на баз! обмежувальних алгоритм1в.

В якост1 точного алгоритму 3.1 запропонований 1тератив-ний алгоритм, ко реал1зуе схему г1лок 1 меж на дерев! перебору D, яке можна отримати за алгоритмом 2.5, ко гарантуе побудову п!дмножини розклад!в мало! потужност1 1П . яка м!с-тить розклад м1н1мально1' довжини U . В алгоритм! використо-вуеться нетрудом1стке з точки зору обчислювання оц1нивання нижньо* 1 верхньо! меж! довжини розкладу.

Ö пер«!й груп! комб!нованих алгоритма запропонован! чотири наближених алгоритми 3.2 - 3.5, отриман! «ляхом спро-кення точного методу, один з яких (3.2) гарантуе отримання розв'яэання з будь-яков заздалег!дь заданою точн!ств.

Використання комб!нац1й алгоритм1в (обмежувального 2.5 та однократного 2.8) дае змогу вукати. краке розв'яэання задач! на попередньо побудованому г-ярусному п!ддерев1 Dx <= D^ для чотирьох алгоритма друго!' групи (3.6, З.бй, 3.7, 3.7ft). .

Самост!йну (трети) трупу комб1нованих алгоритм1в складавть алгоритми, отриман! комб!нац1ею однократного алгоритму 2.8 1з спец!альним методом покрачення о.триманого за цим ал-

- и - , . ..

горитмом початкового розв'язання задач1. Не алгоритми 3.9, 3.9А.

Для вс!х запропонованих алгоритма розроблен! й описан! паралельн! 1"х Bepcll' 3.1П - 3.8Í1, призначен! для реал!зацП на К-процесорн1й £ ОМ 1з сп1льною або розд!льнов паы'яттп з метоп скорочення часу розв'язання задач!.

У вказаному розд!л1 представлен! теоретичн! характеристики комб1нованих алгоритм!в набливеного розв'язання загаль-hoí задач1 теорП' розклад1в. 0триман1 оц1нки часово! та ем-KicHoí l'x складност!, а для набливених алгоритма - похибки розв'язання задач.

Основними обчислювальниыи операц!ями алгоритм!в е опе-рацП пор!вняння та додавання. По в!дновенню до сдыарного числа цих опера!й, цо виконуються алгоритмами в найПрвому раз!, доведено, цо: I) алгоритм 3.1 точного розв'язання -експоненц!альний; алгоритм 3.2 залевно в!д задано* похибки розв'язання моке мати експоненц!альну та пол1ном1альну

складн1сть; складн1сть алгоритм!в 3.3 - 3.5 - пол1ном1альна, з

ОС К ), де N=n*n - розм1р задач!, цо розв'язуеться; 2) ком-

б!нован! алгоритми друго!' групи е експоненц1альними цодо

к1лькост! ярус1в г дерева D^ , для алгоритму 3.6 - ОС Я %ti*

г " i ,£.1-1 г

* N ), для алгоритму 3.7 - 0( V *л * ц ), а при г =

= const складн!сть алгоритму 3.6 - ОС N г ), алгоритму 3,7. -

ОСх) * N^"), де 0 - к1льк!сть реал1зац!й алгоритму 3.6, Л -

середня к1льк1сть дуг, цо виходять э ковно! вервини г-ярус-

ного п!ддерева перебору D^ ; 3) складн1сть алгоритм!в 3.9,

3.9ft - 0( и) * R1" ), де lo - к1льк!сть 1терац1й алгоритм1в

2.3, 3.8; при со = Н - ОСИ ).

Емк1сна складн!сть алгорити!в визначае залеян1сть об'е-

му оперативно!" пам'ят! ЕОМ, яка потр!бка для збер!гання ви-

х!дних, npoMlsHHX та результувчих даних эадач1, що розв'язу-еться, в1д YY розм1ру 1 розрахована на п1дстав! структур програм, як! реал1зують алгоритми. Встановлено, s¡o емк1сна складн1сть алгоритму 3.3 - 0(N); таку а емк!сну складн1сть мавть алгоритми 3.6, 3.?; алгоритм 3.9 мае емк!сну склад-н!сть 0(N г).

Гарантоване абсолютне й в1дносне оц1нювання похибок на-ближених алгоритм1в являе собою позитивно визна'ч^н! функцП' Ад (М), А (К), значения яких не мояуть бути перевищен! в процес1 розв'язання задач цими алгоритмами. В1домов вельми грубою гарантованов оц1нкою однократних алгоритма, цо буду-пть розклади з мнояини . е функц1я А,(Ю = и - 1, тоб-

* о

то (L - L* )/L* = в - 1, зв!дки L <= n * L* . Б1льм точн! оц1нки мокна отримати, визначивши верхн1 Meil довяин макси-мальнкх влях1в ацикл1чних граф!в 6. •

Пехай заданий граф 6 = (I , l .ip.U^.Hj), що визначае вих1дн1 дан! задачК Шлях максимально! довжини з вериини i у вершину i на цьому граф1 визначаеться за вира-

V j *

зом = яах (L . ) по i Е I, де L. = У ,1 = 1,2,

I U t

.... n - час обробки 1-го предмета без затримок виконання

його роб1т. В ацикл1чному граф! G вид1лимо п1дграф = <1г,

ís . íF , , HR ), = ü\ür , НR :Vft -> R * (J{0), припи-

сувчи дугам значения тих вериин, з яких вони виходять у гра-

Ф1 G. Довжина максимального шляху з вериини у вершину i,.

п!дграфа G визначаеться виразом L. = яах { L,, > по q G Q,

гГ. R Ч

де L = ) t¡ . , q = 1, 2, ..., в - час зайнятост! q-Y c¡< р-1- р ь

мавини без просто1'в niд час виконання ней yclx Рл роб 1 т.

— v

Тому що максимальний илях U4 ацикл1чного графа G у загаль-ному випадку утворюеться дугами э мнояин та VR , тобто UK = Uj , його доэяина зниэу'обиеяена величиною 1Ы -

-шах (Ьг , ), «о е точной нижньою межев довяшни розкладу.

Припустимо, максимальний шлях иц на граф! & утворений ус!ма дугами 1з мнонини дуг и1 , и ,цо визначавть довжини олях1в 1Г , . Тод1 + + ДЬ, де А1 < 1г , 1р -апр1ор1 нев1дома величина, е верхньою меяеп довжини розкла-ду, тобто I <- Ьг+ +А1. Враховувчи, «о довжина оптимального розкладу задовольняе нер 1 вност 1 вах ([.- , Ь й ), отримуемо Ла : I - 1т + + Д I - вах (Ь г , 1Й ). Л^ = (Ь - I* )/Ь* <= ((1Г+ I. + ЛЬ) - вах ат, I ))/шах(1_ , ), «о характеризуют ус 1 наближен1 алго-

К Т |ч

ритми, як! розв'язують задачу як поиук мШмалького значения максимальних шлях1в граф1в £ 6 Л .

Прав! частини наведенних нер!вностей можна вважати га-рантованими оц!нками абсолютно!" та в1дносно!' похибок алго-ритм!в т!льки в тому раз1, якцо АЬ кожна виразити через параметри задач!'. Разом з тим отриман1 сп1вв1дноиення вельми зручк! для анал1зу похибки алгоритм1в: вони дозволявть прог-нозувати 1"!' зм1ну, якцо вар1ввати розм1ри задач1 та сп1вв1д-новення и!ж И параметрами п, и.

Очевидно, то 1з зб1лыенням розм!ру задач! N = п * в зб!лы»уються значення Ьг , , Д I. При цьому величина Л I зростае за рахунок зб1львення к1лькост1 простоев б!ль-вого числа машин, цо виконувть б1льву к!льк1сть роб 1т. 3 цього вит!кае, цо права частика другоГ нер1вност1, яка виз-начае в!дносну похибку розв'язання задач!, 1з зб1львенням II розм!ру зростае. Для одного й того ж самого розм1ру задач! в1дносна похибка алгоритму максимальна 1 дор1внюе 1 +Ль/1Т або 1 + АЬ/Ь в тому раз!, якщо Ь =.1, , що характерно

.к г к

при п ~ в. 1м1н1мальна й дор1внюе А 1/Ь , якщо I >> [, .

Н I

цо характерно для п >> в. Отже, похибка наблияенчя алгорит-

Miß 1з зб1льиенням розм!ру задач! зростае. При n/m - const алгоритм« бIльш точно розв'язувть задач1 малих розм!р!в.

И четвертому роздШвикладен! характеристики алгоритм!в точного 1 набликеного розв'язання загально!" задачи отрииан! ексгсериыентальним шляхом. Визначен! мета, завдання. методика п1дготовки й проведения експерименту. Огриман! емп!ричн! за-ле;*ност1 часу i точкост! розв'язання задач! запропонованиии алгоритмами в!д ïï роз«1ру.

Експериментальне досл1дкення алгоритк!в точного 1 набликеного розв'язання загально!" задач! зроблене з метою отрицания робочих характеристик алгоритма, пор!вняння ïx з характеристиками, цо отрииан! анал1тичним вляхом, остаточноУ систематизацП алгоритма 1 в1дбору тих 1з них, як1 можна було б застосувати як базов! для побудови алгоритм1в, що р-озв'язувть задач1 упорядкування реальних виробничих систем. Монкретн! завдання експериментальних досл!джень полягали у тому, щоб отримати статистичн! оц!нки точност! 1 часово! складност1 алгоритма, а також залежност1 ïx точност! та часу виконання задач! в1д ïï розм!ру Nv Експеримент Шдготов-лено й проведено за спец1альною методикою, яка включае про-грамування алгоритма, к1льк!сний 1 паракетричний п!дб!р задач для розв'язування, чо забеэпечуе можлив!сть прийняття правдопод1бних статистичних висновк!в «одо властивостей об'ект1в, чо вивчавться, розв'язання задач на ЕОМ ! статис-тичну обробку,випадкових величин похибок алгоритм!в та часу викон.ання задач.

Bei програми, як1 реал!зують алгоритми, що досл!джують-ся, складен1 на «ов1 ФОРТРАН , оптим1зован1 на р1вн1 uieï моей чодо ввидкост! та потр!бно!" в ЕОМ пам'ят1. Програми об'едиан! у спец!альний комплекс 1 виконан! на ЕОМ ЕС-1022 в

операц1йноиу середович1 ОС 6.2. Експеримент проведено за такими алгоритмами: 1) точниы 1 апроксиыупчим його алгоритмами 3.3. 3.4, 3.5; 2) набли«еними комб1нованиии алгоритмами дру-го1" групи, чо використовувть в1дпов1дн! комб1нацП обмеяу-вального алгоритму та однократного - 3.6, 3.6А, 3.?, 3.7А; 3) алгоритмами третьо! групи (3.9, 3.9А) з використанням спец1ального методу покрацення початкового розв'язання зада-41.

Сукупност1 випадкових похибок алгоритма та часу вико-

накня задач оброблен! з метой встановлення основних чкслових

характеристик статистично!" сукупност1 та вибору теоретичного

закону, якоыу п1дпорядкована випадкова величина. Емп1ричн1

зале*ност1 похибок Д =М/(Н) та часу виконання задач 1= 14К)

в1 д 1'х розм1ру отриман1 за ввидк1ств зростання середньоУ по-

хибки, за зиеншенням величини середньо!' похибки, за витрата-

ми часу на розв'язання задач.

Встановлено, що середн1й процесорний час розв'язання

задач при зб1льиенн1 розм1ру задач1 N зростае як ступенева 6

Функц1я = а * N . Для 1нтервалу 36 <= N <= 169, значен-

е

ня показника Ь в залевност1 Ь(Н) = а * N не перевицувть

2,22, чо менше за його значения, яке дор1внюе 3, встановле-

ного анал1тичним «ляхом для алгоритма 3.3, 3.4, 3.5; для

алгоритма 3.6, 3.6А, 3.7 значения показника Ь знаходиться в

1нтервал1 1,21 <= Ь <= 1,58, но мение за його значения 2,

встановлекё' анал1тичним вляхом; для алгоритма 3.7А, 3.9,

3.9А Ь не перевищуе значения 3, вдо в1дпов1дае теоретичним

припущенням. Найивидвий алгоритм 3.6 задачу N = 10000 на Е0Н

ЕС—1022 розв'язуе в середньому за 7752 секундк з похибков

38,40Х: цв я задачу найб!льв точний алгоритм 3.7А розв'язуе г

за 1,95072*10 секунд з похибков 31,22Х. За двома параметра-

ии - середньов похибкою 1 середн!м процесорним часом розв'я-зання задач найкрацим визначено алгоритм 3.6.

Досл!двенкя комб!нованих алгоритм!в' показали, во при зб1ль»енн! розм1ру задач! N !'х похибки зроставть як дробо-л1н1йк! Функц11' Д (N) = N * (а * N + Ь),. во в!др!знявться коеф1ц!ентами а, Ь. Йвидк1сть зростання похибок алгоритма р1зна. Встановлена, що при зб1львенн! ярус!в г дерева D^ ! N = const комб1нований алгоритм 3.6 змениуе свою похибку за законом г!перболи А(г) = 1/(с * г + d), а найпридатн1ие водо 1нтенсивност1 зменвення похибки та витрат часу значения г дор!внве 5,6. Якщо зб1львити к1льк!сть 1терац1й 0 , N = = const, похибка алгоритму 3.? зменвуеться за законом г1пер-боли л (О ) =0 /(е * ^ - h), а найпридатн1ве подо 1нтен-сивност1 зменвення похибки I витрат часу значения 0 дор1в-нюе: i <= \) <= 5.

£ п'ятому розд!л! сформульован! задач! упорядкування, во найповн1ве в1дбивавть реальн1 умови функцЮнування вироб-ничих систем типу, який розглядаеться. 0бгрунтован1 задач1 з групуванням 1 переналагодяенняк мавин. 0бгрунтован1 модиф!-кац11' запропонованих найефективн!вих алгоритм!в розв'язання реальних задач упорядкування роб!т. Запропонований для практично!" реал!зацП' ППП "Розклад" з указаниям його основних функц!й, структури бази даних, 1нструкц1! користувача.

Додатки. В додатку 1 (таблиц! !.П - 45.il) зосередвен1 первинн! експериментальк1 дан1 - похибки та процесорний час виконання задач за алгоритмами, що тестувться. Додаток 2 м1стить документи. «о п!дтверджувть впровадкення результат1в досл!двень ! розробок у виробництво та 1'х економ!чний,ефект.

- 17 -ЗйШЧНА ЧАСТИЛА

Сукупн1сть результат^, отриманих у дисертацп, е по-дальшим розвиткои дослЦяень у сфер! побудови ефективних алгоритм^ упорядкувакня роб!т у багатостад1йних системах, як1 е центральним розд1лом теорП" розклад1в, H практичному в!д-ноиенн1 вони слугують для п!двицення експлуатац1йних характеристик виробничих систем дискретного типу манинобуд!вного комплексу через застосувакня програмних засоб1в, розроблених на основ! цих алгоритма, та використання на сучасних ЕОМ. Основн! результат« роботи полягаать у:

1. Дане математичне формулшвання загально!' задач! тео-piï розклад1в, до яко!" иляхок спроцення зводиться проблема упорядкування роб 1т. Ц1 формулювання подають загальну задачу як екстремальну задачу комб!наторного типу, в як!й функц!я, чо оптим!зуеться. - довкина розкладу - визначена на множин1 допустимих комб1нац1й - сукупностей порядк!в виконання роб i т

- иавгинами. Викладена головна концепц1я обмеяення перебору розв'язань задач! шляхом побудування п1дмнояин таких l'ï розв'язань р!зно1' потуаност1, як! мають 1 не мають оптимального розв'язання. Наведен! основн! обмеяувальн! алгоритми, що реал!зупть цю Цею.

2. На баз1 алгоритм!в обмеяень розроблен! комб!нован! алгоритми, цо розв'язують задачу в1дноиення п/ш = 1 з висо-ков точн1стю. В цьому клас! для отримання точних розв'язань задач! розроблено точний алгоритм, цо зд!йснюе поиук розв'язань за схемою г!лок ! мея у инояин1 розв'язань найменшоТ потуяност!, цог м!стить оптиыальн! розв'язання задач1. Цоб отримати наблияен! ïï розв'язання, розроблен! алгоритми трьох труп: 1 ) до nepatoï групи належать комб1нован1 алгоритми. отриман! об'еднанняк одного з обмеяувальних алгоритма

та однократного алгоритму. Алгоритм« ц1е!' групи зд1йснюють

переб!р розв'язань задач1 на мноаин1 потужност! | I | , ио

м!стить оптимальна розв'язання, 1 мнояин1 I I . то його не

«!стить; 2) комб!нован1 алгоритма другой групи використову-

ють ту к комб1нац1ю вих1дних алгоритм!в, але спочатку буду-

ють г-ярусне п1ддерево 0<= Б , пот!« одним з алгоритм^

т. ц,

для вузл1в х(г) е ХСг) виконуеться пошук кращого розв'язання задач!; 3) алго^итми третьо1' групи для пошуку початкового розв'язання задач1 використовувть однократний алгоритм, по-т!м здГйснюють покращення цього розв'язання шляхом обернення дуг критичних шлях!в гр£ф!в 6. но в1дпов1даазть черговоиу на-ближеннв задач!.

3. Для вс!х наближених комб1нованих алгоритм!в розроб-лен! 1'хн! паралельн! вере!!', призначек1 для розв'язання задач на багатопроцесорних ЕОМ з метоп скорочення часу Тх розв'язання.

4. Визначен! теоретичн! характеристики алгоритм1в: \'хня часова та емк!сна складн!сть, а такоа запропонована оЩнка !'х похибки,'яка дозволила передбачити й пояснити зм!ну похибки алгоритма як функцП розм!ру задач! К.

5. На п1дстав1 експерименту 1 статистично! обробки да-них отриман1 експерикентальн! характеристики: емп!ричн1 залежност! середньо"! похибки Г процесорного часу роботи набли-яених алгоритм!в в!д розм!ру задач! та ц! ж залежност! в!д параметр!в алгоритм!в ! ряду розм!р!в задач N. Б результат! встановлено, що ц1 залежност! не суперечать теоретичним характеристикам алгоритма. Зокрема, встановлено, що для б!ль-вост! алгоритм!в апроксимуюч! залежност1 вЦносно? похибки та процесорного часу 1'х роботи 81д розм1ру задач! мають в1д-

А я

повЦно вигляд ДШ = Н/Са * N + Ь), ию - с * К , де а.

13 - '

Ь<1, с < 3. 1 < d < 3. При цьому визкачено, що найточн1-ший наближений алгоритм, розв'язуючи задачу характерного

розм1ру U - 10000, дае середню похибку 31,22% й потребуе

$

процессорного часу С ЕС—1022) приблизно 1,95072*10 с. Наймени точний алгоритм дас похибку 40.93Х, на «о витрачае б!ля 69942687 с'.' •

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

7. Дан! постановки та математичнТ формулювання задач упорядкування, цо найповн1ше враховують реальн! умови функ-ц1онування виробничих систем типу, «о розглядаеться, а саме: сформульован! задач1 з групуванням 1 переналагодяенням машин. Показана можлив!сть використання розроблених алгоритм1в для розв'язання вказаних задач, визкачен! необх1дн1 модиф!-кацП алгоритм1в I оц!нений ступ1нь зб1льиення pecypclB £0М, що реал1зують ц! програми.

8. Результат« досл!даень 1 розробок оформлен! у виглядi ППП "Розклад" для 1Вй-сум1сних персональних комп'ютер1в. Пакет впровадяений у виробничу практику.

Ochobhi результати дисертацП' викладен1 у наведених публ1кац1ях

1. Канцедал C.fl., Кост1кова М.В. Два наблияених алгоритми для загально1' задач1 теорН розклад1в // ACH 1 прилади автоматики. - Харк1в: Видавництво Харк1вського ун1верситету. - 1990. - Вип. 96. - с. 25-32.

2. Досл1д»ення !теративних алгоритм!в р1вення загаль-ноТ задач! теорП розклад!в. Частика 1. / Кост 1 ково М.В,;

Харк. автои.-дор. 1н-т. - Харк1в, 1989. - 17 с. - Б1бл1огр. 3 назв. - Рос. - Деп. в ЯкрНДШП 19.01.90, N 85-9к90.

3. Досл1дяення 1теративних алгоритм!в р1шення загаль-ноТ задач1 теорП' розклад1в. Частина 2. / Кост1кова Н.В.; Харк. автом.-дор. 1н-т. - Харк1в, 1990. - 11 с. - 51бл1огр. I назв. - Рос.- Деп. в ЯкрНД1НТ1 11.04.90, N б?4-Ук90.

4. Досл1дяекня 1тератнених алгоритм!в р!шення загаль-но1 задач1 теорП' розклад1в. Частина 3. / Ност1кова М.В.; Харк. автом.-дор. 1н-т. - Харк1в, 1990. - 8 с. - Б1бл1огр. 1 назв. - Рос.- Деп. в НкрНД1НТ1 11.04.90, N 6?5-9к90.

. 5. ДаслЦяення Иеративних алгоритма р!юення загаль-ноТ. задач1 теорП' розклад!в. Частина 4. / Кост1кова И.В.; Харк. автом.-дор. 1н-т. - Харк1в, 1990. - 8 с. - Б1бл1огр. 2 назв. - Рос,- Деп. в йкрНД1НТ1 II.04.90, N 6?6-«к90.

6. Кост1кова М.В. ДаслЦяення коиб1нованого алгоритму для р1мення'загально! задач! теорП' розклад!в // Наукове ви-дання. Обласна конференц!я "Досягнення вчених - народному государству". Тези допов1дей (березень, вересень). - Хар-к!в. - 1990. - с, 307 - 308.

H.U. Kostikova. Combined algorithms of uorks sequencing in multistage production systems of discrete type. Theses is a manuscript. Theses on submitting for a degree of Candidate of science in speciality 05.13.01 - system analysis and theory of optimum decisions. University of Internal Affairs, Ministry of Internal Affairs, Ukraine, Kharkov, 1395.

A scientific work is defended, containing research, elaboration, analysis of combined algorithms, uhich allow to solve the problems of search type in really operating production systems. The following is determined: the elaborated combined algorithms on the basis of algorithms of limitations solve the set task of ratio n/m - 1 with the accuracy uhich considerably exceeds the accuracy of earlier elaborated algorithms; theoretical characteristics of algorithms, as we 11 as proposed estimation of their error allow to forecast and explain the changing of algorithms error as function of the N task dimension and ratio n/в for the task of any dimension. The results of research and elaborations are given in the application software package, uhich is applied in production practice.

М.В.Костикова. Комбинированные алгоритмы упорядочения работ в многостадийных производственных системах дискретного типа. Диссертация - рукопись. Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13,01 -системный анализ и теория оптимальных решений, Университет внутренних дел МВД Украины, Харьков, 1995. Защищается научная работа, содер«ацая исследование, разработку, анализ комбинированных алгоритмов, позволяющих реиать ' задачи переборного типа в реально действуюаих производственных системах. Установлено, что: разработанные комбинированные алгоритмы на базе алгоритмов ограничений реиаит поставленную задачу отноиения n/m =1 с точностью, которая значительно превосходит точность ранее разработанных алгоритмов; теоретические характеристики алгоритмов, а также предложенная оценка их погрешности, позволяют предсказать и объяснить изменение погрешности алгоритмов как функции размера задачи N и отноиения n/m для задач любого размера; Результаты исследований и разработок воплощены в пакете1прикладных программ, который внедрен в производственную практику, Ключов1 слова: комб1нован1 алгоритм«, упорядкування раб!т, обмеження перебору.