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

. Б С , 2 7 ОКТ 1998

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

ШЕЯНОВ Анатолий Владимирович

МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ УПРАВЛЕНИЯ О »СЛУЖИВ А1ГОЕМ ДЕТЕРМИНИРОВАННЫХ ПОТОКОВ ОБЪЕКТОВ ПЕРЕМЕЩАЕМЫМ, ПРОЦЕССОРОМ

Специальность 05.13.0! —Управление в технических системах

Автореферат диссертации на соискание ученой степени кандидата технических наук

Н.Новгород -1998

Работа выполнена на кафедре Информатики и автоматизации производственных процессов Волжской государственной академии водного транспорта.

Научный руководитель:

доктор технических наук, профессор Ю.С. Федосснко Научный консультант:

кандидат физико-математических наук, доцент Д.И. Коган Официальные оппоненты:

доктор технических наук, профессор Л. С. Ломакина кандидат физико-математических наук, доцент В. А. Таланов Ведущее предприятие - Институт машиноведения РАН

Защита состоится " ¡Г" [ЛЪ'Л^Л 1993 г. _

часов на заседании диссертационного совета Д.063.85.02 в Нижегородском государственном техническрм университете по адресу: 603600, г. Нижний Новгород, ГСП-41, ул. Минина, 24.

С диссертацией можно познакомиться в библиотеке НГТУ.

Автореферат разослан " ¿Р""? 1998 г.

Ученый секретарь ,

диссертационного совета У) \/Ц(з<г<-1б' О А.П.Иванов.

ГазетЭТта 1998 Ф°Рмат бут™ бОхв^/Ло,

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

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

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

Актуальным направлением повышения эффективности использования ресурсов СТТ является реализация процессов управления на базе новых информационных технологий .

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

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

Применительно к различным задачам управления обслуживанием потоков объектов в системах со стационарным процессором дискретные оптимизационные модели

рассматривались в работах A.C. Беленького, B.C. Гордона, Р.В. Игудина, Д.И. Когана, С.Е. Ловецкого, B.C. Танаева, Ю.С. Федосенко и других авторов, а соответствующие программно-технические комплексы поддержки управления были созданы, в частности, для Камского грузового района, Уфимского порта и других транспортных предприятий РФ.

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

Известно, •что дискретные модели оптимизации использования ресурсов приводят к переборным задачам на конечном множестве допустимых управлений, которые теоретически могут быть решены путем непосредственной оценки всех возможных вариантов. Однако время, требуемое на отработку переборного алгоритма, сильно зависит от размерности дискретной модели. Например, число различных расписаний в простейшем случае однопроцессорного однофазного обслуживания объектов л-злементного потока равно числу всех возможных перестановок, т.е. л!. Это означает, например, чтс на компьютере, оценивающем 600 тысяч расписаний в секунду, задача синтеза оптимального решения для г- « 11 гложет быть решена полным перебором лишь зи l,)0v мик (здесь и далее в примерах временные оценти приведены к производительности процессора Pentium 11/233 MHz) . Примеры для других значений г. приведены б таблице 1.

Таблица 1.

п Время синтеза оптимального решения Единица измерения времени

10 6, 048 Секунда

15 25,225 Сутки

17 18,798 Год

20 128578 Год

?

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

Заметим, что в иззестных эксплуатационных ситуациях на внутреннем водном транспорте модельный параметр п нередко принимает значения от 10 и выше.' Так, для пиковых навигационных условий количество объектов з обслуживаемом судопотоке может достигать 15-20 единиц. При этом регламент оперативного управления диспетчерского уровня предполагает формирование суточного план-графика (расписания) обработки тоннажа плавучим грузоперерабатьтающим комплексом з течение одного часа. Ясно, что в подобных случаях синтез оптимального план-графика в режиме real-time переборным алгоритмом практически нереализуем.

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

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

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

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

Именно эти направления наряду с задачаьхи моделирования рабочих процессов в СТТ образуют объект"исследования данной диссертационной работы^

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

Достижение поставленной цели требует рассмотрения следующих задач:

- обзор отечественной и зарубежной литературы по теме;

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

- постановка экстремальной задачи;

- анализ существующих методов решения оптимизационных задач управления однофазным обслуживанием конечных детерминированных потоков объектов;

- разработка алгоритмов синтеза точного решения задачи синтеза оптимального расписания однофазного обслуживания конечного детерминированного потока объектов перемещаемым процессором в рамках концепций динамического программирования (ДП) и ветвей и границ (ВГ);

- разработка и реализация алгоритмов синтеза субоптимальных расписаний обслуживания потока объектов перемещаемым процессором;

- создаТТО» » мот.д<аовательского программного комплекса для решения задач управления одностадийным обслуживанием потоков объектов перемещаемым процессором.

