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

РГВ од

М!Н1СТЕРСТВО ВН9ТР1ШН1Х СПРАВ ЯКРАТНИ УН1ВЕРСИТЕТ ВНЭТР1ИН1Х СПРАВ

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

ПОЛОЗОВА ЛОБОВ КИКОЛАТВНА

МАТЕМАТИЧН1 МОДЕЛ1 ТА МЕТОДИ ПРИЙНЯТТЯ Р!ШЕНЬ В ЗАДАЧАХ ЫПОРЯДКЫВАННЯ ДВОСПЕРйШйНИХ ■ РОВ1Т НА ТРАНСПОРТ!

05.13. 01 - Систэнний анал1э та теор1я оптииальних р1шенъ

Ааторефьрат дисертацИ на здобуття наукового ступеня кандидата технЗчния наух

Харк1Б •• 1397

."л;сертац1ею е рлеопмс.

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

Науковий квр1вкик> дохтор техн1чних наук, профвсор ПанХшев Анатол1й Васильйович

0ф1ц1йи1 опоненти»

X. доктор текн!чних паук, профосор Петров Едуард Георг1йович; 2. кандидат техн!чних наук, доцент Кухарев Борис Юхинович.

Пров!дна орган!зац1я - 1нститут проблей нашинобудувэння НАН УкраХни.

на зас1данп1 спеталхзовано! вчено! ради к иг. 29. из в ШЦверситет! внутр1шн1х справ за адресок» 310080, и. Харк1в, проспект ЬС~р1ччя СРСР. 27.

3 дксертац1св ножка ознайеиитися у Ь1бл1отоц1 Ын1ао?ситету внутр1аж1х справ.

Вчоний секретар споц1ад1зовано1' вчено! ради

I А',■■''< ^—-

1. В. Ар1стова

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Траиспорт е зв'язуючим еленентои в склаян!й систем! взаемодИ' р!зноиан1тних виробниитв. Автокоб!льния транспг^т наЯб!льш розповсюджений в переведениях ваитаж!в, без "v.n-'o неможливе Функи10нування будь-яко! економ!чно* систв.ги.

ЕФективн1сть роботи трэнспортноХ системи заложить в!д р1шень, то приймаються на атапЬх календарного планучання 1 оперативного управляй*. Сучасния р!векь управл1н№1 будь-якою тетичною системою пе^едбачае розробку на п1дстав! системного п!дходу як!сних плановик р!швнь за в1дпов!дний час, п!двишення оперативност! 1 "нучкост! 1х прийняття.

Вдосконале.ння планування в транспортних системах в;та-гае поширення клас1в задач, шо можуть бути ефективно раэв'я-зан1 за допоиогою сучасного иатеяатичного апарату. Для • влн-тажного транспорту типовими с задач1 на "вузьк1 м1сця". До Хх числа в1дноситься проблема неуэгод*вност1 вЬкойання роб1т у час1.

i Дискретний характер транспортних роб1т, обмежен! можли-вост! транспортних систем вииагають упорядкування ванта*<но-транспортних onepauln у простор1 1 у час!. Задач! тачого роду успХшно роэв'язуються натематичнин апаратои теорП прийняття р!шзнь.

Природа транспортних роб!т доэаоляс усп1шно поделювати трзнспортний проиес в терм1нах Teopii розклая!в, проектувати • ефективн1 алгоритяи упорядкування onepaulfl э леревеэення вантаж!в,

Н загальн1й Формул1ровах дисертац1я нрксвячена роэ-робц! математичних моделей та метод!в ро?в'яэаннг задач упо-

рядкування дв эоперацИших роб1т у сист«н1 1+М машин. У транспортн!й !нтерпретаи!5! ив с проблеяв часовоХ узгодженос-т! роботк а[>тоиоб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в, одержаних V напряику розв*яэання задач досл!дження>

б) застосування системного п!дходу до розв'язяння за-аач досл1джусиого класу. виб!р 1 обгрунтування иатенатично-

го оларату розз'язання задач, розробка иатеиатичних моделей задач досл1джэння а терм!нах тео?12 розхладХв;

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

