スケジューリングアルゴリズム
【英】：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.
| スケジューリング： | シフティングボトルネック法 ジョブショップ ジョブショップ問題 スケジューリングアルゴリズム スケジューリングソフトウェア スケジューリング問題 スケジューリング理論 |
パケット・スケジューリング
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2023年1月） |
パケット・スケジューリング (Packet Scheduling) または単にスケジューリングとは、コンピュータネットワーク上のネットワーク機器において、パケットをそれが属するグループに応じたレートで送出することである。
概要
パケット・スケジューリングに使用されるアルゴリズムは、オペレーティング・システムなどにおけるスケジューリングと大きな違いはない。
スケジューリングの機構は、パケットをキューイングする機構とバッファ管理を行う機構とに論理的に分けることができる。スケジューリングは適切に制御することによってQoSを保証するのに役立つが、不適切なスケジューリング（キューイング）はQoSを劣化させる。ネットワーク機器の出口、特にLAN（ローカルエリア・ネットワーク）からWAN（広域ネットワーク）への接続点や、複数の入口から特定の出口に向かう点では、キューにパケットがたまりやすい。パケットがキューの中ですごす時間を制御できれば有効なQoS制御ができることになる。
スケジューリングの方法
代表的なスケジューリングの方法として優先キューイング、重み付き公平キューイング、クラスベース・キューイングがある。
- 優先キューイング (Priority Queuing, PQ)
- 最も基本的な方法であり、優先度が異なるクラスごとにキューを持ち、優先度の高いものから出力していく方法である。単純な機構であり、優先度の高いクラスのリアルタイム性が保証されるが、輻輳すると優先度の低いクラスが出力されなくなる可能性がある。クラシファイアによってクラス分けされたパケットは、優先度別にキューに入れられる。スケジューラは優先度が高いキューから順にパケットを取り出して出力していく。
- 重み付き公平キューイング (Weighted Fair Queuing, WFQ)
- フロー（たとえば特定のユーザから他の特定のユーザへのTCPセッション）ごとにキューを割り当てて、フローごとに公平なキューイングを行う方法である。他のフローの影響を一定以下におさえることができるが、フローの数だけキューが必要になる。クラシファイアはフローごとのキューにパケットをいれる。スケジューラはラウンドロビン方式であり、各キューから公平にパケットを出力する。これによって、それぞれのフローは少なくとも1周に1回は処理される機会を得る。
- クラスベース・キューイング (Class-Based Queuing, CBQ)
- フローを階層的に制御するために、クラス毎に規定した使用量に応じたトラフィック制御を行うための方法である。スケジューラの出力はクラスごとに測定され、クラスに設定された上限値を超えた場合にはキューにペナルティが与えられる。スケジューラはそのペナルティを考慮したラウンドロビン方法によって出力する。これにより、クラスごとに「出力のn%まで」というような定量的な割合が定義できるようになる。
関連項目
- scheduling algorithmのページへのリンク
