待ち行列（簡単な例）

<?php

/******************************/
/* 簡単な待ち行列問題（M/M/s）*/
/*      coded by Y.Suganuma   */
/******************************/

/************************/
/* クラスCustomerの定義 */
/************************/
class Customer
{
	public $time;   // 到着時刻
	public $state;   // 客の状態
                     //   =-1 : 待ち行列に入っている
                     //   >=0 : サービスを受けている窓口番号
	/*********************/
	/* コンストラクタ    */
	/*      s : 状態     */
	/*      t : 到着時刻 */
	/*******************************/
	function Customer($s, $t)
	{
		$this->time  = $t;
		$this->state = $s;
	}
}

/**********************/
/* クラスQ_baseの定義 */
/**********************/
class Q_base {
	private $s;   // 窓口の数
	private $asb;   // 全窓口の空き状況
                    //    =0 : すべての窓口がふさがっている
                    //    =n : ｎ個の窓口が空いている
	private $sb;   // 各窓口の空き状況
                   //    =0 : 窓口は空いている
                   //    >0 : サービスを受けている客番号
	private $asb_t;   // すべての窓口がふさがった時刻
	private $c_asb;   // すべての窓口がふさがっている時間の累計
	private $c_sb;   // 各窓口がふさがっている時間の累計
	private $st_e;   // 各窓口のサービス終了時刻
	private $st_s;   // 各窓口がふさがった時刻
	private $m_lq;   // 最大待ち行列長
	private $c_lq_t;   // 待ち行列長にその長さが継続した時間を乗じた値の累計
	private $c_wt;   // 待ち時間の累計
	private $lq_t;   // 現在の待ち行列長になった時刻
	private $m_wt;   // 最大待ち時間
	private $c_sc_t;   // 系内客数にその数が継続した時間を乗じた値の累計
	private $c_sys;   // 滞在時間の累計
	private $m_sys;   // 最大滞在時間
	private $sc_t;   // 現在の系内客数になった時刻
	private $m_sc;   // 最大系内客数
	private $m_a;   // 到着時間間隔の平均値
	private $m_s;   // サービス時間の平均値
	private $at;   // 次の客の到着時刻（負の時は，終了）
	private $p_time;   // 現在時刻
	private $end;   // シミュレーション終了時刻
	private $nc;   // 到着客数カウンタ
	private $cus;   // 系内にいる客のリスト
	private $que;   // 待ち行列

	/*****************************************/
	/* コンストラクタ                        */
    /*      s_i : 窓口の数                   */
    /*      m_a_i : 到着時間間隔の平均値     */
	/*      m_s_i : サービス時間の平均値     */
    /*      end_i : シミュレーション終了時刻 */
    /*****************************************/
	function Q_base ($s_i, $m_a_i, $m_s_i, $end_i)
	{
	/*
	          設定
	*/
		$this->s   = $s_i;
		$this->m_a = $m_a_i;
		$this->m_s = $m_s_i;
		$this->end = $end_i;
	/*
	          領域の確保
	*/
		$this->sb   = array();
		$this->c_sb = array();
		$this->st_e = array();
		$this->st_s = array();
		$this->cus  = array();
		$this->que  = array();
	
		for ($i1 = 0; $i1 < $this->s; $i1++) {
			$this->sb[$i1]   = 0;
			$this->c_sb[$i1] = 0.0;
		}
	/*
	          初期設定
	*/
		$this->p_time = 0.0;
    	$this->nc     = 0;
    	$this->asb    = $this->s;
		$this->m_lq   = 0;
    	$this->m_sc   = 0;
    	$this->c_asb  = 0.0;
		$this->c_wt   = 0.0;
		$this->m_wt   = 0.0;
		$this->c_lq_t = 0.0;
		$this->lq_t   = 0.0;
		$this->m_sys  = 0.0;
		$this->c_sys  = 0.0;
		$this->c_sc_t = 0.0;
		$this->sc_t   = 0.0;
	/*
	          乱数の初期設定
	*/
		mt_srand();
	/*
	          最初の客の到着時刻の設定
	*/
		$this->at = $this->p_time + $this->Next_at();
	}
	
	/********************************/
	/* 次の客の到着までの時間の発生 */
	/********************************/
	function Next_at()
	{
		return -$this->m_a * log(mt_rand() / mt_getrandmax());
	}
    
    /************************/
	/* サービス時間の発生   */
    /************************/
    function Next_sv()
	{
		return -$this->m_s * log(mt_rand() / mt_getrandmax());
	}
	
	/**************/
	/* 全体の制御 */
	/**************/
	function Control()
	{
		$sw = 0;
		while ($sw > -2) {
			$sw = $this->Next();   // 次の処理の選択
			if ($sw == -1)
				$sw = $this->End_o_s();   // シミュレーションの終了
			else {
				if ($sw == 0)
					$this->Arrive();   // 客の到着処理
				else
					$this->Service($sw);   // サービスの終了
			}
		}
	}
	
