scheduling problemとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > scheduling problemの意味・解説 

スケジューリング問題

読み方すけじゅーりんぐもんだい
【英】:scheduling problem

概要

限られた資源用いて多数ジョブ効率よく時間内に実行しなければならないとき, 必要な資源をいつ, どのジョブ割当てるかを決定する問題. 代表的なスケジューリング問題としてジョブショップ問題, 資源制約下のプロジェクトスケジューリング, 勤務スケジューリング, 搬送スケジューリングなどの問題がある.

詳説

 スケジューリング問題は, 多く仕事あるいは活動 (スケジューリング用語ではジョブ (job) という) を種々の制約のもとで実行しなければならないとき, 実行可能なスケジュールや, 最適なスケジュール見出す問題である. 従って, 効率的な運用求められるあらゆる組織においてスケジューリング問題が存在するが, 特に, 生産, 配送, プロジェクト, 要員勤務のスケジューリング問題に対して理論および実務両面において高い関心持たれている [1, 8, 9, 10, 11]. ここではこれらの基本問題1つであるジョブショップ問題 (job shop problem) を中心に説明する(中項目「スケジューリング理論」参照).

 多数ジョブが1台以上の機械一部または全部によって予め指定され順序 (以下では工程順序という) に従って順次処理される. ただし, どのジョブ一時に高々1機械でしか処理されないし, どの機械一時に高々1ジョブしか処理できない. また, 特に断りのない限り, 作業 (各機械におけるジョブの処理) は, いったん開始されると, 終了まで中断されることはない. このようなシステムジョブショップと言われる. ジョブショップにおいて 所与評価基準(目的関数)を最適にするよう, 各機械でのジョブ処理順序見出す, すなわち, 順序づけの問題ジョブショップ問題(または機械順序づけ問題と言われる.

 ジョブショップ問題生産スケジューリング問題の典型的なモデルである [1, 8, 11]. また, 機械ボトルネックとなっている資源代名詞考えれば, ジョブショップ問題適用範囲極めて広い.

 ジョブショップ問題仮定一部変えることによって種々のモデル考えられる. 代表的な例として, 1機械問題 (one-machine problem), 並列機械問題 (parallel-machine problem), フローショップ問題 (flow shop problem), オープンショップ問題 (open shop problem) などがある[1, 2, 9].

 1機械問題では, 全てのジョブがたった1台の機械処理される場合に, ジョブの処理順序決定する問題である.

 並列機械問題は, 2台以上の機械存在し, 各ジョブはそれらのうちのいずれか1台で一度だけ処理されるとき, 各ジョブ対す機械割当てと, 各機械割当てられたジョブの処理順序決定する問題である. 特に, 全機械が同一場合同一並列機械問題 (identical parallel-machine problem), 機械によって処理速度異な場合一様並列機械問題 (uniform parallel-machine problem), ジョブ機械組合せによって, 処理時間異な場合無関連並列機械問題 (unrelated parallel-machine problem) と言う.

 ジョブショップ問題において, 工程順序がどのジョブについても同じ場合を特にフローショップ問題という. また, ジョブ一部または全ての工程順序任意であって, これも最適化対象となる場合オープンショップ問題という.

 以上のジョブショップモデルでは, 機械間のジョブ搬送仕掛かりバッファ有限性, ジョブ間の段取時間などが考慮されていず, 必ずしも現実反映していない. その意味はしばし古典的モデル [4] と言われる. これをさらに拡張したモデルとしてフレキシブルフローショップスケジューリング (flexible flow shop scheduling) [11], FMSスケジューリング (flexible manufacturing system scheduling) [10], ロボティックセルスケジューリング (robotic cell scheduling) [5], 資源制約付きスケジューリング (scheduling under resource constraints) [1], グループスケジューリング (group scheduling) [6] などがしばしば検討されている. フレキシブルフローショップにおいてはフローショップ構成する工程一部または全て並列化されている.FMSは, 1台で多種加工可能なマシニングセンタAGV (automated guided vehicle), ロボット, AS/RS(automated storage/retrieval system)などの自動物流機器構成されている. 特に, 1台のロボット少数マシニングセンタからなる小規模FMSはロボティックセル (またはFMC) と言われる. これらのシステムでは加工スケジューリングのみならず, 搬送などの物流スケジューリングシステム全体効率化大きな影響を及ぼす. ジョブショップにおいて機械以外にボトルネックとなる資源(工作機械治工具, 計算機メモリなど) が存在し, それらのスケジューリング考慮されなければならない場合資源制約付きスケジューリング問題と言われる. ジョブ間に段取時間存在するとき, GT (group technology) に基づいて, 段取時間比較小さジョブグループにまとめ, グループ間で行う順序づけをグループスケジューリングと言う. ジョブショップ問題 (及びその拡張問題) では, ジョブまたは作業種々の制約課せられることが多い. 典型的な制約条件として処理順序に関するジョブ間の先行制約, 最早開始時刻または準備時間制約などがある.  最適化 (ここでは最小化) すべき目的関数代表例として, 全ジョブの終了時間を表す最大完了時間 (メークスパン (makespan) と言うことがある), ジョブシステム滞留し時間総和を表す滞留時間和, 納期からの遅れの指標となる最大納期遅れや遅れ和が挙げられる[1, 2, 3, 8, 9, 10].さらに複数目的関数考慮した多目的スケジューリング問題もある[1, 8, 11].

 以上に述べてたように, ジョブショップ問題は, ショップ (工程) の構成, ジョブ処理環境及び目的関数によって分類されるので, これらを (待ち行列におけるケンドール (Kendall) 記号風の) 3つ組み記法 (\alpha |\beta |\gamma\, ) によって記述することができる [2, 9]. すなわち, \alpha\, 工程, \beta\, ジョブ処理環境, \gamma\, 目的関数である.

 表1それぞれの項目における記号例とその表示意味を示す. \alpha |\beta |\gamma\, による問題表規の例である.



 ジョブショップ問題理論的研究起源1954年ジョンソン (S.M.Johnson) の定理 [7] にまで遡る.

 ジョンソン定理: 2機械フローショップにおいてA_j\, , B_j\, それぞれ第1機械及び第2機械におけるジョブj(=1,2,\cdots,n)\, 処理時間とする. このとき, 最大完了時間最小化問題(F2 || C_{max}\, )の最適順序はつぎの順序付け規則与えられる. すなわち,


\max (A_j,B_{j+1}) < \max (A_{j+1},B_j)\,


 ならば, ジョブj\, ジョブ(j+1\, )より先に処理する. 等号場合は, どちらが先でもよい.

 これ以後この様最適な順序づけ規則研究進められたが, 1970年代初期NP完全理論の誕生と共に, 多くのスケジューリング問題が(問題規模多項式オーダー計算量で解くことが保障されないNP困難になることが証明された [2]. 例えば, 1 || \Sigma c_j\, , 1 || T_{max}\, \, , P || \Sigma c_j, J2 || c_{max}\, (J2は2機械ジョブショップを表す)などは最適順序づけ規則存在するが, 1 | r_j | T_{max}\, , 1 | prec | \Sigma c_j\, , p1 || c_{max}, F2 || \Sigma c_j\, NP困難となる.

 しかし, NP困難問題だからといって, 必ずしも手に負えないという訳ではない. 工夫され分枝限定法などを用いることによって (希な最悪例を除いて) かなり大きな問題例まで解くことが可能である (例えば, [3] 参照). ただし, 実際上のスケジューリング問題に対して効率的な近似解放が必要である(中項目「スケジューリングアルゴリズム参照).



参考文献

[1] J. Blazewicz, W. Cellary, K. Slowinski, J. Weglarz, Scheduling under Resource Constraints : Deterministic Model, J. C. Balzer, Basel, 1986.

[2] P. Brucker, Scheduling Algorithms, Springer, 1995.

[3] J. Cheng, H. Kise, G.Steiner and P. Stephenson, Branch-and-bound algorithm using fuzzy heuristics ofr solbing large-scale flow-shop scheduling problems, Fuzzy Set Based Heuristics for Optimization (J-L. Verdega Ed.),Springer (2003), 21-47.

[[4] R. W. Conway, W. L. Maxwell, and L. W. Miller, Theory of Scheduling, Addison-Weseley Reading, 1967. 関根智明監訳, 『スケジューリング理論』, 日刊工業新聞社, 1971.

[5] M. Dawande, M.N, Geismar, S.P. Sethi and C. Sriskandarajah, "Sequencing and Scheduling in Robotic CellsRecent Developments" Journal of Scheduling. 8(2005), 1099-1423.

[6] 人見勝人, 中島勝, 吉田照彦, 小島敏彦,『GTによる生産管理システム』, 日刊工業新聞社, 1981.

[7] S. M. Johnson, "Optimal Two and Three Stage Production Schedules with Setup Times Included," Naual Research Logistics Quartry, 1 (1954), 61-68.

[8] 木瀬洋,「生産スケジューリング現状と動向」,『システム/制御/情報』, 41 (1997), 92-99.

[9] 木瀬洋,「道しるべジョブショップスケジューリング問題」,『情報処理』, 39 (1998), 1150-1153.

[10] N. Raman, K. Stecke and E. Rachamadugu, "Forcused Review of FMS Scheduling Research," 『計測制御』, 33 (1994), 680-689.

[11] M.L. Pinedo, Planning and Scheduling in Manufacturing and Services, Springer, 2000.


「scheduling problem」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


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

辞書ショートカット

すべての辞書の索引

「scheduling problem」の関連用語

scheduling problemのお隣キーワード
検索ランキング

   

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



scheduling problemのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS