397.58 작업 선후 관계(Precedence Constraints) 그래프

1. 작업 선후 관계의 정의

작업 선후 관계(Precedence Constraints)는 임무를 구성하는 개별 작업(Task) 간에 존재하는 실행 순서 제약을 형식화한 개념이다. 특정 작업 $\tau_j$ 가 작업 $\tau_i$ 의 완료 이후에만 실행될 수 있을 때, $\tau_i$ 를 $\tau_j$ 의 선행 작업(Predecessor), $\tau_j$ 를 $\tau_i$ 의 **후행 작업(Successor)**이라 한다. 이 관계는 $\tau_i \prec \tau_j$ 로 표기하며, 부분 순서(Partial Order)를 형성한다.

임무 계획에서 작업 선후 관계는 물리적 인과성, 자원 의존성, 안전 요구사항 등 다양한 원인으로 발생한다. 예를 들어 “적재물을 들어올리기 전에 적재 지점에 도착해야 한다“는 물리적 인과성에 기인한 선후 관계이고, “센서 캘리브레이션이 완료된 후에야 측정 임무를 수행할 수 있다“는 기능적 의존성에 기인한 선후 관계이다.

2. 선후 관계 그래프의 수학적 표현

2.1 유향 비순환 그래프(DAG) 표현

작업 선후 관계는 유향 비순환 그래프(Directed Acyclic Graph, DAG) $G_p = (V_p, E_p)$ 로 표현된다. 여기서 $V_p = \{\tau_1, \tau_2, \ldots, \tau_n\}$ 은 작업의 집합이고, $E_p \subseteq V_p \times V_p$ 는 선후 관계를 나타내는 유향 간선의 집합이다. 간선 $(\tau_i, \tau_j) \in E_p$ 는 $\tau_i \prec \tau_j$ , 즉 작업 $\tau_i$ 가 작업 $\tau_j$ 보다 먼저 완료되어야 함을 의미한다.

비순환성(Acyclicity)은 선후 관계의 필수적인 성질이다. 만약 $\tau_i \prec \tau_j$ 이고 동시에 $\tau_j \prec \tau_i$ 이면 두 작업 모두 실행 불가능한 순환 교착(Cyclic Deadlock) 상태가 발생한다. 따라서 선후 관계 그래프는 반드시 DAG여야 하며, 이는 다음의 조건으로 형식화된다.

$\nexists \; \tau_{k_1}, \tau_{k_2}, \ldots, \tau_{k_m} \in V_p \text{ such that } (\tau_{k_1}, \tau_{k_2}), (\tau_{k_2}, \tau_{k_3}), \ldots, (\tau_{k_m}, \tau_{k_1}) \in E_p$

2.2 이행적 폐포와 이행적 축소

선후 관계의 이행적 폐포(Transitive Closure) $E_p^+$ 는 $\tau_i \prec \tau_j$ 이고 $\tau_j \prec \tau_k$ 이면 $\tau_i \prec \tau_k$ 를 포함하도록 확장한 간선 집합이다. 이행적 폐포는 Warshall 알고리즘을 사용하여 $O(n^3)$ 의 시간 복잡도로 계산할 수 있다.

반대로, 이행적 축소(Transitive Reduction) $E_p^-$ 는 이행적 폐포와 동일한 도달 가능성을 유지하면서 간선 수를 최소화한 집합이다. DAG에서 이행적 축소는 유일하며, 불필요한 중복 제약 표현을 제거하여 그래프의 가독성과 저장 효율성을 향상시킨다. 이행적 축소는 다음과 같이 정의된다.

$E_p^- = E_p \setminus \{(\tau_i, \tau_j) \in E_p \mid \exists \; \text{path from } \tau_i \text{ to } \tau_j \text{ of length } \geq 2\}$

2.3 인접 행렬 표현

선후 관계 그래프는 인접 행렬 $\mathbf{P} \in \{0, 1\}^{n \times n}$ 으로 표현할 수 있다.

$P_{ij} = \begin{cases} 1, & \text{if } (\tau_i, \tau_j) \in E_p \\ 0, & \text{otherwise} \end{cases}$

