임계 경로법

최적설계 소프트웨어 마지막 수정: 2026-08-29 04:38:05

1. 개요[편집]

임계 경로법 Critical Path Method, CPM
대상	활동 네트워크(선후 관계가 있는 작업들) — 유향 비순환 그래프
계산	전진 스윕(ES·EF) + 후진 스윕(LS·LF)
임계 판정	총여유 $TF = LS - ES = 0$
수학적 정체	DAG 최장경로 = 위상 정렬 후 동적 계획법
복잡도	$\Theta(V+E)$
기원	CPM: 듀폰·레밍턴랜드(1957) / PERT: 미 해군 폴라리스(1958)
같은 뼈대	정적 타이밍 분석 · 병렬 빌드의 span · DAG DP

임계 경로법(Critical Path Method, CPM)은 선후 관계와 소요 시간이 주어진 작업들의 네트워크에서, 전체 완료 시각을 결정하는 가장 긴 경로를 찾고 각 작업이 가진 시간 여유를 계산하는 절차다. 그 가장 긴 경로 위의 작업들을 임계 작업이라 부르고, 이들은 정의상 여유가 0 이라 하루라도 늦어지면 프로젝트 전체가 그만큼 늦는다.

건설·플랜트 공정표의 대명사로 알려져 있지만, 이 문서를 시뮬레이션 위키에 두는 이유는 따로 있다. **CPM 은 이름만 경영 기법이고 내용물은 위상 정렬 뒤에 붙는 두 줄짜리 동적 계획법**이다. 그리고 그 두 줄이 프로젝트 관리를 벗어난 곳 — 반도체의 정적 타이밍 분석, 병렬 빌드의 이론적 하한, 병렬 알고리즘의 span 분석 — 에서 이름만 바꿔 똑같이 돌고 있다. 1957년의 공정표와 오늘의 STA 도구가 같은 알고리즘이라는 사실이 이 주제의 요점이다.¹

2. 활동 네트워크[편집]

작업(activity)과 선후 제약을 그래프로 옮기는 방식이 역사적으로 둘이다.

AOA(activity-on-arrow) — 간선이 작업, 정점이 이정표(event). 초기 PERT/CPM 의 표기. 선후 관계를 정확히 표현하려면 소요 시간 0 짜리 더미 활동을 끼워 넣어야 하는 경우가 생겨 도표가 지저분해진다.
AON(activity-on-node) — 정점이 작업, 간선이 선후 제약. 더미가 필요 없고 “끝-시작” 말고 “시작-시작”, “끝-끝” 같은 관계와 지연(lag)을 붙이기도 쉬워서, 오늘날 소프트웨어는 사실상 전부 이쪽이다.

어느 쪽이든 필수 조건은 하나다. 사이클이 없어야 한다. 작업 A 가 B 뒤에 오고 B 가 A 뒤에 온다면 시작할 수 있는 작업이 없다. 그래서 실무 도구의 “순환 종속성” 오류는 위상 정렬 실패를 사용자 언어로 번역한 것이고, 진단을 제대로 하려면 강한 연결 요소로 사이클 덩어리를 통째로 짚어 줘야 한다. CPM 의 모든 계산은 그래프가 DAG 라는 가정 위에 서 있다.

3. 전진 스윕과 후진 스윕[편집]

작업 $i$ 의 소요 시간을 $d_i$ 라 하자. 위상 순서대로 한 번 훑으며 가장 이른 시각을 채운다.

ES_i \;=\; \max_{j \to i} EF_j, \qquad EF_i \;=\; ES_i + d_i

선행자가 없는 작업은 $ES = 0$ 이다. 마지막에 얻는 $\max_i EF_i$ 가 프로젝트 최소 공기다. 이제 역위상 순서로 되돌아 나오며 가장 늦은 시각을 채운다.

LF_i \;=\; \min_{i \to j} LS_j, \qquad LS_i \;=\; LF_i - d_i

후속자가 없는 작업의 $LF$ 는 프로젝트 완료 시각(또는 계약 납기)으로 둔다. 두 스윕이 끝나면 작업마다 네 개의 시각이 생기고, 여기서 여유가 두 종류로 나온다.

총여유(total float) $TF_i = LS_i - ES_i = LF_i - EF_i$ . 전체 공기를 늘리지 않고 이 작업을 미룰 수 있는 최대 시간.
자유여유(free float) $FF_i = \min_{i \to j} ES_j - EF_i$ . 후속 작업의 가장 이른 시작을 건드리지 않고 미룰 수 있는 시간.

