選択グラフを用いた機械シーケンシング：暗黙の列挙アルゴリズム

機械シーケンシング問題の一つの定式化は、選択グラフにおけるミニマックスパスを見つけることです。本稿では、サーキットフリーグラフのシーケンスを生成し、そのシーケンス内の各グラフに対して若干修正したクリティカルパス問題を解くことで、この問題を解決する暗黙の列挙手続きを説明します。シーケンスの各新しい項は、以前の項から一つの選択アークを補完することによって生成されます。補完の対象となる選択アークはクリティカルパス上のものだけであるため、探索木は大幅に削減されます。これらの候補の評価は、各段階で探索を導くために使用されます。この手続きは、実際の生産で使用されているものや、いくつかのヒューリスティックによって生成されたものなど、いかなる実行可能なスケジュールから開始でき、次第に改善されます。したがって、合理的に「良い」実行可能なスケジュールで最適点に到達せずに止まる可能性もあります。ストレージ要件は、探索木の現在のノードに関連するデータに限られています。