Нэуковв новизна. Каикова новизна та значимость результате досл1джепь тклягас у каступнову.

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

2. Розрсб^эно матакатичн1 иодел" задач координат* роботи казэктажузалъко-розза.чтажуБальних 1 трэнспортних зя-, соб!в з терминах тэорИ роэхлад!в, фориал1зованс задач! у вигляд1 класи©1каи1Яних Формул.

о. Зизкачена оц!нка обчислювально! склапностГ задач часовой узгоджэкост! роботи автоноб1лъного транспорту 1 на-вантажувально-рсзвантажувальних засоб!з.

4. Встанозлен! властивост! ог.тинальних а»-до иаидкодИ розклад1в задач координации роботи навантажувально-розванта-жузального коиплехсу 1 аатомоб1льного транспорту.

5. Розроблен! патекатич.ч! нетоли розз'язання задач »по-рядхузакня двооперэц!йних роб!т в систем! 1+И маиин. ниэка-чеч! частинн! зипадки загальноХ постановки задач!, ио роз-з'кзуються за пол!ном!альний час.

в. До;:л1д>кеко ефективн1сть запропонованкх иатеиатичних Ч0тод1в розр.' яэлння за^ач упоряякування двоопераи1йних роб1Т у систем! 1+М ишп, одержан! анал1тичн! та експе-

риментальн1 ол1нки.

Достов1р <1сть 1 обг!>»нтован1с1ь результат!» роботи п1дтверджуеться систеяним п1дходои до поставлено'! проблеми. коректнии застосуваннян сучвсного иатематичного апарэту, шо використовуаався для доведения топретичних реэультат!в робота, узгоджен1стю теоретичних результат1в э рэзультатаии ых-спериментхв. Для розробки иетодхв розв'язэння зздач дос-л!дження залучалися в1дои! положения 1 результати з i«oplI розхлад!в, теорИ обчислювально! складност1 алгоритн1в, коп-61наторного анал1зу, Teopi'i множии.

Практична ц!ннЛсть результат!в складаеться з можливост1 Хх використання' при опрашованн! 1 впровадженн! l.u--;тек календарного планування i оперативного управления на трзнorwpTi.

Розроблена модель ресурсов 1 роЫт мае ун 1вирсальм*.й характер 1. кр!и транспортной 1нтерпретаи15£, ноже бути . с' niiMO застосована при опрацюваннх систем управления гнучки-ки автогс-тизованиии сисденаии для п1дприснств э дискретпим характеров виробництва.

Ре^.л1зэц1я i впровэдуяння. Викиноне пуогрзмна реал!зац!я запропоноваиих нате-матичних матод1в в середовищ! проблеино-ор1ентованого пакету One Plus М Machine, призначе-иого для класу задач упорядкубйпнй дйоетапних робхт в сгс-теи1 L+M нашин.

Цей пакет було впроваджено на автотранспортных п1дприемствах мхета Харкова.

ftnpo6auta роботи. Натер1али диселтацШш! роботи обго-воряаалися на Всесоюзн1й науков1й конОеренцП "Модел.овання процесёв управления траиспортниии систогоиа" (.»,. Кладивосток,

1989 р.), на Всесоюзны'îtoHÇiepeKUÎÏ "Teopia i практика зас-тосування эхонон1чних засоб!в господарювання у пронисловост." та на автопоб!льнону транспорт!" (к. Суздаль, 1990 9.1, г. . м!жнародн1й науков1й xoHÇepûHulï "Сучасн! транспортк! ¡.- : -лени" Си. XapKla. 1996 р.).

Публ1;-,дaiï. За текою дисертац!Х опубл!ковано ? друхова-них роб!т.

