まちぎょうれつりろん
窓口やサーバに処理の要求が到着し、空くのを待って処理を受ける様子を確率のモデルで表し、待ち時間や行列の長さを求める理論。到着の分布、サービス時間の分布、窓口の数を「M/M/1」のように並べるケンドールの記号で表す。M/M/1モデルでは、利用率ρ = 到着率λ × 平均サービス時間Tsを使って、平均待ち時間を ρ/(1 − ρ) × Ts と求める。コンピュータの性能評価、ネットワークの遅延、工場の仕掛りの分析などに使われる。
「待ち行列理論」は、1分野の6問の練習問題に出てきます(確率・統計と待ち行列など)。
この用語の分野: 確率・統計と待ち行列
待ち行列のモデルは「到着の分布/サービス時間の分布/窓口の数」の形で表します。Mはマルコフ性を表し、到着ならポアソン到着(間隔が指数分布)、サービス時間なら指数分布を意味します。Dは一定の時間、Gは一般の分布です。M/M/1は、ランダムな到着とランダムなサービス時間の窓口が1つのモデルで、待つ場所に限りがなく、先着順に処理し、十分に時間がたった定常状態を考えるのが基本の前提です。
利用率は ρ = λ × Ts で、窓口が忙しい時間の割合です。M/M/1では、平均待ち時間 Wq = ρ/(1 − ρ) × Ts、平均応答時間 W = Wq + Ts = Ts/(1 − ρ)、系の中にある平均の数 L = ρ/(1 − ρ) です。これらはリトルの法則 L = λW で結び付いていて、例えば λ = 3件/分、Ts = 15秒なら、ρ = 0.75、Wq = 45秒、W = 60秒、L = 3件になります。
Wq ÷ Ts = ρ/(1 − ρ) は、利用率0.5で1倍、0.8で4倍、0.9で9倍、0.95で19倍と、利用率が1に近づくほど急に大きくなります。たまたま到着が重なってできた行列を解消するための空き時間 1 − ρ が少なくなるからです。そのため、応答時間が大切なシステムでは、利用率に余裕を持たせて設計します。
正解：A. 0.8
利用率ρは、到着率λと平均サービス時間Tsの積で、窓口が忙しい時間の割合を表します。単位をそろえると4分 = 1/15時間なので、ρ = 12 × 1/15 = 0.8 です。サービス率 μ = 15件/時間を使って、ρ = λ/μ = 12/15 と求めても同じです。
正解：C. 60秒
利用率は ρ = 3件/分 × 15秒 ÷ 60秒 = 0.75 です。平均待ち時間は Wq = ρ/(1 − ρ) × Ts = 0.75/0.25 × 15 = 45秒で、これに処理の時間15秒を足すと、平均応答時間は 45 + 15 = 60秒です。Ts/(1 − ρ) = 15/0.25 = 60秒と求めても同じです。
サービス時間が一定ならM/D/1のように、実際に近いモデルを使います。M/D/1の平均待ち時間はM/M/1のちょうど半分になり、サービス時間のばらつきが小さいほど待ち時間は短くなります。複雑なシステムでは、シミュレーションで確かめることも多く、どの場合でもリトルの法則は成り立ちます。
全体の処理能力が同じなら、2倍速い窓口1つの方が、窓口2つ(1本の行列を共有するM/M/2)より平均応答時間は短くなります。一方、行列で待つ時間だけを比べると、窓口2つの方が短くなります。窓口が2つでも、窓口ごとに別々の行列を作ると、片方が空いているのにもう片方で待つことが起こるので、1本の行列を共有する方式より待ち時間が長くなります。
待ち行列のM/M/1モデルの最初のMは、このような到着を表します。
サーバへの要求が、1分あたり平均6件のポアソン到着(互いに独立なランダムな到着)で届く。到着の間隔が従う分布と、その平…方式Aは、到着率が半分のM/M/1が2つ並んだものとみなせます。
同じ速さの窓口が2つある。方式Aでは、利用者は到着したときにどちらかの窓口を等しい確率で選び、窓口ごとの行列に並ぶ。方…Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。