СППР

244

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

зависимости T^6cn = F(P^ ) , где Рид - некоторый показатель

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

позволит рассчитывать соответствующее время Tf6cn.

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

С„ J r ca и Pi осуществлять диспетчеризацию. Другими словами, алгоритм должен обеспечивать выбор из потока информационных сообщений те, у которых наибольшая важность и наименьшее среднее время анализа, и предоставление полученного решения оператору в вице рекомендаций. Это сдеііает возможным автоматизацию работы оператора посредством выбора для анализа наиболее информативных и важных сообщений.

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

Исходя из сказанного вфдіе, структурная схема СППР пункта анализа сообщений будет иметь вид, приведённый на рис. 2.35. Основными элементами системы являются блок выработки решения и блок обучения. В блоке выработки решения производится оценка важности поступившего сообщения, вычисляется значение показателя информационной доступности, по которому определяется среднее время анализа информационного сообщения данного вида. Далее в блоке управления работой оператора в соответствии с алгоритмом диспетчеризации вырабатывается решение, которое отображается оператору в виде рекомендаций. Блок обучения состоит из базы данных, хранящей подробную информацию об известных сигналах, и электронной таблицы, использующейся для учёта статистических данных о процессах анализа. Все проведённые операции фиксируются в электронной таблице, что в

245

дальнейшем отражается на изменении значения показателя информационной доступности.

Рис. 2.35 Структурная схема системы поддержки принятия решений

Таким образом, при работе СППР выполняются следующие основные процессы:

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

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

вырабатывается решение в соответствии с алгоритмом диспетчеризации;

-обновляется информация в базе данных и электронной таблице. Центральным элементом СППР является блок управления работой

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

246

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

информационной доступности pW i ■Это особенно актуально в системах

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

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

констатирующего типа в системах человек - машина по сравнению с сообщениями императивного типа не вызывает сомнений [10].

Процесс формирования плана выполнения процессов анализа включает в себя:

-ранжирование сообщений в Порядке уменьшения их важности и возрастании среднего времени анализа;

-определение "глубины" плана [10].

Первая задача интерпретируется [16] как задача составления расписания для одного оператора. При этом каждый из возможных видов информационных сообщений характеризуется следующими величинами:

і - номер вида сообщения; Тлоя - допустимое время анализа сообщения;

ta - среднее время анализа сообщения данного вида; С,- - коэффициент

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

доступности анализируемого потока.

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

	247
