Алгоритмы и сложность оптимального обслуживания фиксированного числа требований в многостадийных системах Шахлевич, Наталья Владиславовна

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

Актуальность проблеми. Развитие теории расписаний, одного из разделов "исследования операций", вызвано практ: *еокоп значимостью оптимизационных задач, связанных о вибором наиболее аффективной последовательности действий и возникающих в различных сфераї человеческой деятельности. Кнтяеквяне исследования в области теории расписаний ведутся на протяаешш сорока лет.

Градационно задачи теоркі расписаний формулируются в термтгах требовании а обслужипащнг ях приборов п состоят в оптимизация процесса обслукпвапкя заданного множества требований заделнш кногествои приборов прі заданном критерии оптитачыгоотя. В зависимости от числа ствдаа обелукнвания требований системы принято подразделять па одноотадийвио и шюгостадийные. Под стадией пли операцией подразумевается процесс обслуживания отдельного требования отдельным прибором при конкретном обращении к отому прибору. Б диссертации рассматривается детерминированные мпогостадпЯшю С2сте:ш, состоят» нз га, т>\, различных приборов.

В завноппоетп от задоппоЗ діїсіцшдеті оболуплізипл требований мпогостадийнио мгетешд принята ігодраздолпть іга ююгоотодпйниэ системи с нефлигатсаанпавт .'.{зрзруяекп, скетемм с якеирозапншз одапагдавілм мврзрутшг гі, пс?;олац_в ckopp:cj с фдаоїіровпншмї рззлячншк і?аггрі'т?м;.

Слоппойть зади? сптнмашгопо QSwj-TJxraisw требований в гяіогостадйшн спст^пме доетагегспо Еорошэ изучена прл фиксированной значений чиеля п приборов обедуитаодой системи. Так, одпгы из первш опубяюювшпас: результатов в теории расписании принято считать олгоратм построения оптимального по быстродействию расшеения ободуяавяшг. п требований двумя приборами в системо с фякспрованвша' одинековкш моршрутаїга, прадлозаикнЛ Дхоноопоц и Белдманоы в 1954 году. Задзча привлекла внимание многих исследователей в последукщие года (Н.Л. Лепешипсгай (1967), У.К. Garey, D.S. Johnoon, R. Sethi (1976), O.K. Колышков (1976), (1984), Я.It. Ияфранскви (1973), Т. Gonzales, S. SahnI (1978), O.L. bfonaa (1979), B.A. Струсевич (1981)) it предопределила продолжение дальнейших исследования

многостадийных спетой с фиксированным числом приборов. Мскао сказать, что для большинства традиционных типов обслукзваэдих систем с различными ди^ошлинами обслуживания и о различными дополнительными ограничениями (например, с допустимыми иле запрещенными прерываниями, с отношениями предшествования, зад&ннкш на множестве требований и др.) известны наибольшие значения т, при которых задача оптимального обслуживания п. п > т, требований является полиномиально разрешимой, а тамга наименьшие значения га, при которых указанная задача становится ЯР-трудаой. Отметіш известный факт, что многие задачи полиномиально разрешимы при т=2 и WP-трудны при пь=3.

Начало исследования задач обслуживания фиксированного числа р требований, nsn, мокет быть отнесено к 1955 году, когда С.Аккерс it Да.Орндыан впервые предложили сведение задачи оптимального г Іслуаашаштя двух требований и приборами в системе е фиксированными марирутаы^к задаче отыскания кратчайшего пути на плоскости с недопустимими прямоугольными облеотями. Используя такой графический подход различные авторы (W.Szwaro (1960), W.W. Harugrave, Q.Memhauser (1963/, Н.И.Глебов (1968), В.В.Сврзах (1983), Ю.Н.Сотоков h985), P.Bruolcei» (1988)) разрабатывали полиномиальные влгоритмы решения указанной задачи.

Несмотря на повышенный интерес к названной задаче, в целом задача оптимального обслуживания фиксированного чиола требований п, nsm, в многостадийных системах при различных дисциплинах обслуживания изучены в значительно иеньоєй степени по сравнении с задачами о фиксированным числом приборов ні, тої.

Для систем с фиксированными маршрутами и фиксированным числом требований моїшо отметить результаты Ю.Н. Сотскова (1939). связанные ^л доказательством НР-трЗ'даосги задачи оптимального обслуживания трех тробований.

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

Сравнительно недавно начато изучение неоднородны! обслуживавдих систем, являющиеся обобщением традимяонных дисциплин обслуживания. Для одаях требований, обелузпшаодихоя в таких системах, технологические маршруты фиксированы, для других - нефиксированы. Все известные результаты, полученные для задач этого типа, связаны с рассмотрением фиксированного числа приборов, но но требований.

Поэтому представляется актуальным исследование многостадийных обслуживающих систем о фиксированным числом требований: определение наибольшего числа п требование, при котором задача остается полиномиально разрешайся, а также нвим8Ньпего числа п требований, при котором задача НР-трудна.

Поскольку теория расписаний возникла из потребностей ппктики, вторым важным ее аспектом является разработка алгоритмов рэшенид задач практической размерности. Как следует из результатов по исоледовачиї. слоаности, большинство задач теории расписаний Ш?~трудны уже при небольших значениях я и п. О сложности их реиения ыогно судять по истории рекения трех известных тестовых примеров, опублнкозанаых в 1963. году. В частности, решение наиболее популярного примера построения оптимального по быстродейстхии расписания обслуживания десяти требований десятью приборами было найдено лиш. в 1989 году Дя. Карлиером и Е. пагоном, т.о. спустя 25 лет после ого опубликования. Поэтому ис тользспанш в реальных епетеках оперативно-календарного планирования точных алгоритмов и даго приближенных с хорошши оценками точности решения не представляется возможным в силу чрезмерно большого количества перебираемых расписания. Бри попытке применения этих алгоритмов для решения практических задач большой или даке средней размерности могут быть затрачены значительные вычислительные ресурсы ЭШ без получения приемлемого результате. Применение эвристических алгоритмов такаэ не дает удовлетворительных результатов, т.к. ввриогики, приешимые для одной задачи, могут оказаться непригодными для получения достаточно хорошего решения

другой задача. В то ss время подбор ввристик для конкретных задач явлвяется трудно формализуемый.

В связи о отим представляется перспективней разработка алгоритмов и программ ₍ в которых предусмотрена адаптация используемых, правил предпочтения (евраатик) и некоторых других параметров к специфике класса решаемых задач, а ^акао примэнеше процедур декомпозиции исходной задачи на ряд задач меньшей размерности.

Целью работы является исследование сложности задач оптимального обслуживания требований в многостадкЯнш: дэтерминированта системах при фиксированном количестве требований п, п s т, а также разработка вврнотпчеоких алгоритмов оешения NP-трудных задач указанного типа.

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

Научная новизна работа заключается в следующем.

1. Для детершніфовапшх пшогостсдайнні сиоїєіі о фиксировашашн маршрутами получен предельный (т.е. ноулушваемзй) результат как по числу п обслуживаемых требований, пак в по числу га обслужявапцих приборов, устанавливающий почну» границу мэвду класоами полиномиально разреазаш. ц ЮР-трудных задач! доказана йР-трудаость указанной задачи при п=3, т=3 и асимптотнчаскоы рооте количества стедзг со обслуггоакпз грабований.

2. Для детерминировании шогосгодайта систем о нефкоированнима «арирутами, а токае для пеоднородннж обслукаваящих сиотеы ваервые полученн результаты, уоїанавляваиіяе значения тлела п прасованій, при которга отдельные задачи палзяомаальио разре«лк.ш, a ssynw - йР-трудоц.

