4. 调度问题形式化

并行测试任务调度不能停留在“把任务排一排”的直觉层面。要让调度算法可比较、可复现、可优化，必须先把工程问题转化为形式化模型：明确决策变量、目标函数、约束条件和评价指标。形式化质量直接决定后续算法选型与结果可信度。

一、核心原理：三元组与决策变量

并行测试调度问题可抽象为“任务—资源—时间”三元组。设测试任务集合 T = {t₁, t₂, …, tₙ}，测试资源集合 R = {r₁, r₂, …, rₘ}，每个任务 tᵢ 具有释放时间 rᵢ、处理时间 pᵢ、资源需求向量 reqᵢ、优先级 wᵢ 与截止期 dᵢ。调度解由两个核心决策变量构成：任务到资源的分配矩阵 xᵢⱼ ∈ {0,1}，以及任务开始时间 sᵢ。结束时间则为 cᵢ = sᵢ + pᵢ。

形式化模型的价值在于把“并行测试”中的互斥、占用、顺序、时限等工程语义，统一翻译为数学约束。例如同一资源同一时刻只能执行一个任务，可写为：若 xᵢⱼ = xₖⱼ = 1，则区间 [sᵢ, cᵢ) 与 [sₖ, cₖ) 不得重叠。这样，调度问题就变成了带约束的组合优化问题。

二、约束建模：从工程规则到数学表达

并行测试场景中常见约束可分为五类：资源容量约束、任务互斥约束、时序依赖约束、时间窗约束和状态一致性约束。资源容量约束要求任意时刻资源占用不超过其能力上限；任务互斥约束用于防止共享仪器、夹具或总线冲突；时序依赖约束描述任务先后关系，如校准完成后才能执行测量；时间窗约束限定任务必须在 [rᵢ, dᵢ] 内完成；状态一致性约束则要求同一被测单元上的任务不能并发执行。

约束建模时建议采用“先硬后软”的策略：硬约束必须满足，否则解不可行；软约束允许违反，但需计入惩罚项。例如测试优先级、负载均衡、切换次数等通常作为软约束进入目标函数。下面给出一个简化的约束表达示例：

minimize  F = α·Cmax + β·Σwᵢ·Lᵢ + γ·Switch
subject to
  Σⱼ xᵢⱼ = 1                     ∀i
  Σᵢ reqᵢₖ · xᵢⱼ · I(sᵢ ≤ t < cᵢ) ≤ Capⱼₖ   ∀j,k,t
  sₖ ≥ cᵢ                        若 tᵢ → tₖ
  rᵢ ≤ sᵢ 且 cᵢ ≤ dᵢ             ∀i
  xᵢⱼ ∈ {0,1}, sᵢ ≥ 0

其中 Cmax 为最大完工时间，Lᵢ 为拖期，Switch 为资源切换次数，α、β、γ 为权重系数。该模型可直接用于求解器或启发式算法的适应度评价。

三、优化指标：多目标权衡与归一化

并行测试调度通常不是单目标问题。常见优化指标包括：最大完工时间、总拖期、平均流经时间、资源利用率、负载均衡度、切换开销和测试成本。不同指标之间存在冲突：压缩完工时间可能降低资源利用率，优先高优先级任务可能增加低优先级任务拖期。因此需要多目标建模或加权归一化。

归一化时，可将各指标映射到 [0,1] 区间，再按权重合成。权重应结合测试阶段动态调整：研发阶段更关注完工时间，量产阶段更关注资源利用率与成本。

四、问题分类与复杂度分析

按资源类型，调度问题可分为单机、并行同构机、并行异构机和柔性作业车间。按任务特征，可分为可抢占与不可抢占、独立任务与有依赖任务、静态调度与动态调度。并行测试任务调度通常属于“带资源约束的并行机调度”或“柔性作业车间调度”的变体。

复杂度方面，大多数并行测试调度问题属于 NP-hard。例如，即使只有两台同构机、任务不可抢占且目标为最小化 Cmax，该问题也等价于划分问题，是 NP-hard 的。当引入资源容量、时序依赖和多目标后，解空间呈指数增长。因此工程上很少追求精确最优解，而是采用启发式、元启发式或约束规划，在可接受时间内获得高质量可行解。

五、案例：多仪器并行测试的形式化

某测试线有 3 台仪器，需执行 6 个测试任务。任务 t₁ 与 t₂ 共享夹具，不能并发；t₃ 必须在 t₁ 完成后开始；t₄ 有截止期。形式化后，分配变量 xᵢⱼ 共 18 个，开始时间变量 6 个，约束包括资源容量、互斥、时序和截止期。求解目标为最小化 Cmax 与总拖期的加权和。通过该模型，可清晰比较“先到先服务”“最短加工时间优先”“遗传算法”三种策略的指标差异。

六、误区与复盘

• 误区一：目标函数单一。只优化 Cmax 可能导致高优先级任务拖期，应引入多目标或加权评价。
• 误区二：约束遗漏。忽略资源切换时间或夹具互斥，会使调度解在实际执行中不可行。
• 误区三：复杂度误判。把 NP-hard 问题当作多项式问题处理，导致算法选型错误。
• 复盘要点：每次调度后记录实际完工时间、资源利用率和切换次数，反哺模型参数与权重调整。