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

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

Ищенко Михаил Алексеевич

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

05.25.05- информационные системы и процессы, правовые аспекты информатики

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

Москва – 2009 г.

Работа выполнена в ГОУ ВПО «Российский государственный гуманитарный университет».

Научный руководитель доктор технических наук, доцент

Косяченко Станислав Анатольевич

Официальные оппоненты доктор технических наук, профессор

Максимов Николай Вениаминович

кандидат технических наук

Сергеев Станислав Алексеевич

Ведущая организация ГУ «Российский научно-исследовательский институт информационных технологий и систем автоматизированного проектирования»

Защита состоится «25» декабря 2009 г. в 14-00 часов на заседании диссертационного совета Д 212.198.02 при ГОУ ВПО «Российский государственный гуманитарный университет» по адресу: 125993, г. Москва, Миусская площадь, д.6

С диссертационной работой можно ознакомиться в библиотеке РГГУ по адресу: 125993 г.Москва, Миусская площадь, д.6

Автореферат разослан «24» ноября 2009 г.

Ученый секретарь Меркулов В.Н.

диссертационного совета

I. Общая характеристика работы

Актуальность темы. Широкое развитие автоматизированных информационных систем (АИС) определяет повышенные требования к качеству и эффективности процесса проектирования их информационного и программного обеспечения. Современные системы обработки данных характеризуются большим разнообразием и сложностью взаимосвязей элементов, обработкой больших массивов информации, наличием альтернативных вариантов обработки и элементов конкуренции при использовании ресурсов ЭВМ. Повышение эффективности проектирования систем обработки данных связано с использованием методов синтеза оптимального состава модулей программного и информационного обеспечения на этапе технического проектирования АИС. Вместе с тем, имеющийся в настоящее время аппарат для формализации задач синтеза оптимальных модульных СОД, реализуемых на современных ЭВМ, не полностью описывает их технологические возможности. Полученные проектные решения (структура программных модулей, содержание информационных массивов) определяются обычно без учета наличия альтернативных вариантов обработки, возможности параллельной реализации отдельных процедур, ветвей алгоритма и программных моделей, конкурентности их по отношению к ресурсам ЭВМ. Возникает необходимость в разработке моделей и методов синтеза оптимальных модульных АИС, позволяющих преодолеть отмеченные недостатки. Для этих целей целесообразно использовать аппарат сетей Петри, который позволяет формировать адекватные модели АИС, формулировать с их использованием задачи синтеза оптимальных модульных систем и разработать эффективные методы и алгоритмы их решения.

Формализация моделей и разработка эффективных алгоритмов решения задач синтеза оптимальных модульных АИС на этапе технического проектирования позволяют автоматизировать процесс проектирования систем, сократить сроки проектирования, отладки и внедрения систем в промышленную эксплуатацию на 20-30%, повысить качество проектных решений. Большие масштабы работ по созданию и внедрению АИС, а также недостаточная адекватность имеющихся моделей и методов формализации и автоматизации процесса разработки оптимальных модульных СОД, учитывающих расширенные возможности современных ЭВМ и их комплексов, обуславливают актуальность выполненных научных исследований.

Степень разработанности проблемы. Основы методологии синтеза структур автоматизированных информационных систем были заложены в работах ряда российских и зарубежных ученых: Котова В.Е., Питерсона Дж., Кульбы В.В., Урбански Ф., Спиридонова А.М. и др.

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

Объект исследования - модульные структуры автоматизированных информационных систем.

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

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

Данная цель достигается посредствам решения следующих задач:

- анализ и классификация технологий проектирования автоматизированных информационных систем. Формализация основных понятий связанных с использованием сетей Петри для анализа и проектирования АИС.

- разработка методов моделирования модульных АИС с использованием аппарат сетей Петри.

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

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

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

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

На защиту выносятся следующие положения:

1. Методология анализа и синтеза оптимальных модульных АИС с использованием аппарата сетей Петри.

2. Модели, методы, алгоритмы и программы анализа и синтеза оптимальных модульных АИС по заданным критериям эффективности.

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

4. Точные и приближенные комбинаторные алгоритмы решения поставленных задач синтеза оптимальной структуры модульных АИС.

5. Методы определения оптимального состава программных модулей при заданном информационном обеспечении АИС.

