Исследование устойчивости оптимальных расписаний в задачах на смешанных графах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ



АКАДЕМИЯ НАУК ЕШРУСЙ ИНСТИТУТ МАТЕМАТИКИ

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

Ашпкешч Виктор Бернардошч

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

01.01.09 - иатематнческая кгбернетикя

АВТОРЕФЕРАТ гксо0ртаапи(чва созскангв ученой степейя кандидата <Ьжасэ-гтэискяесксх паук

извет: - 199Э

Работа выйолнена в Институте технической кибернетика Академии наук Беларуси

Научные руководители

Официальные оппоненты

- доктор физико-математических наук, профессор В.С.Таяаев,

- доктор физико-иатематическш наук, старший научный сотрудник Ю.Н.Сотсков.

- доктор физико-иатенатичесюп наук, профессор Н.Н.Метельский,

- кандидат <1изико-математическЕХ наук, доцент 0.И.Мельников.

Ведущая организация

Вычислительный центр РАН

Защита диссертации состоится " &&п исал: 1993 г.

в " " часов на заседании специализированного совета К 006.19.01 в

Институте математики АН Беларуси, е

(220064, г. Иинск, ул. Сурганова, 11)

С диссертацией можно ознакомиться в библиотеке Института математика АН Беларуси.

Автореферат разослан

ап-тое^Л. 1993 года.

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

ка^^з-: фалкз-мзтембютаекпг наук Л-^Ц^- А.ИЛотрсвекий

- з -

Обцая характеристика диссертащонноа работа

Актуальность теш.

Теория расписана® как самостоятельна^ раздел исследования опера-Ци& имеет веяюе прикладное значение. Одной из задач, нзучаешх в ранках ¡крой теории является задача оптаизацпи процесса обслугивення конечного ыноаестаа требований в детергшпированно® системе, содержащей ограниченные ресурсы- Для юэвдого требовгзпя задается ыеыент его • поступления в систему. Требование даащо пройтк одну идя несколько, в „зависимости от условий задачи, стадай обсдугивання. Для каэдсЭ стадии указывается допустимые набора . ресурсов в дгзтельность ебеяуглЕсшм требования. Оговаривается вогиоиность прэрнвангй процесса обслуживания требований. Ограничения на очередность обслуззгзания троЗозетгЗ задаются, как правило, в виде бинарного отЕсзеши строгого порядка.

Широкое практическое ¡шачешэ задач весрнз расзасензй (управление производством, транспортом, строзтельствоы, Еичислотельшшз снстома-еи и т.д.) привлекает к ним серьезное внимание специалистов по деск-ратнсй ыатеизтакэ. Однако щп разработке еффээтгвшс алгоритмов рззе-' пия простзйззх, на первкй взгляд, задач теощи расапсапиЗ боля встречена сначительшгэ трудности, сзяэанхзгэ со етруктурна.3 слозностьв ва-неназванных задач. Косвенным подтверждением этого обстоятельства является НР-трудность большинства практически интересных задач теорги рЗСПЕСеНПЙ.

Вгаотэ о той. сотое естественное отргтэнпе динагтгхя ряда вкокоггз-ео-ыатекатвческшЕ п пропзводствэшпл: моделей, гашскваегсгх о использо-сеззз.м задач госхгтт ргсппсгпзй, достигается в тех условиях. когда входные характвраотша егегс?» • с5ол?гг?п!т# (пащозр. дваташмета

обслуживания трзйозашй, времена пзрен&ладак щяйороз, дгрекшвша срока е т.д.) гададугся нз етчно, а в некоторых пределах возыоаннг изменений. В сэязи с агаи, прпобрат£зт актуальность ЕСОЕЗдаЕЕнга устай-¡гнзоста в задачах теоргх распгсанай, т.о. изучение свойств спагпыадь-екх реаензй задача щзз вазршцлз члалссдг исходных даятштг. Исаладоза-Е2е устойчивости е задачах теораа раеягаанзйг прздсгагяяэ? значдтольЕы2 пнтарае так^э в связн с той, что его ксаладованаа позволяв? в иештсрщ случаях актска'пкшога паяучагь рзгенлэ есег. зодгя, параметры которых оглгжется ст Еарагхетроз негодной Еэдггаз на накшо-руз ватага?, зпачэша которой Еачзсляо<гся в процесса такзго исследования. Краю отого, так кш: часто рзаанЕЭ и чгслсв^э исходам дгшпна задачи иогуг Скть пшучеза с ЕЗКсторсЗ погрзшноетыв, зненае радиуса устоСчивссш шзволязг Ерогерзгеь ргадькоа няаченпз полученного рагз-шхл задачи. Сценка радиуса устойчлаоста даст Евфзрыацпз) о точносзп исходных днзшд, которуэ неовховзио спета парад "геи, как щссвупать к рЗЕЗНЗЕ звдачл.

