|
данного метода трудоемкость решения задачи характеризуется полиномом второй степени относительно числа дуг GERT-сети. В рамках многокомпонентной модели GERT-сеть может использоваться не только для определения нормативных времен исполнения отдельных операций и процессов в целом, но и как составная часть системы имитационного моделирования, выполняющая функции блоков, задающих временные задержки. Таким образом, GERT-компоненты модели могут отображать вероятностное поведение процессов в организационнотехнологических и производственных системах или тех системных компонентов, которые еще не разработаны. Выводы Рассмотрены основные модели и алгоритмы формирования детерминированных наборов задач распределенных производственных процессов. Предполагалось, что графы процессов являются ацикличными, без ответвлений и что времена выполнения операций точно известны. Во многих случаях эти предположения могут нарушаться, однако, ранее систематически не рассматривались реализации циклов и ветвей в графах в рамках общей модели. Показано, что эффективные оптимальные алгоритмы могут существовать только в некоторых частных случаях, представляется перспективным исследование эвристических методов. Таким образом, задачу построения детерминированных сетевых моделей для формирования распределенных производственных процессов можно считать выполненной. Рассмотрен подход к минимизации затрат и времени при формировании распределенных алгоритмов обработки информации и управления с учетом стохастической реализации процесса па базе простой ациклической детерминированной модели, имеющей "GERT-подобную узловую логику". Показано, что полученные оптимизационные задачи могут 98 |
завершения. Пример графа, удовлетворяющего этим требованиям, показан на рис. 2.23. На этом рисунке пара чисел вида A/В рядом с узлом обозначает задачу, чье время начала выполнения равно А и которая должна быть выполнена за В единиц времени после начала выполнения. Рис. 2.23. Граф с многочисленными временными ограничениями Эвристическое решение этой задачи является разновидностью планов с наидлиннейшим путем, рассмотренных ранее. Однако в этом случае большое число наидлиннейших путей может быть определено для задач с пределами. Фактически процедура является вариацией разбиения по последнему предшествованию для случая с неравными временами задач и множественными пределами. Итак, в данном параграфе рассмотрены некоторые из наиболее важных моделей и алгоритмов формирования детерминированных наборов задач распределенных алгоритмов в информационно-управляющих системах (ИУС включают как подклассы, например, АСУ, КСУП и т.д.). Предполагалось, что графы задач являются ацикличными, без ответвлений и что времена выполнения задач точно известны. Тем не менее, следует упомянуть, что во многих компьютерных системах эти предположения могут нарушаться, однако, ранее систематически не рассматривались реализации циклов и ветвей в графах в рамках общей модели. Приведенные результаты показали, что эффективные оптимальные алгоритмы могут существовать только в некоторых частных случаях, и предполагают возможность активного исследования эвристических методов. 76 В заключение отметим, что, для решения моделей GERT-анализа требуются сложные и трудоемкие вычисления, для организации которых следует использовать специально разработанные программные комплексы GERT-процедур в рамках интерактивной системы формирования алгоритмов распределенной обработки и управления в автоматизированных ОТС. Росту функциональных возможностей системы GERT способствует применение моделей в несколько сотен или более дуг (или узлов). Однако при использовании топологического уравнения Мейсона канонического вида с увеличением размерности сети экспоненциально возрастает число петель г-х порядков, г=1,...,п [85]. Для определения плотности распределения вероятностей GERT-сети используется модификация численного метода нахождения закона распределения выходной величины GERT-сети, рассматриваемого в [65]. Для данного метода трудоемкость решения задачи характеризуется полиномом второй степени относительно числа дуг GERTсети. В рамках многокомпонентной модели GERT-сеть может использоваться не только для определения нормативных времен исполнения алгоритмов распределенной обработки и управления, но и как составная часть системы имитационного моделирования, выполняющая функции блоков, задающих временные задержки. Таким образом, GERT-компоненты модели могут отображать вероятностное поведение готовых программноаппаратных частей алгоритмов автоматизированных организационнотехнологических и производственных систем или тех системных компонентов, которые еще не разработаны. 121 В заключение данного параграфа отметим, что нами определены задачи по анализу и тестированию ПО алгоритмов распределенной обработки информации и управления, а также требования к инструментальным средствам их анализа и тестирования. Выводы по разделу 3 1. Рассмотрен подход к минимизации затрат и времени при формировании распределенных алгоритмов обработки информации и управления с учетом стохастической реализации процесса на базе простой ациклической детерминированной модели, имеющей "GERT-подобную узловую логику" и названной сетью для формирования набора алгоритмов. 2. Показано, что поставленные в работе оптимизационные задачи решаются с использованием известных схем метода ветвей и границ и алгоритмов случайного поиска с адаптацией метода изменяющихся вероятностей. 3. GERT-блок многокомпонентной модели может использоваться как для определения нормативных времен исполнения алгоритмов распределенной обработки и управления, так и в качестве компонент системы имитационного моделирования, выполняющих функции блоков, отображающих вероятностное поведение готовых программно-аппаратных частей алгоритмов автоматизированных организационно-технологических и производственных систем или разрабатываемых системных компонент. 4. Разработан способ представления модели программ, реализующих алгоритмы, в виде сетей Петри и предложен набор элементов модели, которые позволяют описывать базовые абстракции и механизмы ПО реализации алгоритмов распределенной обработки и управления. Разработаны способы решения задач анализа и тестирования с использованием моделей программ, реализующих алгоритмы, и моделей распределенного ПО среды реализации алгоритмов обработки информации и управления технологическими и производственными объектами. 141 |