4. 任务依赖与时序约束建模
多阶段任务编排的核心难点，不在于单个任务能否执行，而在于多个任务之间的时序关系是否被正确表达并被可靠检查。一个无人机侦察—打击任务中，若“目标确认”未完成就触发“武器投放”，或“中继通信”与“数据回传”被错误地并行安排，都会导致任务失败甚至安全事故。因此，本节聚焦于把任务之间的先后、同步、互斥、截止时间与时间窗这五类约束，转化为可计算、可检查的模型。
一、五类时序约束的语义与表达
在任务编排模型中，每个任务通常抽象为带时间属性的节点，约束则作用于节点之间或节点自身。以下五类约束是最基础也最常用的表达形式。
- 先后关系（Precedence）：任务 B 必须在任务 A 完成后才能开始，记作 A → B。它是最常见的依赖，例如“目标识别”完成后才能“航路规划”。
- 同步（Synchronization）：多个任务必须同时开始或同时结束，或按固定偏移量协同。例如两架无人机需在同一时刻到达指定空域形成编队，记作 start(B) = start(A) + Δ。
- 互斥（Mutual Exclusion）：两个任务不能同时占用同一资源或同一空域，记作 A ∩ B = ∅。例如同一跑道不能同时起降两架飞机。
- 截止时间（Deadline）：任务必须在某个绝对时刻前完成，记作 end(A) ≤ D。例如“目标打击”必须在 T+120s 内完成。
- 时间窗（Time Window）：任务只能在某个区间内执行，记作 [ES, LF]，即最早开始时间与最晚完成时间。例如卫星过顶窗口为 10:00–10:08。
这五类约束可以统一用时间变量表达：设任务 i 的开始时间为 s_i、持续时间为 d_i、结束时间为 e_i = s_i + d_i，则先后关系为 s_j ≥ e_i，同步为 s_j = s_i + Δ，互斥为 [s_i, e_i] ∩ [s_j, e_j] = ∅，截止时间为 e_i ≤ D_i，时间窗为 ES_i ≤ s_i 且 e_i ≤ LF_i。这种统一表达是后续自动检查的基础。
二、约束检查：从时间变量到可行性判定
建模完成后，必须对约束进行一致性检查，判断是否存在可行调度。检查的核心思路是：把每个任务的时间变量 s_i 视为未知量，把所有约束写成不等式或等式，然后判断该约束系统是否有解。
以先后关系为例，若存在 A → B → C → A 的循环依赖，则意味着 s_A ≥ e_C ≥ e_B ≥ e_A + d_A + d_B + d_C，即要求 d_A + d_B + d_C ≤ 0，而实际持续时间均为正，矛盾，说明该任务集不可调度。因此，循环依赖检测是第一步：对任务依赖图做拓扑排序，若无法排出全序，则存在环，必须打断或调整。
对于时间窗与截止时间，常用最早开始/最晚完成传播算法。设任务 i 的最早开始时间为 ES_i，最晚完成时间为 LF_i，则沿依赖边正向传播：ES_j = max(ES_j, ES_i + d_i)；反向传播：LF_i = min(LF_i, LF_j − d_j)。若某任务出现 ES_i > LF_i，则说明该任务在时间窗内无法完成，约束冲突。例如任务 A 时间窗 [0, 10]，d_A = 6；任务 B 时间窗 [8, 20]，d_B = 5，且 A → B。正向传播得 ES_B = max(8, 0+6) = 8，反向传播得 LF_A = min(10, 20−5) = 10，均满足 ES ≤ LF，可行。若把 B 的时间窗改为 [4, 8]，则 LF_A = min(10, 8−5) = 3，而 ES_A = 0，ES_A ≤ LF_A 仍成立，但 ES_B = max(4, 6) = 6，LF_B = 8，ES_B ≤ LF_B 成立，需进一步检查 e_B = 6+5 = 11 > 8，冲突。这说明仅检查 ES ≤ LF 不够，还需检查 e_i = s_i + d_i ≤ LF_i。
三、互斥与同步的工程处理
互斥约束在工程中常转化为资源占用表。例如空域资源 R1 被任务 A 占用 [10, 20]，任务 B 申请 [15, 25]，则区间 [15, 20] 重叠，冲突。解决方式有三种：调整 B 的开始时间至 20 之后；缩短 A 或 B 的持续时间；或为 B 分配另一资源 R2。实际编排中，通常优先调整开始时间，因为持续时间往往由任务本身决定。
同步约束则需注意偏移量的方向与参照系。本文统一约定：start(B) = start(A) + Δ 表示 B 在 A 开始后 Δ 时刻开始，Δ 可为负，表示 B 先于 A。若两机需同时到达，则 Δ = 0；若 B 需在 A 开始后 5 秒启动，则 Δ = 5。检查时，把同步等式代入时间变量，消去一个未知量，再与其它不等式联立求解。
四、可执行的约束检查清单
为便于实际编排时逐项核对，下面给出一份可直接使用的检查清单，覆盖五类约束的关键判定点。
| 约束类型 | 表达形式 | 检查方法 | 典型冲突信号 |
|---|---|---|---|
| 先后关系 | s_j ≥ e_i | 拓扑排序 + 正向传播 | 存在环，无法排序 |
| 同步 | s_j = s_i + Δ | 代入消元后联立不等式 | Δ 与时间窗矛盾 |
| 互斥 | [s_i,e_i] ∩ [s_j,e_j] = ∅ | 资源占用区间求交 | 交集非空 |
| 截止时间 | e_i ≤ D_i | 计算 e_i 与 D_i 比较 | e_i > D_i |
| 时间窗 | ES_i ≤ s_i 且 e_i ≤ LF_i | 正反向传播 + 端点检查 | ES_i > LF_i 或 e_i > LF_i |
五、一个综合示例
设某侦察打击任务包含四个任务：T1 目标识别（d=8，时间窗 [0, 20]），T2 航路规划（d=6，时间窗 [5, 25]），T3 中继通信（d=10，时间窗 [0, 30]），T4 目标打击（d=4，截止时间 D=35）。约束为：T1 → T2，T2 → T4，T3 与 T4 互斥（同一通信链路），T3 与 T1 同步（Δ=0）。
检查过程：由 T1 → T2 得 s_T2 ≥ e_T1 = s_T1 + 8；由 T2 → T4 得 s_T4 ≥ e_T2 = s_T2 + 6；由同步得 s_T3 = s_T1。取 s_T1 = 0，则 e_T1 = 8，s_T2 = max(5, 8) = 8，e_T2 = 14，s_T4 = max(0, 14) = 14，e_T4 = 18 ≤ 35，满足截止时间。T3 占用 [0, 10]，T4 占用 [14, 18]，区间不重叠，互斥满足。所有时间窗均满足。该调度可行。
若把 T4 的截止时间改为 D=16，则 e_T4 = 18 > 16，冲突。此时可尝试压缩 T2 的持续时间或提前 T1 的开始时间，但 T1 时间窗最早为 0，无法提前，只能压缩 T2 或调整依赖结构。这说明约束检查不仅能判断可行性，还能定位关键瓶颈任务，为编排调整提供依据。
掌握这五类约束的表达与检查方法后，就可以把复杂的多阶段任务转化为一个可计算的时间约束系统，从而在编排阶段提前发现冲突、优化调度，而不是等到执行时才发现任务无法按时完成。