Разработка моделей и методов синтеза модульной структуры автоматизированных информационных систем с использованием сетей Петри тема диссертации и автореферата по ВАК РФ 05.25.05, кандидат технических наук Ищенко, Михаил Алексеевич

• Ищенко, Михаил Алексеевич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Ищенко, Михаил Алексеевич

Введение.

Глава 1. Задачи анализа и синтеза автоматизированных информационных систем.

1.1. Технология проектирования автоматизированных информационных систем.

1.2. Формализованное описание сетей Петри. Основные понятия и определения.

1.3. Содержательная постановка задач анализа и синтеза автоматизированных информационных систем.

Краткие выводы.

Глава 2. Моделирование и анализ процессов проектирования и функционирования автоматизированных информационных систем.

2.1. Использование сетей Петри для моделирования процессов в АИС.

2.2. Характеристики обобщенных сетей Петри.

2.3. Моделирование и анализ автоматизированных информационных систем с использованием сетей Петри.

Краткие выводы.

Глава 3. Синтез оптимальных модульных АИС по критерию максимума информационной производительности.

3.1. Определение информационной производительности автоматизированных информационных систем.

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

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

3.4. Синтез оптимальной системы обработки данных для подсистем АИС «ИНИОН АН РФ».

Краткие выводы.

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

4.1. Синтез оптимального состава модулей программного обеспечения АИС.

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

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

Краткие выводы.

Введение диссертации (часть автореферата) на тему «Разработка моделей и методов синтеза модульной структуры автоматизированных информационных систем с использованием сетей Петри»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Информационные системы и процессы, правовые аспекты информатики», Ищенко, Михаил Алексеевич

Заключение

В диссертационной работе получены следующие основные результаты:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Ищенко, Михаил Алексеевич, 2009 год

1. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ.— М.: Мир, 984.— 264 с.

2. А.А. Лескин П.А. Мальцев A.M. Спиридонов. Сети Петри в моделировании и управлении. Наука, 1989, 133 с.

3. Бодянский Е.В., Кучеренко Е.И., Михалев А.И. Нейро-фаззи сети Петри в задачах моделирования сложных систем Монография (научное издание). Дншропетровськ: Системш технологи, 2005 г. 311 с.

4. Кельтон С., Лоу Дж. Имитацинное моделирование. Computer Science. СПб.: Питер, 2004

5. Котов В.Е. Сети Петри. М.: Наука 1984.

6. Ломазова И.А. Моделирование мультиагентных динамических систем вложенными сетями Петри. М.: Наука. Физматлит, 1999.

7. Воевода А.А., Саркенов Д.О. Сети Петри: симметричные графы состояний // Сб. науч. тр. НГТУ. 2005. - №3 (41). - С. 133-137.

8. Girault, С., Valk, R. Petri Nets for Systems Engineering: a Guide to Modeling, Verification, and Applications, Springer-Verlag, 2002. 607 p

9. Ищенко M.A. Задача синтеза структуры автоматизированных информационных систем // Инженерная физика. №5; 2009.

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

11. Ищенко М.А. Синтез оптимальных модульных структур информационно-управляющих систем. Труды XIV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2006.

12. Ищенко М.А. Применение сетей Петри для решения задач анализа и синтеза ИУС. Труды XV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2007.

13. Ищенко М.А. Этапы эволюции индустрии разработки ИУС. Труды XV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2007.

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

15. В.А. Башкин, И.А. Ломазова «Эквивалентность ресурсов в сетях Петри». М., Мир, 2008

16. Ломазова И.А. «Вложенные сети Петри: моделирование и анализ распределительных систем с объектной структурой.» М., мир 2004

17. Башин Ю.А., Митянов В.П. Моделирование SlMD-систем с использованием теории сетей Петри для оценки времени выполнения задачи с условием синхронной работы комплекса. — М.: ИПУ. — 2004. 39 с

