スケジューリング理論（読み）スケジューリングりろん（その他表記）theory of scheduling

改訂新版　世界大百科事典

スケジューリング理論 (スケジューリングりろん)
theory of scheduling

たとえば工場において，何種類かの仕事を何台かの機械で処理する場合を考える。それぞれの仕事がいくつかの作業から成り，それらの作業の実行順序あるいは仕事の間の先行関係が与えられている時，あるいはまた仕事の処理に要する人員，機械，資金などに関する何らかの制約が与えられている時に，それらの制約条件を満たしつつ総費用または総所要時間を最小にするにはどうすればよいか，といった問題に対する解答を与えるのがスケジューリング理論である。上のような問題は特に機械スケジューリング問題とも呼ばれるが，多くのスケジューリング問題は，何らかの機械スケジューリング問題として数学的に定式化することができる。

　機械スケジューリング問題の代表的なものとしては，フローショップ問題，ジョブショップ問題，並列ショップ問題などがある。フローショップ問題では，すべての仕事が同一の作業群によって構成され，それらの機械による処理順序も同一である場合をいう。それに対してジョブショップ問題では，それぞれの仕事を構成する作業の機械による処理順序が異なる。また並列ショップ問題では，それぞれの仕事がいくつかの同一種類の機械のうちのいずれか1台によって処理される。

　スケジューリング問題におけるスケジュールの効率性を評価する尺度としては，スケジュールの総所要時間，それぞれの仕事の処理を完了するのに要する時間の総和，それぞれの仕事が納期を有する場合の納期遅れの最大値，あるいはその総和などをはじめとして多くのものが考えられる。

　スケジューリング理論の発展のきっかけとなったジョンソンの問題は，1959年に以下のような2機械フローショップ問題として与えられた。たとえば，それぞれの仕事の作業の処理時間が表のように与えられた時に，すべての仕事が機械M₁，M₂の順に作業を処理する場合の総所要時間を最小にするスケジュールを求めたい。そのためには〈処理時間の中の最小値を求め，それがM₁にあればその仕事を最初に実施し，それがM₂にあれば最後に実施する〉という規則（ジョンソンの規則と呼ばれる）にしたがって次々に仕事の順序を決定すればよい。したがって表の例の場合にはC→A→D→B→Eの順に処理すれば総所要時間が最小になる。

　スケジューリング理論の分野では，ジョンソンの問題以後も非常に数多くの問題が提起され，いろいろな評価尺度に対する最適スケジュールを得る方法が提案されている。しかし，たとえば機械の台数，仕事の数などが多い場合に，厳密な最適スケジュールを求めるにはコンピューターを用いてもかなりの計算時間を要することが多く，それゆえ効率的な解法アルゴリズムを求めることが最近のスケジューリング理論の主要な研究の対象となっている。
執筆者：大山 達雄

表

出典　株式会社平凡社「改訂新版　世界大百科事典」