Журнал Автоматизация Проектирования,

выпуск 4, стр. 14-19, 1997.

Комбинаторное проектирование систем

М. Ш. Левин

13.09.1997



Введение

Декомпозируемые системы

Проектирование

Синтез последовательно-параллельной стратегии

Трансформация декомпозируемых систем

Приложения

Заключение

Литература


Задачи комбинаторного синтеза сложных систем из их частей (подсистем, компонентов и т. п.) являются важным практическим направлением во многих приложениях (техника, экономика и др.). Часто такой подход называют модульным проектированием (например, разработка программного обеспечения, проектирование электронных систем и др.) или планированием (например, модульное планирование в производственных системах).


Введение

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

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

моделей описания систем;

моделей комбинаторного синтеза;

информационной поддержки модульного проектирования;

взаимодействия специалистов (экспертов, проектировщиков, лиц принимающих решение и др.) и компьютерных систем;

накопления примеров использования композиционного подхода;

обучения специалистов основам модульного проектирования.

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

проектирование декомпозируемых сложных систем в Вычислительном Центре РАН [6];

проектирование сложных систем на основе морфологического и многокритериального подхода в Институте проблем управления РАН, Институте системных исследований РАН и ряде отраслевых организаций [1, 2, 4, 5];

аппроксимационно-комбинаторный метод проектирования в Вычислительном Центре РАН [12];

математическое исследование "синтеза знаний" [13, 15];

системная среда САПР для проектирования СБИС в НИИСАПРАН [11].

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

Отметим, что предложенная схема проектирования декомпозируемых систем - "Иерархическое Морфологическое Многокритериальное Проектирование" (ИММП), хотя и похожа на иерархические подходы к проектированию, принятию решений, на генетические методы решения задач, отличается от них, в частности, учетом порядковой совместимости элементов составных решений.

Декомпозируемые системы

Под декомпозируемой системой мы понимаем следующее: система состоит из частей (компонентов); для каждой части имеется или может быть сформировано некоторое множество альтернативных проектных вариантов (ПВ).

Мы рассматриваем детерминированные комбинаторные задачи, направленные на композицию декомпозируемых систем из компонентов. Дополнительно мы учитываем парные взаимосвязи (С) или совместимость между ПВ.

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

описание и/или представление (разработка древовидной модели системы; требований и/или характеристик системы и ее частей и их взаимосвязей С);

оценивание системы и ее частей (получение оценок ПВ и С, формирование интегральных оценок системы в целом);

выявление узких мест (выявление элементов системы в виде частей-компонентов и/или их совместимостей, улучшение которых приводит к улучшению качества системы в целом);

сравнение (сравнение вариантов системы или ее частей);

отбор (выбор лучших вариантов системы или ее частей);

синтез (композиция системы из ПВ с учетом качества ПВ и С);

модификация (преобразование, улучшение, адаптация), т. е. изменение, в частности, элементов и их взаимосвязей, состава.

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

Пример декомпозируемой системы представлен на рис. 1. При этом рассматривается следующая ситуация: исходная система S включает три компонента A, B, C с соответствующими ПВ: A1, A2, B1, B2, B3, C1, C2. В качестве примера составного решения можно привести следующее: S' = A2 * B1 * C1.

Дополнительно мы можем рассматривать некоторые изменения системы (трансформация, улучшение и т. п.): добавить ПВ (A3, C3, C4); исключить ПВ (B2, C1); добавить компонент D с ПВ (D1, D2, D3).

Проектирование

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

проектная методология в Carnegie Mellon University [22, 27];

JESSI COMMON FRAMEWORK для процесса проектирования [42];

иерархическое принятие решений [30];

параллельное проектирование [46];

модульное и многозадачное проектирование и производство [16, 48, 50];

Рассматриваемый в работе подход к проектированию декомпозируемых систем ИММП включает следующие стадии:

задание требований к проектируемой системе и ее компонентам (цели или критерии, ограничения);

формирование структуры проектируемой системы;

генерация проектных альтернатив ПВ;

оценивание ПВ и С;

ранжирование (оценивание в порядковой шкале качества) ПВ;

композиция составных ПВ;

анализ составных ПВ и их улучшение.

Укажем базовые предположения, используемые в ИММП:

проектируемая система имеет иерархическую древовидную структуру;

качество (эффективность, совершенство и т. п.) системы представляет собой агрегацию качества составных частей и качества совместимости этих частей;

критерии качества являются монотонными;

качество совместимости частей системы (или подсистемы) равно агрегации парных совместимостей частей;

многокритериальные характеристики качества частей или совместимостей могут быть отображены на некие порядковые шкалы, и эти шкалы могут быть согласованы.

Обычно для перечисленных задач применяются следующие подходы:

оптимизационные модели [16, 25, 49];

системы на основе баз знаний [27, 44, 49];

гибридные методы [32].

ИММП описан в работах [37, 39], а модели комбинаторного синтеза - в [36].

Рассмотрим задачу нашего подхода к комбинаторному синтезу - морфологическую клику. Предполагается, что проектируемая система состоит из m компонентов, и для каждого компонента i = 1, ..., m существует множество альтернативных ПВ (морфологический класс i). Задача заключается в следующем: найти композицию (морфологическую схему, т. е. клику)

S = S(1) * ... * S(i) * ... * S(m),

где S(i) является отобранным ПВ для компонента i (один представитель из каждого морфологического класса) при условии ненулевой совместимости между ПВ. Предполагается порядковая оценка совместимости для всех пар ПВ из разных морфологических классов. (0 соответствует несовместимости.)

Мы используем векторную оценку совершенства системы:

N(S) = (w(S); n(S)),

где w(S) - минимум парных совместимостей в S, n(S) = (n(1), ..., n(r), ..., n(k)) описывает отобранные ПВ (n(r) - это число ПВ с приоритетом r в S, где r = 1 соответствует лучшему классу качества и w = 0, ..., t, t соответствует лучшей совместимости).

На рис. 2 представлено пространство совершенства составной системы в виде решетки, которая соответствует вектору N.

Таким образом мы ищем составную систему S, которая является недоминируемой по N(S).

Аналогично можно описать задачу, когда из каждого морфологического класса ПВ выбирается несколько проектных вариантов. Такие постановки встречаются в инженерной практике последнее время (решения с избыточностью по подсистемам). Отметим также, что n(S) является размытой оценкой.

Cхема решения состоит из:

построения допустимых решений;

выбора Парето-эффективных решений по N.

Предложенная задача морфологической клики близка к ряду известных моделей и подходов к проектированию [3, 20, 28, 31, 43, 47, 52].

Для анализа сложных решений мы используем элементы двух типов ПВ и C в отношении решения S: S-улучшающие, S-нейтральные и S-ухудшающие элементы по вектору N, где S-ухудшающие элементы рассматриваются как "узкие места", которые должны быть улучшены.

Алгоритм анализа и улучшения заключается в следующем:

поиск узких мест (нахождение всех S-ухудшающих элементов для множества Парето-эффективных ПВ);

построение окрестности множества Парето-эффективных точек (каждый элемент этой окрестности может быть преобразован в Парето-эффективную точку только одним улучшающим действием);

исследование возможных улучшающих действий для каждого выявленного узкого места и для каждого элемента окрестности.

Синтез последовательно-параллельной стратегии

Многостадийное планирование используется в экономике, производственных системах, при решении сложных проблем в искусственном интеллекте [45]. На рис. 3 представлены два примера последовательно-параллельных стратегий для четырехстадийной задачи.

Отметим, что последовательно-параллельный процесс соответствует дерево-декомпозируемому графу, т. е. возможна декомпозиция исходного графа на базе дерева "происхождения". Другие дерево-декомпозируемые графы (например, деревья, частичные k-деревья) исследуются в работе [18]. В нашем случае мы используем структуру, которая подобна И-ИЛИ дереву.

Мы рассматриваем композицию схемы решения на основе ИММП, в том числе последовательно-параллельную композицию составных ПВ для обработки данных с учетом С между ПВ. В этом приложении С соответствует совместимости последовательных ПВ (локальных процедур решения для конкретного периода) и независимости параллельных ПВ.

Общая схема проектирования последовательно-параллельной стратегии включает следующие этапы:

1. Построение (описание) базовой иерархической модели стратегии (морфологии).

2. Анализ и отбор элементов исходной модели с целью формирования рабочей морфологии стратегии.

3. Композиция последовательно-параллельной стратегии на основе ИММП.

Примеры построения стратегий описаны в литературе [34, 36].

Трансформация декомпозируемых систем

Трансформация (улучшение, преобразование, реинжиниринг и т. п.) сложных систем исследуются в различных дисциплинах [17, 21, 26, 29].

В общем случае можно указать два повода для проектирования систем [51]:

улучшение существующей системы;

проектирование новой системы.

В первом случае происходит эволюционное улучшение и многокритериальный отбор проектных альтернатив [14, 19, 49].

В работе [39] представлен многостадийный процесс трансформации декомпозируемой новой системы. На каждой стадии на основе ИММП формируется некая композиция действий по трансформации (улучшению) системы.

На верхнем иерархическом уровне осуществляется композиция стадийных составных действий в комплексную многостадийную стратегию улучшения (также на основе ИММП).

Заметим, что иерархические подходы применяются многие годы, например:

иерархическое планирование систем [23];

иерархическое принятие решений в производственных системах [30];

иерархическое планирование в искусственном интеллекте hierarchical tasks network (HTN) decomposition [24].

Приложения

Укажем опубликованные примеры применения ИММП:

проектирование и улучшение интерфейса пользователя [33];

проектирование последовательного набора интерфейсов пользователя [34];

анализ и проектирование человеко-машинных систем [38];

информационное проектирование в гипертекстовых системах [35, 40];

проектирование конвейеров [41];

планирование информационного центра [7];

подготовка бизнес-планов [9];

реинжениринг информационных систем [39];

обучение, включая проектирование учебных программ, планирование карьеры студента [8, 10].

Заключение

Следует указать некоторые теоретические и практические направления, которые представляются важными:

стратегическое многоэтапное проектирование систем с учетом неопределенности в появлении альтернативных вариантов реализации компонентов сложных систем, включая вероятностные описания ПВ или описания на основе теории размытых множеств и т. п.;

многостадийное планирование стратегий решения задач при проектировании и планировании;

исследование более сложных комбинаторных моделей синтеза систем, например, с учетом зависимости парной совместимости от других элементов систем;

построение декомпозиционных схем решения сложных задач комбинаторной оптимизации;

использование комбинаторного синтеза в информационных технологиях на различных этапах обработки данных;

обучение специалистов комбинаторному проектированию сложных многодисциплинарных систем.


Литература

1. Березовский Б.А., Данилов В.Н., Кортнев А.В., Коссов О.А. и др. Формирование наборов высших растений для замкнутой биотехнической системы жизнеобеспечения: Обзор.-М.: ОНТИТЭИМикробиопром, 1977. - 75 с.

2. Березовский Б.А., Конторер Л.А., Эффективный алгоритм построения множества недоминируемых вариантов декомпозируемых объектов. - Автоматика и телемеханика. 1987, # 1. - с. 115-121.

3. Гэри М., Джонсон Д., Вычислительные машины и трудно решаемые задачи. Пер. с англ. - М.: Мир, 1982. - 416 с.

4. Дубов Ю.А., Травкин С.И., Якимец В.Н., Многокритериальные модели формирования и выбора вариантов систем. - М.: Наука, 1986. - 296 с.

5. Емельянов С.В., Озерной В.М., Ларичев О.И. и др. Выбор рациональных вариантов технологических шахт с учетов большого числа критериев. - Горн. журнал. - 1972, # 5.

6. Краснощеков П.С., Морозов В.В., Федоров В.В., Декомпозиция в задачах проектирования. - Техническая кибернетика. - 1979, # 2. - с. 7-17.

7. Левин М.Ш., Задача планирования информационного центра. - НТИ, сер. 2. - 1995, # 2. - с. 16-24.

8. Левин М.Ш., О третьей грамотности. - НТИ, сер. 2. - 1995, # 6 - с. 20-30.

9. Левин М.Ш., Типовые задачи принятия решений при подготовки бизнес-планов. - НТИ, сер. 1. - 1995, # 10. - с. 7-13.

10. Левин М.Ш., Иерархический комбинаторный подход к планированию карьеры. - НТИ, сер. 2. - 1996, # 12. - с. 22-27.

11. Стемпковский А.Л., Шепелев В.А., Власов А.В., Системная среда САПР СБИС. - М.: Наука, 1994. - 251 с.

12. Хачатуров В.Р., Аппроксимационно-комбинаторный метод декомпозиции и композиции систем и ограниченные топологические пространства, решетки, оптимизация. - Ж. вычислительной математики и математической физики. - 1985. - Том 25, # 12. - с. 1777-1794.

13. Цой Е.В., Юдин А.Д., Юдин Д.Б., Проблемы дополнения и синтеза знаний. - Автоматика и телемеханика. - 1994, # 7. - с. 3-36.

14. Эйрес Р., Научно-техническое прогнозирование и долгосрочное планирование. - М.: Мир, 1971. - 296 с.

15. Юдин Д.Б., Системы синтеза знаний. - Докл. АН СССР. -1990. - Том 315, # 4. - с. 809-812.

16. Berman O. and Ashrafi N., "Optimization Models for Reliability of Modular Software Systems". IEEE Trans. on Software Engineering, Vol. 19, # 11, pp. 1119-1123, 1993.

17. Berman O., Ingco D.I. and Odoni A., "Improving the Location of Minimax Facilities Through Network Modification". Networks, vol. 24, pp. 31-41, 1994.

18. Borie R.B., "Generation of Polynomial-Time Algorithms for Some Optimization Problems on Tree-Decomposable Graphs". Algorithmica, Vol. 14, # 2, pp. 123-137, 1995.

19. Buede D.M. and Choisser R.W., "Providing an Analytical Structure for Key System Choices", J. of Multi-Criteria Decision Analysis, vol. 1, # 1, pp. 17-27, 1992.

20. Carraway R.L. and Schmidt R.L., "An Improved Discrete Dynamic Programming Algorithm for Allocating Resources Among Interdependent Projects". Manag. Sci., Vol. 37, # 9, pp. 1195-1200, 1991.

21. Das D., Gupta S.K., and Nau D., "Reducing setup cost by automatic generation of redesign suggestions. In: Proc. of ASME Conference "Computers in Engineering", 1994.

22. Demes G.H., Fenves S.J., Grossmann I.E., Hendrickson C.T., Mitchell T.M., Prinz F.B., Sewiorek D.P., Subrahmanian E., Talukdar S. and Westerberg A.W., "The Engineering Design Research Center of Carnegie Mellon University". Proc. of the IEEE, Vol 81, # 1, pp. 10-23, 1993.

23. Dempster M.A.H., Fisher M.L., Jansen L., Lageweg B.J., Lenstra J.K., and Rinnooy Kan A.H.G., "Analytical Evaluation of Hierarchical Planning Systems". Operations Research, vol. 29, # 4, pp. 707-716, 1981.

24. Erol K., Nau D., and Hendler J., "HTN Planning: Complexity and Expressivity". In: AAAI-1994, Seattle, July 1994.

25. Grossmann I.E., "Mixed-Integer Non-linear Programming Techniques for the Synthesis of Engineering Systems". Res. in Eng. Design, Vol. 1, # 2/3, pp. 205-228, 1990.

26. Gunasekaran A., Korukonda A.R., Virtanen I. and Olli P. Yli, "Improving Productivity and Quality in Manufacturing Organizations". Intl. J. of Production Economics, vol. 36, # 2, 169-183, 1994.

27. Gupta A.P., Birmingham W.P. and Siewiorek D.P., Automating the Design of Computer Systems. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, # 4, pp. 473-487, 1993.

28. Hall M., Jr., Combinatorial Theory, 2nd ed., New York: Wiley, 1986.

29. Hammer M., and Champy J., "Reengineering the corporation: A manifesto for business revolution", Harper business, 1993.

30. Harhalakis G., Lin C.P., Nagi R. and Proth J.M., "Hierarchical Decision Making in Computer Integrated Manufacturing Systems". In: Proc. of the Third Int. Conf. on CIM. CS Press, pp. 15-24, 1992.

31. Knuth D.E. and Raghunathan A., "The Problem of Compatible Representatives". SIAM J. on Disc. Math., Vol. 5, # 3, pp. 422-427, 1992.

32. Kusiak A., "Artificial Intelligence and Integrated Manufacturing Systems". In: A. Kusiak (Ed.) Artificial Intelligence. Implications for CIM. Berlin: IFS (Publications) Ltd. and Springer-Verlag, 1988.

