Введение к работе
Актуальность теш.
Теория расписаний как саыостоятельши раздел исследования операций ииэет вагное прикладное значение. Одной нз задач, нзучаешг в ранках отой теории является задача оптаизадпи процесса обелугивавня конечного ыноаестза требований з двтергшпірованнсй система, оодзрка-щэй ограниченные ресурсы- Для каждого требовгзпя задается ыомент его поступления в систему. Требование доено пройтк одау идя несколько, в „завнсЕмостн от условий задачи, етадай оболугиваЕия. Для кавдоЭ стэдкн указывается допустпыыа наборы . ресурсов н длительность ебедуглЕсшїя требования. Оговаривается возможность прэрнвавзв процесса обслуживания требований. Ограничения на очередность обслуззгзания трсбовзнкЗ задаются, как правило, в вида бинарного отгсаепня строгого порядка.
Широкое практическое значение задач весрни раедааекяз- (упраздениз производством, транспортом, строительством, вкчислЕтадьшшз еяетваа-uz н т.д.) прнвлзкавт к ним серьезное внимание специалистов по ддск-рзтпоЗ ыатеизтзкэ. Однако при рпвработкэ сфїоктавшіг едгоритиоз рззе-пня простзйпх, на первнй взгляд, задач теории расписании била встречена сначЕТвльЕНЭ трудности, сзязаншгэ со структурной слезностьв вл-
с» пзназванных задач. Косвенным подтвзрздением отого обстоятельства яв-
лязтся ЙР-трудность болыгшства практически инторэешп задач теории рзсписЕНПН.
Вгаотэ о той. Солоэ естественное отрггэнпе динаїшся ряда вкскоггз-ЕО-ыатекатЕческвх я проззвадствэшнг ігададвй, сшоіазає>іх с использо-ESHsau задач tscjct ркспнеепиЗ, огтигззтея в тех условия!, когда входные характаряотша езетгу езсяугггакві. (naspsssp. днатасьпостз
-4 -сйслужавангя трзйозшзЗ, врезана пзрен&ладзк приборов, дарзктїгвшга срока Е т.д.) гададугся нз яочно, а в нзкогорнх пределах возыозньа изменений. В сэязи с агаи, npsodpsTEsi актуальность ЕСйЕздоЕанга ycTaS-чизостз в задачах теорхг раазжсахай, т.е. изучение свойств сдгомаль-esz рєізєЕЗй задача щи варзшцлз ядадоглу иоголнт-пг даяттатг. Исаладоза-E2S устойчивости е задачах теория раеягаашй -предстааляэт значительней пяїзрзс так^э в связн с теп, 420 ето исаладованаа позволяет в некоторых асучаях акгоцаянеоіи далучагь р-заєнсз Еоех задач, параметры которые отяясатся о-з параметров исходной задача на некоторую! вапнчгау, значаща которой еичзсдяоия в процесса їааого носледо-вяния. Крема отого, так как часто рзЕакаа и чесло:щ»э есхсдшіз дзшша задачи ігагут быть получена с некоторой погрешность», зненае радиуса устойчивости шзволязт nposejasb раальноа няаченпз полученного pass-шіл задача. Сцепка радиуса устойчлаоота длгд ішфзрмацшз о точности негодных даниаг, которуа Еєобходз» сивіть пэред таи, как щсовупать к
рЗЕЗЕЗЕ аяіг/штг.
Цедьз работа явяязгся:
-
Исапздезгпнэ устола^озгя сптЕиальшгх ео бцгтродайстЕню расписаний.
-
Исагэдозгигю усїойчзЕоет; сйЕхальЕых possess в вшгрекаяьшг задачах на агасаннізі графах.
-
izasa устсйчзеосте в сдгюахщпгщг системах сбслузгвгшая.
-
Раэрабсгка кзтодоз ЕНйаславхл точкою s прк&пнагнного злаченая радіуса устоічгЕоетд сатпмзлъпах рзохкеанаЗ.
Научная новизна. 1. Получаны ссоїноззння иагщу радиусами устоа:-^ssocts, удаЕлатворяхщзпш различили ояраделэшггм. 2. Задача рзачеэа
- 5 -точного значеная радиуса устойчивости иясагастза всех оптгнальных решений: в задачах на сікезенііх графах езедена к задаче математического прогрешгщюЕЕНкя. 3. Последовала устойчивость ыаокеотва всех оптимальных решевги для разлкчнях допустимые взрняцга параметров задачи: с талучеЕЫ аиалЕТЕчесюто формулы расчета радиуса устойчивости. 4. Исследована устойчивость отделкзого оптимального репезия и получены аналитическая формула расчета радиуса устойчивости, а такге необходимые н достаточные условия бесконечности радиуса устойчивости п необходшыз к достаточные условия, при выполнении которых радиус устойчивости пояссз.тел9Н. 5. йеследовена устойчивость .кнезеетва решений по функционалу.
' Методика исследования-. Цетодяческуп сспозу р-боты составляв? лэ-гако-ЕсаЕбпнаторшю иэтоды дискретной математика, методы ыагс-м&игчее-кого прогрзїаарованЕЯ, теории грсфов и тэорЕя расписаний.
Практическая знашагость. Результата диесвртационпоа работа ьвзгут быть использованы при режзннн задач оперативно-календарного планирования, а тзкгз ща генерации тестових задач нэ сыэееепнх графах о sa-
ДЗНЕ2И ESOSaCTBOM psssssa.
Публикация п саюбвдзя рг.бота. По тсыэ дгвевртаддз спубляксзгго З печатных работ. Осеоейзэ результата дэкладазалясь es евкзаерэ в лаборатории иззс Н Вэларуся, р.ч ЗолаавзясЭ ктгфзрєквзі та мерэтгчзсяан йЕбэравкпга (г. Горький), za Дзсятсу пзэсеззнсм сзагогауиэ <г. Карзз-їіизоуу).
Структура а сбъеи работа. ДЕвоэр-тгдал соотетг из евэдэекя, трзд глйз, ваклотения к свисла ляторатури {73 ншшзисгегзя).
Обьак работа - 110 jcmscs гхаезппязегагэ кпегз.