, Методическую и теоретическую базу диссертационной работы составляют подходы и инструментарий теории управления, теории рас;фсаний и вычислительной сложности комбинаторных задач, математического программирования, вычислительный эксперимент. Hpi: выполнении исследований автор опирался на работа г.с указанным разделам ряда отечественных и заруб« -кннх ученых (Д.И. Ватищев, Е.В. Левнер, С.Е., Л^веихий М.Х„ Прилуцкий, Т.П, Подчасова, С.М. Рсзер,

В.А. Таланов), а такке на результаты, полученные Д.И. Коганом, Ю.С. Федосенко, B.C. Танеевым,

М.И. Фейгиным, В.В. Шкурбой, И.Х, Сигалом, М. Сзгеу, D. Johnson.

Научная новизна работы состоит в следующих выносимых на защиту результатах:

- разработана базовая математическая модель однофазного обслуживания конечного детерминированного потока объектов перемещаемым процессором, а

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

- сформулирована экстремальная задача синтеза оптимальной программы управления обслуживанием потока объектов перемещаемым процессором;

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

- разработаны и реализованы программные средства синтеза оптимальных и субоптимальных управлений однофазным обслуживанием объектов конечного детерминированного мультипотока, размещенные в Internetno адресу

ftp ://ftp.aqua.sci-nnov.ru/шаth/shedule.zip Обоснованность и достоверность результатов обеспечена доказательствами сформулированных в работе положений и вычислительными экспериментами.

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

Реализация результатов работы. Работы по теме диссертации выполнялись в соответствии с координационными планами научных исследований РАН по комплексной программе "Кибернетика", поддержаны грантами Российского фонда фундаментальных исследований (проект 96-01-01428) и Госкомитета по ВО РФ (95.2.416). Материал диссертации использован в учебном процессе кафедры Информатики и автоматизации производственных процессов Волжской государственной акаде»4ии водного транспорта и кафедры Информатики и автоматизации научных исследований Нижегородского государственного университета им. Н.И. Лобачевского.

Ряд созданных в рамках диссертационной работы алгоритмов синтеза оптимальных расписаний передан для использования в специализированных компьютерных системах управления ресурсами на транспортно-техно-логических объектах в портах Казани и Уфы.

АпроС. у,;я результатов работы. Основные положения и результаты диссертационной работы представлялись и

докладывались на следующих научных конференциях и

семинарах.

- XI-й Иеясдународной конференции по проблемам теоретической кибернетики (Ульяновск, 1996}.

- IV-й конференции "Нелинейные колебания механических систем".(Нижний Новгород, 1996).

- Всероссийских созещаниях-семинарах "Математическое обеспечение информационных 'технологий б технике г образовании и медицине" (Воронеж, 1996, 1997).

- Международной конференции "Нечеткая логика, интеллектуальные системы и технологии" (Владимир, 1S97).

- Международное семинаре "Нелинейное моделирование и управление™ (Самара, 1997).

- Х-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1997).

- Третьей международной научно-технической конференции "Новые информационные технологии d региональной инфраструктуре™ (Астрахань, 1997).

- 2-f; кэхедукародиой научно-технической конференции "Интерактивные система: Проблемы человеко-компь-гао.'ерного ьзаиггодейсявик" (Ульяновск, 1997) .

~ 3-й международной конференции "Дискретные модели б теории управляющих систем", (Москва-Краснови-ДОЗО, 1SS3).

Публикации. По теьсе исследования опубликовано 15 работ; основное содержание диссертации отражено и работах [1-11].

Структура и объем работы. Диссертация состой; из введения, пяти глав и заключения. Окг со.р.ерзит- ".21-страниц текста, 26 рисунков, список литература и~ 5/ наименований и 3 приложения.

Во введении дается общая характеристика раОо^ы. раскрывается научная' новизна и практпчес.-сгь гиг.чи-мость полученных результатов. Аннотирование ко главам излагается обзор содержания диссертацил.

В первой главе. (Потокоак® задачи оСсяугьс^г.;^.:; ©Зеср як^сгрегуры к проблека^««!) проведен обзор проблематики в области решения потоковых задач обслуживания. Особое внимание уделено вопросу о NP-трудности данного класса задач. Ь связи с этим рассмотрены возможные подходы к их решению.

В §1.1 вводится понятие дискретной потоковой задачи обслуживания. Отмечается целесообразность детерминированного подхода к моделированию оперативного управления ресурсами СТТ (в отличие от вероятностного формализма теории массового обслуживания)„

