Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling

技術的サマリー：低コストなラベル、信頼性の高い選択

問題定義
本論文は、選択型ハイパーヒューリスティクスという観点からジョブショップスケジューリング問題（JSSP）を取り扱います。学習支援型ハイパーヒューリスティクスは、固定されたディスパッチングルールとエンドツーエンドの学習型コンストラクタの中間に位置し、実行可能性と解釈可能性を維持する一方で、2 つの主要なボトルネックに直面しています：

1. ラベル生成コスト: 教師あり学習には、部分スケジューラから終端状態まで候補ディスパッチングルールを「ロールアウト」して生成されたラベルが必要です。各意思決定点で各候補ルールに対して完全なロールアウトを行う場合、計算コストは $O(|H|T)$ となります。ここで、$|H|$ はルールの数、$T$ は残りの意思決定数です。
2. 選択の信頼性: 学習されたセレクターは、ノイズや過学習により、強力なデフォルトルールに対してわずかな改善を誤って予測する可能性があります。予測スコアが最も低いものを盲目的に追従することは、堅牢な固定ルールと比較して性能の低下を招く恐れがあります。

著者らは、これらの監督ラベルを生成するコストと、結果として得られるセレクターの信頼性の間のトレードオフを研究することを目的としており、特に、予測される利益が信頼できる場合を除き、学習されたモデルが強力なデフォルトルールから逸脱しないようにする方法に焦点を当てています。

手法
提案されるアプローチ「ロールアウト較正ハイパーヒューリスティクス」は、以下の 3 つの中核コンポーネントを統合しています：

1. 後悔正規化ロールアウトラベル:
   生のメイクスパンや下限正規化メイクスパンをターゲットとする代わりに、著者らは状態ごとの後悔ラベルを定義します：
   $$r(s, h) = \frac{m(s, h) - \min_{h' \in H_s} m(s, h')}{\min_{h' \in H_s} m(s, h')}$$
   ここで、$m(s, h)$ は状態 $s$ でルール $h$ を適用した結果のメイクスパンです。これにより、ターゲットは局所的なランキング信号に変換され、特定の状態における最良のルールは後悔が 0 となり、その特定の文脈内でのルールの相対的な性能が分離されます。

2. 不確実性ゲート付き選択:
   システムは、各候補ルールの後悔を予測するために文脈 K 近傍法（KNN）回帰器を採用します。信頼性を確保するため、ゲート機構が導入されます。セレクターは、予測される改善が不確実性調整マージンを超えた場合にのみ、固定されたデフォルトルール（$h_0$、トレーニングセット上で最良の固定ルールとして選択される）から予測された最良ルール（$h^*$）へ切り替えます：
   $$\pi_{gated}(s) = \begin{cases} h^* & \text{if } \hat{r}(s, h_0) - \hat{r}(s, h^*) > \lambda \hat{\sigma}(s, h^*) \\ h_0 & \text{otherwise} \end{cases}$$
   ここで、$\hat{\sigma}$ は $k$ 近傍の標準偏差（不確実性の推定値として機能）であり、$\lambda$ は切り替えの積極性を制御するハイパーパラメータです。

3. ロールアウト予算のトレードオフ:
   著者らは明示的にロールアウト幅（$b$、評価される候補ルールの数）とロールアウト深さ（$\kappa$、デフォルトに戻す前に候補ルールを追跡するステップ数）を変化させ、ラベル生成コスト（シミュレーションステップ/ウォールクロック時間）と最終テスト性能（相対パーセント偏差、RPD）の間のパレートフロンティアをマッピングします。

主な貢献

• 保守的な選択フレームワーク: 本論文は、積極的な最適化よりも信頼性を優先するゲート機構を提案し、学習されたセレクターが高い確信度なしに強力な固定ルールを放棄しないことを保証します。
• 後悔ベースの監督: 絶対的なメイクスパンではなく状態ごとの後悔を使用することで、この手法は局所的なルールランキングに焦点を当て、部分スケジューラにおける意思決定に対してより堅牢なものになります。
• 明示的なコスト - 品質分析: ラベル生成を固定された前処理ステップとして扱う多くの研究とは異なり、本研究はロールアウト深さと幅を体系的に変化させてコストと品質のトレードオフを定量化し、展開予算に関する実用的な指針を提供します。
• CPU のみの再現性: ラベル生成、KNN 適合、推論を含むパイプライン全体が、GPU 加速なしで CPU 上で実行されるように設計されており、深層強化学習アプローチとは対照的です。

実験結果
実験は、$6\times6$、$10\times10$、および $15\times10$ のサイズの合成 JSSP インスタンスで行われました。

• 性能: Regret-Gated セレクターは、すべてのスケールにおいて学習された手法の中で平均 RPD が最も低くなりました。それは、通常、これらの合成設定では FIFO または MOPNR である最良の固定ディスパッチングルールに非常に近く、平均 RPD のギャップはそれぞれ 0.70、0.67、0.06 でした。
• 堅牢性: ゲート付きアプローチは、Random-HH ベースラインの平均 RPD を 1 つ以上の桁（約 36–54% から約 0.8–2.8% へ）削減しました。
• アブレーション: この研究は、常に切り替える（argmin 選択）よりもゲート機構の方が安定していることを確認しました。最良の結果は、後悔ラベルと信頼度閾値 $\lambda=1.0$ で得られました。下界（LCB）バリアントはより悪いパフォーマンスを示し、不確実性は直接スコアボーナスとしてではなく、切り替えテストとして使用した方がよいことを示唆しています。
• コスト分析: 完全なロールアウト（$\kappa=\infty, b=|H|$）は最高品質をもたらしましたが、コストも最も高くなりました。浅いロールアウト（$\kappa=1$）は、著しく高い RPD をもたらしました。中間の深さは、許容可能な品質を維持しながらシミュレーションステップを大幅に削減する、実用的なトレードオフを提供しました。

意義と主張
本論文は、学習支援型ハイパーヒューリスティクスにおけるラベルコストと保守的な切り替えを研究するための再現性のある CPU のみのセレクターと評価プロトコルを提供すると、控えめに主張しています。

著者らは、自らの研究を、専門ソルバー、深層 RL ディスパッチャ（例：L2D、ScheduleNet）、および LLM 駆動のプログラム検索（例：FunSearch、ReEvo）を補完するものとして位置づけています。これらのシステムは設計空間の異なる点（多くの場合、新しいオペレータやエンドツーエンドの方策の発明）をターゲットにするのに対し、本研究は既存の解釈可能なルール間の選択という問題を分離しています。

主な意義は、実用的な展開課題に対処することにあります：ラベル生成にどの程度のシミュレーション予算を費やすべきか、そして学習されたセレクターが頻繁に切り替わることで性能を低下させないためにはどうすればよいかです。著者らは、その発見がテストされた合成、静的、決定論的領域に固有のものであると指摘しています。産業インスタンスや動的環境（例：機械の故障、オンライン到着）へのスケーリングには、異なるコスト - 品質のトレードオフと、潜在的に異なるラベル生成ダイナミクスが必要になると認めています。本研究は JSSP 一般を解決するものではなく、学習支援型ハイパーヒューリスティクスを信頼性が高く、費用対効果の高いものにするための制御された研究を提供するものです。