автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Сетевые модели и методы теории расписаний

Академия наук Украинской ССР Ордена Ленина Институт кибернетики имени В.И.Глушхова

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

СОТСКОВ Юрка Назарович

УЖ 519.8

СЕТЕВЫЕ модаи И МЕТОДЫ ТЕОРИИ РАСГШСАНИ

05-13.16 -применение вычислительной тегники, математит"окого моделирования и иатематлчееких методов в нау ала исследования!

Автореферат диссертации на оояока. ге ученой степени доктора физико-математических наук

Киев 1991

Работа выполнена в Ордена Трудового Красного знамени Института технической кибернетики АН БССР

Научный консультант: доктор физико-математических наук, профессор ТАНАЕВ B.C.

Официальные оппоненты: доктор физихо-матеыатнчэеюа наук, npoijeccop Е-ЕЛИЧЕВ В.Д., доктор физико-математических наук, профессор ЛЕОНТЬЕВ В.К., член-корресповден? АН УССР, доктор физкко-математкческих наук, профессор ШОР Н.З.

Ведущая организация: Институт математики СО АН СССР

Запита состоится " ft " 1991 г. в часов на

заседании специализированного совета Д016.45.01. при Институте кибернетики им. В.М.Глуыкова АН УССР по адресу: 252207, Киев 207, проспект Академика Глушкова, 40.

С диссертацией мокно ознакомиться в научно-технической архиве Института.

Г

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

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

скннветии в.®.

"'''"■GTlr 11 -'.л ^

iL зш:. :

. j| ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Отдал ^ \

.:c-1pT^i,'jlHjeHCm3H00 радвии1г оредотв вычислительной тохншси открывает широкие возможности применения математического моделирования и математических методов в научных исследованиях. Одно из ванных направлений прикладной ¡ц^тематикк связано о разработкой и исследованием моделей и методов календарного планирования и оперативного управления. Существенный вклад а исследование-математических вопросов оптимального упорядочения внесли советские ученые Бурков В.Н., Гшиадо Э.Х., Глебов Н.И., Емеличев В.А., Журавлев D.H., Куксв А.И., Леонтьев В.К., Михалевич B.C., Моисеев H.H., Подчасова Т.П., Поспелов Г.С., Сергиенко И.В., Супрунепко Д.А., Уздемир А.П., Танеев B.C., Шафранский В.В., Шкурба В.В. и др. Среди робот зарубекных математиков р области теории расписаний следует отметить работы Ашора С., Балаша 3., Беллмана Р., Блааевича Я., Брукнера П., Гври М., Грабовского D., Дгопоона Д., Двоисона 0., Лоу-лерэ Е., Ленстры Я., Набешыы И., Ринной Кана к. и Шварца В.

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

сокращению сроков га выработки, повышению оперативности и гибкости управления.

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

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

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

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

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

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

Научная новизна. Б диссертации предложены сетевые модели детерминированных систем обслуживания на основе взвешенных смешанных мультиграфов. Показано, что, за редким исключением, любая задача построения оптимального расписания (без прерываний операций в произвольные моменты времени) сводится к некоторой екстремальной задаче на смешанной мультиграф« С=(й,и,У), где множество вершин 0 представляет собой множество выполняемых опораций, множество дуг и и множество ребер V задают типичные для календарного планирования ограничения на порядок выполнения операций из множества возможности их одновременного выполнения, ограничения на длительность выполнения одной или нескольких операций и т.п. Здесь |и|«Ю|2, IV1 * ю 1012 и т - максимальное число различных типов приборов, используемых при выполнении одной операции.

Установлено, что если в ориентированном гр»Г« (0,11) содержатся контурн и все они отрицательного веса, то задача построения допустимого относительно О расписания является ИР-трудной в сильном смысле. Для остальных случаев разработаны полиномиальные алгоритмы построения допустимого расписания или распознавания ситуации, когда такс о расписания не существует. Показано, что со-ШЧзолноИ является задача распознавания условий, при которых любая орюнтация ребер смешанного графа 0 определяет допустимое относительно 0 расписание. Предложены сетевые модели и методы оптимизации процесса обслуживания требований в многостадийных системах при произвольной целевой функции,.!» 'Убывающей от моментов завершения обслуживания требований п числа используемых приборов каядого типа. При отом для выполнения отдельной операции монет требоваться не один, о несколько приборов одного и того же или различных типов.

Исследована слошость задач теории расписаний при фиксированной числе требований. Разработаны полиномиальные алгоритмы оптимального обслуживания двух ;ребований при произвольной регулярном критерии. Отметим, что в настоящее время не опубликовано результатов . о других полиномиально разрешимых задачах оптимального многостадийного обслуживания требований при произвольном регулярном критерии. Установлена КР-трудность задач оптимального обслуживания трех требований даже при сравнительно простых критериях оптимальности: Т^тах - минимизации общего времени обслуживания требований и Е Т, - минимизации суммарюго (среднего) времени обслуживания требований. Впервые доказана ПР-трудность задето построегая оптимального расписания при .фиксированном числе требования и

фиксированном числе приборов (не огршгачепо только число стадий по обслуживанию отдельного требозашш).

Показана принципиальная возможность использования результатов теории расписаний, полученных для дегерыинпровошшх сио-теы оЗ&куюшшшя, при исследовании систем сболу!зтшшя в условиях неопределенности. Для отого ввэдеш; и исследовали понятая устойчивости оптимального (с-олтшзльного) расписания к изменениям числовых параметров оСслуяааакцеЙ системы. Попучени соотношения для вычисления радиуса устойчивости оптимального расписания,. установлены необходимые и достаточные условия, щк выполнении которых радиус устойчивости ровен пула или бесконечности. Эти ц другие результат диссертации создает прэдпосилкк для созданш; единого ыатенатического аппарата исследования детерминированных и стохастических систем обслу-кквйшя.

Практическая ценность. Резработшпшо и диссертации оетеаые модели и метода решения задач составления оптхшальнш расписаний реализованы в виде прикладных программ, основная . часть которых включена в состав ППП РУПОР для решения задач оптимального упорядочения и в состав ППП МОРОЗ для решения опташзациошшх задач в проектирования и управлении.

В период о 1979 года по 1990 год указанные пакеты прогреми, о тькка отдельные системные и Функциональные иоду ли рэкешш so дач аеории расписаний и оптимального упорядочения на снованных (ыульти) графах внедрены ц переданы в эксплуатации в следуицие организации:

- Черноморский фчлиал Центрального научно-исследовательского институт "Центр" (г.Шн-.олаегО ,

- ? -

- Минекое произволетаенное обьданоние ям.В.И.Лонипа,

Научно-производственное объединение "ОРБИТА" (г.Днепропетровск),

- Опытно-конотрукторокое бюро Научно-производственного объединения "ГРАНАТ" (г.Мпнск),

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

- Ноучно-аеследоватгчьский и опытно-конструкторский институт черюй металлургии (г.Днепропетровск),

- Киевское высшее военное авиационно-шгаенерное учижщо,

- Всесоюзный научно-исследовательский и нонструктороко-техяологический институт трубной промышленности (г.Днэпро-петровск).

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

Апробация. Основные результаты работы докладывались на 1 Всесоюзном совещании по статистик© и дискретному анализу нечисловой информации, вкепертшч оценкам и дискретной оптимизации (Алма-Ата,1981 г.), на 6 и 7 Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Карвз~Яыэсеуу,1932 г.,1984г.), на 2 и 4 Всесоюзном совещании "Методы и программы решения оптюшэациошп» аадпч па графах и сетях" (Улан-Удв, 1992 г..Новосибирск,1999 г.), на 9 Межреспубликанской конференции "Совершенствование методов планирования и повышения с$фектиачостч общественного производства"