18. Кулагин В.П. Анализ параллельных процессов на основе сетевых моделей: Учеб. Пособие. Пенза: ИЛИ. 1991

19. Чурина Т.Г. Способ построения раскрашенных сетей Петри, моделирующих SDL системы. - Новосибирск. - 1998. - 56 с.

20. Taubner D.A. The finite representation of abstract programs by automata and Petri nets: Diss. Dokt. Naturwiss. Univ. Munchen. Munchen. - 1988.

21. B.B. Кульба, Д.А. Миронов, Е.Б. Соколова. Отладка систем защиты с использованием сетей Петри. Препр. — М.: ИПУ. 1990. 49 с.

22. Вагнер Г. Основы исследования операций, т. 2, М.: Мир. - 443 с.

23. Котов В.Е. Алгебра регулярных сетей Петри. Новосибирск. 1978. - 38 с. - (Препринт / ВЦ СО АН СССР ; 98).

24. Кристофидес Н. Теория графов. М.: Мир, 1978. - 432 с.

25. Кульба В.В., Мамиконов А.Г. Методы анализа и синтеза оптимальных модульных систем обработки данных (обзор). Автоматика и телемеханика, 1980, № II с. 152-179.

26. Липаев В.В. Распределение ресурсов в вычислительных системах. М.: Статистика. 1979. - 247 с

27. Мамиконов А.Г., Кульба В.В., Цвиркун А.Д. Автоматизация проектирования АСУ. — М.: Энергия. 1980. 328 с.

28. Хьюз Дж., Мичтон Дж. Структурный подход к программированию. М.: Мир, 1980.-278 с.

29. Boehm В. Soft engineering. IEEE Transactions on computers. December 1976, vol. c-25, #12, p. 1226-1241.

30. Devis A.L. The architecture and system method of DDM 1: a recursively structured data driven machine. SIGARCH NEWSLETTER, 1978, 6, #7, p. 210-215

31. Dijkstra E.W. The impact of microprocessors. GMD - Spiegel, 1977, v. 7, #4, p.8-11, 2.

32. Dolota T.A. Data processing in 1980-1985. Wiley-Interscience, N.Y., 1976.

33. Hach M. Analysis for Production Schemata by Petry Nets. Computer Structure Group. TR-94, Project MAC, M.I.T., February 1972 - 119 p.

34. Hamilton M., Zeldin S. Higher order software a methodology for defining software, IEEE Trans. Software Eng., Mar., 1976, p. 9-32

35. Langefors В., Sundgren B. Information system architecture. New York, Petrocelli / Charter, 1975

36. Martin W., Bosyj M. Requirement derivation in automatic programming in Proc. MPT Sump. Comput. Software Eng., Apr., 1976

37. Mc Gowan C.L., Kelly I.R. Top-Down Programming Techniques. New York, Petrocelli / Charter, 1975

38. Mills N.D. Mathematical found action for structured programming, IBM-ESD : rep. ES., p.72-6012, Feb 1972

39. Parnas D.L. The influence of software structure on reliability. Proc. Int. Conf. Reliable software, Apr. 1975, p.358-362.

40. Parnas D.L. On the criteria to be used in decomposing system into modules. GAGM, Dec. 1972, p. 1053-1058.

41. Peterson I.L. Petri-Nets. ACM Computing Surveys, v. 9, 3, September, 1977, p. 223-252

42. Petry C.A. Komminication mit Automater. Univ. Bonn, 1962

43. Riemann, Robert-Christoph (1999). Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus. Herbert Utz Verlag.

44. Storrle, Harald (2000). Models of Software Architecture Design and Analysis with UML and Petri-Nets. Books on Demand

45. Zhou, Mengchu; Frank Dicesare (1993). Petri Net Synthesis for Discrete Event Control of Manufacturing Systems. Kluwer Academic Publishers.

46. Zhou, Mengchu; Kurapati Venkatesh (1998). Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach. World Scientific Publishing.

