待ち行列理論の応用

【まちぎょうれつりろんのおうよう (applications of queueing theory)】

通信への応用

　望ましい情報通信ネットワークを構築するには, 方式, 構成, 品質, コスト等の関係を定量的に評価分析する必要がある. 需要(トラヒック)と供給(設備数, 処理能力等)の関係により, ユーザの感じる通信品質に満足/不満足が生じる. 特に需要は時間的, 空間的に確率的に変動するものであり, 待ち行列理論が必須である. 電話の出現とともに上記の評価分析が開始され, さらに情報通信の発展が待ち行列理論の研究を促進した.

はじめに

　1878年の電話機の発明からほどなくして, 電話交換の設備数に関して通信トラヒック面からの検討が始められた. その後, デンマークの電話会社の技師　アーラン(A. K. Erlang)により体系的に研究された. これが待ち行列理論の始まりといわれる. このように待ち行列理論は情報通信ネットワークの進展・革新とともに発展してきた [1]. 通信網において接続される単位, すなわち電話網における通話やパケット網におけるパケット等はトラヒックとよばれる. トラヒックの発生や継続時間は確率的に変動しており, 通信網においてそれを運ぶための回線, 交換機あるいはコンピュータなどの設備を, 大多数の利用者が満足できるサービス品質のもとでシステム設計するための理論を通信トラヒック理論という. 待ち行列理論の通信への応用とはすなわち通信トラヒック理論そのものである [2] [3].

電話交換, 電話網, ディジタル網への応用

　1965年頃から交換機の制御系が蓄積プログラム制御となり, 処理能力評価あるいは処理能力を向上させる方式の考案が大きな課題であった. リアルタイム性の要求される交換機に特有の周期処理スケジュール方式に関して, 優先クラスごとの平均遅延時間の近似式が求められた [4]. ISDN (サービス総合ディジタル網) では, 性質の異なるトラヒックが同一の設備に加わる. このトラヒックを多元トラヒックとよび, マルチメディア通信網においてはさらに各所に出現する. 多元トラヒックの処理方法には即時式/待時式, 優先権待ち行列 (回線留保を含む) 等がある. パケット網や計算機は随所にバッファを設置しており, 待時式処理が基本となる. これらを評価・分析するモデルとして待ち行列ネットワークが有効である.

パケット網, データ網への応用

　パケット網については, 1970年頃に, 米国でインターネットのルーツであるARPA網が活発に研究・開発された. ルーチング方式やウィンドウ制御, ACKの返送方式に関して, 遅延時間や処理量の観点から多くの研究がなされた. データ通信やLANに関するトラヒック研究も活発に展開された [5].

　CSMA/CD方式に対する平衡状態を仮定した理論解析, ポーリング方式に関するモデル解析およびLANの性能評価への応用, ALOHAシステムの解析等がなされた.

ATM方式への応用

　マルチメディア通信に対する通信方式として, 1980年代初め, ATM (AsynchronousTransfer Mode)方式が考案された. ATM方式では, 情報がセルという固定長の情報単位に分割されて, 網内を流れる. セルが待ち行列理論の客そのものであり, ATM方式の検討には待ち行列理論が必須である [6]. 当初, セルのヘッダによるハードウェアルーチングが注目され, バッファの設置形式を含めて通話路網が多数研究された. ビデオ情報のセルストリームはバースト的であるということで, トラヒックの入力モデルが活発に研究された. さらに, LANの長時間のトラヒックストリームが統計的に分析され, 長時間依存性, 自己相似性が指摘されている [7]. ATM方式のサービスカテゴリーとして, CBR (Constant Bit Rate), VBR (VariableBit Rate)等が提案されその標準化がなされた. 並行して, セルの統計的多重効果に関する実に多くの研究がなされ, トラヒック制御として, コネクション受付制御や使用量パラメータ制御が活発に研究された [8].

移動通信網への応用

