Queue Theory

解决问题

对于某个服务大厅，已知（1）单位时间内会来的客人数（2）服务客人需要的平均时间

• 下一个客人什么时候来？（=t时间内来客人的概率为？）
• t时间后，队伍会排多长？

流程

• 客人到达
• 排队
• 窗口服务
• 离开

初始化

两个重要初始化概念：1. 客人到达时间的概率分布 2. 服务时长的概率分布
这两个定下来后排队所需时间和客人离开时间就固定下来了

• M/M/1：到达时间和服务时长满足泊松分布，且只有一个服务窗口
• M/D/1：到达时间满足泊松分布，服务时长满足固定分布，且只有一个服务窗口

泊松分布（负指数分布）

性质

• 无记忆性（马尔科夫模型）

泊松分布就是描述某段时间内，事件具体的发生概率。

• P：概率
• N： 某种函数关系，
• t：时间
• n：数量，1小时内出生3个婴儿的概率，就表示为 P(N(1) = 3) 。
• λ：表示事件的平均频率（如已知一小时内平均畜生5个婴儿则λ=5）

模拟

% M/M/1 シミュレーション
% イベント駆動型

%シミュレーションの時間
T = 100000;

%客数
N = 10000;

% 客の構造体の定義と初期化
s.arrivalTime_ = -1;
s.departureTime_ = -1;

% repmatは配列のコピーをするコマンド
% repmat(s, N, 1) により，sの値を持つＮ×1行列ができる
% 存储客人的到达时间和离开时间S(N*2)
S = repmat(s, N, 1);

% 乱数
[rndArrival, rndDeparture] = RandStream.create('mrg32k3a','NumStreams', 2, 'seed',seed);

% 最初の到着時刻
numArrivals = 0;
curTime = expRandom(rndArrival, lambda);

nextEvent = 'arrival';
nextArrivalTime = T;
nextDepartureTime = T;

numDepartures = 0;
queueLength = 0;



%出力用
queueTrace = zeros(N, 2);
qnum = 0;
numEvent = 0;

while(curTime < T && numArrivals <= N)
    
    numEvent = numEvent + 1;
    if(strcmp(nextEvent, 'arrival'))
        %到着時のキュー長の累積値を増やす
        qnum = qnum + queueLength;
        %到着した客数の累積値を一つ増やす
        numArrivals = numArrivals + 1;
        %客の到着時刻を構造体に記録
        S(numArrivals, 1).arrivalTime_ = curTime;
        
        %空のキューに到着した客ならば出発時刻を決める
        if(queueLength == 0)
        	% 如果需要M/D/1模型就把这个expRandom()改成加常数
            nextDepartureTime = curTime + expRandom(rndDeparture, mu);
        end
        %キュー長を1つ増加
        queueLength = queueLength + 1;
        %次の到着時刻を決める
        nextArrivalTime = curTime + expRandom(rndArrival, lambda);
        
    elseif(strcmp(nextEvent, 'departure'))
        
        %出発した客数の累積値を増加
        numDepartures = numDepartures + 1;
        %出発時刻を構造体に記録
        S(numDepartures, 1).departureTime_ = curTime;
        %キュー長を一つ減らす
        queueLength = queueLength - 1;
        
        %キュー長が正ならば次の出発時刻を決める
        if(queueLength > 0)
            nextDepartureTime = curTime + expRandom(rndDeparture, mu);
            
        else
            %キュー長が0ならばシミュレーション終了時刻を出発時刻とする
            nextDepartureTime = T;
        end
        
    else
    end
    
    queueTrace(numEvent, 1) = curTime;
    queueTrace(numEvent, 2) = queueLength;
    
    if(nextArrivalTime <= nextDepartureTime)
        nextEvent = 'arrival';
        curTime = nextArrivalTime;
    else
        nextEvent = 'departure';
        curTime = nextDepartureTime;
    end
    
    
    
end


sumQueue = 0;
for i = 1: numEvent - 1
    sumQueue = sumQueue + (queueTrace(i + 1, 1) - queueTrace(i, 1)) * queueTrace(i, 2);
    
end

totalTime = queueTrace(numEvent, 1) - queueTrace(1, 1);
timeAvgQueue = sumQueue/totalTime;
avgQueue = qnum/numArrivals;

delays = zeros(numDepartures,1);
for i = 1: numDepartures
    delays(i, 1) = S(i).departureTime_ - S(i).arrivalTime_;
end

关于平均值的t检定

• 两个样本的母分散不同时的t检定