2. 调度问题基础与量子计算接口

要谈“量子调度”，第一步不是写量子线路，而是把车间里的排产问题翻译成两种语言：一种是经典优化能读懂的形式化模型，另一种是量子硬件能执行的数学结构。本节先回顾经典调度模型，再引入量子计算的基本构件，最后说明二者之间的映射接口。

一、经典调度问题的形式化模型

调度问题的本质是“在资源约束下为任务分配时间与机器”。最基础的是作业车间调度问题（JSP）：有 n 个工件、m 台机器，每个工件按固定工艺路线依次经过若干机器，每道工序占用一台机器且不可中断，同一机器同一时刻只能加工一道工序。其决策变量可写为每道工序的开始时间 s_ij，约束包括工序先后约束 s_i,j+1 ≥ s_ij + p_ij，以及机器不重叠约束（同一机器上任意两道工序的时间区间不相交）。

柔性作业车间调度问题（FJSP）在 JSP 基础上增加“机器选择”维度：每道工序可在多台可选机器中择一加工，且不同机器上的加工时间不同。于是决策变量变成二元组（机器选择 x_ijk，开始时间 s_ij），搜索空间显著扩大，也更贴近真实车间。

优化目标常见的有三类：最小化最大完工时间 C_max（makespan）、最小化总拖期、最小化总流程时间。约束则分为硬约束（工艺顺序、机器容量、不可抢占）与软约束（交期偏好、换型次数）。形式化时通常写成混合整数规划：

min  C_max
s.t. s_ij + p_ij ≤ s_i,j+1            (工艺顺序)
     s_ij + p_ij ≤ s_kl + M(1-y_ijkl)  (机器不重叠, 大M法)
     s_ij + p_kl ≤ s_kl + M·y_ijkl
     s_ij ≥ 0,  y_ijkl ∈ {0,1}

其中 y_ijkl 表示工序 (i,j) 是否排在 (k,l) 之前。这个模型是后续量子映射的“源语言”：无论采用哪种量子编码，最终都要能还原出这组变量与约束。

二、量子计算的基本构件

量子比特（qubit）是信息载体，其状态可表示为 |ψ⟩ = α|0⟩ + β|1⟩，满足 |α|²+|β|²=1。与经典比特不同，qubit 可处于叠加态，n 个 qubit 的联合态空间维度为 2ⁿ，这是量子并行性的来源。

量子门是对 qubit 状态的酉变换。单比特门如 Hadamard 门 H 产生叠加，Pauli-X 门实现翻转，R_z(θ) 引入相位；两比特门如 CNOT 用于产生纠缠。多个门按时间顺序排列即构成量子线路：左侧为输入初态，右侧为测量读出，中间是门序列。线路深度与门数量直接决定在含噪声硬件上的可行性。

对优化问题而言，最常用的两类范式是：量子退火/QAOA（将问题编码为伊辛模型或 QUBO，通过演化寻找低能态）与门模型变分算法（参数化线路 + 经典优化器迭代）。调度问题通常先转成 QUBO，再交给上述任一范式。

三、从调度模型到量子可处理形式

映射的核心步骤是“变量二元化 + 约束罚函数化”。以 JSP 为例，常用时间索引编码：把时间离散为 T 个时隙，定义二元变量 x_ijt=1 表示工序 (i,j) 在时隙 t 开始。于是“每道工序恰好开始一次”写成 Σ_t x_ijt=1；“机器不重叠”写成对同一机器上任意两道工序、任意重叠时隙组合的惩罚项。目标 C_max 则通过引入辅助变量或直接对最晚完成时隙加权表达。

把所有约束乘以罚系数 λ 后并入目标，得到 QUBO 形式：

E(x) = Σ 目标项 + λ1·Σ(工序开始次数-1)²
              + λ2·Σ(机器时隙冲突)
              + λ3·Σ(工艺顺序违背)

该能量函数可直接映射为伊辛哈密顿量 H = Σ h_iZ_i + Σ J_ijZ_iZ_j，其中 Z_i 为 Pauli-Z 算符，x_ijt=(1−Z)/2。此时“求解调度”等价于“寻找哈密顿量基态”。

下面这张图概括了从经典调度模型到量子执行、再到解解码的完整接口链路，重点标出编码方式与罚项在链路中的位置：

四、一个可操作的小例子

设 2 个工件、2 台机器，工件 1 的工序为 M1(2)→M2(1)，工件 2 为 M2(1)→M1(2)，括号内为加工时长。取时间离散单位 1，总时隙 T=5。变量 x_ijt 共 4 道工序 × 5 时隙 = 20 个 qubit。约束项包括：每道工序 Σ_tx_ijt=1；工件 1 的工序 2 开始时间不早于工序 1 结束；同一机器上时隙重叠的工序对产生惩罚。目标项对每道工序的完成时隙加权求和，近似 C_max。

把该 QUBO 交给 QAOA 时，线路由 p 层“代价演化 + 混合演化”组成，代价层对应 e^−iγH，混合层对应 e^−iβΣX。运行后对测量得到的比特串做解码：若某比特串满足全部约束，则按 x_ijt=1 的位置排出甘特图并计算 C_max；若违反约束，则记录违反类型（如机器冲突），用于调整罚系数或增加层数 p。示例中若采样 1024 次，可统计满足约束的比特串比例作为“可行率”，并取其中 C_max 最小者作为当前最优解。这些数值属于教学示例设定，实际结果取决于硬件噪声与参数调优。