이행적 폐포 행렬 $\mathbf{P}^+$ 는 부울 행렬 곱(Boolean Matrix Multiplication)의 반복 적용으로 계산된다.

$\mathbf{P}^+ = \mathbf{P} \lor \mathbf{P}^2 \lor \mathbf{P}^3 \lor \cdots \lor \mathbf{P}^{n-1}$

여기서 $\lor$ 는 성분별 논리합(Element-wise OR) 연산이다.

3. 선후 관계 그래프의 구성 방법

3.1 임무 명세로부터의 자동 추출

형식화된 임무 명세(Mission Specification)로부터 선후 관계를 자동으로 추출하는 방법은 임무 계획의 자동화에서 핵심적 역할을 수행한다.

PDDL(Planning Domain Definition Language)로 기술된 계획 도메인에서는 행동(Action)의 전제 조건(Precondition)과 효과(Effect)를 분석하여 선후 관계를 도출한다. 행동 $a_j$ 의 전제 조건에 포함된 명제(Proposition)가 행동 $a_i$ 의 효과에 의해 생성되면, $a_i \prec a_j$ 의 선후 관계가 성립한다. 이를 형식적으로 기술하면 다음과 같다.

$a_i \prec a_j \iff \text{eff}^+(a_i) \cap \text{pre}(a_j) \neq \emptyset$

여기서 $\text{eff}^+(a_i)$ 는 행동 $a_i$ 의 양의 효과(Positive Effect) 집합, $\text{pre}(a_j)$ 는 행동 $a_j$ 의 전제 조건 집합이다.

3.2 HTN 분해로부터의 구성

계층적 작업 네트워크(Hierarchical Task Network, HTN)에서는 복합 과업(Compound Task)을 원시 과업(Primitive Task)으로 분해하는 과정에서 선후 관계가 자연스럽게 발생한다. 분해 메소드(Decomposition Method)가 순서 제약(Ordering Constraints)을 명시적으로 포함하는 경우, 이 제약이 직접 선후 관계로 변환된다.

전순서 분해(Totally Ordered Decomposition)에서는 분해된 모든 하위 과업 간에 전순서(Total Order)가 존재하여 $\tau_1 \prec \tau_2 \prec \cdots \prec \tau_k$ 와 같은 선형 체인(Linear Chain)을 형성한다. 반면, 부분 순서 분해(Partially Ordered Decomposition)에서는 분해된 하위 과업 중 독립적인 과업 쌍이 존재하여 병렬 실행의 가능성을 제공한다.

3.3 자원 의존성 기반 구성

두 작업이 동일한 자원(Resource)을 배타적으로 사용해야 할 때, 자원 의존성에 기인한 선후 관계가 발생한다. 자원 $r$ 을 필요로 하는 작업 집합 $\mathcal{T}_r$ 이 있을 때, $\mathcal{T}_r$ 내의 작업들 사이에 직렬화 순서(Serialization Order)를 결정하여 자원 충돌(Resource Conflict)을 방지한다.

자원 제약 기반 선후 관계의 결정은 일반적으로 스케줄링 문제와 결합되며, 최적 순서의 결정은 NP-난해(NP-hard) 문제에 해당한다.

4. 선후 관계 그래프의 분석

4.1 임계 경로 분석

임계 경로(Critical Path)는 선후 관계 그래프에서 시작 노드(소스)에서 종료 노드(싱크)까지의 최장 경로(Longest Path)이다. 임계 경로의 길이는 전체 임무의 최소 완수 시간(Makespan)의 하한을 결정한다.

각 작업 $\tau_i$ 의 수행 시간을 $d_i$ 라 하면, 임계 경로 길이 $C^*$ 는 다음과 같이 계산된다.

$C^* = \max_{\text{path } P \text{ from source to sink}} \sum_{\tau_i \in P} d_i$

임계 경로 분석은 CPM(Critical Path Method) 알고리즘을 사용하여 $O(n + m)$ 시간에 수행할 수 있다. 여기서 $n = |V_p|$ , $m = |E_p|$ 이다.

