ジョブショップ・スケジューリング問題

ジョブショップ・スケジューリング問題 (JSP; Job-shop Scheduling Problem) とは、順序関係のあるいくつかの作業を複数の機械で処理する場合に、評価指標（機械全体の稼働時間の最小化、作業の納期遅れの最小化など）を最適にするような機械の稼働スケジュールを決める問題である。

概要

• いくつかの仕事と機械がある。
• ひとつの仕事は定められた順序（技術的順序）で各機械の処理を受けて完成に至る。技術的順序および各機械での処理時間は所与である。
• ある機械が同時に複数の仕事を処理することはできない。
• これらの制約のもと、すべての仕事が完了するまでの所要時間を最小にするよう、各機械でどの仕事をどんな順序で処理するかを決定する。
• 所要時間をメイクスパンと呼ぶ。

仕事と機械の数が大きくなると最適解を求めることが劇的に難しくなる。この問題は機械数が3以上のときNP完全であることが知られている^[1]。

ガントチャート

横軸を時間、縦軸を機械とし、作業にかかる時間経過を機械ごとに表したグラフをガントチャートと呼ぶ。

デッドロック

ある順序を決定した時、その順序での作業が不可能である場合をデッドロックと呼ぶ。

"10 Tough Problems"

JSPにおける難問として有名な10題。ベンチマークテストとしてよく用いられる。abz7, abz8, abz9^[2] および la21, la24, la25, la27, la29, la38, la40^[3]

関連問題

• フローショップ・スケジューリング問題：仕事の作業順序が全て同様の順序の問題である^[4]。
• オープンショップ・スケジューリング問題（英語版）：仕事の作業順序の制約が考慮されない問題である^[4]。