セージ の メモ書き

メモこそ命の恩人だ

C# - 待ち行列理論

待ち行列理論

待ち行列理論 - Wikipedia

  • "混み具合" から "待ち行列" を算出できる理論。
  • 混み具合 = 入ってくる割合 / 出ていく割合
    • 入ってくる割合:1時間あたり、何人がやってくるか。
    • 出ていく割合:1時間あたり、何人をさばけるか。
      • 入ってくる割合:6人/時間
      • 出ていく割合:7.5人/時間
      • 6 / 7.5 = 0.8
  • 待ち行列 = p / (1 - p) 、 p : 混み具合
    • 例:混み具合 p=0.8 の場合
      => 0.8 / (1 - 0.8) = 4(人)
    • つまり上記の混み具合なら、4人は待っている。
  • 待ち時間 = 待ち行列 × サービス時間
    • 例:待ち行列=4人、サービス時間=7.5人/時間
      => 4 / 7.5 = 0.53(時間) = 32(分)
var queuing = new QueuingTheory().GetQueue(6, 7.5);
Debug.WriteLine(queuing);
// 4.000000000000001

var queuingTime = new QueuingTheory().GetQueueTime(6, 7.5);
Debug.WriteLine(queuingTime);
// 0.5333333333333334

internal class QueuingTheory
{
    public double GetQueueTime(double input, double output) => GetQueue(input, output) / output;
    public double GetQueue(double input, double output) 
    {
        var congestion = input / output;
        return congestion / (1 - congestion);
    }
}


ケンドール記号

ケンドールの記号 - Wikipedia

A/B/C
  • 待ち行列の特徴を表す3要因。
    • A:到着分布(入力)
    • B:サービス時間分布(出力)
    • C:窓口数(サービスを処理する数)
  • 使用する記号(AとBの箇所)
    • M(Markovian):ポアソン分布(Aの場合)、指数分布(Bの場合)
    • D(Deterministic):一様分布
    • G(General):一般分布
  • 記号の例
    • M/M/1

M/M/1 待ち行列

M/M/1 待ち行列 - Wikipedia

  • 最も基礎的な待ち行列モデル。
  • 到着分布:ポアソン分布
  • サービス時間分布:指数分布
  • 窓口数:1
  • 問題例:待ち時間はT、サービス時間もT、なら混み具合は?
    • T = p / ( 1 - p) × T
    • T - Tp = Tp
    • 2Tp = T
    • 2p = 1
    • p = 0.5

以上