Цела ра&з-тн шшгзгея:

1. Есапздезгпнэ усгсйъггогэя сапеиальша: ео б истродайс гею распи-сшшй.

2. Веаядававзэ ус«й?ашоегк сагсгашглг ро^знзз в вшервшигавш: задачах на скзсаннЕг грсфаг.

3. Аеаддз устсйчзвоссв в сг?з»т:да£тяс системах сбслззгвгщ&я.

4. РаэраЗсгкз цзтодоз енчзслобхд точкою к пргйЕааешого значеаш радиуса устоЗчх^аетл сагаыгдъзи расгысанаЗ.

Научная новизна. 1. Получена ссояаоаззня иаггду раднуес&н усто£-чзвосав, уяовлетаоряхгвш рааетшш оараделапаш. 2. Задача расчета

точного значения радиуса устойчивости инокастза всех оптгнальных решений: в задачах на гагеианннх гранях езедзна к садсча математического программирования. 3. Последовала устойчивость шокеотва всех оптимальных решанзЗ для различат: допустимых вариаций параметров 2адата с получеЕЫ аналитические форбгулы расчета радиуса устойчивости. 4. Исследована устойчивость отдельного оптлиалыюго репения и получены аналитическая формула расчета радиуса устойчивости, а такге паоб-ходаше н достаточные условия беекснечзостн радиуса устойчивости п ЕЭОбХОДШЫЭ Е достаточшга УСЛОВИЯ, ЩП ВШОЛЕЕЗШ которых раДЗЗ'С устойчивости полс^зталэн. 5. Исследована устойчивость .кназеетва репеннЭ по фунщконалу.

' Методика исследования-. ^атодпчеспуп основу работы составляв? лэ-г^ЕО-ксибпнатсрпыэ «этодн ДкекрвтноЗ математики, мэтодн кого прогрзатроваяЕЯ, теории грсфов п тэорзп расписаний.

Практическая звашаеость. Результата дксертгцщашюа работа еюгт? быть пштальзсзазн прз режзннн задач атэрэтпкто-кялендяряого плсзпрэ-вапня, а такгз ща гекзрацзп тестовзг задач на сь:эееепнх греках о заданным ЦЕСЕЭСТВСМ

Публикация л ыпюбвпзя рг.бота. По тсыэ ягсеврткез сзублякозаго 3 печатных работ. Осноейзэ разуль?а?н докдэдЕзадзсь па свегззарз в лаборатории НТК ж Баяаруеа, т Золавягеа кггЗзреягш та чюерэтагазскЛ гсбэрнетихэ (г. Горький), ев Дзсягс! пзэсеззнс« сзагогауиэ (г. Нарзэ-Пизоуу).

Структура и абъеи работе. Дсосэртиты соотетг г:л евэдэекя, трзг яейз, заключения к схг:с:-п ллторатури СТЗ ашшзззвепая).

Обьеи работа - 110 лмгез шазтясаага кяем.

- £ -

Содержание диссертационной работы

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

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

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

