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

шдекйй наук гшшго!

институт наташюси

Ifa лргзй.*

Ш1ШШ Кеталья ВладолгзоЕЕа

алгоритш и окяиосхь ОГГЕЗИ.ШЮГО обслшвмш «шш)вшюго числа тревовшш в Ш0Г0СТАЕ2!НН2 СЙСЯПЖ

Сседааакость 01.01.09 - 14 Lfaisiissnssssan -пгг^кг.гз

АВТОР2ÖEPAT

даосертацги es аснскз^та ег:г'сп

"кандидата фЕЗЕКо-иагеиапгаоепи saja

Шаек - 1993

Работа гшшнена з ордэна Трудового Красного Знамен» Институте технической кибернетика АН Беларуси

Неутщца руководитель: доктор а тела чич? сках наук

Сотскоь Юрий Назаровгч

Официальное оппоненты: доктор фйзкка-матомй-игюскп наук,

профессор а^длчев Вдадоар Алексеевич;

кандадаз? фгаико-ыятемзютзских наук, еяаретй научяка сочгрудев Деилдегко Вкгьгай ¡¿иха&ловяч

Ведущее предпряятие: Вычислительный цонтр РАН

Згацяга дкссергагш состоится " 13" декабря 1592 г. в "<ь и Чаоов на заседание спэциализпроЕШШого совата К 006.19-01 в Институте математики АН Беларуси (220072, г. Минск, ул. Сурганова, 11).

С диссертацией ысшю ознакомиться в скблютеко Института «атгца-лгки АН Беларуси.

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

Ученай секретарь спевдшшзированвого совета, калл* <£пэ.-ыат. наук

1992г.

ЛЯс-п^Ц- А- и" петровский

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

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