(Минск,1982 г.),на 4 Всесоюзном совещании по автоматизации проектирования елэктротехнических устройств (Таллинн, 1931 г.), на Всесоюзном совещашши "Моделирование и оптимизация проектных реиешШ в САПР" (Таллшш, Виру, 1983 г.), на Республиканском семинаре по дискретной оптимизации (Уагород, 1935 г.), па Мекдународной конференции "Искусствешшй интеллект. Методология, оиотеш, применения. J.XMSA 84" (Варна, 1934 г.), на Всесоюзной конференции "Проблемы теоретической кибернетики" (Горький, 1988 г.), на 4 Всесоюзном координационном совещании "Автоматизация проектно-конетруктореких работ в машиностроении" (Минск, 1988 г.),на Республиканской конференции "Применение информатики и вычислительной техники при решении народно-хозяйственных задач" (Минск, 1989 п.), на Всесоюзном семинаре "Вопросы оптимизации вычисления" (Алушта, 1987 г.), на семинаре "Дискретная оптимизация! методы и приложения" (Севастополь, 1984 г.), на 8 Региональной школе-семинаре "Поисковые метода оптимального проектирования и омеэтые вопросы"(Минск, 1989 г.), на сешшаре-еовещшши "Методы оптимизации в интегрированных информационных системах (САПР, АСУ, АСТПП, ИПС)" (Севастополь, 1989 г.), ка Всесоюзной школе-семинаре "Декомпозиция и координация в слокных системах" (Алуште, 1990 г.), на Межреспубликанской школе-семинаре "Дискретная оптимизация" (Алушта,1990), на Всесоюзной школа-оемшшре "Комбинаторная оптимизация г теория, алгоритмы и при-ненеше" (Батуми, 1990 г.), а такие на научных семинарах Института кибернетики Alt УССР (Киев) .Института математики СО АН СССР (Новосибирск),ВЦ АН СССР (Москва), Института математики АН БССР (Ц;шск) .Института "технической кибернетики АН БССР (Минск) и др.

Публикации. По результатам диссертации опубликовано более

60 научных работ, в том числе одна монография и шесть брошюр.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

В § г перечислены известные результаты относительно сложности задач теории расписаний для многостадийных сиитем обслуживания. Приведена таблица полиномиально разрешимых задач построения оптимальных расписаний и наилучше из известных автору асимптотические оценки трудоемкости соответствующих алгоритмов. Приведена таблица МР-трудны* и ЫР-трудных в сильном смысле задач теории расписаний, причем перечислены только "минимальные" ^-трудные задачи, т.е. задачи, специальные случаи которых являются полиномиально разрешимыми либо для ю;х еще не установлена принадлежность классу

КР-трудных задач. Приведена таблица наилучших характеристик известных, полиномиальных приближенных алгоритмов решения некоторых Щ>-трудаых задач теории расписаний. В таблица указаны асимптотические оценки сложности алгоритмов и оценки точности получаемых решений:. Для каждого из перечисленных в таблицах результата приведена ссылка на соответствущую публикацию, что позволяет рассматривать эти таблицы как часть обзора литературы.

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

Вторая глава диссертации посвящена вопросам сетевого представления сложных обслуживающих систем и разнообразных ситуаций, возникающих в реальных задачах календарного планирования. Характерные особенности многостадийных обслуживающих систем позволяют при поиска оптимальных расписаний их функционирования использовать специфические сетевые модели в виде смешанных графов, предложенные В.В.Шкурбой, Л.П.Матюпковым и В.С.Танаевш, или близкие по назначению модели в виде дизъюнктивных графов, предлошнныо Б.Руя и Б.Суссманом. Несмотря на значительное количество публикаций по вопросам использования 1 сетевых моделей и методов, следует'признать, что сетевые модели, которые ранее изучались, не позволяют учитывать многие типичные для реальных систем обслуживания условия и ограничения.

В § 1 второй главы предлагается использовать модели в

виде взвешенных смешанных мультиграфов. Пусть в многостадийной системе обслуживания требуется выполнить конечное множество операций 0 « {1,2,...,ч}. Для каждой операции известна

длительность > 0 ее выполнения. Прерывания при выполнении операций не допускаются, т.е. Тр^-И^, где ^ (соответственно - момент начала (окончания) операции I. Качество расписания характеризуется значением

заданной не убывающей по каждому из аргументов целевой функции 7(х) =» ?(х1,хг,...,г{1) при 1=774. Расписание о п г и-

м а л ь и о, если ему соответствует наименьшее значение этой функции.

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

предшествовать операции ¡, то должно выполняться неравенство Ду 2 Часто приходится принимать во внимание и временные затраты, связанные о переналадкой приборов, транспортировкой требований и т.п. Если при переходе от операции I к операции 3 вти затраты равны > 13 • то Дал*но выполняться неравенство А^г г^+г^Если разрешено частичное или полное совмещение во времени операций 1 и ¡, то должно выполняться неравенство А^ г где - заданное число, О « Ь Обобщением

этих ситуаций является условие

где а^ - заданное действительное (возможно, отрицательное)

число. Это условие можно записать в вндо 4Ц * (_Wl аЦ]'

Если задано несколько неравенств A^j г а^ для одних и тех so i и J, то достаточно оставить наиболее сильное из них. Поскольку я то неравенства Л^ а а^

и А^^ а а.д ссвместш тогда и только тогда, когда

ЧЗ + aji s

Если операции i , и J могут выполняться в любой последовательности одним и тем ке прибором, то даию выполняться либо неравенство t^ t^, либо неравенство Д^а tj. Коли при переходе от одной операции к другой требуется переналадка прибора, то должно выполняться одно из неравенств г 1Ш! AdiÄ В OÖ4eu случав требуется выполне-

ние хотя бы одного из неравенств

tj - tj а a1;j или tj - t^ а а.ц, (2)

где а^ и а^ - заданные действительные (возможно, отрицательные) числа. Это условие ыокно записать в виде Äj^ « (-öjiifii;})' Оно являотоя существенным, если a^f а^ >0.

Множество операций Q с заданными на нем бинарными отношениями указанных видов будем представлять взвешенным смешанным (мульти)графом G»(Q,Ii,V). Мультиграф 0 не оодераит петель, его подграф (Q,V) мокет содержать кратные ребра, в то время как подграф (Q.U) кратных дуг не содерыит.

Допустимое относительно 0 расписание

(t-j.ig.....lq) должно удовлетворять условиям (1) для всех дуг

(i,j) сии условиям (2) для всех ребер (i,J]k« V (индеко к отражает возмокное наличие в 0 кратных ребер).

г* ,

Обозначим через Р(С) множество всех ориентированных

графов, порождаемых смешанным мультиграфом 0 в результата замены каждого ребра flj]51« V дугой с весом ила

дугой (í.i)^ с весом вд и последующего удаления всвж. кратных дуг за исключением дуг наибольшего веса для каждого набора дуг вида (1,3). При поиске оптимального расписания достаточно ограничиться рассмотрением конечного множества так ввзивавюзх активных расписаний. Показано, что существует взаимно однозначное соответствие между множеством всех активных расписаний, допустимых относительно мультиграфа 0, а

Л л»