Пусть &=(С,и,У) конечный смешанный граф без петель, кратных дуг и кратных ребер, в котором О = {1,2, — ,п) - инокество вершин, и - множество дуг, н V - множество ребер. Каадой дуге (к,Ь) с и поставим в соответствие действительное число а^, каждоиу ребру [к,Ы е V поставим в соответствие пару чисел а^ и а^. Пусть О'- подмножество вершин множества О, вершина хсс О. х^й О', Р(С) = {С^С^,...,С^} - множество всех орграфов, порождаемых смешанным графой С в результате замены каадого ребра [к.Ыс V дугой (к,Ь) длины (веса) а^ или дугой (Ь,к) длины а^. К^ - множество всех путей из варганы Ха в вершину 1 € О' в орграфе множество К^ = и К? , С^- множество контуров, в орграфа Ь .

длиеы дуг и рэбер смешанного графа с представим вектором а *> ( йк,Ь* • • - ,а1м-! )» компоненты которого распологены в лексикогргфгчеиох: порядке пар индексов (к, Ль), 1 = 1,2,....е. Сушу данн дуг и ребер.

пршвдлегещях пути Д <s Kd (идя: контуру 5 е cf1), 1=1.2.....X. будем

называть длиной путя д « ^ (контура 5 с С4) и обозначать 1 (у) и соответственно. Через { Ц > (С 1 }) будем обозначать множест-

во компонент вектора а, которые является слагаемыми величины 1а(д) (1^(1)). через |t (i >1 - число элементов uHcsecrsa { ¡i }. Орграф G4 будеи называть допустимым, если выполняется соотношение!

гахл 1а(?) s О. <Г

КйздсЗ взрзяне 1« Q' поставш в соответствнз неубывающую действительную функции ^(t) такуэ, что ^(t) > О, при t>0, и ^(t) = 0 пря t s о, я действительное неотрицательное число о^. Каздсму допустимому орграфу поставим в соответствие число 1? (а). которое вычисляется со формуле:

Т4(а) = с32 caí ^(l^fl)-!^). 1еО' Ц в К^

/

Пусть Р (G) - шозество допустимых орграфов, порскдаеъых смешанным а

графом S. Задача состоит в поиске орграфа G%e P_(G), для которого вы-

á

полшштся соотношение:

а ) = п i а ( а ),

C&s р' (£)

а

прз отси граф bs называется оптадальпз^.

Пусть р(Е) - шогество слтшальныж орграфов, D(a) - глтсзгестао допус-тагнз варпацза ксгягснэнт вектора а.

Ощййвйеше 1. Зашаучна шар С„(5,а) радиуса р с ценотол а аоа-?cps а называется азрсм уотойтавос-ш орграфа С3« если для .та-

кого вектор« Б s О^(а.а) л 3(а) Екиа.'зм-этся cccmc-sEte ТГй з(с).

Пусть Р(а,з) - штояество пеотрацательшх дейстнлтэлы-ых чазод гз~ яях, что прл р € Р(а,з) пар О (а,э) отляе-гея парой yczcZzmcüzx es-

- а -

графа G? Тогда Eejsrosa pg(a) = max{ pip s P(a,s) } называется радау-ccsa устс2чз-псста орграфа Соотносительно взюэра ¡íí?.

Ощаделааш 2» Залаутый пар Ор( а ) радауса р о центром в векторе а шзызавтея е-иарс:; для бтого вектора, ecus для любого вектора 5' е Ор(а) л 0(a) выполняется cg-oteosshhs:

j 5?s ( 5') ^ 5L ( а ) | s £ Определенна 3. Уакснмальная величена радауссг с-сароз назыйаетея радаусси e-ycToitemocra и обозкачдзгея через р(5,е).

Белее 062534 псиятке!! является область устойчивости. Содержательно, область устойчивости описывает ■ набор преобразований вектора a, Hps которы: асдааозество оиегиальЕнг орграфов ¡¿азвеепш s( £ ) удовлетворяет определенным услоЕлям. В завасгаюсш от ctax условий, по-разнсаду определяет областа устоСчавостЕ.

Опрзделаюа 4. йяозэство а (а) всех векторов í е 3(a) называется областью устойчивости вектора а, если для лзхЗого вектора а'е Ы (а) выполняется ссотноЕешэ v( а' ) s $( а ).

Оарадейапка 5. '¿дшэетао У'(ь) esez векторов 5 в 0(a) называется область» устойчивости вектора Е в сальном сыаеае если для дзбего вектора а' € U'(E). наполняется соотпсЕгпаег

í¡( ) л Jí I ) * а Ощ>ЗД8й6НИ8 0, «юаестао .ае(Е; sees bsetcpos-5 « В(а) навнзавтея сблзстьв усто2чзвос-и ошяашльного орграфа G3 е #(а), еода С3^ ?(а') для яобого вектора а' е й„(1).

Определенна 7. Кшякотзэ *г( а,е ) EOSt векторов 5 е 0(a) щеава-етач область» е-устойчазсста гектара а, ееяв для jaxJoro .вектора а' £ У (а,с) выполняется еоотзевенне:

I S, ( S') - % < S ) I * t.

Тйоргка 1« Для левого вектора а справедливы оледупда соотношения:

а { ä ) Е 1 ), 5 ) s ä ), для любого G8с р(5),