Особистий аиесо& .втора. Ус1 результати яисертац1йИо^ роботи отриманэ за особистс» участя азтора. У лрацях, папя-саних у сп1вазторстз*, дисертантоз! калежиты £13 - розробка натенатмчноХ кодел! посл1довно-паралэлького упорядкувания; С2,3] - анализ обчислюзалъмю"! складност! задач упорягхув;-';.!« ДЕОвтапних ро51т, зизначеиня облас?1 .псхуеу оптипзльних ивньг £4,5,73 - розробка мателатичних котод1з роэв'язанчл задач упорядкузання дзозтапних роб!т> £63 - программа реа-л!эаи1я катод!в оперативного планування на транспорт!.

зступу, чотирьох г>озд!л!в, зисноак!в, списка л1тератури, Робота аихладене яа 139 сто*>1нхах ^рукоэакого трасту. и1стить 25 иал»нх1в, 4! таблиц!, список вияори^тованих ;5«эр8Л - 63. додатки - 13 стор!нок.

3HICT РОЕОТИ

У зступ! сротму-гьорви! задач! досл!джання, ойгрунтгса-на ïx актуальн1сть. аизначена нета i питания, со вир!шу.зтьсг., сфоркильована наукова нозкзна ï практична ц1нн1сть роботн, изведен! в1локост! щодо anï.où£tuiï ! практично* осиоснии полэжень дисертац1К.

9 гшршо! у розд1л1 роботи наведено стислий огляд 1 кла-сиф!кац1я задач оперативного планування та управлХння работою автокоб!льного транспорту. Описан! основах методи I п1дходи розе'язання них задач. СФорнульована загальна задача ефеитивноХ орган1зацН транспс-ртного процгасу. Виявлен! "вузьгЛ М1сия" завершального етапу оперативного планувшшя та упраал!ння на автоноб!льному транспорт!, що укладаються в часову неузгоджгн!сть роботи р1зноман!тних об'е!;т1в тран-спортнрго процесу.

Визначен! задач1 до'сл1дження, а сане: розробна матема-тиних метод1в забезпечення часово'1 узгодженост! роботи авто--иоб1льного транспорту 1 нэвэнтажуБэльно-розЕоНтажувальнот комплексу, складання розхлад!в руху транспортних засо6!в за попередньо розробленини маршрутами. м1н!м1эаи1я простоев транспортних засоб!в.

. Другий розд!л роботи присЕячено обгрунтувангю доц1льност! використання метод1в теорИ розклад!в У розв'г><?«н! задач оптимального планування та управления и а транспорт!. Систеиатизован1 практичн! ситуацИ складання розкладу на навантажувальному транспорт!. вид!лен1 основ'»! класи задач упорядкування при планувзнн! транспортмих робхт, дане Их математичне формулювання й описан! основн! метод» Чк розв'язання.

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

- 9 - '

тим1зуючий критер!й ефективност!. Критер1ем ефективност! найчаст!ше с довжина розкладу.

Нолел! упрорядкування носять детерм1нований характер л тону розуя1нн1. то вся 1нФорнац1я про роботи в1дома у т?£**?!т початку Хх виконання.

Найвэжлив!шипи теоретичниии результатами другого роэ-д!лу роботи с обгрунтування вибору матенатичного апарату теор1Х розклад!в'для« Р">зв'язання задач часово! узгодженност! роботи навантажувально-розвантажувального комплексу й апто-моб!льного транспорту. В терн!нах ц1еХ дисципл1ни описана двор1внева модель ресурс1в1+Н. Дана XX класиф1кац!я з ура-хуванням Финкц1ональних характеристик машин другого Виэначено клас задач теорН розилад!а який цожна описати на-даною моделлю ресирс!в.

Загальна задача в терп!нах теор1Х розклад!в поляг ае в тому, шо в систему 1+И нашим 8 нойент". часу г»О надходить нножина двоетапних роб 1т. Перший вте.я кожноХ роботи, довжи'ною у , J » 1, п, обслуговусться единое яапмною першого р1внй, яка с входом систени. Друг! этапи. роб!т, довжиною в , .3*1, п, закр!плен! эа наяинами другого р1еня. тобто кожнэ паралельна машина другого р!вня повинна вижсиатм эаздалег!дь встановлэну сукупн1сть роб1т О , 1=1. п. Це озна-чае. ио вся мможина роб1т С роэбита на в п1дпко*ин так,

