调度问题示例

作业调度（Job Shop）— CP-SAT

使用 CP-SAT 原生后端求解 2 作业 × 2 机器的作业调度问题。

from optagent import ExactBackendName, ModelBuilder, Orchestrator, OrchestratorConfig, OrchestratorSolver, PhaseConfig

builder = ModelBuilder(metadata={"case": "job_shop_small"})

machine_a = builder.sequence_var(size=2, default=[0, 1], name="machine_a")
machine_b = builder.sequence_var(size=2, default=[0, 1], name="machine_b")

job1_a = builder.interval_var(start=0, length=2, lb_start=0, ub_start=8, lb_length=2, ub_length=2, name="job1_a")
job1_b = builder.interval_var(start=0, length=3, lb_start=0, ub_start=10, lb_length=3, ub_length=3, name="job1_b")
job2_b = builder.interval_var(start=0, length=2, lb_start=0, ub_start=8, lb_length=2, ub_length=2, name="job2_b")
job2_a = builder.interval_var(start=0, length=2, lb_start=0, ub_start=10, lb_length=2, ub_length=2, name="job2_a")

builder.constraint(builder.no_overlap(machine_a, job1_a, job2_a), name="machine_a_capacity")
builder.constraint(builder.no_overlap(machine_b, job1_b, job2_b), name="machine_b_capacity")
builder.constraint(builder.precedence(job1_a, job1_b, lag=0), name="job1_flow")
builder.constraint(builder.precedence(job2_b, job2_a, lag=0), name="job2_flow")
builder.minimize(builder.max(builder.interval_end(job1_b), builder.interval_end(job2_a)), name="makespan")
program = builder.freeze()

result = Orchestrator().run(
    program,
    config=OrchestratorConfig(
        required_backend=ExactBackendName.CP_SAT_NATIVE,
        strict_backend=True,
        phases=[PhaseConfig(name="cp_sat_job_shop", solver=OrchestratorSolver.CP_SAT, budget_iterations=30)],
    ),
)

运行方式：

PYTHONPATH=src python examples/scheduling/job_shop_small.py

流水线调度（Flow Shop）— CP-SAT

使用 CP-SAT 求解切割 → 钻孔 → 包装的流水线调度问题。

from optagent import ExactBackendName, ModelBuilder, Orchestrator, OrchestratorConfig, OrchestratorSolver, PhaseConfig

builder = ModelBuilder(metadata={"case": "flow_shop_cp_sat"})
seq = builder.sequence_var(size=3, default=[2, 1, 0], name="machine_order")
cut = builder.interval_var(start=0, length=2, lb_start=0, ub_start=5, lb_length=2, ub_length=2, name="cut")
drill = builder.interval_var(start=0, length=3, lb_start=0, ub_start=6, lb_length=3, ub_length=3, name="drill")
pack = builder.interval_var(start=0, length=1, lb_start=0, ub_start=8, lb_length=1, ub_length=1, name="pack")

builder.constraint(builder.no_overlap(seq, cut, drill, pack), name="machine_capacity")
builder.constraint(builder.precedence(cut, drill, lag=0), name="cut_before_drill")
builder.constraint(builder.precedence(drill, pack, lag=0), name="drill_before_pack")
builder.minimize(builder.interval_end(pack), name="makespan")
program = builder.freeze()

result = Orchestrator().run(
    program,
    config=OrchestratorConfig(
        required_backend=ExactBackendName.CP_SAT_NATIVE,
        strict_backend=True,
        phases=[PhaseConfig(name="cp_sat_flow_shop", solver=OrchestratorSolver.CP_SAT, budget_iterations=20)],
    ),
)

运行方式：

PYTHONPATH=src python examples/scheduling/flow_shop_cp_sat.py

使用预设求解调度问题

除了手动配置编排器，还可以直接使用预设：

from optagent import BuiltInStrategyPreset, ModelBuilder, Orchestrator

builder = ModelBuilder(metadata={"case": "scheduling_preset"})

machine_a = builder.sequence_var(size=3, default=[0, 1, 2], name="machine_a")
machine_b = builder.sequence_var(size=3, default=[0, 1, 2], name="machine_b")
# ... 定义 interval_var 和约束 ...

program = builder.freeze()

# 使用调度预设 — 自动配置进化搜索 + 局部优化 + 精确修复
result = Orchestrator().run(program, preset=BuiltInStrategyPreset.SCHEDULING_EVOLUTIONARY_REPAIR)

可用的调度预设：

预设	适用场景	特点
SCHEDULING_FOCUS	快速可行解	单阶段禁忌搜索
SCHEDULING_EVOLUTIONARY_REPAIR	高质量解	进化搜索 + 精确修复
SCHEDULING_MEMETIC_QUALITY	最优质量解	记忆算法

建模要点

• sequence_var：定义机器上的作业顺序
• interval_var：定义每个工序的时间区间
• no_overlap：同一机器上的工序不能重叠
• precedence：工序间的先后顺序约束