Scheduling

1 Critical Path Method

Overview 개요

CPM(Critical Path Method)은 작업의 선후행 관계와 기간으로 가장 이른 완료 시점을 계산한다. 기간을 바꾸면 여유와 주공정도 달라진다.

기호: d는 기간, ES·EF는 가장 이른 시작·완료, LS·LF는 가장 늦은 시작·완료다.

Concept 개념

예시 공정표는 5층 RC(Reinforced Concrete) 골조를 층당 6개, 총 30개 작업으로 단순화했다. 기간·인원·선후행은 손으로 정한 예시다. 작업은 중단 없이 연속하고 모든 날짜를 작업일로 취급한다.

위상 순서로 순방향 계산을 해 ES·EF를 구한 뒤, 프로젝트 종료에서 역방향으로 LS·LF를 구한다. 총여유 TF=LS−ES가 0인 작업을 주공정으로 표시한다. 자원 한도는 이 탭에서 적용하지 않는다.

Summary 정리

• 주공정이 여러 갈래일 수도 있다.
• 총여유는 프로젝트 종료를 늦추지 않는 범위다.
• 자원 제약을 넣으면 CPM 공기보다 길어질 수 있다.

Notation 기호

References 참고문헌

1. Kelley & Walker (1959). Critical-Path Planning and Scheduling. Proceedings of the Eastern Joint Computer Conference.

2 Resource Leveling

Overview 개요

Resource leveling(자원 평준화)은 공기를 유지하면서 자원 사용량의 들쑥날쑥함을 줄인다. 여유 있는 작업을 뒤로 옮겨 일별 인원 분포를 비교한다.

기호: rᵢ는 작업 인원, sᵢ는 시작일, Rₜ는 t일 총인원이다.

Concept 개념

수동 이동은 선행 작업 완료와 후행 작업 시작을 모두 지킨다. 슬라이더 또는 간트 막대 끌기로 움직인다. 인원 변경은 해당 작업에만 적용된다.

자동 방식은 가능한 정수 시작일을 순회하며 일별 인원 제곱합을 줄이는 위치를 선택한다. 최대 6회 순회하는 탐욕적 방법이며 전역 최적 평준화를 보장하지 않는다.

인원 제곱합과 최대 인원은 다른 지표다. 제곱합이 줄어도 최대 인원이 그대로일 수 있으므로 둘 다 표시한다.

3 Schedule Optimization

Overview 개요

RCPSP(Resource-Constrained Project Scheduling Problem)는 인원 한도와 선후행 조건을 지키며 공기를 최소화한다. 작업 순서 규칙과 유전 알고리즘을 비교한다.

기호: C는 일별 인원 한도, Cₘₐₓ는 전체 완료일이다.

Concept 개념

Serial schedule generation은 선행 작업을 모두 배정한 작업 중 우선순위가 가장 높은 것을 고른다. 선후행·인원 한도가 동시에 가능한 가장 이른 날짜에 배정한다.

기준선은 작은 LF 우선, 짧은 기간 우선, 작업 번호 순서다. GA는 작업별 실수 우선순위를 진화시킨다. 한 작업의 인원보다 작은 용량은 허용하지 않는다.

30개 예시 작업은 층별 연쇄가 강해 여러 방법의 공기가 같을 수 있다. 같게 나온 수치도 그대로 표시한다. 자원 한도는 모든 결과에서 직접 검사한다.

Summary 정리

• 우선순위는 시작일 자체가 아니다.
• 디코더가 자원·선후행 가능성을 보장한다.
• 작은 예시에서 같은 결과가 나와도 일반적인 동등성은 아니다.

Notation 기호

References 참고문헌

1. Kolisch (1996). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research.
2. Hartmann (1998). A Competitive Genetic Algorithm for Resource-Constrained Project Scheduling. Naval Research Logistics.

4 Schedule Risk

Overview 개요

Schedule risk(공정 위험)는 기간의 불확실성이 전체 완료일에 어떻게 전파되는지 본다. 각 작업의 낙관·최빈·비관 기간에서 1,000–10,000회 표본을 뽑는다.

기호: a·m·b는 삼각분포의 최솟값·최빈값·최댓값이다. P50·P80은 완료일 분포의 분위수다.

Concept 개념

세 점을 사용하지만 이 체험의 분포는 삼각분포다. 평균은 (a+m+b)/3이며 전통적인 PERT 근사 평균 (a+4m+b)/6과 다르다. 입력 조건은 0<a≤m≤b다.

매 반복에서 모든 작업의 기간을 독립적으로 뽑아 CPM을 다시 계산한다. 주공정 빈도는 총여유가 수치 오차 10⁻⁷일 이내인 반복 비율이다. 자원 제약·날씨 공통 충격·달력은 반영하지 않는다.

P80은 이 단순화한 모델에서 완료일의 80% 분위수다. 실제 준공일을 보장하는 확률이 아니다. 난수 시드를 고정하면 분포와 분위수가 재현된다.

Summary 정리

• 작업별 평균 합과 전체 완료일 분위수는 다르다.
• 기간의 독립 가정이 결과에 영향을 준다.
• 반복 횟수는 표본 오차를 줄이지만 모델 오류는 없애지 못한다.

Notation 기호

References 참고문헌

1. SciPy. scipy.stats.triang — triangular distribution reference.
2. Kelley & Walker (1959). Critical-Path Planning and Scheduling. Proceedings of the Eastern Joint Computer Conference.