шо а=и с , |о |-п. г» -о. о п о .

1=1 I 1 П V

Кожиа робота ц . J-1.ii задана упорлдкопаною парою чисел (V, р). СпеииФ1ка задач1 склалаетьср в наступночут •

чЭ о

процес виконання кожиоХ роботи безперереиий. тобто, яквд ви-

конаиня nepiuiro етапу роботи J починаеться в момент часу — о

t «t + в , тэ момент завершения другого етапу роботи j j j

_ о I

дор1вн>л;ться t -t + 4 * p .

j l j j

Наступна робота з нножини G^ починае виконуватись машиною першого р1вня не ран1ше, н1ж буде завершено виконання попередньо'х роботи з uie'i нножини машиною другого р!вня.

Кожиа машина ноже виконувати одночасно не 61 льшо одн1е5£ роботи. 1 кожна робота одночасно ноже обслиговуватися не б1льше. н1ж оди1сю машиною,

Момент эавери!ання виконання Bclei множини роб!т системою 1*Н машин дор1внюе

ПЯР - max (L (Ю 1,

1<«1<«т 1

де L СЮ - момент завершения виконання роб it G , при значении 1 1

на паралельну машину 1. -

и

'.Задача пилягае в побидов1 розкладу JX . якому в1дпо-

в!дае значения *

. L(3l ) «' min max L CJD, ilep i<»i<*-» 1

де Р - иножина вс1х перестановок роб1т Л = (J ,J .....J ).

12 п

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

Fl+m | no uait. Interrupt line, 1»10 | L

. <2> min

де парив поле Формула Fl+m - визначае конвейерни систему CF)' э 1*Н машин. Друге поле в1дображас правило проходження роб1т через систему машин! по ualt - заборона меяопераЩйних простоев! Interrupt line - означас те, юю будь-яка двоетап-

-lina робота завершуеться не п1зн1ше, н!ж починае обслуговува-

тися наступна робота на нашин1 першого р!вня; 1 '10 - оэна-

1

час те, що в конвейерн!й систем! кожна робота виконуеться т1льки двома машинами, включаючи першу. Трете поле вка.ъ\,г. на критер1й оптимальност! задач1.

В робот! вид1лена задача, в як1й довжина других етап!в вс!х роб1т е величиною пост1йною. Ue обуиовлено роз-повсюджен1стю ситуацГй по обслуговуванню автотранспортник п!дприемством ионопостачальник1в. Класиф!каи!йна Формула в1добража це обмеження i мае такий вигляд: Fl+m|no ualt. interrupt line, 1=10, P =Const|L

<2» 2-Í nlrt

На п1дстав1 класиф1кац1йних Формул систематизоваи1 задач! упорядкування двоетапних po6ít в систем! 1+Н маиин. Дана оц!нка р!вня вивченност1 задач цього класу.

Встановлено зв'язок задач досл1джуемого класу э оснэво-положними задачами Teopií розклад!в. Описан! засоби пошу-ху р1игемня задач, що досл!джуються.

Визначено задач1, шо потребують оц1нки обчислювально! складноот1.

Ы третьему розд!л! встановлоно властивост1 оптииальних

за швидкод!ею розклап1в для эадач1 координацИ роботи навпн-

тажувально-розвантажувального комплексу i автопоб1льного

транспорту при обслугоауванн1 ионопостачальчикч. В

дисертац!! ц1 властивост! сФормульован1 1 доведен! у вигляд1

наступних стверджень.

Стверд5сання 1. Оптимальний розклад задач! Fl+m| .

no ualt. Interrupt Uno.1=10 .Р =Const|L лосягаеться при <2> 2j "in

MiHlMlsauii пгосто'хв на яашин! перпого р!вня.

*

Довжина »птимального розклади ЗХ дор!внюе> м J*n М

ия )« г у + р + ася э.

j.I j

»

де dCJt ) - cima простоев нашини Мо.

Ствердження 2. Для задач1 Fl+m | по wait. Interrupt

