индекс кластера выбирается из следующего соотношения i = J1*MAX + 1, где J1MAX — число единиц кластерной инфраструктуры, для которых * зафиксированы варианты развития в выбранном частичном решении (блоки 9, Ю). 2. Исключение неперспективных решений. Если на определенном шаге ветвления будет получено решение, в котором зафиксированы варианты развития для всех кластеров инфраструктуры, то из рассмотрения исключаются все частичные решения, имеющие худшие, чем у данного, оценки критерия оптимальности. Т.е. исключаются все решения, следующие за данным в массиве частичных решений (блок 6). 3. Вычисление оценки. Для произвольной вершины у-го уровня модели с зафиксированными вариантами развития для у-го кластера, оценка вычисляется следующим образом: F« = Fu (xikl) + Fit*(xikl) (3.2.8) где первое слагаемое есть значение критерия для зафиксированной части, второе — оценка критерия для незафиксированной части кластерной инфраструктуры плана развития. Для вычисления Fi*(xiki) выполняются следующие шаги процедуры: * Шаг 3.1. Вычисляется значение оставшейся части ресурсов R R(xat), i I) 100 |
г / к m in Z E Z ^ ^ (2 -2 -7) /=1 /=1 ы Таким образом, план, обеспечивающий минимум дефицита надёжности, на всём интервале времени, выделенном на развитие системы, будет являться оптимальным. Для решения рассмотренной задачи используется алгоритм, применяющий графовую формализацию [65], отражающую возможные варианты развития кластерной системы. Алгоритм основан на процедуре просмотра вариантов решения, использующей схему «ветвей и границ» (см. также [57]). Блок-схема алгоритма приведена в [50, 54]. Здесь рассмотрим только основные шаги алгоритма. 1. Ветвление. Для очередного г-го кластера просматривается множество возможных вариантов его развития. Для каждого вновь полученного варианта проводится расчет оценки критерия оптимальности (блок 4), и каждое вновь полученное решение помещается в массив частичных решений (МЧР), который упорядочивается по значению оценки критерия оптимальности (блок 5). Ветвление осуществляется из решения, у которого зафиксированы варианты развития для наибольшего количества элементов кластерной инфраструктуры; если таких вариантов несколько, то ветвление осуществляется из решения с наилучшей оценкой критерия. Очередной индекс кластера выбирается из следующего соотношения i J1*MAX + 1, где JIM АХ — число единиц кластерной инфраструктуры, для которых зафиксированы варианты развития в выбранном частичном решении (блоки 9, 10). 2. Исключение неперспективных решений. Если на определенном шаге ветвления будет получено решение, в котором зафиксированы варианты развития для всех кластеров инфраструктуры, то из рассмотрения исключаются все частичные решения, имеющие худшие, чем у данного, оценки критерия оптимальности. Т.е. исключаются все решения, следующие за данным в массиве частичных решений (блок 6). 3. Вычисление оценки. Для произвольной вершины у-ro уровня модели с зафиксированными вариантами развития для у-го кластера, оценка вычисляется следующим образом: Fu = F it(:W + F it*(xikt) (2.2.8) где первое слагаемое есть значение критерия для зафиксированной части, второе — оценка критерия для незафиксированной части кластерной 87 инфраструктуры плана развития. Для вычисления Fj*(xik{) выполняются следующие шаги процедуры: Шаг 3.1. Вычисляется значение оставшейся части ресурсов R J+l-R rR(xikt)y i jШаг 3.2. Полагается /=у+1; для всех кластеров, вариант развития которых не зафиксирован, назначается высшая допустимая категория кластера (с учетом кластер-кворума), формируется массив категорий кластеров КМAS (7, t), рассчитываются затраты ресурсов на создание такой сети RQ \ и проверяется ограничение R j+,t R Q (2.2.9) Если ограничение выполнено, то Fu = Fit (xikt), если ограничение не выполнено, то для каждого /-го кластера (i>j) вычисляется значение вносимой им добавки к критерию D(i., t) при уменьшении его категории на единицу, и сформированный таким образом массив MEM (п, t) упорядочивается в порядке увеличения добавок к критерию оптимальности. Шаг 3.3. Выбирается кластер, дающий наименьшую добавку к критерию оптимальности при уменьшении его категории Л = MEM (п. t), KMAS (Л, t) ~ KMAS (Л, t) 1, вычисляется величина RQ \ = Rkmasot t)j Rkmas(i1,о проверяется ограничение (3.2.9). Шаг 3.4. Если ограничение (2.2.9) не осуществлено, то снова выполняется шаг 3.3. В противном случае на основе сформированного массива КМAS (Л, t) вычисляется F*u (xikl) = Fu (xtf (kmasc/i,d,i)* 4. Условие получения оптимального решения. Если на первом месте в массиве частичных решений оказывается решение, в котором зафиксированы варианты развития для всех кластеров инфраструктуры, то получено оптимальное решение, и алгоритм работу заканчивает (блок 7). Рассмотренные модели и алгоритмы используются в следующей главе для оптимизации плана развития кластерной структуры конкретной катастрофоустойчивой системы обработки информации на заданный период развития. Вы воды по главе 2 1. В результате анализа методов оценки надежности информационных систем и с учетом требований, предъявляемых к надежности сегодня, обосновано применение метода уменьшения множества вариантов системы с резервированием, позволяющего определить вариант системы, который обеспечивает успешное |