множеством P(G) Bcei графов из множества P(G), которые не содержат контуров положительного веса. Через Н обозначим мпонество всех контуров ориентированного графа (Q.O), а через Н' - wrosecTBO ncez его контуров положительного веса, Н1 с П. Доказаны следующие утверждения.

Теореме 1.3. Для существования расписания, допустимого относительно смешанного мультиграфа G, необюдамо, чтобы H'*e я достаточно, чтобы Н=а.

Теорема 1.4. Если В*» в и Н * в, то задача проверка существования допустимого относительно смешанного графа О расписания является ГГР-полной в сильном смысле даже в том случае, когда все веса положительны за исключением одного,

приписанного некоторой дуге смешанного графа 0.

»

Теорема 1.5. Ноли Н =а, то задача проверки равенства P(G)=P(G) является оо-КР-полной.

Для случаев, отличник от указанного в теореме 1.4., предложены полиномиальные алгоритмы построения допустимого относительно мультиграфа 0 расписания. Трудоемкость этих алгоритмов изменяется от 0Í1) до 0(г( в зависимости от

ceoêcte мультиграфа С. Аналогично для всех случаев, отличных от

утаенного в теореме 1.5, предложены алгоритмы сложности от 0(1)

до 0(q3) для проверки равенства F(G)=P(G). При выполнении втого

равенства мощность множество активных расписаний достигает

своего максимального значения 2'^'.

§ 2 второй главы поовящен моделированию обслуживающих

систем с последовательными и параллельными приборами. Пусть

множество Ж = {1,2,...,10 обслуживающих приборов разбито иа к

попарно непересекающихся непустых подмасжестэ ЛЦ.Ж^,...,.^,

m _ _

* = 3 , ^ л " .1=1,El, le * 1.

k=1

Кагдое множество ^ состоит из параллельных, одинаковых приборов типа к.

Шохеотво Q заданных операций тагага разбито иа m попарно непересекающихся непустых подопожаста:

о __ __

Q s U Q,„ С^аз, Qj. п Q, ■» о, 1с=Т7и. 1=V3, k * 1.

kai u B-

Для выполнения непрерываемой операции icQ может бить использован любой из приборов цногзства

Известны длительности операций, пуско-наладочных, переналадочных ц транспортных работ. На множестве Q задано отно-шочес строгого порядка, указаны условия совмещения процессов выполнения операций к т.п. Вое бtu условия и ограничения представлены г ввде обобщенной временной модели (Q,U).

Зодане деловая функция Ф(х,у)=Ф(х1,х2,...,х(1>у1,у2>...уя)1 не убывающая но кахдому из аргументов. В задаче (которув в дальнейшем будем называть задачей А) тробуотся

-- определять число гг, г^ а к=Т7й, прабороз адо-

кеотве используемых в процессе выполнения операций Q,r; - распределять операции шюгоства Q,, по втиы приборш;

- построить расписание выполнения множества операций Q. Указанные действия необходимо выполнить так, чтобы значение целевой ФУНКЦИИ Ф(Х,У) бЫЛО МШШМаЛЬНЫМ При Xjsfj, i * QR,

и Ук=гк, к=775.

Для моделирования такой обслуживающей систеш предложено использовать взвешенный смешанный мультиграф C=(Q,U,V), где (Q.U) - обобщенная временная модель, а ребро [i.Jl « V тогда и только тогда, когда операции 1 и J принадлежат одному я тону же множеству Q^, k=*1,m. "-¡ли операции i и J из множества Q^ казна эли на один и тот же прибор из множества то в зависимости от порядка ш выполнения должно иметь место одно из соотт ношений (2). Если жэ операции Inj принадлежат множеству Q^ я поэначеяы на разные приборы из множества то не требуется выполнения соотношений (2). В первом случае ребро [1. 31 заменяется дугой (i, J) веса а^ ила дутой (J, I) веса вд соответственно. Во втором случае это ребро удаляется. Выбирая последова-вательно ребра смешанного графа С в применяя к каждому из них одно иэ трех указанных требований, получаем последовательность

h, 1ъ> h,

,a2 c,...,«|7jV) преобразований G. Здесь в^ означает,

какое именно ребро [lj] выбрано из множества V на 1-ом шаге и какое иэ преобразований Ц к нему применено. Ориентированный граф, полученный из О в результате последовательности преобразований л и последующего удаления всех кратных дуг, за исключением дуг наибольшего веса, обозначим 0 [в ] ■ (Q, U [а )). Доказана ,следующая .

Т е о рем а 2.^Преобразования а являются допустимыми для смешанного графа Г, (т.е. определяют некоторое расписание)

тогда и только тогда, когда ориентированный граф 0 [« ] обладает следующими свойствами:

1) граф 0 [а ] не содержит контуров положительного веса}

2) для каздого к=Т7га число ] слабых компонент связности нороаденного подграфа (О^.и^Еа )) графа (а,и 1«]\и) на превосходит 5

3) квадая слабая компонента связности графа (С^.и^а]), к=Т7й, является турнире^.

Для решения задача А достаточно: построить все смешанные графы 0^1 0^} ооответетеущие различию! наборам чи-

сел г^ к=Т7ш, используемых приборов и различным распре-

делениям операций по приборам} построить множество ориентированных графов Р(О^) для каждого смешанного графа у « 1Д; и выбрать из множества й(С) я граф (0,11'), которому соответствует наименьшее значение целевой функции.

Следующие утверадения получены непосредственно ш теоремы 2.1.

Следствие 2.1. Существует взаимно однозначное оо-

А

ответствие мокду множеством ЩС) а ынокеогвоы активных раопв-сашй задачи А.

Следствие 2.2. Задача А эквивалентна задаче поио-кв оргынтгтюванного графа С[а ] е Н(0), для которого значение