line, 1»10, Р » Const |L Ichvc оптимальний розклад, в яко-<2> 2J mln

ну nepml m роб1т упорядкован1 по неэростанню п^, де п^-

к1льк1сть роб 1т в G . Дал1 в розклад! чергов1сть нашим дру-1

того р1вня збер!гасться.

Тобто оптинальний розклад сл1д шукати в клас1 роз-клад1в. де робота е. попереджуе роботу в за умови, шо

к р

n > n , gee, fl с G , t-z. с к * р 'т

■ Ствердження 3. В оптимальному розклад! першою призна-

чаеться робота э м1н1мальним значениям довжини першого вта-

nv э п1дмножини э.максимальною к1льк1стю роб1т.

л *

.Тобто, в оптимальному розклад! Я g е G , лэ

1 г

п - пах п .

Г 1<а1<жЯ 1 *

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

Доведено, то обмеження р » Co.lst, не дозволяе уникнути принимпових труднош.1в, пов'язаних з побудовою точного ефективного алгоритму потоку Lnin.

Результат анал1зу обчислювально* складност! задач1 сфориульовано у вигляд1 мастипноЗС теореми.

Теорема 1. Задача побудови оптимального розкладу задач!

- 13 - r

Fl+m | no wait. Interrupt line. . 1-10 , P « Const |L e

<2> 2J rain

NP - важхою в сильном« posvnlHHl.

Доведения uiel теорени виконано за допетого» еталонно! NP - повноУ задач1 З-РОЗБИТТЯ.

Задача часовой узгодженост1 роботи навантажу-вальмо-розвэатэжузального комплексу 1 автоиоб!льного транспорту при пзрявезеин! вантаж!в в1д монопостачальника р1зним споживачам с узагальнемням задач 1 «i*m| no ualt, Interrupt

line, 1=10 ,Р » Const ]L

< 2> 2 J mln

За допоногою процадури локально! зам1ни параиетр1в з

робот! довелено. шо ця задача .також NP - ваяжа!

Чей результат сфорпульовано наступним ствердженняи.

Насл1док 1. Задача Fl ♦ m | no wait, interrupt line,

1 >10 , |L MP - важка в сильному розун1нн1. <2> mln

Для повисли анал!зу часовоХ склавност1 поставланих задач роэглянуто частинн1 випадки при т-2.

Задача! F1 + га | no wait. Interrupt line. 1 »10. Р -

<2> 2 J

Const|L при т-2 оптимально вир1шуема за пол1нон1аль-

nin

ний час. Доказ цього ствердження наведено в четвертому Розд1л! роботи.

Задача Fl+m| no wait, interrupt line. 1 ■ 10 .|L

<2> mln

при m-2 не мае такого р!шення.

Це сформульвано 1 доведено наступною теоремою. Теорема 2. Задача Fl + m | no wait. Interrupt line, 1 »10 ,| L NP - важка при ra«2.

<2> mln

Доведения uiei теорепи виконано за лопопогою эталонно! NP-повно! задач! РОЗСИТТЯ.

- 14 -

• К1нцевою «этою розв'яэання задач теорП розклад1в с оп-раиювання алгоритп1в. як1 будують за пол1ном1альний час за-дов1льн! шодо якост1 розклади.

Ы »чтвертону розд1л! роботи викладен1 результати розробки алгоритм!в р1шення задач часовоХ изгодженост1 роботи автомоб1льного транспорту 1 навантажувально-розвантажу-вального комплексу.

За допомогою дихотом1чного пошику в робот1 розроблено алгоритм р1швння задач1 Fl+m| по wait, interrupt line, i -10 I L

<2> mln

Метод дихотдмП використано для пошики н1н1мально! дов-жини розклад у, який ножна побудувати пропонованов процедурою "упаковки" компонент. 1

Суть алгоритму полггае в тому, то на кожн1й 1терац1!£ в1домнй 1нтервал С train. Lmaxl д!литься надвое, а розроб-лена Процедура вибору компонент "упаковуе" роботу а задану довжину Ld • CLraln + Lr»x) '/ 2. Якщо такий розклад 1снуе. то встановити Lmax - Ld i процедура побудови розкладу повториться. а якщо процедура упаковки не будус розклад дов-жикою Ld. то тод! Lmln - Ld .

rain

L - max СГ + mln p , max S, 2 С V + S

rain 1<»1<«п k l<*l<»m 1 1 mln mln

до Г»'*" X » S - Z (v '* p 3, i-ITm, S - min S >

k. 1 k 1 g|,cQi k k mln K.l<»m 1

4 « mln V » V " mln V

1 гцсОк k mln eKcQ«.in k

i* m <

L • 2 2 (V +P > ■

ТТ-ЛК 1=1 k k

Незважаючи на та, шо цей алгоритк наближений , обчислх>-

вальний експеримент показав луже висок! результати. Найже в

50 випадках э! 100 алгоритм будуе оптималышл розклад. В 30

випадках з1 100 в1дхилення в1д оптимума ненш за 1/.. I т1льки

в 4 випадках ai 100 похибка складае б1лы1гз 5'/.. Так! висок!

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

дихотом1* та алгоритм!в упаковки.

Анал!з обчислювально!' склалчост1 задач! Fl + m| по uait,

interrupt line, 1 »10, Р =Const|L . не залииае над!'! на 1с-<2> 2J min

нивэння точного пол1ном!ального алгоритму ÏÏ розв'яэання. Тому bcï зусилля були спрямован! на побудову наближного алгоритму 1з задов!льиою оц1нкою.

Побудова такого алгоритму була спростована тим. шо у третьему po3fliv;I були доведен! властивост! оптимальних р1шень u.leï задач1, на п1дстав1 якии 1 було роэроблено пол1ном1альну процедуру розв'яэання заяач1 часовоХ коорди-nau!ï роботи автомоб!льного транспорту та нэвантажу-вально-розвантажувального комплексу при обслуговуванн1 моко-постачальника.

В робот! дана анал1тична оц1нка иього алгоритму. Ствердження 4. IcHve алгоритм який за пол1ном!альний

о

час будуе розклад Я для задач! Fl+m|no wait, interrupt- line, 1 * 10, P. « Const I L , абсолютна похибка якого менша за

<2> 2J min

6 =щах СО, Z С СВ- т+1) .СП - П )) - В

1»1 rrv-1*1

о и

Тобто LC31 ? I (Я ) ♦ S.

Вивченмя р!эмоиан!тних иодиФ1кац!й поставлених задач

дозволило в1докремити ефективно вир1шуем1 частинн! випааки 1 опрашсвати точн! пол1нои1альн! проиедири 1х розв'язання.

Ствердження 5. Якщо к1льк1сть машин другого р1вня перевишус ¿овжину других етап1в роб1т п > р+1 . тод1 задача Эфективно розв*язусться за пол1ном!альний час. Розроблено точний алгоритм р1шення ц1е! задач1. Ствердження 6. Якыо довжина першого 1 другого етал1в роб!т с величинами постХЯнипи С у^- Const, р^- Const), то задача эфективно розв'язусться за пол1ном1альний час.

Ствердження ?. Якщо сума м1н1мальних довжин перших етап1в роб1т з кожно! п1дпножини G , 1«1.т С1льша р,

jwm 1 • '

тобто Z ml р. у > р , то задача эфективно розв'язусться