각 작업의 최조 시작 시간(Earliest Start Time, EST) 과 최지 시작 시간(Latest Start Time, LST) 은 순방향 전파(Forward Pass)와 역방향 전파(Backward Pass)를 통해 계산된다.

$\text{EST}(\tau_j) = \max_{\tau_i \prec \tau_j} \left(\text{EST}(\tau_i) + d_i\right)$

$\text{LST}(\tau_i) = \min_{\tau_i \prec \tau_j} \left(\text{LST}(\tau_j) - d_i\right)$

작업 $\tau_i$ 의 여유 시간(Slack 또는 Float) $S_i$ 는 다음과 같이 정의된다.

$S_i = \text{LST}(\tau_i) - \text{EST}(\tau_i)$

여유 시간이 0인 작업이 임계 작업(Critical Task)이며, 이러한 작업들의 연쇄가 임계 경로를 구성한다.

4.2 병렬성 분석

선후 관계 그래프에서 직접적 또는 간접적 선후 관계가 존재하지 않는 작업 쌍은 병렬 실행이 가능하다. 그래프의 너비(Width), 즉 최대 반체인(Maximum Antichain)의 크기는 동시에 실행 가능한 작업의 최대 수를 나타낸다. Dilworth의 정리에 의해, DAG의 너비는 최소 체인 분할(Minimum Chain Partition)의 크기와 동일하다.

$\text{Width}(G_p) = \min\{k \mid V_p = C_1 \cup C_2 \cup \cdots \cup C_k, \; C_i \text{ is a chain}\}$

이 분석은 멀티 로봇 시스템에서 사용 가능한 로봇 수에 대한 병렬화 효율성을 평가하는 데 활용된다.

4.3 유연성 분석

선후 관계 그래프의 **유연성(Flexibility)**은 작업 실행 순서의 자유도를 측정하는 지표이다. 전순서 그래프(모든 작업이 선형 체인)의 유연성은 최소이고, 완전히 독립적인 작업 집합(간선이 없는 그래프)의 유연성은 최대이다.

유연성은 선형 확장(Linear Extension)의 수로 정량화할 수 있다. DAG $G_p$ 의 선형 확장 $\mathcal{L}(G_p)$ 은 부분 순서를 보존하는 전순서의 수이며, 이를 정확히 계산하는 것은 $\#P$ -완전( $\#P$ -complete) 문제로 알려져 있다.

5. 스케줄링과의 연관

5.1 자원 제약 프로젝트 스케줄링(RCPSP)

자원 제약 프로젝트 스케줄링 문제(Resource-Constrained Project Scheduling Problem, RCPSP)는 선후 관계와 자원 제약을 동시에 만족하면서 전체 완수 시간을 최소화하는 문제이다. RCPSP는 형식적으로 다음과 같이 정의된다.

$\min \; C_{\max} = \max_{\tau_i \in V_p} (s_i + d_i)$

$\text{subject to:} \quad s_j \geq s_i + d_i, \quad \forall (\tau_i, \tau_j) \in E_p$

$\sum_{\tau_i \in \mathcal{A}(t)} r_{ik} \leq R_k, \quad \forall k, \; \forall t$

여기서 $s_i$ 는 작업 $\tau_i$ 의 시작 시간, $d_i$ 는 수행 시간, $r_{ik}$ 는 작업 $\tau_i$ 가 자원 유형 $k$ 에 대해 요구하는 양, $R_k$ 는 자원 유형 $k$ 의 가용량, $\mathcal{A}(t)$ 는 시각 $t$ 에 진행 중인 작업의 집합이다.

RCPSP는 NP-난해 문제로, 정확 해법으로는 분기 한정법(Branch and Bound)이 사용되고, 근사 해법으로는 우선순위 규칙 기반 휴리스틱(Priority Rule-Based Heuristic), 유전 알고리즘(Genetic Algorithm), 개미 군집 최적화(Ant Colony Optimization) 등이 활용된다.

5.2 다중 로봇 작업 할당과의 통합

다중 로봇 환경에서 선후 관계 그래프는 작업 할당과 스케줄링을 동시에 결정하는 통합 문제의 기반 구조로 활용된다. 각 작업을 특정 로봇에 할당하고, 선후 관계를 만족하는 실행 순서를 결정하며, 로봇 간의 이동 시간을 고려하여 전체 완수 시간을 최소화하는 문제는 다음과 같이 정의된다.