»'( ä ) « о _ t# ( а ).

G3« ?(a) s

Вторая глава посвящена исследовании устоИчивости иногестза ептп-иалышх реаений в задачах на сыейанннх графах. В § 2.1 проведено исследование устойчивости оптимальных репениЭ при условия, что |8'[ « 1, функции итрафа ^(t) = t, ыногество D(i) = и в качестве допустимых решений рассматриваются бесконтурзые ориентированные графы, порездаэ-кна смешанным графой G. Предлоген ыетод пояска радиуса устоЗчквоста. который сводится к рэсенст еледущеЗ задачи нелинейного прогргшдро-вашя:

р( а, х ) -в1д. (1)

л Qin C3Z M 1Z( fi ) s sin ЕЗХ - lz( ff ), (2)

sr а я(1) fí с ВТ l» Й ЗГ

ïïB(â). (3)

Dpa 8тсы, если вектор х, является реиепгоа задача ( 1-3 ). го валзча-

на р„( а ) =» г ( 5. х, ).

Получена ецеша радзуса устоЗчпгсета, а доказано, что а случае, если кнозастБО â ! » { о }, 50 вэлзчеяу р„(5) iscszto оценивать по ёогздгло:

1®<р)-15(р) ¿J^S*

$„(&) я min ein car а а г -■

Sus кнсгзство ç(â) неизвестна, «то .-и. Л.-, сценку радлуса устозчв-поотз tamo вычислять по ©сдаулак

1и(Ц)-1в(Р) -г ß*

pc(â) г Ein e a x -Osisl

- Oslsa I №>I + IW 1-21 Щ}л{»} 1-1-

Y„(ä) - T,(5)

pc(ß) t ---,

nJiV^ 1)

где т„(5) - обцае врсия взгзазнвошг всех операций ¡¿жжества С, наиболее близкое к оптшгалшсиу, g0 = 0 и { ¿I (£...,} - неубывающая последовательность Бленакгов iscaacma ({fí}\{í>}).

Доказало, что ЕообходшлЕМ е доагатсчнна условием цранадлакностп Ееетора s е D(ä) oúiaess устойчивости K(S) является выполнение' усло-еия: _ . . _

„ Ein 2Г'(г>) < я EiШ ПЗХ,

С°€ ?(а) Ус К0 «Г<£ ç(â) fis tr

Сведущее утвераденаа jjsse достаточные условия принадязашости

некоторого цнсссстЕа Бзюторов облаозк устойчивости t'(S).

ïcsps:a Е. Если Eî(q) ■- иеоеэсево вэеторсз £ e каздШ es которых удозлэггорло* Еорззазству:

„ í _ zIái ^ _ „ „ _

Din -— > ы G S ->

(U.h) a, V - Po(a) (k,h) ß,..h - P„(a)

Ь^РсДй} ^ ^

то R(i) G wie).

E случьй, ïxrii zszb liC-'b ка^псгеш1 векгора £ нестабильна, радиус усгойчавоок: р0(а«С) ргшьа ссяакаиьЕску гшачеаа» (^ницвавава в в сесдтедс£ аадаад КУЗ2Ю2ЕОК> прорргзащрюмяЕн:

i»(а, £) -оЗл»

, £л1п г^Хд l~(í¿) й Din rax „ lx(f),

Фй ç(E) K^ isesl ve, K"

5 с В£(Е)о

где с - tsoseotso нэмсзлладаг îssskbse: вазгорз S, Su (à) - hhosscï-

ва таких векторов I. кгаиоЕзктн-х^ которых удовлетворяет? условна:

^kh. 3 Hii' еолз ö

Оценки радауса устоЗчиБосга в атси случао будут шгеть пид:

