Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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





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

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

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

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

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

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

       
   
 
 

 

 


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

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

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

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

 
 

 

 


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

 

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

Ar d
+ + +   + +
  +     +  
+ +     + +
+   + +    
  + + +    

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

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

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

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

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

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

║djℓ║=

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

I [ a1 ], [ a2, a3, a4, a5 ]

II [ a1, a2 ], [ a3, a4, a5 ]

III [ a1, a2, a3 ], [ a4, a5 ]

IV [ a1, a2, a3, a4 ], [ a5 ]

 


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

I.

; ; SI=5

II.

; ; SII=5

III.

; ; SIII=3

IV.

; ; SIV=3

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

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

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

А={a1, a2, …, aj, …, am} – множество задач, далее процедур системы обработки данных

R={r1, r2,…, r,…, rL} – множество информационных элементов

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

процедуры аj

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

 

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

 
 


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

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

 

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

 

 

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

yi=

0, если

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

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

(1)

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

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

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

xij+xij`≤1 , i=1,..,M0 (5)

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

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

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

(8)

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

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

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

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

Zℓii`=

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

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

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

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

Лекция 14.





Дата добавления: 2014-01-07; Просмотров: 343; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.007 сек.