33. Levin M.Sh., "Hierarchical Design of User Interfaces". In: B. Blumenthal, J. Gornostaev, C. Unger (eds.), Human Computer Interaction. LNCS, vol.876, Berlin: Springer, pp. 140-151, 1994.

34. Levin M.Sh., "A Hierarchical Planning and Problem Solving: Approach to Interface Design". In: Proc. of Intl. Conf. on Human-Computer Interaction EWHCI'95, July 2-8, 1995, Moscow, Vol. 1, 180-187, 1995.

35. Levin M.Sh., "Towards Hypertexts and Decision Making." In: Proc. of Intl. Conf. on Human-Computer Interaction EWHCI'95, July 2-8, 1995, Moscow, Vol. 2, 22-37, 1995.

36. Levin M.Sh., Towards Combinatorial Models of Synthesis, Technical Report 96-1-002, The University of Aizu, 1996.

37. Levin M.Sh., "Hierarchical Morphological Multicriteria Design of Decomposable Systems". J. Concurrent Engineering: Research and Applications, vol. 4, no. 2, 1996, 111-118.

38. Levin M.Sh., "Combinatorial Analysis and Adaptation of Human-Computer Systems". Proc. of Intl. Conf. on Human Computer Interaction EWHCI'96, Moscow, 1996, 104-112.

39. Levin M.Sh., "Improvement of Decomposable Systems". Advances in Concurrent Engineering, 3rd ISPE Intl. Conf. on Concurrent Engineering, Toronto, 1996, 319-325.

40. Levin M.Sh., "Combinatorial Design in Hypertext". Proc. of 5th Intl. Conf. on Information Systems Development, Gdansk, 1996, 255-263.

41. Levin M.Sh., and Kaganov Yu.T., Hierarchical Design of Vibration Conveyor. In: Proc. of Intl. Conf. on "Information Technology in Design", Moscow, pp. 164-169, July 1996.

42. Liebisch D.C. and Jain A., "JESSI COMMON FRAMEWORK Design Management - The Means to Configuration and Execution of the Design Process". In: Proc. of EURO DAC'92. Los Alamitos: CS Press, pp. 552-557, 1992.

43. Martello S. and. Toth P, Knapsack Problem: Algorithms and Computer Implementation, New York: Wiley, 1990.

44. McDermott J., "R1: A Rule-Based Configurer of Computer Systems". Artificial Intelligence, vol. 19, # 2, pp. 39-88, 1982.

45. Muhanna W.A. and Pick R.A., "Meta-modeling Concepts and Tools for Model Management: A Systems Approach". Management Science, vol. 40, no. 9, pp. 1093-1123, 1994.

46. Reddy Y.V.R., Srinivas K., Jagannathan V. and Karinthi R., "Computer Support for Concurrent Engineering". Computer, vol. 26, # 1, January, pp. 12-15, 1993.

47. Singha J. and Katz J.L., "A Branch-And-Fathom Algorithm for the Long Range Process Design Problem". Manag. Sci., vol. 36, # 4, pp. 513-516, 1990.

48. Sriram D., Logcher R. and Fukuda S. (Eds.), Computer-Aided Cooperative Product Development. LNCS, vol. 492, Springer-Verlag, 1991.

49. Sykes E.A. and White C.C., III, "Multiobjective Intelligent Computer-Aided Design". IEEE Transactions on Systems, Man, and Cybernetics, vol. 21, # 6, pp. 1498-1511, 1989.

50. Tsukune H., Tsukamoto M., Matsushita T., Tomita F., Okada K., Ogasawara T., Takase K. and Yuba T., "Modular Manufacturing". J. of Intel. Manufacturing, vol. 4, no. 2, pp. 163-181, 1993.

51. Van Gigch J.P., Applied General Systems Theory. 2nd ed., Vol. 1 and 2, Harper and Row Publishers, 1978.

52. Zwicky F., Discovery Invention, Research Through the Morphological Approach. New York: McMillan, 1969.


Журнал "Автоматизация проектирования", #04, 1997 год // Издательство "Открытые системы" (http://www.osp.ru/)
Постоянный адрес статьи:
http://www.osp.ru/ap/1997/04/14.htm