1а(д)-1а(1» - Г ¡Г

OsEs1

p_(â,C) a ¡ain car nin maz a a x -i-

' A*<¿) isosi va* pas4 toua^iWc+lf»Ic-aifbt^lc-i

Если гшогество ез(â) неизвестно, то справедливы слодукща соотно-

шения:

1а(д)-1а(р) - J. è p0(ä,C) a ala na" -----------—

1а(Д)>1а(У) ^

Т„(5) - Ts(5) • р0<а,С) а -pg-j-,

гдэ |{д}|~ - число элементов кнсгэства {д}, прзшдкзйаздх ssosecTsy С, С

3' = О я [ g¡ } - Еэубнзазпдя последовательность элементов

множества ({д}\{У>) л С.

Получена аналитическая формула для расчета радиуса устойчивости а случае нестабильности оддого элемента, а такаа исследована устойчивость 1Э0ЕЗСТЗЗ оятЕздальннг рэсзнзЗ для шогветв Э(а) = { z| öszsä } и 0(5) я {5| 5 s 5>.

3 § 2.2 наследуется устойчивость гшекеатза оптимальных рахениа з случае ограниченного иахешального штрафа, т.а. когда орграф с1 считается оптпиальннц, еолз выполняется соотнозаниз: saz caz , ?,(1а(Д) - О,) ä Ds,

1 € м д с 1 1 *

Доказано, что радиус 'устоЗчизостп в отец случае вычисляется па формула:

ls(jD-o,-t7 - £ в

О

рв(5) sin_ ваг вах, aas ------

в Л UU.lt НУШ и»*! шв^. --*

Фт ?<£) le f* fle Oslsä^ 1Д{ - i

где { g] g? ^ } - неубывавдая последовательность различных зна-

чений а^. (k,h) е í ¡¡ }. gV).

Если множество р(&) неизвестно, то для оценки величины р„(а) моано воспользоваться соотношением:

р„(й) í hüb iu.

Исследованию устойчивости отдельного оптимального оптимального решения посвящен § 2.3. Здесь в качестве допустимых решений рассматриваются ориентированные rpa&i, пороядаеше смешанным графом G, ииею-¡52S, возысдао, циклы отрицательного веса. Доказано, что радиус устойчивости рв(а) удовлетворяет соотношении:

р (а) г ainí шт'1^'!, min min maxf mz, ^^H*^?, шаг, ¿Ш. Н, 1 ^1(5)1 d*а ДеК® V. veZ* |{Д} ó {у}| Sei? (ф!

где | (д) ú {у} подоногество влементов, полученное из множества

Сд) u {V} после удаления из него влементов а^е { о } и а^е { д }

такйх, что либо a^s а^, либо а^ и а^ зависят друг от друга.

Пусть запиоь (Д) ь» {у} означает, что существует взаимно-однозначное отображение влементов мноаества {д} на элементы множества {(/}, пра котором каедоцу елёмзнту мноаества {д} соответствует равный или савншшый от него елецент множества {у}, и наоборот; К3! мнокест-во путей ß е К3 для каадого из которых не существует такого пути У е К4,что {Д} *-* {1>}. Тогда справедливы следующие теоремы.

Теорема 3. Если для любого индекса d, 1aJsl, мноаество С4 ¿густо и для лг-Сого пути ji г все компоненты множества {д} пойарас-нозаййои-

иа# cd а 5

pjа) * sin в1а д ж, - .

3 d#a деХ3**1 os vP- I w

Теорслз 4« Дйя того чтобы выполнялось соотнозениз p3(i)>0 необходимо и достаточно, чтобы выполнялись условия:

1). Е12я { la(f) } < О,

2). для любого пути д с и любого индекса d 'Такого, что

а

S^e 9(5) существовал путь t> « такса, что {д} <-* ОЬ

Teopsíia 5. Для того, чтобы выполнялось соотноаение pg(á) = оз необходимо и достаточно, чтобы выполнялись условия:

1). шюгестзо С3- а,

2). для любого пути р е Ка з любого яндекса dl существовал путь 'j g ^ такой, 4ío {д} «-» {»}.

В § 2.4 наследуется устойчивость репешя щи условии a(ä) = R?. nyófi, зспйсь t Д } é ( f } означает, что существует ннъективное a-roOpaírsiSa ыйойества { д } в «ногаство { v } таксе, что образси любого элемента таогзства { д } является равный еуу или зависимый от наго элемент инозества ( У }; Ке \ к4- подгшоаество путей д е К3, для