47. Desel, Jorg and Juhas, Gabriel " What Is a Petri Net? Informal Answers for the Informed ReaderHartmut Ehrig et al. (Eds.): Unifying Petri Nets, LNCS 2128, pp. 1-25, 2001.

48. AS) Decidability issues for Petri nets a survey, by Javier Esparza and Mogens Nielsen, in: Bulletin of the EATCS, 1994. Revised, 1995.

49. P. Kiingas. Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies. In: Proceedings of the 6th International Symposium on Abstraction, Reformulation and Approximation, SARA 2005, Airth Castle, Scotland, UK, July 26-29, 2005.

50. Petri Nets: Properties, Analysis and Applications, by Tadao Murata, in: Proceedings of the IEEE, vol. 77, no. 4, April 1989

51. T. Araki and T. Kasami, Some Decision Problems Related to the Reachability Problem for Petri Nets, in: Theoretical Computer Science, 3(1), pp. 85-104 (1977)

52. Dawis, E. P., J. F. Dawis, Wei-Pin Koo (2001). Architecture of Computer-based Systems using Dualistic Petri Nets. Systems, Man, and Cybernetics,2001 IEEE International Conference on Volume 3, 2001 Page(s):1554 1558 vol.3

53. Jensen, Kurt (1997). Coloured Petri Nets. Springer Verlag.

54. Reisig, Wolfgang (1992). A Primer in Petri Net Design. Springer-Verlag.

55. Кузнецов H.A., Кульба B.B., Ковалевский С.С., Косяченко С.А. Методы анализа и синтеза модульных информационно-управляющих систем. — М.: ФИЗМАТЛИТ, 2002. 800 с.

56. Марка Д., Мак-Гоуэн К. Методология структурного анализа и проектирования. — М.: МетаТехнология, 1993.

57. Роберте Ф.С. Дискретные математические модели с приложением к социальным, биологическим и экономическим задачам. М.: Наука, 1986

58. Саати Т. Принятие решений. Метод анализа иерархий. М.: Радио и связь. 1993.

59. Таль А.А., Юдицкий С.А. Иерархия и параллелизм в сетях Петри // Автоматика и телемеханика. 1982. — №7, 9

60. Трахтенгерц Э.А. Субъективность в компьютерной поддержке управленческих решений. М.: СИНТЕГ, 2001

61. Юдицкий С.А. Сценарно-целевой подход к системному анализу // Автоматика и телемеханика. — 2001. №4

62. Юдицкий С.А. Сценарный подход к моделированию поведения бизнес-систем. СИНТЕГ, 2001

63. Юдицкий С.А., Владиславлев П.Н. Предпроектное моделирование функционирования организационных систем. М.: Научтехлитиздат, 2004

64. Юдицкий С.А., Радченко Е.Г. Моделирование движения потоков при предпроектном анализе сложных систем // Приборы и системы: Управление, контроль, диагностика. 2003. - №9.

65. Юдицкий С.А., Радченко Е.Г. Построение потоковых моделей многоагентных иерархических систем // Приборы и системы: Управление, контроль, диагностика. 2004. - №2.

66. Юдицкий С.А., Магергут В.З. Логическое управление дискретными процессами. -М.: Машиностроение, 1987.

67. Кононов Д.А., Кульба В.В., Ковалевский С.С., Косяченко С.А. Синтез формализованных сценариев и структурная устойчивость сложных систем (синергетика и аттрактивное поведение) / Институт проблем управления. Препринт - М., 1998

68. Кононов Д.А., Кульба В.В., Ковалевский С.С., Косяченко С.А. Формирование сценарных пространств и анализ динамики поведения социально-экономических систем / Институт проблем управления. -Препринт-М., 1999

69. Кульба В.В., Кононов Д.А., Ковалевский С.С., Косяченко С.А., Нижегородцев P.M., Чернов И.В. Сценарный анализ динамики поведения социально-экономических систем. М.: 2002 (Научное издание / Институт проблем управления им. В.А. Трапезникова РАН).