待ち行列モデルとは?

Weblio 辞書 > 学問 > OR事典 > 待ち行列モデルの意味・解説 

待ち行列モデル

読み方まちぎょうれつもでる
【英】:queueing model

目次

概要

混雑現象解析するための代表的モデル群の1つ単一の待ち行列モデルは,客の到着窓口における客のサービスサービスを待つ客が成す待ち行列,などから構成され,平均待ち時間などによって混雑程度評価される.近年待ち行列ネットワーク状につながった"待ち行列ネットワーク"が積極的に解析され,コンピュータシステム通信システムなどの性能評価利用されている.

 応用分野については,次の各項目を参照のこと:待ち行列の通信への応用待ち行列のコンピュータへの応用待ち行列の生産システムへの応用

詳説

混雑現象

 われわれの身の回りには,混雑現象主因となっている問題がたくさ存在する[5].たとえば,通勤電車繁華街行楽地イベント会場などにおける混雑高速道路幹線道路渋滞スーパーレジ銀行ATM における行列病院での待ち携帯電話の不接続などなど.また,人間が待たされるわけではないが,商品在庫仕事滞貨注文残,考えようによっては洪水などというのもある.コンピュータの中では複数ジョブCPUI/O (Disk など) で待ち行列を作って処理されているし,情報通信ネットワークでも,情報あちこちノード少しずつ待たされながら目的地に運ばれる.

 このような混雑現象は,需要つまりサービス要求量が一時的サービス能力超えることから生じており,次のようにいろいろな方法で処理されている.

a. サービス処理能力需要あわせて変動させる (電力会社は,火力発電水力発電発電量を細かく調整している).

b. サービス品質落として処理能力一時的上げる (通勤電車では客が多くなると尻押しをしてでも詰め込む).

c. バッファ一時的超過分を吸収する (行列待たせる).

d. サービス拒否する (携帯電話では当然のように行われる).

混雑現象のためのモデル

 a.の追随型とb.品質低下型は,混雑対する対応がリアルタイムであるため,需要変動パターンがわかれば,混雑程度解析比較的容易である.これに対してc.のバッファ型とd.拒絶型,とくにc. は,システム挙動サービス仕方とも関連して複雑であり,モデルによる検討が必要になることが多い.そのモデルも,需要変動パターンによって使い分けが必要である.

 i) サービス要求量の増大一定時間続くラッシュアワー型の場合

 ii) 偶然変動による比較短時間増大繰り返し生じる確率型の場合

である.むろんそれらが複合していることもある.

流体近似モデル

 i) のラッシュアワー型の解析は,流体近似 (fluid approximation) を使ってなされることが多い.これは水道水のようにサービス要求がある率でバッファに入ってきて,ある率で流れ出ていく,と考えるものである (図1).このとき,時刻 t\, における入力率\lambda_t\, 出力率 (バッファに貯まっているときに出力する率) を \mu_t\, とすると,時刻 t\, におけるバッファ内容量 Q_t\, は,微分方程式


 \frac{\mbox{d} Q_t}{\mbox{d} t} = \Biggl\{ \Biggr. \, \,

 \lambda_t - \mu_t \,\,     \lambda_t > \mu_t \,\, または Q_t>0 \,\,  のとき
 0 \, \, その他


記述される.ただしこの微分方程式を使わなくても,時間区間 (0, t]\, における累積入力\textstyle A_t = \int_0^\infty \lambda_t \, dt\, グラフから累積出力D_t\, グラフを描くことができ,それらの差 Q_t=A_t - D_t\, から時刻 t\, におけるバッファー内容量求めることができる [2,5].


Sk-0112-b-a-01-2.png
図1:流体近似 : 水道イメージ



待ち行列モデル

 サービス要求量の変動ii) の確率型の場合は,待ち行列モデル (queueing model) や 在庫モデル (inventory model),ダムモデル (dam model) などを使って解析される [1,2].ここでは待ち行列モデルを主に説明しよう.


Sk-0112-b-a-01-3.png
図2:待ち行列イメージ図


 待ち行列モデルは,図2のように,あるサービスステーションに客(customer)が到着し, そこである種サービス (service) をうけ,系外に立ち去る,というサービスシステム (servicing system) のモデルである.サービスステーションは,通常サービスが行われる窓口 (channel) と,到着した客がサービスを受けるために待つ待ち行列 (queue) とから成る.この待ち行列バッファ (buffer) の役割を果たす.待つことのできる客の数に制限がある場合待合室という概念導入することもある.このとき待合室の容量が,待つことのできる客の数の上限となる.

 客,窓口待合室などは,モデルによってさまざまなものに対応する.ある種生産システムでは,客は製品部品であり,窓口加工機,検査機,組立台など,そして待合室仮置き台などである.コンピュータ性能評価では,客はジョブであり,窓口CPUDISK待合室各所メモリである.また情報通信ネットワーク性能評価では,セルパケットといった情報の塊が客であり,各種スイッチ類やチャネル窓口バッファメモリ待合室として扱われる.

