АЛГОРИТМИЗАЦИЯ ДЕТЕРМИНИРОВАННЫХ МОДЕЛЕЙ ТЕХНОЛОГИЧЕСКИХ ЦИКЛОВ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

Полный текст

Введение. Существующая аналитико-оптимизационная процедура, реализуемая в рамках детерминированной модели [1], направлена на решение задачи минимизации (сокращения) времени информационного взаимодействия структурных компонентов сети (информационной карты) [2] путем выявления и сокращения холостых временных «окон» [3]. Также в рамках данной процедуры существует возможность оценить полное время реализации технологического цикла управления (ТЦУ) в рамках границ информационной карты [4]. Однако не менее критичным с точки зрения управления становится задача определения временных затрат маршрута управления [5; 6] на том или ином участке информационной карты, поскольку полное время реализации ТЦУ не позволяет делать вывод о том, где, а также за счет чего достигнуто сокращение холостых временных «окон» [7]. С целью реализации подобной возможности в работе рассматривается применение алгоритма Дейкстры как одного из методов сетевого анализа [8] в решении задачи определения кратчайшего временного пути графа ТЦУ. Обоснование возможности применения данного алгоритма в следующем: современные автоматизированные системы управления (АСУ) можно рассматривать как систему сетей, предназначенных для транспортирования (передачи) и распределения потоков, в том числе энергетических и информационных [9]. Поскольку каждая из подсистем АСУ имеет весьма сложную структуру, возникает необходимость в эффективном использовании уже существующих технических средств и в рациональном проектировании новых [10]. При проектировании и усовершенствовании больших и сложных систем, а также при поиске путей их наиболее рационального использования существенное значение могут иметь методы сетевого анализа [11]. Вводимый термин «временной путь» tp интерпретирован как отрезок времени между заданным исходным узлом и любым другим узлом сети (графа ТЦУ), определяемый компонентами вектора временной развертки (ВВР) и исчисляемый условными единицами времени (у.е.в.). Аналитико-оптимизационная процедура. Рассмотрим подробно модели и методы анализа и оптимизации процессов в АСУ, которые используются в рамках заявленной выше процедуры и направлены на получение аналитических характеристик процессов управления АСУ [12; 13]. Анализ реализуемости детерминированных моделей. Поскольку описание ТЦУ не зависит от типа комплекса управления, имеется начальное значение ВВР для графа ТЦУ G где ti соответствует времени задействования компонента структуры вычислительной системы (ВС) для решения задачи, находящейся в i-й вершине графа G. ВВР полностью определяет информационное взаимодействие между структурными компонентами сети [14]. Граф ТЦУ G, построенный на этой структуре, описывается матрицей инцидентности A = a[i,j]. Это прямоугольная матрица размерности n×m, где Также используется вектор реализации (ВР) где hj является временем выполнения задачи обработки информации и управления ТЦУ, находящейся в начале j-й дуги, и задается структурой ВС. Итак, при анализе реализуемости ТЦУ необходимо установить возможность реализации ВВР на ВС с заданной структурой при заданном векторе h. Для реализации алгоритма анализа реализуемости ТЦУ сформулируем следующее утверждение. Для реализации ТЦУ на заданной структуре ВС с заданным ВВР t необходимо и достаточно выполнение следующего условия: если из i-й вершины графа ТЦУ выходит j-я дуга, входящая в n-ю вершину, то разница tn - ti должна быть не меньше, чем время выполнения задачи в i-й вершине: (1) Следовательно, благодаря матрице A и векторам t и h становится возможным определение многих характеристик процесса выполнения ТЦУ. Например, время реализации определим по формуле Подпись: (2) где zi является временем выполнения задачи, реализация которой начинается в момент ti. Отметим, что последовательность выполнения задач ТЦУ соответствует упорядочению координат ВВР по возрастанию. Если некоторые координаты равны, то это указывает на их параллельное выполнение. Для случая, когда неравенство (1) не выполняется, предлагается следующий алгоритм коррекции ТЦУ, который позволяет производить замену компонентов ВВР на удовлетворительные. Чтобы этот корректирующий алгоритм имел смысл, необходимо выполнение следующих условий. 1. Условие неотрицательности (3) где I = {i} - это совокупность задач ТЦУ. 2. Условие завершения предыдущих задач ТЦУ (4) 3. Условие логической последовательности (5) где aij - это коэффициент связности задач, т. е. ti и hi являются компонентами векторов ВВР и ВР соответственно. Для каждой задачи ТЦУ введем параметры: tif - момент времени, до истечения которого ценность i-й задачи остается максимальной; tis - момент времени, до истечения которого выполнение i-й задачи невозможно: (6) Очевидно, что где T - длительность реализации ТЦУ. Если условия (3)-(5) выполняются, то выполняются и условия для связных задач i и j. С другой стороны, если ТЦУ существует, то: где и - моменты начала j-й и завершения i-й задач. Поэтому для каждой связной пары i и j замена при коррекции ВВР «старых» значений на «новые» max и, соответственно, на min не влияет на факт допустимости существования ТЦУ. Таким образом, в результате работы алгоритма коррекции «старые» координаты ВВР меняются на «новые», удовлетворяющие следующим условиям. 1) 2) 3) Алгоритм Дейкстры разработан для поиска кратчайшего пути (в том числе временного) между заданным исходным узлом и любым другим узлом сети (графа) [8]. В процессе выполнения этого алгоритма при переходе от узла i к следующему узлу j используется специальная процедура пометки ребер. Обозначим через ui кратчайшее расстояние от исходного узла 1 до узла i, через dij - длину ребра (i, j). Тогда для узла j определим метку [uj, i] следующим образом: [uj, i] = [ui + dij, i], dij ≥ 0. (7) Метки узлов в алгоритме Дейкстры могут быть двух типов: временные и постоянные. Временная метка впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный. Вычислительная схема алгоритма состоит из следующих этапов. Этап 0. Исходному узлу (узел 1) присваивается постоянная метка [0, -]. Полагаем i = 1. Этап 1. 1. Вычисляются временные метки [ui + dij, i] для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [uj, k], полученную от другого узла k, и если ui + dij < uj, тогда метка [uj, k] заменяется на [ui + dij, i]. 2. Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка [ur, s] с наименьшим значением расстояния ur среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем этап i. Реализация алгоритма Дейкстры. Определим кратчайший временной путь графа ТЦУ после корректировки ВВР методом анализа и коррекции детерминированной модели процесса (см. рисунок). Откорректированный ВВР {} = {t1 = 3; t2 = 5; t3 = 6; t4 = 9; t5 = 12; t6 = 12; t7 = 15; t8 = 16; t9 = 21; t10 = 24} дает представление о времени выполнения задачи, реализация которой начинается в момент ti. Таким образом, временной отрезок между вершинами, выраженный в условных единицах времени (у.е.в.), есть разность tj - ti. Определим временные отрезки между узлами каждой пары взаимосвязанных вершин графа ТЦУ и представим их в табл. 1. Определение кратчайшего временного пути от узла 1 графа ТЦУ до всех остальных узлов Этап 0. Назначим узлу 1 постоянную метку [0, -]. Этап 1. Из узла 1 можно достичь узлов 2 и 3. Вычислим метки для этих узлов, в результате получим следующую таблицу меток (табл. 2). Среди узлов 2 и 3 узел 2 имеет наименьшее значение (u2 = 2). Поэтому статус метки этого узла изменяется на «постоянная». Этап 2. Из узла 2 можно достичь узла 5. Вычислим метку для этого узла, в результате получим следующую таблицу меток (табл. 3). Поскольку не все узлы имеют постоянные метки, то для дальнейшей реализации алгоритма выбираем метку с наименьшим временным путем, а именно (u3 = 3), при этом статус метки узла 3 изменяется на «постоянная». Последующие этапы описывают вычислительную схему алгоритма с последовательным присвоением статуса метки «постоянная» всем узлам сети. Рассмотрим завершающие этапы. Этап 9. Из узла 9 можно достичь узла 10. Вычислим метку для этого узла, в результате получим следующую таблицу меток (табл. 4). На 9-м этапе узел 10 получает две метки с одинаковым временным путем (u10 = 21). Поскольку не все узлы имеют постоянные метки, то для завершения алгоритма выбираем метку с наименьшим временным путем, а именно, единственную метку (u10 = 21), при этом статус метки узла 10 изменяется на «постоянная». Этап 10. Так как из узла 10 нельзя попасть ни в один другой узел, процесс вычислений заканчивается (табл. 5). Граф ТЦУ и откорректированные значения компонентов ВВР Таблица 1 Временные отрезки между узлами каждой пары взаимосвязанных вершин графа ТЦУ Номера взаимосвязанных вершин Отрезок времени между взаимосвязанными вершинами, у.е.в. t2 - t1 2 t3 - t1 3 t5 - t2 7 … … t10 - t8 8 t10 - t9 3 Таблица 2 Вычислительная схема алгоритма этапа 1 Узел Метка Статус метки 1 [0, -] Постоянная 2 [0 + 2, 1] = [2, 1] Временная 3 [0 + 3, 1] = [3, 1] Временная Таблица 3 Вычислительная схема алгоритма этапа 2 Узел Метка Статус метки 1 [0, -] Постоянная 2 [2, 1] Постоянная 3 [0 + 3, 1] = [3, 1] Временная 5 [2 + 7, 2] = [9, 2] Временная Таблица 4 Вычислительная схема алгоритма этапа 9 Узел Метка Статус метки 1 [0, -] Постоянная 2 [2, 1] Постоянная 3 [3, 1] Постоянная 4 [6, 3] Постоянная 5 [9, 2] Постоянная 6 [9, 3] Постоянная 7 [12, 6] Постоянная Окончание табл. 4 Узел Метка Статус метки 8 [13, 5] Постоянная 9 [18, 7] Постоянная 10 [13 + 8, 8] = [21, 8] [18 + 3, 9] = [21, 9] Временная Таблица 5 Вычислительная схема алгоритма этапа 10 Узел Метка Статус метки 1 [0, -] Постоянная 2 [2, 1] Постоянная 3 [3, 1] Постоянная 4 [6, 3] Постоянная 5 [9, 2] Постоянная 6 [9, 3] Постоянная 7 [12, 6] Постоянная 8 [13, 5] Постоянная 9 [18, 7] Постоянная 10 [21, 8] Постоянная Определение кратчайшего временного пути между узлом 1 и любым другим узлом графа ТЦУ Кратчайший временной путь между узлом 1 и любым другим узлом графа ТЦУ определяется, начиная с узла назначения путем прохождения их в обратном направлении с помощью информации, представленной в постоянных метках. Например, для определения кратчайшего временного пути между узлами 1 и 5 получаем следующую обратную последовательность узлов: (5) → [9, 2] → [2, 1] →(1). Таким образом, получаем путь 1 → 2 → 5 общей продолжительностью tp = 9 у.е.в. Заключение. Аналитико-оптимизационная процедура, применимая к детерминированной модели, в рамках настоящей работы дополнена алгоритмической конструкцией. Вычислительная схема алгоритма Дейкстры показывает его реализуемость в детерминированных моделях (граф ТЦУ) и позволяет определить такие характеристики, как кратчайший временной путь на любом участке информационной карты, что с точки зрения управления позволяет анализировать временные затраты маршрута управления и позволяет делать вывод о том, где, а также за счет чего достигнуто сокращение холостых временных «окон» [15]. Данный результат значим с точки зрения возможности применения методов сетевого анализа в решении задачи параметрической оптимизации детерминированных моделей технологических циклов автоматизированных систем управления.

Об авторах

И. В. Ковалев

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

П. В. Зеленков

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

В. В. Лосев

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

В. В. Храпунова

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

С. В. Ефремова

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

Список литературы

Дополнительные файлы