целевой функции €>(Т1(0[а*3>.....Тч(С{а*]), г^а*],...,^!«*!)

шшшалыю среда значений Ф(С[« ]) в Ф{Т1<с[а]),...Д (С.{«1), г1[а].....гт(*1) ЯДа всех а(<х1 « й(0).

Получены необходаше и достаточные условия, при выполне-

г................. ...... " " И/ Ь, . Ь, "

ни которюс частичная;последовательность (/•« (ы,, ее/),

1<|У|, может быть достроена до полной допустимой последовательности а = (а1,а ^ .....<»|у| ). Эти результаты испольэуются в диссертации при реализации .схем последовательного анализа вариантов.

3 § 3 предложенные сетевые модели и методы обобщаются на случай, когда для выполнения отдельной операции требуется не один, а несколько приборов одновременно. Иными словами, речь идет о задачах оптимального распределения ограниченных ресурсов. Наиболее полно-- излояенио результатов по решению та ух задач содержится в монографии В.С.Михалевича и А.И.Куксы "Методы последовательной оптимизации (в дискретных сетевых задачах оптимального распределения ресурсов)" - и.: Наука, 1983. - 217 с.

В диссертации предлагается новый подход к решению таких задач, основанный на моделях обслуживании* систем в виде смешенных мультиграфсв 0°=(0.и,?°). Кратность ребра, инцидентного вершинам (операциям) 1 и равна числу типов приборов, каядый из которых требуется для выполнения как операции 1, так и операции В частности, если Ю^^! «1, к*1, к=1,гг, 1=1 то краткость каждого ребра графа С0 не превосходит единицы.

Получены аналоги теоремы 2.1, следствия 2.1, следствия 2.2 и других утверждений $ 2 для случая, когда выполняемо одну операцию приборы долашы быть попарно различных типов, и для более сложного случая, когда для выполнения отдельной операции мояет требоваться несколько приборов множества Л, типы которых необязательно попарно различны.

В § 4 второй главы получены соотношения для подсчета активных расписаний оОслукич^чич требпяаний в системах о

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

Теорема 4.1. Если приборы мкокасгва к-1,и,

попарю различны и множество операций Q неупорядочено, то

ш

число активных расписаний вштолнешя операций Q = U Q, приборами

ш k=1 к

45 с- и А, равно к=1 к

m Iii,

" «У' ? fë'J [M-

Теорема 4.2. Если приборы одинаковы, k=T7m, и

ыноаеотво операций Q неупорядочено, то число активных

m га рашисешй выполнения операций Q = U Qlr щибораш U ¡L, разно

k=1 k к=1 к

m l&J "PIQk-l .xv ч y.

П (IQtJ! «

k=1 k rk=1 1=1 K >•

Величина , „ в теореме 4.2 обозначает количество iukl ,rk

различных представлений числа IQ^I в виде сушы г^.

1 г*

неупорядоченных слагаемых, в величина а^' к равна

1_ , где гц - количество попарно различных

tfttît; 7Г.

i1 ! i2 I

к

слагаешг в соответствующая нрэдотавлении IQ^I и - число мнсмостс попарно одинаковы!, слагаеииг в етш представлении lQjj.1. Иоотому того, чтобы воспользоваться теоремой 4.2 достаточно перечислить неупорядоченные гу- разбиения числа (Су для всег r^a'1, I^l • Получены такге более простые соотношения для оценки мощюоти множества активных расписаний.

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

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

л

алгоритм имеет трудоемкость 0(r log2r), где г - максимальное число стадий по обслуживанию одного требования. Если прерывания операций допускаются, то оценка трудоемкости

о

предложенного алгоритма - 0(г ). Если каждое требование обслуживается каждым прибором точно один раз, (например, в задачах поточного типа), то оценки сложности алгоритмов уменьшаются до 0(Н 1очгМ) и 0(1! ) соответственно. Показано, что полиномиально разрешимы и задачи оптимального обслуживания двух требований, которые поступают в систему неодновременно, а также задачи оптимального выполнения частично упорядоченного множества опепаций Q по обслуживанию двух требований.

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

§ 2 посвящен исследовании сложности задач оптимального обслуживания множества требований N=(1,2....,п> фиксированной мощности п в системе с последовательными приборами 1,2,...,М}. Для каждого требования i«N задан м а р и р у т обслуживания I1®!!.*, L*,..-.L^,), íi=TTz\¡\ Отметим,

что по существу все известные результаты относительно сложности задач теории расписаний были связаны о фиксированным числом приборов V и предполагалось, что n>lí. Вопросы слокнооти

задач теории расписаний о фиксированными маршрутами Ь^ДсЛ, при Мзд оставались открытыми. В диссертации доказаны следующие утверждения.

Теорема 2.1. Если №3 и ¥=5, то задача построения оптимального по быстродействию расписания обслуживания а требований К приборами без прерываний операций является КР-трудноЙ.

Теорема 2.2. Если п=3 и 8£=5, то задача построения оптимального по быстродействию расписания обслуживания п требований М приборами с прерываниями операций является КР-трудной.

Теорема 2.3. Если допускаются нулевые длительности операций, то задача построения оптимального по быстродействию расписания обслуживания трах требований о одинаковыми маршрутами обслуживания является ЫР-трудной.

Теорема 2.4. Если М=Э, то задача построения оптимального по быстродействию расписания обслуживания п линейно упорядоченных требований в системе с нефиксированными маршрутами является ЫР-трудной.

Аналогичные теоремам 2.1-2.3 утверждения доказаны и для

задачи минимизации суммарного Т I, (и среднего 1/п Г Т.)

1сН 1 1сМ 1

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

в теории расписаний символическим обозначением различных задач; П1 /Пд /П-, /Пд /П^ /П6, где признак П. означает тип об-олуаивапцей оиотемы (Р - маршруты обслукнвания требований одинаковы, «5 - маршруты различны, О - ыараруты не фиксированы), П2 - число оболуинващих приборов, П^ - ограничения на длительность ^^ выполнения операций, П^ - условия обслуживания требований ( Рр- прорывания операций допускаются, С=С - мнокэство требований линейно упорядочено), П^ -число обслуживаемых требо-

ваннв, П^ - вад целевой функции. В диссертации установлена Ю>~ трудность оледущих задач теории расписаний: г / и / / рг / п=э / I т1, ? / м / / / П=з / Е ? / и / > о / / п»з / Е з / ъ / ^ > о / Рг / п=з / £ 11. л / 5 / > о / / п=з / Е о / з / г1ь / о=о / / е ^.

Таким образом, задачи оптимального обслуживания двух требование полиномиально разрешимы при любой регулярном критерии { ф 1 ), а задачи оптимального обслуживания трех требований ЛР-тргдни даже при сравнительно простых критериях оптимальности Ттах и Е Т1 ( § 2 ). Отметим, что перечнслешше задачи не являются МР-трудаыми в сильном сшсло, поскольку при фиксированном числе требований можно предложить псевдополиномиалыше алгоритмы построения оптимальных расписаний относительно критерия к £ Т^.

В § ? исследована сложность задачи оптимального обслуживания частично упорядоченного множества требований о одинаковыми длительностями операций. Пусть на множестве требований N задано отношение -»• строгого «порядка: еоли 1сН, 1*3, то при любой допустимом расписании завершение обслуживания требования 1 долзкно предяэствоаать началу обслуживания требования Справедлива следующая

Теорема 3.1. Еоли Ы=2, 11е{( 1), (2)>, для всех 1еН н какдая компонента связности графа редукции отноиешг-является цепью, то задача построения оптимального по быстродействии расписания является НР-трудяоЙ в сильном смысле.

Показано, что задача построения оптимального по

быстродействию расписания обслуживашм требований 1с11, поступающих в систему з моменты ¿^>0, сводится к задаче построения расписания с наименьшим значением максимального

т

временного смещения при 4^=0, 1еН. Справедливо и обратное утверждение.

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

В § 5 разработаны алгоритмы последовательного анализа вариантов для решения описанных в § 2 и § 3 второй глава задач оптимального выбора необходимого количества приборов (ресурсов), оптимального р-".стт1 .деления заданного множеств я операций гга вы-

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

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

В § 1 введены определения области, ыара и радиуса устойчивости оптимального расписания* При етш существенно используется сетевое представление обслугзгвакцей системы в виде взвешенного сыоеояного (нультн)графа О = (Q,U,V). Если оптимальное paermca-1ше ...,t ) определяется ориентированным графом

Ga g P(G) = { Gr Г.2.....Gx ), то граф 03 будем

называть оптимальны и. Пусть t я (t ,,t2,.., ,tq) -вектор длительностей операций множества Q. Через (¡¿} обозначим мнокеетво верппш, через которые проходит путь Ц в графе Ga«P(G), а через - вес пути (I. Путь ¡I будем называть

д о м п н я р у ю я и ы, осла в GQ не существует пути i', для которого (JJÍsfy). Обозначим через p(t) ынсикветво всех номеров в оптшелышх графов G„. Пусть Н'и Hfl- rácssoraa всех дошширую-П51Х путей Грефов (а,0) и GB соответственно. R4- множество неотрицательных действительных q-мершх векторов о чебкиевской метрикой. Замкнутый ¡rap Ор( t) радиуса р а центром а векторе t будем называть паром устойчивости 0g, ac?( t), если для лг1сго вектора te O^t^R^ номер в принадлежит f(t'). Наибольшее значение р шара устойчивости CL(t) будем называть

радиусом устойчивости 0„и обозначать через

ц 8

pö(t). Пусть 0 и (t^.t^,....tjj^) - неубывамцая последовательность длительностей операций множества {р} \ {fi} , ы„д® = Id1} \ (|1}|. Доказаны следущие утверждения.

Теорема 1.1. Для того чтобы PB(t) = », необходимо и достаточно, чтобы для любого пути ц « Hg\ H и любого графа Ск€Р(о) существовал путь У е К^ такой, что {fj> s О»).

Теорема 1.2. Если в с f(t), то pB(t)s min max min max___ 1 (У) -1 (p)~E t vu

Теорема 1.3. Для того чтобы выполнялось неравенство pe(t)>0, в с ?(t), t с Rq, необходимо и доогаточно, чтобы для любого пути дсНд \ Н' в любого к с p(t) существовал путь такой, что (ц)е(и).

Аналогичные результаты получены для обслухашавдих систем с последовательными я параллельными приборами. Исследованы свойства всей области устойчивости ß0 оптимального графа Gß.

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

Теорема 1.4. Для того чтобы p(t) = » , необходимо и достаточно, чтобы t е » { t | ç (t) = { 1,2, X ] }.

Показано, что вычисление p(t) сводится к решению нелинейной задачи математического программирования:

max jxj - t1| ----> min,

1-TTq

mill пах Iх (Ц) a mill max l1 (i>),

B'TJ fleH3 kef(t) Vell^

* 0, l=TTq .

Еслп p(t) = fs}, то непосредственно из определений следует соотношение p(t) s pB(t), прячем если pß(t) < <o, то p(t) ■» . pa(t). Такны образом, из теоремы 1.2 получаем

Следствие 1*. Если p(t) » (в) и p(t) < », тэ р (t)= min пах min max _ _ 1 (1>) t vu

§ 2 посвящай ясследовашш устойчивости оптимальных расписаний при произвольном регулярном критерии. Показано, что вычисление радиуса устойчивости сводится к решению нелинейной задачи матеыатепеского программирования. При критерия оптимальности £ Т^ вычисление pg(t) сводится к решении конечного числа задач линейного программирования. ,

Показы ¡о I что предложенный подход к исследованию устойчивости оптимального графа исто, лерянестя на более слокные задачи теории расписаний. В частн^тк, кроме вектора t олучайшш мосе? быть вектор а дештельноотей переналадок приборов и транспортировок требований. Следующее обобщение подученных результатов связано о предпояокешем о тем, что изменяться могут только некоторые компоненты вектора t а вектора а (остальные компоненты предполагаются стабильны"«). Для кавдого переменного числового параметра обслуаявапцей системы иойвт быть указан диапазон возможных изменений.

В § J исследуется устойчивость приближенных расписаний к

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

Более детально исследована устойчивость приближенных решений следующей дискретной вкстреиальной задачи. Пусть V -множество натуральных чисел {1,2,...,*}, а К*7 - множество всех

(0,1 )-вехторов у « (У1,Уг.....Уи). Требуется при заданной

векторе 1; с й" и заданном непустой множестве УсУ" найти вектор

уМу^.Уг.....у£> € У. дяя которого

га.уЬ - Е Чу} = юш с?и,у) I у«*}. (з)

Будем называть вектор у ревенном этой задача в предполагать, что множество У допустимых векторов не зависит о* вектора

Множество б(у,е) векторов пра которых вектор уеУ является с-приближенным решением, т.е. выполняется соотношение

У(4,у) * (1+с) Г (t.yt). (4)

представляет собой область устойчивости е-приближенного решения у. Показано, что множество О(у.е) является выпуклым, замкнутым конусом с вершиной в точке ОсВ* л выполняются равенства г^О(у.е) = {ин"|¥(г,у) * (1+£)Р(^уЪ, у«У) к Д 0(у,£)=0*.

Замкнутый аар О^Ц) радиуса р с центром в точке * <е 0(у,г), Е40, будем называть шаром устойчивости с-приближенного решения уеУ. если Ор(1)лй"с0(у,е). Наибольшее значение р шара устойчивости О^Ш назовем радиусом р (уЛ) устойчивости £-приближенного решения у. Пусть на множестве У задано отношение а нестрогого

порядка такое, что у а у' тогда и только тогда, когда для всех из условия у1=1 следует равенство у|=1. Доказаны следующие утверждения.

Творено 3.1. Для того чтобы р£(у,1;)в0,необходимо и достаточно, чтобы условие (4) выполнялось как равенство и

существовало решение у* задачи (3), для которого отношение г

у а у по наполняется.

Теорема 3-2. Для того чтобы р£(у,1;)=«, необходимо

и достаточно, чтобц для любого вектора у'« у выполнялось

условие 7 а у'.

Отиетам, что в терминах задачи (3) мокло сфорыулирозать

достаточно широкий класс дискретных экстремальных задач, в

частности, линейные траекторпца задачи; о кошпвоязере , о

назначениях (У=УЦ), о кратчайшей связывавдей сети и другие.

В диссертация доказано утверждение, которое позволяет

уточнить теорему 3.1 и теорему 3-2 для эедач о назначениях и о

комшшсякера следуизнм образом.

Следствие 3.1. Пусть Ус СУН, Ук>, тогда для того,

чтобы Ре(у0,1)=0, необходимо и достаточно, чтобы условие (4)

t

выполнялось как равенство и существовало £ решение у задачи (3), отличное от у.

Следотвне 3.2. Если У с {Ун, Ук>, то р£(у, t) < о». В § 4 рекрабставный математический аппарат предлагается использовать для синтеза систем обслуживания в условиях неопределенности. Исследованы свойства областей устойчивости сптЕмашшх графов для сложных систем обслуживания, Установлено существование конечного покрытил мнозества И1* областями устойчивости , п-1 Д. Доказан? следующая

Теорема 4.1. Для того, чтобы радиус p^(t,a) устойчивости с-оптимального графа 0. равнялся пулю, необходимо,

о

чтобы соотношение

*(ï,(a). 1г(в).....ïg(a)) s (1+е) F (Т^а*), ï2(a*),...,ïg(a*))

выполнялось как равенство.

Разработаны мэтоды синтеза статических стохастических систем обслуживания и более слокша динамических стохастических систем обслуживания.

Пятая глава посвящена практически задачам оперативно-калецдарного планирования (ОКП), для реоения которых использовались првдаокенгше в диссертации модели в методы.

В § 1 списана система ОКП работы гибкого автоматизированного участка механообработки (ГАУ). Участок включает две группы параллельных станков (обрабатывавши центров), на которых необходимо обработать заданное множество II деталей о учетом времени in транспортировки и времени переналадки отаяков. В качестве целевой функции используется

Fis) » ij^i 2j(b) +■ ш T., (а), где 2j(s) - заданная функция итрафа за нарушение директивного срока обработки детали jcNs

ejC^ÎBÎ-Dj), если ïj(e)>Dj, О, если ïj(e)sDj.

Здесь «j>0 означаот приоритет детали JcH, который задается с учетом важности ее для всего технологического, процесса, о учетом связей между цехами и участками и т.п.

Наряду с задачей построении оптимального расписания а обработки догалеЯ па ГАУ особо важной s практическом отношении оказалась задача корректировка расписания s в олучье

hl8)

