[정보처리기사] CPM 네트워크 임계경로 Critical path, ES, EF, slack time

⭐ CPM 네트워크 용어정리

✔️ Critical Path (임계 경로)

프로젝트 완료에 필요한 최장 경로로, 여유시간이 0인 작업들로 구성됨

→ 지연되면 전체 프로젝트 일정이 늦어지는 작업들이다.

✔️ ES (Earliest Start, 최조 시작 시간)

해당 작업이 가장 빨리 시작할 수 있는 시점

✔️ EF (Earliest Finish, 최조 완료 시간)

해당 작업이 가장 빨리 완료될 수 있는 시점, ES + 작업 소요 시간

✔️ Slack Time (여유 시간, Float)

작업이 지연될 수 있는 최대 시간, Slack = LS - ES 또는 LF - EF

 

---

 

1. 다음은 소작업 리스트에서 작업 C의 가장 빠른 착수일, 가장 늦은 착수일, 여유 기간(slack time)을 순서대로 쓰시오

작업	선행작업	소요기간
A	-	15
B	-	10
C	A, B	10
D	B	25
E	C	15

 

🐦 작업 관계 정리 (네트워크 흐름)

• A, B는 독립적으로 시작할 수 있음
• C는 A와 B가 끝나야 시작 가능
• D는 B가 끝나야 시작 가능
• E는 C가 끝나야 시작 가능

 

🐦 작업별 Earliest Start (ES) 및 Earliest Finish (EF)
(각 작업이 가장 빨리 시작할 수 있는 시점과 가장 빨리 끝나는 시점)

작업	ES (시작)	EF (종료)	비고
A	0	15	A는 바로 시작 가능
B	0	10	B도 바로 시작 가능
C	max(15, 10) = 15	15 + 10 = 25	A, B 둘 다 끝나야 시작 가능
D	10	10 + 25 = 35	B가 끝난 후 시작 가능
E	25	25 + 15 = 40	C가 끝난 후 시작 가능

 

🐦 크리티컬 패스(임계경로) 
크리티컬 패스(Critical Path)는 가장 오래 걸리는 경로이며, 프로젝트의 최소 완료 기간
여러 경로가 있지만, 가장 긴 경로를 찾으면 됨

가능한 경로들 및 소요 기간
A → C → E = 15 + 10 + 15 = 40
B → C → E = 10 + 10 + 15 = 35
B → D = 10 + 25 = 35

결론
최장 경로는 A → C → E로 총 40일 소요
따라서, 크리티컬 패스는 A → C → E 이며, 프로젝트 완료 기간은 40일

 

🐦 작업 C의 Earliest Start(ES), Latest Start(LS), 여유시간(Float) 계산

 

✔️ 1. Earliest Start (ES)
작업 C는 A와 B가 끝나야 시작 가능
A의 Earliest Finish (EF): 15
B의 Earliest Finish (EF): 10

따라서, 작업 C의 Earliest Start (ES) = max(15, 10) = 15
작업 C의 소요기간이 10일이므로, Earliest Finish (EF) = 15 + 10 = 25

✔️ 2. Latest Finish (LF)
작업 C의 후속 작업은 E이고,
작업 E의 Latest Start (LS) = 25 (E가 늦어도 25일에는 시작해야 함).
따라서, C의 Latest Finish (LF) = 25
작업 C의 소요기간이 10일이므로, Latest Start (LS) = 25 - 10 = 15

✔️ 3. Float (여유시간)
Float(여유시간) = LS - ES = 15 - 15 = 0
→ 작업 C는 크리티컬 경로에 속하므로 여유시간이 없음
즉, 작업 C가 지연되면 프로젝트 전체 일정도 지연됨

 

✅ 정답: 15일, 15일, 0일
작업 C는 15일에 시작해야 하며, 늦어도 15일에 시작해야 한다.
여유시간이 0일이므로, 지연되면 프로젝트 전체 일정이 늦어짐.

---

2. 다음은 프로젝트의 계획 단계에서 수립한 CPM 네트워크의 작업 목록표이다. 프로젝트 완료에 필요한 최소 시간은?

작업	선행작업	소요기간
A	D	15
B	A, D, E	10
C	E	15
D	-	5
E	-	10
F	A, B	20
G	B, C	15

 

🐦 작업 관계 정리 (네트워크 흐름)

• D와 E는 선행 작업이 없으므로 가장 먼저 시작 가능
• A는 D가 끝난 후 시작 가능
• B는 A, D, E가 모두 끝나야 시작 가능
• C는 E가 끝난 후 시작 가능
• F는 A와 B가 끝난 후 시작 가능
• G는 B와 C가 끝난 후 시작 가능

🐦  Earliest Start (ES) 및 Earliest Finish (EF) 
(각 작업이 가장 빨리 시작할 수 있는 시점과 가장 빨리 끝나는 시점)

D 시작 → D 종료

▶ ES = 0, EF = 5 (5일 소요)

E 시작 → E 종료

▶ ES = 0, EF = 10 (10일 소요)

A 시작 → A 종료
▶ ES = D의 EF = 5, EF = 5 + 15 = 20

B 시작 → B 종료
▶ B의 선행 작업은 A, D, E
▶ A의 EF = 20, D의 EF = 5, E의 EF = 10 → 가장 늦은 A의 EF가 기준이 됨
▶ ES = 20, EF = 20 + 10 = 30

C 시작 → C 종료
▶ C의 선행 작업은 E
▶ E의 EF = 10
▶ ES = 10, EF = 10 + 15 = 25

F 시작 → F 종료
▶ F의 선행 작업은 A, B
▶ A의 EF = 20, B의 EF = 30 → 가장 늦은 B의 EF가 기준
▶ ES = 30, EF = 30 + 20 = 50

G 시작 → G 종료
▶ G의 선행 작업은 B, C
▶ B의 EF = 30, C의 EF = 25 → 가장 늦은 B의 EF가 기준
▶ ES = 30, EF = 30 + 15 = 45

 

 

🐦 임계경로(Critical Path) = 프로젝트의 최소 완료 시간
프로젝트 완료 시간은 모든 작업이 끝나는 가장 늦은 시점을 찾는 것!

경로 1: D → A → B → F
5 + 15 + 10 + 20 = 50일

경로 2: E → B → F
10 + 20 + 20 = 50일

경로 3: E → C → G
10 + 15 + 15 = 40일 (짧음, 크리티컬 패스 아님)

✅ 프로젝트 완료 최소 시간: 50일
✅ Critical Path: D → A → B → F 또는 E → B → F
즉, 프로젝트를 50일 안에 완료하려면 A, B, F 또는 E, B, F가 지연되지 않아야 함