идеи декомпозиции и адаптации.

Практическая ценность и реализация результатов.

Отметим два аспекта, которые связаны о исследованием сложности задач теории расписаний я нашли отражение в диссертации. В ходе доказательства принадлежности задачи классу полиномиально разрешимых задач обычно строится алгоритм, трудоемкость которого полиномиально зависит от длины записи исходной информации в бинарном алфавите, и втог алгоритм может быть примен при практическом решении задач большой размерности. В то же время доказательство принадлежности задачи классу NP-трудных задач не предлагает конструктивных путей ее решения, а лишь позволяет сделать вывод о цэлесообраэнооти разработки для нее приближенных (о оценкой погрешности) или ввриотических алгоритмов.

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

Апробация_іработы. Основные результаты работы докладывались и обсуждались на Республиканской конференции молодых ученых и специалистов "Применение инЛэрматики и вычислительной техники при решении народно-хозяйственных задач" *(г.Минск, 1989)5 на Межреспубликанской научно-практической конференции творческой молодежи "Актуальные проблемы информатики! математическое, программное и информационное обеспечение" (г.Минск, 1990){ на 2-ой Всесоюзной школе-семинаре "Декомпозиция и координация -в сложных системах" (г.Алушта, 1990); на 11-ой Всесоюзной конференции "Проблемы теоретической кибернетики" (г.Волгоград, 1990), на VI конференции математиков Беларуси (г.Гродно, 1992), а также на научных семинарах Института математики и Института технической кибернетики АН Беларуси.

Публикации. По теме диссертационной работы опубликовано 9 научных работ.

Объем и структур» аботы. Диссертация состоит из введения, двух глав, заключения, списка литературы из 113 нвименований, еодераат 138 страниц мапинописного текста.

содккшдак РАБОТЫ

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

В достаточно общем виде рассматриваемая задаад мокет бить сформулирован следуюд.'м образом. В обслуживающую систему, состоящую из множества далборов it = С1,2,...,п), одновременно поступают требование множества N = (1,2,... ,п). Для каздого требования известно, какими приборами оно долхио быть обслужено. Причем, если для кахдого требования 1ъЦ заранее задан (технологический) марярут его обслуживания приборами множества Ы, т.е. последовательность І = (і\, ІІ,.-., ї ), I е У, fsqsr_{, в

которой приборы обслуЕИБйют требование t, то такую обслуживающую систему называют системой с фиксированными маршрутами. Если ке 'сехнологачаскао маршрута m заданы и могут быть произвольными, то такую обслухиваюцу» еиоіему называют системой о нефиксированными маршрутами. В англоязычной литературе системы о нефиксированными маршрутами псинято называть "open-shop" н обозначать О.

CHCTew с фиксированными маршрутами принято подразделять на системы типа "flow-shop" (обозначение F) с одинаковиш маршрутами обслукиВсШия и на систем типа "Job-shop" (обозначение J) о фюсированными и, вообще говоря, различными маріярутеми. В рамках систем типа "flouy-shop" технологический маршрут I обслуям»ания любого требования ікії, не умаляя общности, мокэт быть представлен

в виде (1,2,...,т). Это означает, что кяяздое требование долгао быть обслужено внпчплв прибором /, зятем прибором 2 и т.'д. до тех пор, пока оно на будет обслужено последним по порядку следования прибором т. В рямняг систем типп "Job-Shop" кявдоа требование teJf может иметь свои уникялыгай технологический маршрут І = СІ,. ї₂,.... l_r ), причем номер отдельного прибора может

повторяться в маршруте - несколько раз, т.е. требование монет неоднократно обращаться к одному и тому же прибору. Кроме того, отдельные требования могут не обслуживаться некоторыми приборами.

Наконец, обслуживающие системы более общего' для теории расписаний типа, а тленно: неоднородные системы - могут быть определены следующим образом. Множество ' требований N, обслухашащихся в такой.системе, разбито па два непересекающихся по^шожествя: S_Q и Nj. Для требования множества V_Q теїнологичесізде маршруты не фиксированы (подобно системам типа "open-shop"), а для требований множества Jf. - фиксированы (подобно системам типа "flow-shop" пли в общем случае "Job-ehop"). Неоднородные системы будем обозначать через 0,J.

Таким образом, обслуживание требований ипояества II приборами множество И состоит в выполнении некоторого множества операций (оу Ор,..., оJ, Для систем о нефиксированными маршруташ типа О операция Oj, = <{,k> предстявляет собой процесс обслуживания требования і с її прибором . й У. Для сясяш о фиксированными маршрутами типа F и J операция о = представляет собой процесс обслухзгопния требования і « N прибором і' с- И при конкретном обращении к этому прибору па стадии q, 1< q sr_{. Для каждой операции <{ ,S> (или ) зяданв длительность ее выполнения tjb^ft О ^{(?^{а с}о^тветствешо}. Предполагается, что операция, будучи начатой, но прерывается вплоть до момента ее завершения. В противном случае, т.е. когда допустимы прерывания, вто будет оговярпзаться особо и обозначаться параметром Рг.

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

требования и каждое требование обслуживается не более, чем одним прибором.

Рбсгшсяние з обслуживания требований множества N приборами множества И -представляет собой совокупность предписания, характеризующих, какие требования обслуживаются какими приборами в каждый момент времени. Если прерывания операций запрещена, то расписание э однозначно определяется моментами начала tibf³), (t_t(3)) или завершения ^_ік(з) (l_tJaj) выполнения операций <<,>, fee*, (соответственно , f * g « r*_t), t є N. Если жэ прерывания операций разрешены, то выполнение отдельной операции может бить прервано в'' любой момент времени и возобновлено позднее, причем предполагается, что число таких частей операции *.:онечно, и суммарная длительность всеї частей операции <1 ,Ъ> {) равна заданной длительности t_(fe (соответственно t_{ ).

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

обработки требований кавдм прибором с целью минимизации заданной

целевой функции Т(з? = ?(Tj(a), 1_г(з),... Л_п(з)>, неубывающей от

моментов завершения обслукияания требований. Такой критерий

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

Наиболее простые и хорошо изученные критерии задаются функцией

?(з) = ї^цд.Сз) = max {^^(з)\\еЯУ, значение которой определяется

общим временен обслуживания всех требований множества И при

расписании а, и функцией ?(а) = Т^_{(з) со значением, равным сумма

п моментов завераення обслуживания требований! Т ї,(а). Известно,

i=1 ¹ что еоли некоторая задача является NP-трудной при критериях

^ящд/а; и Efjfa;, то она остается NF-трудной и при других

традиционных критериях оптимальности (таких как максимяльное

временное смещение, суммарное запаздывание, число запаздывающих

требований и т.п.).

При формулировке отдельных задач теории расписании

используется сокращенная форма загаси П₁|П₂|П₃|П₄}П_в|П₆. для

которой параметр IL определяет тип обслукивящей системы и

принимает значение О, F, J или 0,J% пар'.\метр П„ - вто чиоло я

обслуживающих приборов: пирометр п₃ - это число п требований: Л. характеризует длительности операций (например, t^a О, t_;fe> О, tj_fe- * или ftjjJ для целочисленных длительностей операций); Пц указывает допустимость прерываний (1Ц= Рг, есла прерывания допустимы, или IL= noVr, если прерывания запрещены); параметр ,ig определяет целевую функцию Р(з). Например, задача минимизации общего времени обслуживания п требований двумя приборами (т.е. построения оптимального по быстродействию расписания) в системе о одинаковыми маршрутами и произвольными длительностями операций при запрещенных прерываниях мохет быть описана с учетом введенных обозначений следующим образом! J|ra=2|n|t_{ *0|noPr| Ъ^^в). ьудем использовать такие сокращенную форму записи ?\т=2\п\\\ї_шх(а), пригашая по умолчанию параметры П^ и IL-, равными t₍ а о и гшРг соответственно.

В первой главе для отдельных задач т&ории расписаний о фиксированным числом требований устанавливается их принадлежность классу полиномиально разрешимых или классу NP-трудных задач. В первом случае предлагается алго^лтм решения задачи, сложность которого ограничена сверху полиномом от длины записи исходной информации задачи, закодированной в бинарном алфавите; во втора» случае строится полиномиальное сведете извеотной Л^гР-полной задачи к задаче распознавания, соответствующей исходной вкстремальной задаче теории расписаний. В качестве эталонной ггр-полвой задачи в дисев:--?вции используется задача о РАЗБИВШИ, состоящая в следущом. Дано множество А=(1,..,,2а), каждому елементу I которого сопоставлено нэтурэльное число е₍, и 8. = 2S. Если А_ъсА. то В_ъ= о,. Существует ли разбиение

мнокєсгва А на два подмр-жествя А₁ и А₂, при которых К_}=₂? Если такие подмнояеетва 4_; и А₀ существуют, то задача о РАЗБИЕНИИ имеет решение.

Первая глава состоит из трех параграфов. В первом пара; /"фа рассматриваются обслуживающие системі' с фиксированными мариругаш, во втором - с нефиксированными, а в третьем -

неоднородные системы.

Основной результат h 1 состоит в доказательстве NP-трудности задачи J|m=3|n-3( ((Т^^.Гз; оптимального обелумтения трех требований тремя приборами в системах с фиксированными различными маршрутами обслуживания. Напомним, что в системах с фиксировакньал различными маршрутами обслуживания кавдое требование может неоднократно обращаться к одному и тому же прибору, и 'поэгому число операций (стадий) не обслуживанию отдельного требования мокр" оказаться сколь угодно большим. В рассматриваемой задаче неограниченно именно количество опараций по обслуживанию требований.

Теорема 1.1. Если га=3 и п=3, то задача j|n|n|| ІЇ^^Са; является NP-трудаой".

Д>? доказательства георемы в качестве ^талонной NP-полной задачи используэтся задача о РАЗБИЕНИИ с дополнительным условием: шохество А₁ включает ровно один елемент из каадой пары 2І-І, 21, islsa. Не умаляя общности, предполагается, что ^Є2І-1^ФЄ2І ^к'

более того, ^е2і-1^>е2і *^^{я ЕсеІ} ** ^^stsa'

Построено полиномиальное сведение указанной IJP-полной задачі: к задаче распознавания, соогвотствукцей исходное задачо составления оптимального по быстродействию расписания! существует ли для задачи J|ro=3|n=3| | |ї„_(я,) расписашо е=2 (1) текоо, что чии^³ ^ ^s У ^ ^заД^анН0ГО целого числа у. Дли отого построена индивидуальная задача J|«=3ja=3|| IT^^fs; с обда числом операций

по обслуживанию требований множества If равным i4-a, а для нес

о о

доказано, что расписание s , при котором t_tlxtx(s )⁵У существуем

тогда и только тогда, когда задача о РАЗБИЕНИИ имеет решение.

Полученный результат устанавливает точную границу месду

полиномиально разрешивши л ИР-трудныш задачами оптимального

обслуживания требований в системах с фксиров8ШЫ..я различный:

маршрутами, поскольку уменьшение хотя бы одного параметра задаче

приводит к полиномиально разресимому случаю: известно, что .задачи

J|ffl=2'n||It-g-lsJ оптимального обслуживания п требований двумя

приборами tr_t<2), а таїдта задачи J\m\n=?.\\\?(3) оптимального

обслуживания двух требований т прж.ораыи полннощвдыю разреши і.

Доказательство теоремы 1.1 оказалось далеко нетривиальным и приведено в диссертации в полном объеме. Доказательства остальных результатов 1 основаны ні незначительных модификациях основного прішера задачи .7|я=3|л=3| W^m^t³) п приведеш в боле крат: ft форме.

Следствие 1.1. Задаче J|m^3|n=3| llEfi^s; является HP-трудной.

С л о д о і в я о 1.2. Задачи J\n=3\n=3\\Pr\t_TXlx( и J|n=3|n=3| \Рг\}$_і(з) являются NP-трудными.

Помимо систем с фиксированшш различными наршр^-гвші
оЗслукітаїшя (п.1.1), в $1 рассмотрены таїсяе еястеш с
фямпровотшш одинаковыми ыаршрутаии обелітккваняя (п. 1.2).
Заметім, что поскольку каздсе требование обслуживается в
соответствии с маршрутом вида (1,2,...,т), то число операций по
обслуживанию каждого требования равно п. По&тоыу все результаты
п. 1.2, связаннее с доказательством ДО-трудно^ти для систем с
фиксированными одннаїсовимл маршрутами, получена при

неограниченном гнач&пга п.

Теорема 1.2. Если п=3, то задачи Ля|п| ІРт^^^/з; и F|ra|rjj |Pr|f_tfa,) являются NP-трудзшш.

Заметим, что исследование сложности задачи составления оптимальных расписаний обслуживания трех требовании начато в работах Ю.Н. Сотскова (',939): им доказана NP-трудность задач обслукивания требовании с іїиксированьшми различными маршрутами: Jltn^r^Wlt^d), Jln^^WPrtf^c}, J!«=5|n=3|||Et_tf3j, a также HP-трудность задач обслуживания требований с 'Ъсксированыкш оданаиовыш! ь-рарутаїдлі F\m\n-3\\\t_mai,(3), ?(m|rib3||t_t *0lt_{*f3.).

В 2 рассматривай: ся задачи оптимального обслуживания фиксированного числа . требования п, п * т, в системах с нефиксированными маршрутами. Следует отметить недостаточную изученность втих систем при рассматриваемом условии п s ... по сравнении с системами с финсировашши маршрутши. Та", практически всэ пэвестаиэ результаты по исследованию слситости

задач оптимального обслуживания требований в многостадийных системах с нетаксированными маршрутами связаны с рассмотревшей фиксированного числа приборов ш, и лишь для критерия оптимальности ї_г (з) (т.е. для даними атпш общего времени обслуживания) из результатов с фиксированным числом т могут быть получены результаты с фиксированным числом п обслуживаемых требований, т.к. для этого критерия и для рассматриваемого типа обелуживвемііс систем множество приборов и множество требований мокно менять ролями не изменяя сущности задачи.

Для определения числа требований, при котором задача с нефиксированными маршрутами WP-трудна, из известного результата об КР-трудности задачи 0|m=3jn|| If^^fa; при n=3 (T.Gonzalez, S.Sahnl, 197о) нетрудно получить доказательство NP-трудности задач Р\^т\^п=3\\^_пах(з) и 0|m|n=3| | |Х^_гСз^ч при л=3, откуда следует КР-трудность' задачи оптимальне о обслукиванпя трех требований в системе с нефиксированными маршрутами без прерываний при всех типичных для теории расписаний критериях оптимальности.

Для определения наибольшего числя требований, при котором задача о нефиксированными маршрутами полиномиально разрешима для произвольного регулярного критерия ?(в), использовать известные результаты о фиксированным числом приборов не удается. Такое число требований установлено в 2, где предлагается алгоритм трудоемкости 0(т) решения задач 0(п|п^Р| \\?(.з) с 0\т\п=2\\Pr\F(з). Значение п=2 является наибольшим значением числа обслуживаемых требований, при котором задачи с нефиксированными маршрутами без прерываний полиномиально разрешимы, поскольку, как отмечено выше, 'задачи оптимального обслукивания трех требований в системах с нефиксированными маршрутами Іії-трудньї.

Алгоритм построения оптимального расписания состоит в следующем. Множество всех индивидуальных задач разбивается на непересекающиеся подмножества, причем каждое подмножество характеризуется набором некоторых соотношений, связывающих исходные данные задачи (длительности операций). Общ^е число таких

поданоквств для задачи 0|п|л=2| \\?(а) равно восши, а для зодьчи 0|n|n=3| \Vr\F(o) - трэд. Порядок проверки соотношений представлен в виде дерева, шокєсгво висячих вершин которого и определяет разбиение ипомества всех :*чдпвидуалышх задач на подшокества. Алгоритм става? в соответствие кавдой виоячой вершине дереза расшісшио, которое является оптимальным для всех индивидуальных задач раосматрзшаеиого подмножества. Таким образом, для каздого подшоаества индивидуальных задач определено соответствующее оптимальное расписание, и применение алгоритма для решения пндивидуальноя задачи состоят в определении, какому подмножеству прднадлекдт данная ігадипидуальная задачи.

В 3 рассиагрпваптся задачи оптимального обслуживания фзксировапного числа требований п, п < т, в неоднородных обслукавающих системах. Впервые терши "неоднородные системы" бил введен В.А. Струсевичем (19Я9). Им иоследовена сложность втих падач при фякспровшном число приборов я, а именно: при г-2. 3 то ss время сло&юстъ задач оптимального обслуживания форсированного числа требований п, ия, в пео.-тіоро, дах системах практнчесіш но исследовалась. В 3 диссертации исследуется сложность указанных задач при фпсскровапном числе нрлборов, а именно при п=2.

В п. 3.1 доказана ЙР-трудноеть задач 0,j\m\ru=3\ | \Ъ_пах(а) и 0,j|m|n=?| | \Т{(з) оптимального оболугзшанпя двух требований в неоднородных системах без прорнвений для простейших критериев оптимальности: Ту^із) л Т$,(я), а в п. 3-2 для задачі! 0,J\n\n=2\ \Рг\?(з) с допустиміша прерываниями и произвольным регулярний критерием F(o) предлоаен \алгорпти трудоемкости 0(т + г). Нопсяшям, что задачи оптимального оОсл-Еяваппя двух гробеваний п однородных системах полиномиально разрешат ?!озпв:іе»до от гого, раэр иены прерывания шга ват.

С е о р о ц а 3.1. Если п=2, оо задача 0,J|ffl|n| | \'i_vax(3) :іздяс-гоп іІР-таудпсЗ.

'^;r,-.i локчеательотва тоовемч 3.1 построено їю,:г,їнод:ш^ 'со г-і,»;іс!г<о ггэпосг'нсп fip-полнсй задали о РАЗР.ТЕКИІ к соотве'ГствугпИ ' ₍;г.-.,г) rwuDrmiiawa (п тепло: существует ля раеппотаю г; Cos

прерываний обслуживания двух требований приборами множества If такое, что l^Ja) а у). Для построенной индивидуальной - задачи O.J\m\n=2\ H^yf і) показано, что оптимальное раописаниэ а вяз нрерчваний, при котором Ї^д-Сз) * у, существует тогда и только тогда, когда задача о РАЗБИЕНИИ имеет решение.

Доказательство второй теоремы нетрудно получить на основа незначительней модификации доказательства теоремы 3.1.

Теорема 3.2. Если п=2, го задача 0,J|m|n| | lEFjfs) является NP-трудной.

Итак, задача 0,J\m\n=2\[\F(a) оптимального обслуживания двух требований в неоднородных системах КР-трудна дане при наиболее простих критериях оптимальности: F(a) = ^^ngfa) и PCs; = Е_{(з,). Учитывая сводимость задач построения оптимальных расписаний при различных 'ритериях оптимальности, градациоьло рассматриваемых в теории расписаний, ыоано сделать вывод о том, что при любом из таких критериев задача 0,J\m\n=2\\\l(a) остается в классе НР-трудшк.

В п. 3.2 показано, что задачи, HP-трудность которых установлена в теоремах 3.1 и 3-2, становятся полиномиально разрешимыми, если только допустить прерывания в процессе выполнения операций. Более того, она полиномиально разрешимы при любом регулярном критерии.

Для задачи 0,J\m\n=2\\Pr\F(a) подучено необходимое в достаточное условие, при котором оба требования 1 и 2 обслуживаются без задержек в штервалад 10, t^J и lO.tgl соответственно (теорема 3.3). Напомним, что tj s t^- суммарные длительности операций операций по обслуживанию требований 1 я. 2 соотьетсвенно. В ходе доказательства достаточности сформулированного условия предлояен алгоритм А построения искомого расписания. Этот алгоритм ь._пользует алгорїтм трудоемкости 0(т) решения задачи 0|m|n=2|\рг\Т(з) оптимального обсл.живанкя двуЕ требований в однородной системе с нефиксированными маршрутами, описанный в 2 диссертации. Общая трудоемкость алгоритма для "неоднородного" случая линейно зависит от числа операций по обслуживанию требований..рчевидао, расписание, при котором обр

требования 1 n 2 обслуживаются без задержек в интервалах /О, ^f₍J a [0,t₂] соотЕотственно, является оптимальным при любом регулярном критерии F(3).

Рассматриваемая задача 0,J\n\n=2\\Pr\F(a) how дована такке я в случае, когда необходимое и достаточное условие отсутстг"*я задерезюк в обслуживании требования 1 в интервале (О, t^l или требования 2 в интервале [О, t^J во выполняется: качество расписания при втом определяется распределением задержек мозду требованиям!!. Заметим, что при выполнении необходимого и достаточного условия отсутствия задеркек одно и то ка расписание является оптимальний прл всех регулярны, критериях; если ж ото условие не выполнено, то для одних целевых функций оптимальны одни расписная, для других F(s) - другие. Трудоемкость алгоритма В, предложенного для решения задачи в рессматривееиом случае, как а трудоемкость алгоритма Л, линейно зависит от числа операции по обслуживанию требований.

Из результатов главы 1 следует, что уке при небольших значениях пат задачи ептималъяого обслуживания требований в многостадийных системах являются NP-трудныыл. Вопроси практического репения задач оптимального обслуживания требовании в много-отадийаых системах требуют создания удобных средств для разработка алгоритмов. Следует отметить, что в терминах сетевых моделей типичные для задач теории расписаний ограничения описываются наиболее естественным образом. Эти модели используют для представления исходных данных оііеаівшшй граф, содержащий множество (ор?9Втироввнных) дуг и множество (неориентированных) ребер.

Во второЗ главе предлагаются алгоритмы рошэния з^дач оптшйлшого "Сслувшйния требования в многоствотзыых сисї «ах, основанные на сетевой модели обслуЕиващея системы. В 1 приведено ошеание сетевой модели; в 2 описаны ввристические алгоритмы решения задачи o,j|m|rc|||fYs; большой размерюсти -декемпоздщиогаый (п.2.1) и адшташшя (п.2.2).

Декомпозиционный йлгороптм осуществляет оарястичоскоо решение исходной задачи на сспопе решения подзады

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

Адаптивный алгоритм предназначен для решения класса однотипных задач посредством "настройки'¹ своих параметров яа етапе обучения. Процесс обучения состоит d решении задач ограниченной*размерности, которые могут бить получены с помощью процедури декомпозиция, описанной в п.2.1. На етапе обучения осуществляется такве выработка логических правая, пркменяеїжж при решении задач большой размерности и учитывающих специфику раооматршоемого класса задач.