поотуп"9кня на участок инокаства N1 новых (вноплвновиж) деталей. При втсм требовалось построить таксе расписание s* обработки как новых деталей H1, так и "старых" (но еще не поступивших на обработку) доталей NQ <с N, чтобы отклонение моментов начала и окончания обработки деталей множества MQ при распасашш в' от соответствующих моментов при р^писанш в было "по возмошюсти минимальны/', иными словами, необходимо обеспечить устойчивость практической реализации расписания. Не-ооб. ,детге втого требовшшя на практика приводит к дополштель-ным издерткам при согласовании планов работы ГАУ и других цехов, участков и елукб.

В § 2 описано использование предлояешшх сетевых методов для сменно-суточного планирования работы "заводского" вычислительного центра, в котором выполняются, в основном, регламентные вычислительные работы о известными на эуапе планирования характеристиками. При сравнительно небольшой размерности задач расписания выполнения заданий на ЭВМ отроились непосредственно с помощью программ составления расписаний, допустимых относительно заданных смешанных мультиграфов. Для решения задач большой размерности предварительно использовались методы декомпозиции.

В § 3 пркводоно краткое описание интерактивного пакета прикладных программ РУПОР для решения широкого класса задач теории расписаний. Функциональные подул« отого пакета, предназначенные для составления расписаний работы многостадийных систем оболуиивакия, реализуют прбдлскешша в диссертации алгоритмы. Управляющая часть ППП РУПОР основана иа системе коллективного доступп ЕЕ07920. Списаны широкие возможности ППП РУПОР

