带换型的单机调度CP模型性能不佳，求优化方案

你的模型在任务数超过10后求解缓慢，核心问题是手动构建的两两顺序约束带来了大量冗余变量和约束，导致求解器搜索空间爆炸。以下是针对性的优化方案：

核心优化点 #

1. 消除冗余的顺序约束 #

原代码中对所有i≠j的任务对都创建了布尔变量，这会导致重复约束（比如order_1_2和order_2_1是完全互斥的重复定义）。只需要处理i<j的任务对，就能将布尔变量数量从n*(n-1)减少到n*(n-1)/2，直接减半。

2. 使用OR-Tools原生的序列变量（Sequence Variable） #

OR-Tools的CP-SAT提供了SequenceVar，专门为单机调度这类顺序优化问题设计，能更高效地建模任务顺序、无重叠约束和换型时间，内部优化的约束传播逻辑比手动写布尔变量快得多。

3. 精简变量数量 #

end_times变量可以直接通过start_times[task_id] + task["processing_time"]推导，无需单独定义，减少变量总数。

优化后的完整代码 #

from ortools.sat.python import cp_model
import random

# 问题参数
num_tasks = 20
processing_time_min = 1
processing_time_max = 10
changeover_time_min = 0
changeover_time_max = 5

# 生成随机任务
tasks = [
    {"id": i + 1, "processing_time": random.randint(processing_time_min, processing_time_max)}
    for i in range(num_tasks)
]

# 生成换型时间矩阵（仅保留i≠j的情况）
changeover = {
    (i + 1, j + 1): random.randint(changeover_time_min, changeover_time_max)
    for i in range(num_tasks)
    for j in range(num_tasks)
    if i != j
}

# 计算更紧凑的makespan上界
processing_time_sum = sum(task["processing_time"] for task in tasks)
max_changeover_sum = (num_tasks - 1) * max(changeover.values())
max_duration = processing_time_sum + max_changeover_sum

# 创建模型
model = cp_model.CpModel()

# 仅定义开始时间变量，结束时间通过推导得到
start_times = {task["id"]: model.NewIntVar(0, max_duration, f"start_{task['id']}") for task in tasks}
makespan = model.NewIntVar(0, max_duration, "makespan")

# 定义序列变量：用于建模任务的执行顺序
intervals = [
    model.NewIntervalVar(
        start_times[task["id"]],
        task["processing_time"],
        start_times[task["id"]] + task["processing_time"],
        f"interval_{task['id']}"
    )
    for task in tasks
]
sequence = model.NewSequenceVar(intervals, [], "task_sequence")

# 添加单机无重叠约束（由序列变量自动处理）
model.AddNoOverlap(sequence)

# 添加换型时间约束
for i in range(num_tasks):
    for j in range(num_tasks):
        if i != j:
            task_i_id = tasks[i]["id"]
            task_j_id = tasks[j]["id"]
            # 当任务i在任务j之前执行时，j的开始时间 >= i的结束时间 + 换型时间
            model.Add(
                start_times[task_j_id] >= start_times[task_i_id] + tasks[i]["processing_time"] + changeover[(task_i_id, task_j_id)]
            ).OnlyEnforceIf(sequence.IsBefore(i, j))

# 关联makespan与所有任务的结束时间
for task in tasks:
    model.Add(makespan >= start_times[task["id"]] + task["processing_time"])

# 目标：最小化makespan
model.Minimize(makespan)

# 求解
solver = cp_model.CpSolver()
# 可选：设置时间限制
# solver.parameters.max_time_in_seconds = 60.0
status = solver.Solve(model)

# 输出结果
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"Makespan: {solver.Value(makespan)}")
    # 按开始时间排序输出任务顺序
    sorted_tasks = sorted(tasks, key=lambda x: solver.Value(start_times[x["id"]]))
    print("任务执行顺序：")
    for task in sorted_tasks:
        start = solver.Value(start_times[task["id"]])
        end = start + task["processing_time"]
        print(f"任务{task['id']}: 开始={start}, 结束={end}, 加工时间={task['processing_time']}")
else:
    print("未找到可行解")

额外优化建议 #

• 如果任务数继续增大（比如超过50），可以添加分支启发式策略，加速最优解搜索：

  solver.parameters.search_branching = cp_model.PORTFOLIO_SEARCH
  solver.parameters.cp_model_presolve = True
  

• 可以设置时间限制，避免求解器无限期运行，比如solver.parameters.max_time_in_seconds = 300（5分钟）。

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