	/**************************************************/
	/* 次の処理の決定                                 */
    /*      return : =-1 : シミュレーションの終了     */
    /*               =0  : 客の到着処理               */
	/*               =i  : ｉ番目の窓口のサービス終了 */
    /**************************************************/
    function Next()
	{
		$sw = -1;
		$t  = $this->end;   // シミュレーション終了時刻で初期設定
						// 次の客の到着時刻
		if ($this->at >= 0.0 && $this->at < $t) {
			$sw = 0;
			$t  = $this->at;
		}
						// サービス終了時刻
		for ($i1 = 0; $i1 < $this->s; $i1++) {
			if ($this->sb[$i1] > 0 && $this->st_e[$i1] <= $t) {
				$sw = $i1 + 1;
				$t  = $this->st_e[$i1];   // 窓口i1のサービス終了時刻
			}
		}
	
		return $sw;
	}
	
	/**********************************/
	/* 終了処理                       */
	/*      return : =-1 : 終了前処理 */
	/*               =-2 : 実際の終了 */
	/**********************************/
	function End_o_s()
    {
    	$sw           = -2;
		$this->p_time = $this->end;   // 現在時刻
    	$this->at     = -1.0;   // 次の客の到着時刻
    
		for ($i1 = 0; $i1 < $this->s; $i1++) {
			if ($this->sb[$i1] > 0) {   // サービス中の客はいるか？
				if ($sw == -2) {
					$sw  = -1;
					$this->end = $this->st_e[$i1];   // 窓口i1のサービス終了時刻
				}
				else {
					if ($this->st_e[$i1] > $this->end)
						$this->end = $this->st_e[$i1];   // 窓口i1のサービス終了時刻
				}
			}
		}
	
		return $sw;
	}
	
	/****************/
	/* 客の到着処理 */
	/****************/
	function Arrive()
	{
	/*
	          客数の増加と次の客の到着時刻の設定
	*/
		$this->nc     += 1;   // 到着客数カウンタ
    	$this->p_time  = $this->at;   // 現在時刻
    	$this->at      = $this->p_time + $this->Next_at();      // 次の客の到着時刻
		if ($this->at >= $this->end)
    		$this->at = -1.0;
    /*
	          系内客数の処理
	*/
		$this->c_sc_t += (count($this->cus) * ($this->p_time - $this->sc_t));   // 系内客数にその数が継続した時間を乗じた値の累計
		$this->sc_t    = $this->p_time;   // 現在の系内客数になった時刻
		if (count($this->cus)+1 > $this->m_sc)
			$this->m_sc = count($this->cus) + 1;   // 最大系内客数
	/*
	          窓口に空きがない場合
	*/
		if ($this->asb == 0) {
			$ct_p = new Customer(-1, $this->p_time);
			$this->cus['no'.strval($this->nc)] = $ct_p;   // 客の登録（系内客数）
			$this->c_lq_t += count($this->que) * ($this->p_time - $this->lq_t);   // 待ち行列長にその長さが継続した時間を乗じた値の累計
			array_push($this->que, $this->nc);   // 客の登録（待ち行列）
			$this->lq_t = $this->p_time;   // 現在の待ち行列長になった時刻
			if (count($this->que) > $this->m_lq)
				$this->m_lq = count($this->que);   // 最大待ち行列長
		}
	/*
	          すぐサービスを受けられる場合
	*/
		else {
			$k = -1;
			for ($i1 = 0; $i1 < $this->s && $k < 0; $i1++) {
				if ($this->sb[$i1] == 0) {
    				$ct_p = new Customer($i1, $this->p_time);
    				$this->cus['no'.strval($this->nc)] = $ct_p;   // 客の登録（系内客数）
					$k              = $i1;
    				$this->sb[$k]   = $this->nc;   // サービスを受けている客番号
    				$this->st_e[$k] = $this->p_time + $this->Next_sv();   // 窓口kのサービス終了時刻
					$this->asb     -= 1;   // 空いている窓口数
				}
			}
			$this->st_s[$k] = $this->p_time;   // 窓口kがふさがった時刻
			if ($this->asb == 0)
				$this->asb_t = $this->p_time;   // すべての窓口がふさがった時刻
		}
	}
	