каздого из которых не существует пути ve К^ такого, что { д } á { v };

(j 1 2 (¡I

3 = О и igt S« ..,g'vfi) - нзуб'шагщаг последовательность элементов

шохества {>} л ( {д} ú {у} ). Справедлива следующие утверздения.

Теорема 6. Если G3 € то

1а(у)-1а(ц)- Е

рЛа) ч ola ala , ваг, шаг -°sfcst .

lJ &фв lieX \ ä ixä11 Osxsa^ | {д} ¿ {г?>| - т

Tscpssía 7, Для того, чтобы выполнялось неравенство о,Ал) > о,

G3« ?(а), необходимо и достаточно, чтобы для любого орграфа íA; 9(5)

заполнялось соотношение:

oaz л la( Д ) < шах л la( f ) i> e ST

Теории 8. Для того, чтобы выполнялось соотношение ра(а) = а необходимо и достаточно, чтобы для любого пути цеИв\ А Д2Х$ОГО КНД8КСЗ d. istíLsX, существовал путь У € такой, что { д } ¿ { }.

Устойчивость множества оптимальных решений по функционалу рассматривается в § 2.5. Доказаны следувдие утверждения.

Теорема 9. Если а - вектор длительностей операций, то

р(а,£) » Í 0111 { р1' г2} * ейШ > £* \ r1t если T$(ä) s е,

где величины г1 и i>2 вычисляются по формулам:

It( Í ) + Е ) - 1а( Д )

г = шах min п1пл —-,

1 1&Ы. 1«а'д« |{ д }|

1а(йМ: fJ<T*(ä)-e)

г0= min шахл д^т-Osl^k-

¿ 1sdsX lcQ'pe CKksU^ |{ д }| - Je

и g°= О, С gl g?...,g"д } - неубыващая последовательность различных

елемантов мнояеетва { д }.

СЛ8ДСТ8И9 1. Если pj^ t ) - t, le О', то

р(5,е) a 6

. еч

В случае, если не стабильны лишь компоненты вектора а, щинадле-каяяз множеству С, то при расчете величин г^ и т^ достаточно заменить 1СМ>\ на |{д}|с, а нижняя оценка величины р (а,с) будет иметь вид:

р(а,£) г .

|С|

Если все компоненты вектора а равны друг другу и 1;, 1с О',

то радиус устойчивости в етоа случав определяется лишь структурой смешанного графа С и равен:

p(â,e) = e / ( sln max пах.I £u}I ). 1sdal. le9'fie ,

Глава 3 посвящена исследовании вопросов устойчивости сптималь-ещ реяепий в одностадзйныт систе!лах обслуживания.

В § 3.1 исследуется устойчивость ситиыальЕН! расписаний в следу-ш^ей задаче. Имеется обслугнзагп&я система, состоящая из одного прз-

бора. Требования из заданного инскэства И = {1,2.....п) поступают в

з систему в цемент временя &Ю. Дттелыюсть обсяугивсния требования i « К равна t^, вес (т.е. значение, вееиость) требования ie ri равен • Прерывание обелугпвкзм требований и простои прибора запрещается. Тогда порядок обслуягвания требований (расписание) ¡логао предстают» перестановкой 2 = ( i-j.ig.....ljj), где пагзр требования, обслуживаемого Ь-ым по порядку. Длительности обедугнвеииз требований представляется Еекторо« t = (t^tg,...,^). Каздсцу расшссяга я поставлена в соответствие изведанная суц^а ыо^гитсп завершения обслуживали ^рэбсваиий шкязатЕа И:

V ^ = -5 S «ц V 2 ).

где t, ( п ) - efsim завэргелия обааугзвгнзя требования при распаде

сапгл Z. Расписание а» называется саакагьшз!, если плюлялатся сост* I»

погзепэ:

?.( Ï ) о ?.( Î ) " Я1П ?„( Î ).

2 11

Пусть C(ï) = {о,«). C2(î).....ûr(ï)) - зозрастегозя поагедовагав.-

еоссь f22.tt4hi2 стэезэпзя t,/^» 1 5 1 s п, iso^scteo Sj{ï)«

~ {i|Va, я сЛ£)}, к! я.п in «u, 5 s^D- глгчгпза po-

1 - 5 3 is 5 (?) 1