Основными элементами дискретных моделей, используемых в решении -задач управления ресурсами СТТ, являются обслуживающий процессор Р и конечный детерминированный поток Zn объектов г(i), подлежащих обслугда-ванию (»= 1,л). Каждый объект r(i) характеризуется такими параметрами, как момент времени /'(/) поступления для обслуживания, продолжительность т(/) обслужиазния процессором Р, штрафом о(/) за единицу времени пребывания в системе обслуживания. Описываются ограничения, возникающие из содержательных особенностей рассматриваемого класса систем: обслуживание каждого объекта реализуется без прерываний; в каждый момент времени процессор может обслуживать только один объект потока Zn; по завершению обслуживания объект немедленно освобождает процессор; немотивированные простои процессора и объектов запрещены.

В §1.2 рассматривается вопрос трудоемкости синтеза оптимального расписания обслуживания объектов потока как экстремальной задачи переборного типа. В связи с практической нереализуемостыо ее решения полным перебором для значимых в приложениях значений размерностей потоков обсуждается проблема построения алгоритмов, решающих эти задачи за приемлемое время. Указывается, что рассматриваемый тип задач относится к классу NP-трудных и, таким образом, построение полиномиального алгоритма не представляется возможным.

Рассмотрению возможных методов решения исследуемого класса задач посвящен §1.3.

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

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

Задан бинарный поток Zn объектов ;{/}, z(2), ..., подлежащих однофазному обслуживанию.

Для каждого объекта :(/) с номером / определены: S°(i) " дискретный момент времени поступления в очередь на обслуживание (f°(l)S:0, S°(i-i)£ S°(i). /*=2,ге); v(t) - продолжительность обслуживания? a(i) - коэффициент линейкой функции штрафа на интервале от /'{>) до момента завершения обслуяизаник;

j'(i) - булев параметр, идентифицирующий принадлежность объекта с.дно,-.г/ из двух подпотоков (/(0 = 0) или zx 0 = 5) •

В оекошеиии полшотоков So и считаем, чте

z3 и л. = я0 г» = 0. Для процессора Р задана (2х2)~кгтрица ¡5(п. ß)! псс^сляктгльностей настройки при переходе от оЗспу-хо5вгкия объекта ks подпотока 2с к о5служпэ::к:э объекта из подпотокг 2р. Здесь а,р = 0- 1» к: аыпсякечк условия: 8(a,ß)ä:0 при а £ ß; 5(iz,ß)=G при с ~ ß.

Процессор готоа к обслуживанию объе.-мгез штоха с момента t-T к изначально настрое::, не. ибслулиз.ч-нко по^потокг ¿*fo .

Допустима расписания обслуживания явядага kov*-пактными. Поэ'лсг.гу расписание К обслуживен:*,*; пстокй .3" однозначно представляется перестановке?.

(/,, ¡2,..., fe ..., У ;')

номеров /{( & = 1,и), соответствующей порядку о5слу;::~:аг~ пия объектов -(4).

Для моментсп качала и згвериения ебслу-

жисания оЗъа.гта ;:(/) по расписание Л иг.;э:о-г место соотношения:

Ы'/) = йот (А>'Л T+Hgo,j{ii)\

Ып) = (i./л./) + 5(/'(4-/).y('i)). A4» (¿ = 2,и).

Суммарный штраф по всем объектам бинарного потока обслуживаемым по расписанию R„ определяется как сумма

я

ЩК) = g оШМО - Ш (2)

Задача синтеза оптимального расписания обслуживания бинарного потока 2" сводится к отыскании на конечной совокупности О всех компактных расписаний перестановки вида (1), доставляющей минимум функционалу W(R)} т.е.

W(R')=minW(R), (3)

В §2.2 показывается NP-трудность задачи (3) к делается вывод о невозможности построения "быстрого® решающего алгоритма, время отработки которого, полиномиально зависит от размерности задачи.

Применению метода ДП к решению задачи (3) посвящен §2.3. В этом случае процесс решения.задачи представляется как последовательность принятий решений по постановке к процессору объектов потока Я" из числа поступивших в очередь на обслуживание; решения принимаются в ситуациях, когда процессор свободено

Момент принятия решения характеризуется текущими временем I и настройкой процессора g, а также множеством S, номеров объектов, ожидающих обслуживания.

Через С(у) и Щу) обозначим множество номеров соответственно необслуженных объектов и объектов, поступающих в очередь на обслуживание в произвольный момент времен^ у. Считается, что в очереди к процессору зсегда присутствуют фиктивные объекты s(fo) и s(fi), относящиеся к подпотокам Z0 и Zi соответственно* Фиктивные объекты характеризуются нулевыми коэффициентами штрафа. Обслуживание объекта (/ » 0,1) осуществляется от момента t до момента f(q) поступле-

ния в систему очередного объекта :(д) потока г", если выполняется условие /'=£. В противном случае обслуживание осуществляется на интервале [/./'(?)]*. где *'(?) = шах (/>(д), I + 8(£. /)).

Введем следующие обозначения:

Т/ - объединение множеств {fo.fi) и 5,;

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

I,

0 ^(У) ~ совокупность номеров объектов,

поступающих в систему на интервале [/+1,/.]."

и(а) - момент времени завершения обслуживания объекта ¿(а);

С(4£,Т(,а) - величина суммарного штрафа за обслуживание на временном отрезке £/, Л(а)-1] объектов потока 2П с номерами из множества Т, и объектов, поступающих в систему в моменты времени /+1,1+2,- I:

V—/+1 тьК»!

Рекуррентное соотношение ДП для синтеза имеет

вид:

ИаШ1

шт {С(<,£,Г, ,а) +

(а),1 - з, (5, \ {а} Д/. (. -V.)}]

В ситуации, характеризующейся тройкой (л 5 г';}, яа обслуживание следует поставить объект с номеро;- а, на котором достигается минимум правой соотно-

шения (5) . Фиксирование б процессе вычислений номеров с:* позволяет очевидным образом построит:- оптимальное расписание й*.

Реализация рекуррентных соотношений (5) согласно схеме ДП предполагает вычисление значений Ч^/.яД) для всех возможных наборов (I, g, 5,) с сохранением их в таблице. При этом / меняется от /"(я) до Т, размер таблицы - (/°(л)-7)-2'"1 значений.

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

Предлагаемые подходы:

1) Хранить в таблице только те значения Ч'Ц&Б,), для которых первый аргумент изменяется на интервале

' [/, /+ тах8(у,/) + тачт(/')].

При этом размер таблицы для хранения значений функции 4* сокращается до величины (?-2я*\ где § -длина временного интервала.

2) Применить предварительную разметку» маркирующую только те наборы аргументов, вычисление функции на которых необходимо.

• 3) Синхронизировать разметку и вычисление значений функции У. Хранение разметки обеспечивается стеком используемого языка программирования, допускающего рекурсивные вызовы функции V. При этом исчезает необходимость выполнения обратного хода алгоритма ДП.

Описание реализации последнего подхода приведено в п.2.3.3, а пример технологии расчета - в п.2.3.4. В п.2.3.5 приводятся оценки быстродействия реализованного алгоритма по результатам тестирования. На стандартном наборе из 10 типов объектов максимальное зарегистрированное время синтеза расписания для бинарного потока из 16 объектов равно 10,19 сек.

В §2.4 рассматривается применение метода ВГ к решению задачи (3). Соответствующий алгоритм описан в п.2.4.1.

Метод ВГ реализуется на древовидной модели Н

множества П, к-й ярус которой (¿ = !,я) относительно корня соответствует номеру в (1), а каждая вершина -принятию решения на обслуживание конкретного объекта. Путь от корня к вершине однозначно определяет частичное расписание Я^к) = {/|...../4), характеризующееся:

моментом времени освобождения процессора í,(Rp(k))c накопленным штрафом W(R¡,(k)), множеством S(Rp(k)) объектов, ожидающих обслуживания на момент принятия решения „

Обозначим через М, множество открытых зершин дерева Е, т.е. таких, из которых возможно ветвление в момент принятия решения; при í=T множество М, состоит только из корня дерева. Введем целую характеристику g текущей настройки процессораs g=i, если процессор настроен на обслуживание объектов подпотока

Считаем также, что множество S{Rp{k)} (¿ = J,ra-ll) всегда включает . б себя фиктивные объекты «гипов rw {ожидающий) и аг (перенастраивающий) с нулевьэш штрафами за единицу времени обслуживания» Продолжительности ízu и обслуживания объектов zw и zs соответственно равны f(irfl)- La(ir) 'л mih).j{ini))'

Использование фиктивных объектов ргглгшзнтйрует-ея слеяухвдши правилами.

1. Объекты sm> и ss занимают процессор Р и& гзре-мзкмом промежутке между двумя последовательно обслуги в а весами объектами z{ir) к -(íV+i) (;' s (i, 2,.... п -1}5 ,

2 „ Объект sw занимает процессор/ если одновременно выполняются условия;

а) объекты s{ir) и принадлежав одваху wvw-

эоку;

S5 Ldir}<f(i?>i).

Э. Объект zz занимает процессор, -тел« ог ¿¡п- -г. -.-»/,) и принадлежат разным подпотокгмо

С оговоркой в части дисциплины з^глт.д.;. потока if1 с процессором, допускающей после~оjí-г?яь-куг» постановку на обслуживание лишь сЗг.«ктоз одного подпогока, объекты ss ы zw позволяв Cjíc-"-; по-са-роенну» модель обслуживания бинарного по:?с:;г. .5" к. базовой.

