🔢 mathematics

Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach

本文通过提出一种逻辑型本德斯分解法（Logic-Based Benders Decomposition），解决了考虑分时电价和机器状态的资源受限项目调度问题，该方法在最小化完工时间和能源成本方面显著优于整体式方法，同时展示了其在其他复杂调度问题上的泛化能力。

原作者： Corentin Juvigny, Antonín Novák, Jan Mandík, Zdeněk Hanzálek

发布于 2026-07-07

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Corentin Juvigny, Antonín Novák, Jan Mandík, Zdeněk Hanzálek

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位繁忙工厂的经理。你有一系列需要完成的任务，有一些一次只能做一件事的机器，以及一套关于哪些任务必须在哪些任务之前进行的严格规则。这就是经典的“资源受限项目调度问题”（RCPSP）。这就像是在组织一场盛大的婚礼，要协调餐饮供应商、乐队和场地的有限可用性，而且切蛋糕的环节不能在仪式之前进行。

但现在，增加了一个转折：电价会在一天之中不断变化。

在某些小时（比如凌晨3点），电价很便宜；而在另一些小时（比如下午5点），电价则非常昂으로。此外，你最耗能的机器（我们称之为“大烤箱”）有三种“情绪”：

烹饪中 (Proc)： 它正在运行并消耗能量。
闲置 (Idle)： 它处于预热状态但不烹饪。它使用少量的能量来保持待命。
关闭 (Off)： 它是冷的。重新启动它需要时间，并且会产生巨大的能量爆发。

你的目标是安排好每一项任务，以便既能尽可能快地完成工作，又能以最低的电力成本完成任务。这是一个平衡艺术：你是应该在电价便宜的时段运行烤箱，即使这意味着整个工厂都要等待？还是应该为了尽早完工而冲刺，即便这意味着要支付昂贵的峰值电力费用？

问题所在：一个单个大脑无法解决的谜题

作者尝试使用两种传统的策略来解决这个谜题：

“单体式”整数线性规划 (ILP)： 试图写出一个巨大的数学方程，同时考虑每一个任务、每一秒钟以及每种机器的状态。这就像是在蒙着眼睛、一只手抓着所有碎片的情况下，试图解开一个1000片的拼图。
“单体式”约束规划 (CP)： 这是另一种逻辑求解器，它非常擅长调度，但在加入复杂的“电价”规则时会感到吃力。

这两种方法在处理小规模谜题时表现尚可，但当工厂规模变大（任务增多）时，它们就会陷入困境。它们无法在合理的时间内找到最优解。

解决方案：“主厨”与“配菜员”

作者提出了一种更聪明的方法，称为基于逻辑的本德斯分解法 (Logic-Based Benders Decomposition, LBBD)。你可以把它想象成将工作分配给两个拥有不同技能的人：

主厨 (主问题 - The Master Problem)： 这位专家精通金钱。他观察电价表，并决定：“好吧，大烤箱应该在这些便宜的时段进行烹饪，而在那些昂贵的时段处于休息状态。” 他并不关心具体是哪块蛋糕进了烤箱；他只是设定了烤箱的“情绪”（开启、闲置、关闭）进度表以节省成本。他使用一种快速的数学求解器 (ILP) 来完成这项工作。
配菜员 (子问题 - The Subproblem)： 这位专家精通物流。他拿到主厨的烤箱进度表，并询问：“我们能否围绕这个烤箱进度表，在不违反任何规则的情况下，把其他任务（如蛋糕、装饰品、宾客）安排进去？” 他使用强大的逻辑引擎（约束规划）来检查计划是否可行。

他们是如何沟通的：

主厨制定一个计划。
配菜员尝试执行它。
如果成功了： 太棒了！他们检查是否可以做得更好。
如果失败了： 配菜员会说：“嘿，你不能在下午2点把烤箱设为‘关闭’模式，因为那时候蛋糕糊需要准备好了！”
主厨接收反馈，从中学习，然后制定一个新的计划，以避免那个特定的错误。

