Grafo de proceso

En la teoría de grafos matemáticos, un grafo de proceso o P-grafo es un grafo bipartito dirigido que se utiliza en el modelado de flujos de trabajo .

En un grafo de procesos, los vértices son de dos tipos: operación (O) y material (M). Estos tipos de vértices forman dos conjuntos disyuntivos . Las aristas del grafo conectan los vértices O y M. Una arista desde un vértice de operación (O) se conecta a un vértice de material (M) si M es el resultado de O, como un documento (material) generado por una operación de redacción. Una arista de M a O indica que M es un elemento del conjunto de entrada de O; por ejemplo, un documento puede ser parte de la entrada de una operación de revisión.

El grafo de procesos se utiliza en diferentes campos de aplicación en la síntesis de redes de procesos (PNS). ^{[ 1 ]} Un ejemplo de aplicación es la síntesis de redes de procesos . ^{[ 2 ]} El método se utiliza científicamente para encontrar cadenas de procesos óptimas en fórmulas químicas, redes de tecnología energética y otros problemas de optimización como rutas de evacuación en edificios o rutas de transporte. Los grafos de procesos también se utilizan para comprender el flujo de control de procesos multihilo. Si hay n hilos concurrentes ejecutándose, un grafo de procesos modela la ejecución de n hilos concurrentes y sus trayectorias a través de un plano cartesiano n-dimensional. El origen del grafo corresponde al estado inicial donde ninguno de los hilos ha completado una instrucción. Cada arista dirigida corresponde a la ejecución de una instrucción y la transición a otra. Las aristas válidas pueden ir hacia arriba o hacia la derecha porque los programas no pueden retroceder para las aristas hacia la izquierda o hacia abajo. Dado que dos hilos no pueden completar la misma instrucción al mismo tiempo, no se permiten aristas diagonales.

• Wiki de P-Graph
• Definición del problema de síntesis de redes de procesos