求解器系统
dispatchatlas.solve 拥有求解器元数据、选择、调度构造、修复、性能保障、基线族、可选适配器,
以及 NDSO 族。
该包仅导入 dispatchatlas.core。基准烟雾集成测试位于 tests/solve/,因此运行时包不依赖于
具体的基准生成器。
可运行示例: examples/compare_solvers.py 并行调度一组求解器并以一个已证明的精确最优解为其锚定。
注册表
SolverRegistry 存储带有丰富元数据的无状态求解器工厂:
- 能力标签,如
capacity-aware、precedence-aware、repair、local-search, 以及ndso - 支持的目标,如
makespan、energy,以及cost - 通过能力标签表达的已声明约束
- 默认停止准则
- 确定性或种子化随机的重放行为
- 解编码(
permutation、mapping、assignment,或native) - 可选依赖声明与商业后端披露
- 用于分阶段导出的证据-层级可见性
- 一个规范引用,或一个显式的引用-不适用理由
每个具名求解器族携带一个失败关闭的引用:一个具有规范开创性来源却省略其引用的族无法被构造, 而一个没有单一规范来源的族记录原因而非捏造一个。
from dispatchatlas.solve import SolverCapability, default_solver_registry
registry = default_solver_registry()
metaheuristics = registry.select(
required_capabilities=(SolverCapability.METAHEURISTIC,),
objective="makespan",
)注册表目录
注册表中的每个求解器,呈现于一个可排序、可搜索的表格中。该表及其总数由
default_solver_registry() 生成,因此下面的计数可从行本身计算。表格上方的一张能力覆盖图汇总有多少个注册表求解器声明每一项已声明能力。
Generated from the solver registry: 87 solvers across 6 groups — constructive (5), dispatching (14), exact (7), learning (11), metaheuristic (47), ndso (3).
Showing 87 of 87 solvers.
| Supported objectives | Notes | ||
|---|---|---|---|
adpso | metaheuristic | makespan, energy, cost | Inspect
|
age-moea-ii | metaheuristic | makespan, lateness, fairness, energy, cost, carbon | Inspect
|
ant-colony | metaheuristic | makespan, energy, cost | Inspect
|
apparent-tardiness-cost | dispatching | makespan, lateness, energy, cost | Inspect
|
arithmetic-optimization | metaheuristic | makespan, energy, cost | Inspect
|
artificial-bee-colony | metaheuristic | makespan, energy, cost | Inspect
|
artificial-fish-swarm | metaheuristic | makespan, energy, cost | Inspect
|
beam-search | constructive | makespan, energy, cost | Inspect
|
branch-and-bound | exact | makespan, energy, cost | Inspect
|
ccgp | metaheuristic | makespan, energy, cost | Inspect
|
clpso | metaheuristic | makespan, energy, cost | Inspect
|
cma-es | metaheuristic | makespan, energy, cost | Inspect
|
cpop | dispatching | makespan, energy, cost | Inspect
|
critical-path-tabu | metaheuristic | makespan, energy, cost | Inspect
|
cuckoo-search | metaheuristic | makespan, energy, cost | Inspect
|
d-clpso | metaheuristic | makespan, energy, cost | Inspect
|
d-depso | metaheuristic | makespan, energy, cost | Inspect
|
d-lshade | metaheuristic | makespan, energy, cost | Inspect
|
dan-dual-attention | learning | makespan, energy, cost | Inspect
|
decima-dag-rl | learning | makespan, energy, cost | Inspect
|
decision-diagram-sequencing | exact | makespan, energy, cost | Inspect
|
differential-evolution | metaheuristic | makespan, energy, cost | Inspect
|
earliest-deadline | dispatching | makespan, energy, cost | Inspect
|
earliest-finish-time | dispatching | makespan, energy, cost | Inspect
|
earliest-start | dispatching | makespan, energy, cost | Inspect
|
epso | metaheuristic | makespan, energy, cost | Inspect
|
exhaustive-enumeration | exact | makespan, energy, cost | Inspect
|
firefly-algorithm | metaheuristic | makespan, energy, cost | Inspect
|
fjsp-hgnn-drl | learning | makespan, energy, cost | Inspect
|
genetic-algorithm | metaheuristic | makespan, energy, cost | Inspect
|
grasshopper-optimization | metaheuristic | makespan, energy, cost | Inspect
|
gravitational-search | metaheuristic | makespan, energy, cost | Inspect
|
greedy-completion | dispatching | makespan, energy, cost | Inspect
|
grey-wolf-optimizer | metaheuristic | makespan, energy, cost | Inspect
|
guided-local-search | metaheuristic | makespan, energy, cost | Inspect
|
gurobi-exact | exact | makespan, energy, cost | Inspect
|
harris-hawks-optimization | metaheuristic | makespan, energy, cost | Inspect
|
heft | dispatching | makespan, energy, cost | Inspect
|
ibea | metaheuristic | makespan, lateness, fairness, energy, cost, carbon | Inspect
|
iterated-greedy-rs | metaheuristic | makespan, energy, cost | Inspect
|
jaya-algorithm | metaheuristic | makespan, energy, cost | Inspect
|
l2d-disjunctive-gnn | learning | makespan, energy, cost | Inspect
|
l2s-improvement | learning | makespan, energy, cost | Inspect
|
learned-priority-policy | learning | makespan, energy, cost | Inspect
|
logic-based-benders-decomposition | exact | makespan, energy, cost | Inspect
|
longest-processing-time | dispatching | makespan, energy, cost | Inspect
|
lshade | metaheuristic | makespan, energy, cost | Inspect
|
marine-predators | metaheuristic | makespan, energy, cost | Inspect
|
matheuristic-restricted-neighbourhood | metaheuristic | makespan | Inspect
|
max-min | dispatching | makespan, energy, cost | Inspect
|
min-min | dispatching | makespan, energy, cost | Inspect
|
minimum-slack | dispatching | makespan, energy, cost | Inspect
|
moead | metaheuristic | makespan, lateness, fairness, energy, cost | Inspect
|
monte-carlo-tree-search | metaheuristic | makespan, energy, cost | Inspect
|
moth-flame-optimization | metaheuristic | makespan, energy, cost | Inspect
|
ndso-core | ndso | makespan, energy, cost | Inspect
|
ndso-fast | ndso | makespan, energy, cost | Inspect
|
ndso-summit | ndso | makespan, energy, cost | Inspect
|
neh | constructive | makespan, energy, cost | Inspect
|
nsga2 | metaheuristic | makespan, lateness, fairness, energy, cost | Inspect
|
nsga3 | metaheuristic | makespan, lateness, fairness, energy, cost, carbon | Inspect
|
ortools-cp-sat | exact | makespan, energy, cost | Inspect
|
particle-swarm | metaheuristic | makespan, energy, cost | Inspect
|
peft | dispatching | makespan, energy, cost | Inspect
|
pulp-milp | exact | makespan, energy, cost | Inspect
|
residual-scheduling | learning | makespan, energy, cost | Inspect
|
rl-dispatching | learning | makespan, energy, cost | Inspect
|
rollout | constructive | makespan, energy, cost | Inspect
|
rvea | metaheuristic | makespan, lateness, fairness, energy, cost, carbon | Inspect
|
salp-swarm | metaheuristic | makespan, energy, cost | Inspect
|
sarsa-dispatching | learning | makespan, energy, cost | Inspect
|
scatter-search | metaheuristic | makespan, energy, cost | Inspect
|
selection-hyper-heuristic | metaheuristic | makespan, energy, cost | Inspect
|
serial-sgs-justification | constructive | makespan, energy, cost | Inspect
|
shifting-bottleneck | constructive | makespan, energy, cost | Inspect
|
shortest-processing-time | dispatching | makespan, energy, cost | Inspect
|
simulated-annealing | metaheuristic | makespan, energy, cost | Inspect
|
sine-cosine-algorithm | metaheuristic | makespan, energy, cost | Inspect
|
slim-self-labeling | learning | makespan, energy, cost | Inspect
|
sms-emoa | metaheuristic | makespan, lateness, fairness, energy, cost, carbon | Inspect
|
spea2 | metaheuristic | makespan, lateness, fairness, energy, cost, carbon | Inspect
|
squeaky-wheel | metaheuristic | makespan, energy, cost | Inspect
|
sufferage | dispatching | makespan, energy, cost | Inspect
|
surrogate-assisted-gp-hh | learning | makespan, energy, cost | Inspect
|
tabu-mrcpsp-mode-search | metaheuristic | makespan, energy, cost | Inspect
|
teaching-learning-optimization | metaheuristic | makespan, energy, cost | Inspect
|
whale-optimization | metaheuristic | makespan, energy, cost | Inspect
|
All objective support is declared registry metadata, not a performance claim. The solver recommender ranks these solvers by declared fit.
求解器适用性
哪些求解器适用于哪个基准族,读取自适用性矩阵。每个单元格都是声明的适用性,绝非性能主张:已验证的 单元格引用具名的公开活动、引文或测试,而近似单元格则由声明的求解器能力和基准族特征推导得出。下表由 公开适用性捆绑包生成,因此其状态总数可从各行自身计数。
Generated from the applicability matrix: 69 benchmark families by 87 public solvers. 10 verified · 5835 approximate · 158 not applicable.
Cell status is declared applicability, never a performance claim. Verified cells cite a named public campaign artifact, citation source, or test; approximate cells are derived from declared solver capabilities and benchmark-family traits and are labeled as such.
Showing 6003 of 6003 cells.
| Basis | |||
|---|---|---|---|
accelerator-coschedulingdistributed-computing | adpso | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; searches a continuous space decoded via the random-key-adapter with topological repair. |
accelerator-coschedulingdistributed-computing | age-moea-ii | Approximate | family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | ant-colony | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | apparent-tardiness-cost | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | arithmetic-optimization | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | artificial-bee-colony | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | artificial-fish-swarm | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | beam-search | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | branch-and-bound | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | ccgp | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | clpso | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; searches a continuous space decoded via the random-key-adapter with topological repair. |
accelerator-coschedulingdistributed-computing | cma-es | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | cpop | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | critical-path-tabu | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | cuckoo-search | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | d-clpso | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; searches a continuous space decoded via the spv-adapter with topological repair. |
accelerator-coschedulingdistributed-computing | d-depso | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | d-lshade | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; searches a continuous space decoded via the rounding-adapter with topological repair. |
accelerator-coschedulingdistributed-computing | dan-dual-attention | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | decima-dag-rl | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | decision-diagram-sequencing | Not applicable | native exact search caps at 12 tasks; family instances carry 96; optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | differential-evolution | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | earliest-deadline | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | earliest-finish-time | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | earliest-start | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | epso | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; searches a continuous space decoded via the random-key-adapter with topological repair. |
accelerator-coschedulingdistributed-computing | exhaustive-enumeration | Not applicable | native exact search caps at 8 tasks; family instances carry 96; optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | firefly-algorithm | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | fjsp-hgnn-drl | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | genetic-algorithm | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | grasshopper-optimization | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | gravitational-search | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | greedy-completion | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | grey-wolf-optimizer | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | guided-local-search | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | gurobi-exact | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | harris-hawks-optimization | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | heft | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | ibea | Approximate | family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | iterated-greedy-rs | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | jaya-algorithm | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | l2d-disjunctive-gnn | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | l2s-improvement | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | learned-priority-policy | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | logic-based-benders-decomposition | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | longest-processing-time | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
accelerator-coschedulingdistributed-computing | lshade | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; searches a continuous space decoded via the random-key-adapter with topological repair. |
accelerator-coschedulingdistributed-computing | marine-predators | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling. |
accelerator-coschedulingdistributed-computing | matheuristic-restricted-neighbourhood | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity; produces a static schedule for a family with dynamic arrivals/rescheduling; no repair or dispatching mechanism for the family's declared uncertainty. |
accelerator-coschedulingdistributed-computing | max-min | Approximate | optimizes one objective axis of a multi-objective family; family declares constraint features with no capability-tag counterpart: affinity. |
Cell status is declared applicability, never a performance claim. Verified cells cite a named public campaign, citation, or test; approximate cells are derived from declared solver capabilities and benchmark-family traits. The solver recommender scores solvers against this matrix by scheduling family.
派遣基线
捆绑的确定性基线是构造式列表-调度求解器。每个控制任务顺序;串行构造器尊重每个任务声明的 资源需求,并将每个任务分配给其最早-可用的被需求资源。每个族命名其规范开创性引用。
| Solver | 优先级依据 | 规范引用 |
|---|---|---|
earliest-start | 拓扑输入顺序 | 不适用(恒等基线) |
shortest-processing-time | 最短任务时长优先 | Smith (1956) |
longest-processing-time | 最长任务时长优先 | Graham (1969) |
earliest-deadline | 最早 deadline 优先(deadline-感知) | Jackson (1955) |
earliest-finish-time | 最早可达完成优先 | Topcuoglu et al. (2002) |
minimum-slack | 最小调度松弛优先 | Conway, Maxwell & Miller (1967) |
greedy-completion | 最早状态-感知完成优先 | Graham (1966) |
apparent-tardiness-cost | 最高表观-延迟-成本指数优先(deadline-感知) | Vepsalainen & Morton (1987) |
已退役的派遣族
资源-映射族被显式记录,而非静默地折叠进一个通用类型。它们控制资源分配,而非任务顺序,且 尊重-需求的串行构造器在当前核心问题模型下不暴露任何自由映射决策:
- 资源映射(
olb、met、mct、round-robin、load-balanced):构造器将每个任务 分配给其声明的资源,因此这些启发式没有可实现的自由度;执行-时间-感知的映射归属于目标与 约束工作,而非此基础。 - 类型标签缺失(
type-aware、domain-aware):需要当前核心问题模型不携带的 任务-类型与资源-类型标签。
retired_dispatching_families() 返回带有每-族理由与引用的完整账本。
基于秩的列表调度器
三个异构-感知的列表调度器共享一个两-阶段形态:一个静态优先级排定阶段依据平均执行时间与 通信成本在优先级 DAG 上为每个任务排秩,而一个处理器-选择阶段以优先级顺序通过串行构造器的 最早-完成规则绑定每个任务。每-资源执行时间来自一个可塑任务声明的执行模式,而一个刚性任务 退化为已记录的同构特化。
| Solver | 优先级依据 | 规范引用 |
|---|---|---|
heft | 向上秩 | Topcuoglu, Hariri & Wu (2002) |
cpop | 组合的向上-加-向下秩,关键路径任务优先 | Topcuoglu, Hariri & Wu (2002) |
peft | 乐观-成本-表秩 | Arabnejad & Barbosa (2014) |
就绪-集映射规则
三个批量映射规则依据每个优先级-就绪任务在其候选绑定上的最早完成为其评分,然后每步映射一个
任务。已发表的规则映射一批独立任务;此处该批即优先级-就绪集,因此这些规则拓展到有依赖的
工作负载,并在独立-任务实例上归约为已发表的行为。一旦可塑的 TaskSpec.modes 使其每-机器
期望-完成矩阵可表示,这些族便离开已退役账本转为一等注册。
| Solver | 优先级依据 | 规范引用 |
|---|---|---|
min-min | 最小最优完成优先 | Ibarra & Kim (1977); Braun et al. (2001) |
max-min | 最大最优完成优先 | Ibarra & Kim (1977); Braun et al. (2001) |
sufferage | 最大次优-减-最优完成差距优先 | Maheswaran et al. (1999) |
迭代贪心、禁忌与 RCPSP 基线
三个已发表的单-解方法搜索优先级-安全的任务顺序空间,各自将其规范机制投影到共享的
顺序-运行接缝上。serial-sgs-justification 是该平台首个资源-受限项目-调度(RCPSP)求解器。
| Solver | 机制 | 规范引用 |
|---|---|---|
iterated-greedy-rs | NEH 播种,带破坏-重构循环与固定-温度接受 | Ruiz & Stutzle (2007) |
critical-path-tabu | 在关键路径块移动上的高级禁忌搜索 | Nowicki & Smutnicki (2005) |
serial-sgs-justification | 带双重先右-后左对齐的串行调度-生成-方案解码 | Valls, Ballestin & Quintanilla (2005) |
元启发式基线
代表性的种子化元启发式基线共享相同的可行性、修复、评分与局部-搜索算子,各自带有其规范引用: 遗传算法(Holland 1975)、模拟退火(Kirkpatrick et al. 1983)、蚁群(Dorigo, Maniezzo & Colorni 1996)、 粒子群(Kennedy & Eberhart 1995),以及差分进化(Storn & Price 1997)。
编码适配器求解器
综合学习粒子群优化与成功-历史自适应差分进化在一个连续的实-值向量上搜索,每个任务对应一个 分量。每个核心对一个连续目标是通用的,因此其收敛行为直接在一个连续基准上验证,并通过一个 编码适配器绑定到调度问题,该适配器将一个向量解码为一个优先级-可行的任务顺序。
| Solver | 灵感 | 适配 | 编码 |
|---|---|---|---|
clpso | 综合学习粒子群(Liang et al. 2006) | 连续群解码为优先级顺序 | random-key |
d-clpso | 综合学习粒子群(Liang et al. 2006) | 在最小-位置-值解码之上的离散适配器 | spv |
lshade | 带线性种群缩减的成功-历史自适应 DE(Tanabe & Fukunaga 2014) | 连续差分进化解码为优先级顺序 | random-key |
d-lshade | 带线性种群缩减的成功-历史自适应 DE(Tanabe & Fukunaga 2014) | 在整数-秩取整之上的离散适配器 | rounding |
CLPSO 从一个综合-学习范例而非单一全局-最优学习每个维度,因此群的最佳适应度在单峰盆地上 单调改善。L-SHADE 从其成功历史自适应交叉与尺度-因子记忆,并将种群线性缩减至最少四个个体。 两者都报告一条收敛轨迹,且一个收敛-正确性测试在观测轨迹与已发表参考行为相矛盾时失败, 独立于种子-可复现性检查。
这些求解器是通过一个编码桥适配到离散域的连续优化器;它们不是任何先前代码的精确重实现,且在 比较性活动运行之前不作任何性能声明。
编码适配器
每个具名的连续-到-离散编码都是一个带有显式修复策略的独立适配器,因此没有编码被静默地折叠进 一个通用解码器。每个适配器将其解码的顺序修复为一个优先级-可行的顺序,并记录修复是否触发。
| 适配器 | 传递 | 解码规则 | 引用状态 |
|---|---|---|---|
random-key | 恒等 | 按截断键排序 | 规范(Bean 1994) |
spv | 恒等 | 最小位置值 | 规范(Tasgetiren et al. 2007) |
rounding | 恒等 | 整数秩槽位 | 不适用 |
sigmoid | S-形 sigmoid | 加权概率抽取 | 规范(Kennedy & Eberhart 1997) |
v-shaped | V-形幅度 | 加权概率抽取 | 规范(Mirjalili & Lewis 2013) |
tanh | 平移双曲正切 | 加权概率抽取 | 规范(Mirjalili & Lewis 2013) |
确定性解码(random-key、spv、rounding)忽略随机源;传递-函数解码消耗一个种子化源并在
固定种子下重放。rounding 适配器记录引用-不适用,因为最近-整数秩取整是一种通用离散化,
没有单一规范开创性来源。
多样化竞争者集合
多样化竞争者集合以一小撮近期的强力同侪将比较拓展到代表性基线之外,每个都是一个具名求解器, 其全文引用被投影到仅-顺序的决策空间上,而非一份庞杂的经典基线名单。一个同侪仅当其越过一个 场所-强度门槛时才留在公共赛场上:发表于后-2020 时效窗口内一个已索引、经同行评审的场所, 且场所层级被记录,以便读者基于证据而非声望来权衡它。
| Solver | 机制 | 场所 | 引用 |
|---|---|---|---|
epso | 带路径汇集的工作负载-偏置-初始化群 | Electronics (MDPI), 2023 — 已索引 | Anbarkhan & Rakrouki (2023) |
adpso | 带成功-自适应递减惯性的群搜索 | Sensors (MDPI), 2022 — 已索引 | Nabi et al. (2022) |
ccgp | 优先级-规则树的协同协进化 | Computers & Operations Research (Elsevier), 2024 — 顶级 OR | Zaki et al. (2024) |
每个同侪在其元数据中携带优势、注意事项,以及一个可运行-基线证据类别,以便推荐器能解释一个 求解器为何契合某个上下文。一个更广的经典基线集合——整数-键、偏置-随机-键,以及 分布-估计遗传算法,以及大-邻域、迭代贪心、禁忌、可变-邻域,与文化基因搜索——为内部比较保持 注册,但被排除在公共赛场之外,因为代表性启发式已携带其机制信号。在比较性活动运行之前不作 任何性能声明。
时效锚点
竞争者与相关-工作集合通过一个后-2020 时效锚点针对当前-十年的工作定位:Karimi-Mamaghan、 Mohammadi、Pasdeloup 与 Meyer(2023,通过集成进迭代贪心的 Q-learning 为排列流水车间学习 选择算子,European Journal of Operational Research 304(3):1296-1330, doi:10.1016/j.ejor.2022.03.054),以及 2024 IEEE Transactions on Evolutionary Computation 为分布式流水车间组调度提出的指标-驱动协作多-目标进化算法(doi:10.1109/TEVC.2023.3339558)。
多-目标竞争者
两个 Pareto 竞争者在一个多-目标向量上演化一个优先级-安全任务顺序的种群,区别于众-目标
nsga3 表面。nsga2 是基于支配的竞争者——快速非支配排序,带拥挤-距离平局决胜——而 moead
是基于分解的对衡,沿一个结构化单纯形权重网格将问题拆分为标量 Tchebycheff 子问题,并在每个
子问题的最近-权重邻域上替换在位者。
| Solver | 机制 | 规范引用 |
|---|---|---|
nsga2 | 基于支配的 Pareto:快速非支配排序、拥挤距离 | Deb et al. (2002) |
moead | 基于分解的 Pareto:单纯形权重网格上的 Tchebycheff 标量化 | Zhang & Li (2007) |
众-目标竞争者
nsga3 是具名的众-目标竞争者(Deb & Jain 2014, doi:10.1109/TEVC.2013.2281535),区别于
双-目标竞争者表面。它在优先级-安全的任务顺序上维护一个种群,在一个多-目标向量(makespan、
延迟与负载公平性)上评估每个顺序,并通过在 Das & Dennis 单位单纯形上的结构化参考点之上的
参考点-小生境选择,使每一代存活。参考点设计、解到其最近参考方向的关联,以及小生境-计数选择
是算法签名;该求解器在 multi-objective 之外声明 many-objective 能力,以便一个活动可
显式地选择它。
能力匹配
SolverRegistry.select 按能力、约束与目标匹配求解器。能力与约束要求都表达为能力标签并作为
合取匹配:一个同时需要 deadline-感知的众-目标活动传入
required_capabilities=(SolverCapability.MANY_OBJECTIVE,) 与
required_constraints=(SolverCapability.DEADLINE_AWARE,),注册表仅返回同时声明两者的求解器。
一个 objective 过滤器进一步将结果限制为声明支持该具名目标的求解器。
NDSO 族
NDSO 族是注册表的原生-编码求解器族:它直接在可行调度上搜索。它产生的每个调度都按构造可行
(一个有效性-按-设计的构造器在每一步构建一个尊重-优先级的顺序),因此该族携带 native 编码,
且从不运行编码/解码步骤或修复过程。该族组合一小组具名机制:
- 信心矩阵 — 一个按(位置、任务)单元存储已学习信任的稀疏存储,随着更好的调度强化其单元 而更新。
- 信心-加权投票 — 通过在由信心矩阵加权的种群上投票来合成精英调度;快速变体改用一个 非-加权多数投票。
- 数量-与-质量调度 — 数量调度设定一个候选改变多少;质量调度设定它从哪个指导源学习。
- 三-源指导 — 一个候选从合成精英(开发利用)、一个同侪(多样性),或一个消逝-知识源 (激进探索)学习。
- 统一自适应系数 — 一个非-线性调度将该族从探索转向开发利用,并驱动敏感性与 学习焦点二者;快速变体将其固定为一个固定值。
| 变体 | 组成 |
|---|---|
ndso-core | 信心-加权投票、自适应系数、三-源指导 |
ndso-fast | 多数-投票合成、固定系数、单一指导源 |
ndso-summit | 协调若干群并带总体合成的群间-议会 |
群间-议会
ndso-summit 变体是质量组成:它并行运行若干群并通过一个议会协调它们。每个群在其自己的种群
上组合核心机制;群间-议会使那些群作为一次搜索而非若干孤立运行来工作,并将其结果合成为一个
单一的总体精英——整个峰会所支持的调度。议会是一眼区分该变体之处:ndso-core 与 ndso-fast
各以一个种群搜索,而 ndso-summit 是为协调的多-群搜索构建的组成。
议会的协调行为与每-群诊断是可配置的,且它产生的每个调度都按构造保持可行。
消融图
消融图为每个具名机制枚举一个隔离配置,以便下游分析能归因每个机制的贡献。群内条目各自禁用 一个核心开关——信心矩阵、信心-加权投票、数量调度、质量调度、多-源指导结构、同侪源、 消逝-知识源,以及自适应系数。协调条目各自禁用一个议会参数——群内- 对 群间-协调,以及 总体合成。每个条目声明分析层采样其比较所在的运行-计数下限,并命名该层应用的统计检验 (一个配对非-参数显著性检验、一个带 Holm 多重-比较校正的 Friedman 平均-秩事后检验,以及一个 Cliff-delta 效应量)。被采样的比较由下游实验引擎物化;进程内 runner 证明每个隔离都可行。
一个分阶段导出过滤器治理一个报告范围可暴露哪些机制:基础范围仅暴露基础性机制,且一个 fail-closed 门在基础范围下抛出而非泄露一个更-快或更高-质量的机制,因此基础与快速范围无法 暴露仅-议会机制。收敛诊断——种群多样性、信心-矩阵熵、探索比率、资源负载、计时,以及改善 轨迹——是可选的且在禁用时不增加开销,且议会导出一个分析层无需导入任何求解器类型即可摄入的 JSON 清单。
精确适配器
精确适配器采取两种形态之一。可选-后端适配器声明一个可选依赖并在运行时检查其导入根;若后端
缺失,它们抛出 MissingOptionalDependencyError,带有 extra 名称、用途、商业标志与许可注记,
而非在包导入期间导入一个重量级依赖。原生-有界适配器不携带第三方依赖,并通过其自身的有界搜索
——一者枚举优先级-可行顺序,另一者为决策图分支定界——精确求解小实例,在实例超过所支持的任务
计数时抛出 UnsupportedCapabilityError。
| Solver | 方法 | 后端 | Extra | 商业 |
|---|---|---|---|---|
ortools-cp-sat | CP-SAT | ortools | exact | 否 |
pulp-milp | MILP / MIP | pulp | exact | 否 |
branch-and-bound | branch-and-bound / cut | ortools | exact | 否 |
logic-based-benders-decomposition | 基于逻辑的 Benders 分解 | pulp | exact | 否 |
exhaustive-enumeration | 穷举枚举 | 原生(无后端) | — | 否 |
decision-diagram-sequencing | 决策图分支定界 | 原生(无后端) | — | 否 |
gurobi-exact | MILP / MIP | gurobipy | exact-commercial | 是 |
公共的精确一小撮是代表性开放集合——CP-SAT、MILP、branch-and-bound 与基于逻辑的 Benders
分解——加上两个原生有界求解器与真正调用的 Gurobi 封装。商业 Gurobi 封装留在
exact-commercial extra 之后,从不被捆绑,并携带
一个显式许可注记;有一个学术许可可用。一个更广的可选后端池为内部使用保持注册。
选择与学习层
选择层为一个问题对求解器排名,而从不声称一个全局-最佳求解器。它消耗一个 SelectionFeatures
记录——difficulty、heterogeneity、objective_conflict、uncertainty、dynamism,以及
solver_sensitivity——与公共求解器元数据,并返回排名的 SolverRecommendation 行。每个推荐
携带一个 RecommendationSource(metadata 或 learned-model)、一个 ConfidenceLabel,
以及显式限制注记,因此一个元数据推荐绝不会被误认为一个已学习的推荐。
FEATURE_ORIGIN 将每个特征追溯到它读取的基准特征化度量;消费者将 dispatchatlas.bench 的
特征化度量映射进特征契约,因此 dispatchatlas.solve 仍仅导入 dispatchatlas.core。两个
选择器发布:RuleBasedSelector 仅从已声明能力与特征化排名(一个元数据推荐),而
SupervisedSelector 从一个带标签语料库通过一个确定性距离-加权最近-邻模型排名
(一个已学习-模型推荐)。
有监督选择器报告留出泛化,而非训练拟合。交叉-验证协议划分一个带标签语料库,使得没有实例、
没有基准族,且没有特征化记录同时出现在训练与测试划分中(partition_by_families、
leave_one_family_out、leakage_report),在剩余族上训练,并对留出族评分
(held_out_generalization、cross_validate)。其信心仅当一个无-泄露的留出评估支持它时才
升至元数据-唯一之上。
learning_interface_catalog() 注册七个具名的学习与混合接口——有监督算法选择、
代理-辅助搜索、强化-学习钩子、超-启发式、策略-引导修复、已学习初始化,以及一个仅-基准基线。
每个声明一个 LearningEvidencePolicy(训练数据、泄露控制、可复现性、证据类别、
证据-层级资格)。两个在此实现;其他五个是已注册的延迟接口,其实现取决于产生训练数据的比较性
活动。重型估计器后端留在可选的 learning extra 之后并按导入根探测,从不在包导入期间导入;
缺失抛出 MissingOptionalDependencyError,而确定性回退保持可用。
性能保障
批量评分通过 BatchScoringProfile 显式化。当前内核使用一个标准-库回退并在诊断中记录该回退。
这使 API 为向量化或加速内核保持就绪,同时保留一条经测试的、可移植的路径。