OR-Tools无法求解员工排班模型，Chuffed2秒出解，如何优化？

我正在为论文开发一个简单的员工排班模型，核心是根据时段t的需求工作量将专业员工分配至对应班次，当前为纯满足性问题。使用Chuffed求解器可在2秒内找到解，但OR-Tools完全无法求解，需要调整模型让OR-Tools在合理时间内输出可行解。

原MiniZinc模型代码 #

enum employees; % 所有员工
set of employees: runnersPrimary; % 负责 Runner 岗位的员工
array[positions] of float: positionsRatio; % 各岗位工作量占比，Runner 占50%

% 岗位枚举
enum positions = {bar, runner, kitchen, free};
set of employees: emergencyResponseOfficer; % 未使用的冗余集合

% 合同工时
array[employees] of int: contractHours;

% 时段工作量需求
set of int: shiftLength = 1..(7*24); % 一周排班，按小时划分
array[shiftLength] of int: workload;

% 班次设置
int: minShiftLength = 3;
int: maxShiftLength = 8;

% 决策变量：员工-时段的岗位分配
array[employees, shiftLength] of var positions: empToShift;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 辅助变量 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
array[shiftLength] of int: runnerLoad = [round(workload[s] * positionsRatio[runner]) | s in shiftLength];
set of positions: runnerAllowed = {runner, free}; % Runner 员工仅能分配这两类状态

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 硬约束 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 门店关闭时段（工作量为0）所有员工必须处于空闲状态
constraint forall(e in employees, s in shiftLength where workload[s] = 0)(empToShift[e,s] = free);

% 固定工时员工的工作时长需满足合同要求的范围
constraint forall(e in employees where contractHours[e] > 0)(
   sum(s in shiftLength)(empToShift[e, s] != free) >= contractHours[e] 
   /\ sum(s in shiftLength)(empToShift[e, s] != free) <= (contractHours[e] + 8)
);

% 最小班次长度约束：员工开始上班后，至少连续工作3小时
constraint forall(e in employees, s in 1..(length(shiftLength) - 3) 
                  where workload[s+1] > 0 /\ empToShift[e,s] = free /\ empToShift[e,s+1] != free)( 
  empToShift[e,s+2] != free /\ empToShift[e,s+3] != free
);    

% 最大班次长度约束：员工开始上班后，连续工作不能超过8小时
constraint forall(e in employees, s in 1..(length(shiftLength) - (maxShiftLength+1)) 
                  where workload[s+1] > 0 /\ empToShift[e,s] = free /\ empToShift[e,s+1] != free)(
  empToShift[e,s+9] = free
); 

% 班次结束后至少休息12小时
constraint forall(e in employees, s in 1..(length(shiftLength) - 12) 
                  where empToShift[e,s] != free /\ empToShift[e,s+1] = free) (
  empToShift[e,s+2] = free /\ empToShift[e,s+3] = free /\ empToShift[e,s+4] = free /\ 
  empToShift[e,s+5] = free /\ empToShift[e,s+6] = free /\ empToShift[e,s+7] = free /\ empToShift[e,s+8] = free /\ 
  empToShift[e,s+9] = free /\ empToShift[e,s+10] = free /\ empToShift[e,s+11] = free /\ empToShift[e,s+12] = free
);

% Runner 员工仅能分配允许的岗位
include "member.mzn";
constraint forall(e in runnersPrimary, s in shiftLength)(member(runnerAllowed, empToShift[e,s]));

% Runner 岗位的人员数量需匹配目标工作量
constraint forall(s in shiftLength)(
  sum(e in runnersPrimary where runnerLoad[s] = 0)(empToShift[e,s] = runner) = 0
  /\ sum(e in runnersPrimary where runnerLoad[s] != 0)(empToShift[e,s] = runner) = runnerLoad[s]
);

solve satisfy;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 输出 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

var int: targetRunnerLoad = sum(s in shiftLength)(runnerLoad[s]);
var int: assignedRunnerLoad = sum(s in shiftLength, e in runnersPrimary)(empToShift[e, s] != free);

output [ "time:\t" ];
output [ "\((t mod 24))\t" | t in shiftLength ];
output [ "\n\ntotal workload:\t" ];
output [ "\(p)\t" | p in workload ];
output [ "\nbarload:\t" ];
output [ "\(p)\t" | p in runnerLoad ];
output [ "\nkitchenload:\t" ];
output [ if s = 1 then "\n\(e)\t\(empToShift[e,s])\t" else "\(empToShift[e,s])\t" endif | e in employees, s in shiftLength ];
output [ "\nTarget runner:\(targetRunnerLoad)\tActual runner:\(assignedRunnerLoad)" ];

数据集 #

