スケジューリングアルゴリズム

【すけじゅーりんぐあるごりずむ (scheduling algorithm)】

概要

仕事を機械や人に割り当て, 処理する順序を決めたスケジュールを作成するための手続きである. 与えられた指標をできるだけ良くするものが良い. 所与の指標に対して最適なスケジュールを求めるもの, 仕事の特性に着目して経験的に良好な解を与えるスケジュールを作成する発見的方法, 最適とは限らないができるだけ良い解を求めるメタヒューリスティクスと呼ばれる一連の方法等がある.

詳説

　スケジューリングアルゴリズム (scheduling algorithm) はスケジューリング問題 (中項目スケジューリング問題参照) を解く, すなわちスケジュールを作成するための方法・手続きであり, 問題の特性により様々なものが提案されている [1]-[6]. アルゴリズムは所与の評価値に対して最適なスケジュールを求める最適化法と最適とは限らないができる だけ良いスケジュールを求める方法に大別できる.

　最適解を求める解析的方法には簡単な一機械総滞留時間最小化問題における処理時間順 (SPT) 規則の適用や, 2機械フローショップ問題に対するジョンソン (J.H.Johnson) の方法, その拡張である2機械ジョブショップ問題に対するジャクソン(J.R.Jackson)の方法などがある [1, 4]. より複雑な問題に対しては整数計画アプローチ (integer programming approach) [2], 分枝限定法 (branch and bound method) [1, 6, 7] などがあるが, 問題の規模が大きくなると最適解を求めることが困難になり, 良い解で満足せざるを得なくなることが多い. 分枝限定法は分枝操作における分枝先の探索法や, 限定操作等のために利用する上 (下) 界値の推定値の精度によって求解効率は大きく影響される. このため問題に応じた探索方法, 推定法の考案など個別的対応が必要である. 早い時点で得られた暫定解の最適性の証明に (長い) 計算時間のほとんどを費やすことが多く, 許容可能な時間で探索を打ち切り, その時点での暫定解を実行解とすることも考えられる.

　様々なディスパッチング規則 (dispatching rule) [4, 8] を単独あるいは組み合わせて適用する方法はスケジューリングに広く用いられている. さらに, 直感的経験的なディスパッチング規則に加えて, 部分的に最適化を図るなどして, できるだけ最適解に近いスケジュールを探索する方法がいろいろ提案されている．例えば, ラグランジュ分解調整法 [17], リストスケジューリング (list scheduling) [3, 5], 分割アルゴリズム (decomposition algorithm) [9], ジョブショップスケジューリング問題に対するシフティングボトルネック法　(shifting bottleneck procedure) [10] 等がある. これらは発見的方法あるいはヒューリスティクス(heuristics)と呼ばれている [5].

　また, 熟練したスケジューリング担当者の専門的な知識を利用する人工知能 (artificial intelligence) を用いたスケジューリング・エキスパートシステム (expert system) の開発も活発に行われ, 実用に供されている [4, 11]. スケジューリング知識の獲得や更新の難しさもあり, その効率化を目指した知識獲得法や事例ベースの構築に関する研究などが進められている [11, 16]. 最近は計算機性能の向上とともにメタヒューリスティクス (meta-heuristics) と呼ばれる方法の研究が活発である [12]. これはスケジューリングに限らず幅広い組合せ最適化問題の解法として発展したものであり, シミュレーテッドアニーリング(simulated annealing), タブー探索 (tabusearch), 遺伝アルゴリズム (genetic algorithm), ニューラルネットワーク (neural network) などがある.

　近似アルゴリズム (approximation algorithm) とは広義には, 上述のような必ずしも最適解を与えるとは限らないアルゴリズム全般を指すが、アルゴリズムの理論的研究においては、解の精度が解析的に求められているものだけを特に指すことがある [3]. 　実務面ではこれらのアルゴリズムを組み込んだ生産スケジューリングソフトウェア (scheduling software) が多数開発されており, 実用に供されている [4, 14, 15]. また, スケジュール作成作業や修正を支援する対話型スケジューリングソフトウェアも実務的な効率化の一つの方向である. シミュレーション (simulation) はスケジュールの評価だけでなくスケジュールの作成にも広く用いられており, バックワード／フォワード・ハイブリッドシミュレーション法など様々な方法が提案されている [4, 13, 15].

---

参考文献

[1] コーンウエイ他著, 関根智明訳,『スケジューリングの理論』, 日刊工業新聞社, 1971.

[2] 鍋島一郎,『スケジューリング理論』, 森北出版, 1974.

[3] P.Chretienne, E.G.Coffman, Jr., J.K.Lenstra and Z.Liu, Eds.,Scheduling Theory and its Applications, John Wiley and Sons, 1995.

[4] 田中克己, 石井信明,『スケジューリングとシミュレーション』, 計測自動制御学会, 1995.

[5] J.Blazewicz, K.Ecker, E.Pesch, G.Schmidt and J.Weglarz, Scheduling in Computer and Manufacturing Processes, Springer, 1996.

[6] P. Brucker, Scheduling Algorithms, Second revised and Enlarged Edition, Springer, 1998.

[7] 茨木俊秀,『組み合わせ最適化 : 分枝限定法を中心として』, 産業図書、1983.

[8] T.E. Morton and D.W. Pentico, Heuristic Scheduling Systems, John Wiley & Sons, Inc., 1993.

[9] C.N.Potts and L.N. van Wassenhove, "Dynamic Programming and Decomposition Approaches for the Single Machine Total Tardiness Problem," European Journal of Operational Research, 32 (1987), 405-414.

[10] J.Adams, E. Balas and D. Zawack, "The Shifting Bottlerneck Procedure for Job Shop Scheduling," Management Science, 34 (1988), 391-401.

[11] 特集：生産スケジューリング, 『計測と制御』, 33 (1994), 531-599.

[12] ミニ特集：組合せ最適化とスケジューリング問題への新接近, 『計測と制御』, 34 (1995), 339-375.

[13] 冬木正彦, 井上一郎, 「バックワード/フォワード・ハイブリッドシミュレーション法に基づく個別受注生産における納期重視型生産スケジューリング」,『日本経営工学会誌』, 46 (1995), 144-151.

[14] 安田一彦, 「生産スケジューリングソフトウェアの現状」, 『生産スケジューリング・シンポジウム'95講演論文集』, 31-36, 1995.

[15] 中野一夫,「スケジューリングにおけるシミュレーション技術とソフトウェア」,『システム/制御/情報』, 41 (1997), 106-111.

[16] 諏訪晴彦, 森田浩, 藤井進,「帰納的学習法によるスケジューリング・ルールの自動獲得とルールに基づく近傍探索スケジューリング-ジョブショップ総所要時間最小化問題への適用-」,『システム制御情報学会論文誌』, 12 (1999), 152-160.

[17] 特集　スケジューリングの革新的アルゴリズム‐ラグランジュ分解調整法‐, 『オペレーションズ・リサーチ』, 45, (2000), 256-286.