他们重复这种对话，直到找到完美的进度表。

他们的发现

作者在数百个不同的工厂场景中，将这种“团队协作法”与“单打独斗法”进行了对比测试：

当目标纯粹是节省资金（忽略完成时长）时： “团队协作法”（LBBD）是巨大的赢家。它能完美解决多达 480 个任务 的问题，而单打独斗的方法要么放弃，要么耗时过久。这就像是一个知道如何避开拥堵路段的 GPS，而单打独斗的司机只能靠猜测。
当目标是速度与金钱的结合时： “团队协作法”通常仍然是最好的，尤其是在大型、拥挤的工厂中。
例外情况： 如果工厂非常空闲（任务很少）且速度是唯一重要的因素，那么传统的“单体逻辑”方法（约束规划）有时会更快。

“魔术技巧”（泛化性）

这篇论文最令人兴奋的部分在于，这种“主厨/配菜员”的团队协作模式并不局限于这个特定的工厂。作者展示了你可以将这种协作策略应用于其他类型的调度问题，例如：

柔性作业车间 (Flexible Job Shops)： 其中一项任务可以在好几台机器中的任何一台完成。
带有“阻塞”的项目： 其中机器因为等待零件到达而处于停滞状态。

在所有这些案例中，将“能量/金钱”决策与“任务/时间”决策分开，都让计算机解决问题的速度更快，并找到了更好的解决方案。

总结

简单来说，这篇论文告诉我们：不要试图用一个巨大的大脑去解决整个能源调度谜题。 相反，将其拆分。让一位专家处理电费账单，让另一位专家处理任务物流。让他们互相沟通，直到他们达成共识，找到最佳方案。这种方法比旧方法更快、更聪明，并且能够处理比旧方法更庞大、更复杂的现实世界工厂。

技术摘要：考虑分时电价与机器状态的资源受限项目调度问题

1. 问题定义

本文研究了一种资源受限项目调度问题（RCPSP）的变体，该变体集成了分时（TOU）电价和机器状态转换。该问题涉及在满足前置约束和有限资源容量的情况下，对一组非抢占式任务进行调度。

主要特征包括：

高能耗资源： 一个特定的资源（ $R_0$ ）具有单位容量且属于高能耗资源。它可以存在三种状态：加工（proc）、空闲（idle）或关闭（off）。
状态转换： 状态之间的转换会产生特定的持续时间和能量成本。例如，开启或关闭机器会消耗大量的能量和时间。机器必须在“关闭”状态下开始并结束。
任务分类： 任务分为高能耗任务（需要 $R_0$ 处于“加工”状态）和非高能耗任务（不使用 $R_0$ ）。
目标函数： 目标是最小化**总能量成本（TEC）与完工时间（ $C_{max}$ ）**的凸组合。TEC 根据分时电价进行计算，电价随时间变化，甚至可能为负值。目标函数通过基于独立优化 TEC 和 $C_{max}$ 组件所得的下界进行归一化处理。

2. 研究方法

作者提出了并对比了三种不同的建模方法：

A. 单体模型（Monolithic Models）
通过两个紧凑的模型将问题作为一个整体进行求解：

单体整数线性规划（Monolithic ILP）： 使用时间索引变量构建的整数线性规划模型。它结合了通过 SPACES 算法预计算的加工区间之间的最优转换成本，以处理机器状态。
单体约束规划（Monolithic CP）： 利用可选区间变量（optional interval variables）的约束规划模型。该方法将任务处理和最优状态转换表示为区间变量，允许求解器动态确定转换的数量和位置。

B. 基于逻辑的 Benders 分解法（Logic-Based Benders Decomposition, LBBD）
其核心贡献是一种混合 LBBD 方法，将问题分解为两个耦合的子问题：