В затетшоетп от зодг.шоЛ дцецяпдппи оболупшзшш требований мпогостадвйпяо мгетсны щиплто подразделять ïtq гаюгостадпйшэ енот cm с нержяроваяпгя! марзругаш, епстеш с {здкеирозашшмз одттнетошлм нврзрутшг и, псколац, (T.cwj. с {отоировпянамл различными каггрутум;.

Слогаоать эаднз ошишаяытогс оЭДогэт&пкл требования . в гдтогоетадгйш ■ система:: доотйгочео горогэ изучена прт фИКОИрОВаННОУ ЕПаЧОНЛЯ чледр п приборог; обедуютеодой плетены. Так, одига пз первш опублягковшпас: результатов в • теории расписаний принято считать алгоритм построения оптимального по быстродействий расшойшя ейелуяявянм п требований двумя приборзии в системе с Сикспрованши одпнековнмя ывршругани, прэдоозаиннй Дхоноопоц и Белдманш в 1954 году. Задача привлекла внимание ¡.яогга исследователей в последующие года (H.A. Лепешинсгай (1967), Ii.К. Garey, D.S. Johnoon, R. Seth! (1976), O.Ii. Мельников (1976), (1984), Я.Г5. ШяфранскЕЙ (1978), T. Gonzales, S. Sahni (1978), O.L. îlonaa (1979), B.A. Струсевич (1981)) it предопределила продолжение дальнейших исследований

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

Начало исследования задач обслуживания фиксированного числа р требований, пяп, мокет Сыть отнесено к 1955 году, когда С.Аккорс 1! Да.Орндман впервые предложили сведение задача оптимального г Юлузашаштя двух требований и приборами в системе е 'фиксированными марирутаы^к задаче отыскания кратчайшего пути на плоскости с недопусткмши прямоугольными облестями. Используя такой графический подход различные авторы (W.Szwaro (1960), W.W. Hardgrava, Q.Memhauaer (1963/, Н.И.Глебов (1968), В.В.Серзах (1983), Ю.Н.Сотоков ( 19S3), P.Bruclœi» (1988)) разрабатывали полиномиальные алгоритмы репения указанной задачи.

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

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

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

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

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

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

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

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

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

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

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

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

2. Для вотврминарованшгх шогостодайных систем • о не^лхешров иарсрутазд:, а чокао для кеоднородтн обслуштаэдих сиотеы ваервые получен« результаты, у&гановяявйшдае значения тлела п ?робсваяи39 при которш отдельные садзчи полаяомаалыю разр&дайг, а другае - йМ'рудоц.

3. Кяя рвттп ¡Фнвд'Ша оадач Совыгоа разыараосгл отиЕ:а;;ь:£ето сбояргэания ироОов£ааЛ а дадоргашровсаваг! шогостядайшх ейотеааа: р^дксшиы оьрао>лшшс:э алго&тш, сапш евг-ове^ :;ол,е.иЛ обех^^ш^И с:-;сч'ё;*и и шУхи>эугаяо

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

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

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

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

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

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

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

СОДОТСШК РАБОТЫ

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

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

состоящую из множества приборов if = (1,2,___,п), одновременно

поступают требование множества N = (1,2,...,п). Для каздого требования известно, какими приборами оно должно быть обслужено. Причем, если для кявдого требования заранее задан

(технологический) марирут его обслуживания приборами множества И, т.е. последовательность ll= (Ij, Z^,..., ), I^ е У, isqsr{, в

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

Системы с фиксированными маршрутами принято подразделять на системы типа Vlew-shop" (обозначение F) с оданаковиш маршрутами обслуживания и на систем типа "Job-shop* (обозначение J) о фнссированными и, вообще говоря, различными марорутеш. В рамках систем типа "flou>-3hop" технологический маршрут 0бслуияг»1шия любого требования ieN, не умаляя общности, мокэт быть представлен

в виде (1,2,...,т). Это ознячяет, что кладов требование долгао быть обслужено внячяле прибором 1, зятем прибором 2 и т.'д. до тех пор, пока оно не будет обслужено последним по порядку следования прибором п. В рямхях систем типа "/оЬ-зЛор" кявдое требование (еМ может иметь свой уникальный технологический маршрут (I*. •. -, причем номер отдельного прибора может

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

Наконец, обслуживающие системы более общего' для теории расписаний типа, п именно: неоднородные системы - могут быть определены следующим образом. Множество ' требований ?/, обслуживающихся в такой.системе, разбито па два непересекающихся по^шожествя: II0 и Яу. Для требований множества технологичес:эде мярпрутц не фиксированы (подобно системам типа "ореп-еНюр"), а для требований множества - фиксированы (подобно системам типа "/То^зЛор" плн в общем случае "¿оЪ-зНор"). Неоднородные системы будем обозначать через О,/.

Таким образом, обслуживание требований нпояеетвя /Г приборами множества 1/ состоит в выполнении некоторого множества операций (О], Ср...., ог>. Для систем с не^яксирон я шия маршрут я? я типа О операция о^ - <{ ,к> представляет собой процесс обслуживания требования 1 с 1! прибором й й У. Для систем о фиксированными маршрут е.ми типа / л J операция о = <1 ,<р представляет собой процесс обслугашпния требования I « N прибором с- И при конкретном обращении к этому прибору па стадии д, 1< д . Для кяадой операции <■( ,й> (или << ,д>) заданв длительность ее выполнения О а^ О соответственно). Предполагается, что операция, будучи начатой, но прерывается вплоть до момента ее завершения. В противном случае, т.е. когда допустимы прерывания, вто будет оговариваться особо и обозначаться параметром Рг.

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

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

Расписание з обслуживания требований множества N приборами множества И представляет собой совокупность предписаний, характеризующих, какие требования обслуживаются какими приборами в каадый момент времени. Если прерывания операций запрещены, то расписание э однозначно определяется моментами начала t ^faj (tj-fз)) или завершения (^iq(3J) выполнения операций

<t,fe>, fee*, (соответственно <i,q>, 1 s q s r{), t e N. Если «а прерывания операций разрешены, то выполнение отдельной операции может быть прервано в'* любой момент времени и возобновлено позднее, причем предполагается, что число таких частей операции конечно, и суммарная длительность всв1 частей операции <1,К> (<t,q>) равна заданной длительности t(fe (соответственно t(<?).

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

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

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

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

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

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

?(з) = ?mr(a) = max (il(3)\tnH), значение которой определяется

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

расписании з, и функцией F(з) - со значением, равным сумма

п

моментов завераешя обслуживания требований! Г f,(a). Известно,

<=1 1

что еоли некоторая задача является NP-трудной при критериях fjjoj.l's; и С а), то она остается NF-трудной и при других традиционных критериях оптимальности (таких как максимяльное временное смещение, суммарное запаздывание, число зшшздыващих требований и т.п.).

При формулировке отдельных задач теории расписаний используется сокращенная форлв записи П1JЛ^ ]ПЭ }П4 ¡П^ |П6, для которой параметр ГЦ определяет Т1Ш обслукивящей системы и принимает значение О, Р, J или O.J; пв^.летр П„ - вто число я

оболушващш приборов: параметр П3 - это число п требований: Л^ характеризует длительности операций (например, о, Х^ О.

1 или М^! для целочисленных длительностей операций); П^ указывает допустимость прерываний Рг, есла прерывания

допустимы, или поРг, если прерывания запрещены); параметр определяет целевую функцию Р(з). Например, задача минимизации общего времени обслуживания п требований двумя приборами (т.е. построения оптимального по быстродействию расписания) в системе о одинаковыми маршрутами и произвольными длительностями операций при запрещенных прерываниях может быть описана с учетом введенных обозначений следующим образом; г{д*0|поРг| ьудем

использовать также сокращенную форму записи ?\т=2\п\\\1пах(а), пригашая по умолчанию параметры П4 и П^, равными о и поРг соответственно.

В первой главе для отдельных задач тьории расписаний о фиксированным числом требований устанавливается их принадлежность классу полиномиально разрешимых или классу №-трудных задач. В первом случае предлагается алго^лтм решения задачи, сложность которого ограничена сверху полиномом от длины записи исходной информации задачи, закодированной в бинарном алфавите; во втора« случае строится жшшешальяое сведете известной }}?-полной задачи к задаче распознавания, соответствующей исходной вкстремальной задаче теории расписаний. В качестве эталонной «УР-полиоЙ задачи в диссертации используется задача о РАЗБШЭДИ, состоящая в следующем. Дано множество А=(1,...,2а), каждому влементу I которого сопоставлено натуральное число е£, и

£ а. = 2Е. Если АъсА, то Въ= £ е.. Существует ли разбиение <еЛ 1 а» я I ,

множества А на два подар-хеотвя А1 и Аг, при которых Если

тэгае подмнокества 4; п А0 существуют, то задача о РАЗБИЕНИИ имеет решение.

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

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

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

Теорема 1.1. Если т=3 и п=3, то задача ^|и|п||является ЯР-трудной.

Дл? доказательства георемы в качестве ^талонной Щ>-полной задачи используэтся задача о РАЗБШШ с дополнительным условием: шохество А1 включает ровно один элемент из каадой пары 21-1, 21, 1Маа. Не умаляя общности, предполагается, что е21-1Фе21 к* более того, е21-1>е21 Есег **

Построено полиномиальное сведение указанной Г?Р-полной задачи к задаче распознавания, соответствуюцей ¡¡сходной задаче составления оптимального по быстродействию расписания! существует ли для задачи ^|т=з|п=3||расписание е°=2 (1) такоо, что 1^(3 ) з у для заданного целого числа у. Для этого построэш индивидуальная задача J\m=3\n=з\\\^mx¡::(s) с обда числом операций

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

о о

доказано, что расписание в , при котором ^ггах^ '^ оусеотвуе',,

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

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

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

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

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

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

J\чi=2^n\\\tm:a,(з) оптимального обслуживания п требований двумя

приборами ¡г,<2), а гапта задачи J\ш\n=P.\\[T(з) оптимального

обслуживания двух требований т прис.ораыи полиномиально разреши i.

Доказательство теоремы 1.1 оказалось далеко нетривиальным и приведено в диссертации в полном объеме. Доказательства остальных результатов §1 основаны hi незначительных модификациях основного примера задачи «7|я=3|л=3| 11?()тГэ/) и приведены в более крат: ft форда.

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

Слодотняо 1.2. Задачи J[ui=3(n=3|\'Pr\trxlx(3) я J|n=3|n=3| |Pr|Eftf3,> являются КР-трудаыми.

Помимо систем с фиксированными различными маршрутами оЗслукивания (п.1.1), в рассмотрены таюге системы с

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

Теорема 1.2. Если п=3, то задачи ^¡!л|п| |Рг»| з; и P|n|rji |Pr|£fiCa) язляются NP-трудныш.

Зшгелш, что исследование с.чсккооти задачи составления оптимальных расписаний обслуживания трех требований начато в работах Ю.Н. Сотскоза ('ОДЭ): им доказана NP-трудаость звдач обслуживания требований с фнссированыыми различными маршрутами: Jlm^lr.^lllt^a;, iPr-li^icJT, J!«=5|n=3|||Ettfa;, a

также НР-трудаость задач обслуживания требований с 'Ъшсированыыш оданоковыш ь-раруташ: Fjm|n-3|1 It^^is,), ?(яг|пьЗ| |it a£>l£l{*i3j.

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

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

Для определения числа требований, при котором задача с нефиксированными маршрутами №Р-трудна, из известного результата об KP-трудности задачи 0|m=3jn|| lî^^fa; при п=3 (T.Gonzalez, S.Sahni, 197о) нетрудно получить доказательство WP-труднооти задач 0|m|n=3| IJ^ajis.) и 0|m|n=3| | ll^fs4 при л=3, откуда следует КР-трудность' задачи оптимально о обслуживания трех требований в системе с нефиксированными маршрутами без прерываний при всех типичных для теории расписаний критериях оптимальности.

Для определения наибольшего числа требований, при котором задача о нефиксированными маршрутами полиномиально разрешима для произвольного регулярного критерия ?(в), использовать известные результаты о фиксированным числом приборов не удается. Такое число требований установлено в §2, где предлагается алгоритм трудоемкости 0(т) решения задач 0\т\п=2\\\?(з) с 0\т\п=2\\Pr\F(з). Значение п=2 является наибольшим значением числа обслуживаемых требований, при котором задачи с нефиксированными маршрутами без прерываний полиномиально разрешимы, поскольку, как отмечено выше, "задачи оптимального обслуживания трех требований в системах с нефиксированными маршрутами Nï-трудны.

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

поданокеств для задачи 0|п|л=2| | |?(aj равно восши, а для зодьчи 0|¡n|n=3| |Рг|Р(о.) - трем. Порядок проверки соотношений представлен в виде дерева, шокесгво висячих вершин которого и определяет разбиение множества всех :<чдпвидуалышх задач на подшокоства. Алгоритм ставит в соответствие навдой виоячой вернино дереза расгасшио, которое является оптимальным для всех индивидуальных задач расематрзшаеного подмножества. Таким образом, для каздого подмножества индивидуальных задач определено соответствующее оптималыюе расписание, и применение алгоритма для решения индивидуальной задачи состоит в определении, какому подмножеству принадлежит данная индивидуальная задачи.

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

В п. 3.1 доказана ÍJP-трудяость задач 0,,/|n|/i=2| | и

0,j\n\n=2\ | (EftC3> оптимального обслугзгознля двух требований в неоднородных системах без прерываний для простейших критериев оптимальности: Т^^Сз) л а в п. 3.2 для задачи

0,J\at\jv=2\ |Рг|УСз> с допустимыми прерываниями и произвольным рогуляряш критерием Р(а) предложен \алгорптм трудоемкости 0(п t- г). Напаяем, что задачи оптимального обог'ЕШзанпя двух гробевакий я однородных системах полиномиально разрешимы независимо от того, раэр пены прерывания шта цат.

'С ворона 3.1. Если п~2, то задача О,J|n|n| | з) я-*М8?еа ¿Ф-таудасЗ.

>гг,'Л лок'заатвльотоа teowm 3.1 построзно подавални»' 'со г4к»лс1г<в тпшосгзоа ОТ-подясй задачи о РАЗПШШ к соотвв-гствука^

" vw> porawtwaaww! (ч friamos существуй'? ли рашговдо tP Соя

прерываний обслуживания двух требований приборами множества Ы такое, что д u). для построенной индивидуальной - задачи

ТаЛи q

O.J|m|n=g| | If^yfi) показано, что оптимальное раошсаниэ а бпз прерчваний, при котором i^^fs0,) « у, сущеогвует тогда и только тогда, когда задача о РАЗБИЕНИИ имеет решение.

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

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