employees = {fixed1, fixed2, fixed3, fixed4, fixed5, fixed6, fixed7, fixed8, fixed9, fixed10, variable1, variable2, variable3, variable4, variable5, variable6, variable7, variable8, variable9, variable10, variable11, variable12, variable13, variable14, variable15, variable16, variable17, variable18, variable19, variable20, variable21, variable22, variable23, variable24, variable25, variable26, variable27, variable28, variable29, variable30, variable31, variable32, variable33, variable34, variable35, variable36, variable37, variable38, variable39, variable40};
contractHours = [24, 40, 24, 40, 24, 40, 24, 40, 24, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
positionsRatio = [0.20 , 0.50, 0.30, 0];
runnersPrimary = {fixed3, fixed4, fixed5, fixed6, fixed7, variable9, variable10, variable11, variable12, variable13, variable14, variable15, variable16, variable17, variable18, variable19, variable20, variable21, variable22, variable23, variable24, variable25, variable26, variable27, variable28};
emergencyResponseOfficer = {fixed1, fixed9, fixed10, variable8, variable31};
                                                          
%           1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17  18  19  20  21 22 23 24
workload = [0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 6, 8, 8, 8, 8, 8, 12, 12, 12, 12, 6, 6, 0, 0, %周一
            0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 9, 9, 9, 9, 9, 14, 14, 14, 14, 7, 7, 0, 0, %周二
            0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 9, 9, 9, 9, 9, 14, 14, 14, 14, 7, 7, 0, 0, %周三
            0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 9, 9, 9, 9, 9, 14, 14, 14, 16, 9, 9, 0, 0, %周四
            0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 10, 10, 10, 18, 18, 18, 11, 11, 11, 0, %周五
            0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 14, 14, 14, 14, 14, 14, 20, 20, 20, 18, 16, 16, 16, 16, %周六
            0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 12, 12, 12, 12, 12, 12, 18, 18, 18, 11, 11, 11, 0, 0]; %周日

针对OR-Tools的优化调整方案 #

1. 替换动态计算为常量，简化约束逻辑 #

• 将length(shiftLength)直接替换为常量168（7*24的结果），OR-Tools对常量的约束传播效率远高于动态计算值。
• 把工时范围的复合约束拆分为两个独立约束：

  % 固定工时员工至少满足合同工时
  constraint forall(e in employees where contractHours[e] > 0)(
     sum(s in shiftLength)(empToShift[e, s] != free) >= contractHours[e]
  );
  % 固定工时员工最多超出合同工时8小时
  constraint forall(e in employees where contractHours[e] > 0)(
     sum(s in shiftLength)(empToShift[e, s] != free) <= contractHours[e] + 8
  );
  

2. 移除低效通用函数，改用直接枚举判断 #

• 删除include "member.mzn"，将Runner岗位约束改为直接的枚举值比较：

  constraint forall(e in runnersPrimary, s in shiftLength)(
      empToShift[e,s] = runner \/ empToShift[e,s] = free
  );
  

  避免member函数带来的额外计算开销，OR-Tools对直接的枚举值比较支持更高效。

3. 引入辅助布尔变量优化序列约束 #

• 为每个员工的每个时段定义工作状态布尔变量，用正则约束替代当前的班次长度判断：

  % 辅助变量：标记员工e在时段s是否工作
  array[employees, shiftLength] of var bool: is_working = [empToShift[e,s] != free | e in employees, s in shiftLength];
  
  % 定义班次长度的正则自动机：空闲状态可任意停留；工作状态需连续3-8小时
  include "regular.mzn";
  constraint forall(e in employees)(
      regular(is_working[e, *], 2, [
          % 状态0：空闲，输入0（继续空闲）留0，输入1（开始工作）转1
          [0, 1],
          % 状态1-3：工作1-3小时，输入1继续留当前状态，输入0转0（违反最小长度）
          [0, 2], [0, 3], [0, 4],
          % 状态4-7：工作4-7小时，输入1继续留当前状态，输入0转0
          [0, 5], [0, 6], [0, 7], [0, 8],
          % 状态8：工作8小时，输入1违反最大长度，输入0转0
          [0, -1]
      ], 0, {0})
  );
  

  OR-Tools的正则约束传播器对序列型约束的处理效率远高于手动编写的forall约束。

4. 预定义工时统计辅助变量 #

• 为每个员工定义总工时辅助变量，减少重复计算：

  array[employees] of var int: total_hours = [sum(s in shiftLength)(is_working[e,s]) | e in employees];
  constraint forall(e in employees where contractHours[e]>0)(
      total_hours[e] >= contractHours[e] /\ total_hours[e] <= contractHours[e]+8
  );
  

5. 优化搜索策略 #

• 显式指定搜索顺序，优先处理约束更紧的变量（比如固定工时员工、高需求时段）：

  solve satisfy :: int_search(
      [empToShift[e,s] | e in employees where contractHours[e]>0, s in shiftLength where workload[s]>0],
      first_fail, % 优先选择域最小的变量
      indomain_min, % 优先选择最小枚举值
      complete
  );
  

6. 移除冗余定义 #

• 删除未使用的emergencyResponseOfficer集合，减少求解器的不必要处理。

7. 简化输出变量 #

• 将targetRunnerLoad和assignedRunnerLoad改为普通int变量，无需作为决策变量：

  int: targetRunnerLoad = sum(s in shiftLength)(runnerLoad[s]);
  var int: assignedRunnerLoad = sum(s in shiftLength, e in runnersPrimary)(is_working[e,s]);
  

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