待ち行列ネットワークとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > 待ち行列ネットワークの意味・解説 

待ち行列ネットワーク

読み方まちぎょうれつねっとわーく
【英】:queueing network

概要

複数待ち行列システムが,直列リング状あるいはネットワーク状に組み合わされ数学モデル情報ネットワークコンピュータシステムFMSflexible manufacturing system)を始めとする生産システム交通システムなどの複合システムにおける「待ち現象確率的振る舞い取り扱う.待ち時間待ち行列長スループットなどの性能評価量を算出するのに用いられる

詳説

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


図1:待ち行列ネットワーク
図1:待ち行列ネットワーク


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

Sk-0123-b-b-01-1.png
図2:直列型待ち行列


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



図3:循環型待ち行列

図3:循環型待ち行列


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


Sk-0123-b-b-01-2.png
図4:セントラルサーバモデル


 また単一待ち行列モデルで客の母集団有限である場合も, 閉鎖型ネットワーク一例と見ることも可能である.  さらに客が優先権,待ち行列ネットワーク内の移動経路などの属性により複数クラス分類され一部クラス属する客に関して開放型で,他のクラス の客に関して閉鎖型ネットワーク混合型待ち行列ネットワークと呼ぶ.  待ち行列ネットワークの別の分類として,各ノード許容される待ち行列長に関する制限有無依るものがある.制限が無い場合には適当なモデル化の仮 定を設ければ積形式解用いた実用的な計算が可能であるが,制限がある場合には,ブロッキング発生しノード間のより一層複雑な従属性が生じ有効な解析法は存在しないこのような場合には近似的なアプローチを取らざるを得ないブロッキングとは,次に訪問するノード待合室一杯のときに移動妨げられることを言う.この結果モデルによっては元のサーバ次の客へのサービス行なえない.客がいるにも拘わらずサービス開始されない.これは例えば多段工程からなる生産ラインにおける,各工程における仕掛品置き場のように大容量バッファがないシステム相当する一方通信網においてはブロッキング発生すると客であるパケット・メッセージなどは消滅する.  待ち行列ネットワークは,従来単一待ち行列システムモデル化されていた生産通信・コンピュータ輸送交通システムネットワーク化に伴い,その 重要性増しており,特に積形式解を持つモデル数値計算支援するソフトウェア・パッケージなども提供されている.




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「待ち行列ネットワーク」の関連用語

待ち行列ネットワークのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



待ち行列ネットワークのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2024 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2024 GRAS Group, Inc.RSS