AOE Network( 작업 공정의 최장, 최단 시간 알아보기 )

A,B,C,D 작업을 간선으로 하여 공정을 의미하게 하는 것 AOV Network

[AOE Network]

C라는 작업은 A 가 걸처와야 작업이 가능하고

B라는 작업도 A 가 걸처와야 작업이 가능하다

D 라는 작업은 B,C 가 거처 와야지만 가능하다

AOE 처럼 하게 되다 보면 비용이 0(더미 엣지) 인 간선이 생길 수 있다

그런데 c,d 를 제거 하면 되지 안느냐 라는 의문이 생길 수 있는데

제거 하게 되면 b 와 e 의 중간 에 있는 작업들이 구분이 되지 않게 된다 => 어떤 작업이 끝나는지 명확히 구분하기 힘들다

그래서 중간에 비용이 0 인 더미 간선을 둔다 그러면서 c,d 를 두게 된다

그런데 c 는 없고 d 만 존재해도 가능한 형태이다

* b,e 사이에 C 가 있고 d,e 사이에 c 가 있으므로 구문이 가능하다

---

A ,B 중간에 있는 숫자가 소요 시간

전체 공정이 완료되는 시간은 최대 비용을 찾으면 된다

A->B->C->D->E->I->K->L->M 이 최대 비용 이 작업을 임계 작업이라 한다

이 작업들이 작업들이 실제로 작업 공정에 전체 완료 일자에 큰 영향을 미치므로

=> 이 공정에서 시간을 줄이면 새로운 임계경로가 잡히게 된다

즉 무엇을 줄여야 임계작업을 줄일 수 있는지를 알아 보는것이 AOV NetWork 이다

---

위의 아래 그래프에서는 위로 가는 쪽이 임계작업(임계경로)이다 (9)

최장시간, 최단시간은 C++ 알고리즘 참고

최장, 최단 시간은 각 노드에서 걸리는 최장, 최단 시간을 말한다