Содержание к диссертации
ВВЕДОНИЕ 5
ГЛАВА I. ИСПОЛЬЗОВАНИЕ МАТРИЧНЫХ И ГРАФОВЫХ МОДЕЖЙ
ДЛЯ ОПИСАНИЯ И АНАЛИЗА ТЕХНОЛОГИИ РЕШЕНИЯ
ЗАДАЧ ОБРАБОТКИ ДАННЫХ ПРИ РАЗРАБОТКЕ ТИПО
ВЫХ МОДУЛЬНЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ (СОД) .. 16
I.I. Формализация представления исходной инфор
мации и процедур ее обработки для анализа
технологии решения задач обработки данных
при разработке типовых модульных СОД 17
1.2. Процедуры формирования полного структури
рованного графа технологии задач обработки
данных '. 27
1.3. Использование процедур формализации и
структуризации для формирования полного графа технологии решения задачи приходования грузов на складах и формирования приемных актов, решаемой на Московском Метрополитене . ^6
КРАТКИЕ ВЫВОДЫ 46
ГЛАВА П. ФОРМАЛИЗОВАННЫЕ МЕТОДЫ АНАЛИЗА МНОЖЕСТВА ЗАДАЧ ОБРАБОТКИ ДАННЫХ ЗАДАННОГО КЛАССА ПРИ ПРОЕКТИРОВАНИИ ТИПОВЫХ МОДУЛЬНЫХ СОД . . . 48 " 2.Ї. Формализация процедур выделения типовых и специфичных частей технологических структур
для множества задач обработки данных 50
2.2. Процедуры и алгоритм выделения типовых и
специфичных частей заданного множества
задач обработки данных 56
2.3. Формализованные процедуры формирования интегри
рованного графа технологии для заданного мно
жества задач обработки данных 69
2.4. Использование методов и процедур формализации
для формирования интегрированного графа техно
логии решения множества задач обработки данных
приходования грузов на складах и формирования
приемных актов в АСУ МТС "Метро" 77
КРАТКИЕ ВЫВОДЫ 85
ГЛАВА Ш. ЗАДАЧИ СИНТЕЗА ТИПОВЫХ МОДУЛЬНЫХ СОД 87
. 3.1. Задачи синтеза типовых модульных СОД с использованием общесистемных критериев проектирования.. 83 3.2. Задачи синтеза состава типовых модулей программного обеспечения СОД при заданном информационном
обеспечении 96
3.3. Задачи синтеза типовых модульных СОД с исполь
зованием минимаксных критериев проектирования . . ЮЗ
КРАТКИЕ ВЫВОДЫ 105
ГЛАВА ІУ. МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ СИНТЕЗА
ТИПОВЫХ МОДУЛЬНЫХ СОД 107
4.1. Методы вычисления оценок и алгоритмы решения
задач синтеза типовых модульных СОД, основанные
на схеме "ветвей и границ" 108
4.2. Эвристические методы и алгоритмы решения задач
синтеза типовых модульных СОД 131
4.3. Синтез оптимальной типовой модульной СОД для решения задач приходования грузов на складах и формирования приемных актов в АСУ МТС "Метро".. 142
КРАТКИЕ ВЫВОДЫ 148
ЗАКЛЮЧЕНИЕ 151
ЛИТЕРАТУРА 153
ПРИЛОЖЕНИЕ 163
- 5 ~
Введение к работе
Актуальность темы. Повышение качества и эффективности систем управления, сокращение сроков и затрат на их внедрение определены как важные народно-хозяйственные задачи.
Повышение эффективности создаваемых систем связано с использованием при разработке их программного и информационного обеспечения моделей и методов синтеза типовых модульных систем обработки данных ССОД),
Основные преимущества разработки АСУ с использованием типовых модулей состоят в следующем;
~ уменьшаются общие затраты и время на разработку и внедрение АСУ за счет использования готовых проектных решений и модулей;
повышается научный потенциал и квалификация разработчиков за счет сравнительного анализа и обобщения большего числа систем и проектов АСУ;
легче внедряются передовые методы разработки и автоматизации проектирования;
значительно облегчается эксплуатация АСУ, подготовка персонала и его взаимозаменяемость.
По отечественным и зарубежным данным затраты на разработку и внедрение модульных АСУ сокращаются в среднем на 20%, а затраты и время на разработку типовых модульных АСУ уменьшаются в еще большей степени по сравнению с традиционным индивидуальным проектированием при одновременном повышении качества функционирования систем(71 ],
Возможности типизации модульных СОД основаны на разработке и использовании ограниченного множества типовых модулей алгоритмического, программного и информационного обеспечения дяя реше-
ния задач АСУ выбранного класса объектов с учетом их индивидуальных особенностей. Решение задач типизации должно предваряться анализом и классификацией состава и содержания функциональных задач АСУ, формулировкой требований к их реализации.
Большие масштабы работ по созданию и внедрению АСУ в различных областях народного хозяйства, необходимость решения большого числа однотипных задач, и в то же вреия отсутствие теоретических основ, моделей и методов формализации разработки типовых модульных систем обработки данных для множества задач некоторой проблемной области обуславливают актуальность выполненных научных исследований.
Цель работы. Целью работы является разработка формализованных методов и моделей анализа множества задач обработки данных и синтеза типовых модульных систем.
Научная новизна. На основании проведенных исследований и обобщения опыта создания модульных СОД разработан общий методологический подход, формализованные методы и модели синтеза оптимальных типовых модульных систем обработки данных для заданного множества задач одного класса.
На основе единой методологии разработаны методы формализации, постановки задач, модели, алгоритмы и программы анализа и синтеза оптимальных типовых модульных АСУ, обеспечивающие: формализацию описания и анализа технологии решения задач обработки данных; выделение типовых частей заданного множества задач или его подмножеств, а также специфичных частей каждой задачи и параметров настройки; получение интегрированного графа технологии решения заданного множества задач обработки данных; синтез оптимальной типовой модульной системы обработки данных по общесистемным критериям проектирования: минимум общего времени обмена между оперативной и внешней памятью для множества задач обра-
ботки данных, минимум суммарного числа обращений к внешней памяти при решении заданного множества задач, минимум суммарного числа межмодульных информационных связей для заданного множества задач; синтез типовых модульных СОД с использованием минимаксных критериев проектирования; синтез состава типовых модулей программного обеспечения СОД при заданном информационном обеспечении.
Приведенные в диссертации модели, методы и алгоритмы синтеза типовых оптимальных модульных СОД впервые разработаны и опубликованы автором и по сравнению с традиционными методами проектирования, ориентированными, в основном, на использование опыта разработчиков, позволяют формализовать, алгоритмизировать и в значительной мере автоматизировать процесс проектирования для заданного множества задач оптимального состава типовых модулей программного и информационного обеспечения АСУ, что существенно снижает затраты на его разработку и повышает качество принимаемых проектных решений.
Практическая ценность» Разработанные методы формализации и постановки задач обеспечивают анализ и синтез оптимальной по заданному критерию системы типовых программных модулей и информационных массивов для заданного класса задач обработки данных. Использование разработанного комплекса методов, алгоритмов и программ проектирования типовых модульных СОД позволяет сократить общее время разработки программного и информационного обеспечения АСУ на 25-30 и повысить качество типовых проектных решений. Разработанные алгоритмы реализованы на языке Фортран, входящем в состав математического обеспечения ЕС ЭВМ и других отечественных ЭВМ, и могут быть использованы при разработке программного и информационного обеспечения отраслевых автоматизированных систем управления различного класса и назначения, автоматизированных систем управления и информационных систем в производственных и
научно-производственных объединениях, научно-исследовательских, проектных и конструкторских организациях, а также в вычислительных центрах, разрабатывающих, внедряющих и эксплуатирующих системы обработки данных на ЭВМ и методы их автоматизированного проектирования.
Внедрение. Эффективность разработанных в диссертационной работе моделей и методов анализа и синтеза типовых модульных СОД подтверждена их практическим использованием.
При непосредственном участии автора они внедрены при разработке типовой автоматизированной системы управления метрополитенами страны (АСУ "Метро"), ряда типовых подсистем в ОАСУ "Пром-стройматериалы" Министерства промышленности Арм. ССР и в ОАСУ "Торговля" Министерства торговли Арм. ССР.
Использование разработанных методов, алгоритмов и программ позволило за счет выбора оптимального состава типовых модулей программного обеспечения получить экономический эффект около 50 тыс. рублей в год.
Содержание работы. Полученные в диссертационной работе научные результаты распределяются по главам следующим образом.
Во введении обосновывается выбор цели и проблем, рассматриваемых в диссертации, приводятся основные положения, которые выносятся на защиту, подчеркивается, что широкое внедрение АСУ в различных областях народного хозяйства требует разработки формализованных методов синтеза типовых модульных АСУ, позволяющих определять состав и интерфейс типовых модулей программного и информационного обеспечения»
Проблемы синтеза оптимальных типовых модульных СОД весьма разнообразны, в большинстве своем не формализованы и в настоящее время интенсивно разрабатываются многими исследователями [і--''І,9ь]
При разработке АСУ существуют различные направления типизации. Н таким направлениям относится типизация организационного, алгоритмического, программного, информационного, технического и других видов обеспечения АСУ.
Каждое из направлений типизации может быть осуществлено на различных структурных уровнях:
на уровне системы или проекта в целом;
на уровне отдельных функциональных подсистем АСУ;
на уровне задач обработки данных и управления;
- на уровне совокупностей процедур и информационных элементов.
К числу важнейших требований, которые должны выполняться при выработке типовых проектных решений по всем направлениям и на всех уровнях типизации! относятся следующие;
разработка типовых проектных решений должна проводиться на основе анализа и оценки степени общности требований и характеристик объектов автоматизации;
требования и характеристики объектов автоматизации должны быть унифицированы и представлены в стандартной, однозначно понимаемой форме;
типовые проектные решения должны формироваться в строгом соответствии со стандартами и ГОСТами на алгоритмическое, программное и информационное обеспечение АСУ;
формирование типовых проектных решений при проектировании АСУ должно базироваться на разработке многофункциональных типовых модулей программного и информационного обеспечения.
6 диссертационной работе основное внимание уделено следующим этапам разработки типовых модульных СОД: этапу анализа и этапу технического проектирования оптимальных типовых модулей программного и информационного обеспечения. Предложенный в диссерта-
- 10 -ции подход к формализации и автоматизации этих этапов базируется на формализованных процедурах описания и анализа задач АСУ, их программного и информационного обеспечения, позволяющих получить информацию, необходимую для сравнения рассматриваемых алгоритмов задач обработки данных с целью выделения общих и специфичных частей, построения интегрированного графа технологии и синтеза на этой основе системы типовых программных и информационных модулей, обеспечивающих решение заданного множества задач
В основу предложенного подхода положен модульный принцип проектирования АСУ, который связан с процессом разбиения системы на отдельные слабо связанные компоненты (модули), допускающие их относительно независимую разработку и использование. Использование принципа модульности при проектировании информационного и программного обеспечения АСУ позволяет свести проектирование к синтезу функционально независимых отдельных частей (модулей), совместно выполняющих заданные функции системы с требуемой эффективностью.
Сформулированные в диссертации проблемы и задачи анализа и синтеза типовых оптимальных модульных АСУ рассматриваются в последующих главах работы.
В главе I рассматриваются типовые модели описания и анализа алгоритмов решения задач обработки данных в АСУ, позволяющие формализовать получение требуемой информации, необходимой для сравнения различных задач одного класса с целью выделения в них типовых и специфичных частей и элементов, используемых при синтезе типовых модулей программного и информационного обеспечения АСУ.
В качестве моделей описания и анализа задач и алгоритмов обработки данных использована совокупность графовых и матричных
- II -
моделей, которые получили наибольшее развитие и использование при решении практических задач анализа благодаря удобному представлению порядка и вида отношений между элементами системы. Методика анализа и структуризации исходной для синтеза системы ти-новых модулей информации базируется на последовательном эквивалентном преобразовании матричных и графовых моделей алгоритмов решения задач обработки данных, содержащих всю необходимую информацию о взаимосвязях и отношениях между различными элементами отдельных задач.
Предлагаемая совокупность моделей ориентирована на автоматизированный анализ задач обработки данных, получение дополнительной информации о структуре задач и корректировку исходной информации в режиме диалога проектировщика с ЭВМ* Данная совокупность обеспечивает структуризацию и подготовку всей необходимой информации для последующего сравнения элементов и динамических характеристик множества задач обработки данных заданного класса.
В главе 2 рассматриваются формализованные методы и модели анализа технологии решения заданного множества задач обработки данных, имеющие целью выделение общих или типовых частей данного множества задач или его подмножеств, специфичных частей каждой задачи, а также построение единого интегированного графа технологии, обеспечивающего решение анализируемых задач.
Исходными данными для анализа и выделения типовых и специфичных частей множества задач обработки данных заданного класса являются полученные на предыдущих этапах анализа каждой задачи множества процедур обработки данных, информационных элементов и их областей определения, структурированный граф технологии, структурированные матрицы смежности и достижимости технологии обработки данных отдельных задач. Введение различных классов эк-
вивалентности анализируемых задач позволяет осуществлять сравнение алгоритмов их решения на заданном уровне абстракции. Рассмотрены постановка и алгоритмы решения задачи сравнения технологических структур заданных алгоритмов обработки данных и выделения совпадающих и специфичных частей без учета имеющихся различий в константах и областях определения информационных элементов.
Результаты решения задачи сравнения алгоритмов использованы для построения общего интегрированного графа технологии множества задач обработки данных. В главе приведены примеры использования разработанных методов и алгоритмов для формирования общего интегрированного графа обработки данных для задач приходования грузов на складах и формирования приемных актов, решаемых в АСУ МТС "Метро".
В третьей главе рассматриваются постановки задач синтеза программного и информационного обеспечения оптимальных типовых мо-дульных СОД. Использование принципа модульности при проектировании типовых модульных СОД позволяет свести проектирование к синтезу функционально независимых типовых и специфичных модулей, обеспечивающих решение заданного множества задач выбранного класса с требуемой эффективностью.
Исходными данными для постановки задач синтеза системы типовых модулей являются: общий интегрированный граф технологии обработки данных заданного множества задач, структурированная матрица смежности технологии обработки данных множества задач, типовые и специфичные подграфы, множество информационных элементов и процедур, входящих в состав типовых и специфичных подграфов, последовательности выполнения процедур общего интегрированного графа технологии обработки данных в процессе решения каждой задачи, входные и выходные элементы типовых и специфичных частей.
В работе рассмотрены два класса критериев синтеза типовых модулей программного и информационного обеспечения АСУ: общесис-
- ІЗ -
темные и минимаксные.
Первые определяются с помощью суммарных показателей качества синтеза для множества задач обработки данных, вторые - с помощью показателей гарантированного качества синтеза для отдельных задач обработки данных, входящих в рассматриваемое множество. Б качестве общесистемных критериев рассматриваются: минимум общего времени обмена между оперативной и внешней памятью, минимум суммарного числа обращений к программным модулям и информационным массивам, минимум суммарного числа межмодульных информационных связей, минимум общего времени обмена системы типовых модулей с внешней памятью, минимум общего числа неиспользуемых процедур при обращении к программным модулям, минимум общего числа обращений к программным модулям при решении заданного множества задач.
В качестве минимаксных критериев используются минимум на множестве задач обработки данных максимальных значений перечисленных выше показателей, обеспечивающих гарантированный уровень качества проектных решений для каждой из задач обработки данных.
6 качестве ограничений при решении задач синтеза оптимальных типовых модульных СОД используются, кроме вышеперечисленных показателей, такие характеристики, как состав процедур и объем каждого модуля, состав и объем информационных массивов, сложность и состав интерфейса между отдельными модулями, степень дублирования процедур и информационных элементов в СОД, объем оперативной памяти ЭВМ, возможности передачи управления внутри и между модулями и т.д.
Решение поставленных задач синтеза позволяет по заданным критериям эффективности с учетом имеющихся ресурсных и технологических ограничений определять оптимальный состав типовых модулей программного и информационного обеспечения, обеспечивающих требования заданного множества задач обработки данных.
Доставленные в работе задачи синтеза типовых модульных СОД
являются нелинейными задачами целочисленного программирования большой размерности.
В четвертой главе диссертации рассматриваются методы и алгоритмы решения синтеза типовых модульных СОД. Учет особенностей поставленных задач позволил разработать эффективные алгоритмы их решения, основанные на схеме "ветвей и границ". Использование свойств модульных СОД и введенных формальных понятий позволило получить аналитические выражения для оценки множеств решений в разработанных комбинаторных алгоритмах. Кроме того, для ряда практически важных случаев разработан эвристический алгоритм, позволяющий получать достаточно эффективные приближенные решения поставленных задач синтеза. Б работе приведены примеры использования разработанных моделей, методов и алгоритмов для синтеза оптимальной типовой модульной СОД для решения задач приходования грузов на складах и формирования приемных актов в АСУ МТС "Метро".
В приложении к диссертации приведены блок-схемы разработанных программ анализа технологии решения множества задач обработки данных и синтеза типовых модульных СОД, а также материалы, подтверждающие практическое использование полученных автором научных результатов.
Апробация работы. Основные результаты диссертационной работы обсуждались и докладывались автором на Конференции молодых ученых и специалистов Института проблем управления (Москва, 1980), на Всесоюзном семинаре по методам синтеза типовых модульных систем обработки данных (Звенигород, 1981) и других семинарах и совещаниях.
Публикации. Диссертационная работа выполнена в соответствии с планом научных исследований по естественным и общественным наукам АН СССР на 1981-1985 годы - проблема Z.I2 "Проблемы вычисли-
тельной техники, управления и кибернетики" и планом назгчных работ Института проблем управления - тема 12-79 (номер государственной регистрации 79062179) "Синтез оптимальных модульных и типовых модульных автоматизированных информационно-управляющих систем (научный руководитель темы - академик Трапезников 6.А.) и изложена в пяти научных работах.
Объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, приложения и включает 125 страниц машинописного текста, 25 рисунков и 25 таблиц.
