基于您提供的论文内容，以下是对应四个问题的专业解读： <分析> <标题生成> 标题需要专业且突出主题，保留专业名词的英文/缩写（RAPO-RL-TAC, IJSP），使用中文，并保持学术吸引力。 <关键词> 从标题和摘要中提取核心概念：Interval Job Shop Problem (IJSP), Reinforcement Learning, Timed Automata, Partial-Order, Risk-Aware, Scheduling。 <摘要翻译> 忠实原文，使用学术语言，将“we”替换为“研究人员”，保留专业缩写和上下角标。 <论文解读> 按照背景与问题、研究内容、方法、结果（含小标题）、讨论与结论的结构进行总结，确保内容均源自原文，避免推测。 --- 中文标题 风险感知部分序强化学习与时间自动机补全的区间作业车间调度方法（RAPO-RL-TAC）

《Processes》：RAPO-RL-TAC: Risk-Aware Partial-Order Reinforcement Learning with Timed Automata Completion for the Interval Job Shop Problem

　　

在区间作业车间调度问题（Interval Job Shop Problem, IJSP）中，工序加工时间以区间表示，这使得机器排序决策对时间不确定性高度敏感。研究人员提出了风险感知部分序强化学习与时间自动机补全（Risk-Aware Partial-Order Reinforcement Learning with Timed Automata Completion, RAPO-RL-TAC），该方法将用于机器顺序构建的风险感知部分序强化学习（RAPO-RL）与用于执行阶段延迟排序决策消解的时间自动机补全（TAC）相结合。风险感知侧重于保留机器顺序关系中那些偏好排序对区间不确定性敏感的时间灵活性。RAPO-RL 选择性地提交相对确定的机器冲突，同时保留有界数量的时序敏感关系。TAC 在执行过程中补全未决关系，同时通过统计模型检验刻画时间执行下的完工时间变异性。在 14 个 ORB 和 LA 基准实例上，RAPO-RL-TAC 的平均中点完工时间分别比基于种群的邻域搜索（Population-based Neighbourhood Search, PNS）和遗传算法（Genetic Algorithm, GA）低 2.92% 和 1.63%。与复现的快速精英人工蜂群（Fast Elitist Artificial Bee Colony, fEABC）变体相比，RAPO-RL-TAC 在 14 个实例中的 7 个上取得了低于至少一个变体的中点值。在受控消融研究中，RAPO-RL-TAC 的平均中点完工时间比强制执行学习到的关系低 13.85%。这些结果表明，风险感知的选择性提交在区间不确定性下保留了时间灵活性，同时保持了具有竞争力的标称调度质量。

**1. 研究背景与问题**

作业车间调度问题（Job Shop Scheduling Problem, JSSP）关注在满足工艺约束和机器容量约束的前提下，对共享机器上的工序进行分配与排序，其最广泛研究的优化目标之一是最小化完工时间（makespan）。由于组合特性，确定性 JSSP 已被证明是 NP-难的。然而在实际生产中，加工时间很少能被精确获知，可靠的概率分布也往往难以获得，但工序时长的上下界通常可以较好地估计。因此，区间作业车间调度问题（Interval Job Shop Problem, IJSP）通过将每道工序的持续时间表示为由其上下界定义的区间来建模加工时间的不确定性，无需依赖显式的概率分布。

现有的大多数 IJSP 方法采用“序列优先”策略，即在传播区间时长进行评估之前，预先确定一个完整的工序或机器序列。然而，鲁棒调度研究表明，保留部分排序自由度有助于在不确定时长下提升适应性。这揭示了一个关键矛盾：预先固定所有同机冲突会消除潜在的有用时间灵活性，而保留过多关系又会留下不必要的大规模残差决策空间。因此，核心挑战在于确定哪些机器冲突应在执行前提交，哪些应保持开放，从而在组合优化约简与不确定性下的灵活性之间取得平衡。

**2. 研究内容与结论**

针对上述问题，研究人员提出了 RAPO-RL-TAC 框架。该框架是一个分阶段的“学习-形式化”流水线：首先，其学习组件风险感知部分序强化学习（RAPO-RL）通过解析相对稳定的冲突，同时保留有界数量的时序敏感关系，构建一个机器偏序；随后，时间自动机补全（TAC）在执行过程中根据演化时间状态消解这些被刻意保留的关系；最后，统计模型检验（Statistical Model Checking, SMC）刻画完工时间分布及时序变异性。

研究结论表明，在 14 个 ORB 和 LA 基准实例上，RAPO-RL-TAC 对比基于种群的邻域搜索（PNS）和遗传算法（GA）实现了平均中点完工时间的显著降低（分别低 2.92% 和 1.63%）。通过与复现的快速精英人工蜂群（fEABC）变体相比，其在7个实例上优于至少一个变体。消融研究进一步证明，相较于硬性强制执行学习到的关系，风险感知的选择性提交机制能显著降低平均中点完工时间（降低 13.85%）。该框架的重要意义在于，它通过有选择地提交机器冲突，成功地在保持竞争力的标称调度质量的同时，保留了区间不确定性下的时间灵活性，为 IJSP 提供了一种新的鲁棒调度方法论。

**3. 主要关键技术方法**

