Задачи комбинаторного синтеза сложных систем из их частей (подсистем, компонентов и т. п.) являются важным практическим направлением во многих приложениях (техника, экономика и др.). Часто такой подход называют модульным проектированием (например, разработка программного обеспечения, проектирование электронных систем и др.) или планированием (например, модульное планирование в производственных системах).
Введение
В последние годы значимость модульного подхода резко возрастает, поскольку во многих областях созданы и создаются библиотеки и каталоги компонентов (локальных решений) или такие локальные решения можно получить за счет информационного анализа имеющихся баз данных и/или заказать. Иными словами, проектирование сложных решений во многих приложениях теперь основывается на подборе локальных проектных вариантов и композиции их в результирующую систему.
Очевидно, что широкое применение такого композиционного подхода к проектированию сложных систем требует разработки или переосмысления следующего:
Следует отметить, что в России накоплен значительный опыт по проектированию сложных систем, часто базирующийся именно на модульном проектировании. Приведем несколько примеров научных направлений указанного типа:
В данной статье кратко описываются декомпозируемые системы и основные операции для них (представление, оценивание, выявление узких мест, сравнение, отбор вариантов, синтез, модификация), иерархическое комбинаторное проектирование и реинжиниринг систем, приложения.
Отметим, что предложенная схема проектирования декомпозируемых систем - "Иерархическое Морфологическое Многокритериальное Проектирование" (ИММП), хотя и похожа на иерархические подходы к проектированию, принятию решений, на генетические методы решения задач, отличается от них, в частности, учетом порядковой совместимости элементов составных решений.
Декомпозируемые системы
Под декомпозируемой системой мы понимаем следующее: система состоит из частей (компонентов); для каждой части имеется или может быть сформировано некоторое множество альтернативных проектных вариантов (ПВ).
Мы рассматриваем детерминированные комбинаторные задачи, направленные на композицию декомпозируемых систем из компонентов. Дополнительно мы учитываем парные взаимосвязи (С) или совместимость между ПВ.
Часто реальные системы требуют многоуровневого описания или такое описание целесообразно использовать (например, для уменьшения исходной размерности). Приведем перечень основных функциональных операций, требуемых при проектировании, анализе и преобразовании декомпозируемых систем:
Программные модули и блоки данных, элементы маршрутов, модели из проектных библиотек, тесты и средства верификации и их комбинации могут рассматриваться как указанные выше ПВ. Наша задача может быть рассмотрена как составная. Отметим, что мы не рассматриваем модели синтеза, подобные тем, которые используются в химии (синтез химических продуктов и др.).
Пример декомпозируемой системы представлен на рис. 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).
Проектирование
Задача композиции является важной частью процесса проектирования в различных проектных дисциплинах. Укажем некоторые западные проектные методологии, которые включают такой этап в рамках общей схемы проектирования:
Рассматриваемый в работе подход к проектированию декомпозируемых систем ИММП включает следующие стадии:
Укажем базовые предположения, используемые в ИММП:
Обычно для перечисленных задач применяются следующие подходы:
ИММП описан в работах [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хема решения состоит из:
Предложенная задача морфологической клики близка к ряду известных моделей и подходов к проектированию [3, 20, 28, 31, 43, 47, 52].
Для анализа сложных решений мы используем элементы двух типов ПВ и C в отношении решения S: S-улучшающие, S-нейтральные и S-ухудшающие элементы по вектору N, где S-ухудшающие элементы рассматриваются как "узкие места", которые должны быть улучшены.
Алгоритм анализа и улучшения заключается в следующем:
Синтез последовательно-параллельной стратегии
Многостадийное планирование используется в экономике, производственных системах, при решении сложных проблем в искусственном интеллекте [45]. На рис. 3 представлены два примера последовательно-параллельных стратегий для четырехстадийной задачи.
Отметим, что последовательно-параллельный процесс соответствует дерево-декомпозируемому графу, т. е. возможна декомпозиция исходного графа на базе дерева "происхождения". Другие дерево-декомпозируемые графы (например, деревья, частичные k-деревья) исследуются в работе [18]. В нашем случае мы используем структуру, которая подобна И-ИЛИ дереву.
Мы рассматриваем композицию схемы решения на основе ИММП, в том числе последовательно-параллельную композицию составных ПВ для обработки данных с учетом С между ПВ. В этом приложении С соответствует совместимости последовательных ПВ (локальных процедур решения для конкретного периода) и независимости параллельных ПВ.
Общая схема проектирования последовательно-параллельной стратегии включает следующие этапы:
1. Построение (описание) базовой иерархической модели стратегии (морфологии).
2. Анализ и отбор элементов исходной модели с целью формирования рабочей морфологии стратегии.
3. Композиция последовательно-параллельной стратегии на основе ИММП.
Примеры построения стратегий описаны в литературе [34, 36].
Трансформация декомпозируемых систем
Трансформация (улучшение, преобразование, реинжиниринг и т. п.) сложных систем исследуются в различных дисциплинах [17, 21, 26, 29].
В общем случае можно указать два повода для проектирования систем [51]:
В первом случае происходит эволюционное улучшение и многокритериальный отбор проектных альтернатив [14, 19, 49].
В работе [39] представлен многостадийный процесс трансформации декомпозируемой новой системы. На каждой стадии на основе ИММП формируется некая композиция действий по трансформации (улучшению) системы.
На верхнем иерархическом уровне осуществляется композиция стадийных составных действий в комплексную многостадийную стратегию улучшения (также на основе ИММП).
Заметим, что иерархические подходы применяются многие годы, например:
Приложения
Укажем опубликованные примеры применения ИММП:
Заключение
Следует указать некоторые теоретические и практические направления, которые представляются важными:
Литература
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.