항상 $0 \le FF_i \le TF_i$ 다. 둘의 구분이 실무에서 중요한 이유는, 총여유는 경로 위 작업들이 공유하는 자원이기 때문이다. 여유 5일짜리 경로에 작업이 셋 있으면 각각 $TF = 5$ 로 표시되지만, 그중 하나가 5일을 다 쓰면 나머지 둘의 여유는 0 이 된다. 소프트웨어가 뿌려 주는 총여유 숫자를 작업별 독립 예산으로 읽고 세 작업을 동시에 미뤘다가 공기가 밀리는 것은, 이 바닥에서 매년 재현되는 사고다. 자유여유는 그런 공유가 없어서 진짜 “혼자 써도 되는” 몫이다.

납기가 최소 공기보다 앞이면 $TF < 0$ 인 음의 여유가 나온다. 값 자체가 “얼마나 부족한가”를 정량화해 주므로, 공정 압축(crashing) 대상을 고르는 출발점이 된다.

4. 사실은 DAG 최장경로다[편집]

위 두 스윕은 새로울 것이 없다. 전진 스윕은 정확히 DAG 위의 최장경로 동적 계획법이고, 후진 스윕은 그 수반(adjoint) 계산이다. 일반 그래프의 최장경로는 NP-완전이지만(해밀턴 경로가 특수 사례), 사이클이 없다는 조건 하나로 문제가 $\Theta(V+E)$ 로 무너진다.

임계 경로의 정확한 정의도 여기서 나온다. 시작에서 끝까지 이어지는 경로 중 길이가 최대인 것이며, 동치로 경로 위 모든 작업의 총여유가 0 인 경로다. 주의할 점 두 가지.

임계 경로는 여러 개일 수 있다. 같은 길이의 경로가 여럿이면 전부 임계다. 실제 대형 공정에서는 임계 경로가 하나뿐인 경우가 오히려 드물다.
” $TF = 0$ 인 작업들의 집합”이 곧 하나의 경로는 아니다. 임계 작업들을 모으면 여러 갈래가 나오고, 그것들을 이어 붙여야 경로가 된다. 소프트웨어가 임계 경로를 굵은 선으로 그려 줄 때 갈래가 여러 개 보이는 이유다.

전진·후진 두 번의 스윕이라는 골격은 위상 정렬 문서가 짚듯 자동 미분의 순방향 평가 + 역방향 수반 누적과 정확히 같은 형태다. 최장경로 DP 의 $\max$ 를 합으로 바꾸면 경로 개수 세기가, 확률의 곱으로 바꾸면 신뢰도 계산이 되는 식으로, 같은 두 스윕에 다른 반환(semiring)을 얹는 것이 이 계열 알고리즘의 공통 문법이다.

CPM 이 못 하는 것도 분명히 해 두자. 자원 제약이 없다. 작업 A 와 B 가 선후 관계가 없다고 CPM 은 동시에 시켜 버리는데, 크레인이 한 대뿐이면 불가능하다. 자원 제약을 넣은 자원 제약 프로젝트 스케줄링 문제(RCPSP)는 NP-난해이고, 상용 도구의 “자원 평준화” 버튼은 그 위의 휴리스틱이다. 즉 CPM 이 선형 시간인 것은 문제를 쉬운 부분만 잘라 냈기 때문이다.²

5. PERT — 3점 추정과 그 함정[편집]

CPM 이 듀폰의 정비 공사 일정에서 나온 결정론적 도구라면, 거의 같은 시기에 미 해군 폴라리스 미사일 개발에서 나온 PERT(Program Evaluation and Review Technique)는 소요 시간이 불확실하다는 전제에서 출발한다. 각 작업에 대해 세 개의 값을 받는다 — 낙관치 $a$ , 최빈치 $m$ , 비관치 $b$ . 그리고 베타분포를 가정해 다음 근사를 쓴다.

t_e \;=\; \frac{a + 4m + b}{6}, \qquad \sigma \;=\; \frac{b-a}{6}, \qquad \sigma^2 = \left(\frac{b-a}{6}\right)^{\!2}