Ы l<aJ(«mi Ji

л

за иол1нон1е.лы1ий sac.

Ствердження 8. Якшо довжини перших втапХв вс1х роб 1т б1лыо! або дор1внк>ються довжин! другого етапу в!дпов!дно1 роботи, тобто у^»» p,J*T7n. то задача эфективно розв'язусться за пол!нон1альний час.

Ствердження 9. Якыо и» 2 I p. 1=ГГй, то задача

Fl » m I по wait. Interrupt line. 1- 10 . Р - Const | L ,

<2> 2J «In

е$и&тивко розв'язусться за пол1ном1альния час.

В робот1 пропонуються точн1 пол!нои!альн1 процедури розв'язання наведених частинних випадк1а задач досл!дження.

Програмна реал1эац!я алгоритмов задач часовоХ коорди>-наиП роботи а»токоб1лького транспорту.* та навактажу-пально-розвантажувалнногс комплексу виконана на Паскал1 в севмовмя! проблонно-ор1е»:то»сяого пакету . який признаЧо-ний для систоиатизаиП на програмноиу р!вн! результат^.

одержаких в хлас! задач посл1довно-паралелъногс упоряяхува;"-ня в систем! 1+М машин. Принцип створення пакету яозволяе доповнювати його нозими модулями ! задачапи..

0СН03Н1 РЕ39ЛЫАТИ ТА 8ИСН08КИ Результат« проведених дослхджень е лодальшии роэвмт-ком розд!лу теор.'.Х розхлад!в, яхий займаеться розз'язакняи задач упорядкування двоетапних роб!т у систем! 1+М каимк.

9 практичному вхдношенн! викомана робота с знвскоя » роэв'язання задач оптимального планування роботи яазаитажу-вально-розвантажувального комплексу 1 рухомого складу на зантажному автоиоб1льному транспорт!. Основн! результат» по-лягають у наступноиу!

1. Обгрунтовано виб1р математичного аг.арату для роза'я-зання задач часово'х узгодженност! роботи кавантажу-вально-розвантажувального комплексу ! автокоб!лького трак-спорту. Дано Формулювання поставлених. задач а теря1ксх теор11 розклзд!в.

2. Описано двор1вневу модель ресурс1в 1 + М . Дама класиф1кац1я моделей ресурс!в з урахуванням функц!0нальних характеристик мешин другого р!вня; Вид!лено клас задач оперативного управл1ння на автопоб1льнопу транспорт!, що описуеться наданою моделлю ресурс!в.

3. Розроблен! класиФ1каи!йн! Формули задач, шо дос-л!джуються. Систематизован1 на п!дстав1 класиФ1кац1йг.их Фор-пул задач1 упорядкування двоетапних роб1т в систем! 1+М.

4. На п1дстэЕ1 теорП НР-склад1:ост! проведено анал!з обчислювально* скл»дност! задач упорядкування вантажно-тран-

спортних cr.ofauiß на вантажноиу &атомоб1льнону ъ*раиспорт1. Доведена сильна NF-Baxalcvb загальних постановок задач дос-л1джузаного класу.

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

3, Розроблано натеиаткчн! методи розв'яэання задач упо-рядкуванля сзоетаяних роб!т в систем! 1+Н машин.

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

8. В1дохреклено ряд частинних аипадх!в загальноХ задачи лоординаиш робота наваитажувально-роэвантажувального комплексу 1 азтойоб1льног' транспорту.' ьп иожуть бути опти-кьльнс розв'язан1 за пол1нои!алький час.

9. Виконано программу реал!зац!ю розроблвних алго-ритл!в в середовиа! проблеино-ор1ентовакого пакету One Plus И KAChlno. Одержан! результата обчислввального експер!венту п1дтБорджуат1. тсоретичн! оц!кки розроблэних алгоритм1о.

ССНОВНИП ЗН1СТ AKCEPTAIiii ОПУБЛИКОВАНО Ы CJlt ДЫЮЧИХ . 9АЫК0ВИХ ПРАЦЯХ

'.. Панишеа A.B., Бурцева Л. П. . Полозо£1а Л Н. О аибори оптнкальнпй очередк с0сл;+яв<э«хя техиолэгческих линий тран-criO?TiiO( механизмам // Зле'/троикоз коделирование. - 13сС, N2.- г.СО-94.

2. Ма1о1ергу ft.. Varakin A. S. , . ?a,nls$^ev ft. V. , Polozova L, N. Some New Results for Generalized Tvw-stage Floushop Sequencings Problems // Articles of Polish Cybernetlcal Society "System. Modelling. Control." - 1999,

3. - p. 15-20.

3. Maiolepsy A.. Panishev ft. V. , Polozova L. H. Some Кем P.esults for Optimal Tvo-stagB flowshop System Setzuensing. /( Articles of Polish Cybernetlcal Society "3ysten. Kodeliing. Control." - 1993.- V. 2. - p. 104-1C8.

4. Пакииэв А. В, , Полозова Л. H. , Черношг. С. А. Метод дихотомии в решении задач теории * расписаний // Ксследова}"''.о? проблем транспортных систем. - Сб. яаучн. .трудов. - Харьков» Изд. ХГАДТУ, 1996. - с. 6S-60.

5. Панишев А. В. . Полозова Л. Н., Сослозский В. Г. Алгоритмы оптимального упорядочения в управлении погрузоч-но-транспортными системами // Тезисы доклада Всесоюзной конференции "Моделирование процессов управления транспортным»! системами".- Владивосток. 1989. - с. 168-189.

6. Кузьменко Н. Н., Панишев А. В. , Полозова Л. Н. и др. Подсистема оперативного планирования и учета затрат на АТП // Тезисы докладов Всесоюзной конференции "Теория и практика применения экономических методов хозяйствования з промышленности и на автомобильном транспорте". - Суздаль, 1990.

с. 278-230.

7. Костикова П. В., Полозова Л. Н. Теория расписаний в оптимизационных э?тачах на транспорте // Тезисы докладов Международной научной конференции "Современные транспортные проблемы". Харьков, 1'»96, - с. 75.

- 20 -АК0ТАШI

L. N. Polozova. The mathematical models of ths selection of the decisions in the problems of the regulation of two-operatj tig works at transport. Dissertation on competition of a scientific degree of candidate of technical sciences on speciality C5.13.01,- "System Analysis and Optimum Decisions Theory". University of Internal Affairs. Kharkov. 1997.

Here is submitted the scientif work containing the research of the problems of requiation of the load-transport operations. The problem Is formulated by means of the terns of .hsory of the schedules as the problem of the requlate of two-stage works in system uith 1+H Machines. The dissertation is containing the mathematical models' of researched problems. Tf"3 analysis of the calculating complexity of problem was executed. There are the proofs of the equality of the optimal schadulings, taking into consideration the speed o* the calculations. The authoress Ьая developed mathematical methods for solving the problems of requiation of two-staaa works In • system with 1 + fi M&chineG. The authoress has determined the effective solving of particular cases of the problem &nd the precise algorithms of their decisions. The algorithms navo bsen reclizeci on computers in environment of the packet One Plus ff Kachir.s wich игл* integrated to the production.

•it. H. Полозова. Натоиатуческхе модели и метола прмнкткк решений а задачах упорядочэи»ч двухоперационных раЗст на транспорте. Лиссе?тааия на соискание иченоЛ степени кандидата

технических наук по специальности 05.13,01 - системный анализ и теория оптимальных решений. Университет внутренних дел. Харьков, 1997.

Задцицается научная работа, содержащая исследование задач упорядочения погрузочно-транспортных операций. . Задача Формализована в терминах теории расписаний, как задача упорядочения двухоперационных работ в система 1+М машин. В диссертации раэаработаны математические модели поставленных задач, доказаны свойства оптимальных по быстродействию расписаний. выполнен анализ вычислительной сложности, vдоработаны математические методы- решения задача упорядочения двухоперационных работ в системе 1+М машин. Установлены эффективно разрешимые частные случаи, разработаны точные алгоритмы их решения. Выполнена программная реализация разработанных алгоритмов в среде проблемно-ориентированного пакета One Plus И Hachine, который внедрен в производственную практику.

Ключов1 слова« системний анал1э, иатематичн! модел1, упоряд-кування роб 1т. ефективний алгоритм. НР-складн1сть задач, оп-тимальне р1шення.

В1дпов1дальний за випуск-Ар1стова 1. В.

Шдписано до друку 20.03.97. Формат 60x90/16. Пап1р галет. Друк. офсетн. Умовн. друк. арк. 1.0. Тираж 100 прим. З&мовлення N

Ротапринт Ун1верситету внутр1шн1х справ 310080, п. Харк1в. пр, 80-р1ччя СРСР, 27.