ло созданию программных средств для ОКП. ППП РУПОР включен в состав Мотодоориентировпнного ППП МОРОЗ для решения оптимизационных задач в проектировании и управлешш. ППП МОРОЗ разрабатывался совместно специалистами НТК АН БССР, ИМ АН БССР, ИК АН УССР, Ш и К Лит. ССР и НТК? Болгарской Академии наук.

Одно из наиболее перспективных направлений разработки программных средств решения задач ОКП связано с автоматизацией процесса адаптации еврмстических алгоритмов к реальпым условиям функционирования обслухиващих систем. В § 4 перечислены основные принципы, которые наши применение при разработке адаптивных алгоритмов и программ на основе предложенных в главе 2 сетевых моделей. Адаптивные алгоритмы и программы включают три основных этапа: настройку, обучение в вкзамен. На етале настройки задается список евристических правил разрешения когфгактов и определяется некоторые параметра вычислительного процесса. На етале адаптации в результате решения так называемых "обучащих" примеров (как праьлло, небольшой размерности) происходит накопление информации о рассматриваемом классе задач ОКИ в виде стандартной таблицы обучения. При атом существенно используется математический аппарат теории распознавания образов. Основной вопрос на етале разрешения конфликтной ситуации состоит ь распознавании класса, которому принадлекит данный о б ь е к т. Под объектом здесь подраиумогаетоя конфликтное реСро [1, Л, рассматриваемое на очередной итерации алгоритма, л по^ классом - множество преобразований етого ребра, которые могут привести к оптимальному графу.

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

информативные признаю! конфликтных ребер, конфликтные ребра разбиваются на класси и прл необходимости производится "скатиз;1 полученной информации. Ключевым моментом при решении адшггизнш алгоритмом задачи ОКП, возможно, большой размерности (т.е. на этапе экзамена ) является распознавание класса, к которому принадлежит очередной объект. Н" втоы етапе могею использовать различные методы теории распознавания образов, в том числе алгоритмы распознавания, основанные на вычислена . оценок. Сущность последних состоит в вычислении оценок сходства набора значений признаков распознаваемого объекта и наборов знвчетй признаков эталонных объектов, полученных на этапе обучения и принадлежность которых заданным классом известна. На основании анализа оценок сходства принимается решение об отнесении объекта [1, Я к одному из классов и соответственно принимается Р(. ;ение о выбора ориентации (1, 3) или (3, 1) етого ребра (если в обслузшвавдей системе имеются параллельные приборы, то помимо ориентации ребра предусматривается возможность удаления его).

Несмотря на то, что мощность множеств 7 к и растет полиномиально с ростом п, тем нэ менее^'при ренэнии задач большой размерности для хранения ребер 'смешанного гграфа О может потребоваться память большого * об^-ямя. Поетсму в разработанных адаптивных программах множество ребер V не используется в кечэотве исходных данных, вти ребра строятся последовательно по мере реализации алгоритма. В заключении § 4 описан метод декомпозиции задачи построения отдельного pacпIfcaния. допустимого относительно 0. на ряд задач с ограниченным числом ребер. Приведены результаты вычислительных

вкспериментов по оценке трудоемкости разработанных в диссертации программ. Проведенные эксперименты с различными задачами теории расписаний, в том числе о широко известными тестовыми задачами при п = II = б, п = М = 10 и п = 20, Ы = 5. показали высокую эффективность разработанных программ.

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

ЗАКЛЮЧЕНИЕ

Вое главк, кроме первой, завершаются параграфом "Основные результаты и публикации", в котором дано краткое описание полученных результатов, указано, где они опубликованы, и сформулированы некоторые выводы. В частности, в последнем параграфе третьей главы подсчитано, для какого количества "открытых задач" теории расписаний получен ответ относительно их статуса, е именно: для 1003 задач теории расписаний в диссертации предложены полиномиальные алгог'.тмы решения и для 864 задач установлена принадлекность к классу ОТ-трудных. Таким образом, суммарное число задач теории расписаний, для которых в диссертации установлен статус (относительно КР-трудности), равно 1872, что составляет 19,796 от общего числа 9504 задач, рассматриваемых в современной теории расписаний.

В табл.1 перечислены "минимальные задачи", Ш'-трудность которых установлена в диссертации, о в табл.? - "максимальные задачи", для которых: в дисеергшш! предложены полиномиальные алгоритмы решения.

Таблица 1

Щ/ n2 / n3 / rr4 / "5 / "6 Оценка сложности Раздел диссертации

P / U / tlh / / n=2 / P(ß) 0(Mlog2M) Гл.3,п.1.13

P / !i / tih / Vr / n=2 / P(s) 0( M2) Гл.3.п.1.13

J / m / tlh / / 11=2 / P(o) 0(r2log2r) Гл.З.П.1.8-12

J / If /tlh,dj/ G / n-2 / F (a) 0(r2log2p) Гл.3»п.1.14

J / - / tlh / Pr / n=2 / F(e) 0( r3) Гл.3,л.1.3-6

J / lí /t^.^/ír.G / V 2 / ?(a) 0( r3) Гл.3.п.1.14

J / h / tlh / / n=2prJs!í / P(a) o(uioe0u) Гл.З.п.1.13

J /Ы/ tlh / РГ / n=2,iy:M / Píe) o( и2) Гл.3,п.1.13

J / ы /t^.a^ G / / P(a) 0( li2) Гл.З.п.1.14

J / !í Ajj^/PF.G f n=2,i'1£H / P(a) 0( u2) Гл.3,П.1.14

J.O/ U / tlh / G / U-a, / a(G) 0(1) Гл.2,п.1.9

J,0/ и / tlh / 0 / U=e, / s(G) 0(q+m ) Гл.2.п.1.9

J.O/ U / tlh / G / -a / (G) 0(q2) • Гл.2,п.1.4

J,0/If / tlh / G П1*в,V=a,W*a,H=a/8(G) 0(q+|U¡) Гл.2,п.1.4

J,О/ ü / tJh / G /U*a,.-e,î7^a,H»!0/a(G) 0(q3) ГЛ.2.П.1.7

J,О/ Ii / tlh / G / U*£>,V#e,W=a / b(G) OfqflUMV!) Гл.2,п. 1.4

J,О/ U / tlh / G /UwoJw.lîw.U'M/siS) 0(q3) Гл.г,п.1.10

J,О/ Ii /tlh / G 0(qf|И|+|7| ) Гл.2,п.1.10

J,О/ !! 1 tih / G / / P(G)=P(G) О^2) Гл.2,л. 1.13

J,0/ M / t^ / G / / P(G)=P(G) 0(q3) Гл.2,П.1.13

J,0/ Ц / tth / G / P(C)=P(G) Otq") ГЛ.2.П.1.13

J.O/ ti / tlh / G/U^a.^a.^a.Vi^a/TiOsPlG) 0(1) ГЛ.2.1Т.1.1Э

