ジョブショップ・スケジューリング問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > ジョブショップ・スケジューリング問題の意味・解説 

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

(Job Shop Scheduling から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/04/04 06:51 UTC 版)

ジョブショップ・スケジューリング問題 (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]

関連問題

脚注

  1. ^ 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. 
  2. ^ J. Adams, E. Balas and D. Zawack (1988), The shifting bottleneck procedure for job shop scheduling, Management Science 34, 391-401.
  3. ^ 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.
  4. ^ a b MacCarthy 1993, pp. 61–62.

参考文献

  • MacCarthy, B.; Liu, J. (1993). “Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling”. International Journal of Production Research (Taylor & Francis) 31 (1): 59-79. doi:10.1080/00207549308956713. ISSN 1366-588X. 

関連項目




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ジョブショップ・スケジューリング問題」の関連用語

ジョブショップ・スケジューリング問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ジョブショップ・スケジューリング問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのジョブショップ・スケジューリング問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS