임계 경로법(CPM)란?

프로젝트 작업의 소요 일수와 순서 관계로부터 각 작업의 가장 이른·가장 늦은 시작일과 여유 일수(플로트)를 구하고, 여유가 0인 작업을 이은 가장 긴 경로(임계 경로)와 전체 소요 일수를 구하는 일정 관리 기법. 임계 경로 위의 작업이 늦어지면 전체가 늦어진다.

일본어 명칭: クリティカルパス法(CPM)

임계 경로법(CPM)은(는) 소프트웨어 개발과 프로젝트 관리 등 1개 분야의 연습 문제 1개에 나와요.

분야: 소프트웨어 개발과 프로젝트 관리

가장 이른 시작일과 가장 늦은 시작일

앞에서부터 차례로, 선행 작업이 모두 끝나는 날 중 가장 늦은 날을 가장 이른 시작일로 구하면, 마지막 작업의 가장 이른 종료일이 전체 소요 일수가 됩니다. 다음으로 뒤에서부터 차례로, 전체를 늘리지 않기 위해 늦어도 시작해야 하는 날을 가장 늦은 시작일로 구합니다. 가장 늦은 시작일 − 가장 이른 시작일이 그 작업의 여유 일수(총 여유, 토털 플로트)이며, 이것이 0인 작업을 이은 경로가 임계 경로입니다. 예를 들어 A(6일) → D(4일) → F(3일)가 13일로 가장 길다면, A, D, F 중 어느 것이 1일 늦어지면 전체도 1일 늦어집니다.

화살표 다이어그램과 더미 작업

일본의 정보처리기술자시험에서는 작업을 화살표로, 작업의 구분을 결합점(원)으로 나타내는 화살표 다이어그램(PERT도)이 자주 쓰입니다. 화살표만으로는 나타낼 수 없는 순서 관계는 소요 일수 0인 더미 작업(점선 화살표)으로 나타냅니다. 예를 들어 작업 D를 시작하려면 B뿐만 아니라 A도 끝나 있어야 할 때, A의 끝점에서 D의 시작점으로 더미 작업을 긋습니다. 더미 작업을 놓치면 실제보다 짧은 소요 일수를 구하게 되므로 주의가 필요합니다.

일정을 단축하는 방법

전체를 줄이려면 임계 경로 위의 작업을 줄여야 하며, 임계 경로 위에 없는 작업을 아무리 줄여도 전체는 바뀌지 않습니다. 사람이나 비용을 추가하여 작업을 줄이는 것을 크래싱, 순서대로 할 예정인 작업을 일부 겹쳐 병행으로 진행하는 것을 패스트 트래킹이라고 합니다. 크래싱에서는 1일 단축하기 위한 비용이 가장 적은 임계 경로 위의 작업부터 줄입니다. 단축하면 다른 경로가 새로운 임계 경로가 되는 경우가 있으므로, 그때마다 다시 계산합니다.

도전해 보기: 임계 경로법(CPM) 관련 문제

작업과 소요 일수, 선행 작업이 A: 4일(선행 작업 없음), B: 2일(없음), C: 3일(A), D: 2일(B), E: 5일(C), F: 4일(C와 D), G: 2일(F)인 프로젝트가 있다. 다른 작업은 가능한 한 일찍 시작할 때, 작업 B의 시작을 늦춰도 전체 소요 일수가 늘어나지 않는 최대 일수는?

A0일
B1일
C3일

정답과 해설 보기

정답: C. 3일

가장 이른 시작일은 C가 4일, E와 F가 7일(F는 C가 끝나는 7일과 D가 끝나는 4일 중 늦은 쪽), G가 11일이며, 전체는 A→C→F→G의 4 + 3 + 4 + 2 = 13일입니다. 뒤에서부터 가장 늦은 시작일을 구하면 G가 11일, F가 7일, D가 7 − 2 = 5일, B가 5 − 2 = 3일이므로, B의 총 여유(토털 플로트)는 3 − 0 = 3일입니다. B를 늦추면 D의 시작도 늦어지지만, D에도 같은 여유가 있으므로 3일까지라면 전체는 늘어나지 않습니다. 0일은 B의 자유 여유(후속 작업 D의 가장 이른 시작을 늦추지 않는 여유), 1일은 E의 여유 일수입니다. 임계 경로법(CPM)에서는 이처럼 여유 일수를 구하고, 여유가 0인 작업을 이은 경로를 임계 경로로 합니다.

자주 묻는 질문

임계 경로는 하나뿐인가요?

여러 개인 경우도 있습니다. 소요 일수가 같은 최장 경로가 2개 있으면 둘 다 임계 경로이며, 전체를 줄이려면 두 경로를 모두 줄여야 합니다.

총 여유와 자유 여유의 차이는 무엇인가요?

총 여유(토털 플로트)는 전체 소요 일수를 늘리지 않고 그 작업을 늦출 수 있는 일수입니다. 자유 여유(프리 플로트)는 후속 작업의 가장 이른 시작일을 늦추지 않고 늦출 수 있는 일수로, 총 여유 이하가 됩니다. 후속 작업과 여유를 공유하는 경우, 자유 여유는 0이어도 총 여유는 양수가 되는 경우가 있습니다.

해설 속 임계 경로법(CPM)

임계 경로법(CPM)에서는 이처럼 여유 일수를 구하고, 여유가 0인 작업을 이은 경로를 임계 경로로 합니다.
작업과 소요 일수, 선행 작업이 A: 4일(선행 작업 없음), B: 2일(없음), C: 3일(A), D: …

임계 경로법(CPM)이(가) 나오는 문제 (1)

작업과 소요 일수, 선행 작업이 A: 4일(선행 작업 없음), B: 2일(없음), C: 3일(A), D: 2일(B), E: 5일(C), F: 4일(C와 D), G: 2일(F)인 프로젝트가 있다. 다른 작업은 가능한 한 일찍 시작할 때, 작업 B의 시작을 늦춰도 전체 소요 일수가 늘어나지 않는 최대 일수는?