В конкретных реализациях общая схема ws^oxí. ВГ сжтезь Я0 предусматривает циклическое выполнение елгдуощих процедур стандартного набора Ш о n¡i - проверка выполнения условия прекращений вычислительного процесса; О Пг ~ отсечение бесперспективным ветвей дереве. Е;

о П3 - ветвление;

о П« - вычисление верхней оценки W*{Rp) критерия (2); о П5 - вычисление ' нижней оценки W~(Rp} критерия {2) § о П( - идентификация'расписания

Процедура üi зазерпает работу алгоритма, когда множество М, пусто, что соответствует синтезу опта-мального расписания R*.-

Процедурой П2 вершины с минкей оценкой выше хранимой величины W рекорда (наименьпего из достигнуты! значений верхней оценки функционала ЩЩ) исключаются -из кногсестза М„ как источники бесперспек-шш направлений поиска решения (3) „

Процедура 03 реализует процесс ветвления. В данной реализации метода ЗГ для заявления выбирается вершке с наименьшей верхней оценкой sss Ма ®а~ браниая зершмна изымается из множества

Ветвление б зыбранкой вершина выполняемся ■jci.zur.z л о оямдазщкм обслуживания объектам текущего подпота-•«а % и фихсгизкьк объектам, согласно правила»: 1-3. Лля ззргаин, получениях в результата зэтзлекияг вн~ чкслягэ^сл значения сценок; з зависимости о? соотао-ления значений оценок и рекорда принижаете." рвшкив, .•Зуда:? ли данная ззрхина отброшена или пемащенг з Mt.

Зсли в пронесся выполнения процедуры üj apostso-оис обкезлекие значения W'e то по завершекигэ аэгзла-ния шговесгзс М, контролируется на предмет отеэчекия бе-пгрспективкьж направлений процедурой Fi2.

Характеристик:-: зер^гины-потомка получен-

ной при ветзлении вершины-предка -R^k} кгайг^вякем объекта с номером 4 и? о з с очитка а:о:: сп ив характеристик гс следующим есогнсзэкиямг

1}} « fH*#)>+ oftWXMW+W -

Процедура ¡ПЦ прс?/;зводит- вычисление верхней оценки Vf{R^ критерия {2} а выбранной вершине. За верх-ягта «цзчку критерия ношю принять значение (2} на

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

Процедура П5 вычисляет нижнюю оценку IV(R,,) критерия (2). Простейшую нижнюю оценку можно построить следующим образом:

- текущее время полагается равным t,(R/^k)), значение нижней оценки W~(RP) инициализируем накопленным штрафом HXR/k));

- пренебрегаем временем перенастройки процессора 8«х, р);

- объекты из S(Rp(k)) обслуживаются по порядку убывания отношения с(/)/т(/);

- все остальные объекты z(i) из множества необ-служенных СО) считаются обслуживаемыми с момента поступления, добавляя при этом к нижней оценке величину о(»)т(»).

