График процесса

В математической теории графов граф процесса или P-граф — это ориентированный двудольный граф, используемый при рабочих процессов моделировании .

Описание

В графе процесса вершины графа . бывают двух типов: операции (O) и материала (M) Эти типы вершин образуют два дизъюнктивных множества . Ребра графа соединяют вершины O и M. Ребро операционной вершины (O) соединяется с материальной вершиной (M), если M является выходом O, например, «документ» (материал), который выводится с помощью «описания» (операции). Край от M до O указывает, что M является элементом входного набора O, например, документ может быть частью входных данных для операции «просмотра».

Приложения

Граф процесса используется в различных областях применения в Синтезе сети процессов (PNS). ^[1] Примером приложения является Process Network Synthesis . ^[2] Этот метод используется в научных целях для поиска оптимальных технологических цепочек в химических формулах, энергетических технологических сетях и других задачах оптимизации, таких как маршруты эвакуации в зданиях или маршруты транспортировки.Графы процессов также используются для понимания потока управления многопоточными процессами. Если одновременно выполняются n потоков, граф процесса моделирует выполнение n параллельных потоков и их траектории через n-мерную декартову плоскость. Начало графа соответствует начальному состоянию, когда ни один из потоков не завершил инструкцию. Каждое направленное ребро соответствует выполнению одной инструкции и переходу к другой. Допустимые ребра могут идти либо вверх, либо вправо, поскольку программы не могут работать в обратном направлении для ребер влево или вниз. Поскольку два потока не могут одновременно выполнить одну и ту же инструкцию, диагональные ребра не допускаются.

Ссылки

^ Фридлер, Ф.; Хуанг, Ю.В.; Фан, LT (1992). «Комбинаторные алгоритмы синтеза процессов». Компьютеры Химическая инженерия . 16 (Приложение 1): 313–320. дои : 10.1016/S0098-1354(09)80037-9 .
^ Фридлер, Ф.; Варга, Дж.Б.; Фехер, Э.; Фан, LT (1996). «Комбинаторно-ускоренный метод ветвей и границ для решения MIP-модели синтеза технологической сети». Современное состояние глобальной оптимизации . Невыпуклая оптимизация и ее приложения. Том. 7. Дордрехт: Академическое издательство Kluwer. стр. 609–626. дои : 10.1007/978-1-4613-3437-8_35 . ISBN 978-0-7923-4351-6 .

Внешние ссылки

[1] Фридлер, Ф.; Хуанг, Ю.В.; Фан, LT (1992). «Комбинаторные алгоритмы синтеза процессов». Компьютеры Химическая инженерия . 16 (Приложение 1): 313–320. дои : 10.1016/S0098-1354(09)80037-9 .

[2] Фридлер, Ф.; Варга, Дж.Б.; Фехер, Э.; Фан, LT (1996). «Комбинаторно-ускоренный метод ветвей и границ для решения MIP-модели синтеза технологической сети». Современное состояние глобальной оптимизации . Невыпуклая оптимизация и ее приложения. Том. 7. Дордрехт: Академическое издательство Kluwer. стр. 609–626. дои : 10.1007/978-1-4613-3437-8_35 . ISBN 978-0-7923-4351-6 .

[1]

[2]