$\min \; C_{\max} \quad \text{subject to:}$

$s_j \geq s_i + d_i + t_{\text{travel}}(v_i, v_j), \quad \forall (\tau_i, \tau_j) \in E_p, \; \text{assigned to same robot}$

$s_j \geq s_i + d_i, \quad \forall (\tau_i, \tau_j) \in E_p, \; \text{assigned to different robots}$

여기서 $t_{\text{travel}}(v_i, v_j)$ 는 작업 $\tau_i$ 의 수행 위치에서 작업 $\tau_j$ 의 수행 위치까지의 이동 시간이다.

6. 동적 선후 관계의 관리

실행 중에 새로운 작업이 삽입되거나 기존 작업이 취소되면, 선후 관계 그래프의 동적 갱신이 필요하다. 동적 갱신에서는 다음의 사항이 검증되어야 한다.

비순환성 유지: 새로운 간선 추가 시 순환이 발생하지 않는지 검증한다. 이는 깊이 우선 탐색(DFS) 기반의 순환 검출 알고리즘으로 $O(n + m)$ 시간에 수행된다.
도달 가능성 갱신: 노드 추가·삭제에 따라 이행적 폐포를 증분적으로 갱신한다.
임계 경로 재계산: 작업의 추가·삭제 또는 수행 시간 변경에 따라 임계 경로와 여유 시간을 재계산한다.

증분적 갱신 알고리즘은 전체 그래프를 재생성하는 것보다 계산 효율성이 우수하며, 실시간 임무 재계획(Real-Time Mission Replanning) 시나리오에서 필수적이다.

7. 선후 관계 그래프의 응용 사례

7.1 조립 공정 로봇 임무 계획

제조업의 조립 공정에서는 부품 간의 조립 순서가 엄격한 선후 관계를 형성한다. 예를 들어 기판에 부품을 실장(Mounting)한 후에 납땜(Soldering)을 수행해야 하며, 외장 케이스 조립은 내부 배선 완료 후에만 가능하다. 이러한 관계는 조립 선후 관계 그래프(Assembly Precedence Graph)로 모델링되며, 이로부터 최적 조립 시퀀스를 도출한다.

7.2 물류 배송 임무 계획

물류 환경에서 픽업(Pickup)과 배송(Delivery) 작업은 자연스러운 선후 관계를 형성한다. 물품 $i$ 에 대해 픽업 작업 $\tau_i^p$ 와 배송 작업 $\tau_i^d$ 는 $\tau_i^p \prec \tau_i^d$ 의 관계를 가진다. 다수의 물품에 대한 픽업·배송 쌍이 존재할 때, 적재 용량(Capacity) 제약과 결합하여 최적 경로를 탐색하는 문제는 선후 관계가 포함된 차량 경로 문제(Vehicle Routing Problem with Precedence Constraints, VRPPC)로 정식화된다.

7.3 다중 드론 감시 임무

다중 드론 감시 임무에서는 특정 구역의 정찰 완료 후 후속 구역 진입이 허용되는 경우, 구역 간 선후 관계가 발생한다. 이러한 선후 관계를 그래프로 구성하고 임계 경로를 분석하여 최소 시간 내에 전체 감시 임무를 완수하는 계획을 수립한다.

8. 참고 문헌

Brucker, P. (2007). Scheduling Algorithms (5th ed.). Springer.
Dechter, R., Meiri, I., & Pearl, J. (1991). “Temporal constraint networks.” Artificial Intelligence, 49(1-3), 61-95.
Herroelen, W., & Leus, R. (2005). “Project scheduling under uncertainty: Survey and research potentials.” European Journal of Operational Research, 165(2), 289-306.
Pinedo, M. L. (2016). Scheduling: Theory, Algorithms, and Systems (5th ed.). Springer.
Erol, K., Hendler, J., & Nau, D. S. (1994). “HTN planning: Complexity and expressivity.” Proceedings of the National Conference on Artificial Intelligence (AAAI).

버전: 2026-03-24