36. Синтез организационной структуры на графовых моделях. Критерии синтеза.

Синтез организационной структуры на графовых моделях

Рассмотрим особенности использования графовых моделей для синтеза организационной структуры ИС.

Организационную структуру системы удобно представить в виде графа G(E,V), где Е – множество вершин, представляющих собой элементы структуры; V – множество дуг, указывающих связи между элементами.

Синтез организационной структуры на графовых моделях основан на принципе агрегирования, т.е. объединении в одну подсистему наиболее близких задач, или в один управляющий узел наиболее тесно взаимодействующих подразделений и исполнителей.

Задача синтеза организационной структуры в терминах теории графов формулируется как разбиение графа G на подграфы G₁, G₂, …, G_N. При этом каждый из графов G_i  G, i = 1, 2, …, N, подграфы не должны пересекаться G_i  G_j = 0, для i, j =1, 2, …, i  j, объединение должно дать исходный граф: .

Полученное разбиение должно минимизировать функцию:

, (1)

где C_i(G_i) - некоторая функция, определенная на множестве разбиений G_i , i = 1, 2, …N.

В зависимости от вида целевой функции графовые задачи синтеза организационной структуры формализуются следующим образом:

1. Найти разбиение графа G(E,V) на подграфы G₁ , G₂, … G_N при r(E_i)≤r, которое минимизирует некоторую функцию от величины внешних связей между подграфами (например, сумму внешних связей, величину связей между отдельными подграфами и т.д.). Ограничение r(E_i)≤r может означать, например, допустимое количество вершин (сотрудников) в подграфе (в подразделении).

2. Найти разбиение графа G(E,V) на сильно связанные подграфы, т.е. на подграфы, у которых связи между элементами внутри подграфа больше, чем с другими элементами графа G₁, G₂, …, G_N.

3. Найти разбиение графа G(E,V), чтобы a(U)=0,5∑c(E_i)→min при max l(E_i)≤ a(U), где a(U) – суммарная внешняя связанность подграфов минимизируется, при котором максимальная внутренняя связь подграфа не должна превышать суммарной внешней связи.

Обозначения: c(E_i) - число связей всех вершин E_i с другими вершинами V\V_i; l(E_i) – число связей вершин графа G_i между собой.

4. Найти разбиение графа G(E,V) на N непересекающихся подмножеств , G_s  G_t =0 для s, t =1, 2, …N, s  t таким образом, чтобы

,

где d_ij – показатель степени связи между вершинами графа G;

.

37. Синтез функциональной структуры ис на графовых моделях.

См выше.

38. Синтез иерархической структуры комплекса технических средств информационной системы.

Синтеза организационной структуры методом центральной планирующей организации

В основу метода центральной планирующей организации положен принцип максимальной связности задач, решаемых в каждом подразделении [18]. Задача синтеза формализуется аналогично предыдущей задаче, но для получения многоуровневой структуры поиск автономных подсистем ведется не только по горизонтали (в пределах одного иерархического уровня), но и по вертикали.

Вначале по заданному ограничению max b(E_i)≤B для графа G(E,V) решается задача поиска оптимального разбиения u₁ для нижнего иерархического уровня с целевой функцией a(E_i)→min (из графа G выделяется подграф первого уровня по критерию минимума внешних связей и ограничении числа внутренних связей В. Для графа G\ G₁= G_u1 решение повторяется и т.д., пока число внутренних связей не будет превышать В).

Затем та же задача решается вновь, но уже для графа G_u1, что позволяет найти такое разбиение u₂ для второго уровня, у которого a(u₂)→min. И так до тех пор, пока на некотором уровне β значение min a(u_β) не будет превосходить константу В. Тем самым проблема синтеза структуры сводиться к определению частных (субоптимальных) разбиений u₁ , u₂ ,.. u_β .

Использование методов теории массового обслуживания для синтеза организационной структуры

При оптимизации структуры иерархической системы оперативного управления каждый из узлов системы рассматривается как система массового обслуживания (СМО), имеющая m входов (входящих потоков требований на обслуживание) и l выходов [17].

На вход любого узла системы в некоторые случайные моменты времени в соответствии с заданным законом распределения поступает m потоков. Потоки могут быть либо неограниченными, либо состоять из конечного числа требований. Выходящий поток образуется из последовательности обслуженных требований различных входящих потоков и из требований, покидающих систему или очередь до окончания обслуживания.

Оптимизация проводится для однородных иерархических структур, т.е. характеристики узлов одной ступени одинаковы, и к каждому узлу подключено одинаковое для данной ступени число узлов предыдущей. В качестве общего критерия функционирования системы, характеризующего суммарные потери, принимается

(2)

где W(m)- величина критерия для m-ступенчатой системы; W(m-1)- соответствующие потери для составляющих ее подсистем (m-1)-го порядка (всего таких подсистем nm-1); Wm – потери в системе обслуживания последней ступени; Wi - потери в системе обслуживания одного узла i-й ступени; n_j – число узлов j-й ступени, подключаемых к одному узлу (j+1)-й ступени.

Оптимизация заключается в нахождении таких значений n_i*, i=1, 2, ..(m-1), nm=1 , при которых W(m) минимально; где m - число ступеней.

В критерии первая формула выражает суммарные потери через потери в однородных подсистемах, их число nm-1 , потери в каждой подсистеме W(m-1). Во второй формуле потери вычисляются через потери в узлах W_i , количество узлов nj, подключаемых к одному узлу (j+1)-й ступени.