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