Основные результаты и выводы Рассмотренные формальные модели типичных задач планирования производства являются моделями условной псевдобулевой оптимизации с довольно сложными целевыми функциями и функциями ограничений, имеющими за счет перехода к булевым переменным огромные размерности для реальных задач. Вторым важным недостатком рассмотренного подхода является то, что не учитывается фактор неопределенности и случайности, что существенно понижает адекватность моделей реальным процессам. Рассмотрены основные модели и алгоритмы формирования детерминированных наборов задач распределенных производственных процессов. Предполагалось, что графы процессов являются ацикличными, без ответвлений и что времена выполнения операций точно известны. Во многих случаях эти предположения могут нарушаться, однако, ранее систематически не рассматривались реализации циклов и ветвей в графах в рамках общей модели. Показано, что эффективные оптимальные алгоритмы могут существовать только в некоторых частных случаях, представляется перспективным исследование эвристических методов. Таким образом, задачу построения детерминированных сетевых моделей для формирования распределенных производственных процессов можно считать выполненной. Рассмотрен подход к минимизации затрат и времени при формировании распределенных алгоритмов обработки информации и управления с учетом стохастической реализации процесса на базе простой ациклической детерминированной модели, имеющей "GERT-подобную узловую логику". Показано, что полученные оптимизационные задачи могут быть решены с использованием известных схем метода ветвей и границ и метода изменяющихся вероятностей. GERT-блок многокомпонентной модели может использоваться как для определения нормативных времен исполнения отдельных операций и процессов в целом, так и в качестве компонент системы имитационного 119 |
завершения. Пример графа, удовлетворяющего этим требованиям, показан на рис. 2.23. На этом рисунке пара чисел вида A/В рядом с узлом обозначает задачу, чье время начала выполнения равно А и которая должна быть выполнена за В единиц времени после начала выполнения. Рис. 2.23. Граф с многочисленными временными ограничениями Эвристическое решение этой задачи является разновидностью планов с наидлиннейшим путем, рассмотренных ранее. Однако в этом случае большое число наидлиннейших путей может быть определено для задач с пределами. Фактически процедура является вариацией разбиения по последнему предшествованию для случая с неравными временами задач и множественными пределами. Итак, в данном параграфе рассмотрены некоторые из наиболее важных моделей и алгоритмов формирования детерминированных наборов задач распределенных алгоритмов в информационно-управляющих системах (ИУС включают как подклассы, например, АСУ, КСУП и т.д.). Предполагалось, что графы задач являются ацикличными, без ответвлений и что времена выполнения задач точно известны. Тем не менее, следует упомянуть, что во многих компьютерных системах эти предположения могут нарушаться, однако, ранее систематически не рассматривались реализации циклов и ветвей в графах в рамках общей модели. Приведенные результаты показали, что эффективные оптимальные алгоритмы могут существовать только в некоторых частных случаях, и предполагают возможность активного исследования эвристических методов. 76 3.1.1. GERT-сетевая модель стохастической структуры Далее рассматривается подход к минимизации затрат и времени при формировании распределенных алгоритмов обработки информации и управления с учетом стохастической реализации процесса. В качестве базовой модели рассмотрим простую ациклическую детерминированную модель, которая имеет "GERT-подобную узловую логику" [61]. Такую модель будем называть сетью для формирования (или решения) алгоритма (или набора алгоритмов), подчеркивая этим термином, что план реализации алгоритма выбирается в процессе формирования, т.е. принимается решение о том, какие задачи алгоритма должны быть выполнены для минимизации некоторой целевой функции. Это приводит к задаче комбинаторной оптимизации, частным случаем которой является, например, "decision CMP" метод критического пути для случая, когда присутствуют только GERT-узлы двух типов «AND» n «OR». Для учета вероятностных характеристик реализации алгоритмов ниже вводится понятие случайных акций и рассматривается возможность многоразовой последовательной реализации задач алгоритма [62] до момента его полного успешного завершения. Итак, пусть N ациклическая сетевая модель распределенного алгоритма с источниками и стоками (действия, соответствующие задачам алгоритма, представляются дугами), где множество узлов обозначается V, а множество дуг Е (веса для дуг будут определены далее). Предположим, что N имеет только один исток, который обозначается через г и соответствует началу формируемого алгоритма. Предполагается также, что один из стоков N представляет собой успешное завершение всех задач алгоритма и-, обозначается 5. Оставшиеся: стоки, если они есть, могут представлять собой различные виды неудачного завершения или прерывания алгоритма: Определение (1). Ациклическую сетевую модель N(V,E) только с одним истоком и со стоками назовем сетью для формирования/решения распределенного алгоритма, если каждый узел i из N определен через входную характеристику е O,l,...,P(z) и выходную характеристику 95 В заключение данного параграфа отметим, что нами определены задачи по анализу и тестированию ПО алгоритмов распределенной обработки информации и управления, а также требования к инструментальным средствам их анализа и тестирования. Выводы по разделу 3 1. Рассмотрен подход к минимизации затрат и времени при формировании распределенных алгоритмов обработки информации и управления с учетом стохастической реализации процесса на базе простой ациклической детерминированной модели, имеющей "GERT-подобную узловую логику" и названной сетью для формирования набора алгоритмов. 2. Показано, что поставленные в работе оптимизационные задачи решаются с использованием известных схем метода ветвей и границ и алгоритмов случайного поиска с адаптацией метода изменяющихся вероятностей. 3. GERT-блок многокомпонентной модели может использоваться как для определения нормативных времен исполнения алгоритмов распределенной обработки и управления, так и в качестве компонент системы имитационного моделирования, выполняющих функции блоков, отображающих вероятностное поведение готовых программно-аппаратных частей алгоритмов автоматизированных организационно-технологических и производственных систем или разрабатываемых системных компонент. 4. Разработан способ представления модели программ, реализующих алгоритмы, в виде сетей Петри и предложен набор элементов модели, которые позволяют описывать базовые абстракции и механизмы ПО реализации алгоритмов распределенной обработки и управления. Разработаны способы решения задач анализа и тестирования с использованием моделей программ, реализующих алгоритмы, и моделей распределенного ПО среды реализации алгоритмов обработки информации и управления технологическими и производственными объектами. 141 |