дпуоа ,yctcî423cst3 k3sto es!e»ei» s» i32|tj7"3!

с» е

p„m = sin (ei+1(i)-e1(i)) У .

Слоеность расчетов равна 0(n*log n).

Если изменяться могут лишь компоненты вектора 1, принадлежащие множеству I), то радиус устойчивости pn(i.D) в этом случае uosho вычислять по формула:

p„(i.B) - о i и --2-.

i с J а а 2 1/сц * шах 1/а,. ieSj(i)/-D. 1 k£S3+1(i)rB к

Слоеность расчетов равна O(n-log в + |D| -е).

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

вычисляется по формуле;

P0(i.E) к Ein

rg(i) - F»(t) + С

2 Fe(i)

Слсаность расчетов равна 0(п!).

Пусть ff^f) - шсввство перестановок 2S таких, что выполняется

соотношение: fs( I )•=?_(£) = вах Р„( 1 ): вэктор ё в (1,1.....1).

Е* а в

Тогда справедливы слздукдне теорзиы.

Теорема 10. Eomi ^(ё) л f(t) »» е, то радиус устойчивости р„(1,£) ыогно вычислить по

Слсетость расчет-os равна QCn-log а).

11. 1схн шюазство ?(?Me}t то ра(5) Е P„(t), в против-

ном случае р„(») ® 0.

О

В § 3.2 рассматривается устойчивость оптимальных решений в детерминированной систеиз обслузивания о одвги прибор!, где целевая функция шазт зад:

f_(i) «aas ЬЛяД), 2 IsLsn г

гдз 1^(3,?) я ^(Я)-^ -' зрвызввее смеявниэ, - дзрэк-пшный срок, а

::стерс;?у трэйуатсп обслужить требование Is Et.

Пусть hhcssctbo расписаний " таких, что выполняется ccotsoeb-

азэ Ojä D^s ...sO^, а икяестао И(я) - Us ЩЬ^яД) =»

Тогда справедливы следугздта соспгсионзя .

1,(1,t) - b.r(33,t)

pa(l)~ min nin таг-^---,

za f(t) issjai iskini^s.ij + IS^DI-S.¡5.^(2,J^dDI

?'(?) - ?,(f)

B(i)

n

Г ?,(i)-L(*,t)+e L,(:i,t)-P4(i)+e 1

p(t,£)=aiiHEa2 nin-—-,2dn сад—-- \

1 Я 1й1йП SM*)! Я läisn |SL(3) 1 J

гдэ ?'(H) - напквпгдгев нвошишальЕсе значеапе функционала с). Tsopswa 12. Если расписание Р0>, то

ь^(яд) - _

Pa(i)= ПЗД

¿!(За).15кгп|3,Д^) ^¡З^Я) 1-2-1^(1, )лЗ^(Я)|

р

Слсггиость расчетов равна 0(п ).

Теор8313 !Э, Если р„, на величина р„(5) > О тогда и только

тогда, когда выполняется неравенство:

газ: ЬЛя Д) <

2 Ра(?)= есля распгсаянз п « ?,. -

В 5 3.3. рассматривается устойчивость сшгиадьшх рзивнна в задача оболуяраная требований параллелыаюн адешичныш приборами, когда з качества цаловоЭ супкцЕл используется суммарное зреыя ебелу-гпвання •требований.

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

еея величин tp i с St, üi(l) - usóseство требований к таких, что (1-1).М+1 á k гяаШ { 1-E2.ni }. и 1 äp. гдэ г - Í(n-1)/13]+1, и [о] -- аяасольиао целое число не больна чей о. Доказаны слэдуадиа теореда.

Теорша 14. Если í - вектор длитеяьноате2 обслуживания требова-£22, ТО

р„(?) = а!д Clin Ein с t_ - t„)/ 2 , lala« tico,, <(í) м 0, (t) p 4

lala« qcOl+1(t) p« O^i) p P(i,£) =

p q

2-е

e

Сложность расчетов раша Q(n-lHn-log п) и 0(1), соотйствешю.

Теорзма 15, Если для некоторого индекса 1, 1sls(r-1), выполняется coGTHoaemie í-, = t-, ,„.,, то'для либого расписания а с o(í) выполня-

i.*i иг 1

отся равенсттво Ра (Í) - О- В противной случаз справедливо равенство