主问题（ILP）： 解决机器状态和能量成本优化问题。它确定高能耗任务的开始时间以及状态转换的序列。它利用改进的 SPACES 图来计算转换成本。
子问题（CP）： 进行 RCPSP 组件的可行性检查。在给定来自主问题的高能耗任务固定开始时间的情况下，尝试调度所有剩余的非高能耗任务，同时遵守资源容量和前置约束。
割平面（Cutting Planes）：
- 可行性割（Feasibility Cuts）： 当子问题不可行时生成，防止主问题再次选择同一组冲突的高能耗任务开始时间。
- 最优性割（Optimality Cuts）： 当子问题可行但产生的完工时间与主问题估计值不同时生成。这些割利用资源流图的临界路径，在主问题中强制执行完工时间的下界。

3. 核心贡献

问题建模： 引入了一种新的 RCPSP 变体，该变体将机器状态动力学（加工、空闲、关闭）与分时电价相结合，将以往针对单机研究的内容扩展到了多资源项目调度背景下。
新颖的 LBBD 框架： 开发了一种分解策略，将能量管理（主问题）与组合调度（子问题）分离。作者推导出了专门用于处理机器状态与 RCPSP 约束之间相互作用的特定 Benders 割。
泛化性： 证明了 LBBD 架构适用于其他调度问题，具体包括：
- 带有阻塞时间（blocking times）且以总加权延迟为目标的 RCPSP。
- 柔性车间调度问题（FJSP）。

4. 实验结果

实验基于 PSPLIB 数据集生成的实例进行，根据高能耗任务的密度（稀疏、标准、密集）以及能量成本与完工时间之间的不同权重参数（ $\alpha$ ）进行分类。

相对于单体模型的表现：
- 在大多数场景下，尤其是对于较大的实例（高达 480 个任务）以及当完工时间准则不占主导地位时（ $\alpha \to 1$ ），单体 ILP 和 CP 方法的表现均逊于 LBBD。
- 在求解大规模实例时，LBBD 比单体 CP 更快地求解出最优解，因为后者在处理巨大的搜索空间时表现挣扎。
- 单体 ILP 表现尚可，但通常比 LBBD 慢。
参数的影响：
- $\alpha = 1$ （仅考虑能量）： LBBD 表现异常出色，因为此时子问题简化为纯粹的可行性检查，CP 求解器可以高效处理此类问题。
- $\alpha < 1$ （混合目标）： 在标准和密集实例中，LBBD 依然保持领先。然而，在低 $\alpha$ 值（高完工时间权重）的稀疏实例中，单体 CP 有时会优于 LBBD，因为 LBBD 的子问题时间限制可能会阻碍对搜索空间的充分探索。
泛化结果：
- 在带有阻塞时间的 RCPSP 中，LBBD 在 30 分钟内找到了近 90% 的实例的最优解，而单体 CP 的成功率不足 5%。
- 在柔性车间调度问题中，在时间限制下，LBBD 比单体 ILP 更频繁地找到可行解（107/120 次对比 83/120 次）。

5. 重要性与主张

论文声称，所提出的 LBBD 方法 代表了能源感知调度问题（涉及复杂机器状态）的一个重大进展。其主要意义在于能够将连续的能量成本优化与离散的组合调度约束进行解耦，从而允许使用最合适的求解器（用 ILP 处理能量，用 CP 处理调度）分别解决这两个问题。

作者断言，这种分解不仅对特定的 RCPSP-TOU 问题有效，而且是一个可泛化的框架，适用于任何可以将高能耗活动与其他资源分配逻辑分离的调度问题。这项工作强调，虽然单体模型直观，但往往难以随着问题规模和复杂度的增加而扩展，而 LBBD 方法在不同的实例密度和目标权重下都能保持稳健性。

论文最后指出，未来的工作可以探索多能源消耗资源、更复杂的状态转换以及储能或现场发电的集成，以及能源价格不确定性的影响。