研究人员采用了以下关键方法：
- **图神经网络（Graph Neural Network, GNN）状态编码器**：将当前的偏析取图（partial disjunctive graph）结构与基于区间传播的完工时间上下界特征编码为节点嵌入和图级嵌入。
- **近端策略优化（Proximal Policy Optimization, PPO）**：用于训练 GNN 编码器和策略网络，学习全局的未决冲突边优先级。
- **风险感知确定性评估与开放边预算机制**：通过归一化时间重叠度和排序关键度构成时间冲突确定性评分，并引入每机器开放边预算来控制保留的时序敏感关系数量。
- **时间自动机补全（TAC）**：利用 UPPAAL-SMC 工具构建 Job、Controller 和 Machine 三个时间自动机模板，通过层级矩阵指导队列级选择，实现残差排序决策的在线补全和统计模型检验。

**4. 研究结果**

**4.1 基准实例比较与统计显著性分析**

在 14 个 ORB 和 LA 基准实例上进行的对比实验表明，RAPO-RL-TAC 实现了平均中点完工时间为 998.59，相较 PNS 和 GA 分别提高了 2.92% 和 1.63%。配对的双侧 Wilcoxon 符号秩检验证实了相对于 PNS（p=0.001）和 GA（p=0.002）的优越性在统计上显著，分别在13个和12个实例上取得更低值。与复现的 fEABC 相比无显著差异，但与 fEABC-LS 的比较中其表现较弱，尽管如此，RAPO-RL-TAC 在 LA21 和 LA24 实例上取得了所有对比方法中的最低中点值。

**4.2 随机种子鲁棒性分析**

研究人员通过三个独立 PPO/GNN 训练种子（种子 10, 20, 30）评估了训练随机性的影响。结果表明，所有14个实例的变异系数均低于1%，平均约0.43%，种子平均中点值的整体均值（999.77）与主实验（998.59）差异仅约0.12%，证明了训练过程在不同随机种子下的性能稳定性。

**4.3 计算与结构效率分析**

计算剖析显示，主要计算开销集中在离线训练阶段（较大实例可达约25000秒），而训练后推理时间低于6秒，TAC执行时间平均为12-18秒每轮。结构上，RAPO-RL在10x10实例上平均消解了96.60%的机器冲突，在15x15实例上该比例达到98.33%，仅保留12-19条未决关系交由TAC处理，显著减小了残差决策空间。

**4.4 消融研究**

在 ABZ9、FT20、LA21 和 LA24 四个异构实例上，RAPO-RL-TAC（平均中点 1023.50）优于仅用强化学习（RL-only，1053.75）和仅用统计模型检验（SMC-only，1094.00）以及硬约束执行（Hard-constraint，1188.00）。结果显示，移除任何单一阶段都会导致性能下降，其中硬性执行学习到的关系导致的性能下降最大（13.85%），这支持了将学习到的偏序信息作为队列级引导而非硬性前置约束的设计。

**4.5 超参数敏感性分析**

对时间确定性阈值 θ 和机器开放边预算 k 的敏感性测试显示，在默认设置 θ=0.05 和 k=3 下，四个消融实例的平均中点完工时间最低。预算 k 的敏感性呈现出预期模式：过小（k=1）或过大（k=5）均导致平均中点和性能较默认值有所提升（即变差），验证了默认设置在平衡冲突消解与保留灵活性方面的合理性。

**4.6 统计模型检验评估**

针对 ORB2 和 FT10 实例，UPPAAL-SMC 分析显示所有采样执行均能在时间界限 T=1300 内完成，时界完成概率为 1.0。然而，两者的完工时间分布形态差异显著：ORB2 的范围约为 942.91–1175.33，远宽于 FT10 的范围 938.20–1028.73，揭示出 ORB2 在采样的执行语义下具有更大的时间变异性。这证明了 SMC 能够提供固定序列中点指标无法反映的分布特征和时界行为信息。

**5. 讨论与结论**

讨论部分指出，RAPO-RL-TAC 在保持竞争性标称调度质量的同时，通过保留时序敏感关系实现了时间灵活性。统计检验确认了对PNS和GA的显著优势；与更强的fEABC-LS对比仍有差距，但在特定实例上展现出优势。随机种子分析确认了性能稳定性；计算剖析表明主要成本在离线训练。消融和敏感性分析支持了各组件设计的合理性与互补性。研究也承认了若干局限，包括针对单实例训练而未验证跨实例泛化能力、学习与形式化分析间的单向信息流，以及随机种子和超参数研究范围的有限性。

研究结论部分（翻译）：本研究确立了 RAPO-RL-TAC，一个用于区间作业车间调度问题（IJSP）的强化学习引导的形式化框架，证明了在 RAPO-RL 和 TAC 之间选择性地划分机器排序决策，能有效平衡区间不确定性下的调度质量与时间灵活性。通过在执?行前解决大部分机器冲突，该方法大幅减少了残差决策空间，同时保留了关键的不确定性敏感关系。对比实验证实，当最优序列依赖于实际时间实现时，这种选择性策略保留了必要调度灵活性，同时维持了有竞争力的标称调度质量。此外，消融结果表明，集成 RAPO-RL 和 TAC 有效降低了 IJSP 解的完工时间。统计模型检验通过揭示采样时间执行中的完工时间变异性补充了优化结果，提供了区间不确定性下调度行为的更广阔视角。总之，RAPO-RL-TAC 为缓解决策复杂性、保留序列灵活性以及严格评估 IJSP 中的时间性能提供了一种稳健的方法论。