ジョブショップ・スケジューリング問題
いくつかの仕事と機械がある。
ひとつの仕事は定められた順序(技術的順序)で各機械の処理を受けて完成に至る。技術的順序および各機械での処理時間は所与である。
ある機械が同時に複数の仕事を処理することはできない。
これらの制約のもと、すべての仕事が完了するまでの所要時間を最小にするよう、各機械でどの仕事をどんな順序で処理するかを決定する。
所要時間をメイクスパンと呼ぶ。
仕事と機械の数が大きくなると最適解を求めることが劇的に難しくなる。この問題はNP完全であることが知られている。