공정 그래프
Process graph수학 그래프 이론에서 공정 그래프 또는 P-그래프는 워크플로우 모델링에 사용되는 유도 쌍방향 그래프다.
설명
공정 그래프에서 그래프의 정점은 작동(O)과 재료(M)의 두 가지 유형이다.이 꼭지점 유형은 두 개의 이형 세트를 형성한다.그래프의 가장자리는 O와 M 정점을 연결한다.M이 O의 출력인 경우, 예를 들어 '쓰기'(작동)에 의해 출력되는 '문서'(재료)와 같이, 작동 정점(O)에서 나오는 에지는 재료 정점(M)에 연결된다.M에서 O까지의 가장자리는 M이 O의 입력 집합의 요소임을 나타낸다. 예를 들어 문서는 '검토' 작업에 대한 입력의 일부일 수 있다.
적용들
프로세스 그래프는 PNS(Process Network Synthetic)에서 응용 프로그램의 다른 분야에서 사용되고 있다.[1] 응용 프로그램의 예는 Process Network Synthisation이다.[2]이 방법은 화학 공식, 에너지 기술 네트워크 및 건물이나 운송 경로의 피난 경로와 같은 기타 최적화 문제에서 최적의 프로세스 체인을 찾기 위해 과학적으로 사용된다.공정 그래프는 다중 스레드 공정의 제어 흐름을 이해하는 데도 사용된다.실행 중인 동시 스레드가 n개인 경우 프로세스 그래프는 n개의 동시 스레드의 실행과 n차원 데카르트 평면을 통한 궤적을 모델링한다.그래프의 원점은 스레드가 명령을 완료하지 않은 초기 상태에 해당한다.각 지시된 가장자리는 명령의 실행과 다른 명령으로의 전환에 해당한다.프로그램이 가장자리를 왼쪽 또는 아래로 뒤로 실행할 수 없기 때문에 유효한 가장자리는 위 또는 오른쪽으로 이동할 수 있다.두 개의 스레드가 동일한 명령을 동시에 완료할 수 없기 때문에 대각선 가장자리는 허용되지 않는다.
참조
- ^ Friedler, F.; Huang, Y.W.; Fan, L.T. (1992). "Combinatorial Algorithms for Process Synthesis". Computers Chemical Engineering. 16 Suppl. 1: 313–320. doi:10.1016/S0098-1354(09)80037-9.
- ^ Friedler, F.; Varga, J. B.; Feher, E.; Fan, L. T. (1996). "Combinatorially Accelerated Branch-and-Bound Method for Solving the MIP Model of Process Network Synthesis". State of the Art in Global Optimization. Nonconvex Optimization and Its Applications. Vol. 7 (7 ed.). Dordrecht: Kluwer Academic Publishers. pp. 609–626. doi:10.1007/978-1-4613-3437-8_35. ISBN 978-0-7923-4351-6.
