优化高能耗产线调度，兼顾电费波动与设备状态变化。
Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach
- 用逻辑割平面法分解调度与能耗问题，分步求解更高效。
- 在480任务规模下可最优求解，比纯约束规划快数倍。
- 适合关注能源成本、设备状态的智能制造场景。
本文研究考虑分时电价与设备状态（运行、空闲、关闭）的资源受限项目调度问题（RCPSP），目标是同时最小化总工期和总能耗成本（TEC），其中电价随时间波动且可为负值。提出两种新方法：单一约束规划（CP）模型和逻辑型贝德斯分解（LBBD）方法。后者将能耗部分建模为整数线性规划（ILP）主问题，任务调度部分用约束规划（CP）子问题处理。相比紧凑型混合整数规划（ILP）模型，两种方法均表现更优；而LBBD在不包含工期目标时显著优于单体式CP，在480任务实例上可求得最优解。此外，该方法可推广至含阻塞时间或加权延迟等类似结构的问题，如柔性作业车间调度。
原文摘要 · Abstract (English)
In this paper, we investigate the Resource-Constrained Project Scheduling Problem (RCPSP) with Time-of-Use (TOU) energy tariffs and machine states, a variant of RCPSP for production scheduling, where energy price is part of the criteria and one highly energy-demanding machine can be in one of the following three states: proc, idle, or off. The problem involves scheduling all tasks, respecting precedence constraints and resource limitations, while minimizing the combination of the overall makespan and the Total Energy Cost (TEC), which varies according to the TOU tariffs, which can take negative values. We propose two novel approaches to solve it: a monolithic Constraint Programming (CP) approach and a Logic-Based Benders Decomposition (LBBD) approach. The latter combines a master problem handling the energy cost solved using Integer Linear Programming (ILP) with a subproblem handling the RCPSP, resolved using CP. Both approaches outperform the monolithic compact ILP counterpart, but the LBBD significantly outperforms the monolithic CP in most cases, especially when the makespan criterion is not included in the objective function, solving to optimality instances with up to 480 tasks. Finally, we propose a way to generalize our LBBD approach to other problems sharing similar characteristics, and applied it to various problems, such as an RCPSP with blocking times & total weighted tardiness criterion, or a flexible job shop.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。