《待ち行列ネットワーク》

【まちぎょうれつねっとわーく (queueing network) 】

　複数の待ち行列システム(以下ノードと表記)が, 図1のようにネットワーク上に結合された数学モデルを待ち行列ネットワーク (queueing network あるいは network of queues) と呼ぶ.

図１：待ち行列ネットワーク

　各ノード間の移動は通常確率的に選択される. 例えばノード $i$ から $j$ は確率 $r_{ij}$ で移動する. 経路選択確率 (routing probability) あるいは分岐確率 (branching probability) と呼ぶ. 特にネットワーク外を表現するのにノード0と記す．このモデルの確率的な振る舞いを解析し, 待ち時間・待ち行列長・スループットなどに関する性能評価量を算出が可能となる. 特に図2のように直列につながったモデルを直列型待ち行列(queueing networkあるいはnetwork of queues)と呼ぶ．

図２：直列型待ち行列

　これらのモデルにおいては，あるノードからの退去過程は他のノードへの到着過程になることからノード間の従属性が生じる．さらにはネットワークにフィー ドバック・ループがある場合には，退去した客が再度到着する可能性もあり，到着客間にも従属性が生じる．これらのことから個別のノードを取り出し，解 析するのは不可能であり，ネットワーク全体を捉えた解析が必要である．これまでに解析的にはマルコフ性を保持しながら，積形式解が得られる範囲内で，現実のシステムにより近いモデルが次々と発表されて来た．

　待ち行列ネットワークは，外部との関わり方で開放型ネットワーク(open network)と閉鎖型ネットワーク(closed network)に分類が可能である．開放型ネットワークにおいてはネットワーク外からの客の到着があり，またネッ トワーク外への退去もある．従ってネットワーク内の総客数は可変であり，一定ではない．これは例えば蓄積交換型のパケット交換網においては，パケット 送信要求の発生が客のネットワークへの流入に相当し，各交換機およびそれに付随するバッファが各ノードに対応する．従って目的局に受信されることが， ネットワークからの退去に当たる．一方閉鎖型ネットワークにおいてはネットワーク外からの客の到着，外への退去はない．従って総客数が常に一定に保た れる．これは例えば一定台数の機械から構成されるシステムにおいて機械の故障・修理を考慮した性能評価を行なう際に用いられる．あるいはマルチプログ ラミング環境下で動作する計算機システムのように，内部にCPU，I/O機器などのサーバおよびそれに付随した待ち行列があり，総客数は一定に保たれている 場合に相当する．計算が完了したジョブ／トランザクションはネットワークから消滅するが，それと同時にネットワーク外のバッファに貯えられていたジョ ブ・トランザクションが投入され，結果として総数が変わらないような場合にも適用が可能であり，計算機アーキテクチュアなどの評価に用いられた．閉鎖 型ネットワークで，機械修理問題に見られるように，稼動状態，修理待ち状態，検査待ち状態のそれぞれに対応するノードを順番に訪問し，客の流れが同一方 向で，訪問する待ち行列の順番が一定な直列型待ち行列を特に循環型待ち行列(図3参照)と呼ぶ．

図３：循環型待ち行列

　また図4に示すように, 計算機システムをモデル化した閉鎖型ネットワークで, 中央に位置するサーバ (CPU に相当) と複数の他のサーバ (入出力機器などの周辺機器に相当) およびそれに付随する待ち行列からなり, 客がこれらの間を交互に行き来するモデルをセントラルサーバモデルと呼ぶ.

図４：セントラルサーバモデル

　また単一待ち行列モデルで客の母集団が有限である場合も, 閉鎖型ネットワークの一例と見ることも可能である.

　さらに客が優先権，待ち行列ネットワーク内の移動経路などの属性により複数クラスに分類され，一部のクラスに属する客に関しては開放型で，他のクラス の客に関しては閉鎖型のネットワークを\yougolink{B-B-01}{混合型ネットワーク}{混合型ネットワーク}と呼ぶ．

　待ち行列ネットワークの別の分類として，各ノードで許容される待ち行列長に関する制限の有無に依るものがある．制限が無い場合には適当なモデル化の仮 定を設ければ積形式解を用いた実用的な計算が可能であるが，制限がある場合には，ブロッキングが発生し，ノード間のより一層複雑な従属性が生じ，有効な解析法は存在しない．このような場合には近似的なアプローチを取らざるを得ない．ブロッキングとは，次に訪問するノードの待合室が一杯のときに移動が妨げられることを言う．この結果，モデルによっては元のサーバが次の客へのサービスを行なえない．客がいるにも拘わら ずサービスが開始されない．これは例えば多段工程からなる生産ラインにおける，各工程における仕掛品置き場のように大容量のバッファがないシステムに 相当する．一方通信網においては，ブロッキングが発生すると客であるパケット・メッセージなどは消滅する．