Итак, задача 0,J\m\n=2\|\?(з) оптимального обслуживания двух требований в неоднородных системах KP-трудна дане при наиболее просты критериях оптимальности: Р(а) = и PCs; = ЦЕ^а). Учитывая сводимость задач построения оптимальных расписаний при различных 'ритериях оптимальности, традациоьло рассматриваемых в теории расписаний, можно сделать вывод о том, что при любом из таких критериев задача 0,J\m\n=2\\\l(&) остается в классе КР-трудных.

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

Для задачи 0,J\m\n=2\\Pr\F(a) подучено необходимое в достаточное условие, при котором оба требования 1 и 2 обслуживаются без задержек в интервалах 10, t^l и fO,i2J соответственно (теорема 3.3). Напомним, что t^ s t^- суммарные длительности операций операций по обслуживанию требований 1 и 2 соответсвенно. В ходе доказательства достаточности сформулированного условия предложен алгоритм А построения искомого расписания. Этот алгоритм L-пользует алгорим трудоемкости 0(т) решения задачи 0\т\п=2\ |Pr|2Y3; оптимального обсл„живания двуг требований в однородной системе с нефиксированными маршруте?®, описанный в §2 диссертации. Общая трудоемкость алгоритма для "неоднородного" случая линейно зависит от числа операций по обслуживанию требований.. .Очевидно, расписание, при котором обр