6. Методы определения оптимального состава информационных массивов при заданном программном обеспечении АИС.

7. Методы и алгоритмы синтеза оптимальной функциональной модульной блок-схем обработки данных.

Теоретическая и практическая значимость. Предложенные модели, методы и алгоритмы решения задач синтеза оптимальных модульных АИС разработаны автором впервые либо являются обобщением уже известных моделей. Их использование позволяет адекватно описывать процесс функционирования АИС, формализовать, алгоритмизировать и в значительной степени автоматизировать этап технического проектирования систем, повысить качество формируемых проектных решений. Разработанные с использованием сетей Петри формальные модели, методы, алгоритмы и программы обеспечивают синтез оптимальных по заданным критериям эффективности и различных по своему назначению модульных систем обработки данных на этапе их технического проектирования. Кроме того, их целесообразно использовать при разработке прикладного программного обеспечения АСУ (САПР АСУ). Использование разработанных алгоритмов и программ проектирования оптимальных модульных АИС позволяет сократить сроки разработки и внедрения систем в среднем на 20 – 30% и повысить их качество.

Внедрение. Эффективность разработанных в диссертационной работе моделей, методов, алгоритмов и программ синтеза с использованием аппарата сетей Петри модельных АИС подтверждена положительным опытов их использования при проектировании ряда систем. При непосредственном участии автора они внедрены при разработке АИС «ИНИОН АН РФ». Использование разработанных моделей и методов, алгоритмов и программ позволило сократить временные и стоимостные затраты на разработку и внедрение систем в среднем на 20-30% за счет оптимизации получаемых проектных решений.

Апробация работы. Основные результаты работы докладывались автором и обсуждались на международных конференциях: «Проблемы управления Безопасностью Сложных Систем», Москва 2006, 2007 гг., «Проблемы регионального и муниципального управления», Москва, 2009.

Связь с планами отраслей науки и народного хозяйства. Диссертационная работа выполнена в соответствии с координационными планами научных исследований РАН по приоритетному направлению 2.3.10.1 «Теория построения распределенных и модульных автоматизированных информационно-управляющих систем», а также планами научно-исследовательских работ Российского государственного гуманитарного университета в области повышения эффективности и качества систем данного класса.

Публикации. По теме диссертации опубликованы 6 печатных работ, в том числе 2 в изданиях, перечень которых утвержден ВАК РФ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, приложения и включает 143 страницы машинописного текста, 25 рисунков и 9 таблиц.

II. Основное содержание работы

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

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

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

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

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

Сетью Петри называется четвёрка элементов:

C = (P, T, I,O),

где P = { p1, p2,…,pn }, n > 0

множество позиций (конечное),

T = { t1, t2,…,tm }, m > 0

множество переходов (конечное),

I: T P

функция входов (отображение множества переходов во входные позиции),

O: T P

функция выходов (отображение множества переходов в выходные позиции).

Если pi I (tj), то pi – входная позиция j - го перехода, если pi I (tj), то pi – выходная позиция j - го перехода.

Для наглядного представления сетей Петри используются графы. Граф сети Петри есть двудольный ориентированный мультиграф:

G = (V, ),

где V = P U T, причём P T =.

Исходя из графического представления сети Петри, её можно определить и так:

C = (P, T, A),

где А – матрица инцидентности графа сети.

Определим понятие маркированной сети Петри – оно является ключевым для любой сети.

Маркировка сети Петри C = (P, T, I, O) есть функция:

N = (P), N N,

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

= {1, 2,…, n},

где n = P, а i N. Между этими определениями есть связь:

i = (pi)

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

Таким образом, маркированная сеть Петри представляет собой пятёрку элементов:

M = (P, T, I, O, ).

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

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

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

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

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

При решении практических задач часто необходимо совместное рассмотрение различных характеристик исследуемых объектов. Рассмотрим обобщенную сеть Петри (ОбСП) и дадим ее определение.