　1980年代初頭に自動車電話サービスが開始され, 1993年にディジタル方式が提供され始め, 1990年代後半急速に普及している. 移動通信方式では, 有限の無線周波数をいかに有効活用するかが最も重要であり, トラヒック理論が非常に有効な分野である. 電波強度の関係と周波数を繰り返して使用するため, 地域を比較的小さなゾーンに分けている. そこで無線チャネルの割り当て法の研究が必要となる. また, ユーザの移動のため, 位置登録信号, 通話中チャネル切り替え, 一斉呼び出し等の信号が使用される. これら運ぶ制御チャネルの動作分析に関してもトラヒック理論が使える [9].

インターネットへの応用

　爆発的に成長しているインターネットは待時式処理が基本であり, その評価・分析には待ち行列理論が利用できる. たとえば, WWWで画像データを取込むと大きなデータが動く. これはテキスト情報の情報量と比較すると数桁以上も大きい. WWWの発生間隔や情報量の統計的分析をベースに, 待ち行列理論を利用して応答時間等が評価できる.

---

参考文献

[1] 高橋幸雄, 「待ち行列研究の変遷」, 『オペレーションズ・リサーチ』, 43 (1998), 495-502.

[2] 秋丸春夫, 川島幸之助, 『情報通信トラヒック』, 電気通信協会, 1990.

[3] 村田正幸, 宮原秀夫, 「通信トラヒック理論とその応用[I]～[VII]」, 『電子情報通信学会誌』, 77 (1994), 968-975, 1043-1051, 1249-1255, 78 (1995). 85-90, 195-202, 264-270, 482-488.

[4] 藤木正也, 「トラヒック理論の応用　5. 交換機制御系への応用」, 『電子通信学会誌』, 64 (1981), 50-58.

[5] 秋山稔, 川島幸之助, 木村丈治, 『LANのシステム設計』, オーム社, 1989.

[6] 川島幸之助, 町原文明, 高橋敬隆, 斎藤洋, 『通信トラヒック理論の基礎とマルチメディア通信網』, 電子情報通信学会, 1995.

[7] 小沢利久, 「いろいろな入力過程モデル」, 『オペレーションズ・リサーチ』, 43 (1998), 680-686.

[8] 滝根哲哉, 村田正幸, 「通信網における待ち行列　－理論の応用と課題－」, 『オペレーションズ・リサーチ』, 43 (1998), 264-271.

[9] Davide Grillo, Ronald A. Skoog, Stanley Chia and Kin K. Leung, "Teletraffic Engineering for Mobile Personal Communications in ITU-T Work: The Need to Match Practice and Theory," IEEE Personal Communications Magazine, 5 (1998), 38-58.

コンピュータシステムへの応用

複雑で大規模なコンピュータシステムでは, 性質の異なる様々な処理要求が非同期に発生するため, システムの内部は資源競合が発生し混雑している. この混雑現象のモデル化と解析を行うことによりコンピュータシステムの性能を評価し, 過不足のない最適なシステム設計, 性能トラブルを起こさないシステム開発など的確に推進するために, 待ち行列理論や待ち行列ネットワークモデルが活用されている.

セントラルサーバモデル

　大規模なコンピュータシステムでは, 多数の利用者から性質の異なる様々な処理が非同期に要求されるため, その内部では CPU を始めとする種々のシステム資源の競合が発生する. すなわち, コンピュータの内部は混雑しているのである. この混雑現象を解析し, その結果をシステムの設計開発の利用するため, 待ち行列理論, とりわけ待ち行列ネットワークモデルがよく利用される. 閉鎖型ジャクソンネットワークを利用したセントラルサーバモデルとその計算アルゴリズム [7]が最も簡単な待ち行列ネットワークモデルとして知られている.

BCMPネットワーク