требования 1 и 2 обслуживаются без • задержек в интервалах [О, + а [О,соответственно, является оптимальным при любом регулярном критерии Ж а).

Рассматриваемая задача 0,}\ш\ти=2\\Рг\Т(а) ис£У дована таккз я в случае, когда необходимое и достаточное условие отсутстг'-я задерезюк в обслуживании требования < п интервале (О, t1l или требования 2 в интервала ¡О, х^ но выполняется: качество расписания при втом определяется распределением задержек моаду требованиям;!. Заметим, что при выполнении необходимого и достаточного условия отсутствия задержек одно и то »9 расписание является оптимальнш при всех регулярны, критериях; если ж ото условие нэ выполнено, то для одних целевых функций оптимальны одни расшския, для других 7(з) - другие. Трудоемкость алгоритма В, предложенного для решения задачи в рассматриваемом случае, как и трудоемкость алгоритма Л, линейно зависит от числа операций по обслуживанию требований.

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

Во второа глава предлагаются алгоритмы рэшэшя э^дач оптимального "сслувшашия требований в шогосталпыых сист «ах, основанные на сетевой модели обслуживающей системы. В 5 1 приведено списание сетевой модели; в § 2 описаны эвристические алгоритмы решения задачи | \Р(з) большой размерюсти -

