Pyomo作业调度模型添加小时级资源约束的方法问询

问题背景 #

现有Pyomo作业调度模型：

• 核心二进制决策变量y[m,p,t]：表示作业p是否被分配至机器m的时间槽t（t为单台机器的时间槽排序）
• 已推导变量cum_time[m,t]：表示机器m截至时间槽t的累计运行时长（单位：小时）
• 需求：新增决策变量hourly[m,h]，统计机器m在小时h内启动/结束的作业数量，用于添加小时级资源约束，且无需重写整个模型

核心思路 #

无需重构模型，通过辅助二进制变量关联cum_time[m,t]与hourly[m,h]，将作业的时间槽分配映射到实际小时区间，最终统计小时级作业数量。

约束构建逻辑 #

以统计作业结束时间为例（启动时间逻辑完全类似）：

1. 定义小时h的时间区间为[h, h+1)
2. 引入辅助二进制变量z[m,t,h]：表示机器m的时间槽t对应的作业结束时间落在小时h内
3. 通过线性约束实现逻辑映射：
   • 若作业分配到时间槽t（sum(y[m,p,t])=1），则当cum_time[m,t]落在[h, h+1)时，z[m,t,h]=1
   • 若时间槽t无作业，则z[m,t,h]=0
4. 最终hourly[m,h]为所有对应z[m,t,h]的求和

Pyomo实现示例 #

import pyomo.environ as pyo
import numpy as np

# 基础参数与数据生成
num_machines = 10
num_slots = 5
num_jobs = 50
processing_time = np.random.rand(num_machines, num_slots)  # 各机器时间槽的作业处理时长
max_possible_time = int(np.sum(processing_time, axis=1).max()) + 2  # 最大可能总时长
hours = range(max_possible_time)

# 创建模型
model = pyo.ConcreteModel()

# 1. 核心决策变量：作业-机器-时间槽分配
model.y = pyo.Var(range(num_machines), range(num_jobs), range(num_slots), domain=pyo.Binary)
# 约束：每个时间槽最多分配一个作业
model.slot_assignment = pyo.Constraint(range(num_machines), range(num_slots),
    rule=lambda m, t: sum(model.y[m,p,t] for p in range(num_jobs)) <= 1)

# 2. 累计运行时长变量定义
model.cum_time = pyo.Var(range(num_machines), range(num_slots), domain=pyo.NonNegativeReals)
model.cum_time_def = pyo.Constraint(range(num_machines), range(num_slots),
    rule=lambda m, t: model.cum_time[m,t] == (model.cum_time[m,t-1] if t>0 else 0) + 
                      sum(processing_time[m,t] * model.y[m,p,t] for p in range(num_jobs)))

# 3. 辅助变量z[m,t,h]：标记作业结束时间所属小时
model.z = pyo.Var(range(num_machines), range(num_slots), hours, domain=pyo.Binary)
M = max_possible_time  # 大M常数，需覆盖最大可能的cum_time值

# z的逻辑约束：锁定cum_time所在小时区间
model.z_upper = pyo.Constraint(range(num_machines), range(num_slots), hours,
    rule=lambda m, t, h: model.cum_time[m,t] <= (h+1) - 1e-6 + M*(1 - model.z[m,t,h]))
model.z_lower = pyo.Constraint(range(num_machines), range(num_slots), hours,
    rule=lambda m, t, h: model.cum_time[m,t] >= h - M*(1 - model.z[m,t,h]))
# 约束：无作业的时间槽，z必须为0
model.z_zero = pyo.Constraint(range(num_machines), range(num_slots), hours,
    rule=lambda m, t, h: model.z[m,t,h] <= sum(model.y[m,p,t] for p in range(num_jobs)))

# 4. 小时级统计变量hourly[m,h]定义
model.hourly = pyo.Var(range(num_machines), hours, domain=pyo.NonNegativeIntegers)
model.hourly_def = pyo.Constraint(range(num_machines), hours,
    rule=lambda m, h: model.hourly[m,h] == sum(model.z[m,t,h] for t in range(num_slots)))

# 示例：添加小时级资源约束（每台机器每小时最多结束2个作业）
model.hourly_limit = pyo.Constraint(range(num_machines), hours,
    rule=lambda m, h: model.hourly[m,h] <= 2)

注意事项 #

• 大M取值：需足够覆盖最大可能的cum_time值，但不宜过大避免数值不稳定
• 启动时间统计：只需将cum_time[m,t]替换为cum_time[m,t-1]（t>0时）或0（t=0时），调整对应约束即可
• 简化场景：若每个时间槽必分配作业（sum(y[m,p,t])=1），可移除z_zero约束

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