FPTR：截止时间约束下的可行性与事务性优化框架

在无线调度器中，短间隔内的波束与资源分配必须在每个执行截止时间前返回完整且可行的方案；任何延迟或无效输出都会导致当前控制周期零效用。延长搜索可能提升流量，但也可能错过截止时间或仅得到不可行的中间解。为此，研究者提出可行性保持的事务性精炼（Feasibility-Preserving Transactional Refinement, FPTR），其核心思想是始终维护一个已验证的可行分配（现任解），每个精炼阶段独立构建候选解，只有候选解完整、在阶段截止前通过可行性验证且严格改进目标时才替换现任解。

FPTR如何工作：事务性精炼与可行性保障

FPTR将强制输出构建与可选精炼分离。首先通过基础构造器（Base constructor）生成一个初步可行解，随后依次执行四个精炼阶段：

• 缓冲区感知的资源选择：根据缓冲区状态选择资源，减少潜在冲突。
• 兼容组（CG）用户共享：通过兼容组允许多用户共享资源，提升效率。
• 基于剩余需求的波束掩码重建：利用剩余需求重建波束掩码，优化覆盖。
• 两个资源的联合重新分配：对两个资源进行联合调整，进一步改进目标。

每个阶段都在独立空间中构建候选解，并设置阶段截止时间。候选解必须在该截止时间前通过可行性验证器，且严格改进目标函数，否则被丢弃。这种“事务性”设计确保现任解始终可行，避免因搜索而陷入不可行状态。

波束掩码是无线通信中波束赋形的一种具体实现方式：它将天线阵列的权重配置编码为一个掩码（通常是二进制或离散取值），用以控制哪些天线单元激活、以何种相位/幅度组合形成指向特定方向的波束。掩码重建即根据当前用户分布与资源占用情况，重新计算并生成一组新的波束配置，使覆盖范围与容量匹配剩余需求。在FPTR中，该步骤利用前序阶段处理后的剩余需求来重建掩码，避免对已满足的用户重复分配资源，从而在有限时间内定向优化覆盖。

实验表现：流量提升与截止时间满足

在150个固定合成实例上，完整流水线（Full）的平均流量比轻量级波束优先参考方案（beam-first reference）提升3.83%，比其Base构造器提升1.79%。在另一组匹配输入的测试中，Full在输出延迟超过100毫秒即零效用的约束下，比六种独立搜索基线（ALNS、禁忌搜索、遗传算法、模拟退火、迭代局部搜索和GRASP）高出6.68%至8.35%。

内部套件的全部750次Full运行均返回可行分配，且无一超过100毫秒。这表明FPTR在严格截止时间下仍能可靠地提供高质量解，而不会因搜索而牺牲可行性或时效性。

ALNS（自适应大邻域搜索） 是一种元启发式算法，它通过多组“破坏-修复”算子迭代地移除并重新插入解中的部分元素，并根据算子近期表现自适应调整其选择概率。其优势在于能跳出局部最优，但每次迭代都需要完整评估解的质量。禁忌搜索则利用短期记忆（禁忌表）禁止重复访问近期解，以探索更广的解空间；遗传算法通过选择、交叉和变异进化种群；模拟退火以概率接受劣解以逃离局部最优；迭代局部搜索在局部搜索后施加扰动再重启；GRASP（贪婪随机自适应搜索）则反复构造随机化贪婪解并进行局部改进。这些基线均属于通用搜索框架，在硬截止时间下可能因无法保证每次迭代输出可行解而失效，而FPTR通过事务性精炼规避了这一缺陷。

设计启示：分离强制构造与可选精炼

FPTR的关键贡献在于将强制输出构造与可选精炼解耦。强制构造保证在任何情况下都有可行解可用，而可选精炼则利用剩余计算时间改进解的质量，同时不危及现任解。这种架构适用于任何需要在硬截止时间下持续输出可行解的优化场景，不仅限于无线调度。

开源实现已提供，支持独立复现。对于需要实时决策的工程师和研究者，FPTR提供了一种兼顾可行性与性能的实用框架。