	/*********************************/
	/* サービス終了時の処理          */
	/*      k : サービス終了窓口番号 */
	/*********************************/
	function Service($k)
	{
	/*
	          時間の設定
	*/
		$k             -= 1;
		$this->p_time   = $this->st_e[$k];   // 現在時刻
		$this->st_e[$k] = -1.0;   // サービス終了時間
	/*
	          系内客数の処理
	*/
		$this->c_sc_t += (count($this->cus) * ($this->p_time - $this->sc_t));   // 系内客数にその数が継続した時間を乗じた値の累計
    	$this->sc_t    = $this->p_time;   // 現在の系内客数になった時刻
    /*
	          滞在時間の処理
    */
    	$it = $this->cus['no'.strval($this->sb[$k])];
		$x1 = $this->p_time - $it->time;
		$this->c_sys += $x1;   // 滞在時間の累計
		if ($x1 > $this->m_sys)
			$this->m_sys = $x1;   // 最大滞在時間
		unset($this->cus['no'.strval($this->sb[$k])]);   // 客の削除（系内客数）
	/*
	          窓口使用時間の処理
	*/
		$this->asb      += 1;   // 空いている窓口数
		$this->sb[$k]    = 0;   // 窓口kを空き状態にする
		$this->c_sb[$k] += ($this->p_time - $this->st_s[$k]);   // 窓口kがふさがっている時間の累計
	/*
	          待ち行列がある場合
	*/
		if (count($this->que) > 0) {
			$this->asb    -= 1;   // 開いている窓口数
			$this->c_lq_t += count($this->que) * ($this->p_time - $this->lq_t);   // 待ち行列長にその長さが継続した時間を乗じた値の累計
			$n = array_shift($this->que);   // 客の削除（待ち行列）
			$this->lq_t  = $this->p_time;   // 現在の待ち行列長になった時刻
			$it          = $this->cus['no'.strval($n)];
			$x1          = $this->p_time - $it->time;
			$this->c_wt += $x1;   // 待ち時間の累計
			if ($x1 > $this->m_wt)
				$this->m_wt = $x1;   // 最大待ち時間
    		$k = -1;
    		for ($i1 = 0; $i1 < $this->s && $k < 0; $i1++) {
				if ($this->sb[$i1] == 0) {
    				$k              = $i1;
    				$this->sb[$k]   = $n;   // 窓口kの客番号
					$this->st_e[$k] = $this->p_time + $this->Next_sv();   // 窓口kのサービス終了時刻
					$this->st_s[$k] = $this->p_time;   // 窓口kがふさがった時刻
					$it->state      = $k;   // 客の状態変更
				}
			}
		}
	/*
	          待ち行列がない場合
	*/
		else {
			if ($this->asb == 1)
				$this->c_asb += ($this->p_time - $this->asb_t);   // すべての窓口がふさがっている時間の累計
		}
	}
	
	/************************/
	/* 結果の出力           */
	/* （カッコ内は理論値） */
	/************************/
	function Output()
	{
		$rn  = floatval($this->nc);
		$rs  = floatval($this->s);
		$ram = 1.0 / $this->m_a;
		$myu = 1.0 / $this->m_s;
    	$rou = $ram / ($rs * $myu);
		if ($this->s == 1) {
    		$p0 = 1.0 - $rou;
    		$pi = $rou;
		}
		else {
			$p0 = 1.0 / (1.0 + 2.0 * $rou + 4.0 * $rou * $rou / (2.0 * (1.0 - $rou)));
			$pi = 4.0 * $rou * $rou * $p0 / (2.0 * (1.0 - $rou));
		}
		$Lq = $pi * $rou / (1.0 - $rou);
		$L  = $Lq + $rs * $rou;
		$Wq = $Lq / $ram;
		$W  = $Wq + 1.0 / $myu;
		printf("シミュレーション終了時間＝%.3f 客数＝%d ρ＝%.3f ｐ0＝%.3f\n",
	           $this->p_time, $this->nc, $rou, $p0);
		printf("   すべての窓口が塞がっている割合＝%.3f (%.3f)\n",
	           $this->c_asb/$this->p_time, $pi);
		printf("   各窓口が塞がっている割合\n");
		for ($i1 = 0; $i1 < $this->s; $i1++)
			printf("      %d   %.3f\n", $i1+1, $this->c_sb[$i1]/$this->p_time);
		printf("   平均待ち行列長＝%.3f (%.3f)  最大待ち行列長＝%d\n",
	           $this->c_lq_t/$this->p_time, $Lq, $this->m_lq);
		printf("   平均系内客数  ＝%.3f (%.3f)  最大系内客数  ＝%d\n",
	           $this->c_sc_t/$this->p_time, $L, $this->m_sc);
		printf("   平均待ち時間  ＝%.3f (%.3f)  最大待ち時間  ＝%.3f\n",
	           $this->c_wt/$rn, $Wq, $this->m_wt);
		printf("   平均滞在時間  ＝%.3f (%.3f)  最大滞在時間  ＝%.3f\n",
	           $this->c_sys/$rn, $W, $this->m_sys);
	}
}
    
/****************/
/* main program */
/****************/
/*
          入力データ
*/
	printf("窓口の数は？ ");
	fscanf(STDIN, "%d", $s);

	printf("シミュレーション終了時間？ ");
	fscanf(STDIN, "%lf", $end);

	printf("   到着時間間隔の平均値は？ ");
	fscanf(STDIN, "%lf", $m_a);

	printf("   サービス時間の平均値は？ ");
	fscanf(STDIN, "%lf", $m_s);
/*
          システムの定義
*/
	$base = new Q_base($s, $m_a, $m_s, $end);
/*
          シミュレーションの実行
*/
	$base->Control();
/*
         出力
*/
	$base->Output();

?>