декомпозиционный (п.2.1) и адаптивный (п.2.2).

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И КЛЮЯ' 1." Установлена ИТ-трудность зада1-« »Т|й=3|п=3| | (^^Се.) оптимального обслуживания трех требований.' троил приборалм г: системах с фякенровйнншя различайся ыарарутькп обслукквыа:;:. (Поскольку известны пешивошалыше елгоразшь ромькл задача ) |г Го; шммадьвого оболушвашя п требований двуи;. приборам?, при условна г{с2, е такие аадечЕ !)?(в)

оптимального обслуживания двух требований и прибораш;, то иол;. -чешшй результат определяет точную границу меда? павагалгедй-ь':. разрешимыми и 1П>-чрудными задачекг с фженроа&шшж «ар.цруты}.

На основе этого результата доказана ну-грудаоеть слодуктг. задач оптимального обслуживания трех требовшай тро(И щебораж I системах о «¿иксировашыци различными маршруте обслуживания;

■7|т=э|п=3|

а также задач оптимального обслуживания трос требований V ■ системах с фиксированными одинаковы® маршруты® обслуживания * *

РМЛ^ЗПрг^ГЗН

УЧатквяя сбоизшоои. задач теогсэ с-

кгятергжш ст-Ецадьнеом!, из жхдуча^з: сз«:;*?

кг-трудность укьэаншн задач вря веах ~ друга* теории распасапий хркиагйза отзгй'ллтлоспг.

2. Разработан алторзш грудсегэсзк: т^гх;.::.;; -о|й|г-=з[ i ¡гсл; и о|я|я=*2| ш^лат-гл

расписанзя обояуаивавня дзуг тробозпгп! я птсгс^з,*^ и а

нефакелрованнши чэршруталя ща пдоггватгся рогухх Поеаольяу язвеоянп, что задача оатааг&гшого обсх/^гс^ч ълч требований з системах с н^экварсзаксгп трзрутл без прерываний яр-трудна вря яягйолзэ яроетах кстгоглл! стгс^глгкяз - ^йотСз; а Е^Гэ), ®о получений! разула;; уогсглпгслзг наибольшее зяпченае п=2, ярз »»5ор«1 задача 0(м|й(} (РО.) г^—Очг." всяяашаалшо разретгной (эе.ля епразэдггзз игпег-ззл Р Л!).

3. Исследована алоавовяь задач ся^^лгпйУо дэуз требований в неоднородннх евмегжг! дохао^г задач 0^1я|п=2|| (Т^Сз; а 0„ф.ф=211 ¡Ег.Гз; обслумшания двух требований без прзрпшагзй ¡¡¿л" сатшалькостн а Е^а), а гфэкгс-оз. аэгогзо трудоемкое та С^я + ревапяя задпчз | Р, > | а.) оптимальней обслукшашш дзуа тробозкзп} е - прорхагг-тя прз произвольном регулярно« критерии! ^з^.

4-. Дм решения' пр-трудных задач большой рпи:-:-г.тосг! оптЕыальЕого обсяугэЕавпя тргбо2£шЗ з ыкогоетадаЛянг езстеша предзойева еврасгетосиго хзйспсзаслйзпХ и адаптивный алгоритма» основанное сз сзютсЗ г.одолц обслуетвазщей оистзш.

Основное результаты дзссертоцзн олублпаезеза .а следушл работах

1. ¡Пахлевич Н.В., Сссежоз О.К. Пострс'пзэ сп^т^г^сго г.о быстродействии коыкгсгвого расгасеззя. - Проп^лг?/ ЬШ Л*

п

5ССР. - Низок, 1987. - N 13. - 2S о.

'¿. Еахлеш* H.B. Ол оцтЕ'альцсы по бштрсдэйс^зтг иа*шакть"ац расписании/' Применение рнфсрмышси и вхчкехятсхьноЯ теанша; пря решении народспо-хозяй^твенжсг задач: Тез. докл. респ. шыф. исходах учета я азецпслнсгов. - ьйгнек. I9S9- - С. 193.

3. Шглевет Н.?.., Сетонов D.H. Использование дёжсшознции для шш&газацик обгцего времени оЗслуышания тробозшй последовательней прмбораш// М&тоды решения экстремальных задач и гневные вопросы. - Минск: !Ш АН БССР, 1990. - С. 4-25.

4. Сот сков Ю.Н., Шахлевич Н.З. 2ГР-т?удкоеть задач оптимального обслуживания трех требований/У Известия АН КССР. Сер. $ыз.-мат. наук. - 1590. - N 4. - С. 96-101.

5. сотсксв В.Я., ШахленЕЧ К.В. Дцаятдыыа алгоритм минимизации общего Ерэммп обелухявепвл трех требований последоваяельааш rpii-icpabcr// Известен -'Л СССР. Техническая кибернетик. -1990. -Кб. ~ С. 137-142.

с. ShaJQilevioh ИЛ*., Stmsevioh Y.A. Scheduling two ¡lots In & &ulti-macMiie open aiop to ainiulze an arbitrary regular penalty Junction. - Report 9125/А/ Econometric Institute, BrasKua University. - Rotterdam, 1390. - 24p. .

7. Сот сков Ю.Н., Шахлевяч Н.Э. Задача оптимального сбслуашашш трах требований является NP-трудной// Проблемы теоретической кибернетики: Тез. докл. П Всесоюзной конференции. Волгоград, 1950. - Ч. I <3)- - С.40.

S. SVia&ilevIoh Н Л. f Strusevloh 7.A. Two tsaoMne open shop sotalullng pro'clera to nlninlse an arbitrary machine usage regular penalty fvmotlor.// J. Opl Еез. - 1992.

9. ШаждеЕИч H.B. Оптимальное обслуатаание двух требований . з неоднородных системах с прерываниями// Тез. докл. "VI конф. математиков Беларуси. - Гродно, 1932. - Ч. 4. - С. 105.

10. Шахлавач Н.В., Струеевич В.А. "Снтимзльное расписание обслуживания двух требований в системах с нефиксированными марЕфупзш// Еуриал вы-пгелгтелыюй математики и математической isisEKii. - 1992 (принято к опубликовании).