MiniZinc约束规划并行任务调度模型性能优化咨询

我正在学习MiniZinc约束规划，编写了一个并行任务调度模型：将t个任务分配到m台机器执行，每个任务仅在一台机器上运行，目标是最小化最后一个任务的结束时间（Makespan）。该模型在小数据集（10个短时长任务、2台机器）下可正常求解，但当增加任务数量或延长任务时长时，搜索时间呈指数级增长（使用Chuffed求解器：10任务耗时2.7秒，11任务耗时14秒……）。

我已尝试通过设置start_times和end_times的变量边界、使用int_search搜索策略来优化性能，但仍希望模型能支持40个及以上任务的处理。请问有哪些优化该模型的建议？

附当前模型代码：

include "cumulative.mzn";

int: num_tasks = 10;
set of int : tasks = 1..num_tasks;
int: num_machines = 2;
set of int : machines = 1..num_machines;

% 定义每个任务的时长
array[tasks] of int: task_durations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

% 定义每个任务的开始时间和结束时间
array[tasks] of var 0..sum(task_durations): start_times;
array[tasks] of var 0..sum(task_durations): end_times;

% 定义任务-机器分配的二元变量，表示任务是否在对应机器上执行
array[tasks,machines] of var 0..1: task_on_machine;

% 定义Makespan为所有任务的最晚结束时间
var int: makespan = max(end_times);

% 确保每台机器同一时间仅处理一个任务
constraint forall(m in machines) (
  cumulative(
  start_times,
  task_durations,
  [task_on_machine[t,m] | t in tasks],
  1)
);

% 确保任务结束时间等于开始时间加任务时长
constraint forall(t in tasks)(
    end_times[t] >= start_times[t] + task_durations[t]
);

% 确保每个任务仅分配到一台机器
constraint forall(t in tasks)(
    sum([task_on_machine[t,m] | m in machines]) == 1
);


% 最小化Makespan
solve :: int_search(
    start_times ++ machines,
    smallest, indomain_min,
    complete
) minimize makespan;

% 输出每台机器上的任务执行时间信息
output [
    "Machine " ++ show(m) ++ ": " ++ show(start_times[t]) ++ " -> " ++ show(end_times[t]) ++ " (" ++ show(task_durations[t]) ++ ")\n"
    | m in machines, t in tasks where fix(task_on_machine[t,m] == 1)
] ++
[ "Makespan: " ++ show(makespan)
];

模型结构优化 #

精简任务分配变量 #

当前用t*m个二元变量存储任务-机器分配关系，任务数到40时仅这部分就有80个变量。可以改为单数组变量直接存储每个任务的分配机器，变量数从t*m降到t，大幅降低变量规模：

% 替换原task_on_machine变量
array[tasks] of var machines: assigned_machine;

% 调整cumulative约束逻辑
constraint forall(m in machines) (
    cumulative(
        start_times,
        task_durations,
        [bool2int(assigned_machine[t] == m) | t in tasks],
        1
    )
);

% 去掉原sum(task_on_machine[t,m])==1的约束，因为assigned_machine本身就保证每个任务分配到一台机器

收紧变量边界 #

• 计算makespan的理论下界：取「最长任务时长」和「总任务时长/机器数的向上取整」的最大值，作为makespan的初始下界。
• 将start_times和end_times的边界与makespan绑定，避免不必要的搜索空间：

  int: makespan_lb = max(max(task_durations), ceil(sum(task_durations) / num_machines));
  var makespan_lb..sum(task_durations): makespan = max(end_times);
  array[tasks] of var 0..makespan - task_durations[t]: start_times;
  array[tasks] of var task_durations[t]..makespan: end_times;
  

替换冗余约束 #

任务是连续执行无中断的，原end_times[t] >= ...可以直接改为等式，减少约束模糊性：

constraint forall(t in tasks)(
    end_times[t] == start_times[t] + task_durations[t]
);

搜索策略优化 #

优先搜索关键变量 #

Makespan优化的核心是长任务的分配和调度，调整搜索顺序优先处理长任务：

solve :: int_search(
    % 先按任务时长降序处理机器分配，再处理开始时间
    [assigned_machine[t] | t in tasks order by -task_durations[t]] ++ 
    [start_times[t] | t in tasks order by -task_durations[t]],
    first_fail,  % 优先选择域最小的变量，减少无效分支
    indomain_min,
    complete
) minimize makespan;

启用专用调度搜索策略 #

如果MiniZinc版本支持，使用schedule_search（针对调度场景设计的启发式）替代通用int_search：

solve :: schedule_search(
    start_times, task_durations, assigned_machine,
    largest_duration,  % 优先处理长任务
    earliest_start,
    complete
) minimize makespan;

加入重启机制 #

Chuffed支持重启策略，避免求解器陷入局部搜索瓶颈：

solve :: restart(geometric(100, 1.2)) :: int_search(
    [assigned_machine[t] | t in tasks order by -task_durations[t]],
    first_fail,
    indomain_random,
    complete
) minimize makespan;

求解器选择与配置 #

切换专用求解器 #

Chuffed适合小规模问题，大规模调度场景可以尝试Gecode或Opturion CPX：

• Gecode对cumulative约束的剪枝效率更高，支持调度专用模式；
• Opturion CPX在优化类问题上的表现更优。

启用求解器优化参数 #

• Chuffed：添加--optimize参数启用内置优化；
• Gecode：添加-mode schedule启用调度专用模式。

额外约束强化 #

添加负载均衡约束 #

提前限制每台机器的总任务时长不超过makespan，帮助求解器快速排除负载失衡的方案：

constraint forall(m in machines)(
    sum(task_durations[t] | t in tasks where assigned_machine[t] == m) <= makespan
);

对称性破缺 #

如果机器是同构的，添加约束避免对称解搜索：

% 固定第一个任务分配到机器1，减少对称分支
constraint assigned_machine[1] == 1;

% 长任务的分配机器不大于后续短任务的分配机器（按需调整）
constraint forall(t in 2..num_tasks where task_durations[t] >= task_durations[t-1])(
    assigned_machine[t] <= assigned_machine[t-1]
);

内容的提问来源于stack exchange，提问作者Hegyi István