автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему: Сетевые модели и методы теории расписаний
05-13.16 -применение вычислительной тегники, математит"окого моделирования и иатематлчееких методов в нау ала исследования!
Автореферат диссертации на оояока. ге ученой степени доктора физико-математических наук
Работа выполнена в Ордена Трудового Красного знамени Института технической кибернетики АН БССР
Научный консультант: доктор физико-математических наук, профессор ТАНАЕВ B.C.
Официальные оппоненты: доктор физихо-матеыатнчэеюа наук, npoijeccop Е-ЕЛИЧЕВ В.Д., доктор физико-математических наук, профессор ЛЕОНТЬЕВ В.К., член-корресповден? АН УССР, доктор физкко-математкческих наук, профессор ШОР Н.З.
Ведущая организация: Институт математики СО АН СССР
Запита состоится " ft " 1991 г. в часов на
заседании специализированного совета Д016.45.01. при Институте кибернетики им. В.М.Глуыкова АН УССР по адресу: 252207, Киев 207, проспект Академика Глушкова, 40.
С диссертацией мокно ознакомиться в научно-технической архиве Института.
Автореферат разослан " г.
Ученый секретарь специализированного совета
. 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 « . Для каждой операции известна
длительность > 0 ее выполнения. Прерывания при выполнении операций не допускаются, т.е. Тр^-И^, где ^ (соответственно - момент начала (окончания) операции I. Качество расписания характеризуется значением
заданной не убывающей по каждому из аргументов целевой функции 7(х) =» ?(х1,хг. г)' Оно являотоя существенным, если 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 второй главы поовящен моделированию обслуживающих
систем с последовательными и параллельными приборами. Пусть
попарно непересекающихся непустых подмасжестэ ЛЦ.Ж^. ^,
* = 3 , ^ л " .1=1,El, le * 1.
Кагдое множество ^ состоит из параллельных, одинаковых приборов типа к.
Шохеотво Q заданных операций тагага разбито иа m попарно непересекающихся непустых подопожаста:
Q s U Q,„ С^аз, Qj. п Q, ■» о, 1с=Т7и. 1=V3, k * 1.
Для выполнения непрерываемой операции icQ может бить использован любой из приборов цногзства
Известны длительности операций, пуско-наладочных, переналадочных ц транспортных работ. На множестве Q задано отно-шочес строгого порядка, указаны условия совмещения процессов выполнения операций к т.п. Вое бtu условия и ограничения представлены г ввде обобщенной временной модели (Q,U).
Зодане деловая функция Ф(х,у)=Ф(х1,х2. х(1>у1,у2>. уя)1 не убывающая но кахдому из аргументов. В задаче (которув в дальнейшем будем называть задачей А) тробуотся
-- определять число гг, г^ а к=Т7й, прабороз адо-
кеотве используемых в процессе выполнения операций Q,r; - распределять операции шюгоства Q,, по втиы приборш;
- построить расписание выполнения множества операций Q. Указанные действия необходимо выполнить так, чтобы значение целевой ФУНКЦИИ Ф(Х,У) бЫЛО МШШМаЛЬНЫМ При Xjsfj, i * QR,
Для моделирования такой обслуживающей систеш предложено использовать взвешенный смешанный мультиграф 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) веса вд соответственно. Во втором случае это ребро удаляется. Выбирая последова-вательно ребра смешанного графа С в применяя к каждому из них одно иэ трех указанных требований, получаем последовательность
,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<|У|, может быть достроена до полной допустимой последовательности а = (а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, приборами
45 с- и А, равно к=1 к
Теорема 4.2. Если приборы одинаковы, k=T7m, и
ыноаеотво операций Q неупорядочено, то число активных
m га рашисешй выполнения операций Q = U Qlr щибораш U ¡L, разно
m l&J "PIQk-l .xv ч y.
Величина , „ в теореме 4.2 обозначает количество iukl ,rk
различных представлений числа IQ^I в виде сушы г^.
неупорядоченных слагаемых, в величина а^' к равна
1_ , где гц - количество попарно различных
слагаешг в соответствующая нрэдотавлении 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 /Пд /П-, /Пд /П^ /П6, где признак П. означает тип об-олуаивапцей оиотемы (Р - маршруты обслукнвания требований одинаковы, «5 - маршруты различны, О - ыараруты не фиксированы), П2 - число оболуинващих приборов, П^ - ограничения на длительность ^^ выполнения операций, П^ - условия обслуживания требований ( Рр- прорывания операций допускаются, С=С - мнокэство требований линейно упорядочено), П^ -число обслуживаемых требо-
ваннв, П^ - вад целевой функции. В диссертации установлена Ю>
трудность оледущих задач теории расписаний: г / и / / рг / п=э / I т1, ? / м / / / П=з / Е ? / и / > о / / п»з / Е з / ъ / ^ > о / Рг / п=з / £ 11. л / 5 / > о / / п=з / Е о / з / г1ь / о=о / / е ^.
В § ? исследована сложность задачи оптимального обслуживания частично упорядоченного множества требований о одинаковыми длительностями операций. Пусть на множестве требований N задано отношение -»• строгого «порядка: еоли 1сН, 1*3, то при любой допустимом расписании завершение обслуживания требования 1 долзкно предяэствоаать началу обслуживания требования Справедлива следующая
Показано, что задача построения оптимального по
быстродействию расписания обслуживашм требований 1с11, поступающих в систему з моменты ¿^>0, сводится к задаче построения расписания с наименьшим значением максимального
временного смещения при 4^=0, 1еН. Справедливо и обратное утверждение.
В § 4 и § 5 развиваются алгоритмы последовательного анализа вариантов для точного и приближенного решения всевозможных задач теории расписаний. При атом существенно нсполгзуется сетевое представление обслуживащнх систем в виде взвешенных смешанных мультиграфов. В начале § 4 предложена общая схема решения сложных задач построения оптимальных расписаний при произвольных регулярных критериях. Далее отдельные саги общей схемы конкретизируются для различных частных случаев задачи теории расписаний в сетевой постановке. Приведены некоторые оценки трудоемкости метода ветвей и границ (оценки числа рассматриваемых вершин дерева решений) в зависимости от используемых оценок целевой функции, стратегии поиска, отношения доминирования и т.п. Описаны правила вычисления апостериорных оценок точности получаемых решений при преждевременном прекращении вычислений, а также преимущества приближенных алгоритмов с априорными оценками точности искомых решений. В конце § 4 показано, как можно использовать отнесение доминирования в схеме ветвей и границ для построения полиномиальных алгоритмов решения некоторых задач теории расписаний.
В § 5 разработаны алгоритмы последовательного анализа вариантов для решения описанных в § 2 и § 3 второй глава задач оптимального выбора необходимого количества приборов (ресурсов), оптимального р-".стт1 .деления заданного множеств я операций гга вы-
брашшм приборам и составления оптимального распгюания выполнения операций. При етом существенно используются результаты, полученные во второй главе диссертации.
В четвертой главе проведено исследование устойчивости оптимальных расписаний к изменениям длительностей опэраций, длительностей переналадок приборов к других параыетрор обслуживающей системы. Получзиные результаты направлены на расширение области применения методов теории расписаний для оптимизации фун-кцио .'¡гровония обслуживающих систем в условиях неопределенности.
В § 1 введены определения области, ыара и радиуса устойчивости оптимального расписания* При етш существенно используется сетевое представление обслугзгвакцей системы в виде взвешенного сыоеояного (нультн)графа О = (Q,U,V). Если оптимальное paermca-1ше . t ) определяется ориентированным графом
называть оптимальны и. Пусть 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„и обозначать через
pö(t). Пусть 0 и (t^.t^. tjj^) - неубывамцая последовательность длительностей операций множества \ , ы„д® = Id1> \ (|1>|. Доказаны следущие утверждения.
Теорема 1.1. Для того чтобы PB(t) = », необходимо и достаточно, чтобы для любого пути ц « Hg\ H и любого графа Ск€Р(о) существовал путь У е К^ такой, что .
Показано, что вычисление p(t) сводится к решению нелинейной задачи математического программирования:
max jxj - t1| ----> min,
mill пах Iх (Ц) a mill max l1 (i>),
B'TJ fleH3 kef(t) Vell^
Еслп 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 -множество натуральных чисел , а К*7 - множество всех
(0,1 )-вехторов у « (У1,Уг. Уи). Требуется при заданной
векторе 1; с й" и заданном непустой множестве УсУ" найти вектор
уМу^.Уг. у£> € У. дяя которого
га.уЬ - Е Чу> = юш с?и,у) I у«*>. (з)
Будем называть вектор у ревенном этой задача в предполагать, что множество У допустимых векторов не зависит о* вектора
Множество б(у,е) векторов пра которых вектор уеУ является с-приближенным решением, т.е. выполняется соотношение
У(4,у) * (1+с) Г (t.yt). (4)
представляет собой область устойчивости е-приближенного решения у. Показано, что множество О(у.е) является выпуклым, замкнутым конусом с вершиной в точке ОсВ* л выполняются равенства г^О(у.е) = / 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 БССР. Сер.