ソルバーシステム
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-字シグモイド | 重み付き確率抽選 | 正準(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)。
多目的競争者
二つのパレート競争者は、多数目的 nsga3 表面とは別個に、優先順位-安全なタスク順序の種群を
多-目的ベクトルの上で進化させます。nsga2 は優越-基盤の競争者——高速非優越ソートと混雑距離
同点解消——であり、moead は分解-基盤の対抗馬で、問題を構造化された単体重みグリッドに沿った
スカラー Tchebycheff 部分問題に分割し、各部分問題の最近-重み近傍にわたって現行解を置換します。
| Solver | 機構 | 正準参照 |
|---|---|---|
nsga2 | 優越-基盤のパレート:高速非優越ソート、混雑距離 | Deb et al. (2002) |
moead | 分解-基盤のパレート:単体重みグリッド上の 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 マニフェストをエクスポートします。
厳密アダプタ
厳密アダプタは二つの形態の一つを取ります。オプション-バックエンドアダプタはオプション依存を
宣言し実行時にそのインポート根を検査します;バックエンドが不在ならば、パッケージインポート中に
重量級依存をインポートする代わりに、extra 名、目的、商用フラグ、および licensing 注記を伴う
MissingOptionalDependencyError を上げます。原生-有界アダプタは第三者依存を担わず、自らの
有界探索——一方は優先順位-実行可能な順序の列挙、他方は決定図分枝限定——により小さなインスタンス
を厳密に解き、インスタンスが対応タスク数を超えるとき 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 の
背後に留まり、決してバンドルされず、明示的な licensing 注記を担います;学術ライセンスが利用
可能です。より広いオプションバックエンドのプールは内部使用のため登録されたままです。
選択と学習層
選択層は、大域-最良ソルバーを決して主張することなく、ある問題に対しソルバーをランク付けします。
それは 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 はラベル
付き corpus から決定論的な距離-重み付き最近-傍モデルによってランク付けします(学習-モデル推薦)。
有監督選択器は訓練適合ではなく、留め置き汎化を報告します。交叉-検証プロトコルはラベル付き
corpus を、いかなるインスタンス、いかなるベンチマークファミリ、いかなる特徴化記録も訓練とテスト
の両分割に現れないよう分割し(partition_by_families、leave_one_family_out、
leakage_report)、残りのファミリで訓練し、留め置きファミリを採点します
(held_out_generalization、cross_validate)。その信頼は、漏洩-のない留め置き評価がそれを
支持するときのみ、メタデータ-のみを超えて上昇します。
learning_interface_catalog() は七つの具名の学習・ハイブリッドインターフェース——有監督
アルゴリズム選択、代理-支援探索、強化-学習フック、ハイパー-ヒューリスティック、方策-誘導修復、
学習された初期化、およびベンチマーク-のみベースライン——を登録します。各々が
LearningEvidencePolicy(訓練データ、漏洩制御、再現性、証拠クラス、証拠-層適格性)を宣言します。
二つはここで実装されます;他の五つは、その実現が訓練データを生む比較キャンペーンに依存する登録
された遅延インターフェースです。重い推定器バックエンドはオプションの learning extra の背後に
留まりインポート根で探られ、決してパッケージインポート中にインポートされません;不在は
MissingOptionalDependencyError を上げ、決定論的フォールバックは利用可能であり続けます。
性能保護
バッチ採点は BatchScoringProfile を通じて明示的です。現在のカーネルは標準-ライブラリ
フォールバックを用い、そのフォールバックを診断に記録します。これは API をベクトル化または
加速されたカーネルに対し準備されたまま保ちつつ、テスト済みで移植可能な経路を保ちます。