スケジューリング問題

【すけじゅーりんぐもんだい (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 \,$による問題表規の例である.

表 1: 3つ組み記法によるジョブショップ問題の分類

項目 表示 意味 $\alpha \,$ $1\,$ 1機械 $P\,$ 同一並列機械 $Q\,$ 一様並列機械 $R\,$ 無関連並列機械 $F\,$ フローショップ $O\,$ オープンショップ $J\,$ ジョブショップ

項目 表示 意味 $\beta \,$ $prec\,$ 先行制約 $r_{j}\,$ 準備時間制約 $\gamma \,$ $C_{max}\,$ 最大完了時間 $\Sigma c_{j}\,$ 滞留時間和 $T_{max}\,$ 最大納期遅れ $\Sigma T_{j}\,$ 納期遅れ和

　ジョブショップ問題の理論的研究の起源は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 Cells：Recent 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.