MILP循环任务调度约束构建咨询：A类任务循环执行约束设计

问题梳理 #

针对4个A类任务[A1,A2,A3,A4]，需补充MILP约束实现：A4执行完成后必须循环回到A1，直至规划时域结束；同时保留已有的任务顺序约束（X_a=1表示任务A_a在某时刻执行，对a∈{1,2,3}，sum_{t∈T} X_{a,t} ≥ sum_{t∈T} X_{a+1,t}，T为规划时域）。

核心约束构建 #

要实现循环衔接，需从任务执行的时间逻辑入手，确保A4执行后必然衔接A1，且循环不中断。

1. 任务时序衔接约束 #

引入辅助二进制变量Y_{a,t}：

• 当a∈{1,2,3}时，Y_{a,t}=1表示A_a在时刻t执行，且A_{a+1}在t+1执行
• 当a=4时，Y_{4,t}=1表示A4在时刻t执行，且A1在t+1执行

通过以下线性约束定义Y_{a,t}的逻辑：

# 针对A1-A3与后续任务的衔接
∀a∈{1,2,3}, ∀t∈T\last(T):
X_{a,t} + X_{a+1,t+1} - 1 ≤ Y_{a,t} ≤ X_{a,t}
Y_{a,t} ≤ X_{a+1,t+1}

# 针对A4与A1的循环衔接
∀t∈T\last(T):
X_{4,t} + X_{1,t+1} - 1 ≤ Y_{4,t} ≤ X_{4,t}
Y_{4,t} ≤ X_{1,t+1}

2. 循环完整性约束 #

为避免循环中断，需保证除首个执行的任务外，每个任务的执行都由前序任务（或A4对A1）衔接而来：
引入二进制变量Z_a，Z_a=1表示A_a是规划时域内第一个执行的任务，添加约束：

# 每个后续任务的执行次数不超过前序衔接次数，或作为首个任务启动
∀a∈{1,2,3}:
sum_{t∈T} X_{a+1,t} ≤ sum_{t∈T\last(T)} Y_{a,t} + Z_{a+1}

# A1的执行次数不超过A4的衔接次数，或作为首个任务启动
sum_{t∈T} X_{1,t} ≤ sum_{t∈T\last(T)} Y_{4,t} + Z_1

# 确保仅有一个首个任务
sum_{a=1}^4 Z_a = 1

3. 循环次数一致性约束 #

结合你已有的顺序约束，可添加以下约束保证循环次数的合理性：

# A1的执行次数最多比A4多1（时域结束于A1执行的情况）
sum_{t∈T} X_1 ≤ sum_{t∈T} X_4 + 1
# A4的执行次数不超过A1（循环不会在A4处中断）
sum_{t∈T} X_4 ≤ sum_{t∈T} X_1

约束集整合 #

最终完整约束包含：

• 原有的任务顺序约束
• 上述任务时序衔接约束
• 循环完整性约束
• 循环次数一致性约束

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