　BCMPネットワークは, 複数の異なる網内移動経路 (経路選択確率行列) をもつ客が混在することが許されるため, それぞれの網内移動経路を性格の異なるサブシステムに対応付けることにより, 複雑で大規模なコンピュータシステムの性能評価モデルを柔軟に構成することができる. 待ち行列ネットワークを実用化するに際しては, 正規化定数の効率的な計算方法の開発, 積形式解をもたないようなモデルに関する近似解法の開発, 利用者に分かりやすく使いやすいインターフェィスをもつソフトウエアパッケージの開発等が欠かせないが, 1975年は BCMP ネットワークに関する積形式解 [1] が発表されるとともに, その正規化定数の計算法の提案 [9], ならびにそのアルゴリズムを実装したソフトウエアパッケージの開発が行われた. それを契機に, BCMP ネットワークに関する研究と応用は大きな進展をみせた. とりわけ, 開放型ネットワークと閉鎖型ネットワークが混在する混合型待ち行列ネットワークは現在広く実用に供されている.

待ち行列ネットワークの計算法

　積形式解をもつ待ち行列ネットワークを利用する際には, ネットワーク状態分布の正規化定数といわれる定数を計算することが必要になる. この正規化定数は, 確率条件から定められるものであるが, ネットワークを構成するノード数, 網内移動経路数 (部分連鎖数) , 閉鎖型連鎖にしたがう客数等が大きくなるにしたがい, その計算量は組み合わせ的な速さで増大する. そのため, 待ち行列ネットワークに関する効率的な計算法の開発は実用化のためには欠かせない. この計算法は, 大きく分けると, たたみ込み法の系統に属するものと, MVA (Mean Value Analysis) 法 [10]の系統に属するものに分けることができる. たたみ込み法では, 正規化定数をたたみ込み演算を利用して直接求める. MVA 法では, ネットワークの積形式解から連鎖と客数をパラメータとする漸化式をつくり, これを手がかりにして計算を行う. たたみ込み法では, 指数部のあふれ, MVA 法では仮数部の桁落ち, という数値計算上の不安定要因をもっているため, それを避ける計算法についての研究も多数なされている. 実際に待ち行列ネットワークを利用する際には, これらの計算アルゴリズムを実装したソフトウエアパッケージが必要になる. コンピュータシステムへの応用を目的とした開発も QM-X [7] をはじめ多数行われている.

性能測定技術

　待ち行列ネットワークを利用してコンピュータシステムの性能評価を行う際には, 評価の基礎となるデータをどのようにして得るのか, という問題が重要となる. 質の良いデータを効率的に測定するための技術も色々と開発されている. また, 待ち行列ネットワークを効果的に利用するための方法論と測定法の提案もなされている. これらについては, 解説 [5, 6] に示される. また, 待ち行列ネットワークとそのコンピュータシステムの性能評価への応用については, [3, 4, 7, 9] に詳しい.

---

参考文献

[1] F. Baskett, K. M. Chandy, R. R. Muntz and F. G. Palacios, "Open, Closed, and Mixed Networks of Queues with Different Classes of Customers," Journal of Association of Computing Machinery, 22 (1975), 248-260.

[2] J. P. Buzen, "Computatonal Algorithm for Closed Queueing Networks with Exponential Servers," Communication of Association for Computing Machinery, 16 (1973), 527-531.

[3] 亀田壽夫, 紀 一誠, 李 頡, 『性能評価の基礎と応用』, 共立出版, 1998.

[4] K. Kant, Introduction to Computer Performance Evaluation, McGraw-Hill, Inc., 1992.

[5] 紀 一誠, 「情報処理システムの性能評価(1)(2)(3)」, 『オペレーションズ・リサーチ』, 40 (1995), 315-320, 370--375, 431-436.

[6] 紀 一誠, 「コンピュータシステム」, 『オペレーションズ・リサーチ』, 43 (1998), 562-567.

[7] 紀 一誠, 『待ち行列ネットワーク』,朝倉書店 , 2002.

[8] 紀 一誠, 納富研造, 「待ち行列網モデルによる計算機システムの性能評価用ソフトウエアパッケージ QM-X」, 『情報処理学会論文誌』, 25 (1984), 570-578.

[9] S. S. Lavenvarg (Ed. ), Computer Performance Handbook, Academic Press, 1983.

