ジョブショップスケジューリング問題
工場の機械稼動計画を作成する問題
順序制約付きの組み合わせ最適化問題
N個の仕事をM台の機械で処理することを考える。
各仕事を処理する機械の順序(技術的順序)、および、各機械上での各仕事(作業)の処理時間は与えられているものとする。
JSPは、すべての仕事を処理し終えるまでの総所要時間(makespan)を最小にするようなの順序を決定する問題である。
ただし、各機械の種類はすべて異なり、同時に複数の作業を処理することができない。
また、各作業は、与えられた処理時間をかけて、各機械上で中断されることなく処理されるものとする。 以下にJSPの特徴をまとめた。
複数の仕事を複数の機械で処理することを考える。
目的
すべての仕事完了に要する時間（makespan）を最小にするようなスケジュールを求める 制約条件
仕事は処理順序を指定された作業からなる(技術的順序)
機械は同時に複数の作業を処理することはできない
各機械は必ず各作業を中断せずに処理する