スケジューリング理論
【英】：scheduling theory
概要
スケジューリングとは時間軸上で活動に資源を割り当てることである. その成果物がスケジュールである. スケジューリング理論は, 広義にはスケジューリング問題のモデル化, 分析, 解法の開発・分析, スケジューリングシステム, 実際問題への応用などの分野を含むが, 狭義には順序づけ(sequencing)理論ないしジョブショップスケジューリング(job shop scheduling)と同義である. 代表的な応用分野としてジョブショップとコンピュータシステムが挙げられる.
詳説
スケジュールとは, 時間軸上で設備(ないし資源)に1つ以上の活動を割り当てたものをいう. スケジューリングとは, スケジュールを決めることであって, スケジューリング理論 (scheduling theory) は, 広義にはスケジューリング問題のモデル化, 分析, 解法の開発・分析, スケジューリングシステム, 実際問題への応用などの分野にまたがる理論である. 1つの設備には同時に1つの活動だけを割り当てることができ, 1つの活動は同時に1つの設備にのみ割り当てることができるとするとき, 1つ以上の設備から成るシステムをジョブショップ (job shop) という. 各設備に割り当てる活動を作業 (operation) と呼び, いくつかの作業の集合をジョブ (job) と呼ぶ. ジョブショップの設備は一般に機械 (machine) と呼ばれ, 機械はその種類によって工程 (process) に分けられる. ジョブショップは機能別配置 [1] の機械加工工場のモデルと考えられるが, 機械を様々な生産資源に置き換えることによって広い応用分野に対応する. 各工程が1つの機械から成るのが基本的なジョブショップである. あるジョブを構成する作業の間に技術的観点から指定された順序を技術的順序 (technological order) という. 技術的順序に従って各作業を工程に割り付けたときに得る工程の順序を工程順序（routing）という．各機械において処理する作業の順序をその機械におけるジョブの (あるいは同じことであるが作業の) 処理順序 (sequence) と呼ぶ.
 |
図１：ガントチャート |
ジョブショップにおいて1つのスケジュールが与えられるとき, 横軸に時間をとり縦軸に機械をとって, 各機械ごとに作業を処理する期間を帯状に表示したものを機械向き (machine oriented) ガントチャート (Gantt chart), 縦軸にはジョブを取りその作業の処理期間を帯状に表示したものをジョブ向き (job oriented) ガントチャートという (図1). スケジュールは本来, 各作業の着手と完了の時刻の集合である. しかし, 各機械が同時には1つの作業しか処理できないことから, 着手順に作業を整列すれば1つの順列を得る. これは処理順序に対応する. 従って, 処理順序が決まれば各作業の着手時刻が自動的に決定されるような状況では, スケジュールと処理順序は実質的に同じ意味である. このためスケジューリング理論は狭義には順序づけ理論(sequencing theory)の意味で使われる. 以下, この狭義のスケジューリング理論の基礎概念を説明する. 関連項目としてスケジューリング問題, スケジューリング・アルゴリズムを参照されたい.
順序付け (sequencing) の研究においては処理順序の評価基準を関数表現したものを順序付け関数 (sequencing function) という。理論的には評価基準として各作業の完了時刻に関して非減少な尺度がよく利用される. このような尺度を正則尺度 (regular measure) と呼ぶ。実用的には正則でない尺度も多用される。正則尺度の下では処理順序ごとに, 各作業を工程順序に違反しないでできるだけ早期に着手するただ1つのスケジュールが検討対象となる. すべてのスケジュールに対して、任意の作業をそれより遅くなることなく完了するスケジュールが少なくとも1つは含まれているようなスケジュールの集合を, スケジュールの優越集合 (dominant set) と呼ぶ. 正則尺度の下で優越集合はすべての処理順序から上記のように「各作業にできるだけ早期に着手する」ものとして生成されるスケジュールの集合であり, その中の最良のスケジュール(処理順序)が最適である. 次のような活性スケジュール (active shedule) 全体の集合が優越集合であることは知られているが, 最小の優越集合はまだ知られていない.
1つの処理順序が与えられるとする. この時, この処理順序に従いできるだけ早期に各作業を処理開始するスケジュールを準活性スケジュールと呼ぶ. 準活性スケジュールにおいて, 他のどの作業の処理開始時刻にも影響を与えないで他の作業を飛び越してより早く着手できる作業を順次前に移動することによって, 他の作業の着手を遅らせるのでなければもはやどの作業も前に移動できないスケジュールが生成される. これが活性スケジュールである. 活性スケジュールを系統的に生成するアルゴリズム [3] は知られているが, 一般に活性スケジュールは極めて多数存在するので, これを完全列挙することによって最適処理順序を決定するのは実際上困難である.
ジョブの処理順序に関する制約を先行関係 (precedence relation) 制約という. 多くの先行関係は2項関係を用いて記述できるが, 特定のジョブを処理順序の先頭にしてはいけない, などのように, 2項関係では表現できないものもある. 着手可能時刻 (release time) あるいは最早着手可能時刻はジョブの最初の作業の処理を開始できる最早時刻をいう. 順序づけするすべてのジョブの着手可能時刻が既知の状況を静的 (static), そうでない場合を動的順序づけという. 各ジョブに納期が指定される場合もある. 各作業の処理に要する時間を処理時間 (processing time) という. 各作業にはこの他, 段取り時間 (setup time), 後始末時間 (removal time), 前後の作業の間の完了と着手の最小（あるいは最大）の時間間隔である遅れ時間 (delay time) などが指定されることがある.
 |
| 図２：離接グラフ(機械3, ジョブ3) |
ジョブやその作業に様々な条件が付加されることがあるが, ジョブショップにおける順序づけの基本は, 工程順序, 先行関係と整合するような処理順序の中から順序づけ関数を最適化するものを決定することである. これを表示するのに図2のような離接グラフ (disjunctive graph) が利用される. この図の両方向の矢線の各々に対して一方向を選択しアサイクリックな接続グラフ (conjunctive graph) を作成すると, 実行可能な処理順序が得られる. 順序づけとは様々な付加的条件の下で, 離接グラフから最適な接続グラフを構成することである, ということもできる. 処理順序 (接続グラフ) を生成する効率的な手続きを順序付け規則 (sequencing rule) と呼び, それが所与の順序づけ関数に関して最適な接続グラフを生成するとき, 最適であるという. 順序づけ規則やスケジューリング・アルゴリズムを構成する際に, 合成ジョブ (composite job) と呼ばれる架空のジョブを導入することがある。
[1] 秋庭雅夫編, 『生産管理』, 日本規格協会, 1980.
[2] K. R. Baker, Introduction to Sequencing and Scheduling, Wiley, New York, 1974.
[3] B. Giffler and G. L. Thompson, "Algorithms for Solving Production Scheduling Problems," Operations Research, 8 (1960), 487-503.
| スケジューリング： | スケジューリングアルゴリズム スケジューリングソフトウェア スケジューリング問題 スケジューリング理論 ディスパッチング規則 フローショップ問題 リストスケジューリング |
- スケジューリング理論のページへのリンク
