どの変数から値を当てはめるか、変数に対して候補の値をどれから当てはめるか(あるいはどの値ではないとするか)によって問題を解く速さに大きな差が発生する例を、ジョブショップスケジューリング問題で示します。
(探索戦略のデモンストレーション - ジョブショップスケジューリング問題を例に もお読みください)
その他の探索戦略を使った場合のデモです。
問題の定義
ジョブは10個定義されています。
- 各色はそれぞれジョブ1～10を処理するのに必要な機械の種類を表します。
- 各ジョブは、定義された順序の機械で処理される必要があります。
- 横方向の長さは、各処理に必要な時間を表します。
- 各機械が一度に処理できるジョブは 1つだけです。
途中経過
この探索戦略では計画が全体的に組み替えられますが、似た解を探してしまって改善が滞る場合があります。 単純な探索戦略 よりは早い段階で良い解が得られる傾向にあります。