η.(,) = J^i* ecnliiO > 1 ? * '	(2.52)
[О-в противном случае.

Задача ранжирования сообщений в соответствии с [10] формулируется следующим образом. Необходимо найти такую перестановку сообщений П, где П(к) - і, если i-e сообщение должно быть проанализировано λ-м по счёту, чтобы суммарная функция штрафов была минимальной, а именно

Ση<(0

(2·53)

/=I

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

Всоответствии с [10] предварительно введём две величины

Λ = Σ - ~ - .	(2.54)
I=I^- *β|
M n	(2.55)
R2 β Σ - ½ - ,

i=w+l^ ' ^ai

где Ri и R2 характеризуют сумму отношений важности сообщений ко

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

вводимый с целью получения безразмерных величин R1и R2 (например,

maxi.

a I

Определим глубину плана исходя из заданного относительного уровня "notepb", связанного с исключением менее важных сообщений и сообщений с большим временем анализа из плана. Таким образом, необходимо рассматривать такое количество сообщений W=W0, при

котором

— <β,

(2.56)

R1 +R2

где β - заданный относительный уровень потерь.

248

Задача ранжирования сообщений в, пбстановке (2.53) относится к классу задач составления оптимального расписания. Такие задачи не поддаются решению аналитическими методами и считаются традиционно трудноразрешимыми [19]. Для их решения существуют точные и приближённые методы. Использование точных методов для ранжирования сообщений неприемлемо, так как они не предназначены для реализации в реальном времени. Поэтому в соответствии с рекомендациями [10] в основу алгоритма формирования плана выполнения процессов анализа можно положить один из наиболее эффективных приближённых методов - метод динамического программирования.

Из теории известны два подобных алгоритма: алгоритм Хелда - Карпа [17] и алгоритм Сахни - Горвица [16]. Ввиду меньшей вычислительной сложности второго, что довольно существенно при реализации в системах реального времени, воспользуемся им для формирования плана выполнения процессов анализа.

Множество сообщений	разбивается на два подмножества:
подмножество U - сообщений,	которые	можно проанализировать за
директивное время, и подмножество U -		сообщений, которые нельзя

проанализировать за директивное время. Пространство решений представляется в виде двоичного дерева [18]. Пусть все сообщения

пронумерованы в порядке неубывания директивных сроков		анализа
d x< d 2 <,...< dn. Все допустимые решения (разбиения)	можно записать в
виде последовательности литералов α^α^, -,α^, где	a = U или	a = U .

Если а = U , то Sj є U , и сообщение анализируется в указанном порядке и

с соблюдением директивного времени dx. Если же a = U , то Sj e l l , и сообщение не анализируется. Все возможные последовательности выполнения процессов анализа можно представить в виде ветвей двоичного полного дерева.

На рис. 2.12 нзображец^дерево для N = 4. Через I обозначен корень дерева, а остальным вершинам поставлены в соответствие

последовательности a ua 2,-,o .N· Например,	ветвь 1234	обозначает
разбиение (/ = (SliS3), С/ = {52,54}. Каждой	вершине	a l,a 2,...,aN

двоичного дерева ставится в соответствие пара (η,τ), где η обозначает

сумму штрафов сообщений, уже находящихся в U i а τ		обозначает общее
время анализа сообщений, находящихся в U , т.е.
η= Σ^ΛΟ; T= Σ ν		(2.57)
α,=ι	CXi=/

На рис. 2.36 приведен пример дерева решений, построенного для 4-х сообщений с типичными параметрами (табл. 2.9).

Рис. 2.36 Пример двоичного дерева полного решения для N

250

Т а б л и ц а 2.9

Работа алгоритма заключается в вычислении последовательности

множеств .... S^-nK Каждое множество Si0 представляет собой лексикографически упорядоченный набор пар (η,τ), сопоставленных каждой вершине уровня / в двоичном дереве (компоненты пары соответствуют суммарному штрафу и суммарному времени выполнения).

Формирование	на каждом уровне происходит следующим образом.
Для каждой пары (η,τ) реализуется проверка
	т +t Bj <7}доп.	(2.58)
Если условие (2.58) выполняется, то образуются множества
	U = U и {(η, τ + ta/)},	(2.59)
	£7= £/υ{(η + η,·,τ)},	(2.60)

в противном случае - только множество U . После просмотра всех пар (η,τ) /-го уровня множества U n U сливаются и получается множество

S(t) = U u U . Затем исключаются бесперспективные ветви дерева. Если

вершинам α 1,α 2,··.,αΝ и		P15P2V 5PaT соответствуют пары			(ηα,τα) и
(ηβ,τρ) такие,	что %а £	и	τα <	то лучшее полное решение,
начинающееся	с a 1, a 2,—, a N,		является	по крайней мере	таким же
хорошим, как и лучшее полное решение,				начинающееся с	PltP2V 5Pjv.

Следовательно, частичное решение, начинающееся с Pi,P2, -,Pjv, можно

исключить,	поскольку	над	ним доминирует a I,a 2,...,aN	[18,19].
Оптимальное	решение	(X1,	а 2..--,Oln соответствует паре из	с

наименьшим значением η.

Обобщённая схема работы алгоритма диспетчеризации приведена на рис.2.37. Основной задачей этого алгоритма является формирование дерева полного решения и поиск вершины с минимальным штрафом. Блок-схема

251

Рис. 2.37 Обобщеннаясхемаалгоритмадиспетчеризации

Исходные данные для алгоритма задаются в блоке I. В нбм вводятся

значения Tfon (допустимое время анализа сообщения), Ї (номер вада

сообщения) и Jt (количество анализируемых сообщений). Кроме этого, в нбм производится формирование вершин 1-го уровня дерева - присваиваются значения переменных VRAN и SHTR. В блоках 2 - 2 5 осуществляется формирование дерева полного решения с исключением бесперспективных вариантов. Каждое из вершин дерева характеризует элемента массивов MAS, VRAN и SHTR. Это одномерные массивы с пределами изменения индекса от 1 до 2* (по числу вершин). Массив M AS- двоичный массив включений вершин в дерево. Если MAS(I)sO, то вершина исключена из дальнейшего рассмотрения, если MAS(I)=I - вершина рассматривается. Каждой вершине после завершения формирования дерева соответствует вариант полного решения. Формирование дерева заключается в последовательном заполнении массивов SHTR и VRAN и корректировке массива MAS от уровня к уровню. Номер уровня показывает, сколько сообщений включено в частичное решение, соответствующее вершинам данного уровня.

252

Нет

В массиве VRAN суммируется время анализа сообщений, которые укладываются в директивные сроки (S,eU); в массиве SHTR суммируются штрафы сообщений, анализ которых не укладывается в директивные сроки (Si s t/) .

В блоках 12-21 между собой сравниваются все вершины одного уровня. Если найдена такая пара значений, что VRANij\) ^ VRAN(Jl) и SHTR(JX) S SHTR(Jl), то f t исключается из дальнейшего рассмотрения. Результатом работы блоков 2 - 2 5 является массив MAS, каждый из элементов которого равен 1, если соответствующее полное решение He исключено из рассмотрения, и массивы VRAN и SHTR, каждый из элементов которых также соответствует полному решению.

В блоках 26 - 32 ведётся поиск полного решения с минимальным штрафом. При этом попарно сравниваются штрафы всех вершин j, для которых MAS(j)=l. Для вершины j с большим штрафом присваивается MAS(j):=0, а номер вершины с меньшим штрафом присваивается переменной f i . В результате остаётся только одна вершина, для которой MAS(J)==I и номер её присвоен переменной J3. Таким образом, найдено решение, позволяющее исключить из рассмотрения сообщения с малой важностью и большим временем.