Когда прибор 1 етзет производительность а^>0 и длительность обслуживания требования 1 s í3 прнборои 1 равна a^-t^, то значение радиуса устойчивости вычисляется по форыулагд:

p0(í) = и i n (tj- tj.)/ 2, "ink -

- p(tjC) n е/-Е ,7, Islam

гдз - fc-ыа axsuern последователь^остат, полученной посла упорядочены т,1с€л ai-i, isirií, isla*, по ноубывааз».

Тгорзнл 16, Если для требований ke П и le ti таких, что t^ услогиг {?,, \о для лвбого расписания в « ¡>(?) радиус jcvc.r-nscoxs ?3(t) С£3£Н_0, В противней случай р (Í) в р„Ш.

В § Э-4 рассматривается устойчивость г.тмт.ткттггг регзпиЗ в аадз-че обслузивания требований дзуыя пдентичныии параллельгаши щзззоры-хз. когда целевая функция P„(i) aises ецд:

к

?_(t) ■ cas 1ЛЗ). s Ig Г!

Пусть Pg и - цногества требовашй, обслугзваеиых вра pacnnca-

__v »

hsh s на первой и второй щпборах соответственно; величина t) вычисляется ш формуле: = £ tj. число (^(t) « arg tsar d^(t).

< pk 1sk£2

s

В диссертации доказана справедливость слздупсих тосрец. Tecpsîa 17. Если 1 - вектор длительностей задачи. то

p0(ï)=nin пах aln----в----^--

eev(t) i*?<ï) Ш jpgJÎ),

p(ï.e)».

Ai)- ?s(ï)+c P,(ï)- Aïl+C

nia пах —-к-,пзх nia —----

a 1â3rs2 |Pfj s X&A JP^l

s»

Пусть paсписание u e

ÎECpS^a IS. Если сугествуат расписание a e o*u. такое, что

P^'* P^î то Pu(ï) = О. В протшшса случае, рц(?) = p„(ï).

Осесееегз результата диссзртецгп! спуйгппетваин в слэдугщх работах:

1. ДлгЕкевнч В.Б., Сотскоз 23. Н. йсслздовзппэ устойчивости ептпьгалыпи по быстродействия рзспис^шй. ИЕ£ ¿H ECCP.1SS7, Препринт H 9.

2. Алеежзвич В.Б. Исследование устойчивости в одно® зячаче теории расписаний."Becni ¿H БССР". Сер. Ф1з.-шт. иавук, 1939, ü 33. Аягшс9вач В.Б. УстоЗчивость ептг-гюлшх по быстродействии рсс.'зсз-вий сбслукшсшя тробоззннЗ двуггл идентичнши пргборакз. Десятый все-согзшй езшагпун, г. Езрзз-Г^-зсуг, п., 1SS3, Доклада кааезцуиз.

4. Длгпкзвнч-В.Е., Сотспсз D.H. УстоЗчпвосгь з задачах калаягярзого

дарного планирования. Весц± АН ВЗОР, Сер. ф1з.-тег. навук, 1S89, К 3.

5. Алшкешч В.Б. Исследование устойчивости оптимальных расписаний обслуживания требований одншы приборов. ИТК АН БССР, Доклада IV Всесоюзного координационного осваивания "Автоматизация проектно-конструи-торскил работ в машиностроении", Минск, 19S8.

6. Алшкевич В.Б. К устойчивости задачи теории расписаний. III Всесоюзная школе "Дискретная отядазацпя и компьютеры", г. Таштагол, 1937« Тезисы докладез.

?. Алвзкевич В.Е., Сотсков Ю.Н. Устойчивость оптимального раепиеенэк. Всесоюзная конференция по теоретической кибернетика, г. .Горький, 1932 S. Сотсков D.H., ¿лшкевич В.Б. Устойчивость оптшдальной ориентации ребер сыевазного графа. Доклады АН БССР, тш 32, 1933, Ы 2.

о

Подписано в печать 24.04.93 Формат 60x84/16. Бумага тип. К 3 Печать офсетная. Уч.-изд. 1,2 п.л. Tupas 100 зкз. Заказ ¿/Р

Отпечатано ка ротапринте Гродненского государственного университета ик. Я.Купали 230023, Г. Гродно, ул. Океихо, 22.