3. 量子退火与组合优化调度建模

量子退火是一种利用量子涨落与热涨落协同搜索能量最低状态的启发式优化方法。它并不直接“求解调度问题”，而是先把调度问题翻译成一个物理系统能够理解的能量函数，再让硬件在退火过程中自然演化到低能量构型。因此，本节的核心不是量子硬件细节，而是如何把调度问题写成伊辛模型或 QUBO 形式，以及如何处理约束与目标之间的转化。

一、量子退火的基本原理

量子退火的过程可以理解为：系统初始处于一个已知的、容易制备的哈密顿量 H₀ 的基态（通常是横向场，使所有量子比特处于叠加态），随后缓慢调节参数，使系统哈密顿量逐渐过渡到问题哈密顿量 H_P：

H(s) = A(s)·H₀ + B(s)·H_P,   s: 0 → 1
A(0) 大、B(0) 小  →  A(1) 小、B(1) 大

若演化足够慢，系统依据绝热定理保持在瞬时基态附近，最终测量得到的比特串就对应问题的一个低能解。实际硬件中演化时间有限、存在噪声与耦合精度限制，因此结果通常是“近似最优”，需要多次采样并挑选能量最低的样本。这一点对调度建模非常重要：建模质量决定了搜索空间里是否存在好解，采样次数决定了能否把它找出来。

二、伊辛模型与 QUBO 的关系

伊辛模型用自旋变量 s_i ∈ {−1, +1} 描述相互作用，能量为：

E(s) = Σ_i h_i·s_i + Σ_{i<j} J_ij·s_i·s_j

QUBO（二次无约束二值优化）使用 x_i ∈ {0, 1}，目标为最小化：

E(x) = xᵀQx = Σ_i Q_ii·x_i + Σ_{i<j} Q_ij·x_i·x_j

两者可通过 s_i = 2x_i − 1 相互转换。工程上更常用 QUBO，因为“是否把任务 j 排在位置 k”这类决策天然是 0/1 变量。需要注意：转换会引入常数项和对角项偏移，若关心绝对能量值需重新计算常数，但若只比较解的优劣，常数项可忽略。

三、单机调度问题的 QUBO 构建

考虑一个典型单机总拖期问题：有 n 个任务，加工时间 p_j、交期 d_j，单机同一时刻只能加工一个任务，目标是最小化总拖期 ΣT_j，其中 T_j = max(0, C_j − d_j)。

采用“位置分配”编码：定义 x_j,k = 1 表示任务 j 排在序列第 k 位。完成时间可写成 C_j = Σ_k x_j,k · (Σ_m≤k Σ_i p_i·x_i,m)，这会产生三次项，直接放入 QUBO 不可行。工程上常用两种处理：

• 引入辅助变量：用 y_k 表示第 k 位的累计加工时间，通过约束 y_k = y_k−1 + Σ_j p_j·x_j,k 把三次项降为二次，代价是变量数增加。
• 改用时间索引编码：定义 x_j,t = 1 表示任务 j 在时刻 t 开始，时间离散为 0..T−1。此时拖期项可直接写成 Σ_t x_j,t·max(0, t+p_j−d_j)，是线性项，但变量规模为 n×T，且需处理“不重叠”约束。

以位置编码为例，目标项可近似写成二次形式：

H_obj = Σ_j Σ_k w_jk · x_jk
w_jk = max(0, Σ_{m≤k} p̄_m − d_j)   // p̄_m 为位置 m 的期望加工时间

约束“每个任务恰好一个位置”和“每个位置恰好一个任务”用平方惩罚表达：

H_pen = Σ_j (Σ_k x_jk − 1)² + Σ_k (Σ_j x_jk − 1)²

展开后得到对角项 −1·x_j,k 与耦合项 2·x_j,k·x_j,k'、2·x_j,k·x_j',k，全部是二次的，可直接写入 Q 矩阵。总哈密顿量为 H = H_obj + λ·H_pen，λ 需大于目标项可能的最大改善量，否则求解器可能用“违反约束”换取更低能量。

四、并行机调度的建模要点

并行机（同速机）最小化最大完工时间 C_max 时，常用“任务—机器—位置”三维变量 x_j,m,k，或“任务—机器”二维变量配合每台机器内部的排序。前者变量数为 n×m×n，规模增长快；后者把每台机器视为一个独立单机子问题，再用负载均衡项耦合：

H = Σ_m (Σ_j p_j·x_jm)² · α  +  β·Σ_j (Σ_m x_jm − 1)²

第一项惩罚机器负载差异（平方项鼓励均衡），第二项保证每个任务只分配一次。α 与 β 的相对大小决定“均衡”与“可行性”的优先级，通常先保证 β 足够大，再调 α。若问题还带机器可用时间窗或任务先后约束，可继续叠加惩罚项，但每加一项都会增加耦合密度，需评估硬件耦合图的连通性是否支持。

五、约束处理与目标转化的实用技巧

第一，惩罚系数要“够大但不过大”。λ 太小会得到不可行解，太大会让能量景观变得陡峭、退火过程难以穿越，建议先用小规模实例扫描 λ 的取值区间，观察可行解比例与目标值的变化。第二，优先选择变量数少的编码，位置编码适合 n 较小的排序问题，时间索引编码适合时间窗约束强的问题。第三，利用问题结构降维，例如单机问题中若已知最优解满足某种排序规则（如 EDD 对最大拖期），可先固定部分变量或缩小候选位置范围。第四，结果必须解码并校验：把比特串还原为调度序列，检查每个任务是否只出现一次、机器是否超载，再计算真实目标值，不能只看 QUBO 能量。

综上，量子退火求解调度的关键不在于硬件本身，而在于把“任务—位置—机器—时间”的决策关系准确映射为二次型能量函数，并通过合理的惩罚系数与编码方式，让低能量构型恰好对应高质量且可行的调度方案。