J.O/M / ,lh / G /P(G)=P(G) 0(q3) ГЛ.2.П.1.13

Таблица 2

П1/П2 / П3 / n4 / % / П6 Раздел диссертации

¥ / U / r>-3 / \ax Гл.3,п.2.4

F / И Pr / n=3 / T tsax Гл.З,По2.5

У / Н Pr / / т ШХ Гл.З.п.2.5

Р / И ' W / »1=3 / Гл.3,п.2.а

Í / н ' W Pr / n=3 / ETi Гл.3.п.2.8

У / Ы /tlh>0/ Pr / n=3 / ETt Гл.3,п.2.8

J / 5 /ttt>0/ / 11=3 / T ШХ Гл.3,п.2.1

J / 5 /^>0/ Pr / 11=3 / T wz Гл.3,п.2.2

J / 5 'W / 11=3 / ^ЕШХ Гл.3,п.2.1

J / 5 Pr / n»3 / ^¡aax Гл.3,п.2.2

J / 5 /t^o / / n=3 / Гл.3.п.2.8

J / 5 /tlh>0/ Pr / n=3 / E^i Гл.З.П.2.8

J / 5 'W / n=3 / Гл.З.п.2.7

J / 2 /tlh=1/ 0=0,4... uop / b^muBH / í Ш1 Гл.3,П.3.1

J / 2 /1^1/ C=0^J...U0p / LMUUB)} / f mox Гл.З.П.З.З

0 / э 'W G=0 / / *юах Гл.3,П.2.6

о/э ' 4h ' G=0 / / E ^ i Гл.3,п.2.8

J.0/ м ' tih/ G /UtóJ«, |W|= =a/ 8(G) ГЛ.2.п.1.10

J.0/ и / tlh / О Гл.2.п. 1.11

Помимо введенных ранее обозначений в таблицах используются;

символ Р(а) для обозначения произвольного заданного регулярного критерия оптимальности;

символ в(С), если в задаче трнбуетг-л пос-троят?.

допусдашоо относительно заданного смешенного мультиграфа С к

= (о.ид);

запись Р(С)-Р(0)„ если в задача требуется проверить

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

-

Кроме того, впппеь О ~ С^У», .1*0^ (соответственно 0 = С1и.. .ио ) указывает. яа чо, что яа шнжзства ярзЗевашй (операций) задано отионашэ строгого порядка» граф радугами о ( С ) которого язляотоя цепь». Через Щ (соответственно Ч") обозначено ЫЕшеокю всех дуг и ребер неположительного (полокр-тельного) веса а «ультиграфе С.

Основные результат« диссертационной реботи состоят в следующем;

1 .Прздлокены и нселодоввш сетевые иоде ли слояпнх оболуаа-ванцих систем в виде взвешенных снованных мульткграфов. которые позволяют в значительной степени приблизить математические ооод-ства теории расписаний и практически* задачам ОХИ. Предложенные сетевые мод ;лк п метода позволяет ошонзать и учитывать многий типичные для задач ОКИ ситусцш! и ограничения, а имекао:

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

- наличие в обслуктааодей скотоме апм последовательных (различных), ток и параллельных (одинаковых по назначению) оОслугпввщях х!риЛороп, р:вт количества и стоимости несчо-

льких еидов используемнх ресурсов (складируемых и несклада-руемых);

- задание фиксированных (одинаковых или различных) маршрутов обслуживания одних требований и нефиксированных маршрутов обслуживания других требований;

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

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

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

4.Установлена КР-трудность задач оптглпяьного обслуживания (с прериьонкяш операций и без прерываний операций') трех требований С фИКСНрОЕ0ЖШМ!1 (одинаковыми или различными) маршрутами при сравнительно простых критериях оптималтости I и I Tj. Впервые доказана К -трудность задач теории расписаний с фикси -

тювашпл! числом требований и фиксированным числом приборов (не ограничено только гасла стадий по обслуживанию требований).

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

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

7.Па основе сетевого подхода разработаны адаптивные алгоритмы, позволящие определять специфические свойотва того или иного класса рэссматршаемых задач и учитывать затем ати особенности в процессе решения сложных задач из данного класса. Разработанные в диссертации алгоритмы реализованы в виде программ, которые включены в состав интерактивных ГШП РУПОР и МОРОЗ и практически использовались для решения многих задач календарного планирования.

СПИСОК ПУБЛИКАЦИЙ

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

1. Сотсков D.H. Расписания на смешинных графа* о ограниченным макашолышм штрафом // Известия АН БССР. Сор.

физ.-матем. наук. - 1980. - N 2. - С.37-41.

2. Сотсков Ю.Н. Задачи теорга расписаний на смешанных графах // Теория и методы автоматизации проектирования, - Минск: ИТК АН БССР, 1980. - 0. 19-22.

3. Сотсков Ю.Н. Об ориентировании ребер смешанного графа//Извес-тип АН БССР. Сер. физ.-матем. наук. - 1981.- N5.-0. 22-24.

4. Сотсков Ю.Н, Составление оптимального по быстродействию расписания выполнения взаимосвязанных работ последовательные . приборами // Методы и программы решения екстремальных задач. - Минск: ИТК АН БССР, 1981. - С.28-34.

5. Сотоков Ю.Н, Черняк Х.А. Определение параметров сетевого графика // Алгоритмы и программы решения екстремальных задач и сменные вопросы. - Минск: НТК АН БССР, 1982. - С.42-53.

6. Сотсков Ю.Н., Барановская С.М. Минимизация максимального штрафа за обслуживание требовании последовательными приборами // Сложность в методы решения задач оптимизации. - Минск! ИТК АН БССР, '934. - С.37-47.

7. Сотсков Ю.Н. Сетевые модели в теории расписаний // Оптимизация, принятие решений, микропроцессорные система. -Софии ИТКР Болгарской Академии наук, 1985. - С.157-162.

8. Сотоков Ю.Н. Оптимальное обслуживание двух требований при регулярном критерии // Автоматизация процессов проектирования. - Минск: ИТК АН БССР. 1985. - С.86-95.

9. Сотсков Ю.Н. Сетевой подход к решению задач теории распи-оаниЯ // Методы, алгоритмы и программы решения вксггмгмаль-нь'х задач. - Минск: ИТК АН БССР, 1985.- С.52-6?.

10.Сотоков Ю.Н., Алгакэвич В.Б. УстоАчмвость оптимальной ориентации робе, смешанного графа // доклады АН БССР. -

198Р. - Т.32, N 9. - С. 103-111.

11.Сотсков D.H. Устойчивость оптимального расписания выполнения множества операций // Известия All БССР. Сер. {из.-мате«, наук. - 1988. -Мб,- С.99-104.

12.Шахлевич Н.В., Сотсков D.H. Использование декомпозиции для минимизации общего времени обслуживания требова7-*й последовательными приборами // Методы решения вкотремальных задач и смежные вопросы. - Минск: ИТК АН БССР, 1990. - С.4-25.

13.« ленский A.B., Сотсков D.H. Подсчет активных расписаний выполнения независимых операций в системе о последовательными и параллельными приборами' // Метода решения экстремальных задач и смепше вопросы. - Минск: -ИТК АН БССР, 1990. - С.26-37.

14.Сотсков D.H., Танаев B.C. Построение расписания, допустимого относительно смешанного мультиграфа // Иззостия АН БССР. Сер. физ.-ыатем. наук. - 1939. - Н 4. - С.94-98.

15.Сотсков D.H. Устойчивость оптимального расписания при регулярном критерии // Методы решения экстремальных задач. - Минск: ИТК АН БССР. 1989. - С.48-56.

16.Сотсков 13.Н. Оптимальное планирование детерминированных работ в вычислительной системе // Автоматика и вычлол. техника. - 1939 -HI.- С.17-22.

17.Сотсков D.H. Сетевая модель оптимального использования нескладаруемых ресурсов // Методы решения окстремалышх задач. - Минск: ИТК АН БССР, 1989. - С. 35-47.

18.Сотсков D.H. Устойчивость оптимальнш по быстродействию расписаний // Журнал ьычисл. метем, и матеи. физики.- 19Я9. -• Т.29, N 5- - С. 723-731.

)9.0отскоя ,«).Н. Использование устойчивости оптимальных расписаний для синтеза информационно-вычислительных сетей //