Обобщенная сеть Петри определяется как упорядоченный набор вида Nо6 =(P,T,,F,H,,,,,,), где Р = {р} - не пустое конечное множество позиций; Т = ТА Тс - не пустое конечное множество переходов, которое разбивается на два непересекающихся под­множества: ТА ={}, содержащее простые переходы, и Тс = {}, содержащее составные переходы (агрегаты первого уровня), которые имеют сложную структуру и сами являются сетями Петри (возможно, обобщенными); = {}- конечное не пустое множество цветов маркеров; и - функции инцидентности множеств позиций и переходов (N- множество целых натуральных чисел); :(P Q) T{l, 0} - функция распределе­ния цветов маркеров по входным позициям переходов сети; :T (P Q) P - функция распределения цветов маркеров по выходным позициям переходов сети; : L(N) - функция, отображающая множество слов свободного языка сети Петри во множество неотрицательных вещественных чисел; (l): (l L(N)) - минимальное время, за которое данное слово может быть получено
в сети No6; : L(N) - функция, отображающая множество
слов свободного языка L(N) в = {[,]: , ,i N} множество отрезков с концами из Значение (l) определяет
набор отрезков [,], …[,] таких, что слово l может быть получено только в течение промежутков времени
[,] = [,], …,[,]= [,]; - вероятностная мера, заданная на множестве всех подмножеств достижимых
маркировок 2R(N), (т.е. # 2R(N) [0, 1]); : Р N,2R(N) = {}, R(N) начальная маркировка сети, задаваемая матрицей размера |Q||P|, проиндексированной по строкам множеством цветов маркеров, а по столбцам множеством позиций сети.

Обобщенная сеть Петри является наиболее общей моделью и содержит (в зависимости от наличия в описываемом ее наборе тех или иных элементов) различные подклассы СП. Можно выделить тридцать два подкласса обобщенных сетей Петри.

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

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

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

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

Используемые в настоящее время традиционные модели АИС (сетевые, графовые мо­дели, и др.) не полностью учитывают перечисленные выше характер­ные особенности современных ЭВМ и систем обработки данных. Для учета этих особенностей при моделировании АИС пред­лагается использовать сети Петри, позволяющие адекватно описы­вать дискретные процессы обработки данных на современных ЭВМ или в сетях ЭВМ. Представим процесс функционирования АИС с помощью сети Петри, определенной набором . Поставим в соответствие каждому элементу вершину-состояние сети Петри, а процедуре обработки данных вершину-переход . В соответствии с матрицей взаимосвязи процедур и информационных элементов соединяем дугами элементы множеств и . Поскольку информационный элемент СОД может являться входным для нескольких процедур обработки данных, то для восстановления маркерных точек состояния соединим его с такими переходами , для которых существуют дуги . Пометим маркерными точками все состояния сети Петри, соответствующие входным информационным элементам СОД. Тогда – мерный вектор , координаты которого равны числу маркерных точек в соответствующих состояниях, будет определять начальную разметку сети Петри, моделирующую заданную систему обработки данных.

На элементах сети Петри введены теоретико-множественные операции, необходимые для выделения множеств элементов сети, обладающих заданными свойствами:

1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 

Операции 1 и 3 выделяют входные и выходные переходы для заданного состояния . Операции 2 и 4 выделяют входные и выходные состояния для заданного перехода . Операции 5 и 7 выделяют входные и выходные состояния сети Петри, операции 6 и 8 соответствующие переходы. При этом соответствует множество входных информационных элементов процедуры обработки данных , а - множество выходных информационных элементов.

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

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

;

;

;

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

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

Внешним интерфейсом модуля будет множество состояний

Информационному массиву АИС соответствует ядро фрагмента состояний

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

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

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

(1)

и соответственно энтропия запросов и среднего количества информации, содержащегося в одном ответе на запрос. Вероятности и удовлетворяют ограничениям:

(2)

(3)

Если АИС работает в справочном режиме без оперативного обновления информации, то в этом случае и функция (1) примет вид:

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

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

С использованием критерия максимума информационной производительности поставлена и решена задача синтеза оптимальной модульной блок-схемы обработки данных (критерий 1). Для решения данной задачи разработан комбинаторный алгоритм, основанный на методе локальной оптимизации. Показано, что разработанный алгоритм является сходящимся. Рассмотрена также задача синтеза структуры программного обеспечения оптимальных модульных АИС по критерию максимума их информационной производительности. Поставленная задача является задачей математического программирования. Алгоритм ее решения основан на методе последовательного построения, анализа и отбора вариантов. В процессе конструирования программных модулей определяется последовательность их выполнения, а также последовательность выполнения процедур обработки данных. Для сокращения числа рассматриваемых вариантов (в среднем на 10-30%) доказано следующее утверждение, основанное на особенностях модульных АИС и свойствах сетей Петри, описывающих данную СОД:

Утверждение 1. Пусть имеется последовательность выполнения и состав допустимых фрагментов Переход является таким, что

1) h ( h (N, P) ),

