ジョブショップ・スケジューリング問題
この記事には独自研究が含まれているおそれがあります。 |
ジョブショップ・スケジューリング問題 (JSP; Job-shop Scheduling Problem) とは、順序関係のあるいくつかの作業を複数の機械で処理する場合に、評価指標(機械全体の稼働時間の最小化、作業の納期遅れの最小化など)を最適にするような機械の稼働スケジュールを決める問題である。
概要[編集]
- いくつかの仕事と機械がある。
- ひとつの仕事は定められた順序(技術的順序)で各機械の処理を受けて完成に至る。技術的順序および各機械での処理時間は所与である。
- ある機械が同時に複数の仕事を処理することはできない。
- これらの制約のもと、すべての仕事が完了するまでの所要時間を最小にするよう、各機械でどの仕事をどんな順序で処理するかを決定する。
- 所要時間をメイクスパンと呼ぶ。
仕事と機械の数が大きくなると最適解を求めることが劇的に難しくなる。この問題はNP完全であることが知られている[1]。
JSPの例[編集]
キャンプでカレーを作るとか身近な例
ガントチャート[編集]
横軸を時間、縦軸を機械とし、作業にかかる時間経過を機械ごとに表したグラフをガントチャートと呼ぶ。
デッドロック[編集]
ある順序を決定した時、その順序での作業が不可能である場合をデッドロックと呼ぶ。
"10 Tough Problems"[編集]
JSPにおける難問として有名な10題。ベンチマークテストとしてよく用いられる。abz7, abz8, abz9[2] および la21, la24, la25, la27, la29, la38, la40[3]
脚注[編集]
- ^ M.R.Garey; D.S.Johoson; R.Sethi (1976). “The Complexity of Flowshop and Jobshop Scheduling”. Mathematics of Operations Research (INFORMS) 1 (2): 117-129. doi:10.1287/moor.1.2.117. ISSN 0364-765X. JSTOR 3689278.
- ^ J. Adams, E. Balas and D. Zawack (1988), The shifting bottleneck procedure for job shop scheduling, Management Science 34, 391-401.
- ^ S. Lawrence (1984), Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement), Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania.