ジョブショップ・スケジューリング問題 (JSP; Job-shop Scheduling Problem) とは、順序関係のあるいくつかの作業を複数の機械で処理する場合に、全体の時間が最小になるような機械の稼働スケジュールを決める問題である。仕事と機械の数が大きくなると最適解を求めることが劇的に難しくなる。この問題はNP完全であることが知られている。キャンプでカレーを作るとか身近な例横軸を時間、縦軸を機械とし、作業にかかる時間経過を機械ごとに表したグラフをガントチャートと呼ぶ。ある順序を決定した時、その順序での作業が不可能である場合をデッドロックと呼ぶ。JSPにおける難問として有名な10題。ベンチマークテストとしてよく用いられる。abz7, abz8, abz9 [1] および la21, la24, la25, la27, la29, la38, la40 [2]

出典:wikipedia