调度问题求解优化问询：多任务场景下求解器性能瓶颈及提速需求

问题概述 #

这是一类基于可再生资源池的调度问题，核心需求与当前困境如下：

• 问题定义：一组任务需从资源池中获取指定数量资源，目标是在给定周期内完成所有任务的同时最小化资源使用成本（优先使用编号更小的资源），核心约束为同一资源的任务时间不可重叠。
• 当前瓶颈：任务数量超过1000时，现有模型扩展性极差。已知最优解为所有任务复用资源1-15，但任务数达3000时，求解器无法在合理时间内找到该最优解，尝试多种搜索策略均无明显改善。
• Chuffed求解器测试结果：

n_tasks = 100，最优解34秒找到
n_tasks = 500，最优解3分43秒找到
n_tasks = 3000，可行解2分40秒找到，但4分钟仍未找到最优解

• 需求：大幅提升可行解与最优解的求解速度。

现有模型分析 #

现有代码的性能瓶颈主要来自三个方面：

1. 变量维度过载：resource_allocation是n_tasks × n_resources的二维0-1数组，3000×35=105000个变量导致搜索空间爆炸。
2. 搜索策略偏离最优方向：使用indomain_max优先分配大编号资源，与最优解（优先用小编号资源）的逻辑完全相反。
3. 冗余计算：用max([resource_allocation[t, r] | t in Tasks])判断资源是否被使用，大规模任务下该计算会显著增加求解器负担。

优化方案与代码实现 #

方案1：利用最优解先验信息，直接固定资源范围 #

已知最优解是复用资源1-15，可直接固定资源分配范围，彻底消除资源分配变量的搜索空间，仅需求解任务的时间安排：

n_tasks = 3000;
duration = [1 | i in 1..n_tasks];
optimal_n_resources = 15;  % 最优解使用的资源数量
n_resources = 35;
number_resource_needed = [15 | i in 1..n_tasks];
t_max = 18000;

include "cumulative.mzn";

% 模型参数
int: n_tasks;
set of int: Tasks = 1..n_tasks;
array[Tasks] of int : duration;

int: n_resources;
int: optimal_n_resources;
set of int: Optimal_Resources = 1..optimal_n_resources;
array[Tasks] of int: number_resource_needed;

int: t_max;

% 模型变量：仅保留任务开始时间
array [Tasks] of var 1..t_max: start;

% 核心约束：每个最优资源的任务时间不重叠（所有任务都使用该资源）
constraint forall(r in Optimal_Resources)(
    cumulative(start, duration, [1 | t in Tasks], 1)
);

% 验证任务资源需求满足（固定为15个资源，自动满足）
constraint forall(t in Tasks) (
    optimal_n_resources = number_resource_needed[t]
);

% 目标与输出
var int: nb_active_workers = optimal_n_resources;
var int: objective = sum(r in Optimal_Resources) r;

solve :: int_search(start, input_order, indomain_min) minimize objective;

output ["objective = \(objective) \n"];
output ["nb_active_workers = \(nb_active_workers) \n"];

方案2：调整原模型的搜索策略与变量结构 #

若需保留模型灵活性（不直接固定资源范围），可通过以下修改提升性能：

1. 反转资源分配的取值策略，优先分配小编号资源；
2. 引入辅助变量简化资源使用状态的计算；
3. 添加对称破缺约束减少冗余搜索。

优化后的原模型代码：

n_tasks = 3000;
duration = [1 | i in 1..n_tasks];
n_resources = 35;
number_resource_needed = [15 | i in 1..n_tasks];
t_max = 18000;

include "cumulative.mzn";

% 模型参数
int: n_tasks;
set of int: Tasks = 1..n_tasks;
array[Tasks] of int : duration;

int: n_resources;
set of int: Resources = 1..n_resources; 
array[Tasks] of int: number_resource_needed;

int: t_max;

% 模型变量
array [Tasks] of var 1..t_max: start;
array[Tasks, Resources] of var 0..1: resource_allocation;
% 辅助变量：标记资源是否被使用，简化目标计算
array[Resources] of var 0..1: resource_used;

% 约束
% 任务资源数量需求
constraint forall(t in Tasks) (
  sum(r in Resources) (resource_allocation[t, r]) = number_resource_needed[t]
);

% 资源时间不重叠约束
constraint forall(r in Resources)(
    cumulative(start, duration, [resource_allocation[t, r] | t in Tasks], 1)
);

% 辅助变量关联
constraint forall(r in Resources)(
    resource_used[r] = max([resource_allocation[t, r] | t in Tasks])
);

% 对称破缺：任务按开始时间排序，减少冗余搜索
constraint forall(t in Tasks where t < n_tasks)(
    start[t] <= start[t+1]
);

% 目标函数
var int: objective = sum(r in Resources) (r * resource_used[r]);
var int: nb_active_workers = sum(r in Resources) resource_used[r];

% 调整搜索策略：优先分配小编号资源，优先安排早开始时间
solve :: seq_search([
             int_search(resource_allocation, input_order, indomain_min),
             int_search(start, input_order, indomain_min),
             ])
      minimize objective;

output ["objective = \(objective) \n"];
output ["nb_active_workers = \(nb_active_workers) \n"];

额外优化建议 #

• 添加重启策略：使用solve :: restart(geometric(200, 1.2)) ...帮助求解器跳出局部搜索陷阱；
• 尝试其他求解器：如Gecode或OR-Tools，部分求解器在大规模调度问题上的剪枝效率更高。

内容的提问来源于stack exchange，提问作者Timothée HENRY