性能評価指標,混雑指標

 図2のような標準的モデルでは,利用率 (traffic intensity),\rho\, というのが重要なシステムパラメータである.これは

Sk-0112-b-a-01-1.png


という形で定義される.たとえば客が平均 \lambda^{-1}\, 間隔到着し,c\, 個の窓口平均 \mu^{-1}\, サービスが行われるようなシステムでは,\rho=\lambda/c \mu\, である.多く場合\rho<1\, であればシステム平衡状態(stationary) とよばれる安定な状態へ向かい確率論的解析が可能となる.

 一般に\rho\, が 0に近いときは混雑はほとんどなく,1に近づくにつれて混雑がひどくなる.このような混雑評価する指標としては,待ち時間 (waiting time) (客が待ち行列で待たされる時間),滞在時間 (sojourn time) (客が到着してからサービス終了するまでの時間),待ち行列長 (queue length) (待ち行列待っている客の数),系内人数 (number of customers in the system) (待ち行列窓口にいる客の数) などの平均分散,または分布などが用いられる.

 待合室の容量 (capacity of waiting room) が有限で,システムに入れる客の数に制限がある場合呼損率 (loss probability) も重要な指標である.これは到着した客のうち待合室一杯サービスを受けられずに退去する客の割合である.ここで "呼 (こ,よび)" という耳慣れない言葉が使われているが,これは電話をかけるときの接続要求のことで,待ち行列理論デンマーク電話技術者アーラン(A. K. Erlang) によって20世紀初頭始められ以来電話交換機適正数を評価するのに有限待合室モデル (finite-buffer model) がずっと使われてきたという経緯からきている [4].


読書案内

 近年待ち行列理論分野では,情報通信技術発達などと歩調合わせて,より複雑でより一般的な状況の下でのモデル解析が進められている.待ち行列理論関係の参考書は,日本オペレーションズリサーチ学会待ち行列研究部会のホームページに「待ち行列関係書籍和書)」としてまとめられている.[7] 中でも [5] は混雑現象全般にわたって解説されているので,初学者には参考になるだろう.[6] は初学者から専門研究者まで幅広い読者層想定して,待ち行列理論基本的な項目が解説されている.英語の書籍紹介は [3,4] にある.



参考文献

[1] 森村英典,大前義次,『応用待ち行列理論』,日科技連出版社,1975.ISBN 481715313X

[2] 高橋幸雄,「入門講座,やさしい待ち行列(1)~(4)」,『オペレーションズ・リサーチ』,40 (1995),649-654,716-721,41 (1996),35-40,100-105.http://www.orsj.or.jp/~archive/pdf/bul/Vol.41_01_035.pdf

[3] 高橋敬隆,高橋幸雄,牧本直,「入門講座,やさしい待ち行列 (補遺) ― 待ち行列の本」,『オペレーションズ・リサーチ』,41 (1996),106-107.http://www.orsj.or.jp/~archive/pdf/bul/Vol.41_02_106.pdf

[4] 高橋幸雄,「講座待ち行列研究新し潮流 (1)― 待ち行列研究変遷」,『オペレーションズ・リサーチ』,43 (1998),495-499.

[5] 高橋幸雄森村英典,『混雑待ち』,朝倉書店2001ISBN: 425427517X

[6] 宮沢 政清,『待ち行列数理とその応用』,牧野書店2006ISBN-13: 978-4434076978

[7] 日本オペレーションズリサーチ学会待ち行列研究部http://www.orsj.or.jp/queue/


待ち行列理論

(待ち行列モデル から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/03/23 16:57 UTC 版)

待ち行列理論(まちぎょうれつりろん 英語: Queueing Theory)とは、顧客がサービスを受けるために行列に並ぶような確率的に挙動するシステムの混雑現象を数理モデルを用いて解析することを目的とした理論である。応用数学オペレーションズ・リサーチにおける分野の一つに数えられる。






「待ち行列理論」の続きの解説一覧




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

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「待ち行列モデル」の関連用語

待ち行列モデルのお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング

画像から探す

中里麗美

ビロードキンクロ

822SH

土系舗装

アカテンイロウミウシ

スタンダードデッカー

アックス

重ね石





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

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2017 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの待ち行列理論 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2017 Weblio RSS