「待ち行列モデル」の版間の差分

2009年6月30日 (火) 17:42時点における最新版

【まちぎょうれつもでる (queueing model)】

単一窓口待ち行列の挙動

概要

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

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

詳説

混雑現象

　われわれの身の回りには，混雑現象が主因となっている問題がたくさん存在する[5]．たとえば，通勤電車，繁華街，行楽地，イベント会場などにおける混雑，高速道路や幹線道路の渋滞，スーパーのレジや銀行の ATM における行列，病院での待ち，携帯電話の不接続，などなど．また，人間が待たされるわけではないが，商品の在庫，仕事の滞貨，注文残，考えようによっては洪水などというのもある．コンピュータの中では複数のジョブが CPU や I/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]．

図１：流体近似 : 水道のイメージ

待ち行列モデル

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

図２：待ち行列のイメージ図

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

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

性能評価指標，混雑指標

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

という形で定義される．たとえば客が平均 $\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．https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.41_01_035.pdf

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

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

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

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

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

@@ 1行目: / 1行目: @@
 '''【まちぎょうれつもでる (queueing model)】'''
-混雑現象を解析するための代表的なモデル群の1つ. 単一の待ち行列モデルは, 客の到着, 窓口における客のサービス, サービスを待つ客が成す待ち行列, などから構成され, 平均待ち時間などによって混雑の程度が評価される. 近年, 待ち行列がネットワーク状につながった"待ち行列ネットワーク"が積極的に解析され, コンピュータシステムや通信システムなどの性能評価に利用されている.
+[[画像:queue.gif|thumb|421px|単一窓口待ち行列の挙動]]
+== 概要 ==
+混雑現象を解析するための代表的なモデル群の1つ．単一の待ち行列モデルは，客の到着，窓口における客のサービス，サービスを待つ客が成す待ち行列，などから構成され，平均待ち時間などによって混雑の程度が評価される．近年，待ち行列がネットワーク状につながった"[[待ち行列ネットワーク]]"が積極的に解析され，コンピュータシステムや通信システムなどの性能評価に利用されている．
+　応用分野については，次の各項目を参照のこと：待ち行列の[[待ち行列の通信への応用|通信への応用]]，待ち行列の[[待ち行列のコンピュータへの応用|コンピュータへの応用]]，待ち行列の[[待ち行列の生産システムへの応用|生産システムへの応用]]．
+== 詳説 ==
+=== 混雑現象 ===
+　われわれの身の回りには，[[混雑現象]]が主因となっている問題がたくさん存在する[5]．たとえば，通勤電車，繁華街，行楽地，イベント会場などにおける混雑，高速道路や幹線道路の渋滞， スーパーのレジや銀行の ATM における行列，病院での待ち，携帯電話の不接続，などなど．また，人間が待たされるわけではないが，商品の在庫，仕事の滞貨，注文残，考えようによっては洪水などというのもある．コンピュータの中では複数のジョブが CPU や I/O (Disk など) で待ち行列を作って処理されているし，情報通信ネットワークでも，情報があちこちのノードで少しずつ待たされながら目的地に運ばれる．
+　このような混雑現象は，需要つまりサービス要求量が一時的にサービス能力を超えることから生じており，次のようにいろいろな方法で処理されている．
+a.　サービス処理能力を需要にあわせて変動させる (電力会社は，火力発電や水力発電で発電量を細かく調整している)．
+b.　サービス品質を落として処理能力を一時的に上げる (通勤電車では客が多くなると尻押しをしてでも詰め込む)．
+c.　バッファで一時的な超過分を吸収する (行列で待たせる)．
+d.　サービスを拒否する (携帯電話では当然のように行われる)．
+=== 混雑現象のためのモデル ===
+　a．の追随型とb．の品質低下型は，混雑に対する対応がリアルタイムであるため，需要の変動パターンがわかれば，混雑の程度の解析は比較的容易である．これに対してc．のバッファ型とd．の拒絶型，とくにc.　は，システムの挙動がサービスの仕方とも関連して複雑であり，モデルによる検討が必要になることが多い．そのモデルも，需要の変動パターンによって使い分けが必要である．
+　i)　サービス要求量の増大が一定時間続くラッシュアワー型の場合
+　ii)　偶然変動による比較的短時間の増大が繰り返し生じる確率型の場合
+である．むろんそれらが複合していることもある．
+=== 流体近似モデル ===
+　i) のラッシュアワー型の解析は，[[流体近似]] (fluid approximation) を使ってなされることが多い．これは水道の水のように，サービス要求がある率でバッファに入ってきて，ある率で流れ出ていく，と考えるものである (図1)．このとき，時刻 <math>t\, </math> における入力率を <math>\lambda_t\, </math>，出力率 (バッファに貯まっているときに出力する率) を <math>\mu_t\, </math> とすると，時刻 <math>t\, </math> におけるバッファの内容量 <math>Q_t\, </math> は，微分方程式
+<center>
+<table>
+<tr>
+<td><table>
+<math> \frac{\mbox{d} Q_t}{\mbox{d} t} = \Biggl\{ \Biggr. \, \, </math>
+</table></td>
+<td><table>
+  <tr>
+    <td><math> \lambda_t - \mu_t \,\, </math></td>
+    <td>　　</td>
+    <td><math> \lambda_t > \mu_t \,\, </math>または<math> Q_t>0 \,\, </math>　のとき</td>
+  </tr>
+  <tr>
+    <td><math> 0 \, \, </math></td>
+    <td></td>
+    <td align="left">その他</td>
+  </tr>
+</table></td>
+</tr>
+</table>
+</center>
+で記述される．ただしこの微分方程式を使わなくても，時間区間 <math>(0, t]\, </math> における累積入力量<math>\textstyle A_t = \int_0^\infty \lambda_t \, dt\, </math> のグラフから累積出力量 <math>D_t\, </math> のグラフを描くことができ，それらの差 <math>Q_t=A_t - D_t\, </math> から時刻 <math>t\, </math> におけるバッファーの内容量を求めることができる [2,5]．
+<center><table><tr><td align=center>[[画像:sk-0112-b-a-01-2.png]]</td></tr>
+<td align=center>図１：流体近似 : 水道のイメージ<br>
+</td></table></center>
+<!--
+\begin{figure} \setlength{\unitlength}{.6mm} \begin{center} \begin{picture}(60, 35)(0, 5) \thicklines \put(10, 39){\line(1, 0){16}} \put(26, 32){\oval(14, 14)[tr]} \put(33, 32){\line(0, -1){4}} \put(10, 34){\line(1, 0){14}} \put(24, 31){\oval(6, 6)[tr]} \put(27, 31){\line(0, -1){3}} \put(23, 39){\line(0, 1){3}} \put(21, 39){\line(0, 1){3}} \put(22, 43.5){\oval(8, 3)}
+\put(0, 15){\oval(8, 14)[tr]} \put(14, 15){\oval(20, 14)[bl]} \put(14, 5){\oval(24, 6)[tr]} \put(60, 15){\oval(8, 14)[tl]} \put(46, 15){\oval(20, 14)[br]} \put(46, 5){\oval(24, 6)[tl]}
+\thinlines \put(4, 18){\line(1, 0){52}} \multiput(27.5, 29)(1, 0){6}{\line(0, -1){5}} \multiput(26.5, 4)(1, 0){8}{\line(0, -1){4}} \end{picture} \end{center} \caption{流体近似 : 水道のイメージ} \label{B-A-01+suidou} \end{figure}
+-->
+=== 待ち行列モデル ===
+　サービス要求量の変動が ii) の確率型の場合は，[[待ち行列モデル]] (queueing model) や [[在庫モデル]] (inventory model)，[[ダムモデル]] (dam model) などを使って解析される [1，2]．ここでは待ち行列モデルを主に説明しよう．
+<center><table><tr><td align=center>[[画像:sk-0112-b-a-01-3.png]]</td></tr>
+<td align=center>図２：待ち行列のイメージ図<br>
+</td></table></center>
+<!--
+\begin{figure} \setlength{\unitlength}{1mm} \begin{center} \thicklines \begin{picture}(65, 20)(0, 7) \put(10, 15){\vector(1, 0){7.5}} \put(45, 15){\vector(1, 0){7.5}} \put(20, 12.5){\line(1, 0){15}} \put(20, 17.5){\line(1, 0){15}} \put(25, 12.5){\line(0, 1){5}} \put(30, 12.5){\line(0, 1){5}} \put(35, 12.5){\line(0, 1){5}} \put(37.5, 10){\line(0, 1){10}} \put(42.5, 10){\line(0, 1){10}} \put(37.5, 10){\line(1, 0){5}} \put(37.5, 15){\line(1, 0){5}} \put(37.5, 20){\line(1, 0){5}} \put(32.5, 15){\circle{4}} \put(40, 12.5){\circle{4}} \put(40, 17.5){\circle{4}}
+\put(0, 15){\makebox(0, 0){客の到着}} \put(25.5, 7){\makebox(0, 0){待ち行列}} \put(40, 4){\makebox(0, 0){窓口}} \put(57.5, 15){\makebox(0, 0){退去}} %\put(27.5, 23){\makebox(0, 0){待ち時間}} %\put(40, 27.5){\makebox(0, 0){サービス時間}} \end{picture} \end{center} \caption{待ち行列のイメージ図} \label{B-A-01+queue1} \end{figure}
+-->
+　待ち行列モデルは，図2のように，あるサービスステーションに[[客]](customer)が[[到着]]し， そこである種の[[サービス]] (service) をうけ，系外に立ち去る，という[[サービスシステム]] (servicing system) のモデルである．サービスステーションは，通常，サービスが行われる[[窓口]] (channel) と，到着した客がサービスを受けるために待つ[[待ち行列]] (queue) とから成る．この待ち行列が[[バッファ]] (buffer) の役割を果たす．待つことのできる客の数に制限がある場合，待合室という概念を導入することもある．このとき待合室の容量が，待つことのできる客の数の上限となる．
+　客，窓口，待合室などは，モデルによってさまざまなものに対応する．ある種の生産システムでは，客は製品や部品であり，窓口は加工機，検査機，組立台など，そして待合室は仮置き台などである．コンピュータの性能評価では，客はジョブであり，窓口は CPU や DISK，待合室は各所のメモリである．また情報通信ネットワークの性能評価では，セルやパケットといった情報の塊が客であり，各種のスイッチ類やチャネルが窓口，バッファメモリが待合室として扱われる．
+=== 性能評価指標，混雑指標 ===
+　図2のような標準的なモデルでは，[[利用率]] (traffic intensity)，<math>\rho\, </math> というのが重要なシステムパラメータである．これは
+<center>
+[[画像:sk-0112-b-a-01-1.png]]
+</center>
+<!--
+\[
+\rho = \frac{サービス要求量}{サービス処理能力}
+\]
+-->
+という形で定義される．たとえば客が平均 <math>\lambda^{-1}\, </math> の間隔で到着し，<math>c\, </math> 個の窓口で平均 <math>\mu^{-1}\, </math> のサービスが行われるようなシステムでは，<math>\rho=\lambda/c \mu\, </math> である．多くの場合，<math>\rho<1\, </math> であれば，システムは[[平衡状態]](stationary) とよばれる安定な状態へ向かい，確率論的な解析が可能となる．
+　一般に，<math>\rho\, </math> が 0に近いときは混雑はほとんどなく，1に近づくにつれて混雑がひどくなる．このような混雑を評価する指標としては，[[待ち時間]] (waiting time) (客が待ち行列で待たされる時間)，[[滞在時間]] (sojourn time) (客が到着してからサービスが終了するまでの時間)，[[待ち行列長]] (queue length) (待ち行列で待っている客の数)，[[系内人数]] (number of customers in the system) (待ち行列と窓口にいる客の数) などの平均や分散，または分布などが用いられる．
+　[[待合室の容量]] (capacity of waiting room) が有限で，システムに入れる客の数に制限がある場合，[[呼損率]] (loss probability) も重要な指標である．これは到着した客のうち待合室が一杯でサービスを受けられずに退去する客の割合である．ここで "呼 (こ，よび)" という耳慣れない言葉が使われているが，これは電話をかけるときの接続要求のことで，待ち行列理論がデンマークの電話技術者[[アーラン, アグナー・K|アーラン]](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．https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.41_01_035.pdf
+[3] 高橋敬隆，高橋幸雄，牧本直樹，「入門講座，やさしい待ち行列 (補遺) ― 待ち行列の本」，『オペレーションズ・リサーチ』，'''41''' (1996)，106-107．https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.41_02_106.pdf
+[4] 高橋幸雄，「講座，待ち行列研究の新しい潮流 (1)― 待ち行列研究の変遷」，『オペレーションズ・リサーチ』，'''43''' (1998)，495-499.
+[5] 高橋幸雄，森村英典，『混雑と待ち』，朝倉書店，2001．ISBN: 425427517X
+[6] 宮沢 政清，『待ち行列の数理とその応用』，牧野書店，2006．ISBN-13: 978-4434076978
+[7] 日本オペレーションズリサーチ学会待ち行列研究部会
+https://orsj.org/queue/
+[[category:確率と確率過程|まちぎょうれつ]]
+[[category:待ち行列|まちぎょうれつ]]