Процедура П6 производит идентификацию структуры расписания Rоптимальному расписанию соответствует ветвь, на которой достигнуто последнее в процессе отработки алгоритма значение рекорда IV =И/*.

В п.2.4.2 рассматриваются возможные варианты реализации алгоритма.

Рассмотрены следующие стратегии ветвления:

а) ветвление в вершине с наименьшей нижней оценкой;

б) ветвление в вершине с минимальным значением верхней оценки.

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

Реализована возможность поддерживать множество А/, упорядоченным таким образом, чтобы исключить поиск следующей. выбираемой для ветвления вершины из М,. Тестирование показало, что поддержание упорядо-

чения на множестве А/, дает заметное снижение времени синтеза для задач большей размерности («>18).

В процедуре построения верхней оценки реализованы три варианта построения эвристического расписания - A*i, А'г, А%.

A+i - простейший алгоритм: необслуженные объекты обслуживаются в порядке поступления в систему. Качество эвристики не очень хорошее, но время работы линейно зависит от длины расписания.

А*2 - вариация алгоритма A*x: объекты рассматриваются в порядке поступления и накапливаются в множестве Si; на обслуживание ставится объект z(i) из S¡¡ с наибольшим значением отношения a(í)/x(í). Значение критерия на получаемом расписании лучше, чем при использовании A+i, но его синтез идет дольше.

А*з - алгоритм последовательного зондирования: необслуженные объекты добавляются в расписание по одному- для каждого объекта подбирается место для вставки в расписание. Значение критерия на решении с точностью до 1% близко к оптимальному, но время синтеза кубично зависит от размерности множества C(í)-

Реализованы две процедуры построения нижней оценки - А-1 и А_2 -

Алгоритм оценки A-i изложен в описании процедуры

•ГУ.,.

Процедура оценки А_2 основана на замене объекта ;(а.) с характеристиками подлежащего об-

слу;хиванигог на совокупность т(а) специальным образом сконструированных объектов с характеристиками (f(е.), 1 ,a(a)h(a)).

Сравнительные характеристики алгоритмов подсчета оценок приведены на рис.1.

Для иллюстрации технологии расчета п.2.4.3 содержи? пример синтеза оптимального расписания. В л. 2 , 4. <: приводятся, результаты тестирования быстро-дейстнкк реализованного алгоритма и его сравнение с алгоритмом ДП (рис.2).

Рис.^. Характеристик!» оценок

СЭледКГ

2,0

--- ~7?

Г у X Ч

МП \ X ад

-г-4.

0т&>

\—^ п к> че да

Рме.2. Сравнительные характеристики алгоритмов ВГ и ДП.

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

В третьей главе (Модшщрохвита к оггаивдвгзшрш ©0-евдхэомцнивв муяадгато'В'ок® о0"й®отоа>) модель обслуживания бинарного потока объектов обобщается на случай произвольного числа подпотоков. С учетом результатов сравнения алгоритмов ВГ и ДП, полученных в главе 2, обобщенная задача решается методом ВГ и приводятся результаты численного эксперимента. Рассматриваются практически .значимые модификации базовой модели, учитывающие:

- ограничения на дисциплину обслуживания (позволяющие выделить полиномиально разрешимые подклассы);

- наличие директивных сроков и штрафов за пробой процессора.

§3.1 посвящен построению модели обслуживания сультипотока объектов. В п.3.1.1 излагается содержательная постановка задачи, а в п.3.1.2, 3.1.3 форму-шруется математическая модель и экстремальная зада-га синтеза оптимального расписания обслуживания ¿ультипотока объектов.

В обобщенной модели обслуживания целочисленный тараметр j(i) идентифицирует принадлежность объекта эдному из ш подпотоков. В отношении подпотоков Z\e ..., 2Ш считается, что

т

(J Zi = zn, Zi n Zj = 0 Vi * j.

Матрица |5(и, P)i продолжительностей кастройки при переходе от обслуживания объекта из подпотока Za к обср.ужмЕанию объекта из Zß имеет соответственно размерность (ихот) .

3 53»'? описываются кодификации алгоритма ВГ, необходимые для перехода от случая бинарного потока объектов г мультипотоку, суть которых сзохтяся к следующему:

- реализация механизма хранения (дахда)-матрицы !S(с, ¡3)1;

- введение в множества S(Rp(k)) вместо объекта ss фиктивных объектов , zsi, ..., :sm для изменения настройки процессора нг подпотоки Zu ..., 2S ссетззт-стзенно.

Требование- "не ставить подряд два объекта типа zs" реализуется в естественном предположении выполнения неравенства треугольника

V сгГ',Т S<a,ß)+S(ß,y} fe 8(а,у).

Результаты тестирования реализованного алгоритма ПГ приводится в §3.3 м проиллюстрированы на рис.З.

Рис. 3. Зависимость средней продолжительности синтета оптималыюго расписания от параметров мультипотока п и т.

В §3.4 показывается, что свойство полиномиально! разрешимости ряда частных подклассов задачи диспетчеризации для однопоточной задачи сохраняется и ! случае мультипотока. Конкретно речь идет о подклассах (¿-расписаний, ц-расписаний и моделях с к типам! объектов в потоке1'.

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

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

§3.5 посвящен двум возможным расширениям задачи оптимизации обслуживания мультипотока объектов.

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

В четвертой главе (Разработка алгоритмов сзимгеас р&цмоштэдшх расписаний для однопроцессорных моделей

11 Коган Д.П., Федосенко Ю.С. Задача диспетчеризации: анализ вычислительной сложности и полиномиально разрешимые подклассы. Дискретная математика. РАН. Т.8. N3, 1996.

дкофааиоуо абслутгиваикя. Оценка уетойш«®оеггг р©ша-ия) разрабатывается и экспериментально исследуется яд эвристических алгоритмов синтеза рациональных субоптимальных) расписаний. Программные реализации □строенных алгоритмов подвергаются сравнительному естированию по скорости и точности приближенного эшения. Рассматриваются вопросы оценки устойчивости эшения и приводится пример исследования устойчи-эсти для модельной задачи обслуживания объектов би-эрного потока.

На практике допустимое время синтеза оптимально-э расписания обслуживания потока объектов сильно 1>раничизает размер задач, поддающихся точному решено. В связи с этим возникает задача разработки ал-эритмов, которые, не гарантируя возможность по-гроэния точных решений, все же позволяют за допу-гиггае производственным регламентом время синтезиро-;ть расписания приемлемого для использования ка-гства. Такие расписания будем называть рациональны-5. Различные эвристические алгоритмы синтеза рацио-■лькых расписаний конструируются в §4.1.

Простейшие эвристические алгоритмы, основанные г дисциплина обслуживания объектов "в порядке поколения", рассматриваются з п.4.1.1. Это алгоритм ., строягдий гризиальное расписание, и его вариация !. Согласно логике работы алгоритма Ь2 объекты рас-гатриваются в порядке поступления и накапливаются в ;о;:сзстве на обслуживание ставится объект "(О из St наибольшим значением отношения т{(]1а{И).

Алгоритм последовательного зондирования 1\3 опи-гаается з п.1.2: необслуженные объекты добавлягот-1 з синтезируемое расписание по одному. При этом ^сто вставки очередного объекта в расписание подби-:ется переберем вариантов.

П.4.1.3 пссзящен описанию (р,я)-алгоритма (алго-;тм Ь4). На первом шаге алгоритма расписание Я ини-(ализируется пустым расписанием, а множество С не-¡служенных объектов ~ множеством {!,2,...,я}„ Далее выбреются первые р объектов (р<п) из Си строится оп-■мальное расписание их обслуживания. Начальный сег-нт этого расписания, состоящий из ц объектов (ц <, р), реносится в синтезируемое расписание Я. Оставшиеся

Pif объектов возвращаются в С. Процедура циклическ! прш&ишется к объектам множества С до полного ег< исчерпания.

Алгоритм h5 (использование алгоритма ВГ в качестве эвристического) рассматривается в п.4.1.4.

При решении задачи методом ВГ, как правило, наблюдается следующая последовательность, событий: Hi начальном этапе вычислительного процесса значени< рекорда улучшается; оставшееся время алгоритм занимается отсечением ветвей без улучшения значений рекорда. Второй этап процесса синтеза по сути являето процессом "подтверждения" оптимальности уже найденного рекордного расписания. Эксперимент показал, чт< второй этап работы алгоритма требует в среднем в дв; раза больше ветвлений, чем первый. Например, npi и=20 для получения приближенного решения можно остановить работу алгоритм по прошествии 50000 вызово! процедуры ветвления с момента последнего улучшени. рекорда. При больших значениях п естественным яв ляется другое условие останова алгоритма ВГ - превы шение отведенного на синтез расписания времени.

В п.4.1.5 излагается алгоритм Ьб, основанный н методе кристаллизации. В основе метода кристаллиза ции (simulated annealing) лежит аналогия с термоди намическими процессами, имеющими место при остывани и кристаллизации металла. Общая схема данного мето да, подходящая для решения комбинаторных проблем оп тимизации большой размерности и с большим числом ло кальных экстремумов', известна под названием алгорит ма Метрополиса (Metropolis algorithm). Для примене ни я алгоритма Метрополиса к системам, отличным о термодинамических, необходимо ввести следующие эле менты.

- Описание возможных конфигураций системы.

- Генератор случайных изменений конфигурации.

-Целевую функцию Б (аналог энергии)в качеств

критерия оптимизации.

- Управляющий параметр Т (аналог температуры) расписание кристаллизации, описывающее как Т меняет ся от высоких значений к низким.

Для применения метода кристаллизации к задач обслуживания мультипотока определим элементы алго ритма h6 следующим образом.

Возможные конфигурации - множество всех расписа-лй, представленных перестановками.

Случайные изменения конфигурации включают две азновидности: часть расписания записывается в об-атном порядке либо "переставляется" на другое мес-о. . -

Целевая функция - значение критерия на расписа-

ии.

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

Результаты тестирования алгоритмов Ы-Ьб приво-¡ятся в §4.2. По результатам экспериментов наилучшие )езультаты показали алгоритмы ЬЗ и Ьб. Оба алгоритма ¡оказывают среднее отклонение от наилучшего из-5естного значения критерия в пределах 1%. Алгоритм 16 показал лучшие результаты в большем количестве гестов. С другой стороны, дополнительным достоинством алгоритма ЬЗ является малое время отработки, ле превышающее на рассмотренных примерах (для л250) 0,05 секунды.

В §4.3 рассматриваются вопросы оценки устойчивости расписания. Различные ее определения (в частности, по функционалу и по структуре ) вводятся з п.4.3.1.

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

В п.4.3.2 приводится пример исследования устойчивости для модельной задачи.

В пятой главе (Структура кай^жтвкого ксшшакеа) списывается разработанный прм/'^лолнении диссертаци-

онной работы программный комплекс синтеза оптима.1 ного (субоптимального) расписания обслуживания.

В §5.1 дается краткое описание программного кс плекса (п.5.1.1).

Комплекс синтеза оптимального расписания одь сталийного обслуживания дискретного детерминировг ного потока объектов перемещаемым процессором пре ставляет собой исследовательское средство. Для peu ния задачи синтеза оптимального расписания при^ няется адаптированный метод ВГ. Программный компле написан на языке С++ и откомпилирован 32—>: битн компилятором DJGPP.

В п.5.1.2 описываются назначение и возможное программного комплекса, а §5.2 посвящен изложен его структуры, состава, назначения файлов; опис вается штатный режим работы.

В §5.3 описывается интерфейс программного ко плекса.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

При решении указанной задачи получены следуют) научно-технические результаты.

1. Построена базовая математическая модель oi служивания потока объектов перемещаемым процессор! и ее обобщающие модификации, адекватно покрывают

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

гнкционирования ряда массовых транспортно-техноло-1ческих процессов.

2: Сформулированы и теоретически исследованы :стремальные задачи синтеза оптимальных программ [равления обслуживанием потока объектов переме-1емым процессором.

3. Разработаны алгоритмы синтеза точных и прижженных решений задачи оптимального управления од->фазным обслуживанием потока объектов перемещаемым >оцессором.

4. Создан исследовательский программный комплекс гя решения задач управления одностадийным обслужи-щием потоков объектов перемещаемым процессором.

5. Разработанные алгоритмы переданы для реализа-[и в системах управления транспортно-технологичес-;ю! процессами на предприятиях внутреннего водного >анспорта.

По исследованной проблеме автором опубликовано < работ. Ниже перечислены публикации, в которых жведены основные научные результаты диссертации. Шеянов А.З. Полиномиальная реализация метода ветвей и границ в некоторых задачах обслуживания потоков заявок транспортного типа. Тезисы докладов на XI Международной конференции по проблемам теоретической кибернетики. СВНЦ. Ульяновск. 1996. Коган Д.И., Федссенко ГО.С., Шеянов A.B. Синтез оптимальных расписаний однопроцессорного обслуживания мультипотока об7^ектов. Труды ВГАВТ. Вып. 273. 4.1.ВГАВТ. Н.Новгород. 1996. Экспериментально-статистическое исследование алгоритмов синтеза решений в одной задаче оптимального обслуживания потока объектов. Сб. тезисов докладов IV-й конференции "Нелинейные колебания механических систем". Н.Новгород. 1996. Королев С.А., Федосенко Ю.С., Шеянов A.B. Опыт реализации алгоритмов динамического программирования для проектирования расписаний однопроцессорного обслуживания бинарного лотока заявок. Сб. Математическое обеспечение информационных технологий в технике, образовании, медицине. 4.1.Воронеж. 1996.

Коган Д.И., Шеянов A.B. Полиномиальная реализуемость метода ветвей и' границ для частных классов

задач диспетчеризации. Вестник ННГУ т Н.И.Лобачевского. Математическое моделирование оптимальное управление. Н.Новгород. 1997.

6. Федосенко Ю.С., Шеянов A.B. Задача управления oí служиванием мультипотока объектов в систег. raobil-процессоров. В сб. тезисов докладов межд> народного семинара "Нелинейное моделирование управление" Самара, 1997.

7. Федосенко ¡O.C., Шеянов A.B. Синтез оптимальнь решений для одного класса задач диспетчеризаци!-Матекатическое программирование и приложения. Тс зисы докладов Х-й Всероссийской конференции. Екг теринбург. Информационный бюллетень Ассоциац* математического программирования № 7 1997. У! РАН.

8. Федосенко Ю.С., Шеянов A.B. Математическая моде; и алгоритмы синтеза оптимальных управлений обсл^ живанием мультипотока объектов транспортного ti па. Новые информационные технологии в региональ кой инфраструктуре. Материалы третьей междукаро; кой научно-технической конференции. Астрахаш 1997.

9. Федосенко Ю.С.г Шеянов A.B. The generic dynamics model for an interactive schedule optimisation с object flow processed by mobile processor. Тезис докладов 2-й международной научно-техническ< конференции "Интерактивные Системы: Проблемы Ч< ловеко-Компыотерного Взаимодействия". 4.1. Улы новск. 1997. С.32-33.

1С.Шеянов A.B. Влияние времени передвижения проце< сора на оптимальное расписание в задаче обслуж! вания • мультипотока движущимся процессором. Тру; ВГАВТ. Вып.275. 4.2. Н.Новгород. 1998.

11.Программный комплекс синтеза оптимального расш сания обслуживания дискретного детерминированно] потока объектов перемещаемым процессором [post< 25 May 1998] World Wide Web» ftp://ftp.aqua.sci-nnov.ru/math/sheduie.zip