Агтоматкка и вычисл. техника. 1990. - № 2. - С.54-61.

20.Ковалев М.Я., Сотсков D.H. Устойчивость е-приближенши решений булевых задач минимизации .т*чейной формы II Известия АН БССР. Сер. физ.-матем. наук. - 1990. - N 2. - С.111-116.

21.Ковалев !-,Я., Кузнецова О.В., Подолгоошй О.Ы., Сотоков D.H. Построение оптимального расписания работы гибкого автоматизированного участка // Известия АН БССР. Сер. (Jas.-техн. наук. - 1989. - N 4. - С.104-109-

22.Алшкевич В.Б., Сотоков D.H. Устойчивость в задачах календарного планирования // Извеотия АН БССР. Сер. фаз.-техн. наук. -1989. - N 3. - С.102- 107.

23.Сотоков D.H. Слокаооть задач теории расписаний о фиксированным числом гребований/УДоклада АН БССР.- 1989.-Т.33,N 6.-С.483-491.

24.Танаев B.C., Гордон B.C., Сотоков D.H., Янова О.В. Пакет программ решения задач теории расписаний // Управляющие системы и машины. - 1989. - N 4. - С.107-111.

25.Сотсков D.H. О олоююоти построения расписаний, допустимых относительно смешанного графа И Известия АН БССР. Сер. физ. матем. наук. - 1991. - Н 1 - С.121.

26.Сотсков D.H., Шахлевич Н.В. NP-трудность задач оптимального обслуживания трех требований // Известия АН БССР. Сер. физ.-матем. наук. - 1990. - N 4. - С.96-1'и.

27.Сотсков D.H. сложность задач оптимального обслуживания трех требований // Кибернетика. - 1990. - N 5. - С. 74-78.

28.Горох О.В., Сотсков D.H., Андреев С.И., Андреев Г.В. Пакет гтрогрямм оптимизации упаковки изделий (краткое сообщение) // Упр-тлящие системы и машины. - 1991. - N ?. - С. 100 -103.

29.Шп*.1|«рич Н.В., Сотсков Ю.Н. Построение оптимального по быстро-

действию ксыпахтного расписания. - Препринт / ИТК АН БССР. -Минск, 1987. - H 18. - 28 с.

ЗО.Алшкевш; В.Б., Сотсков D.H. Исследование устойчивости оптимальных по быстродействию рааг-саний.- Препринт/ ИТК АН БССР.-Минек, 1987. - Я 9. -20 с.

31.Зверев З.И., Андреев Г.В., Буракова Н.С., Кабанова Л.П., Сотсков D.H. Диалоговый редактор всходил текстов. Язык хо-манд. - Минск! ИТК АН БССР, 1983. - 150 я.

32.Зверев В.И., Андреев Г.В., Бураксва Н.С., Кабанова Л.П., Сотсков D.H. Диалоговый редактор исходных текстов. Сообщения системы. - Игзек! ИТК АН БССР, 1984. - 68 о.

ЗЗЛаваев B.c., Гордон B.C., Сотсков D.H., Янова О.В..,Шафрвн-ский Я.М., Горох О.В., Барановская С.М. Пакет програж рвве-ния задаче оптимального упорядочения (ПШ1 РУПОР). - Микян ИНК АН БССР, 1986. - 66 о.

34.Ханаев B.C., Гордон B.C.. Сотсков D.H.. Янова О.В., Шеф - • ранений Я.Ц., Горох О.В., Барановская С.М. Паке? программ ре-еония задач оптимального упорядочения (ПШ РУПОР), списание программ. -- Нинсх: ИТК АН БССР, 1987. - 86 о.

35.Сотсков D.H., Барановская С.М. OzmtoASdft збелушмяха требований поедадсватеяшшш-ж параллельная ореборамж. -Минск: ИТК АН БССР, 1989. - 64 е.

36.Горох О.В., Сотоков D.H., Андреев с.И., Андреев Г.В., Анти-пова H.A. Автоматизированная система оптимальной упаковки изделий. - Минск: ИТК АН БССР, 1990. - 64 о.

37.Сотоков D.H. Раднуо устойчивости с-приближенного решения булевой задачи шшшкэацян jnœetaoa форм. - Препринт И 21, Минск, ИТК АН БССР, 1991.- 28 0.

ЗЗ.Сотсков D.H., Шахлеюге И.В. Адаптивный алгоритм минимизации общего времени обслуживания требований последовательными приборами // Изв. АН СССР. Техн. кибернетика. - 1990.- N 6. -С. 137-142.

19.COTOKOB D.H. Сетевые модели я метода оперативно-календарного планирования // 6th International slapoeium on Syetea-Modelling - control. - Lodz: Institute of Inloraatios Teohnical Uhivarsity of Lodz, - 1990.- V. 3-- P.1-5.

40.Sotskov Yu.N. Stability oi an optimal soh.ed.ule // European Journal of Operational Research.- 1991.- "V. 55.- P. 1-12.

41.Sotskov yu.N. Analysis of optimal and approximate aohedulea stability // Workshop on Discrete Algorithms. - Osnabrücks University of Osnabruok, 1991.

42.Sotskov YU.W. A review of solution stability analysis in aequ-ensing and scheduling - Preprint N 25. Minsk, Institute of Engineerirg Cybernetics of BSSR Aoadeny of Soienses, 1991.24 p.

43.Sotskov YU.N. The complexity cf shop-eoheduling problems with two or thrae jobs // European Journal of Operational Research, 1991. - 54.- P. 1 - 11.

44.Танеев B.C., Сотсков D.H., Струсевич В.А. Теория расписаний. Многостадийные системы. - U.: Наука, 1939. - 328 с.