2) и такие, что F (p,

3)

4)

где

– объем оперативной памяти, занимаемый -ой процедурой;

- ограничение на объем фрагментов переходов.

В этих условиях последовательность фрагментов переходов является оптимальной, если оптимальна последовательность Здесь

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

, где - количество состояний во фрагменте состояний , - ограничение на число фрагментов состояний.

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

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

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

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

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

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

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

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

(4)

при ограничениях (2), (3) и дополнительных ограничениях:

• число переходов в каждом фрагменте переходов не более заданного;

(5)

• интерфейс между отдельным модулем и системой не более заданного:

(6)

• межмодульный интерфейс системы ограничен:

(7)

где - среднее время обращения к заданным информационным массивам, размещенным во внешней памяти ЭВМ.

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

Утверждение. Пусть - допустимые фрагменты переходов такие, что и переход удовлетворяет следующим условиям:

а)

б)

в)

Тогда, если существует оптимальное множество фрагментов, содержащее фрагмент переходов , то существует и оптимальное множество фрагментов, содержащих фрагмент переходов

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

Полученные в диссертационной работе результаты использования при проектировании АИС «ИНИОН АН РФ».

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

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

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

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

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

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

• определение оптимального состава программных модулей при заданном информационном обеспечении АИС;
• определение оптимального состава системы информационных массивов при заданном программном обеспечении АИС;
• синтез оптимальной функциональной модульной блок-схемы обработки данных.

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

6. Формализована и решена задача синтеза блок-схемы модульных АИС, функционирующих в справочном режиме по критерию минимума общего времени обмена с внешней памятью. В процессе решения определяется оптимальный состав программных модулей и информационных массивов, а также последовательность выполнения процедур обработки данных. Данная задача решается с использованием метода локальной оптимизации и алгоритмов решения частных задач синтеза.
7. Поставлены и решены задачи синтеза программных модулей при заданном информационном обеспечении АИС по критерию минимума общего времени обмена с внешней памятью и по критерию минимума общего числа обращений к внешней памяти ЭВМ. Данные задачи решены с использованием метода последовательного построения, анализа и отбора вариантов. Сокращение числа рассматриваемых вариантов решения достигается применением утверждения, основанного на использовании свойств и особенностей, модульных АИС рассматриваемого типа.
8. Поставлена и решена задача оптимального выбора состава информационных массивов по критерию минимума общего времени обмена между внешней и оперативной памятью ЭВМ при заданном составе программных модулей. Решение данной задачи состоит в определении оптимальной последовательности выполнения процедур в программных модулях по критерию минимума числа обращений к внешней памяти и последующем выборе состава информационных массивов. Для решения данной задачи разработан комбинаторный алгоритм, основанный на методах последовательного построения, анализа и отбора вариантов решений и наименьшего разбиения.
9. Полученные в работе модели и методы использовались при разработке АИС «ИНИОН АН РФ».

Основные положения диссертации отражены в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Ищенко М.А. Задача синтеза структуры автоматизированных информационных систем // Инженерная физика. №5; 2009. 0,6 п.л.
2. Ищенко М.А. Постановка и решение задачи синтеза структуры оптимальных модульных автоматизированных информационных систем по критерию максимума информационной производительности // Приборы и Системы. Управление, Контроль, Диагностика. №5; 2009. 0,7 п.л.

Статьи и материалы конференций

3. Ищенко М.А. Синтез оптимальных модульных структур информационно-управляющих систем. Труды XIV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2006. 0,1 п.л.
4. Ищенко М.А. Применение сетей Петри для решения задач анализа и синтеза ИУС. Труды XV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2007. 0,1 п.л.
5. Ищенко М.А. Этапы эволюции индустрии разработки ИУС. Труды XV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2007. 0,1 п.л.
6. Ищенко М.А. Моделирование систем обработки данных с использованием сетей Петри. Сборник докладов международной научной конференции: Проблемы регионального и муниципального управления. Москва, 2009. 0,2 п.л.