OR-Tools作业车间调度如何添加全局总功耗上限约束

核心思路 #

你要实现的全局功耗限制本质是跨机器的全局累积资源约束，完全可以用CP-SAT求解器内置的全局累积约束实现，不需要逐时间单位手动建变量做累加校验，后者性能极差，规模稍大就会出现求解超时问题。
这个约束的逻辑刚好匹配需求：每个任务运行时占用的资源量等于它的固定功耗值，全局资源的总容量就是你设定的功耗阈值，约束生效后会自动保证任意时间点所有运行中任务的功耗总和不超过阈值——总功耗没超的时候允许不同机器的任务并行，总功耗即将超限的时候自动错开高功耗任务的运行时段，不需要额外写重叠判断逻辑。
注意原有作业车间的单机器任务不重叠约束必须保留，它和全局功耗约束是叠加生效的关系：单机器约束保证同一台机器上的任务永远不会并行，全局功耗约束保证跨机器并行的任务总功耗不超标。

具体实现步骤 #

• 先按照作业车间调度的常规建模流程，完成基础变量和基础约束定义：
  • 为每个任务定义开始时间变量、结束时间变量、区间变量
  • 添加工序顺序约束：同一个作业内的任务必须按顺序执行，前序任务结束后后续任务才能启动
  • 添加单机器无重叠约束：同一台机器分配到的所有任务不能时间重叠
• 配置你设定的固定总功耗阈值常量
• 平铺收集所有任务的区间变量、对应任务的固定功耗值，组成两个顺序一一对应的列表
• 调用求解器的累积约束API，传入区间列表、功耗列表、功耗阈值，完成约束添加

对应测试用例的C#实现片段 #

//  --- 以下是作业车间基础建模逻辑，按常规方式实现即可 ---
CpModel model = new CpModel();
int horizon = allJobs.Sum(job => job.Sum(task => task.duration)); // 调度上界，取所有任务时长总和
// 存储每个任务的start、end、interval变量
var start = new IntVar[allJobs.Count][];
var end = new IntVar[allJobs.Count][];
var interval = new IntervalVar[allJobs.Count][];
// 按机器分组存储任务区间，用于加单机器无重叠约束
var machineToIntervals = new Dictionary<int, List<IntervalVar>>();
for (int j = 0; j < allJobs.Count; j++)
{
    start[j] = new IntVar[allJobs[j].Count];
    end[j] = new IntVar[allJobs[j].Count];
    interval[j] = new IntervalVar[allJobs[j].Count];
    for (int t = 0; t < allJobs[j].Count; t++)
    {
        var task = allJobs[j][t];
        start[j][t] = model.NewIntVar(0, horizon, $"start_j{j}_t{t}");
        end[j][t] = model.NewIntVar(0, horizon, $"end_j{j}_t{t}");
        interval[j][t] = model.NewIntervalVar(start[j][t], task.duration, end[j][t], $"interval_j{j}_t{t}");
        // 按机器归类
        if (!machineToIntervals.ContainsKey(task.machine)) machineToIntervals[task.machine] = new List<IntervalVar>();
        machineToIntervals[task.machine].Add(interval[j][t]);
    }
    // 加作业内部工序先后约束
    for (int t = 0; t < allJobs[j].Count - 1; t++)
    {
        model.Add(end[j][t] <= start[j][t + 1]);
    }
}
// 加单机器无重叠约束
foreach (var intervals in machineToIntervals.Values)
{
    model.AddNoOverlap(intervals);
}
// --- 以上是基础建模逻辑，以下是新增的全局功耗约束 ---
const int PowerThreshold = 7; // 替换为你实际需要的功耗阈值
var allTaskIntervals = new List<IntervalVar>();
var allTaskPower = new List<long>();
for (int j = 0; j < allJobs.Count; j++)
{
    for (int t = 0; t < allJobs[j].Count; t++)
    {
        allTaskIntervals.Add(interval[j][t]);
        allTaskPower.Add(allJobs[j][t].power);
    }
}
// 全局累积功耗约束，自动保证任意时间点总功耗不超过阈值
model.AddCumulative(allTaskIntervals, allTaskPower, PowerThreshold);

避坑说明 #

不要尝试手动逐时间单位创建变量、判断任务是否在运行、累加功耗做限制。这种写法的变量规模会随调度总时长线性增长，调度周期稍大就会产生数千甚至数万个冗余变量，求解效率会比用内置全局累积约束低几个数量级。AddCumulative是CP-SAT专门针对这类累积资源调度场景做的全局约束，内部会做高效的剪枝优化，是这类场景的标准实现方式。

内容的提问来源于stack exchange，提问作者Filipe