/******************************/
/* 簡単な待ち行列問題（M/M/s）*/
/* coded by Y.Suganuma */
/******************************/
import java.io.*;
import java.util.*;
public class Test
{
/****************/
/* main program */
/****************/
public static void main(String args[]) throws IOException
{
int s;
double end, m_a, m_s;
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
/*
入力データ
*/
System.out.print("窓口の数は？ ");
s = Integer.parseInt(in.readLine());
System.out.print("シミュレーション終了時間？ ");
end = Double.parseDouble(in.readLine());
System.out.print(" 到着時間間隔の平均値は？ ");
m_a = Double.parseDouble(in.readLine());
System.out.print(" サービス時間の平均値は？ ");
m_s = Double.parseDouble(in.readLine());
/*
システムの定義
*/
Q_base base = new Q_base(s, m_a, m_s, end);
/*
シミュレーションの実行
*/
base.Control();
/*
出力
*/
base.Output();
}
}
/**********************/
/* クラスQ_baseの定義 */
/**********************/
class Q_base {
private int s; // 窓口の数
private int asb; // 全窓口の空き状況
// =0 : すべての窓口がふさがっている
// =n : ｎ個の窓口が空いている
private int [] sb; // 各窓口の空き状況
// =0 : 窓口は空いている
// >0 : サービスを受けている客番号
private double asb_t; // すべての窓口がふさがった時間
private double c_asb; // すべての窓口がふさがっている時間の累計
private double [] c_sb; // 各窓口がふさがっている時間の累計
private double [] st_e; // 各窓口のサービス終了時間
private double [] st_s; // 各窓口がふさがった時間
private int m_lq; // 最大待ち行列長
private double c_lq_t; // 待ち行列長にその長さが継続した時間を乗じた値の累計
private double c_wt; // 待ち時間の累計
private double lq_t; // 現在の待ち行列長になった時間
private double m_wt; // 最大待ち時間
private int sc; // 現在の系内客数
private double c_sc_t; // 系内客数にその数が継続した時間を乗じた値の累計
private double c_sys; // 滞在時間の累計
private double m_sys; // 最大滞在時間
private double sc_t; // 現在の系内客数になった時間
private int m_sc; // 最大系内客数
private double m_a; // 到着時間間隔の平均値
private double m_s; // サービス時間の平均値
private double at; // 次の客の到着時間（負の時は，終了）
private double p_time; // 現在時間
private double end; // シミュレーション終了時間
private int nc; // 到着客数カウンタ
private Random rn; // 乱数
private TreeMap <Integer, Customer> cus; // 系内にいる客のリスト
private ArrayDeque <Integer> que; // 待ち行列
/*****************************************/
/* コンストラクタ */
/* s_i : 窓口の数 */
/* m_a_i : 到着時間間隔の平均値 */
/* m_s_i : サービス時間の平均値 */
/* end_i : シミュレーション終了時間 */
/*****************************************/
Q_base (int s_i, double m_a_i, double m_s_i, double end_i)
{
/*
設定
*/
s = s_i;
m_a = m_a_i;
m_s = m_s_i;
end = end_i;
/*
領域の確保
*/
sb = new int [s];
c_sb = new double [s];
st_e = new double [s];
st_s = new double [s];
for (int i1 = 0; i1 < s; i1++) {
sb[i1] = 0;
c_sb[i1] = 0.0;
}
cus = new TreeMap <Integer, Customer> ();
que = new ArrayDeque <Integer> ();
/*
初期設定
*/
p_time = 0.0;
nc = 0;
asb = s;
m_lq = 0;
m_sc = 0;
c_asb = 0.0;
c_wt = 0.0;
m_wt = 0.0;
c_lq_t = 0.0;
lq_t = 0.0;
m_sys = 0.0;
c_sys = 0.0;
c_sc_t = 0.0;
sc_t = 0.0;
/*
乱数の初期設定
*/
rn = new Random();
/*
最初の客の到着時間の設定
*/
at = p_time + Next_at();
}
/**********************************/
/* 次の客の到着までの時間の発生 */
/**********************************/
double Next_at()
{
return -m_a * Math.log(rn.nextDouble());
}
/************************/
/* サービス時間の発生 */
/************************/
double Next_sv()
{
return -m_s * Math.log(rn.nextDouble());
}
/**************/
/* 全体の制御 */
/**************/
void Control()
{
int sw = 0;
while (sw > -2) {
sw = Next(); // 次の処理の選択
if (sw == -1)
sw = End_o_s(); // シミュレーションの終了
else {
if (sw == 0)
Arrive(); // 客の到着処理
else
Service(sw); // サービスの終了
}
}
}
/**************************************************/
/* 次の処理の決定 */
/* return : =-1 : シミュレーションの終了 */
/* =0 : 客の到着処理 */
/* =i : ｉ番目の窓口のサービス終了 */
/**************************************************/
int Next()
{
int sw = -1;
double t = end; // シミュレーション終了時刻で初期設定
// 次の客の到着時刻
if (at >= 0.0 && at < t) {
sw = 0;
t = at;
}
// サービス終了時刻
for (int i1 = 0; i1 < s; i1++) {
if (sb[i1] > 0 && st_e[i1] <= t) {
sw = i1 + 1;
t = st_e[i1]; // 窓口i1のサービス終了時刻
}
}
return sw;
}
/**********************************/
/* 終了処理 */
/* return : =-1 : 終了前処理 */
/* =-2 : 実際の終了 */
/**********************************/
int End_o_s()
{
int sw = -2;
p_time = end; // 現在時刻
at = -1.0; // 次の客の到着時刻
for (int i1 = 0; i1 < s; i1++) {
if (sb[i1] > 0) { // サービス中の客はいるか？
if (sw == -2) {
sw = -1;
end = st_e[i1]; // 窓口i1のサービス終了時刻
}
else {
if (st_e[i1] > end)
end = st_e[i1]; // 窓口i1のサービス終了時刻
}
}
}
return sw;
}
/****************************/
/* 客の到着処理 */
/* ct : 客リストの先頭 */
/****************************/
void Arrive()
{
/*
客数の増加と次の客の到着時刻の設定
*/
nc += 1; // 到着客数カウンタ
p_time = at; // 現在時刻
at = p_time + Next_at(); // 次の客の到着時刻
if (at >= end)
at = -1.0;
/*
系内客数の処理
*/
c_sc_t += cus.size() * (p_time - sc_t); // 系内客数にその数が継続した時間を乗じた値の累計
sc_t = p_time; // 現在の系内客数になった時刻
if (cus.size()+1 > m_sc)
m_sc = cus.size() + 1; // 最大系内客数
/*
窓口に空きがない場合
*/
if (asb == 0) {
Customer ct_p = new Customer(-1, p_time);
cus.put(new Integer(nc), ct_p); // 客の登録（系内客数）
c_lq_t += que.size() * (p_time - lq_t); // 待ち行列長にその長さが継続した時間を乗じた値の累計
que.add(new Integer(nc)); // 客の登録（待ち行列）
lq_t = p_time; // 現在の待ち行列長になった時刻
if (que.size() > m_lq)
m_lq = que.size(); // 最大待ち行列長
}
/*
すぐサービスを受けられる場合
*/
else {
int k = -1;
for (int i1 = 0; i1 < s && k < 0; i1++) {
if (sb[i1] == 0) {
Customer ct_p = new Customer(i1, p_time);
cus.put(new Integer(nc), ct_p); // 客の登録（系内客数）
k = i1;
sb[k] = nc; // サービスを受けている客番号
st_e[k] = p_time + Next_sv(); // 窓口kのサービス終了時刻
asb -= 1; // 空いている窓口数
}
}
st_s[k] = p_time; // 窓口kがふさがった時刻
if (asb == 0)
asb_t = p_time; // すべての窓口がふさがった時刻
}
}
/*********************************/
/* サービス終了時の処理 */
/* k : サービス終了窓口番号 */
/* ct : 客リストの先頭 */
/*********************************/
void Service(int k)
{
/*
時間の設定
*/
k -= 1;
p_time = st_e[k]; // 現在時刻
st_e[k] = -1.0; // サービス終了時間
/*
系内客数の処理
*/
c_sc_t += cus.size() * (p_time - sc_t); // 系内客数にその数が継続した時間を乗じた値の累計
sc_t = p_time; // 現在の系内客数になった時刻
/*
滞在時間の処理
*/
Customer ct = cus.get(new Integer(sb[k]));
double x1 = p_time - ct.time;
c_sys += x1; // 滞在時間の累計
if (x1 > m_sys)
m_sys = x1; // 最大滞在時間
cus.remove(new Integer(sb[k])); // 客の削除（系内客数）
/*
窓口使用時間の処理
*/
asb += 1; // 空いている窓口数
sb[k] = 0; // 窓口kを空き状態にする
c_sb[k] += (p_time - st_s[k]); // 窓口kがふさがっている時間の累計
/*
待ち行列がある場合
*/
if (que.size() > 0) {
asb -= 1; // 開いている窓口数
c_lq_t += que.size() * (p_time - lq_t); // 待ち行列長にその長さが継続した時間を乗じた値の累計
int n = que.pollFirst().intValue(); // 客の削除（待ち行列）
lq_t = p_time; // 現在の待ち行列長になった時刻
ct = cus.get(new Integer(n));
x1 = p_time - ct.time;
c_wt += x1; // 待ち時間の累計
if (x1 > m_wt)
m_wt = x1; // 最大待ち時間
k = -1;
for (int i1 = 0; i1 < s && k < 0; i1++) {
if (sb[i1] == 0) {
k = i1;
sb[k] = n; // 窓口kの客番号
st_e[k] = p_time + Next_sv(); // 窓口kのサービス終了時刻
st_s[k] = p_time; // 窓口kがふさがった時刻
ct.state = k; // 客の状態変更
}
}
}
/*
待ち行列がない場合
*/
else {
if (asb == 1)
c_asb += (p_time - asb_t); // すべての窓口がふさがっている時間の累計
}
}
/************************/
/* 結果の出力 */
/* （カッコ内は理論値） */
/************************/
void Output()
{
double rn = (double)nc;
double rs = (double)s;
double ram = 1.0 / m_a;
double myu = 1.0 / m_s;
double rou = ram / (rs * myu);
double p0, pi;
if (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));
}
double Lq = pi * rou / (1.0 - rou);
double L = Lq + rs * rou;
double Wq = Lq / ram;
double W = Wq + 1.0 / myu;
System.out.printf("シミュレーション終了時間＝%.3f 客数＝%d ρ＝%.3f ｐ0＝%.3f\n",
p_time, nc, rou, p0);
System.out.printf(" すべての窓口が塞がっている割合＝%.3f (%.3f)\n",
c_asb/p_time, pi);
System.out.printf(" 各窓口が塞がっている割合\n");
for (int i1 = 0; i1 < s; i1++)
System.out.printf(" %d %.3f\n", i1+1, c_sb[i1]/p_time);
System.out.printf(" 平均待ち行列長＝%.3f (%.3f) 最大待ち行列長＝%d\n",
c_lq_t/p_time, Lq, m_lq);
System.out.printf(" 平均系内客数 ＝%.3f (%.3f) 最大系内客数 ＝%d\n",
c_sc_t/p_time, L, m_sc);
System.out.printf(" 平均待ち時間 ＝%.3f (%.3f) 最大待ち時間 ＝%.3f\n",
c_wt/rn, Wq, m_wt);
System.out.printf(" 平均滞在時間 ＝%.3f (%.3f) 最大滞在時間 ＝%.3f\n",
c_sys/rn, W, m_sys);
}
}
/************************/
/* クラスCustomerの定義 */
/************************/
class Customer
{
double time; // 到着時刻
int state; // 客の状態
// =-1 : 待ち行列に入っている
// >=0 : サービスを受けている窓口番号
/*******************/
/* コンストラクタ */
/* n : 客番号 */
/* s : 状態 */
/*******************/
Customer (int s, double t)
{
time = t;
state = s;
}
}