OR-Tools CP-SAT作业车间调度：如何获取首个可行解？

针对大规模作业车间调度（20000+任务）场景，要让CP-SAT求解器找到首个可行解就终止搜索，可通过自定义CpSolverSolutionCallback实现，具体步骤如下：

1. 自定义回调类 #

继承CpSolverSolutionCallback，重写OnSolutionCallback方法，找到第一个可行解后立即终止搜索：

from ortools.sat.python import cp_model

class FirstSolutionCallback(cp_model.CpSolverSolutionCallback):
    def __init__(self):
        super().__init__()
        self._found_first = False

    def OnSolutionCallback(self):
        if not self._found_first:
            # 可在此处记录解的信息，比如任务的开始/结束时间
            # 示例：遍历任务变量输出值
            # for task_id, start_var in task_start_times.items():
            #     print(f"任务{task_id}开始时间: {self.Value(start_var)}")
            print("已找到首个可行解")
            self._found_first = True
            self.StopSearch()  # 终止求解器搜索

2. 配置求解器参数 #

为加快首个可行解的查找速度，可调整求解器参数，优先聚焦可行解而非最优解：

solver = cp_model.CpSolver()
# 关闭全解枚举，聚焦首个可行解
solver.parameters.enumerate_all_solutions = False
# 启用预解析简化模型，减少计算量
solver.parameters.cp_model_presolve = True
# 采用组合搜索策略，提升可行解查找效率
solver.parameters.search_branching = cp_model.PORTFOLIO_SEARCH

3. 调用回调执行求解 #

在完成作业车间调度模型构建（包括任务顺序约束、机器资源约束等）后，传入回调类执行求解：

# 假设model是你已构建好的作业车间调度模型
callback = FirstSolutionCallback()
solve_status = solver.SolveWithSolutionCallback(model, callback)

# 处理求解结果
if solve_status in [cp_model.FEASIBLE, cp_model.OPTIMAL]:
    print("求解完成，已获取首个可行解")
    # 可通过solver.Value(var)或回调内记录的信息获取解的具体值
else:
    print("搜索终止前未找到可行解")

额外优化建议 #

• 模型构建时，尽量采用批量添加约束的方式（比如用AddAllDifferent替代循环添加NotEqual），减少模型构建时间
• 对于大规模任务，可适当调整变量的域范围（比如根据任务总时长预估合理的时间区间），缩小搜索空间

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