　待ち行列ネットワークは，従来単一待ち行列システムでモデル化されていた生産・通信・コンピュータ・輸送・交通システムのネットワーク化に伴い，その 重要性が増しており，特に積形式解を持つモデルの数値計算を支援するソフトウェア・パッケージなども提供されている．

%\begin{thebibliography}{99} %\bibitem{M12+MATSUI2} % A. V. Aho, J. E. Hopcraft and J. D. Ullman, % and の前に「,」は入れない % {\it The Design and Analysis of Computer Algorithms}, % Addison-Wesley, 1974. % 本の題は斜体 %-------------------------- 英語単行本の章 ------------------------------ %\bibitem{M12+MATSUI3} % R. K. Ahuja, T. L. Magnanti and J. B. Orlin, % % ``Network Flows, % 章名は 「``題目,」 % in {\it Optimization}, % 「in」を入れる % G. L. Nemhauser, A. H. G. Rinooy Kan and M. J. Todd, eds., % North-Holland, 1989. % 編者は「 eds.,」とする %-------------------------- 英語予稿集(予稿集名) ------------------------ %\bibitem{M12+MATSUI4} % D. S. Johnson, % ``Fast Allocation Algorithms, % in {\it Proceedings of the Thirteenth Annual Symposium on Switching and Automata Theory}, % 144--154, 1972. %--------------------------- 英語予稿集(会議名) -------------------------- %\bibitem{M12+MATSUI5} % M. X. Goemans and D. P. Williamson, % 会議名は省略形も可 % ``.878-Approximation Algorithms for MAX CUT and MAX2SAT, % {\it STOC}, Canada, 422--431, 1984. % 場所は国名程度 %--------------------------- 翻訳アリ ------------------------------------ %\bibitem{M12+MATSUI6} % E. W. Cheney, % ``Introduction to Approximation Theory, % McGraw-Hill, 1966. % 最後はピリオド % 一松信, 新島耕一 訳, % 『近似理論入門』, % 共立出版, 1977. %------------------------- 翻訳本 --------------------------------------- %\bibitem{M12+MATSUI7} % 国沢清典監訳, % 『確率論とその応用II』, % 紀ノ国屋書店, 1970. %-------------------------- 日本語文献(和名雑誌)----------------------- %\bibitem{M12+MATSUI8} % 伊理正夫, 久保田光一, % % 「高速自動微分法(I)(II)」, % 論文は「…」 % 『応用数理』, % 雑誌は『…』 % {\bf 1} (1991), 17--35, 153--163. %-------------------------- 日本語文献(欧名雑誌)----------------------- %\bibitem{M12+MATSUI9} % 大沢義明, 鈴木敦夫, % 「グループ利用施設の最適配置とその頑健性について」, % {\it Journal of the Operations Research Society of Japan}, % {\bf 30} (1987), 368--395. %--------------------------- 日本語単行本(欧名交じり)------------------- %\bibitem{M12+MATSUI10} % D. Avis, 今井浩, 松永信介, % 『計算幾何学・離散幾何学』, % 朝倉書店, 1994. %--------------------------- 日本語単行本(監修と編集)------------------- %\bibitem{M12+MATSUI11} % 伊理正夫監修, 腰塚武志編集, % 『計算幾何学と地理情報処理(第２版)』, % 共立出版株式会社, 1993. %--------------------------- 日本語予稿集(予稿集名) ----------------------- %\bibitem{M12+MATSUI12} % 鈴木敦夫, 伊理正夫, % 「駅の位置決め問題--利用者の費用最小」, % 『日本オペレーションズ・リサーチ学会1986年春季研究発表会アブストラクト集』, % 210--146, 1986. %--------------------------- 日本語予稿集(会議名) ------------------------- %\bibitem{M12+MATSUI13} % 鈴木敦夫, % 「地理的最適化問題」, % 日本オペレーションズ・リサーチ学会第13回シンポジウム, % 25--28, 1984. %---------------------------------------------------------------------------

%\end{thebibliography}

\end{document}