如何用约束规划建模带能量分配的可抢占任务以提升求解效率？

核心思路 #

针对最多允许1次中断的任务，将其建模为1个或2个连续工作区间：

• 无中断：单个连续区间，总工时为5
• 有中断：两个连续区间，区间之间至少间隔1天，两区间工时之和为5

通过区间变量（CP建模的核心工具）实现紧凑表达，避免冗余变量和分支逻辑。

变量定义 #

参数 #

• total_hours = 5：任务总工时
• min_block_days = 1：每个工作区间的最小天数（可按需调整）
• max_days：任务允许的最大完成天数（例如30，可自定义）

决策变量 #

1. 区间变量

   • block1：必选工作区间，代表第一个连续工作段。包含属性：
     • 起始日 start(block1)、结束日 end(block1)（整数，end(block1) >= start(block1) + min_block_days -1，单天任务的end=start）
     • 总工时 h1（实数，h1 > 0）
   • block2：可选工作区间，代表中断后的第二个连续工作段。包含属性：
     • 起始日 start(block2)、结束日 end(block2)（整数，仅当区间存在时有效）
     • 总工时 h2（实数，仅当区间存在时h2 >0）

2. 辅助变量

   • has_interrupt：二进制变量（1=存在中断，0=无中断），与block2的存在性绑定。

关键约束 #

1. 总工时约束

   h1 + h2 = total_hours
   

2. 区间有效性约束
   • 第一个区间必存在且工时为正：

     h1 > 0
     end(block1) >= start(block1) + min_block_days - 1
     

   • 第二个区间仅当有中断时存在，且工时为正、区间有效：

     has_interrupt <-> exists(block2)
     has_interrupt -> (h2 > 0 /\ end(block2) >= start(block2) + min_block_days -1)
     

3. 中断间隔约束
   若存在第二个区间，其起始日必须晚于第一个区间的结束日（保证至少1天中断）：

   has_interrupt -> (start(block2) > end(block1))
   

4. 工时细化约束（可选）
   若需追踪每日工时分配（如设置每日工时上限），可添加：

   forall(d in start(block1)..end(block1)): daily_hours[d] >=0
   sum(d in start(block1)..end(block1)): daily_hours[d] = h1
   

   注：无需追踪每日工时可省略此部分，仅保留区间总工时约束。

MiniZinc 示例代码片段 #

int: total_hours = 5;
int: min_block_days = 1;
int: max_days = 30;

% 区间变量
interval block1 optional = no;
interval block2 optional = yes;

% 工时变量
var float: h1 > 0;
var float: h2 >= 0;

% 中断状态变量
var bool: has_interrupt;

% 核心约束
constraint h1 + h2 = total_hours;
constraint end_of(block1) >= start_of(block1) + min_block_days - 1;
constraint has_interrupt <-> exists(block2);
constraint has_interrupt -> (h2 > 0 /\ end_of(block2) >= start_of(block2) + min_block_days -1);
constraint has_interrupt -> (start_of(block2) > end_of(block1));

% 区间范围约束
constraint start_of(block1) >= 1;
constraint end_of(block1) <= max_days;
constraint exists(block2) -> (start_of(block2) >=1 /\ end_of(block2) <= max_days);

% 目标函数：最小化总工期
var int: total_duration = if has_interrupt then end_of(block2) - start_of(block1) +1 else end_of(block1) - start_of(block1) +1;
solve minimize total_duration;

output [
    "是否中断：" ++ show(has_interrupt) ++ "\n",
    "第一区间：第" ++ show(start_of(block1)) ++ "天至第" ++ show(end_of(block1)) ++ "天，工时：" ++ show(h1) ++ "\n",
    if has_interrupt then "第二区间：第" ++ show(start_of(block2)) ++ "天至第" ++ show(end_of(block2)) ++ "天，工时：" ++ show(h2) ++ "\n" else ""
];

CPLEX 适配说明 #

CPLEX CP Optimizer支持区间变量建模，逻辑与MiniZinc一致：

• 使用 IloIntervalVar 定义必选区间，IloOptionalIntervalVar 定义可选区间
• 通过 IloIfThen 约束关联中断状态与可选区间的存在性
• 工时约束可通过 IloSum 或直接变量关联实现

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