[10] M. Reiser and H. Kobasyashi, "Queueing Networks with Multiple Closed Chains: Theory and Computational Algorithms," IBM Research and Development, 19 (1975), 283-249.

[11] M. Reiser and S. S. Lavenverg, "Mean Value Analysis of Closed Multichain Queueing Networks," Journal of Association for Computing Machinery, 22 (1980), 313-333.

生産システムへの応用

生産システムは, 原材料や部品をより付加価値の高い半製品, 製品へと加工, 組立てを行なうシステムであり, 単一工程から多工程直列生産ライン, トランスファライン, FMS (flexible manufacturing system), JIT生産システム等々広範な生産システムが含まれる. これら生産システムにたいして, 生産リードタイム, スループット等の性能評価を始め, 単調性, 可逆性等の構造的性質が待ち行列理論等を駆使して導かれている.

一定加工時間モデル

　生産システムは, 原材料や部品をより付加価値の高い半製品, 製品へと加工, 組立てを行なうシステムであり, ネットワーク状につながった生産工程から構成される. まず基本的なものとして, 図1に示される$N\,$工程が直列につながった生産ラインを考える. 製品の需要(原材料と生産指示)は任意の確率過程に従って到着し, 原材料をもとに工程1から$N\,$へと到着順に加工をうけ, 製品となる. 各工程$n\,$ $(=1,\ldots ,N)\,$は1台の機械からなり, その加工時間は一定時間$s_{n}\,$ $(\geq 0)\,$ である. 工程1の前には無限の容量を持つバッファがあり, 工程$n\,$ $(\geq 2)\,$ の前には有限(0でもよい)容量のバッファがあるものとする. 需要が到着してから製品として完成するまでの時間を生産リードタイム, 単位時間あたりに生産可能な最大数をスループット(throughput) あるいは生産率と呼んでいる.

図１：直列生産ライン

　このとき, 需要の任意の到着過程に対して, 生産リードタイムおよびスループットは, 工程の順序にもバッファ容量にも依存しないことが示される. そして, 最大の加工時間を持つ最上流の工程を$L\,$とすれば, スループットは$1/s_{L}\,$で与えられる. また, 遅れの分布は客がその到着過程に従い, 一定時間$s_{L}\,$のサービス時間をもつ窓口1つの待ち行列モデルの待ち時間分布で与えられる. したがって, 需要が到着率$\lambda \,$のポアソン過程に従って到着する場合, 待ち行列モデル M/D/1 の結果から, 図1の生産ラインの平均生産リードタイム$PL\,$は,

$PL=\sum _{n=1}^{N}s_{n}+{\frac {\rho _{L}^{2}}{2\lambda (1-\rho _{L})}}\,$

となる. ここで$\rho _{L}=\lambda s_{L}<1\,$である. これらの結果は, 各工程が複数の機械をもつ場合にも一般化されている [1].

確率的に変動する加工時間モデル

　機械には故障も起これば, 工具の折損, 摩耗も発生し, 必ずしも加工時間は一定ではない. また, 生産ラインも多品種を混流生産することが多く, 加工時間も生産される製品毎に異なってくる. したがって, 加工時間は確率的に変動し, 何らかの確率分布をもつものと考えられる. これらの確率分布が指数分布であるときの直列生産ラインに対する結果や文献等が [2] に紹介されている. さらに, FMS (Flexible Manufacturing System) やネットワークを含む広範な生産システムに対する包括的な結果が[2] - [4]に論じられている.

かんばん方式, JIT

　JIT (Just in Time) 生産システムは, 1973年のオイル・ショック時にトヨタ生産方式として登場して以来, この30余年の間に JIT production system あるいはkanban systemとして全世界に定着した. 特に1980年代以後, 製造業の復権をめざす米国を中心に待ち行列理論を駆使した理論的研究が精力的に行われてきた.

