Постановка и модель решения задачи разбиения ИЛМ АСУ на функциональные модули с минимальным числом информационных связей

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

Исходными данными для задачи являются:

1) множество различных типов входных, промежуточных и выходных данных,

2) множество необходимых процедур преобразования данных.

При этом задачи относятся к одному и тому же уровню (см. л. 8).

Отношение, т.е. оператор отображения множества процедур к множеству информационных элементов можно представить в виде двудольного графа, дуги которого соединяют процедуры с соответствующими информационными данными (см. рис. 3.13).

Рис. 3.13. Двудольный граф связи процедур и информационных элементов

Разбиение информационного и программного обеспечения АСУ на модули сводится в данной к разбиению данного множества задач (процедур обработки данных) на непересекающиеся подмножества, имеющие минимальное число общих информационных элементов.

Предварительно рассмотрим пример решения задачи разбиения программного и информационного обеспечения АСУ на функциональные модули, имеющие минимальное число информационных связей (см. конспект лекций).

Пусть граф задачи содержит пять процедур и шесть информационных элементов (см. рис. 3.14). Матричная форма соотношений между процедурами и информационными элементами приведена в таблице 3.4.

Рис. 3.14 Граф взаимосвязи процедур с информационными элементами

Таблица 3.4. Матричная форма соотношений

Ar	dℓ
	+	+	+		+	+
		+			+
	+	+			+	+
	+		+	+
		+	+	+

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

Рассмотрим решение задачи при следующих ограничениях:

1) общее число модулей V=2;

2) общее число информационных элементов в каждом из модулей L_v≤6, v=1,2;

3) общее число процедур в каждом модуле M_v≤4, v=1,2.

Находим матрицу взаимосвязи процедур обработки с информационными элементами:

║d_jℓ║=

При заданных условиях возможно четыре варианта разбиения процедур на модули

I [ a₁ ], [ a₂, a₃, a₄, a₅ ]

II [ a₁, a₂ ], [ a₃, a₄, a₅ ]

III [ a₁, a₂, a₃ ], [ a₄, a₅ ]

IV [ a₁, a₂, a₃, a₄ ], [ a₅ ]

Для каждого варианта разбиения определяем матрицы X_ji и Y_ℓi и значение критерия S:

I.

; ; S_I=5

II.

; ; S_II=5

III.

; ; S_III=3

IV.

; ; S_IV=3

По критерию оптимальным является IV вариант разбиения.

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

Для формализации задачи введем следующие обозначения:

А={a₁, a₂, …, a_j, …, a_m} – множество задач, далее процедур системы обработки данных

R={r₁, r₂,…, r_ℓ,…, r_L} – множество информационных элементов

1, если информационный элемент r_ℓ используется для выполнения

процедуры а_j

0, в противном случае

Введем в рассмотрение следующие переменные:

1, если процедура а_j входит в модуль А_i, j=1,..,m; i=1,..,M=2^m-1

0, в противном случае

и связанные с ней переменные:

1, если ; i=1,..,M; ℓ=1,..,L

y_ℓi=

0, если

т.е. y_ℓi=1, если r_ℓ - й информационный элемент используется процедурой a_j, которая размещается в модуле А_i.

При этих обозначения суммарное число различных информационных элементов, являющихся общими для различных модулей А_i, i=1,..,M равно

(1)

При ограничениях:

1. На число выделяемых модулей M₀≤M (2)
Каждая процедура хотя бы в одном модуле должна находиться:

j=1,..,m (3)
3. Число процедур в одном модуле может быть ограничено некоторой величиной N: i=1,..,M₀ (4)
4. Некоторые процедуры j и j` должны быть разнесены по разным модулям, т.е.

x_ij+x_ij`≤1, i=1,..,M₀ (5)

5. Число информационных элементов, с которыми связан модуль, может быть ограничено, т.е. i=1,..,M₀ (6)

6. Ограничения на сложность взаимодействия информационных элементов и процедур внутри модулей, т.е. i=1,..,M₀ (7)

7. Ограничения на количество сложных связей между информационными элементами и некоторой парой i и i` модулей, т.е.

(8)

Задача (1)-(8) является задачей квадратичного целочисленного программирования.

Для удобства решения она может быть сведена к линейной форме путем линеаризации выражений (1) и (8).

Введем переменную

1, если ℓ-й информационный элемент необходим для модулей А_i и A_i`

Z_ℓii`=

0, в противном случае

Тогда критерий (1) может быть записан так:

(9)
Ограничение (8) при этом будет иметь вид:

для заданных i и i` (10)
Задача разбиения, представленная выражениями (9), (2)-(7), (10) имеет линейный вид и может быть решена с использованием стандартных методов.

Лекция 14.

Дата добавления: 2014-01-07