$t_e$ 로 CPM 을 돌려 임계 경로를 찾고, 그 경로 위 작업들의 분산을 더한 뒤 중심극한정리로 완료 시각을 정규분포로 취급해 “납기를 지킬 확률”을 계산한다. 절차만 보면 그럴듯한데, 여기에 세 겹의 문제가 있다.

첫째, 계수 자체가 근사다. $(a+4m+b)/6$ 과 $(b-a)/6$ 은 특정 베타분포족을 가정하고 손으로 계산하기 쉽게 다듬은 공식이지, 임의의 베타분포에서 성립하는 항등식이 아니다. 특히 $\sigma = (b-a)/6$ 은 “범위가 표준편차 6개분”이라는 정규분포식 어림이라, 분포가 치우칠수록 분산을 과소평가한다.

둘째, 세 숫자를 받는 방식 자체가 흔들린다. 사람은 비관치를 지독하게 과소평가한다. $b$ 를 “최악”이 아니라 “좀 나쁜 경우”로 적어 내는 순간, 위 공식 전체가 낙관 쪽으로 통째로 밀린다.

셋째, 그리고 가장 구조적인 것 — 병합 편향(merge bias). 결정적 임계 경로 하나만 보고 확률을 계산한다는 발상 자체가 틀렸다. 어떤 작업이 여러 선행 작업을 기다린다면 그 시작 시각은 선행자들의 최댓값이고, 최댓값에는 젠센 부등식이 그대로 작동한다.

\mathbb{E}\bigl[\max(X_1,\dots,X_k)\bigr] \;\ge\; \max\bigl(\mathbb{E}[X_1],\dots,\mathbb{E}[X_k]\bigr)

즉 평균값을 넣고 계산한 완료 시각은 실제 기댓값의 하한이다. 게다가 임계 경로가 아닌 “거의 임계”인 경로도 확률적으로 얼마든지 임계가 될 수 있는데, PERT 는 그 가능성을 아예 세지 않는다. 병렬 경로가 많고 길이가 비슷할수록 편향이 커져서, 고전적인 분석 사례에서 20~30 % 수준의 과소추정이 보고돼 있다.³ **“공정을 잘게 쪼개고 병렬로 많이 돌릴수록 PERT 는 더 낙관적으로 거짓말한다”**는 것이 이 편향의 실무적 요약이다.

정직한 해법은 하나뿐이다. 경로 하나가 아니라 네트워크 전체를 몬테카를로 방법으로 굴린다. 작업마다 소요 시간 분포에서 표본을 뽑아 매 회 CPM 을 통째로 다시 돌리고, 완료 시각의 분포와 함께 각 작업이 임계 경로에 포함된 비율(임계도 지수, criticality index)을 센다. 한 번 계산이 선형 시간이므로 수만 회 반복도 싸고, 결정론적 CPM 이 못 주는 정보 — “이 작업은 평소엔 여유가 있지만 15 % 확률로 임계가 된다” — 가 나온다. 요즘 리스크 분석 도구가 하는 일이 이것이며, 여기에 라틴 하이퍼큐브 표본추출이나 작업 간 상관을 넣은 코퓰라 모델링이 얹힌다. 상관을 무시하면(현실에서 지연은 함께 온다) 또 한 번 낙관 쪽으로 틀린다.

여담으로, 골드랫이 1997년에 제안한 임계 사슬(critical chain)은 이 문제를 통계가 아니라 행동 쪽에서 공격한다. 작업마다 개인이 숨겨 둔 안전 여유를 걷어내 프로젝트 끝단의 버퍼로 모으고, 자원 제약까지 반영한 사슬을 관리 대상으로 삼는다. “각 작업에 여유를 나눠 주면 파킨슨 법칙과 학생 증후군으로 그 여유가 전부 소진된다”는 관찰이 근거다. 통계적으로도 일리가 있다 — 분산은 따로 두는 것보다 모아 두는 편이 상대적으로 작다.

6. 같은 뼈대의 다른 이름들[편집]

정적 타이밍 분석(STA) — 디지털 회로의 셀과 배선을 정점·간선으로 놓으면 그대로 DAG 다. 전진 스윕으로 각 노드의 도착 시각(arrival time)을, 후진 스윕으로 요구 시각(required time)을 구하고, 그 차이가 슬랙이다. 슬랙이 음수인 경로가 타이밍 위반이고, 슬랙 0 인 경로가 임계 경로다. 용어만 ES/LS 에서 arrival/required 로 바뀌었을 뿐 식이 같다. 다른 점은 규모(수억 개 노드)와, 실제로는 전기적으로 활성화될 수 없는 거짓 경로(false path)를 걸러내야 한다는 것 — 순수 그래프 문제였다면 없었을 골칫거리다. SPICE 급 회로 시뮬레이션으로 전 경로를 다 확인하는 것이 불가능하기 때문에 이 정적 근사가 존재한다.
병렬 빌드와 span — make -j 로 코어를 아무리 늘려도 빌드 시간은 의존성 DAG 의 최장경로 아래로 내려가지 않는다. 병렬 알고리즘 분석에서 총 작업량 $T_1$ 과 임계 경로 길이 $T_\infty$ (span, depth)를 잡고 $T_p \le T_1/p + T_\infty$ 로 프로세서 $p$ 개일 때의 시간을 경계 짓는 그 $T_\infty$ 가 바로 임계 경로다. 병렬화 여지의 상한을 정하는 것은 코어 수가 아니라 그래프의 깊이라는 이야기이며, 빌드 시스템 개선이 어느 순간부터 효과가 없어지는 이유이기도 하다.
공정·생산 스케줄링 — 공정 스케줄링과 작업장 스케줄링에서 CPM 은 자원 제약을 넣기 전의 하한을 준다. “이 하한도 못 맞추는 납기”라면 자원을 아무리 잘 배치해도 소용없으니, 협상 자료로 먼저 써먹는 숫자다.
시뮬레이션 워크플로 — 전처리·격자 생성·솔버·후처리가 얽힌 해석 파이프라인, 다분야 최적화의 분야별 해석 순서, HPC 작업 의존성 그래프. 어느 단계를 빠르게 만들어야 전체가 빨라지는지 묻는 순간 이미 임계 경로를 계산하고 있는 것이고, 임계 경로 위에 없는 단계를 최적화하는 것은 총여유를 태우는 짓이다. 암달의 법칙이 말하는 것과 같은 이야기를 그래프 언어로 하는 셈.

7. 관련 문서[편집]

위상 정렬 · 깊이 우선 탐색 · 강한 연결 요소 · 동적 계획법
다익스트라 알고리즘 · 벨만-포드 알고리즘 · 네트워크 흐름
NP-완전 · 조합 최적화 · 정수계획법 · 공정 스케줄링
몬테카를로 방법 · 불확실성 정량화 · 중심극한정리 · 라틴 하이퍼큐브 표본추출
정적 타이밍 분석 · 빌드 시스템 · 암달의 법칙 · 자동 미분

CPM 은 1957년 듀폰의 모건 워커와 레밍턴랜드의 제임스 켈리가 화학 플랜트 정비 공사 일정을 UNIVAC 으로 계산하려다 나왔고, PERT 는 1958년 미 해군 특수사업국이 폴라리스 잠수함발사탄도미사일 개발을 관리하려고 부즈앨런·록히드와 함께 만들었다. 폴라리스가 예정보다 2년 빨리 끝난 공을 PERT 가 가져갔는데, 나중의 분석들은 그 성과 대부분이 실제로는 정치적 우선순위와 예산 덕이었고 PERT 는 훌륭한 홍보물이었다고 본다. 그래도 그 홍보 덕에 온 세상이 화살표 도표를 그리게 됐으니 역사적 공은 확실하다. ↩
자원 제약을 빼는 것이 왜 결정적인가 하면, RCPSP 는 작업 30개짜리 표준 벤치마크(PSPLIB j30)조차 한동안 미해결 인스턴스가 남아 있던 문제이기 때문이다. 정점 수만 개짜리 CPM 이 눈 깜짝할 사이에 끝나는 것과 대비하면, “크레인이 한 대”라는 조건 하나가 문제의 계산 등급을 통째로 바꿔 놓는 셈이다. ↩
MacCrimmon, K. R. & Ryavec, C. A. (1964). “An analytical study of the PERT assumptions”. Operations Research 12(1), 16–37. 병합 편향과 3점 추정 근사 오차를 정량적으로 분해한 고전이다. 네트워크 전체를 표본추출로 굴려 이 편향을 우회하자는 제안은 Van Slyke, R. M. (1963), “Monte Carlo methods and the PERT problem”, Operations Research 11(5), 839–860 이 처음이다. 요약하면 1963년에 이미 답이 나와 있었는데 60년째 평균값 하나를 공정표에 적고 있다는 이야기. ↩