　Mitra and Mitrani [5, 6] は, 生産指示かんばんによって生産が制御され, 引き取りは生産指示かんばんポストにかんばんがある限り直ちに行われるものとした, $N\,$工程からなる生産指示かんばんモデルを考察している. 生産指示かんばんは, 直列生産ラインにおけるバッファに比べてより柔軟であり, 生産リードタイムを短縮し, スループットを向上させることが示されている. さらに, 需要がポアソン過程に従って到着し, 各加工時間が指数分布に従うときの近似解法を導き, シミュレーションと比較してその精度を検証している.

　Tayur [7] は, $N\,$工程からなる生産指示かんばんモデルにおいて, より一般的に各工程が充分なバッファをとって直列に配置された複数の機械からなる生産ラインを考え, 種々の構造的特性を導いている. また, スループットが最大になるように, 与えられた枚数のかんばんを各工程に配分する問題を考え, スループットの代わりに, 加工時間分布が指数分布に従う場合のマルコフ待ち行列の状態数を最大化することを提案し, そのアルゴリズムを与えて, 大多数の数値例で実際にスループットを最大化することを示している. さらに, [8] では工程1への原材料の確率的な到着, 工程$N\,$からの需要の確率的な引き取りおよび各工程での機械故障, 部品の再加工, 部品の廃棄がある場合を論じ, ほぼ同様な結果が成り立つことを示している.

　Buzacott and Shanthikumar [3] 第4章は, 原材料倉庫をもち, 需要の確率的な引き取りがある単一工程生産指示かんばんモデルを考え, 通常の待ち行列モデルと等価であることを示している. さらに, $N\,$工程直列生産システムに対して, 調達タグ (tag), 発注タグ, 加工タグ, 生産指示かんばんを用いる PAC (Production Authorization Cards) システムを提案し, MRP, かんばん方式, OPT等を含むことやその性質を示し, 近似的な性能評価を与えている [3] . また, Glasserman and Yao [9] 第5章も生産指示かんばん方式の一般化である$(a,b,k)\,$モデルを提案し, 一般化セミマルコフ過程を用いて様々な構造的性質を導いており, Altiok [4] 第7章も生産指示かんばん方式を論じている.

　JIT生産システムを特徴づける1つが多能工とU字型生産ラインである. 多能工数を調整することで, 需要変動に柔軟に対応でき, 現今の需要の多様化と製品寿命の短命化に適合した数少ない生産ラインである. U字型生産ラインを含めたJIT生産システムに対する結果や文献等が [10] - [11] に紹介されている.

---

参考文献

[1] B. Avi-Itzhak and H. Levy, "A Sequence of Servers with Arbitrary Input and Regular Service Times Revisited," Management Science, 41 (1965), 1039-1047.

[2] 大野勝久, 「生産システムをめぐって」, 『Basic数学』, 25 (1992), 61-67.

[3] J. A. Buzacott and J. G. Shanthikumar, Stochastic Models of Manufacturing Systems, Prentice Hall, 1993.

[4] T. Altiok, Performance Analysis of Manufacturing Systems, Springer-Verlag, 1997.

[5] D. Mitra and I. Mitrani, "Analysis of a Kanban Discipline for Cell Coordination in Production Lines. I," Management Science, 36 (1990), 1548-1566.

[6] D. Mitra and I. Mitrani, "Analysis of a Kanban Discipline for Cell Coordination in Production Lines. II," Operations Research, 39 (1991), 807-823.

[7] S. R. Tayur, "Structural Properties and a Heuristic for Kanban-Controlled Serial Lines," Management Science, 39 (1993), 1347-1368.

[8] J. A. Muckstadt and S. R. Tayur, "A Comparison of Alternative Kanban Control Mechanisms. I," IIE Transactions, 27 (1995), 140-150.

[9] P. Glasserman and D. D. Yao, Monotone Structure in Discrete-Event Systems, John Wiley & Sons, 1994.

[10] 大野勝久, 「JIT生産システム」, 『オペレーションズ・リサーチ』, 43 (1998), 272-278.

[11] K. Nakade and K. Ohno, "An Optimal Worker Allocation Problem for a U-shaped Production Line," International Journal of Production Economics, 60-61 (1999), 353-358.